Research map / Graph learning / GNN architectures
GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring
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.
Shows that minimizing the spectral gap can help GNNs when community structure aligns with labels, and proposes community-based (ComMa), feature-similarity-based (FeaSt), and hybrid (ComFy) graph rewiring methods that outperform spectral rewiring baselines on node classification.
Problem
Spectral gap maximization via graph rewiring is the standard remedy for over-squashing, but it attenuates community structure and can hurt GNN accuracy when community structure aligns with node labels; existing rewiring methods ignore graph-task alignment.
Approach
Analyze rewiring on stochastic block models to show spectral gap minimization helps under high community-label alignment, then propose rewiring that directly targets community structure (ComMa), feature similarity (FeaSt), and a hybrid that maximizes feature similarity within community-pair budgets (ComFy).
Key results
- On Cora, GCN+FeaStDel reaches 90.74% accuracy vs. 86.12% for GCN, and on Texas GCN+FeaStDel reaches 64.86% vs. 35.14%.
- With both additions and deletions, GCN+ComFy achieves best results on 7 of 9 standard datasets (e.g., Cornell 62.16%, Wisconsin 64.00%), outperforming spectral baselines.
- ComMa runs in about 0.05 s on Cora for 50 edges versus 4.69 s for FoSR and 4.30 s for ProxyAddMax.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Delete feature-similarity-ranked edges (FeaStDel) | GCN · Cora | accuracy: 86.12±0.36 -> 90.74±0.39 | Helped |
| Use community-budgeted feature-similarity edge deletion (ComFyDel) | GCN · Cornell | accuracy: 35.14±1.63 -> 70.27±1.50 | Helped |
| Use community-budgeted feature-similarity edge deletion (ComFyDel) | GCN · Chameleon | accuracy: 39.33±0.59 -> 45.51±0.76 | Helped |
| Use community-budgeted feature-similarity edge addition (ComFyAdd) | GCN · Minesweeper | accuracy: 89.49±0.07 -> 89.76±0.05 | No clear effect |
| Add edges to maximize global feature similarity (FeaStAdd) | GCN · Roman-Empire | accuracy: 70.30±0.73 -> 79.67±0.07 | Helped |
| Use FeaSt edge deletion instead of no rewiring | GCN · Texas | accuracy: 35.14±1.50 -> 64.86±1.43 | Helped |
| Use FeaSt edge deletion instead of no rewiring | GCN · Pubmed | accuracy: 85.57±0.11 -> 86.76±0.10 | Helped |
| Use FeaSt edge addition instead of no rewiring | GCN · Squirrel | accuracy: 31.69±0.42 -> 39.33±0.73 | Helped |
| Use ComFy edge addition instead of no rewiring | GCN · Actor | accuracy: 27.24±0.21 -> 32.30±0.25 | Helped |
| Use ComFy edge deletion instead of no rewiring | GCN · Wisconsin | accuracy: 38.00±1.47 -> 66.00±1.34 | Helped |
| Use FeaSt edge deletion instead of no rewiring | GCN · Citeseer | accuracy: 77.83±0.35 -> 81.60±0.39 | Helped |
| Use FeaSt edge addition instead of no rewiring | GCN · Amazon-Ratings | accuracy: 47.20±0.33 -> 49.46±0.07 | Helped |
Surprising findings
- Minimizing the spectral gap (amplifying community structure) can improve generalization when community structure aligns with node labels.
- Spectral gap maximization by edge additions on Cora and Citeseer reduces graph-task alignment and test accuracy.
Limitations
- Theory is restricted to a single-feature, one-step sum aggregation SBM proxy with normal approximations.
- Experiments use only GCN as backbone; the authors note rewiring could be combined with other GNNs but did not test this.
- ComFy is slower than ComMa and comparable to other spectral baselines in runtime.
Experimental setup
Datasets: Cora Citeseer Pubmed Cornell Texas Wisconsin Chameleon Squirrel Actor Roman-Empire Amazon-Ratings Minesweeper
Benchmarks: Cora Citeseer Pubmed Cornell Texas Wisconsin Chameleon Squirrel Actor Roman-Empire Amazon-Ratings Minesweeper
Metrics: accuracy NMI runtime (seconds)
Baselines: GCN BORF FoSR ProxyAddMin ProxyAddMax ProxyDelMin ProxyDelMax
Builds on: GCN FoSR Spectral gap proxy rewiring (ProxyAddMax/ProxyDelMax) BORF Louvain
Closest papers by meaning
- Locality-Aware Graph Rewiring in GNNs (ICLR 2024 · similarity 0.92)
- The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisited (ICLR 2025 · similarity 0.89)
- Graph Cascades: Contagion-Based Mesoscopic Rewiring for Structure-Aware Graph Machine Learning (NeurIPS 2026 · similarity 0.89)
- PANDA: Expanded Width-Aware Message Passing Beyond Rewiring (ICML 2024 · similarity 0.89)
- Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification (ICML 2025 · similarity 0.88)
- On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning (NeurIPS 2025 · similarity 0.88)
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.