Variational Graph Embedding and Clustering with Laplacian Eigenmaps

1 Introduction

Graphs are natural expressions to characterize the complex interactions between entities, such as social networks, citation networks, and gene interactions. Revealing the underlying structure is of significance to understanding these data. To this end, graph clustering is proposed to identify groups of nodes having a higher probability of being connected than to members of other groups. The graph clustering methods have shown its potential in many real-world applications, such as global air transportation network analysis and protein interaction analysis.

∗Corresponding Author

As a fundamental unsupervised machine learning problem, graph clustering, also called community detection, has attracted considerable research attention in the past few decades. Traditional algorithms seek to find the cluster structure based on specific criteria, e.g., modularity, normalized cut, permanence, and conductance. Among these methods, nonnegative matrix factorization (NMF) [Kuang et al., ; Li et al., 2019] and eigenvalue decomposition (EVD) are widely adopted and various approaches have been derived from them. They first map a network to embeddings in a low-dimensional latent space and then identify the structure. However, these types of embedding are linear [Yang et al., 2016] which is not only in sharp contrast to the complex relationship among nodes but also limits the embedding capacity of the model. What's more, they represent nodes with deterministic embeddings ignoring the uncertainty of the embeddings which is inherent in the relationship. For example, nodes connecting to multiple clusters, also called hubs, would be confronted with cluster contradiction between their neighboring nodes. Such discrepancy should be considered in the uncertainty of its embedding and clustering. More importantly, the pairwise relationship is the building block of the graph data. Preserving such property in the embedding would benefit the clustering task.

On the other hand, deep learning models in numerous machine learning tasks have achieved state-of-the-art performance resulted from learning effective representations in a non-linear way. As a result, some recent works try to learn a more powerful embedding by the non-linear mappings. Instead of learning the mapping in the spectral clustering, GraphEncoder [Tian et al., 2014] first introduces a sparse autoencoder to encoder the similarity matrix, and then does the k-means in embedding space to learn the clusters. Similarly, [Sun et al., 2017; Ye et al., 2018] proposes a nonnegative symmetric encoder-decoder approach to preserve the nonnegative property of embeddings like NMF. Deep nonlinear reconstruction (DNR) [Yang et al., 2016] extends the traditional modularity based clustering by reconstructing the modularity matrix with deep autoencoder, which introduces non-linear mapping in graph clustering. The better performance of these deep learning model in graph clustering demonstrates the potential of non-linear mappings. However, all of these approaches could not learn the uncertainty in the graph and well preserve the relationships in the embedding space. More importantly, the processing of indicating clusters is not inherent in the learning model, which leads to a loss of information.

To adequately capture the uncertainty and learn the implicit relationships in embedding space, the integration of probabilistic graphical models and deep clustering models is taking into consideration. Probabilistic graphical models are widely adopted to model the user-item relationships in the recommendation and generate samples in computer vision. By modeling each sample as a Gaussian distribution, probabilistic models can not only describe the sample's noise by dividing the representation into mean and covariance (i.e., the true position and the uncertainty), but also capture the implicit relationship between samples well. Very recently, [Jiang et al., 2017; Dilokthanakul et al., 2016] and [Hsu et al., 2019] explore image generation and text topic modeling by combining the Gaussian mixture model (GMM) with a variational autoencoder (VAE). They propose these generative clustering models to generate highly realistic samples from a latent cluster. And the disentanglement of covariance is to preserve the diversity in generating samples. Despite the state-of-the-art performance they gain, they are feature-based approaches dealing with samples in Euclidean space and assume i.i.d. inputs. There is not the case in graph data in which the non-i.i.d. nature arises from the complex interactions between the nodes. And directly applying these methods to the graph data in non-Euclidean space will inevitably impact the performance ignoring the pairwise characteristic of the graph. Since the structure and influence of neighborhood vary widely by the node, preserving this information from the graph space to embedding space make a better performance on clustering task possible.

To address the above challenges, we propose a neural variational model which can compress the node representation as a Gaussian distribution preserving the pairwise relationship and cluster the nodes in their generative process simultaneously. The model, called variational graph embedding and clustering with Laplacian Eigenmaps (VGECLE), is formulated as a generative model based on the variational autoencoder (VAE) framework with a Mixture-of-Gaussian prior and a Teacher-Student (T-S) like regularization. In order to model the pairwise relationship in embedding, under the Stochastic Gradient Variational Bayes (SGVB) estimator, this T-S regularization term forces the node (student) to learn a distribution closer to its neighbors' one (teacher) with respect to the similarity. By learning the embedding from each other at different train batch, we show that it is also the Laplacian Eigenmaps (LE) [Belkin and Niyogi, 2003] to some extent. Specifically, our contributions can be summarized as follows:

