# ASIL: Augmented Structural Information Learning for Deep Graph Clustering in Hyperbolic Space

arXiv: https://arxiv.org/abs/2504.09970 · HTML: https://mlsanity.com/paper/2504.09970/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 50 of its 78 references that are in the map.
- First posted on arXiv 14 Apr 2025.

## Builds on (most cited first, 30 of 50)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Class-Balanced Loss Based on Effective Number of Samples](https://mlsanity.com/paper/1901.05555/) (2019)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Unsupervised Deep Embedding for Clustering Analysis](https://mlsanity.com/paper/1511.06335/) (2015)
- [Contrastive Multi-View Representation Learning on Graphs](https://mlsanity.com/paper/2006.05582/) (2020)
- [Deep Graph Contrastive Representation Learning](https://mlsanity.com/paper/2006.04131/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Hyperbolic Graph Convolutional Neural Networks](https://mlsanity.com/paper/1910.12933/) (2019)
- [Hyperbolic Graph Neural Networks](https://mlsanity.com/paper/1910.12892/) (2019)
- [Spherical Fourier Neural Operators: Learning Stable Dynamics on the Sphere](https://mlsanity.com/paper/2306.03838/) (2023)
- [Towards Unsupervised Deep Graph Structure Learning](https://mlsanity.com/paper/2201.06367/) (2022)
- [Constant Curvature Graph Convolutional Networks](https://mlsanity.com/paper/1911.05076/) (2019)
- [Fully Hyperbolic Neural Networks](https://mlsanity.com/paper/2105.14686/) (2021)
- [Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature](https://mlsanity.com/paper/2211.15779/) (2022)
- [Deep Graph Clustering via Dual Correlation Reduction](https://mlsanity.com/paper/2112.14772/) (2021)
- [Hyperspherical Prototype Networks](https://mlsanity.com/paper/1901.10514/) (2019)
- [Multi-view Contrastive Graph Clustering](https://mlsanity.com/paper/2110.11842/) (2021)
- [ProGCL: Rethinking Hard Negative Mining in Graph Contrastive Learning](https://mlsanity.com/paper/2110.02027/) (2021)
- [Lorentzian Graph Convolutional Networks](https://mlsanity.com/paper/2104.07477/) (2021)
- [From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering](https://mlsanity.com/paper/2010.00402/) (2020)
- [Structural Entropy Guided Graph Hierarchical Pooling](https://mlsanity.com/paper/2206.13510/) (2022)
- [A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challenges](https://mlsanity.com/paper/2403.04468/) (2024)
- [Differentiating through the Fr'echet Mean](https://mlsanity.com/paper/2003.00335/) (2020)
- [Dink-Net: Neural Clustering on Large Graphs](https://mlsanity.com/paper/2305.18405/) (2023)
- [SE-GSL: A General and Effective Graph Structure Learning Framework through Structural Entropy Optimization](https://mlsanity.com/paper/2303.09778/) (2023)
- [Graph Communal Contrastive Learning](https://mlsanity.com/paper/2110.14863/) (2021)

## Built on by (most cited first, 4 of 4)

- [Multi-Domain Riemannian Graph Gluing for Building Graph Foundation Models](https://mlsanity.com/paper/2603.00618/) (2026)
- [Beyond the Academic Monoculture: A Unified Framework and Industrial Perspective for Attributed Graph Clustering](https://mlsanity.com/paper/2603.20829/) (2026)
- [Riemannian Geometry Speaks Louder Than Words: From Graph Foundation Model to Next-Generation Graph Intelligence](https://mlsanity.com/paper/2603.21601/) (2026)
- [Are Common Substructures Transferable? Riemannian Graph Foundation Model with Neural Vector Bundles](https://mlsanity.com/paper/2606.03270/) (2026)

## Abstract (arXiv)

Graph clustering is a longstanding topic in machine learning. Recently, deep methods have achieved results but still require predefined cluster numbers K and struggle with imbalanced graphs. We study deep graph clustering without K considering realistic imbalance through structural information theory. In the literature, structural information is rarely used in deep clustering, and its classic discrete definition neglects node attributes while exhibiting prohibitive complexity. In this paper, we establish a differentiable structural information framework, generalizing the discrete formalism to the continuous realm. We design a hyperbolic model (LSEnet) to learn the neural partitioning tree in the Lorentz model. Theoretically, we demonstrate its capability in clustering without K and identifying minority clusters. Second, we refine hyperbolic representations to enhance graph semantics. Since tree contrastive learning is non-trivial and costs quadratic complexity, we advance our theory by discovering that structural entropy bounds the tree contrastive loss. Finally, we approach graph clustering through a novel augmented structural information learning (ASIL), which offers an efficient objective to integrate hyperbolic partitioning tree construction and contrastive learning. With a provable improvement in graph conductance, ASIL achieves effective debiased graph clustering in linear complexity. Extensive experiments show ASIL outperforms 20 strong baselines by an average of +12.42% in NMI on the Citeseer dataset.