Attributed Graph Clustering: A Deep Attentional Embedding Approach

Introduction

The development of networked applications has resulted in an overwhelming number of scenarios in which data is naturally represented in graph format rather than flat-table or vector format. Graph-based representation characterizes individual properties through node attributes, and at the same time captures the pairwise relationship through the graph structure. Many real-world tasks, such as the analysis of citation networks, social networks, and protein-protein interaction, all rely on graph-data mining skills. However, the complexity of graph structure has imposed significant challenges on these graph-related learning tasks, including graph clustering, which is one of the most popular topics.

Graph clustering aims to partition the nodes in the graph into disjoint groups. Typical applications include community detection Hastings 2006, group segmentation Kim et al. 2006, and functional group discovery in enterprise social networks Hu et al. 2016. Further for attributed graph clustering, a key problem is how to capture the structural relationship and exploit the node content information.

To solve this problem, more recent studies have resorted to deep learning techniques to learn compact representation to exploit the rich information of both the content and structure data Wu et al. 2019. Based on the learned graph embedding, simple clustering algorithms such as $k$-means are applied. Autoencoder is a mainstream solution for this kind of embedding-based approach Cao et al. 2016; Tian et al. 2014, as the autoencoder based hidden representation learning approach can be applied to purely unsupervised environments.

Nevertheless, all these embedding-based methods are two-step approaches. The drawback is that the learned embedding may not be the best fit for the subsequent graph clustering task, and the graph clustering task is not beneficial to the graph embedding learning. To achieve mutual benefit for these two steps, a goal-directed training framework is highly desirable. However, traditional goal-directed training models are mostly applied to the classification task. For instance, Kipf and Welling 2016 proposed graph convolutional networks for networked data. Fewer studies on goal-directed embedding methods for graph clustering exist, to the best of our knowledge.

Motivated by the above observations, we propose a goal-directed graph attentional autoencoder based attributed graph clustering framework in this paper. To exploit the interrelationship of various-typed graph data, we develop a graph attentional autoencoder to learn latent representation. The encoder exploits both graph structure and node content with a graph attention network, and multiple layers of encoders are stacked to build a deep architecture for embedding learning. The decoder on the other side, reconstruct the topological graph information and manipulates the latent graph representation. We further employ a self-training module, which takes the “confident” clustering assignments as soft labels to guide the optimizing procedure. By forcing the current clustering distribution approaching a hypothetical better distribution, in contrast to the two-step embedding learning-based methods (shown in Fig 1), this specialized clustering component simultaneously learns the embedding and performs clustering in a unified framework, thereby achieving better clustering performance. Our contributions can be summarized as follows:

We develop the first graph attention-based autoencoder to effectively integrate both structure and content information for deep latent representation learning.

We propose a new goal-directed framework for attributed graph clustering. The framework jointly optimizes the embedding learning and graph clustering, to the mutual benefit of both components.

The experimental results show that our algorithm outperforms state-of-the-art graph clustering methods.

Related Work

Graph clustering has been a long-standing research topic. Early methods have taken various shallow approaches to graph clustering. Girvan and Newman 2002 used centrality indices to find community boundaries and detect social communities. Hastings 2006 applied belief propagation to community detection and determined the most likely arrangement of communities. Many embedding learning based approaches apply an existing clustering algorithm on the learned embedding Wang et al. 2017b. To handle both content and structure information, relational topic models Sun et al. 2009; Chang and Blei 2009, co-clustering method Guo et al. 2019, and content propagation Liu et al. 2015 have also been widely used.

The limitations of these methods are that (1) they only capture either parts of the network information or shallow relationships between the content and structure data, and (2) they are directly applied on sparse original graphs. As a result, these methods cannot effectively exploit the graph structure or the interplay between the graph structure and the node content information.

In recent years, benefiting from the development of deep learning, graph clustering has progressed significantly. Many deep graph clustering algorithms employ autoencoders, adopting either the variational autoencoder Kipf and Welling 2016, sparse autoencoder Tian et al. 2014; Hu et al. 2017, adversarially regularized method Pan et al. 2019 or denoising autoencoder Cao et al. 2016 to learn deep representation for clustering. However, these methods are two-step methods, whereas the algorithm presented in this paper is a unified approach.

2 Deep Clustering Algorithms

Autoencoders have been a widely used tool in the deep learning area, especially for unsupervised learning tasks such as clustering Wang et al. 2017a and anomaly detection Zhou and Paffenroth 2017.

