# Optimalization of Parallel GNG by Neurons Assigned to Processes

Lukáš Vojáček, Pavla Dráždilová, Jiří Dvorský

► To cite this version:

Lukáš Vojáček, Pavla Dráždilová, Jiří Dvorský. Optimalization of Parallel GNG by Neurons Assigned to Processes. 16th IFIP International Conference on Computer Information Systems and Industrial Management (CISIM), Jun 2017, Bialystok, Poland. pp.63-72, 10.1007/978-3-319-59105-6_6. hal-01656222

HAL Id: hal-01656222

https://inria.hal.science/hal-01656222

Submitted on 5 Dec 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Optimalization of parallel GNG by neurons
assigned to processes

Lukáš Vojáček¹, Pavla Dráždilová², and Jiří Dvorský²

¹ IT4Innovations, VŠB - Technical University of Ostrava,

17. listopadu 15/2172, 708 33 Ostrava, Czech Republic

² Department of Computer Science, FEECS,

VŠB - Technical University of Ostrava,

17. listopadu 15/2172, 708 33 Ostrava-Poruba,

Czech Republic

lukas.vojacek@vsb.cz, pavla.drazdilova@vsb.cz, jiri.dvorsky@vsb.cz

**Abstract.** The size, complexity and dimensionality of data collections are ever increasing from the beginning of the computer era. Clustering is used to reveal structures and to reduce large amounts of raw data. There are two main issues when clustering based on unsupervised learning, such as Growing Neural Gas (GNG) [9], is performed on vast high dimensional data collection – the fast growth of computational complexity with respect to growing data dimensionality, and the specific similarity measurement in a high-dimensional space. These two factors reduce the effectiveness of clustering algorithms in many real applications. The growth of computational complexity can be partially solved using the parallel computation facilities, such as High Performance Computing (HPC) cluster with MPI. An effective parallel implementation of GNG is discussed in this paper, while the main focus is on minimizing of interprocess communication. The achieved speed-up was better than previous approach and the results from the standard and parallel version of GNG are same.

**Keywords:** growing neural gas, high-dimensional dataset, high performance computing, MPI

# 1 Introduction

The size and complexity of data collections are ever increasing from the beginning of the computer era, while the dimensionality of the data sets is rapidly increasing in recent years. Contemporary and especially future technologies allow us to acquire, store and process large high dimensional data collections. High dimensional data collections are commonly available in areas like medicine, biology, information retrieval, web analysis, social network analysis, image processing, financial transaction analysis and many others.

Clustering, considered the most important unsupervised learning problem, is used to reveal structures, to identify “natural” groupings of the data collections
and to reduce large amounts of raw data by categorizing in smaller sets of similar items.

There are two main issues when clustering based on unsupervised learning, such as *Growing Neural Gas* (GNG) [9], is performed on vast high dimensional data collection:

1. The fast growth of computational complexity with respect to growing data dimensionality, and

2. The specific similarity measurement in a high-dimensional space, where the expected distance, computed by Euclidean metrics to the closest and to the farthest point of any given point, shrinks with growing dimensionality [2].

These two factors reduce the effectiveness of clustering algorithms on the above-mentioned high-dimensional data collections in many real applications.

The growth of computational complexity can be partially solved using the parallel computation facilities, such as *High Performance Computing* (HPC) cluster with MPI. Obviously, it is necessary to resolve technical and implementation issues specific to this computing platform. An effective parallel implementation of GNG is discussed in this paper, while the main focus is on minimizing of interprocess communication.

# 2 Artificial Neural Networks

## 2.1 Related Works

The methods based on Artificial Neural Networks (ANN) are highly computationally expensive. There are different approaches on how to improve effectivity of these methods. The one possibility is to improve computation. The authors of this paper [3] propose two optimization techniques that are aimed at an efficient implementation of the GNG algorithm internal structure. Their optimizations preserve all properties of the GNG algorithm. The first technique enhances the nearest neighbor search using a space partitioning by a grid of rectangular cells and the second technique speeds up the handling of node errors using the lazy evaluation approach.

