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

Area of Science:

• Machine Learning
• Graph Theory
• Information Theory

Background:

• Deep learning methods for graph clustering require a predefined number of clusters (K) and struggle with imbalanced graphs, particularly in identifying minority clusters.
• Existing structural information definitions in deep clustering are limited by discrete formulations, neglecting node attributes and complexity issues.

Purpose of the Study:

• To address the limitations of deep graph clustering by developing a method that does not require a predefined number of clusters (K) and can handle imbalanced graphs.
• To leverage information theory, specifically structural information, to improve deep graph clustering performance.

Main Methods:

• Developed a differentiable structural information measure and a hyperbolic deep model (LSEnet) for clustering without K.
• Refined hyperbolic representations of partitioning trees and utilized structural entropy to bound contrastive loss for enhanced graph semantics.
• Introduced Augmented Structural Information Learning (ASIL) integrating hyperbolic partitioning tree construction and contrastive learning with an augmented structural entropy objective.

Main Results:

• The proposed hyperbolic deep model (LSEnet) demonstrates capability in clustering without K and identifying minority clusters in imbalanced graphs.
• Augmented Structural Information Learning (ASIL) achieves provable improvement in graph conductance and effective debiased graph clustering.
• ASIL outperforms 20 strong baselines by an average of +12.42% in NMI on the Citeseer dataset, operating with linear complexity.

Conclusions:

• ASIL offers a novel, efficient, and effective approach to deep graph clustering, overcoming limitations of existing methods regarding K and graph imbalance.
• The integration of hyperbolic geometry and information theory provides a robust framework for graph representation and clustering.
• The method demonstrates significant performance gains and scalability, paving the way for more advanced graph clustering applications.