mlsanityData to 7 Oct 2026

GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring

arXiv 2502.04891 ↗First posted 7 Feb 2025cs.LG cs.SI stat.MLcited by 13

Not on the map. Why?

Abstract (arXiv)

Maximizing the spectral gap through graph rewiring has been proposed to enhance the performance of message-passing graph neural networks (GNNs) by addressing over-squashing. However, as we show, minimizing the spectral gap can also improve generalization. To explain this, we analyze how rewiring can benefit GNNs within the context of stochastic block models. Since spectral gap optimization primarily influences community strength, it improves performance when the community structure aligns with node labels. Building on this insight, we propose three distinct rewiring strategies that explicitly target community structure, node labels, and their alignment: (a) community structure-based rewiring (ComMa), a more computationally efficient alternative to spectral gap optimization that achieves similar goals; (b) feature similarity-based rewiring (FeaSt), which focuses on maximizing global homophily; and (c) a hybrid approach (ComFy), which enhances local feature similarity while preserving community structure to optimize label-community alignment. Extensive experiments confirm the effectiveness of these strategies and support our theoretical insights.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 34 of its 57 references that are in the map. First posted on arXiv 7 Feb 2025.

Builds on

34 of 57 references.

References · 34

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  6. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  7. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,131
  8. 2018Pitfalls of Graph Neural Network Evaluationcited by 994
  9. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  10. 2020Learning to Simulate Complex Physics with Graph Networkscited by 867
  11. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  12. 2019DeepGCNs: Can GCNs Go as Deep as CNNs?cited by 527
22 more
  1. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  2. 2023A critical look at the evaluation of GNNs under heterophily: Are we really making progress?cited by 332
  3. 2017Community Detection and Stochastic Block Modelscited by 317
  4. 2019Revisiting Graph Neural Networks: All We Have is Low-Pass Filterscited by 260
  5. 2019A Fair Comparison of Graph Neural Networks for Graph Classificationcited by 244
  6. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  7. 2022Graph neural networks for materials science and chemistrycited by 181
  8. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 117
  9. 2022Not too little, not too much: a theoretical analysis of graph (over)smoothingcited by 106
  10. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 104
  11. 2021Dirichlet Energy Constrained Learning for Deep Graph Neural Networkscited by 97
  12. 2022Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvaturecited by 96
  13. 2023Understanding Oversquashing in GNNs through the Lens of Effective Resistancecited by 94
  14. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  15. 2022Expander Graph Propagationcited by 75
  16. 2022On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networkscited by 63
  17. 2022Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyondcited by 60
  18. 2022Oversquashing in GNNs through the lens of information contraction and graph expansioncited by 52
  19. 2024Spectral Graph Pruning Against Over-Squashing and Over-Smoothingcited by 23
  20. 2022MM-GNN: Mix-Moment Graph Neural Network towards Modeling Neighborhood Feature Distributioncited by 11
  21. 2023Are GATs Out of Balance?cited by 9
  22. 2024GATE: How to Keep Out Intrusive Neighborscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 10.

13 papers.

Sort:

By area:

  1. 2026Fixed Aggregation Features Can Rival GNNscited by 2
  2. 2026Layer Embedding Deep Fusion Graph Neural Networkcited by 1
  3. 2025How do Probabilistic Graphical Models and Graph Neural Networks Look at Network Data?cited by 0
  4. 2025Memorization in Graph Neural Networkscited by 0
  5. 2025ATLAS: Adaptive Topology-based Learning at Scale for Homophilic and Heterophilic Graphscited by 0
  6. 2026Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Surveycited by 0
  7. 2026SCGNN: Semantic Consistency enhanced Graph Neural Network Guided by Granular-ball Computingcited by 0
  8. 2026RAwR: Role-Aware Rewiring via Approximate Equitable Partitioncited by 0
  9. 2026Multi-Agent Systems are Mixtures of Experts: Who Becomes an Influencer?cited by 0
  10. 2026Learn When and Where to Connect: Adaptive Virtual Nodes for Dynamic Message Passing on Graphscited by 0
  11. 2026Graph Cascades: Contagion-Based Mesoscopic Rewiring for Structure-Aware Graph Machine Learningcited by 0
  12. 2026Pair-Centric Graph Rewiring for Over-Squashing via Optimal Transport-Guided Communication Alignmentcited by 0
1 more
  1. 2026Learning the Graph and the Embedding Together: Classifier-Independent Rewiring for Heterophilic Node Classificationcited by 0