Learning Deep Representations for Graph Clustering

By Fei Tian, Bin Gao, Qing Cui, Enhong Chen, Tie-Yan Liu. 2014

684 citations recorded by the source corpus.

Recently deep learning has been successfully adopted in many applications such as speech recognition and image classification. In this work, we explore the possibility of employing deep learning in graph clustering. We propose a simple method, which first learns a nonlinear embedding of the original graph by stacked autoencoder, and then runs $k$-means algorithm on the embedding to obtain the clustering result. We show that this simple method has solid theoretical foundation, due to the similarity between autoencoder and spectral clustering in terms of what they actually optimize. Then, we demonstrate that the proposed method is more efficient and flexible than spectral clustering. First, the computational complexity of autoencoder is much lower than spectral clustering: the former can be linear to the number of nodes in a sparse graph while the latter is super quadratic due to eigenvalue decomposition. Second, when additional sparsity constraint is imposed, we can simply employ the sparse autoencoder developed in the literature of deep learning; however, it is non-straightforward to implement a sparse spectral method. The experimental results on various graph datasets show that the proposed method significantly outperforms conventional spectral clustering which clearly indicates the effectiveness of deep learning in graph clustering.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Representation & Self-Supervised Learning, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

In Representation & Self-Supervised Learning

In Graph Learning

Citations in the corpus

node2vec: Scalable Feature Learning for Networks (2016, background): “Finally, for both node and edge based prediction tasks, there is a body of recent work for supervised feature learning based on existing and novel graph-speciﬁc deep network architectures [15, 16, 17, 31, 39].”
Revisiting Semi-Supervised Learning with Graph Embeddings (2016, methodology): “Autoen-coders were used to learn graph embeddings for clustering on graphs (Tian et al., 2014).”
A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications (2017, methodology): “SDNE [20] autoencoder A DNGR [23] stacked denoising autoencoder PPMI SAE [22] sparse autoencoder D (1)A [55] CNN node sequence SCNN [118] Spectral CNN graph [119] Spectral CNN with smooth graph spectral multipliers MoNet [80] Mixture model network graph ChebNet [82] Graph CNN a.”
Joint Unsupervised Learning of Deep Representations and Image Clusters (2016, background): “In [51], the authors proposed to learn a non-linear embedding of the undirected affinity graph using stacked autoencoder, and then ran K-means in the embedding space to obtain clusters.”
Deep Neural Networks for Learning Graph Representations (2016, methodology): “Following (Tian et al. 2014), we built a graph using cosine similarity of two different instances as edge weights, and labels as ground truth.”
Permutation invariant training of deep models for speaker-independent multi-talker speech separation (2016, background): “Although this is a valid assumption on tasks such as image segmentation [13, 23], it’s only a very rough approximation on speech separation.”
Clustering with Deep Learning: Taxonomy and New Methods (2018, methodology): “In the past, dimensionality reduction (or representation learning) and clustering have been treated separately, and sequentially applied on the data (Ding and He, 2004; Tian et al., 2014; Trigeorgis et al., 2014).”
Heterogeneous Network Embedding via Deep Architectures (2015, background): “Thus, similarities between different data points can be directly measured by an appropriate metric to solve traditional tasks such as classification [37], clustering [21, 43, 45] and retrieval [10].”
Learning Graph Embedding With Adversarial Training Methods (2019, background): “A Variational Graph Encoder is deﬁned by an inference model: Here, µ = Z (2) is the matrix of mean vectors z i ; similarly log σ = f linear ( Z (1) , A | W (1) ) which share the weights W (0) with µ in the ﬁrst layer in Eq.”
A Comprehensive Survey on Community Detection With Deep Learning (2021, methodology): “( The autoencoder-based graph clustering model (GraphEn-coder) [118] was the ﬁrst approach to use an AE for graph clustering.”
Spectral Clustering with Graph Neural Networks for Graph Pooling (2019, methodology): “In (Tian et al., 2014), an autoencoder is trained to map the ith row of the Laplacian to the ith components of the first K eigenvectors.”
Deep Network Embedding for Graph Representation Learning in Signed Networks (2019, neutral): “quadratic computational complexity [20].”
Learning Community Embedding with Community Detection and Node Embedding on Graphs (2017, methodology): “With the recent development of neural networks and deep learning, node embedding is utilized to assist community detection [15, 27].”
A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning (2021, methodology): “Stacked Semi-DNR (2016) [100] Yes No MLP MLP Network embedding Pairwise constraint DIR (2017) [101] Yes Yes MLP MLP Network embedding INSNCCD (2018) [102] Yes Yes MLP MLP Network embedding Modularity maximization AAGR (2018) [103] Yes Yes MLP MLP Network embedding Adaptive parameter CDDTA (2019) [10”
UniWalk: Explainable and Accurate Recommendation for Rating and Network Data (2017, background): “Recently proposed network embedding methods [1,2,5,22,26,27] try to encode proximity structure.”
A Survey on Network Embedding (2017, methodology): “The node clustering performance is tested on three types of networks: social networks (e.g., Facebook (Traud, Mucha, and Porter 2012) and YELP (Huang and Mamoulis 2017)), citation networks (e.g., DBLP (Sun et al. 2011)), and document networks (e.g., 20-NewsGroup (Tian et al. 2014)).”
LASAGNE: Locality and Structure Aware Graph Node Embedding (2017, neutral): “ss labels [20]. The learning algorithm alternates between prediction of nodes in neighborhood as in DeepWalk and prediction of nodes having the same labels. Further related approaches can be found in [21, 22, 23, 24, 25, 26]. 2.2 Embedding Words with Word2vec Word2vec [27, 28] is a framework for lea”
SpectralNet: Spectral Clustering using Deep Neural Networks (2018, methodology): “In the context of spectral clustering, Tian et al. (2014) learn an autoencoder that maps the rows of a graph Laplacian matrix onto the corresponding spectral embedding, and then use k -means in code space to cluster the underlying data.”