Hashing-Based Distributed Clustering
for Massive High-Dimensional Data

The aim of distributed clustering methods is to make clustering analysis of data discretely stored in distributed different sites without direct transmission of the original data. Therefore, the algorithm design is substantially influenced by the topological properties of site networks. Generally, there are two network paradigms that are mainly researched: peer-to-peer (P2P) networks and global-sub-site networks[15]. The main difference between them is whether there is a global site that has access to all sub-sites to collect necessary data for clustering. In the P2P paradigm, there is not such a global site, and each sub-site can only communicates with a few other sites for local clustering[15]. By contrast, the global-sub-site paradigm has a global site acting as a central server, and there is no direct communication between sub-sites. In this paper, only the global-sub-site paradigm is discussed.

In [1], Januzaj et al. proposed a DBSCAN-based distributed clustering method called DBDC. In the first step, it clusters data in the sub-sites locally by DBSCAN. In each local cluster, some core samples are selected and associated with their neighborhood parameters. These samples and parameters are sent to the global site and participate in global DBSCAN clustering to generate final clusters. Though DBDC can find latent clusters with arbitrary shapes, it also inherits the downside of DBSCAN, the sensitivity to input parameters, which means that DBDC method can only perform well when receiving proper parameters. For that matter, [16] improved DBDC and made good progress in clustering performance. On the other hand, in [17], Xu et al. used DBSCAN to process centralized clustering parallel by dividing dataset at global site into some clusters, and then used distributed machines to handle each cluster parallel. Overall, these density-based methods can find clusters with complex shapes but are highly dependent on the input parameters.

In [18], Jagannathan and Wright extended the basic clustering algorithm k-means into the distributed case. Meanwhile, privacy protection was also considered by avoiding exposure of original private data. It performs well when the data in different sites represent different attributes of common entities. Ji and Ling[9] proposed an ensemble-learning-based clustering algorithm. In this distributed k-means clustering algorithm, the entire clustering process is divided into two steps. First, every sub-site executes local k-means clustering and summarizes the centroid points of all clusters and the numbers of points in each cluster as the weights of centroid points. Then all the centroid points and their weights are sent to the global site, where another k-means clustering to centroid points is done. Based on the results of the two clusterings, sub-sites can get the final result. Essentially, the whole clustering process is composed of a 2-layer hierarchical clustering and both sub-site and global site take one of them. In [19], Balcon et al. proposed a distributed k-means clustering based on core-set of samples to process distributed data more efficiently. Jeong et al. [20] focused on biological data and modified distributed k-means algorithm. This modified algorithm can achieve outstanding performance on enormous datasets. Overall, the foregoing methods are efficient in handling distributed clustering tasks, whereas their performance is highly limited by their basis k-means algorithm.

A model-based distributed clustering algorithm based on expectation maximum (EM) method[21] was proposed by Kriegel et al. in 2005[22]. It uses a mixture of Gaussian distributions to model local data, and the parameters of distribution functions are estimated by EM method. Then, these Gaussian mixture distributions from all sub-sites are merged at the global site and form a general global model. For the concern of privacy, a modified algorithm in [18] limits data sharing between sites to preclude possible data divulging. Another algorithm referred to LDSDC[6] uses subspace Gaussian model, which is flexible to data dimension, to do local clustering at sub-sites and achieve better performance on HD datasets. But the subspace Gaussian model contains parameters whose number rises dramatically with data dimension, so the cost is still high. Furthermore, sometimes the Gaussian model cannot fit datasets well, which limits its performance. On the other hand, there are also some centralized methods aiming to directly process HD data. In [23], R Agrawal et al. proposed a grid-based algorithm CLIQUE. It divides feature space into isometric intervals in every dimension, and the grids which contain more than a certain threshold number of samples are regarded as dense cells. Then, adjacent dense cells are merged to constitute clusters in a bottom-up fashion. CLIQUE is highly dependent on proper input parameters, including threshold and grid size. Another up-bottom grid-based method WFC[24] overcomes the drawbacks of CLIQUE by using a Weber–Fechner-Law-inspired approach to calculate different scales and obtain multi-scale clustering results. However, these centralized clustering methods cannot be extended to distributed cases while maintaining their efficacy and economy.