• We propose a variational autoencoder for graph embedding and clustering, representing each node in the graph as a Gaussian distribution to disentangle the uncertainty and the true position of embedding.
• We propose a Teacher-Student mechanism in the stochastic gradient descent training process, which preserves the pairwise relationship and makes full use of the graph information.
• Extensive experiment on real-world datasets has shown that VGECLE can significantly outperform the state-ofthe-art models.

2 RelatedWork

In this section, we briefly review the representative works in graph clustering and the graph embedding technique. The related works on probabilistic modeling are also included.

Since graph data are ubiquitous and almost feature-based data can be described by the similarity, a great deal of effort has been devoted to graph clustering over the past few decades [Fortunato, 2010]. However, there is no consensus on the formalization of the graph clustering and a variety of criteria are proposed to evaluate the quality of a network partition, such as modularity [Newman, 2006], normalized/ratio cut [Shi and Malik, 2000], permanence [Chakraborty et al., 2014] and conductance [Leskovec et al., 2010]. Spectral Clustering (SC) [von Luxburg, 2007] is one of the most widely adopted approach in graph clustering and various spectral-based approaches have been developed for graph clustering [Craddock et al., 2012; B¨uhler and Hein, 2009]. Readers can refer to [Fortunato and Hric, 2016; Javed et al., 2018] for more traditional methods and shallow models. For the deep graph clustering, GraphEncoder [Tian et al., 2014] first investigated the connection between spectral clustering and autoencoder in terms of reconstructing the normalized graph similarity matrix. And it runs k-means on the graph embeddings learned by a sparse autoencoder (SAE) to partition the graph. SAE tries to compress the information of the node neighbors or a row of the adjacency matrix into an embedding and reconstruct the original vector. [Yang et al., 2016] tried to encode the modularity matrix instead of the adjacency matrix to do clustering. [Sun et al., 2017] proposed a nonnegative encoder-decoder architecture using the same nonnegative matrix to compress and reconstruct the neighborhood and cluster nodes with the nonnegative embeddings. However, all these graph clustering methods only learn a vector for each node entangled with uncertainty and restricts the performance in the clustering task.

Graph embedding aims to compress the node representations to a low-dimensional space meanwhile preserve some specific properties of the graph, such as the proximity and node degree. Typical network embedding methods include DeepWalk [Perozzi et al., 2014], Node2vec [Grover and Leskovec, 2016] and SDNE [Wang et al., 2016]. DeepWalk learns embeddings by exploiting the co-occurrence of nodes in a random walk. SDNE learns embeddings by combining GraphEncoder with a Laplacian Eigenmaps term to preserve the pairwise relationships. Very recently, Graph2Gauss [Bojchevski and G¨unnemann, 2018] and DVNE [Zhu et al., 2018] attempt to use Gaussian distributions to represent a node to integrate uncertainty and position to embeddings.

Although graph embedding offers an effective way to obtain node representations, it still left the clustering problem unsolved. Consequently, we have to conduct clustering on the obtained embedding which does not correspond to the cluster structure of the graph. In this paper, we directly learn the clusters and the representation is the by-product, without requiring a clustering post-processing step.

3 Proposed Framework

In this section, we describe the proposed variational graph embedding and clustering with Laplacian Eigenmap (VGECLE) model. Before diving into the details of the proposed method, we first summarize the notations used in this paper. Then we present the details of VGECLE. The graphical model of the VGECLE is shown in Figure 1.

Throughout this paper, we denote scalars, vectors and matrices by lowercase letters, bold lowercase letters and bold uppercase letters respectively. A graph is denoted as G = (V,E), where V = {v1, v2, · · · , vn} is a set of n nodes and E = {eij}ni,j=1 is a set of edges. Each edge eij is associated with a weight sij ≥ 0. Only when vi and vj are not linked by an edge, sij = 0. S = {s1, s2, · · · , sn} provides the information of the neighborhood structure of each node. The neighborhood of node vi is denoted as N(vi). We aim to partition the graph into K parts, where K is given. We denote Ni = N(µi,σ2i I) as a low-dimensional Gaussian embedding for node vi, where µi,σi ∈ RD ,D ≪ n and I is the identity matrix.

