Technical Summary: Breaking Structural Isolation in Scalable Graph Clustering

1. Problem Statement

Unsupervised graph clustering is essential for uncovering semantic patterns in large-scale networks. While Graph Contrastive Learning (GCL) has shown promise, existing methods face a critical bottleneck known as "structural isolation" during mini-batch training. Traditional sampling strategies (random or local neighborhood-based) often sever global community contexts, fragmenting cohesive semantic clusters into disparate batches. This isolation prevents models from capturing the global topological distribution, leading to fragmented representations that fail to reflect underlying structural organization. Furthermore, existing structure-aware methods often rely on noisy, unrefined graph statistics, while contrastive frameworks lack mechanisms to compensate for sampling-induced fragmentation. The core challenge is reconciling the trade-off between computational scalability (requiring mini-batch processing) and structural integrity (requiring global community awareness).

2. Methodology: The SCISE Framework

The authors propose SCISE (Scalable unsupervised graph Clustering framework preserving structural Integrity), which synergizes community-aware sampling with constrained structural entropy. The framework operates in two stages: preprocessing and representation learning.

2.1 Structural Entropy Community Constraint (SECC)

To address the issue of over-segmentation and local optima common in greedy structural entropy minimization, SCISE introduces a community cardinality constraint.

• Mechanism: Instead of merging nodes until no entropy reduction is possible, SECC optimizes structural entropy within a bounded solution space defined by a target community count ($N_{comm}$).
• Process: It initializes with singleton communities and iteratively merges pairs based on structural entropy changes ($\Delta H$). If the target count is not reached but no entropy-decreasing pairs remain, the algorithm relaxes the strict descent condition to force merges, ensuring convergence to exactly $N_{comm}$ cohesive groups.
• Outcome: This generates a stable set of community anchors that serve as structural priors for downstream tasks, preventing the formation of excessive micro-communities.

2.2 Community-Aware Sampling Expansion (CSampE)

To mitigate structural isolation during mini-batch training, CSampE adaptively expands the initial batch of sampled nodes.

• Mechanism: For each seed node in a batch, the algorithm identifies its corresponding community (derived from SECC) and expands the batch to include critical topological structures from that community.
• Dual-Track Strategy:
  • Small Communities ($|c(v)| \le \theta$): Performs full-community expansion to restore local topology entirely within a single training step.
  • Large Communities ($|c(v)| > \theta$): Executes random walks within the community to extract a "structural backbone" (nodes with high visitation frequency), preventing memory explosion while preserving key connectivity.
• Outcome: This bridges the gap between isolated nodes and their global community context, restoring topological continuity required for stable optimization.

2.3 Structural Contrastive Learning (StructCL)

To refine representations without incurring quadratic computational costs, SCISE employs a structural contrastive learning module.

• Mechanism: Instead of treating all nodes in a community as positive pairs, StructCL constructs a structural affinity matrix ($A^*$) based on random walk visitation frequencies within the expanded batch.
• Loss Function: It defines a multi-positive InfoNCE loss where positive pairs are determined by non-zero entries in $A^*$. This guides the encoder to align embeddings with latent structural similarities rather than raw adjacency.
• Outcome: The model learns high-order structural representations that are inherently aware of community topology, maximizing consistency among structurally similar nodes.

2.4 Overall Optimization

The pipeline integrates these components: SECC pre-processes the graph to generate community maps; CSampE expands mini-batches during training; StructCL optimizes the GCN encoder using the refined structural affinities; and a final K-means clustering is applied to the global embeddings.

3. Key Contributions

1. SCISE Framework: A scalable unsupervised clustering framework that harmonizes computational efficiency with structural integrity through the synergy of community-aware sampling and constrained structural entropy.
2. CSampE Mechanism: A novel sampling strategy that breaks "structural isolation" by adaptively incorporating global community contexts into mini-batches, effectively restoring topological continuity.
3. SECC Operator: A constrained structural entropy operator that explicitly quantifies community compactness, mitigating partition fragmentation and ensuring global community integrity without requiring exhaustive hyperparameter searches for the optimal community number.
4. StructCL Module: A contrastive learning approach that refines edge weights based on intra-batch structural similarity, guiding the encoder to learn in a higher-order structural space.

4. Experimental Results

The authors evaluated SCISE on six benchmark datasets (Photo, Computers, Pubmed, Ogbn-arxiv, Reddit, Ogbn-products), ranging from medium-scale to millions of nodes.

• Performance: SCISE achieved state-of-the-art (SOTA) results in 21 out of 24 metrics across all datasets, significantly outperforming ten baselines (including DGI, S3GC, DMoN, and MAGI). Notable improvements include a 3.25% increase in NMI and a 17.08% increase in F1-score on Ogbn-arxiv.
• Scalability: Unlike many competitors that encounter Out-of-Memory (OOM) errors on large graphs (e.g., Reddit, Ogbn-products), SCISE scales efficiently. Runtime analysis shows near-linear growth with graph size, and the entire pipeline for a 2.45M node graph completes in under 8 hours.
• Ablation Studies: Removing any of the three core components (SECC, CSampE, StructCL) led to performance degradation. CSampE was identified as the most critical component for large-scale graphs, with its removal causing significant drops in ARI (e.g., from 37.66% to 21.15% on Ogbn-arxiv).
• Robustness:
  • Noise: SCISE remained stable even when 20% of community priors were randomly corrupted.
  • Sparsity: The framework maintained clustering quality even when up to 80% of edges were removed, outperforming baselines that suffered dramatic collapses on sparse graphs.
  • Hyperparameters: The model demonstrated low sensitivity to variations in merge speed ($p$), community number ($N_{comm}$), and learning rates.

5. Significance and Claims

The paper claims that SCISE effectively resolves the "structural isolation" issue inherent in mini-batch training for large-scale graphs. By integrating structural entropy constraints with community-aware sampling, the framework preserves global topological awareness without sacrificing scalability.

The authors emphasize that:

• Global Awareness: Unlike existing scalable methods that lose global context, SCISE maintains topological integrity through CSampE, allowing the model to learn cohesive community structures.
• Practicality: The SECC preprocessing step introduces negligible overhead (seconds to minutes) compared to the training time, making the framework viable for real-world deployment on million-node graphs.
• Robustness: The framework is robust to noisy community priors and graph sparsification, suggesting that community-aware structural guidance is a powerful, resilient mechanism for unsupervised learning.

The work concludes that integrating community-level structural information is fundamental for high-performance graph clustering at scale, and that reliable structural priors can effectively mitigate sampling-induced information loss. Future work is proposed to extend these techniques to ultra-large benchmarks (e.g., Ogbn-papers100M) and develop adaptive sampling strategies.