The next possibility for how to improve effectivity methods based on ANN is parallelization. In the paper [4] the authors combine the batch variant of the GNG algorithm with the MapReduce paradigm resulting in a GNG variant suitable for processing large data sets in scalable, general cluster environments. The paper [16] is focused on the actualizations of neurons weights in the learning phase of parallel implementation of SOM. There are two extremal update strategies. Using the first strategy, all necessary updates are done immediately after processing one input vector. The other extremal choice is used in Batch SOM - updates which are processed at the end of whole epoch and authors study update strategies between these two extremal strategies.

For parallelization is often use Graphics Processing Units (GPU). In the paper [1] authors present the results of different parallelization approaches to the
GNG clustering algorithm. They especially investigated the GPU and multi-core CPU architectures. Authors in the paper [12] explore an alternative approach for the parallelization of growing self-organizing networks, based on an algorithm variant designed to match the features of the large-scale, ne-grained parallelism of GPUs, in which multiple input signals are processed simultaneously. The paper [15] describes the implementation and analysis of a network-agnostic and convergence-invariant coarse-grain parallelization of the deep neural network (DNN) training algorithm. The coarse-grain parallelization is achieved through the exploitation of the batch-level parallelism. This strategy is independent from the support of specialized and optimized libraries. Therefore, the optimization is immediately available for accelerating the DNN training. The proposal is compatible with multi-GPU execution without altering the algorithm convergence rate.

## 2.2 Growing Neural Gas

The principle of this neural network is an undirected graph which need not be connected. Generally, there are no restrictions on the topology. The graph is generated and continuously updated by competitive Hebbian Learning [8, 13]. According to the pre-set conditions, new neurons are automatically added and connections between neurons are subject to time and can be removed. GNG can be used for vector quantization by finding the code-vectors in clusters [7], clustering data streams [6], biologically influenced [14] and 3D model reconstruction [10]. GNG works by modifying the graph, where the operations are the addition and removal of neurons and edges between neurons.

To understand the functioning of GNG, it is necessary to define the algorithm. The algorithm described in our previous article [17] is based on the original algorithm [5] [7], but it is modified for better continuity in the SOM algorithm. The description of the algorithm has been divided for convenience into two parts. Here is the Algorithm 1 which describes one iteration.

*Remark* The notation used in the paper is briefly listed in Table 1.

# 3 Parallelization

In the paper [17] we have dealt with the parallelization of GNG. The following is a brief description of our parallelization algorithm.

After analysing the GNG learning algorithm we identified the one most time-consuming processor area. This part was selected as a candidate for the possible parallelization. The selected area are:

**Finding BMU** – this part of GNG learning can be significantly accelerated by dividing the GNG output layer into smaller pieces – distribution of neurons for effective parallelization. Each piece is then assigned to an individual computation process. The calculation of the Euclidean distance among the
<table><caption>**Table 1.** Notation used in the paper</caption><thead><tr><th>Symbol</th><th>Description</th></tr></thead><tbody><tr><td><i>M</i></td><td>Number of input vectors</td></tr><tr><td><i>n</i></td><td>Dimension of input vectors, number of input neurons, dimension of weight vectors in GNG output layer neurons</td></tr><tr><td><i>N</i></td><td>Current number of neurons in GNG output layer</td></tr><tr><td><i>N</i><sub>max</sub></td><td>Maximum allowed number of neurons in GNG output layer</td></tr><tr><td><i>n</i><sub>i</sub></td><td><i>i</i>-th input neuron, <i>i</i> = 1, 2, ..., <i>n</i></td></tr><tr><td><i>N</i><sub>i</sub></td><td><i>i</i>-th output neuron, <i>i</i> = 1, 2, ..., <i>N</i></td></tr><tr><td><b><i>e</i></b><sub><i>ij</i></sub></td><td>edge between neurons <i>N</i><sub><i>i</i></sub> and <i>N</i><sub><i>j</i></sub> for some <i>i</i>, <i>j</i> = 1, ..., <i>N</i>, where <i>i</i> ≠ <i>j</i>.</td></tr><tr><td><b>E</b></td><td>set of all edges in GNG</td></tr><tr><td><b>G</b></td><td>undirected graph describing topology of GNG, <i>G</i>(<b>N</b><sub>1</sub>, ..., <b>N</b><sub><i>N</i></sub>), <b>E</b></td></tr><tr><td><i>t</i></td><td>Current epoch, <i>t</i> = 1, 2, ..., <i>T</i></td></tr><tr><td><b>X</b></td><td>Set of input vectors, <i>X</i> ⊂ ℝ<sup><i>n</i></sup></td></tr><tr><td><b><i>x</i></b>(<i>t</i>)</td><td>Current input vector in epoch <i>t</i>, arbitrarily selected vector from set <i>X</i><br><i>x</i>(<i>t</i>) ∈ <i>X</i>, <b><i>x</i></b>(<i>t</i>) = (x<sub>1</sub>, x<sub>2</sub>, ..., x<sub><i>n</i></sub>)</td></tr><tr><td><b><i>w</i></b><sub><b><i>k</i></b></sub>(<i>t</i>)</td><td>Weight vector of neuron <b>N</b><sub><b><i>k</i></b></sub>, <i>k</i> = 1, 2, ..., <i>N</i><br><b><i>w</i></b><sub><b><i>k</i></b></sub>(<i>t</i>) ∈ ℝ<sup><i>n</i></sup>, <b><i>w</i></b><sub><b><i>k</i></b></sub>(<i>t</i>) = (w<sub>1k</sub>, w<sub>2k</sub>, ..., w<sub><i>nk</i></sub>)</td></tr><tr><td><b>N</b><sub>c1</sub></td><td>The first Best Matching Unit (<i>BMU</i><sub>1</sub>), winner of learning competition</td></tr><tr><td><b>N</b><sub>c2</sub></td><td>The second Best Matching Unit (<i>BMU</i><sub>2</sub>), the second best matching neuron in learning competition</td></tr><tr><td><b>w</b><sub>c1</sub>(<i>t</i>)</td><td>Weight vector of <i>BMU</i><sub>1</sub></td></tr><tr><td><b>w</b><sub>c2</sub>(<i>t</i>)</td><td>Weight vector of <i>BMU</i><sub>2</sub></td></tr><tr><td><i>l</i><sub>c1</sub></td><td>Learning factor of <i>BMU</i><sub>1</sub></td></tr><tr><td><i>l</i><sub>nc1</sub></td><td>Learning factor of <i>BMU</i><sub>1</sub> neighbours</td></tr><tr><td><i>e</i><sub><i>i</i></sub></td><td>Local error of output neuron <b>N</b><sub><i>i</i></sub>, <i>i</i> = 1, 2, ..., <i>N</i></td></tr><tr><td><i>α</i></td><td>Error <i>e</i><sub><i>i</i></sub> reduction factor</td></tr><tr><td><i>β</i></td><td>Neuron error reduction factor</td></tr><tr><td><i>γ</i></td><td>Interval of input patterns to add a new neuron</td></tr><tr><td><i>a</i><sub>max</sub></td><td>Maximum edges age</td></tr><tr><td><i>a</i><sub><i>ij</i></sub></td><td>Age of edge <b><i>e</i></b><sub><i>ij</i></sub></td></tr><tr><td><i>p</i></td><td>Number of processes.</td></tr><tr><td><i>V</i><sub><i>i</i></sub></td><td>Set of neurons assigned to <i>Process</i><sub><i>i</i></sub>.</td></tr><tr><td><i>V</i></td><td>Set of neurons in the GNG.</td></tr></tbody></table>
**Algorithm 1** One iteration of the Growing Neural Gas algorithm

1. Find neurons BMUs $N_{c1}$ and $N_{c2}$.

2. Update the local error $e_{c1}$ of neuron $N_{c1}$

$$e_{c1} = e_{c1} + \|w_{c1} - x\|^2 \qquad (1)$$