Although we focus on the clustering task instead of the generative task in this model, for better understanding of the model, we follow the literature in introducing the variants of VAE with the generative process first and then the inference.

3.1 Generative Model withMixture of Gaussian Prior

Two latent variables c and z are introduced to model the MoG prior in VAE. Specifically, c is a K-way categorical discrete variable, named latent mixture-component indicator, and z is a D-dimensional continuous variable, named latent sample. Given an observed node vi and neighborhood structure x = si ∈ Rn , we aim to reconstruct the neighborhood from the latent variables. The latent variable c first sampled from its prior p(c), choosing the mixture-component/cluster. And then the latent sample z is sampled from a conditional distribution p(z|c), choosing a sample from the given component. Finally, the neighborhood is drawn from p(x|z). Assuming p(x|z) = p(x|z, c), the joint probability can be factorized as:

where α ∈ RK , ∑Kk=1 αk = 1 and Cat(α) is a categorical distribution. N(µc,σ2c I) is a Gaussian component with learnable means µc and variances σ2c . As a result, the marginal distribution of latent variable z is a MoG:

As a result, the latent variable c points out the cluster that generates the targeted neighborhood structure. In other words, the assignment of the node clustering is done according to the cluster information accompanied by itself. This good interpretability is inherent in the latent variables of the MoG model and passed to the nodes in the graph. The distribution of x is learned by a deep neural network (DNN) fθ(z) which is parametrized by θ and fθ(z) = [µx, σ2x ].

3.2 Variational Inference

Following the VAE framework [Kingma and Welling, 2013], to maximize the likelihood of the given data points is equal to maximizing its evidence lower bound (ELBO) with an inference model:

where q(z, c|x) is the inference model for approximating the intractable posterior p(z, c|x). We assume the mean-field variational family q(z, c|x) can be factorized as q(z, c|x) = q(z|x)q(c|x). The approximated posterior is a Gaussian distribution N(µz,σ2z I), where the mean µz and variance σz are also learned by a DNN gφ(x) = [µz, σ2z ]. The Gaussian embedding of node vi is the learned approximated posterior Ni = q(z|xi) = N(gφ(xi)). As for inferencing the mixturecomponent/clustering assignment, we can approximate it in a more elegant way instead of introducing another DNN. Since q(c|x) is an approximation of the true posterior p(c|x), we can achieve it by assuming p(c|z) = p(c|z, x):

where p(c|z) is the membership-weights of z in MoG and has a closed-form solution:

To sum up, we compress the graph nodes to the latent cluster and the latent distribution by variational inference DNN gφ(·), and reconstruct the graph nodes from this latent information by generative DNN fθ(·). We also call gφ(·) as an Encoder transforming the neighborhood structure si into a low-dimensional code Ni, which is a Gaussian distribution. Accordingly, fθ(·) is the Decoder interpreting the latent code/distribution Ni to reconstruct the neighborhood structure x = si.

Similar to VAE, the ELBO can be optimized by using SGVB estimator and reparameterization trick [Kingma and Welling, 2013].

where L is the number of Monte Carlo samples in evaluation, zi,l = µi + σi ⊙ ϵl and ϵl ∼ N(0, I).

3.3 Teacher-Student Mechanism

To improve the clustering performance of Gaussian embeddings and learn the pairwise relationships in the graph, we propose a Teacher-Student mechanism which can effectively distill information from graph space to embedding space. Intuitively, nodes in the same cluster would be more likely to have stronger relationships than that in other clusters. It is natural to get nodes closer in the embedding space if they are linked by an edge. However, in a stochastic gradient descent optimization scenario, the goal of updating all the non-i.i.d. node embeddings at the same time is hard to reach. Therefore, from the point of view of a single node, a node ought to seek the guidance information from its neighbors to learn a better Gaussian embedding for itself. We recruit the neighbors' Gaussian embeddings as teachers to provide information for learning. Specifically, the loss function for node vi to reach this goal is defined as follows:

where D∗(Ni, Nj ) measures the distance between two distributions and here we adopt KL divergence from Nj to Ni as the VAEs usually do. For the weighted graph, it is reasonable for student to pay more attentions to the teachers whom have a tighter connection to the student in its learning process.

All in all, we formulate the objective function of VGECLE for a single node vi as:

where β is for balancing the trade-off between reconstruction loss and the pairwise relationship.

Next, we will show the relationship between the TeacherStudent mechanism and the Laplacian Eigenmaps (LE) [Belkin and Niyogi, 2003]. In training with stochastic gradient descent, the gradient is back-propagate to optimize the loss of a single node. While training with gradient, the model will update the loss of the whole graph. In that case, the Teacher-Student termwill be formulated as follows:

While the objective function in LE adopts ℓ-2 Norm to measure the difference between vectors instead of distributions:

However, it is unpractical for VGECLE to optimize the whole graph with gradient descent, especially when dealing with the large-scale graphs.

4 Experiments

In this section, we use four benchmark real-world datasets to demonstrate the effectiveness of VGECLE. We provide quantitative comparisons of VGECLE with other state-of-the-art clustering methods in two categories: shallow models and deep learning models. The experimental results show significant improvements with respect to the baselines.

4.1 Baseline Methods

To evaluate the performance of our proposed VGECLE, we compared it with the following five baseline methods. To validate the effectiveness of deep models in graph clustering, two shallow approaches are used for comparison, i.e., k-means and Spectral Clustering. VGECLE also compares to a deep graph clustering method GraphEncoder, a representative embedding method based on autoencoder SDNE, and a variational feature-based clustering method VaDE. The detailed descriptions of these methods are listed as follows.

• k-means: This algorithm aims to partition n observations into k clusters. It assigns each observation to the cluster with the minimal distance to the others. We run the k-means algorithm taking the neighborhood structure as representation.

• Spectral Clustering [von Luxburg, 2007]: This algorithm makes use of the spectrum of the similarity matrix of the data to perform dimensionality reduction. It performs k-means on the learned eigenvector-based solutions.
• GraphEncoder [Tian et al., 2014]: This method learns a nonlinear embedding of the original graph by sparse autoencoder, and then runs the k-means algorithm on the embedding to obtain a clustering result.
• SDNE [Wang et al., 2016]: SDNE try to preserve the first and second order proximity to the embeddings. It learns a point-vector for each node using a deep autoencoder with LE regularization. We run k-means on the deterministic embeddings to acquire the clustering assignments.
• VaDE [Jiang et al., 2017]: VaDE is one of the representative feature-based variational clustering methods adopting a Mixture of Gaussian as the prior in VAE. We evaluate the effectiveness of the proposed TeacherStudent mechanism.

4.2 Datasets

To evaluate the effectiveness and efficiency of the proposed framework, we employ three networked datasets: Cora, BlogCatalog, and Flickr. All the networks are publicly available, and also undirected. The statistics of the datasets are summarized in Table 1. The detailed information is shown as follows:

• Cora: This network represents the citation relationships between scientific publications, which consists of 2708 scientific publications classified into one of seven classes.
• BlogCatalog: It is a blogger community. The network is formed according to the interaction between users. The labels represent the topic categories provided by the authors. Those users without a predefined category have been removed. There are 6 different categories.
• Flickr: It is an online platform where people can share photos. Photographers can follow each other and form a network. The labels represent the interest groups of the users. There are overall 9 different categories for Flickr1 and 195 categories for Flickr2.

4.3 EvaluationMetric

In our experiment, we perform the task of clustering. We use the unsupervised clustering accuracy (ACC) to measure the performance of VGECLE. This metric is widely used in unsupervised learning scenario.

• ACC: For the node vi, ci is the clustering result from the algorithm, and li is the ground-truth label. Then the ACC is defined as:

where n is the total number of nodes, and m is the optimal mapping function in mapping set M that can be computed by employing the KuhnMunkres algorithm. The higher the ACC value, the better the clustering performance.

4.4 Implementation

In the unsupervised clustering scenario, we are not capable of determining network structure by cross-validation on a validation set. And for a fair comparison, we use the same network architectures in all the deep learning models. So we set the network dimensions to input - 500 - 100 - D, where input is the dimension of adjacency vector aka n. As mentioned in [Kingma and Salimans, 2016], VAE-based models suffer from the reconstructed problem. The reconstruction term in ELBO is too weak to play a part at the beginning of training. Thus, pretraining is necessary. We use the autoencoder to pretrain the network and initialize the parameters for the deep models. The learning rate for Cora, BlogCatalog and Flickr2 is 0.01 and decreases every 100 epochs with a decay rate of 0.9. And The learning rate for Flickr1 is 0.001 and decreases every 100 epochs with a decay rate of 0.9. For all baseline algorithms, we simply run them 10 times and obtain the average performance.

