GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring

Celia Rubio-Madrigal ​, Adarsh Jamadandi ​, Rebekka Burkholz ​ · 2025

Read GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring by Celia Rubio-Madrigal ​, Adarsh Jamadandi ​, Rebekka Burkholz ​ (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-04891.txt.

Description

Graph neural networks pass messages along the edges of a graph, and when too much information squeezes through a few edges, learning suffers. Rewiring the graph to widen its spectral gap is a known fix. But Rubio-Madrigal and co-authors show that narrowing the gap can sometimes help instead. Their analysis uses stochastic block models to explain when each direction works. Rewiring mainly changes how strong the community structure is, so it helps when communities line up with the labels.

Building on that insight, they propose three rewiring plans. ComMa adjusts community structure cheaply, FeaSt links nodes with similar features to raise global homophily, and ComFy mixes both. ComFy lifts local feature similarity while keeping the community layout. Wide experiments supported the theory and the value of the three plans. The work reframes rewiring as a choice about label and community alignment rather than a single gap to maximize.

Catalog record

CREATORCelia Rubio-Madrigal ​, Adarsh Jamadandi ​, Rebekka Burkholz ​
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE96 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-04891

Browse the full library · About the Tower of Babel