3. Update the weight vector $w_{c1}$ of neuron $N_{c1}$

$$w_{c1} = w_{c1} + l_{c1}(x - w_{c1}) \qquad (2)$$

4. For all neurons $N_k$ where exists edge $e_{c1k}$ ($N_{c1}$ neighbourhood)

(a) Update the weights $w_k$ using $l_{nc1}$ learning factor

$$w_k = w_k + l_{nc1}(x - w_k) \qquad (3)$$

(b) Increase age $a_{kc1}$ of edge $e_{c1k}$

$$a_{kc1} = a_{kc1} + 1 \qquad (4)$$

5. If there is no edge between neurons $N_{c1}$ and $N_{c2}$, then create such edge. If the edge exists, the age is set to 0.

6. If any edge has reached the age of $a_{max}$, it is removed.

7. If there is a neuron without connection to any edge, the neuron is then removed.

8. If the number of processed input vectors in the current iteration has reached the whole multiple of the value $\gamma$ and the maximum allowed number of output neurons is not reached, add a new neuron $N_{N+1}$. The location and error of the new neuron is determined by the following rules:

(a) Found neuron $N_b$ (NBE) which has the biggest error $e_b$.

(b) Found neuron $N_c$ (NSE) among neighbours of neuron $N_b$ and has the biggest error $e_c$ among these neighbours.

(c) Create a new neuron $N_{N+1}$ and the value of $w_n$ is set as:

$$w_{N+1} = \frac{1}{2}(w_b + w_c) \qquad (5)$$

(d) Creating edges between neurons $N_b$ and $N_{N+1}$, and also between neurons $N_c$ and $N_{N+1}$.

(e) Removed edge between neurons $N_b$ and $N_c$.

(f) Reduction of error value in neurons $N_b$ and $N_c$ using the multiplying factor $\alpha$. Error for neuron $N_{N+1}$ is equal to the new error of neuron $N_b$.

individual input vector and all the weight vectors to find BMU in a given part of the GNG output layer is the crucial point of this part of GNG learning. Each process finds its own partial BMU in its part of the GNG output layer. Each partial BMU is then compared with other BMUs obtained by other processes. Information about the BMU of the whole network is then transmitted to all the processes to perform the updates of the BMU neighbourhood.
**Updates of weights** – update weights of edges incident with $N_{c1}$ it is quickly in the event that the neighboring nodes to $N_{c1}$ are on a same process. This part can theoretically accelerate if we move adjacent nodes on a single process. Unfortunately, the transfer node for multidimensional data is very time consuming (test data have a dimension of 8000+).

A detailed description of our parallelization process is described in Fig. 1.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Parallel Algorithm</figcaption></figure>

The parallelization of GNG learning was performed on an HPC cluster, using *Message Passing Interface* (MPI) technology. MPI technology is based on effective communication between processes. That means that one application can run on many cores. The application uses MPI processes which run on individual cores. The processes are able to send and receive messages and data, communicate etc. Detailed information about HPC and MPI technology is provided, for example, in [11].<fnref n="3" />

**3.1 Distribution Neurons for Effective Parallelization**

In the paper [17] we used Method 1 (the equal distribution of neurons), where new neurons are allocated to the process with the lowest number of neurons (see Figure 2). The advantage of this distribution is constant workload processes. The disadvantage is increased communication between processes.

<footnote n="3">³ A specification of MPI is available on the web: http://www.mpi-forum.org/</footnote>
<figure><img src="image_3.png" /><figcaption>Fig. 2. Add the new neuron to the next free Process_j by a cyclic way - Method1.</figcaption></figure>

Our goal is to focus on reducing interprocessor communication by using the following methods for adding new neuron:

Method 2 The neurons are gradually added to the process, which currently does not contain a predetermined number of neurons ($\frac{N_{max}}{p}$). If one process is filled up so a new neuron is added to the next process (see Figure 3).

<figure><img src="image_4.png" /><figcaption>Fig. 3. Add the new neuron to the Process_x by gradual way - Method2.</figcaption></figure>

