Mitigating Over-Smoothing in Graph Neural Networks via Separation Coefficient-Guided Adaptive Graph Structure Adjustment

Hanyang Meng, Jielong Yang, Li PengIJCAI 2025 · DOI

Abstract

Graph Neural Networks (GNNs) face a significant challenge known as over-smoothing, where node features from different classes converge and become indistinguishable as network depth increases. This paper introduces the Separation Coefficient ($S$), a theoretical metric designed to quantify this phenomenon. Leveraging this theory, we propose SCA-GNN, an adaptive framework that rewires the graph topology using high-confidence pseudo-labels to enhance inter-class separation while maintaining intra-class compactness. Our method also incorporates singular value stretching to prevent feature collapse. Extensive evaluations on both homogeneous and heterophilic graphs demonstrate that SCA-GNN consistently improves performance and scalability, effectively mitigating over-smoothing in deep architectures.

Introduction: The Over-Smoothing Problem

Graph Neural Networks (GNNs) have revolutionized learning on networked data through message-passing mechanisms. However, a persistent bottleneck is over-smoothing: as more layers are added, nodes aggregate information from increasingly wider neighborhoods, causing features of nodes from distinct classes to become nearly identical. This process is often compared to mixing different colors of paint until they result in a uniform gray.

Visualization of feature collapse where inter-class representations overlap.

While heuristics like skip-connections or edge-dropping provide partial relief, they lack a rigorous theoretical foundation. This work addresses this gap by providing a mathematical explanation for feature contraction and a targeted topological solution.

Theoretical Framework: The Separation Coefficient

The authors introduce the Separation Coefficient ($S$), which quantifies the ratio of the distance between class representations after message passing relative to their initial distance. A low $S$ value indicates that classes are collapsing into each other, a direct symptom of over-smoothing. The theory proves that the graph's topology is the primary driver of this contraction, suggesting that strategic structural adjustments can restore numerical stability.

Methodology: SCA-GNN

To counteract feature collapse, the proposed SCA-GNN (Separation Coefficient-Guided Adaptive GNN) employs a three-pronged approach:

  1. Adaptive Graph Rewiring: The model identifies nodes with high "prediction non-uniformity" (nodes the model is very confident about) and assigns them pseudo-labels. The graph is then rewired to favor homophilic connections (edges between nodes with the same pseudo-label) and prune heterophilic connections (edges between nodes with different pseudo-labels).
  2. Singular Value Stretching: During retraining, a mathematical "stretch" is applied to the weight matrix $W$. This ensures that its singular values remain large enough to maintain feature variance, preventing the weights themselves from contributing to collapse.
  3. Intra-class Compactness: The method balances inter-class separation with intra-class compactness. Theorem 2 in the paper provides probability bounds for this compactness, ensuring that nodes within the same class remain tightly clustered in the feature space.

Key Results and Insights

The SCA-GNN framework was evaluated on standard benchmarks (Cora, Citeseer, Pubmed) and large-scale datasets like OGBN-Arxiv.

  • Performance Gains: SCA-enhanced models consistently outperformed baselines. For instance, on the Cora dataset, accuracy rose from 80.65% to 83.53%.
  • Depth Resilience: Unlike standard GCNs, which suffer sharp performance drops beyond a few layers, SCA-GCN maintained high accuracy in deep configurations (up to 6 layers).
  • Scalability and Efficiency: On the OGBN-Arxiv dataset (1.1M+ edges), SCA-GCN achieved 73.16% accuracy, while several state-of-the-art competitors failed due to memory constraints.
Comparison of feature distributions before and after SCA-GNN adjustment.

The method also showed significant success on heterophilic graphs (e.g., Texas), where neighboring nodes naturally belong to different classes, proving that label-based rewiring is a robust strategy for noisy topologies.

Conclusion

SCA-GNN provides a theoretically grounded and computationally efficient solution to the over-smoothing problem. By focusing on the "Separation Coefficient," the method transforms the graph structure into a more discriminative topology, enabling deeper and more powerful Graph Neural Networks. Future work will explore extending this separation theory to tasks such as link prediction and community detection.

Summary updated

BibTeX
@inproceedings{meng2025mitigating,
  author = {Hanyang Meng and Jielong Yang and Li Peng},
  title = {{Mitigating Over-Smoothing in Graph Neural Networks via Separation Coefficient-Guided Adaptive Graph Structure Adjustment}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/663},
}
Figure