A Deep Graph Structured Clustering Network

Xunkai Li, Youpeng Hu, Yaoqi Sun, Ji Hu, Jiyong Zhang, Meixia Qu

Abstract

Graph clustering is a fundamental task in network analysis, aiming to group nodes based on both their attributes and topological structure. Traditional Graph Convolutional Networks (GCNs) often struggle with "over-smoothing" when depth is increased, limiting their ability to capture high-order relationships. This paper presents the Deep Graph Structured Clustering Network (DGSCN), which utilizes a "DenseGCN" architecture with vertex cascading and a triple self-supervised loss function to achieve state-of-the-art performance while mitigating the over-smoothing problem.

Introduction

Graph clustering—grouping nodes in a network based on both their attributes and their connections—is vital for applications ranging from recommendation engines to protein analysis. While Graph Convolutional Networks (GCNs) are powerful, they face significant hurdles in clustering tasks:

  1. Shallow Learning: Most existing models use only a few layers, preventing them from capturing complex, high-order relationships in large datasets.
  2. Over-smoothing: Increasing GCN depth often leads to node features becoming nearly identical due to repeated neighbor averaging, making clusters indistinguishable.
  3. Information Gaps: Many models fail to fully integrate the implicit interactions between a node's raw features (like text in a document) and the graph's structure (who cites whom).

Methodology

The DGSCN framework consists of four integrated modules designed to learn robust node representations for clustering.

The overall architecture of DGSCN, showing the integration of GCN and DNN auto-encoders with a triple self-supervised loss.

Integrated Modules

  • GCN Auto-encoder: Learns high-dimensional representations specifically focused on the graph's topology (structure).
  • DNN Auto-encoder: Learns representations focused on raw node features, ensuring feature integrity by temporarily ignoring graph structure.
  • DenseGCN Backbone: The core "deep" component of the network. Inspired by DenseNet in computer vision, it uses "vertex cascading" to connect each layer to all preceding layers.
  • Triple Self-supervised Module: Optimizes the network without labels by calculating a joint loss from three sources: feature reconstruction (from the DNN), topology reconstruction (from the GCN), and clustering distribution (using a KL-divergence loss to push the model toward high-confidence cluster assignments).

Alleviating Over-smoothing with DenseGCN

To overcome the over-smoothing problem, DGSCN employs a DenseGCN architecture. By using vertex cascading, the model maintains access to the "sharp" features from earlier layers even at significant depths (up to 36 layers in experiments). This acts as a memory mechanism, preventing the "graying out" effect of deep convolutions.

The DenseGCN architecture featuring vertex cascading, which allows for deeper networks by preserving feature information across layers.

Experimental Evaluation

The model was evaluated on five diverse benchmarks: Wiki, Reuters, Citeseer, DBLP, and ACM. DGSCN consistently outperformed nine baseline models, including GAE and SDCN, across metrics such as Accuracy, NMI, ARI, and F1-score.

  • Superior Accuracy: On the Citeseer dataset, DGSCN achieved an accuracy of 67.23%, outperforming the previous state-of-the-art (SDCN) at 65.96%.
  • Topology Performance: The model showed its greatest strength on the Wiki dataset, achieving 46.61% accuracy, significantly higher than the 41.21% of SDCN.
  • Stability: Unlike models that show performance fluctuations during training, DGSCN remained stable and only slightly decreased in accuracy after reaching its peak, indicating high robustness.

Conclusion

DGSCN demonstrates that deeper GCNs can significantly improve clustering performance if managed with dense connections to prevent feature washout. By combining feature-based and topology-based learning with a triple self-supervised loss, the model effectively navigates the trade-offs between depth and feature discriminability. Future work may explore adaptive processing to automatically adjust network depth based on input graph characteristics.

Summary updated

Abstract

Graph clustering is a fundamental task in data analysis and has attracted considerable attention in recommendation systems, mapping knowledge domain, and biological science. Because graph convolution is very effective in combining the feature information and topology information of graph data, some graph clustering methods based on graph convolution have achieved superior performance. However, current methods lack the consideration of structured information and the process of graph convolution. Specifically, most of existing methods ignore the implicit interaction between topology information and feature information, and the stacking of a small number of graph convolutional layers leads to insufficient learning of complex information. Inspired by graph convolutional network and auto-encoder, we propose a deep graph structured clustering network that applies a deep clustering method to graph structured data processing. Deep graph convolution is employed in the backbone network, and evaluates the result of each iteration with node feature and topology information. In order to optimize the network without supervision, a triple self-supervised module is designed to help update parameters for overall network. In our model, we exploit all information of the graph structured data and perform self-supervised learning. Furthermore, improved graph convolution layers significantly alleviate the problem of clustering performance degradation caused by over-smoothing. Our model is designed to perform on representative and indirect graph datasets, and experimental results demonstrate that our model achieves superior performance over state-of-the-art models.
BibTeX
@article{li2020deep,
  author = {Xunkai Li and Youpeng Hu and Yaoqi Sun and Ji Hu and Jiyong Zhang and Meixia Qu},
  title = {{A Deep Graph Structured Clustering Network}},
  journal = {IEEE Access},
  year = {2020},
  doi = {10.1109/access.2020.3020192},
}
Figure