Method 3 The start is similar to Method 1. If $|V_i| \ge 2 \forall i \le p$ then add $N_{new}$ to Process_i where ($N_{c1} \in V_i$ and $|V_i| \le \frac{N_{max}}{p}$) or add $N_{new}$ to Process_k where ($N_{c2} \in V_k$ and $|V_k| \le \frac{N_{max}}{p}$) or add $N_{new}$ to the next free Process_j (see Figure 4).

<figure><img src="image_5.png" /><figcaption>Fig. 4. Add the new neuron to the Process_x where is $N_{c1}$ or $N_{c2}$ - Method3.</figcaption></figure>
# 4 Experiments

## 4.1 Experimental Datasets and Hardware

One dataset was used in the experiments. The dataset was commonly used in Information Retrieval – *Medlars*.

**Medlars Dataset** The Medlars dataset consisted of 1,033 English abstracts from a medical science⁴. The 8,567 distinct terms were extracted from the Medlars dataset. Each term represents a potential dimension in the input vector space. The term's level of significance (weight) in a particular document represents a value of the component of the input vector. Finally, the input vector space has a dimension of 8,707, and 1,033 input vectors were extracted from the dataset.

**Experimental Hardware** The experiments were performed on a Linux HPC cluster, named Anselm, with 209 computing nodes, where each node had 16 processors with 64 GB of memory. Processors in the nodes were Intel Sandy Bridge E5-2665. Compute network is InfiniBand QDR, fully non-blocking, fat-tree. Detailed information about hardware is possible to find on the web site of Anselm HPC cluster⁵.

## 4.2 The Experiment

The experiment was oriented towards a comparison of the parallel GNG algorithm and parallel by modification by assignment to processes. The Medlars dataset was used for the experiment. A parallel version of the learning algorithm was run using 2, 8, 16, 24, 32 and 64 MPI processes. The records with an asterisk (*) represents the results for only one process i.e. this is the original serial learning algorithm and there is no network communication.

GNG parameters are the same for all experiments and are as follows $γ = 200$, $e_w = 0.05$, $e_n = 0.006$, $α = 0.5$, $β = 0.0005$, $a_{max} = 88$, M = 2021, $δ = 1500$. The achieved computing time is presented in Table 2.

As we can see from Table 2 and Fig. 5, the computing time depends on the number of used cores as well. With a growing number of processors, the computation effectiveness increases, and the computational time is sufficiently reduced (in the paper [17] we used Method 1).

# 5 Conclusion

In this paper the parallel implementation of the GNG neural network algorithm is presented. The achieved speed-up was better than our previous approach.

⁴ The collection can be downloaded from ftp://ftp.cs.cornell.edu/pub/smart. The total size of the dataset is approximately 1.03 MB.

⁵ https://support.it4i.cz/docs/anselm-cluster-documentation/hardware-overview
<table><caption>**Table 2.** Computing Time with Respect to Number of Cores, Standard GNG Algorithm, Dataset Medlars</caption><thead><tr><th rowspan="2">Cores</th><th colspan="3">Computing Time [mm:ss]</th></tr><tr><th>Method 1</th><th>Method 2</th><th>Method 3</th></tr></thead><tbody><tr><td>1*</td><td></td><td>35:41</td><td></td></tr><tr><td>4</td><td>09:36</td><td>10:28</td><td>10:41</td></tr><tr><td>8</td><td>06:59</td><td>06:25</td><td>06:52</td></tr><tr><td>16</td><td>05:53</td><td>06:18</td><td>06:37</td></tr><tr><td>24</td><td>07:29</td><td>05:33</td><td>05:35</td></tr><tr><td>32</td><td>07:42</td><td>07:13</td><td>07:17</td></tr></tbody></table>

<figure><img src="image_6.png" /><figcaption>**Fig. 5.** Graph of Computing Time with Respect to Number of Cores, Standard GNG Algorithm, Dataset Medlars</figcaption></figure>

