Research map / Graph learning / GNN architectures
A Signed Graph Approach to Understanding and Mitigating Oversmoothing
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Structural Balanced Propagation (SBP), a parameter-free plug-and-play method that adds signed edges (from labels or feature similarity) to promote structural balance, mitigating oversmoothing in deep GNNs up to 300 layers.
Problem
Deep GNNs suffer from oversmoothing; existing remedies (normalization, residual connections, edge dropout) lack a unified theoretical explanation, and simply adding negative edges can cause either oversmoothing or divergence.
Approach
Interprets oversmoothing remedies as implicitly adding negative edges to message passing, and uses structural balance theory to design signed graphs (Label-SBP using labels, Feature-SBP using feature similarity) with bounded (LayerNorm-constrained) propagation that converges to cluster-specific representations without oversmoothing.
Key results
- Label-SBP reaches 82.90% on Cora and 73.04% on Citeseer with a 2-layer SGC, the best among 10 baselines on those datasets.
- SBP remains effective up to 300 layers on homophilic graphs while normalization methods degrade with depth.
- On the 2-CSBM synthetic graph at depth 300, Label-SBP reaches 97.50% accuracy and Feature-SBP 80.00%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Label-SBP instead of the strongest listed baseline | 2-layer SGC · Cora | accuracy: 81.60 { $\pm$ 0.00 } -> 82.90 { $\pm$ 0.00} | Helped |
| Use Label-SBP instead of the strongest listed baseline | 2-layer SGC · Citeseer | accuracy: 72.25 { $\pm$ 0.08 } -> 73.04 { $\pm$ 0.10 } | Helped |
| Use Label-SBP instead of the strongest listed baseline | 2-layer SGC · PubMed | accuracy: 79.30 { $\pm$ 0.10 } -> 80.32 { $\pm$ 0.04 } | Helped |
| Use Feature-SBP instead of the strongest listed baseline | 2-layer SGC · Squirrel | accuracy: 48.63 { $\pm$ 0.16} -> 49.16 { $\pm$ 0.19} | Helped |
| Use SBP instead of the strongest listed baseline | 2-layer SGC · Amazon-ratings | accuracy: 42.98 { $\pm$ 0.04} -> 42.41 { $\pm$ 0.02} | Hurt |
| Use SBP instead of the strongest listed baseline | 2-layer SGC · Texas | accuracy: 59.46 { $\pm$ 8.11} -> 78.38 { $\pm$ 0.00} | Helped |
| Use SBP instead of the strongest listed baseline | 2-layer SGC · Wisconsin | accuracy: 63.73 { $\pm$ 0.98} -> 80.39 { $\pm$ 0.00} | Helped |
| Use Feature-SBP instead of the strongest listed baseline | 2-layer SGC · Cornell | accuracy: 61.89 { $\pm$ 3.91} -> 72.97 { $\pm$ 0.00} | Helped |
| Increase the training label ratio (ablation) | Label-SBP · CSBM and Cora | accuracy: null | Helped |
| Use a training label ratio of 20% (ablation) | Label-SBP · CSBM and Cora | accuracy: over 80% accuracy | Helped |
| Increase negative-edge strength β on heterophilic graphs (ablation) | SBP · CSBM, φ < 0 | accuracy: null | Helped |
| Increase negative-edge strength β on homophilic graphs (ablation) | SBP · CSBM, φ > 0 | accuracy: null | Hurt |
Surprising findings
- Adding negative edges in an unstructured way is insufficient: too-weak repulsion leads to oversmoothing and too-strong repulsion leads to divergence.
- On heterophilic graphs SBP needs repulsion strength beta greater than typical values (beta>1), while homophilic graphs favor smaller beta.
Limitations
- Not evaluated on super-large graphs due to limited computational resources.
- Focuses only on oversmoothing and classic techniques; other GNN degradation factors are not addressed.
- Label-SBP relies on ground-truth labels, and its performance depends on label ratio.
Experimental setup
Datasets: Cora Citeseer PubMed Texas Cornell Wisconsin Squirrel Amazon-ratings ogbn-arxiv CSBM
Benchmarks: Cora Citeseer PubMed Texas Cornell Wisconsin Squirrel Amazon-ratings ogbn-arxiv
Metrics: node classification accuracy
Baselines: MLP SGC BatchNorm PairNorm ContraNorm DropEdge Residual APPNP JKNET DAGNN GCNII
Builds on: SGC PairNorm ContraNorm DropEdge APPNP
Closest papers by meaning
- Structure Balance and Gradient Matching-Based Signed Graph Condensation (AAAI 2025 · similarity 0.90)
- Graph Neural Networks Do Not Always Oversmooth (NeurIPS 2024 · similarity 0.89)
- Deep Hypergraph Neural Networks with Tight Framelets (AAAI 2025 · similarity 0.88)
- Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphs (ICML 2024 · similarity 0.87)
- Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Models (NeurIPS 2025 · similarity 0.87)
- On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.