Learning Deep Representations for Graph Clustering
Learning Deep Representations for Graph Clustering
复制标题
DOI：
10.1609/aaai.v28i1.8916
复制
发表时间：
2014-06
影响因子：
3.4
通讯作者：
Fei Tian;Bin Gao;Qing Cui;Enhong Chen;Tie-Yan Liu
中科院分区：
文献类型：
--
作者：
Fei Tian;Bin Gao;Qing Cui;Enhong Chen;Tie-Yan Liu
最近，深度学习已成功应用于语音识别和图像分类等许多应用中。在这项工作中，我们探索了在图聚类中使用深度学习的可能性。我们提出了一种简单的方法，首先通过堆叠式自编码器学习原始图的非线性嵌入，然后在嵌入上运行$k$-means算法以获得聚类结果。我们表明，这种简单的方法具有坚实的理论基础，由于自动编码器和谱聚类之间的相似性，他们实际上优化。然后，我们证明了所提出的方法是更有效和更灵活的谱聚类。首先，自编码器的计算复杂度比谱聚类低得多：前者可以是稀疏图中节点数的线性，而后者由于特征值分解是超二次的。其次，当施加额外的稀疏性约束时，我们可以简单地使用深度学习文献中开发的稀疏自编码器;然而，实现稀疏谱方法并不简单。在各种图数据集上的实验结果表明，该方法的性能明显优于传统的谱聚类，这清楚地表明了深度学习在图聚类中的有效性。
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.