Deep Embedded Clustering (DEC) is a specialized clustering technique Xie et al. 2016. This method employs a stacked denoising autoencoder learning approach. After obtaining the hidden representation of the autoencoder by pre-train, the encoder pathway is fine-tuned by a defined Kullback-Leibler divergence clustering loss. Guo et al. 2017a considered that the defined clustering loss could corrupt the feature space and lead to non-representative features, so they added back the decoder and optimized the reconstruction error together with the clustering loss.

There have since then been increasing algorithms based on such deep clustering framework Dizaji et al. 2017; Guo et al. 2017b. However, as far as we know, they are only designed for data with flat-table representation. For graph data, complex structure and content information need to be carefully exploited, and goal-directed clustering for graph data is still an open problem in this area.

Problem Definition and Overall Framework

We consider clustering task on attributed graphs in this paper. A graph is represented as $G=(V,E,X)$, where $V=\{v_{i}\}_{i=1,\cdots,n}$ consists of a set of nodes, $E=\{e_{ij}\}$ is a set of edges between nodes. The topological structure of graph $G$ can be represented by an adjacency matrix $A$, where $A_{i,j}=1$ if $(v_{i},v_{j})\in E$; otherwise $A_{i,j}=0$. $X=\{x_{1};\dots;x_{n}\}$ are the attribute values where $x_{i}\in R^{m}$ is a real-value attribute vector associated with vertex $v_{i}$.

Given the graph $G$, graph clustering aims to partition the nodes in $G$ into $k$ disjoint groups $\{G_{1},G_{2},\cdots,G_{k}\}$, so that nodes within the same cluster are generally: (1) close to each other in terms of graph structure while distant otherwise; and (2) more likely to have similar attribute values.

Our framework is shown in Fig 2 and consists of two parts: a graph attentional autoencoder and a self-training clustering module.

Graph Attentional Autoencoder: Our autoencoder takes the attribute values and graph structure as input, and learns the latent embedding by minimizing the reconstruction loss.

Self-training Clustering: The self-training module performs clustering based on the learned representation, and in return, manipulates the latent representation according to the current clustering result.

We jointly learn the graph embedding and perform clustering in a unified framework, so that each component benefits the other.

Proposed Method

In this section, we present our proposed Deep Attentional Embedded Graph Clustering (DAEGC). We first develop a graph attentional autoencoder which effectively integrates both structure and content information to learn a latent representation. Based on the representation, a self-training module is proposed to guide the clustering algorithm towards better performance.

To represent both graph structure ${A}$ and node content ${X}$ in a unified framework, we develop a variant of the graph attention network Velickovic et al. 2017 as a graph encoder. The idea is to learn hidden representations of each node by attending over its neighbors, to combine the attribute values with the graph structure in the latent representation. The most straightforward strategy to attend the neighbors of a node is to integrate its representation equally with all its neighbors. However, in order to measure the importance of various neighbors, different weights are given to the neighbor representations in our layer-wise graph attention strategy:

Here, $z_{i}^{l+1}$ denotes the output representation of node $i$, and $N_{i}$ denotes the neighbors of $i$. $\alpha_{ij}$ is the attention coefficient that indicates the importance of neighbor node $j$ to node $i$, and $\sigma$ is a nonlinerity function. To calculate the attention coefficient $\alpha_{ij}$, we measure the importance of neighbor node $j$ from both the aspects of the attribute value and the topological distance.

From the perspective of attribute values, the attention coefficient $\alpha_{ij}$ can be represented as a single-layer feedforward neural network on the concatenation of $x_{i}$ and $x_{j}$ with weight vector $\overrightarrow{a}\in R^{2m^{\prime}}$:

Topologically, neighbor nodes contribute to the representation of a target node through edges. GAT considers only the 1-hop neighboring nodes (first-order) for graph attention Velickovic et al. 2017. As graphs have complex structure relationships, we propose to exploit high-order neighbors in our encoder. We obtain a proximity matrix by considering $t$-order neighbor nodes in the graph:

here $B$ is the transition matrix where $B_{ij}=1/d_{i}$ if $e_{ij}\in E$ and $B_{ij}=0$ otherwise. $d_{i}$ is the degree of node $i$. Therefore $M_{ij}$ denotes the topological relevance of node $j$ to node $i$ up to $t$ orders. In this case, $N_{i}$ means the neighboring nodes of $i$ in $M$. i.e., $j$ is a neighbor of $i$ if $M_{ij}>0$. $t$ could be chosen flexibly for different datasets to balance the precision and efficiency of the model.

The attention coefficients are usually normalized across all neighborhoods $j\in N_{i}$ with a softmax function to make them easily comparable across nodes:

Adding the topological weights $M$ and an activation function $\delta$ (here LeakyReLU is used), the coefficients can be expressed as:

We have $x_{i}=z_{i}^{0}$ as the input for our problem, and stack two graph attention layers:

in this way, our encoder encodes both the structure and the node attributes into a hidden representation, i.e., we will have $z_{i}=z_{i}^{(2)}$.

1.2 Inner product decoder:

There are various kinds of decoders, which reconstruct either the graph structure, the attribute value, or both. As our latent embedding already contains both content and structure information, we choose to adopt a simple inner product decoder to predict the links between nodes, which would be efficient and flexible:

where $\hat{A}$ is the reconstructed structure matrix of the graph.

1.3 Reconstruction loss:

We minimize the reconstruction error by measuring the difference between $A$ and $\hat{A}$:

2 Self-optimizing Embedding

One of the main challenges for graph clustering methods is the nonexistence of label guidance. The graph clustering task is naturally unsupervised and feedback during training as to whether the learned embedding is well optimized cannot therefore be obtained. To confront this challenge, we develop a self-optimizing embedding algorithm as a solution.

Apart from optimizing the reconstruction error, we input our hidden embedding into a self-optimizing clustering module which minimizes the following objective:

Where $q_{iu}$ measures the similarity between node embedding $z_{i}$ and cluster center embedding $\mu_{u}$. We measure it with a Student’s $t$-distribution so that it could handle different scaled clusters and is computationally convenient Maaten and Hinton 2008:

it can be seen as a soft clustering assignment distribution of each node. On the other hand, $p_{iu}$ is the target distribution defined as:

Soft assignments with high probability (nodes close to the cluster center) are considered to be trustworthy in $Q$. So the target distribution $P$ raises $Q$ to the second power to emphasize the role of those “confident assignments”. The clustering loss then force the current distribution $Q$ to approach the target distribution $P$, so as to set these “confident assignments” as soft labels to supervise $Q$’s embedding learning.

To this end, we first train the autoencoder without the self-optimize clustering part to obtain a meaningful embedding $z$ as described in Eq.(7). Self-optimizing clustering is then performed to improve this embedding. To obtain the soft clustering assignment distributions of all the nodes $Q$ through Eq.(11), the $k$-means clustering is performed once and for all on the embedding $z$ before training the entire model, to obtain the initial cluster centers $\mu$.

Then in the following training, the cluster centers $\mu$ are updated together with the embedding $z$ using Stochastic Gradient Descent (SGD) based on the gradients of $L_{c}$ with respect to $\mu$ and $z$.

We calculate the target distribution $P$ according to Eq.(12), and the clustering loss $L_{c}$ according to Eq.(10).

The target distribution $P$ works as “ground-truth labels” in the training procedure, but also depends on the current soft assignment $Q$ which updates at every iteration. It would be hazardous to update $P$ at every iteration with $Q$ as the constant change of target would obstruct learning and convergence. To avoid instability in the self-optimizing process, we update $P$ every 5 iterations in our experiment.

In summary, we minimize the clustering loss to help the autoencoder manipulate the embedding space using the embedding’s own characteristics and scatter embedding points to obtain better clustering performance.

3 Joint Embedding and Clustering Optimization

We jointly optimize the autoencoder embedding and clustering learning, and define our total objective function as:

where $L_{r}$ and $L_{c}$ are the reconstruction loss and clustering loss respectively, $\gamma\geq 0$ is a coefficient that controls the balance in between. It is worth mentioning that we could gain our clustering result directly from the last optimized $Q$, and the label estimated for node $v_{i}$ could be obtained as:

which is the most likely assignment from the last soft assignment distribution $Q$.

Our method is summarized in Algorithm 1. Our algorithm has the following advantages:

Interplay Exploitation. The graph attention network-based autoencoder efficiently exploits the interplay between both the structure and content information.

Clustering Specialized Embedding. The proposed self-training clustering component manipulates the embedding to improve the clustering performance.

Joint Learning. The framework jointly optimizes the two parts of the loss functions, learns the embedding and performs clustering in a unified framework.

Experiments

We used three standard citation networks widely-used for assessment of attributed graph analysis in our experiments, summarized in Table 1. Publications in the datasets are categorized by the research sub-fields.

2 Baseline Methods

We compared a total of ten algorithms with our method in our experiments. The graph clustering algorithms include approaches that use only node attributes or network structure information, and also approaches that combine both. Deep representation learning-based graph clustering algorithms were also compared.

$K$-means is the basis of many clustering methods.

Spectral clustering uses the eigenvalues to perform dimensionality reduction before clustering.

GraphEncoder Tian et al. 2014 trains a stacked sparse autoencoder to obtain representation.

DeepWalk Perozzi et al. 2014 is a structure-only representation learning method.