To solve the nearest neighbor searching problem, researchers have made a wide range of endeavors to learn compact hash functions from data to preserve the distance order in original space. Y Gong et al. proposed AQBC[25], which uses cosine similarity between two samples as the measure and maps vectors into the nearest binary hypercube. In [26], Jie Gui et al. regressed semantic labels of samples to hash codes in a supervised manner and then optimized the hash codes. Many further types of research [27][28][29] have been proposed to achieve better performance. However, limited by the ability of representation, these simple hashing methods are not scalable for massive and complex datasets.

With the development of deep learning, more and more researchers are trying to apply deep neural networks to hashing algorithms, called deep hashing (DH). DH uses hashing neural networks as hash functions to map data into hash codes in an end-to-end manner. Generally, the DH methods can be divided into supervised DH and unsupervised DH, and researchers mainly focus on the supervised methods. The core issue of current supervised methods is how to measure the similarities of samples. There are three categories generally: point-wise methods, pairwise methods and ranking-based methods. CQS[30] employs a point-wise method that uses label information directly instead of similarity information. First, it generates some central hash codes with different class labels and then enforces the outputs of networks to approach the hash centers with the same labels. In [31], H Liu et al. proposed a pair-wised method DSH. It uses labels representing whether a pair of samples are semantically similar to train a hashing network by minimizing the hamming distances of the hash codes with similar labels and maximizing those with different labels. A network consisting of three convolutional layers and two following fully-connected layers is designed as the hash function of DSH. H Lai et al. proposed DNNH[32] based on the ranking method. It groups samples into triplets and encourages hash codes of more similar samples to be closer.

The supervised methods are the basis of the unsupervised ones. To compensate for the loss of label information, most unsupervised methods utilize pre-trained networks to obtain semantic information, and convert the problem into a supervised one. However, some works still chose to use data themselves for training without generating semantic information. For example, AETBH[33] and BinGAN[34] introduced self-supervised techniques into unsupervised deep hashing and used auto-encoder and generative adversarial networks as hash functions, respectively. In [35], YK Jang and NI Cho involved contrastive learning in the training of hash functions. The contrastive-learning method uses one sample to generate more inputs by adding noise randomly. The inputs deriving from the same samples should be mapped to closer hash codes. Although these unsupervised methods can generate high-quality hash codes and achieve promising performance, the computational cost is usually very high because of the heavy structure of neural networks. In distributed cases, it will result in unacceptable transmission cost, so more slight networks should be chosen. The HBDC proposed in this paper provides a feasible solution.

Unlike existing DH methods, the overall hash function for distributed clustering cannot be trained in a single machine, which means that the overhead during the training process must be considered. The transmission cost for training can be calculated as:

where $|\Theta|$ donates the number of parameters of hashing network, $N$ donates the number of iterations in the training process and a float32 data accounts for $32$ bits. $2N$ contains data transmitted in unlink and downlink communication. For simplicity, this research does not consider quantization techniques of parameters for cost reduction[36][37]. All network parameters are transmitted as original float32 datatype.

To limit the cost, we need to reduce the number of network parameters and accelerate the convergence. Centralized DH methods usually use complex networks with over millions parameters to achieve promising performance, such as ResNet50[38], while distributed training of these networks can result in enormous communication cost. Thus, in this paper, more slight and compact networks are used as hashing networks.

