cs.LGNov 4, 2026

Alleviating Limited Effectiveness and Multi-Class Collapse in Deep Graph-level Clustering

Authors: Xiaoyang Lin, Renchi Yang, Yuqi Chen, Xin Huang

Organizations: Hong Kong Baptist University Hong Kong SAR, China

Abstract

Given a collection of NN graphs, graph-level clustering (GLC) seeks to partition the NN graphs into semantically meaningful groups, which serves as a fundamental task in analyzing graph-structured data. While Graph Isomorphism Networks (GINs) have become the de facto encoders for GLC, they still fail to distinguish graphs due to their neglect of global topology. On top of that, existing deep clustering frameworks suffer from severe "clustering collapse" issues, particularly in imbalanced multi-class scenarios. To address these challenges, we propose S3^3GLC, a novel framework that integrates global topological characteristics with local neighborhood features for balanced GLC. Theoretically, we leverage the Hoffman-Wielandt inequality to construct Spectral Signature as a rigorous lower bound for graph edit distance (GED), providing a computationally efficient proxy for global topological features. We additionally propose a joint manifold-preserving sparse regression module to fuse Spectral Signature with Spatial Representation, eliminating noise while preserving the complementary information. Furthermore, to mitigate clustering collapse, we introduce a balanced clustering objective based on optimal transport, harnessing the Sinkhorn-Knopp normalization to enforce equipartition constraints on cluster assignments. Extensive experiments on 10 real-world datasets demonstrate that S3^3GLC significantly outperforms 15 state-of-the-art baselines, achieving remarkable improvements on benchmark datasets such as REDDIT-12K and OGBG-PPA.

Figures & tables

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Compactness and Consistency: A Conjoint Framework for Deep Graph Clustering

    Oct 8, 2026Wei Ju, Siyu Yi, Kangjie Zheng +6Low-Rank Representation LearningGraph Clustering

  2. Robust Contrastive Graph Clustering with Adaptive Local-Global Integration

    May 27, 2026Lei Zhang, Fubo Sun, Haipeng Yang +2Graph Representation LearningMulti-Scale Feature Fusion

  3. Breaking Structural Isolation: Scalable Graph Clustering via Community-Aware Sampling and Structural Entropy

    Jul 6, 2026Jingyun Zhang, Hao Peng, Jianxin Li +2Graph ClusteringGraph Contrastive Learning