However, the effectiveness of a parallel solution is dependent on the division of the output layer. the authors introduced three different methods of neuron assignment to processes, where better acceleration for the new approaches was achieved. these approaches reached the best time but speed up is not too significant for the selected data set. Our methods are focusing on the different ways of assigning a new neuron in the GNG to processes for parallel computation.

In future work we intend to focus on the sparse data, use combinations of neural networks for improved result and improved acceleration.

**Acknowledgement** This work was supported by The Ministry of Education, Youth and Sports from the Large Infrastructures for Research, Experimental Development and Innovations project “IT4Innovations National Supercomputing
Center LM2015070" and by Grant of SGS No. SP2017/100 "Parallel processing of Big Data 4", VŠB-Technical University of Ostrava, Czech Republic.

References

1. Adam, A., Leuoth, S., Dienelt, S., Benn, W.: Performance gain for clustering with growing neural gas using parallelization methods. In: ICEIS (2). pp. 264–269 (2010)

2. Beyer, K., Goldstein, J., Ramakrishnan, R., Shaft, U.: When is “nearest neighbor” meaningful? In: Database Theory ’99. vol. 1540, pp. 217–235 (1999)

3. FišEr, D., Faigl, J., Kulich, M.: Growing neural gas efficiently. Neurocomputing 104, 72–82 (2013)

4. Fliege, J., Benn, W.: Mapreduce-based growing neural gas for scalable cluster environments. In: Machine Learning and Data Mining in Pattern Recognition, pp. 545–559. Springer (2016)

5. Fritzke, B.: A growing neural gas network learns topologies. In: Advances in Neural Information Processing Systems 7. pp. 625–632. MIT Press (1995)

6. Ghesmoune, M., Lebbah, M., Azzag, H.: A new growing neural gas for clustering data streams. Neural Networks 78, 36–50 (2016)

7. Holmström, J.: Growing Neural Gas Experiments with GNG, GNG with Utility and Supervised GNG. Master’s thesis, Uppsala University (2002-08-30)

8. Martinetz, T.: Competitive hebbian learning rule forms perfectly topology preserving maps. In: Gielen, S., Kappen, B. (eds.) ICANN ’93, pp. 427–434. Springer London (1993)

9. Martinetz, T., Schulten, K.: A “neural-gas” network learns topologies. Artificial Neural Networks 1, 397–402 (1991)

10. Orts-Escolano, S., Garcia-Rodriguez, J., Serra-Perez, J.A., Jimeno-Morenilla, A., Garcia-Garcia, A., Morell, V., Cazorla, M.: 3d model reconstruction using neural gas accelerated on gpu. Applied Soft Computing 32, 87–100 (2015)

11. Pacheco, P.: Parallel Programming with MPI. Morgan Kaufmann, 1st edn. (1996)

12. Parigi, G., Stramieri, A., Pau, D., Piastra, M.: A multi-signal variant for the gpu-based parallelization of growing self-organizing networks. In: Informatics in Control, Automation and Robotics, pp. 83–100. Springer (2014)

13. Prudent, Y., Ennaji, A.: An incremental growing neural gas learns topologies. In: Neural Networks, 2005. IJCNN ’05. Proceedings. 2005 IEEE International Joint Conference on. vol. 2, pp. 1211–1216 vol. 2 (2005)

14. Sledge, I., Keller, J.: Growing neural gas for temporal clustering. In: Pattern Recognition, 2008. ICPR 2008. 19th International Conference on. pp. 1–4 (2008)

15. Tallada, M.G.: Coarse grain parallelization of deep neural networks. SIGPLAN Not. 51(8), 1:1–1:12 (2016)

16. Vojáček, L., Dráždilová, P., Dvorský, J.: Self organizing maps with delay actualization. In: IFIP International Conference on Computer Information Systems and Industrial Management. pp. 154–165. Springer (2015)

17. Vojáček, L., Dvorský, J.: Growing neural gas–a parallel approach. In: Computer Information Systems and Industrial Management. pp. 408–419. Springer (2013)