DNGR Cao et al. 2016 uses stacked denoising autoencoders and encodes each vertex into a low dimensional vector representation.

M-NMF Wang et al. 2017b is a Nonnegative Matrix Factorization model targeted at community-preserved embedding.

2.2 Methods Using Both Structure and Content

RMSC Xia et al. 2014 is a robust multi-view spectral clustering method. We regard structure and content data as two views of information.

TADW Yang et al. 2015 regards DeepWalk as a matrix factorization method and adds the features of vertices for representation learning.

VGAE & GAE Kipf and Welling 2016 combine graph convolutional network with the (variational) autoencoder to learn representations.

DAEGC is our proposed unsupervised deep attentional embedded graph clustering.

For representation learning algorithms such as DeepWalk, TADW and DNGR which do not specify the clustering algorithm, we learned the representation from these algorithms, and then applied the $k$-means algorithm on their respective representations, but for algorithms like RMSC which require an alternative algorithm as its clustering method, we followed their preference and used the specified algorithms.

3 Evaluation Metrics & Parameter Settings

Metrics: We use four metrics Xia et al. 2014 to evaluate the clustering result: Accuracy (ACC), Normalized Mutual Information (NMI), F-score, and Adjusted Rand Index (ARI). A better clustering result should lead to a higher values for all the metrics.

Baseline Settings: For the baseline algorithms, we carefully select the parameters for each algorithm, following the procedures in the original papers. In TADW, for instance, we set the dimension of the factorized matrix to 80 and the regularization parameter to 0.2; For the RMSC algorithm, we regard graph structure and node content as two different views of the data and construct a Gaussian kernel on them. We run the $k$-means algorithm 50 times to get an average score for all embedding learning methods for fair comparison.

Parameter Settings: For our method, we set the clustering coefficient $\gamma$ to 10. We consider second-order neighbors and set $M=(B+B^{2})/2$. The encoder is constructed with a 256-neuron hidden layer and a 16-neuron embedding layer for all datasets.

4 Experiment Results

The experiment results on the three benchmark datasets are summarized in Table 2, 3, and 4, where the bold values indicate the best performance. C, S, and C&S indicate if the algorithm uses only content, structure, or both content and structure information, respectively. We can see that our method clearly outperforms all the baselines across most of the evaluation metrics.

We can observe from these results that methods using both the structure and content information of the graph generally perform better than those using only one side of information. In the Cora dataset, for example, TADW, GAE, VGAE and our method outperform all the baselines using one side of information. This observation demonstrates that both the graph structure and node content contain useful information for graph clustering, and illustrates the significance of capturing the interplay between two-sides information.

The results of most of the deep learning models are satisfactory. The GraphEncoder and DNGR algorithm are not necessarily an improvement although they both employ deep autoencoder for representation learning. This observation may result from their neglect at the node content information.

It is worth mentioning that our algorithm significantly outperforms GAE and VGAE. On the Cora dataset for example, our method represents a relative increase of 18.97% and 29.49% w.r.t. accuracy and NMI against VGAE, and the increase is even greater on the Citeseer dataset. The reasons for this are that (1) we employ a graph attention network that effectively integrates both content and structure information of the graph; (2) Our self-training clustering component is specialized and powerful in improving the clustering efficiency.

Parameter Study: We vary the dimension of embedding from 4 neurons to 1024 and report the results in Fig 4. It can be observed from both 4(a) and 4(b) that: when adding the dimension of embedding from 4-neuron to 16-neuron, the performance on clustering steadily rises; but when we further increase the neurons of the embedding layer, the performance fluctuates, though the ACC and NMI score both remain good on the whole.

Network Visulization: We visualize the Cora dataset in a two-dimensional space by applying the t-SNE algorithm Van Der Maaten 2014 on the learned embedding during training. The result in Fig 3 demonstrates that, after training with our graph attentional autoencoder, the embedding is already meaningful. However by applying self-training clustering, the embedding becomes more evident as our training progresses, with less overlapping and each group of nodes gradually gathered together.

Conclusion

In this paper, we propose an unsupervised deep attentional embedding algorithm, DAEGC, to jointly perform graph clustering and learn graph embedding in a unified framework. The learned graph embedding integrates both the structure and content information and is specialized for clustering tasks. While the graph clustering task is naturally unsupervised, we propose a self-training clustering component that generates soft labels from “confident” assignments to supervise the embedding updating. The clustering loss and autoencoder reconstruction loss are jointly optimized to simultaneously obtain both graph embedding and graph clustering result. A comparison of the experimental results with various state-of-the-art algorithms validate DAEGC’s graph clustering performance.

References