On the other hand, to compensate for the loss of representation ability caused by the network structure, the whole clustering is divided into two steps hierarchically. The hash codes represent the result of the first-step clustering, which means the hashing network does not have to be powerful enough to generate an end-to-end result. As shown in Fig.2, the shape information is coupled with color in the hash codes, but later clustering can group the hash codes into proper categories. In more complex datasets with more features, this can be achieved by increasing the length of hash codes $L$. In this way, a part of network function can be transferred to the second step.

In addition, to increase the convergence rate, a filter is designed to make the samples for local training more representative. The principle of selection is to make the samples as different as possible. After randomly choosing the first sample, the second one comes from the cluster with the hash code, which has the biggest hamming distance from the first one. Following this mechanism, the $i$th sample is chosen randomly from the cluster that maximizes the sum of hamming distances from the previous $i-1$ codes until the whole batch of samples is determined. An illustration of the mechanism of sample selection is shown in Fig.3

The local training of hashing network exploits the pair-wise method. After normalization, two samples are grouped together, and the model is trained by minimizing the difference between the distances of input space and hamming space, i.e.,

where $\textbf{x}_{i}^{m}$, $\textbf{x}_{j}^{m}$ donate the inputs in $m$th sub-site, $\textbf{b}_{i}^{m}=\Psi(\textbf{x}_{i}^{m};\Theta)$ donates the hash codes and $\lambda$, $t$ are hyper-parameters. Since the maximum hamming distance between hash codes is $2L$, the inputs with distances more than $2\lambda L$ reward hash function maps them to totally different codes. Thus we can encourage the hash function to yield more kinds of hash codes to use the $L$bits to the greatest extent by adjusting the parameter $\lambda$.

Because of the gradient property of sign function, the gradients of $\Theta$ cannot be obtained by back-propagating. Thus, $\tanh({\cdot})$ is used to approximate the sign function in the training part, and problem (2) is rewritten as:

where $\textbf{h}_{i}=\widetilde{\Psi}(\textbf{x}_{i};\Theta)$ donate the outputs of hashing network with the last hashing layer replaced by $\tanh({\cdot})$. This replacement is only used for upgrading neural parameters $\Theta$. After that, the sign function will be used to generate hash codes.

After the local training, the local average parameter gradients $\nabla\Theta^{m}_{n}$ are transmitted to the global site and then it can upgrade the model to the next iteration with the average:

where the parameter $l$ denote learning rate. Although we assume that all the sub-sites have the same batch size, (4) can be easily extended to some cases in that different sub-sites have different batch-size, such as online clustering. Although the batch size in each sub-site may be small, the total size of all batches can be much larger to make the model upgrade more reliable. The hashing network with updated parameters is broadcast to the sub-sites to begin the next training iteration. This iteration is repeated $N$ times to get a high-quality hash function.

After training, the sub-sites use the hashing network to transform all local data into hash codes and count the number of samples corresponding to each hash code as its degree. Compared with massive original data, the number of hash codes is much smaller, and their binary format makes it much more convenient for storage, transmission and computation. The hash codes and their degrees are sent to the global site for final clustering. In this communication, the volume of transmitted data is

where $num_{m}$ donates the number of hash codes in the $m$th sub-site. $L$ is the length of hash codes, and the degrees are transmitted as the data type float32.

Since the hash codes are actually distributed on the vertices of an $L$-dimensional cube, clustering for hash codes may not be convex. Thus, justifiably exploiting simple clustering methods on hash codes may not be reasonable. For that matter, we use the codes to generate a graph and exploit spectral clustering[39] on it. Spectral clustering is a class of clustering algorithms working on an undirected graph. It divides the vertices into a given number of clusters by cutting the edges between them. There are different methods of graph cutting, such as Radio Cut[40] and Normalized Cut[41] In this research, the Normalized Cut method is chosen, which aims to minimize the following loss function:

where $G_{1},G_{2},...,G_{k}$ are sub-graphs, $vol(\cdot)$ represents the number of vertices, and $W(G_{i},\overline{G_{i}})$ is the sum of edge weights connecting the sub-graph $G_{i}$ and its complementary sub-graph $\overline{G_{i}}$. This graph cutting can be solved by matrix analysis method, which is detailed in [41]. Note that the feasibility of spectral clustering is also enabled by the superiority of hash codes because calculating an adjacent matrix between millions of HD samples is time-consuming, while it is much easier when processing much fewer binary hash codes.

In the hash code clustering, the undirected graph $G$ is generated by the hash codes and their degree. The vertices of $G$ denote the hash codes. The weights of edges between codes are calculated by their hamming distances and the degrees of codes as follows:

The weight of an edge represents how strongly two vertices are connected, i.e., how possible these two vertices are in the same cluster. Thus, besides the reciprocal of hamming distance, the degrees of hash codes are also considered to generate the graph. The later graph cutting tries to cut the edges with low weights, and this is the same with density-based clustering methods, which partition clusters by low-density regions. Therefore, the input adjacent matrix for spectral clustering consists of the weights in (7):

In summary, a whole algorithm description is presented in Algorithm 1. It is clear that this algorithm can be modified by quick start with a pre-trained network. This can improve clustering performance, dramatically reduce the training cost, and even skip the training process. Besides, choosing suitable network structures can act as a similar role. Compared with existing distributed clustering algorithms, the HDBC is more robust to different kinds of datasets because of the selectivity of hashing networks.

One of the most important considerations of distributed algorithms is the transmission cost. In the HDBC, it consists of two parts: the cost for distributed training and for hash code transmission. According to (1) and (5), the total cost is:

The first term is different from (1) because the broadcasting of the latest parameters (the $9th$ step in Algorithm 1) is included. For simplicity, we do not consider extra quantization methods for transmitted data to reduce the cost. In (9), the size of parameter set $|\Theta|$ and the number of hash codes $num_{m}$ are two key factors influencing the cost mostly. No matter what kind of hashing network is chosen, $|\Theta|$ is $O(D)$, where $D$ is the data dimension. Traditional algorithms usually use multiple parameters to model one dimension of data[42][6], but with convolutional-pooling layers, the number of parameters in a network can be much smaller than the data dimension. On the other hand, $num_{m}$ can be controlled by setting the length of hash codes $L$ because its upper bound is $2^{L}$. By selecting proper $\lambda$ in the loss function (3), we can encourage the hash function to map data to more kinds of hash codes to make the best use of the $L$ bits. Thus $L$ can be set with a small value without unacceptable performance loss, and this part of cost can be limited. Therefore, an upper bound of the total cost is:

Except for some fixed constants, the transmission cost is $O(D)$.

Two measures are chosen to test the quality of clustering results: purity[43] and normalized mutual information (NMI)[44]. The purity counts the number of correct samples divided by the number of total number. For example, given a dataset with size $S$, assume that $\{\mathcal{C}_{1},\mathcal{C}_{2},...,\mathcal{C}_{I}\}$ and $\{\mathcal{T}_{1},\mathcal{T}_{2},...,\mathcal{T}_{J}\}$ are set of clusters and goundtruth respectively. The purity can be calculated by:

Since there is a drawback of purity when the number of clusters is small, the purity cannot evaluate the quality of clustering appropriately. An extreme example is that if all samples are grouped into one cluster, the purity will reach $1$. Thus, the NMI is also included to rule out situations like this and make performance evaluation more comprehensive. The NMI is a variant of a basic concept in information theory called mutual information. Given a set of size $S$, similarly assume that there are $I$ clusters and $J$ true clusters. Use $S_{i}$, $S^{j}$ and $S_{i}^{j}$ to represent the number of samples in cluster $i$, cluster $j$ and both of them. The NMI can be calculated by:

In addition, to evaluate the economy of methods, the data volume needed to be transmitted between sub-sites and global site is also considered as cost in the experiments.

All algorithms are tested on both synthetic datasets and real-world datasets. Following subsections demonstrate their details.