4.5 Experiment Results

The clustering results on four datasets are summarized in Table 2. For an overview, our proposed method achieves much better clustering performances than others on each dataset.

From the results, all the deep learning methods outperform the shallow models in all datasets. Especially, the difference between Spectral Cluster and GraphEncoder in experiment and methodology analysis show that deep structures can help to obtain better representation and improve the performance in clustering. Furthermore, the deep probabilistic models, i.e. VaDE and VGECLE, also give a better results in almost all comparisons, which demonstrates the advantage of disentangling the position and the uncertainty in learning the embeddings. Taking the embedding and clustering as an integral task in learning is also superior to the two-stage learning e.g., SDNE first, then k-means. Compared with VaDE, the improvement of VGECLE validates the effectiveness of the proposed Teacher-Student mechanism and the importance of the pairwise relationship in graph clustering.

Our proposed method compresses the node representation as a Gaussian distribution while preserving the proximity of the neighborhood. It can be seen that VGECLE achieves ACC of 34.67%, 35.61%, 28.39% and 27.53% on Cora, BlogCatalog, Flickr1, Flickr2 respectively.

4.6 Effectiveness Analysis

In order to demonstrate the effectiveness of our proposed VGECLE, we design an experiment running on the BlogCatalog dataset. Specifically, we conducted five sets of experiments on graphs under different signal-to-noise ratios. We add edges inner clusters and cross clusters to adjust the ratios. The result is presented in Table 3. From the results, we have the following observations and analysis.

The results show that our proposed method achieves better performances than others. It demonstrates that our method is able to learn the complicated distribution of the dataset better. Although VGECLE and VaDE both adopt a Mixture of Gaussian as the prior in VAE, VGECLE outperforms the VaDE by 2% on average. This result testifies the effectiveness of the proposed Teacher-Student mechanism. And the pairwise relationship plays an important role in the graph clustering. And then we can see that our proposed VGECLE outperforms the GraphEncoder(GE) by 8% on average. Without taking the graph uncertainty into account, GraphEncoder is inferior to both VGECLE and VaDE in the performance

4.7 Parameter Sensitivity

In this part, we investigate how the different dimensions D of the Gaussian embedding and the different hyper-parameter β values affect the performances. Specifically, we run our approach on the BlogCatalog dataset.

As shown in Figure 2(a), we can see that the dimension of the Gaussian embedding affects the performance in ACC. With the increase of D value from 5 to 10, the performance raises. However, when the number of dimensions continuously increases, the performance is in a declining trend and fluctuates within a range and less than 0.34. The reason is that when the D value is too low, it could not capture enough structure information of the graph. While the number of dimensions is too large, it may contain more noise, leading to poor performance. It is essential to determine the appropriate number of Gaussian embedding dimensions. Therefore, we set the dimension of the embeddings to 10 in all experiments.

As for the parameter β, it is for balancing the trade-off between reconstruction loss and the pairwise relationship. Then we show how the value of β affects the clustering results in Figure 2(b) with fixed embedding dimension D = 10. When β = 0, the pairwise relationship in the graph is ignored and VGECLE is replaced by VaDE. The larger the β, the better the performance of VGECLE. Therefore, the pairwise relationship is important for VGECLE. We can see that the performance of β = 0.0001 is better than the others.

5 Conclusion

In this paper, we propose a novel probabilistic deep graph clustering framework VGECLE. Unlike the other methods in deep graph clustering, we disentangle the position and uncertainty of the graph node by representing each node as a Gaussian distribution. And we propose a Teacher-Student mechanism to preserve the pairwise relationship in the graph space to the Gaussian embeddings space. It offers an interpretable clustering assignment which is learned by the variational inference with a Mixture of Gaussian prior. We compared the clustering performance of VGECLE with baselines on 4 realworld datasets, and the experiment results show that VGECLE outperforms the other methods. Also, we conduct 5 sets of experiments on graphs under different signal-to-noise ratios to testify the effectiveness of VGECLE.

Acknowledgements

The work described in this paper was supported by the National Key R&D Program of China (2016YFB0200604), the National Natural Science Foundation of China (61722214, 11801595, 11571384), Natural Science Foundation of Guangdong (2018A030310076, 2017B030311001) and CCF Opening Project of Information System. Chuan Chen is corresponding author.