To test the representative capability of hash codes, we compare the HBDC in the distributed situation with centralized clustering algorithms to test how representative the hash codes can be. In this subsection, we conduct experiments on four datasets: WBCD, Waveform-noise, LSD and WFRND, because executing centralized clustering on big HD datasets in one machine could be very time-consuming and these four datasets are relatively small. Since spectral clustering is the downstream clustering method for HBDC, it is chosen as the centralized clustering method for comparison intuitively. In addition, we also use k-means for supplementary when spectral clustering cannot perform well.

In order to simulate the distributed situation, each dataset is distributed into ten sub-sites randomly, and the size of data at each site is larger than fifty to make sure all sites have enough data for local training. It is not difficult to extend to a more general case in reality. Even though under extreme circumstances the data in some sub-sites are very small, we can reduce their batch sizes and make the equation (4) weighted average. Besides, the structure of hashing network in this part is set as three fully connected layers. The numbers of units in the first two layers are equal to the dimension of input data and use $Relu$ as active functions. The output layer is of the length of hash codesthe with $tanh$ as an active function. This $tanh$ is replaced by $sign$ after the training part to generate binary codes.

Table 3 shows the clustering performance in terms of purity and NMI. On the later three datasets, the HDBC can outperform centralized spectral clustering. This is because the original spectral clustering is unsuitable for processing HD data. As the dimension of space grows, the distribution of samples becomes sparse and their connection becomes weak, so edge cutting may not lead to promising results. By contrast, graphs generated by shorter hash codes have edges whose weights vary with a greater scale, so the input adjacent matrix is denser. On the other hand, the weak performance on the WBCD may be attributed to the small size of the dataset. Whereas it still achieves eighty percent of the centralized case. On the WBCD and LSD, the results of k-means are better than spectral clustering. The reason is the differences between the numbers of samples in different classes are relatively large, but spectral clustering based on (6) tends to group samples evenly.

The convergence of distributed training is a substantial factor in the HBDC. We report it on five synthetic Gaussian datasets to see the convergence rate and its sensitivity to the number of sub-sites. In this subsection, the convergence is represented by the relative error ratio (RER), which is defined as:

where $\mathcal{L}$, $\mathcal{L}_{min}$ and $\mathcal{L}_{max}$ donate the value, minimum and maximum of the loss function (2), respectively.

Fig 4 shows how the RER changes as the number of iterations grows. It is clear that the number of sub-sites influences the rate of convergence significantly. In general, more sub-sites result in faster convergence. The reason is that with more sub-sites, more samples participate in training within certain iterations, so it influences the convergence in the same way as increasing batch size. But there are still differences on different datasets. For example, S5 is the most complex dataset, so subfigure (e) shows the slowest descent of the curves. Even with $100$ sub-sites, the model still takes nearly $20$ iterations for convergence, It is similar on S4 that curves representing more sub-sites fall faster. The model with $100$ sub-sites almost converges within $10$ iterations, which is faster than that on S5. Whereas, when datasets become more simple, in addition to the faster overall convergence rate, the acceleration brought by more sub-sites is not absolute. The differences between the curves become smaller gradually from (e) to (a). On the relatively simple datasets S2 and S3, the blue curves (representing the model with $80$ sub-sites) descend faster than the purple curves (representing the model with $100$ sub-sites). When it comes to S1, the model with $40$ sub-sites can converge at a high rate, and keeping increasing the number $s$ cannot bring more conspicuous benefit.

In this subsection, five state-of-the-art distributed clustering algorithms are selected deliberately, including a partition-based algorithm k-means$||$[48], two density-based algorithms DBDC[1] and LSHDDP[49], and two model-based algorithms LDSDC[6] and REMOLD[50]. We report the methods on all synthetic datasets and four HD real-world datasets: Salinas, Pavia Centre, Pavia University and MNIST.