GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring
Authors: Celia Rubio-Madrigal
Adarsh Jamadandi
Rebekka Burkholz
Venue: ICLR 2025 Poster (2025)
Keywords: graph neural networks
over-squashing
graph rewiring
community structure
homophily
feature similarity
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose a new set of graph rewiring algorithms that take into account the community structure and/or feature similarity to enhance GNN performance.

Abstract: 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.

Published as a conference paper at ICLR 2025
GNNS GETTING COMFY: COMMUNITY AND FEATURE SIMILARITY GUIDED REWIRING
Celia Rubio-Madrigal
Adarsh Jamadandi +1.2
Rebekka Burkholz'
1 CISPA Helmholtz Center for Information Security
2 Universität des Saarlandes
ABSTRACT
Maximizing the spectral gap through graph rewiring has been proposed to en- hance the performance of paasaggg 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, improves performance when the community structure aligns with node labels. Building on this insight, we propose three distinct rewiring strategies that explicitly target community struc- ture, node labels, and their alignment: (a) community structure-based rewiring (ComMa), more computationally efficient alternative to spectral gap optimization that achieves similar goals; (b) feature similarity- cuses on maximizing global homophily; and (c) a hybrid approach (ComFy), which enhances local feature similarity while preserving community structure to optimize community aligmment. Extensive experiments confirm the effectiveness these strategies and support our theoretical insights.
rewiring (FeaSt), which fo-
INTRODUCTION
Graph Neural Networks (GNNs) are class of deep learning models that commonly adopt the paradigm of message passing (Gori et al. 2005 Scarselli et al. 2009 Bronstein et al. 2021), where information is repeatedly aggregated and diffused on the graph generate graph level representation that can be leveraged to perform either node-level (Kipf & Welling 2017; Hamilton et al. 20176] Veličković et al. 2018) or graph-level tasks (Errica et al. 2020). Although GNNs have found many applications in wide array of fields, including Chemistry (Reiser et al., 2022). Biology (Bongini cct al. 2023) and even Physics "Sanchez-Gonzaler et al., 2020; Shlomi et al. (02I), they are also known to have several limitations. For instance, GNNs can fail to distinguish simple graph structures (Leman 1968 Morris et al. Papp et al. 202T). Some other problems include over-squashing (Alon & Yahav 2021 Giovanni et al. 2023), where topological bottlenecks in the input graph desensitize the node features to information from distant nodes, and over smoothing (Li et al.) 2019)
NT & Maehara 2019 Oono & Suzuki 2020 Zhou al. 2002 Keriven 2022), where node features tend to become indistinguishable due to repeated aggregations resulting from high model depth.
A popular approach to circumvent problems like over-squashing and over-smoothing is to make the input graph more amenable to message passing by rewiring the graph. This can be based on edge curvature (Topping al. 2022 Giraldo et al. 2023 Nguyen al. 2023) or maximizing the spectral gap (Karbadkar et al. [202]] Jamadandi et al. 2024). Spectral gap maximization, however, attenuates the graph's ' community structure. As our first contribution, we point out that also minimization, and thus an amplification of community structure, can improve the performance of GNNs, and provide a systematic analysis of the scenarios where one preferred over the other. We argue that current rewiring techniques are limited in their effectiveness, as they do not account for the alignment between the nodes' ground truth labels and their cluster membership labels. If this 'graph-task' alignment is high, sometimes referred to the cluster hypothesis (Chapelle et al.) 2209),, reducing the latent community structure can be detrimental to solving a task. Similarly, if the alignment is poor, spectral gap maximization can amplify the misalignment, which still have degrading effects GNN performance.
"Equal contribution. Corresponding email: celia a. rubi o-madr ga 1 1 cca.pp

---

Published as a conference paper at ICLR 2025
We gain these insights by theoretical analysis of random graphs drawn from the Stochastic Block Model (SBM), a paradigm model of graphs with community structure, on which we define a node classification task where we control two central quantities that determine the success of GNNs; the community strength and the graph-task alignment ($.3). The main mechanism through which rewiring improves performance in this context is by adding edges between nodes that have similar features, and by removing edges between nodes with very different features, which would pollute each other's neighborhood aggregation and contribute to over-smoothing. Rewiring that improves feature similarity indirectly improves homophily, because nodes with the same label usually have more similar features. Our arguments thus align with the literature that suggests that homophily critically influences the performance of GNNs (Ma et al. 2022) and is also related to the alignment between the optimal kernel matrix and the adjacency matrix of the graph (Yang et al., 2024). To further corroborate our theoretical insight, we analyze in depth the effect of spectral rewiring on real-world graphs, and observe that the number of edges that improve the graph-task alignment (and thus homophily) correlate with the effectiveness of different spectral rewiring approaches.
To overcome the limitations of spectral rewiring, our theory and analysis provide insights into the mechanisms that influence alignment and identify feature similarity promising additional criterion to take into account. This motivates our novel graph rewiring proposals, as shown in Figure We introduce three different families of methods study the importance of both topology and homophily, in isolation as well as in combination.
The first one, ComMa, targets the strength of latent communities of the input graph: Hi Highe CCoMMa adds random intra-cluster edges and deletes inter-cluster edges, thus increas- ing the community structure. Its counterpart, LowerComMa, deletes intra-cluster edges and adds inter-cluster edges, lowering the community strength. These are randomized counterparts of the spectral methods, but they perform much faster, they only require run once a community detection algorithm at the beginning.
The second method that we propose, FeaSt, aims to maximize the global feature similarity. prioritizes edges according to this objective. It thus adds edges that increase the average similarity the most, and deletes existing edges that connect the least similar nodes. FeaSt performs especially well for highly homophilic graphs, as this procedure might help denoise the conflicting neighbourhoods. F FeaSt therefore likes to focus on graph regions that already have homophilic tendency, and further enhances this trend.
ComFy rewires edges based on feature similarity, but is able to budget the number edges according to the community they belong to, such that the effect is distributed across the graph. ComFy fares comparably well to FeaSt in homophilic settings, and outperforms other methods in heterophilic settings. Our extensive results several GNN benchmarks prove that graph rewiring cannot be purely grounded on topological criteria, but that a combination of both topology and feature similarity is helpful.
1.1 RELATED WORK
Graph rewiring. A key component for GNNs is the input graph, since it not only acts as the data for model training but is also the computational structure on which message passing (Gilmer et al. 2017) is performed. Real-world graphs, however, can be noisy and sub-optimal for downstream lasks. For example, recent studies have pointed out issues like over-squashing (Alon & Yahav] 2021 Topping et al., 2022; Giovanni et al., 2023), caused by topological bottlenecks, which affect how information is diffused. This highlights the importance of the graph topology and begs the question: how can we obtain an optimal computational structure that aligns with the downstream task? Graph rewiring has emerged as popular technique to effect changes to the edge structure. This can be done based on various criteria. For instance, Topping et al. (2022); Giraldo et al. (2023); Nguyen et al. (2023) propose to use different variants of Ricci curvature (Hamilton) 1988) to rewire the graph, while Black et al. (2023) propose the effective resistance (Chandra et al. 1996). and Banerjee et al.) (2022): Deac et al. (2022) transform the input graph into expander graph (Salez 2021 for efficient message passing. Edges can be added or deleted and even though GNNs should be able to learn to drop iask-irrelevant neighbors, trainability and expressiveness issues can limit this ability (Mustafa jet al.) [023] Mustafa & Burkhhlzz (204),, which explains why edge deletions can also help fight over-smoothing in addition over-squashing (Jamadandi al. 2024
2

---

Published as a conference paper at ICLR 2025
Sizes A, B, and C of the three edge areas:
2-cluster graph:
=
|Co [Cal
; =
|Col
|Cil
1011-101
(k)
Feast (k)
ComFy(k)
LowerComMa
HigherComka
Add
nel
Add
De
If De draw and delete Lifte k| edges
If hds, draw and add bite AJ edges
Add top
Delete bottom of sim( o) for (u.e) E
Feast/ Adid
Peast De
of sim/u, el for (u.)) E
If Add. draw and add k edges
If Dw draw and delete edges
Feast/ Add
Ri -k)
Feast Del
Lasssee -k))
mhe drew and Les -] edges
Add, draw and Jake edges
PeaSt
Pewst
Lankere .t))
Add
Figure 1: Behaviour of the proposed algorithms on a 2-cluster graph for & edge modifications. Columns denote our methods and their variants (see $ SB Rows indicate 3 edge areas used for budgeting across the graph eexcept for FeaSt, which is global. The (latent) clusters are precomputed via Louvain. ComMa randomly draws edges from all intra or all inter-cluster areas, which is equivalent to drawing from each area with proportional budget in expectation. This insight is translated to ComFy, but the edges are not drawn randomly but prioritized similarly to FeaSt.
Spectral gap maximization. Contemporaneously. spectral-based methods such as Karhadkar et al. (2023) aim to maximize the spectral gap by edge additions, as a larger spectral gap is inherently linked to faster mixing time (Levin et al. (2066) and thus better information flow. However, this can be detrimental in the case of heterophilic graphs (Ma et al., 2022 Platonov ct al. 2023a) as
we might add edges between nodes of different labels resulting in over-smoothing (Li et al. 2019
NT & Maehara 2019 Oono & Suzuki, 2020) Zhou et al.] [202]] Keriven 2022). The spectral 2024) and this has shown to be beneficial in slowing down detrimental over-smoothing while simultaneously mitigating over- squashing, especially in heterophilic settings. Contrarily, (Arnaiz-Rodriguez et al. (2022) advocate for spectral gap minimization, but do not explain when this could be advantageous.
gap can also be maximized by deleting edges (Jamadandi et al.
Graph and task alignment. Our findings reveal that the underlying mechanism enhancing GNN performance by rewiring actually depends on whether we modify edges connecting nodes with similar or dissimilar features, that are usually associated with similar or dissimilar labels. In fact, Hussain al. (202T) take first step this direction by analysing the interplay between community and node- labels. They propose an infformationntheoretti metric, and demonstrate its impact performance by artificially creating and destroying communities in real-world graphs. This also highlights the importance of the positive influence of same-label neighbours and how different- neighbours can impair node classification performance (Chen et al. (020). We take this analysis several steps further and analyze why spectral rewiring cannot induce this alignment (Theorem
The desirability of alignment between the graph structure and the task in GNNs has been explored in the context of their training dynamics by Yang et al. (2024). This study theoretically analyzes how GNN models tend to align their Neural Tangent Kernel (NTK) matrix θ with the adjacency matrix A of the input graph. They further derive generalization bound for the NTK regime without considering node features, specifically in cases where the adjacency matrix A is well-aligned with the optimal kernel matrix @", This matrix @* precisely indicates whether a pair of nodes share the same label, making this concept of alignment similar to ours tthuuhh not explicitly referring to the graph's 's communities- and to the concept of homophily. Our theory on SBMs supports this result on GNN performance, while additionally relating it to the demoising effect of node features by their neighborhoods (Theorem 2} and considering different levels of alignment [Theorem 3).
1.2 CONTRIBUTIONS
1. Complementing the graph rewiring literature on spectral gap maximization to fight over-squashing. highlight real-world cases in which spectral gap minimization is more effective, contrary to
3

---

Published as a conference paper at ICLR 2025
C1
p q
q
C2
9
P
4
P
(a) Perfect alignment & 1.
(b) Alignment 1o
Figure 2: Adjacency matrices of (p, g)-SMM for different alignments. Shaded areas are intra- community edges drawn with probability p (except self-loops), and unshaded areas are inter- community edges drawn with probability In Figure [(a] the two communities match classes Cı (orange) and C2 (purple). In Figure 2(b) a third nodes in each community are of the opposite class.
conventional approaches. These cases characterized by high graph-task alignment (when community labels overlap with node labels).
2. Our theoretical insights on SBMs and experimental evidence identify the degree of task and graph structure alignment as the most critical underlying factor to explain when spectral gap rewiring improves a learning task. This highlights the major limitation of mpectral-based methods, which is that they cannot improve the graph-task alignment directly.
3. To overcome this limitation, motivated by our theoretical insights, we propose to integrate feature similarity into graph rewiring approaches. We explore three novel strategies study the effect of community structure and feature similarity in isolation (ComMa and FeaSt) and combination (ComFy).
4. Extensive real-world experiments confirm our previous insights, highlighting the effectiveness of feature similarity. We find that homophilic graphs tend to benefit most from maximizing global feature similarity FeaSt, while heterophilic graphs gain most from a hybrid approach, ComFy, y. that maximizes feature similarity while respecting the community structure.
CONCEPTUAL ANALYSIS
2.1 SPECTRAL REWIRING AFFECTS COMMUNITY STRENGTH
Spectral rewiring approaches usually focus reducing over-squashing by maximizing the spectral gap of the input graph. However, maximizing the gap has a distinct effect on its latent community structure. It is the case that, by maximizing the spectral gap. inter-community edges added and intra-community edges are deleted, which attenuates the community strength (Theorem 1
When there is high graph-task alignment, which has also been termed the cluster hypothesis (Chapelle et af.) 2009), the addition of inter-community edges likely adds more inter-class edges, while the removal of intra-community edges likely deletes many intra-class edges. Consequently, message passing happens on a less informative computational structure, rendering the rewiring detrimental the performance of any classifier (Theorem 2p. On the other hand, by minimizing the spectral gap nnter-community edges are deleted and intra- corma-cmmmuityy edges are added, which strengthens the community structure. this structure is highly aligned with the labels, the rewiring should be beneficial, as it increases feature similarity of nodes that have the same label, thus making different class nodes better separable.
To make these intuitive statements more rigorous and quantifiable, we relate community structure and node labels in a paradigmatic example community structure: the Stochastic Block Model (SBM (p, q, C)), which is random graph model with planted communities. The nodes are partitioned into communities -we adopt binary SBM (C = 2) unless explicitly stated otherwise. We can observe the form of the adjacency matrix of two-block (p, q) SBM in Figure 2) The edges are randomly sampled with probabilities p for mara-community edges and q for coterncommuntty edges. Both values critically influence the performance of GNNs sampled graph, they determine the amount
4

---

Published as a conference paper at ICLR 2025
of neighborhood aggregation. High values of p and low values of q lead to strong, pronouneed community structure. Thus, the node features after message passing tend to become more similar within communities in this setting. Similar values of q would make the community structure difficult to detect and the feature distributions of different communities would not necessarily become more distinguishable after neighborhood aggregation.
To relate this reasoning to spectral gap optimization, we first establish a direct link to the community structure in SBMs.
Theorem 1 (A less pronounced community structure corresponds to a higher spectral gap). Let G be a (p-q)-SBM with N nodes in 2 equally-sized communities and intra/inter eddee probabilities > q. Let Gddl be (pl -q)-SBM where p' < and Gudil be (p-q') J-SBM where q' > The (expected) spectral gap of G is smaller than those of Gdel and Gudd; X1 (G) < (Glel))), and X (G) < X1 (G Infat fact, the spectral gap grows approximately like p--
q+p
In summary, increasing q and decreasing p increases the spectral gap but makes the community structure less pronounced, and vice versa. The next theorem establishes how this is connected to the performance of a model that performs sum aggregation, which we use as a tractable GNN proxy.
Theorem 2 (A less pronounced community structure harms performance if high graph-task alignment), Let G be the (p-q)- from Theorem 1| Let 2; be the single feature of node i where C1 or 2; [I,,,) 1) ifts class & = c2. and l, corresponds one-to-one
I; (,,,1,1) if its class to node i's block membership. Let f be an optimal classifier on the model's s features, X, and end X) the (expected) proportion of misclassified nodes. After a step of sum aggregation, is monotonically decreasing with respect to p. and increasing with respect to q.
2.2 VARYING THE AMOUNT OF GRAPII-TASK ALIGNMENT
Theorem applies to an SBM with perfect alignment between its clusters and node labels. However, in real-world graphs, this assumption is rarely satisfied. The relationship between the task and the underlying community structure, which might not necessarily pronounced, can take more complex forms. For instance, in heterophilic settings, similar nodes do not need to be connected, effect of spectral rewiring on them is not straightforward. While spectral rewiring can influence performance by modifying how pronounced the latent community structure is, aggregation the input graph is much more effective we improve the mentioned alignment directly, which spectral rewiring fails to do.
the
This intuition is corroborated and quantified by our theory. Theorem 3) describes the behaviour of the proportion of misclassified nodes after step of neighborhood aggregation. Let 1 capture the graph-task alignment. An illustration of an SBM with vb of 1 can be found in Figure 2(b) If th = 1, we obtain the same behaviour (perfect alignment) as in Theorem 2 With e O, we obtain an SBM where the node labels are assigned oppositely to their communitics, so by renaming the communities we also have perfect alignment. For e 0.5, P(M) = (0)
so half the nodes are misclassified and this classifier is as good as a random choice. In this setup, most of the real distributions of neighbours follow binomials. For better interpretability, we have simplified the formula with normal approximations to look at the continuous trends. All nuances are derived in the proof ($A.3) which suggests that the central v parameter controls GNN performance.
Theorem 3 (The effect of different alignments on performance). Let G be the (p-9)-SBM from Theorem (pp > q). Let D; be the single feature of node where T; ~ (-11,,1) or x; ~ N(1, 1) depending on its class, and & its label, which may correspond to node i's block membership with fixed probability vt. After a step of sum aggregation, the proportion of misclassified nodes of the best classifier f approximately
X (2 1)(p 9)
P(M) Rd 1 (2 - 1)
(1 p(1 p) + q(1 9) 2(p 1 2/2 - +))
2.3 EXPERIMENTS ON SBM FOR DIFFERENT p AND g
The previously stated theorems are also supported by empirical results. Theorem I proves that maximizing the spectral gap results in weaker latent community structure, while minimization
5

---

Published as a conference paper at ICLR 2025
Correlation Matrix for SBM
Accuracy for SBM (p.q)
(0.9800
Spectral Gap-
6.3
0.6
(5, 7.0.2)
0.5
Ap-aliip-a)
(9.
0.55
0.5-
(C. (0.790.2)
(0 (0.5pp2)
Modularity
Accuracy
(0. 00..9....2
@
(0 (0.5pp.0
(..5)
Homephily-1.0
0.88
64
(0.70.2)
(8.9g00.)
0.5
(0.500 21
Homophilly
-0.87
0.88
(0.710.5
50.500.51
Spectral Gap
xp altorr
Modularty
Hom-10
Homophily
(0.59.0.2)
0.5
0/4
4.
Spectral Gap
(a) Correlation of some scores for different values of (p. 4).
(b) Accuracy of GCN trained on different (p. q) (averaged for 8 different seeds).
Figure The effects of Theorem I (for the spectral gap) and Theorems 2 3 (for accuracy) on 1000-node SBM-(p, q). Each SBM has different and q. where p {0.5. 0.7, 0.8, 0.99} and ? - (0,2, 0.5). and different alignment between the labels and the communities: {0.9, 0.95, 1}. as well as example of 0.6 alignment which gets practically null performance. The spectral gap correlates perfectly with p_g, and negatively with the community structure and the homophily with perfect alignment. Thus, it is equivalent to plot Figure ((b) with any of these as the x-axis.
p+g-
enhances it. To quantify the impact of the spectral gap on the performance, sample SBM graphs with normally distributed node features, whose means indicate their class membership. The class memberships are sampled from independent Bernoulli distributions whose probability (the alignment) depends on a node's 's community label. For different values of p and q, we train 2-layered GCN (Kipf Welling 2017) and measure the Normalized Mutual Information (NMI) (Chen al. 2019 between the ground truth labels and the predictions made by the GCN, which we show in Figure 3(
Figure ((a) furthermore validates that the spectral gap correlates with 2_ and the community 9+p strength of the SBM (negatively), as well with the graph's 'ss normalized homophily score when the alignment is perfect. When the alignment is weaker, the homophily also decreases homogeneously. In (igure(3(b) we compare the spectral gap of these different SBM graphs against the accuracy of GCN trained it, using fixed train test split.
We find that, in cases of high homophily and high alignment, it beneficial to minimize the spectral gap, as the communities that get strengthened also correspond to the task labels. However, the spectral gap does not completely correlate with the GCN accuracy, as it can only affect the community strength. We also that lack of graph-task alignment reduces the GNN performance, shown by the different hues in the scatter plot. Changing the alignment only from 1.0 to 0.95 reduces dramatically the influence of different (p, q) on the performance. But even given fixed theoretical alignment, the topology of the graph can have nuanced effects on GNN accuracy. For instance, the SBM-(0.55 0.2) has lower spectral gap (and higher homophily) than the SBM-(0.99) 0.5), although worse test performance. Yet, the latter has higher density, which means it is potentially better at denoising and obtaining better separable node representations. This observation highlights potential benefits resulting from adding edges (and thus increasing the graph density) even without considering feature similarity or graph-task alignments.
2.4 ANALYSIS OF
DATASETS
Real-world datasets usually have complex community structures and mixed alignment trends. Some parts of the graph might show good graph-task alignment while other parts do not invite for spectral- based rewiring. This makes it difficult predict when minimization maximization works best or how many edge modifications are required to see changes in GNN performance. On the one hand, very homophilic datasets might be similar to the SBM setup analyzed in the previous theorems, so spectral maximization is detrimental in the long run -as seen for Cora and Citeseer in (nfiiuure 4 where the alignment between labels and communities gets heavily reduced, and does the accuracy. On

---

Published as a conference paper at ICLR 2025
Cora Alignment vs Avg Accuracy
Citeseer - Alignment vs Avg Test Accuracy
sap Adding Slge
10
Max mire Cop rid mg rdggs
100
Average Test Accuracy
46.2
50
Accuracy
100
M1-3-
10
81-0-
500
1000
500
86.3-
70.3
80.0
1000
2000
Community
Community Labels
Figure 4: Maximizing the spectral gap (using (Jaaadandi et al., 2024 on Cora and Citeseer reduces both the graph-task alignment and the test accuracy. Labels denote the number of edge additions.
MinSap add
Chamei MinSap
Chamelcon: MinGap
Sanre
152
148
Diilwnst Sarral
-367
-50
Samee
95
41
OPPICC Same
-68
-15
-09
Drfinest
Diflreent
21
179
-42
265
99
-358
-59
Cora: MaxClap- - add
Cora: MaxGan del
Chameleon: MaxClap add
Chameleon: Maxfiap - del
Dfferent Some
Difloent L Suree
-409
Dffferntt Same
Diferentt Same
-167
-MM
464
-57
-16
-09
348
-333
Same
Diffreent
Same E.
Diffwert
Same
Different C
Samtie
Difeeent C
Randorn
Rendom del
Diftrent Same L
26
62
Difierrtt Same
-366
-38
27
70
Same
-104
-2
Different
DiffrentL
15
395
-66
-28
76
326
-385
-8
(a) Cora: additions vs. deletions
(b) Chameleon: additions vs. deletions
Figure 5: Alignment matrices for Cora (homophilic) and Chameleon (heterophilic) by a 500-edge rewiring method. In each row: spectral minimization and maximization from Jamadandi et al. (2024), and random rewiring. In each column: additions and deletions. Each alignment matrix compares the number of edges added/deleted in terms of the type of nodes it connects: with the Same or Different L(abel), and with the Same or Different C(ommunity).
the other hand, increasing connectivity might be key for some tasks, where, for example, information needs to travel across different clusters. All kinds of spectral rewiring methods can be effective for small number of edge changes, as they might locally have a denoising effect for some (lucky) edges.
However, the trend variability for spectral rewiring might be explained by the type of edges it adds or deletes, considering both the node and community labels that they connect. Figure 5 visualizes the number of edges that connect nodes with the same or different node and community labels, for spectral minimization, maximization, and random rewiring of 500 edges. for both Cora and Chameleon. We use the spectral gap optimization algorithms presented in Jamadandi et al. (2024). as they are reliable in maximizing the spectral gap for additions and deletions, and adapt them for minimization (as described in Algs. and 2). The amount of edges for each type clearly changes from the homophilic to the heterophilic case for the different methods.
In the first row (spectral gap minimization), we see that minimization adds more same- comm--cmmmuity edges than the other two methods. When adding edges in homophilic settings (Cora), this is preferred,
7

---

Published as a conference paper at ICLR 2025
because these same-community edges are mostly same-label edges (same C: 152/21). However, in heterophilic settings (Chameleon) the opposite is true: making the community structure more pronounced adds edges connecting different labels (same C: 95/265). Deletions are, however, more similar to random rewiring, with the exception of a subtle increase in the pruning of different- community edges for the heterophilic setting, compared random (Different C: -15/-99).
In the second row (spectral gap maximization), the algorithm exclusively adds cnfferent-commuiiee edges. In homophilic settings, this is detrimental, as most of them will be from different classes (Different C: 36/464). However, in heterophilic settings, often nodes of the same class are connected, which helps align the community structure with the task (different C: 152/348). MaxGap also prunes almost exclusively sume-communic edges, which is again detrimental for the homophilic case (same C: --40//557) but helps in the heterophilic case (same C: -667/333.. The fact that spectral maximization by deletions helps especially in heterophilic settings is also supported by its strong benefits for GNN performance (Jamadandi et al. 2024).
The alignment matrices serve guiding principle to determine if spectral gap maximization or minimization should be preferred. However, spectral gap optimization fails to transform the input graph into computational structure that is well aligned for the downstream task, which leaves the question, can we do better?
GRAPH REWIRING FOR COMMUNITY-NODE LABEL ALIGNMENT
ComMa. In our conceptual analysis, we have proven that spectral rewiring algorithms directly affect the community strength of the input graph, and that this can be detrimental to the task when there is an originally good alignment between community and node labels. Yet, pre-processing spectral rewiring methods are usually performed in a Greedy manner, and this causes the methods to affect newly obtained community structure but not the original one, which can get lost. To obtain clearer insights into the impact of community structure, we propose a non-Greedy and more efficient alternative spectral rewiring: ComMa. This method modifies edges such that they increase or decrease the original community structure directly. The variant that increases community structure is called Hi RigheeComM (Alg. 3). and corresponds to minimizing the spectral gap. The method that decreases it is LowerComM, (Alg. 4. and corresponds to maximizing the spectral gap. In general, this approach is flexible regarding the method that is applied to detect the community structure of the initial input graph. We use the Louvain algorithm (Blondel et al. 2008), as it scales to large graphs and is implemented by the library cugrrpph for GPU acceleration. The non-accelerated algorithm runs in ((V) log [V]). Rewiring only needs to consider the edges to add (O(EE)) delete (O((ET)) and to randomly pick a fixed number of them (provided by hyperparameter N).
FeaSt. To make neighborhood aggregation more homogeneous to fight svor-smog and likely increase homophily, we propose to maximize the pairwise feature similarity of all connected nodes in the graph. The feature (cosine) similarity between nodes and v is defined as sim(u, v) = x xxx.ll)..ll)) x.Il)* where X,, X. the respective features of nodes and v. Although this operation can also be accelerated by GPU, the non- non-accoe accelerated computation runs in O( (1))). We consider all edges that can be added or deleted, and we rank them according the similarity. which would obtain if the edges were added or deleted, respectively. The modified edges are the top ones of this ranking, which can be obtained in ( El) for additions or ((N[E)) for deletions. The concrete formulas are specified in Alg. 5
.x.)
ComFy. While feature similarity maximization is well performing pre-processing rewiring ap- proach, it suffers from complementary pitfalls to the spectral rewiring methods. For the latter, it can be disadvantageous to ignore the task. For the former (FeaSt), can be disadvantageous to not account for the original community structure of the graph. Therefore, we propose to restrict the similarity maximization to edges between particular pairs of communities or pairs within community. We call this algorithm ComFy (Alg. (6). In this way, the effect of rewiring is spread across the whole graph, and the original structure is proportionally accounted for. This method still requires to compute all pairwise similarity values, and to detect the graph's 's original communities. Afterwards, it budgets the number of edges B.j to modify between each pair of communities (i.j) (including intra-community with i 2) depending on their sizes, and such that the total sum of budgets is approximately N. For each j). we find the top B.j edges that maximize the similarity of edges bridging them. The complexity of this algorithm is thus comparable to the sum of the other two algorithms.
8

---

Published as a conference paper at ICLR 2025
Table 1: Accuracy on node classification comparing different rewiring schemes.
Mothod
Cora
Citeseer
Pubmed
Cornell
Texas
Wisconsin
Chameleon
Squiree
Actor
OCN
86,12e0 36
37.83+0.35
85,57+0.11
35. 14+11.6 1.63
35, 1.514...5
10.001447
30.53+00.5 59
31. 31,69=0.42
27.2440.21
OCN-BORF
87.5010..0
73. 23.00.0.20
NA
10.80.1.10
NA
50.30s0.90
41.5010.40
NA
GCN-FoSR
83,5010
75. 33.47.0.331
86.0810.10
40.54:1.47
11.35
41.01a0.63 4400a1.46
32.36.0.37
27.57.0.21
GCN+ProsyAddMe AdkMiin
84,10+0 39
78. 18.7740.40
86.15e0.10 10
45 45.95=1.50
45
4:.00=1.25
30 00.3540.55
+3.71
GCN+Prorg PrroeyPdddda
85,9240.43
79 20225.0.5 35
86.41+0.11 11
48.65=1.11
40.54+1.
50.00=1.25
38, 20+0000000 7000
35.06=0.44
25. 99+0.20
GCN- PraxyDelMin
85.92=0.37
79.01=0.34 34
86.2840.11 11
15.95
48.65+1.3
44.00=1.13
39 89.00.99
34,83=045
26.5820
GCN+PoxyDelMaxx
86.32s0.38
61.84:0.38
85,9540.11
54.05a1.67
48.65a1.35
52.00s1.33
39.3340.70
34.61=0.39
27.30+0.22
GCN+Highet Audi
83.6410
77. 13+10.88
86:0 10
19.33:1.34
52.66 12.6611.447
50.55=1:24
41.23ee0.22 72
30 40.51=0140
GCN-High::ComMihhd
83,820033 51
77. 11:11.11
85.90+4 11
40.03-1.256
48.57+1.53
50:32+1.38
40.4440.69
54.66-0.399
30.74+0.24
83,41+0.37
77. 15+ 36
85 85.85+0.09
51. 0661667
50.29+1.71
50.95=1.29
4061+0.64
34.48=0.39
30 79+1.22
GONoLowerooMaDee
83.6120.35
77.39+0.37
85,9040.10
19.09s1.43
50.59+1.52
50.61=1.35
40.4360.71
34.76=0.40
30.7940.22
GCN=FesStAdd
87.73+0.39
78.54+0.34
49:444000
19.46e1.49
$4.05e1.51
60:00=1.09
43 13.2640.66 62
39.33=0.73
31 2544022222
GCN-FeaSiDel
90.7420.39
$1 31,009
86.7610.10
11.3521.63
64.8611143
60.00:1:27
42/70.0.69
36.40:0.36
3) 11.9720,21
GCN+ComPyAdd
87.73=0.26
77.3620.38
$6,7440 10
67.5741.68
62 16+1.52
62.00:1.12
41 41.57400.3
36.8520.38
32 9040.25
GCN+ComFyDel
88.1310.27
78,0740.35
86,2540.11
70.27a1.50
64
66,00:1.34
45.5110.76
39.10.0.43
31.1240.19
Table 2: Node classification on Large Heterophilic Datasets comparing different rewiring schemes.
Method
Roman- Empire
Amazon- Ratings
Minesweeper
Baseline
70.30+0.73
47.20+0.33
89.49=0.07
GCN+FoSR
73.60=1.11
49.68+0.73
89.66=0.04
GCN+Proxy-AdMMin
79.1840.06
49.30+0.05
89.5620.05
GCN+ProxyAddMarr
77.54
49.72 41
89.63=0.05
GCN+ProoxDeelMin
79,09=0.05
49.57=0.00
89.60=0.05
GCN+ProxyDelMax
77.45+0.68
49.75+0.46
89.58=0.04
GCN+FeaStAdd
79.6720.07
49.46+0.07
89.75=0.05
GCN+FeaSiDel
78.9940.05
49. 19.1940.06 06
89.02=0.00 0,04
GCN+FcaStAddDel
79.03+0.07
49.39x0.07
89.62=0.05
GCN+ComPyAdd
79.53+0.01
49 49.2990.04
89.7620.05
GCN+ComFyDel
79.17
49.21
89.6620.05
GCN+ComFyAddul
79.27=0.06
49.45+0.07
89.40=0.08
4 EXPERIMENTS
We conduct a comprehensive set of experiments for all proposed algorithms on various benchmark datasets. Our backbone model is GCN (Kipf & Welling, (217). Our rewiring techniques could be combined with any GNN model. We focus on simple, common base architecture, as we compare many rewiring techniques in comparable environment. Our proposed rewiring algorithms include: Highe ComMa which randomly adds/deletes intra- communitmuityy edges and inter-community edges respectively based on communities detected (Newman 2006; Blondel et al., 2008); LowerComMa which does the opposite by randomly deleting intra-class edges and adding inter-class edges based on the communities detected; FeaSt, which rewires the graph to maximize the pair- pair-wise cosine similarity between node features; and ComFy, a hybrid version of other two algorithms that uses both the community structure and the feature similarity rewire the graph. We use the suffixes Add, Delete and AddDel to represent only additions, deletions, or both. Our baselines with which we compare our algorithms are spectral gap maximization methods such as FoSR (Karhadkar et al.) 2023), ProxyAddMax, and ProxyDelMax proposed in Jamadandi et al. (2024). We further modify the latter algorithms also minimize the spectral gap, resulting in methods Proxy AddMin (Alg. MT and ProxyDelMin (Alg. 2 The results for the Ricci curvature- based method BORF (Nguyen et al. (023) is directly taken from their paper-henne -ence Not Available (NA) for a few datasets. For all tables, the best-performing methods are highlighted in bold, and the second best-performing methods are highlighted with underlines. More details on the hyperparameters used are described CC
Cora (McCallum) ct al. 2200). Citeseer (Sen et al. 2008), Pubmed (Namata et al.. 2012), Cornell, Texas, Wisconsin, Chameleon, Squirrel, and Actor (Platonov et al. 2023c). We find that FeaSt especially well for bomophilic graphs. However, ComFy-Del seems to be in the lead for the heterophilic ones, and performs comparably for some of the homophilic ones. In Table 2 we present the results on accuracy for the large heterophilic graph benchmarks (Platonov et al. 2023c) for the spectral rewiring methods, for FeaSt and ComFy. While FeaSt-Add has some good results, all
In Table I we test our algorithms on a variety of homophilic and heterophilic graphs:
performs

---

Published as a conference paper at ICLR 2025
Table 3: Accuracy node classification with both additions and deletions.
Method
Cora
Citsseer
Pubmed
Cornell
Texas
Wiscousin
Chamoloon
Squirrel
Actor
GKN
16.22-036
75,834033
85.5740.11
35.14-1.60
35.12e1.50
18.0011144
39.33-0.50 5y
31.69-0.,2
27.3440.21
GON+BORF
87.50=0.20
23.0000.20
50.80=1.110
61.50e00.00
GCN+Fo5R
83.50:0.39
75.47H0.31
86.08ab. 10
40.54:1.47
51.35e1.75
54.00s1 46
41.0120.63
32,36,0.37
27.57:0.21
GCN+HigheCCmMMa
83,82:0.34
77.32:0.35 58
8583+0.11
48 48.92s1.48
52.44s1.66 64
51.35t1440 40
41 41.22:s.75
34,70s00.40
30.81:0.19
OCN+LoweConMaa
83.7620.35
77.0540.37
51.4611.49
50.29g1.59
34.1120.38
30.6010.22
GCN-FeaSt
85.71=0.36
80 1940
87.01=0.12
54,05=1.62
56.76+1 .65
58.00+1 26
44,9420.70 70
35.73=0048
32.63+0.21
OCN+Comfy
88.93=0.31
80,4220.46
87.2220..10
62.16.11.9
59.46=1168
64.00:1.08
46.63=0.09
37.75=0.41
33.0920.21
Table 4: Runtime for different rewiring schemes, in seconds, for 50 edges.
Method
Cora
Citeseer
Chameleon
Squirel
FoSR
4.69
5.33
5.04
19.48
ProxyAddMax
4.30
3.13
1.15
9.12
ProxyAddMin
5.03
1.08
10.01
ProxyDelMax
1.18
1.46
7.26
ProxyDelMin
3.59
3.12
8.43
CamMaAdd
0.05
0.04
0.63
ComMaDel
0.05
0.04
0.68
FeaStAdd
0.56
4.43
FeaStDel
0.56
4.52
Cod
6.29
3.85
2.84
8.72
ComFyDel
6.68
3.73
2.99
8.97
ComPy variants seem to also perform comparably. Finally, Table we present results for both simultaneous additions and deletions for our methods.
Table reports the computational efficiency compared to baselines, in seconds, when adding or deleting 50 edges. Concretely, ComMa is orders of magnitude faster than the spectral methods, FeaSt beats most the baselines, and ComFy is comparable to them. The runtime of methods HigherCombs and LowerComMa are exactly the same, which we denote by ComMa.
5 CONCLUSIONS
We have introduced three novel graph rewiring techniques -ComMa, FeaSt, and ComFy- designed to improve the performance of Graph Neural Networks (GNNs) by focusing on the alignment between the graph structure and the target task.
Through our theoretical analysis, we have identified this aligmment as a critical factor in explaining performance gains and highlighted it as major limitation of purely topological-bese bassed rewiring strategies that they cannot improve this alignment directly. We have discussed this specifically the context of spectral gap maximization, widely adopted strategy address over-squashing, which attenuates the community structure of a graph. However, when the community labels overlap with the node labels, minimizing the spectral gap (thus amplifying the community structure) would yield significant performance improvements instead.
The basic mechanism behind this improvement the increase of feature similarity by neighborhood aggregation. In line with this finding, we have shown that rewiring techniques that explicitly take feature similarity into account, such as Feast and ComFy, y, can lead to significant performance gains, particularly in highly homophilic settings. Our proposed ComFy method, which balances community structure and feature similarity, was shown to outperform spectral rewiring methods in heterophilic settings, where feature alignment across different communities plays critical role.
Our comprehensive experiments on real-world datasets confirm the effectiveness of these rewiring strategies, demonstrating that combination of topological and reature-based approaches is key to overcoming the limitations of spectral methods. We believe that this work lays the foundation for future research on task-aware rewiring strategies, and opens the door more sophisticated methods that leverage both graph topology and node features to optimize GNN performance across a wide range of graph-based applications.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS AND DISCLOSURE OF FUNDING
The authors gratefully acknowledge the Gauss Centre for Supercomputing e.V. for funding this project by providing computing time on the GCS Supercomputer JUWELS at Jülich Supercomputing Centre (ISC). We also gratefully acknowledge funding from the European Research Council (ERC) under the Horizon Europe Framework Programme (HORIZON) for proposal number 1011 16395 SPARSE-ML.
REFERENCES
Emmanuel Abbe. Community detection and stochastic block models: Recent developments. Journal of Machine Learning Research, 18(177):1-88) 86,, 2018. URL httt:://jmlr.org//pprr.s
v18/16 480 html
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021. URL
net vet/forum:s Petoormmiiiiio 80CPhOCVH2
Adrián RodriggR Ahmed Begga, Francisco Escolano, and Nuria Oliver. Diffwire: Inductive
graph rewiring via the lovász bound, 2022.
07369
Pradeep Kr. Banerjee, Kedar Karhadkar, Yu Guang Wang, Uri Alon, and Guido Montúfar. Over- squashing in gnns through the lens of information contraction and graph expansion. In 2022 58th Annual Allerton Conference on Communication, Control, and Computing (Aller- (on), pp. 1-8. IEEE Press, 2022. doi: 10. 11111///cccco0999300000999999999 7/doi org/ / 10. 1109/A1 http//Aleeeoooem 9937. 2022. 9929363
URL https
Wendong Bi, Lun Du, Qiang Fu, Yanlin Wang, Shi Han, and Dongmei Zhang. Mm-gnn: Mix- moment graph neural network towards modeling neighborhood feature distribution. In Proceed- ings of the Sixteenth ACM International Conference on Web Search and Data Mining, WSDM '23, pp. 32-140, New York, NY. USA. 2023. Association for Computing Machinery. ISBN 978 1503940777 doi: 10.1145/3595597.5574557
URL
3533597 3570457
Mitchell Black, Zhengehao Wan, Amir Nayyeri, and Yusu Wang. Understanding oversquashing in gnns through the lens of effective resistance. In Proceedings of the 40th International Conference Machine Learning. ICML'23. JMLR.org, 2023.
Vincent D Blondel, Joup Guillaume, Renaud Lambiotte, and Etienne Lefebwre. Fast unfolding of communitics in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008 (10):P10008, oct 2008 doi:
orq/10.1168/41 000////446/20000////0 1/1000000000000000000.. URL https:: //tps://dx... doi
5468
Pietro Bongini, Niccolò Pancino, Franco Scarselli, and Monica Bianchini. Biognn: How graph neural networks solve biological problems. In Artificial Intelligence and Machine Learning for Healthcare, pp. 211-231. Springer, 2023.
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Velickovic. Geometric deep learning: Grids, groups. graphs, geodesies, and gauges. CoRR, abs/2104.13478. 2021. URL https
//arxiv.org/abb
Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, and Prasoon Tiwari. The electrical resistance of graph captures its commute and cover times. computational complex- iry, 6(4):312 340, 1996. doi: 10. 20.1007//F012703355. URL hww.https//doollog///....
BFC1270385
O. Chapelle, B. Scholkopf, and A. Zien, Eds. Semi-supervised learning (chapelle, al., eds.; 2006) [book reviews]. IEEE Transactions on Neural Networks, 20(3):542-542. 2009. doi: 10.1 1100//NN.2009.215555
11

---

Published as a conference paper at ICLR 2025
Hao Chen, Yue Xu, Feiran Huang, Zengde Deng, Wenbing Huang. Senzhang Wang, Peng He, and Zhoujun Li. Label-aware graph convolutional networks. In Proceedings of the 29th ACM International Conference Information & Knowledge Management, CIKM '20, pp. 1977-1980, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781 450338559. doi: 10.1 (0.11455/340531.341211 URihtttps:///oi.orree 0t5.:/......1.1111333355553333.3 341213441133
Zhengdao Chen, Lisha Li, and Joan Bruna. Supervised community detection with line graph neural networks. In International Conference on Learning Representations. 2019. URL
//openreview. net. www.:nnneeoooommmimiiliiolooooe.
Andreea Deac, Marc Lackenby, and Petar Veličković. Expander graph propagation. In The First net/ forum?
Learning on Graphs Conference, 2022. URL. https:://pperretteee
IKr
Mingze Dong and Yuval Kluger. Towards understanding and reducing graph structural noise for GNNs, In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardd, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning. volume 202 of Proceedings of Machine Learning Research, pp. 8202-822666222222 PMLR, 23-29 Jul 2023. URL
html
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In International Conference on Learning Representations, 2020. httpppppss///eeeeeeee.ee.eeeeeee net/ forum? d 6NFPB
Matthias Fey and Jan Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learming on Graphs and Manifolds, 2019.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' pp. 1263 1272. JMLR.org. 2017.
Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pictro Lio', and Michael Bronstein. On over-squashing in message passing neural networks: The impact of width, depth, and topology, 2023.
Jhony H. Giraldo, Konstantinos Skianis, Thierry Bouwmans, and Fragkiskos D. Malliaros. On the trade-off between over- wer-shooth and over-squashing deep graph neural networks. In Proceed- ings of the 32nd ACM International Conference on Information and Knowledge Management, CIKM '23, pp. 566-576, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701245. 245. doi: 10.1145/35837880661199999 URLhttps: http://:////oi..00/0111115555// 3583780.3614999
M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume pp. 729-734 vol. 2. 2005. doi: 10. W0W19//UUNNNN200.55550555.
Richard Hamilton. The ricci flow on surfaces. In Mathematics and general relativity, Proceedings of the AMS-IMS-SIAN Joint Summer Research Conference in the Mathematical Sciences on Mathematies in General Relativity, 1988.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 1025-1035, Red Hook, NY, USA, 2017a. Curran Associates Inc. ISBN 9781510860964.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive Representation Learning on Large Graphs. In NIPS, pp. 1024-1034, 2017b.
Hussain Hussain, Tomislav Duricic, Elisabeth Lex, Denis Helic, and Roman Kern. The interplay between communities and homophily in semi-supervised classification using graph neural networks.
Applied Network Science 6 600, 2021. doi: 10. 1007/s44 109-021-00423--111 URL https?
7/doi. .arii.or//100 19t 0010033-
12

---

Published as a conference paper at ICLR 2025
Adarsh Jamadandi, Celia Rubio- Madrigal, and Rebekka Burkholz. Spectral graph pruning against over-squashing and ovor-shn... In The Thirty-eighth Annual Conference on Neural Informa- tion Processing Systems, 2024.
Kedar Karhadkar, Pradeep Kr. Banerjee, and Guido Montufar. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. In The Eleventh International Confereence on Learning Representations, 2023. URL httpst:::
Nicolas Keriven. Not too little, not too much: a theoretical analysis of graph (over)smoothiing In
NeurIPS, 2022. URL htthttt:: wwtppipppppppppppppppppp http:///ppppppapap.aoooooaaaaaas /ttpa//eeeeoaa/ooa..o.ooaaaaaaaa
01956c66666762220711111777773333 Aatp Cow.rracct-Cofffennee.e. html
Abst
Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional
Networks. ICLR, 2017.
Adrien Leman. The reduction of a graph to canonical form and the algebra which appears therein. 1968.
David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov chains and mixing times. American Mathematical Society, 2006.
Guohao Li, Matthias Müller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? In The IEEE International Conference on Computer Vision (ICCV), 2019.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? In International Conference on Learning Representations, 2022. URL https //openreview. wttprriee..w.ffootee
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the con- struction of internet portals with machine learning. Information Retrieval, 1()3 2000. doi: 10.1023/A:1009955381444 14988. URL [t/ppppp////oo...o///00000000200 0001:/......0001110099000058014
/oi.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 33000))4602-4609, Jul. 2019. doi: http://aaaaa3311.3333333333
[ttts:ts::/// http:://ooosaaaa..ogoo.o..
article/view/4B2
Nimrah Mustafa and Rebekka Burkholz. GATE: How to keep out intrusive neighbors. In Firty International Conference Machine Learning, 2024. URL https://openrevvew. net/
Nimrah Mustafa, Aleksandar Bojchevski, and Rebekka Burkholz. Are GATs out of balance? In
Thirty-sevnnth Conference Neural Information Processing Systems, 2023. URL https:
Galileo Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven active surveying for collective classification. 2012.
M. F. Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103((3):8577-8588 Jun 2006. doi: ...1073/pnas.00016022
Khang Nguyen, Hieu Nong, Vinh Nguyen, Nhat Ho, Stanley Osher, and Tan Nguyen. Revisiting over-smoothing and oqur-squahhnn using ollivier-ricci curvature, 2023.
Hoang NT and Takanori Machara. Revisiting graph neural networks: All we have is low-pass filters. ArXiv, abs/1905. 905,095500, 2019.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. DropGNN: Random dropouts increase the expressiveness of graph neural networks. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), ), Advances in Neural Information Processing Systems, 2021. URL htt.:htttp//ppeeeiee
net. wwwp:ewwwwwweeeeeeeeeeeeeeeeeeee fttt:/forrmmiisfffoooooooor
13

---

Published as a conference paper at ICLR 2025
Oleg Platonov, Denis Kuznedelev, Artem Babenko, and Liudmila Prokhorenkova. Characteriz- ing graph datasets for node classification: -hntopillyheetrophily dichotomy and beyond. In Thirty-sevnnth Conference Neural Information Processing Systems, 2023a. URL https:
//ooenreview. www.ww.ee//teeee. wwt//efooumm d=m P
Oleg Platonov, Denis Kuznedelev, Artem Babenko, and Liudmila Prokhorenkova, Characterizing dichotomy and beyond. In The Second Learning Graphs Conference, 2023b. URL httpt::t/ppppeeeeeeeeeeeeeee www.nee/foruuut
graph datasets for node classification:
id=D4GLZKTphJ
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look evaluation of gnns under heterophily: Are we really making progress? In The Eleventh International Conference Learning Representations, 2023c.
Patrick Reiser, Marlen Neubert, André Eberhard, Luca Torresi, Chen Zhou, Chen Shao, Houssam Metni, Clint van Hoesel, Henrik Schopmans, Timo Sommer, and Pascal Friederich. Graph neural networks for materials science and chemistry. Communications Materials, 3(1):93, 2022. doi: 10. 1038/s43246-022 020----022-00115---
Justin Salez. Sparse expanders have negative curvature, 2021.
Alvaro Sanchez-Gonzalez, Jonathan Godwin, Tobias Pfaff, Rex Ying, Jure Leskovec, and Peter Battaglia. Learning to simulate complex physics with graph networks. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 8459-8468. PMLR, 13-18 Jul 2020. URL https: pettps:/pproeeddingg
mwr prwss.pres///e / 19w.hceee/eeeeeeee gwn.a html
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions Neural Networks, 20(1):61 2009. doi: 10. 20W.TNN..00...00......
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al Magazine, 29(3):93, Sep. 2008 doi: 10. 12.1609/aima..2293222555 URL/httss://ojs.aaa wrg. wwtpg/iidxx.... wttp:p/aamaaaamieeem/ article/view/2151
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation, 2019.
Jonathan Shlomi, Peter Battaglia, and Jean-Roch Vlimant. Graph neural networks in particle physics.
Machine Learning: Science and Technology, 2(2):021001, jan 2021. doi: 10.1088/2632-2158/ abbf9a. URL BtRLhtts::/// //otps:///oi..oo www.oo.g/..... 1088 22000882222222/ 2 abbf9a
John R. Silvester. Determinants of block matrices. Mathematical Gazette, 84(501):460-467, Novem- ber 2000. doi: 10.2307/3620776.
Jake Topping. Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M.
Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2022. URL https:tt: /ttp////pppp/.e..///////e
/ hwtpeewwwwwwweeeeeeeeeeeeeeeeeee net wtt.:/wruuet//oommmm/
id= 1d=7UmjRG2p-22
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In /CLR, 2018.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, highiy-performant package for graph neural networks. arXiv preprint arXiv: 1009v:9909.033 1909.0/319. 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https: net./ wtt.eeeeeeeeoootmam////////////e
A5km
14

---

Published as a conference paper at ICLR 2025
Chenxiao Yang. Qitian Wu, David Wipf, Ruoyu Sun, and Junchi Yan. How graph neural networks learn: Lessons from training dynamics. In Forty-first International Conference on Machine Learning, 2024. URL httphttt/ppeereeeeee
net httt//oouummiddDnnn1331111 o/ cCW
Kaixiong Zhou, Xiao Huang, Daochen Zha, Rui Chen, Li Li, Soo-Hyun Choi, and Xia Hu. Dirichlet energy constrained learning for deep graph neural networks. Advances in neural information processing systems, 2021.
15

---

Published as a conference paper at ICLR 2025
APPENDIX
A PROOFS
A.1 PROOF OF THEOREM
Proof. We consider SBM with 2 classes and T nodes in each class, with intra-class edge prob- ability p and interclass edge probability q. Its adjacency matrix is a random matrix where Ay Bernoulli(p) if nodes i,j are in the same cluster, and A. Bernouli(g) otherwise. For large N. the adjacency matrix can be approximated by its expected value, which is a block matrix:
Á = ( 9) where P p- L + (1 pg where all values are p except the diagonal which consists of ones, and Q q g. where all values are By summing up each row we find that the expected degree matrix D is the diagonal matrix with entries D, = 1 - (p + q). To find the second largest eigenvalue A2, need spectrally analyze the (expected) normalized Laplacian of A; that is, L = -1- D 1/2 3-1/2AD AD 1/2, We have that D-1 ( 1
1/2
IN. so
D-1/2AD-112
(1-p
1
A= dÅ, where we define d for convenience.
1-p 2 (p +
Then C == dÅ. We need to find À such that det (C - N1) = 0.
C- = - dĀ - a1 -A (A 1)1 (- dP (A 1--11 1)7 -dQ
-dQ -dp (A- 1)1)
(-åP -(- (A-1)1] 1) and -dQ commute, so by (Silvester 2000). the determinant of that matrix is
det ((-ip- (A (A-))) - (-ae))
(11))(((i0)))
det (āce - P) -
1))) (2-1)))
det (-ã(Q + P) - (A--1)
We have that Q- 1) +(1-))/ which has eigenvalues (1-p) and ((g-p) x) +1 so we finally get the required eigenvalue
N 2
+ (1- p)) +1 ( p) N 2
(1 (1-p) p)
A d((a p)
+1
(q (
N
(1-p)
2
For N > 2 and p.g E (0,1):
&
1 (1-0 +1 +
2N(Ng+2)
0, while
Bp
(atp)
(N N
0. This proves that d2 increases when de- creases, and when g increases. So higher spectral gap related to lower community structure. 0
a (1--) 8q + +1 ((N ( N2+
2N p
>
A.1.1 EXTENSIONS OF THE THEOREM
P
Q
Q
The argument still follows for a higher amount of blocks. Let À =
Q
:
Q
with k diagonal
Q
P blocks of sizes each. The degree of every node now D2 1 1- p+ + N(K-1) q. Because of the block structure of our matrix, we still get the second eigenvalue from the difference between on and off diagonal blocks Q P. which now has eigenvalues (1 p) and ((g p) + (1 p)). Therefore
- ( + (1 p)
kkp 1) - N(p - 9) k(Ng - - N(p 9)
d = d(((-p))
+ (1-p))+1=
+1
+1
k
N $
N(k-1),
+ p)
16

---

Published as a conference paper at ICLR 2025
If k is constant with respect to N, this quantity grows like 1 (k- 1e-1)p
If a.V, then it goes to 1
as N increases.
P1 Q2
(2) where P1
The argument also still holds for different--ized communnttess Let Å
1 + (1 p and P2 p- N + +1 (1- N where all values are except the diagonal
which consists of ones, and Q1 = q 1M. Q2 = LN-M. where all values are 9. We assume that
M > - MM. Then δ the diagonal matrix with entries D3 = (1 + (M - 1)p++ + (N - M M)
i < M, and D. = (1 + (N - M - 1 Mq) otherwise. We define di = I+ - 1) --++-N-MM MM and d2 I-(N - p- for convenience. Because di < dz, the second largest eigenvalue will come
from the interactions of the first block. So the eigenvalues are (1 p) and ((q p)M + (1 p)). Therefore
(q M + (1 p) +1 A dig - P)M + (1- +1= (1+ (M 1)p (N M )4)
If M aN, this quantity grows like bigger than the first and we get the second eigenvalue from it instead.
a(p-g) If M is constant, then the second block gets ap-(1-0)4
A.2 PROOF OF THEOREM
Proof. We consider an SBM with classes and
2 nodes in each class, with intra-class edge proba-
bility p and inter-class edge probability q. Each node i {0, ......,,,, .N - 1} has one feature, Tú, and label l which corresponds to the block it belongs to: 4 = + i2 Z. predict each node's community association. In this case, the alignment of communities and labels perfect.
N The task is, therefore, to
Each feature xy is aligned with its label following a normal distribution: class-0 node features follow N- oî), while class-1 node features follow N(Ho, shown in Figure 6(a) A perfect classifier ff without any knowledge of the graph structure builds decision boundary at x = 0. The expected number of misclassified nodes is A/ times the intersection area of both distributions
because they are normalized from a population of N each. Such area is 2 4 -1ta ). where 4 is the cumulative distribution function of the standard normal distribution (see Figure 6(b)) Therefore, the proportion of misclassifications is e(f) N 2 Φ ())) ) N = o (He) ) As T is cumulative function, it is monotonically increasing with respect to its argument.
2
The classification error of f can be reduced by performing a step of message passing on the graph. which utilizes the community information to further separate the two classes. We shall consider a single round of sum aggregation as an example.
N(- 14, 08)
N(Ho, of)
.o 1)
Density
Density
Ho
140
(a) The distribution features from both clusters before training. The area in purple corresponds to nodes wrongly classified by the decision boundary
(b) The cumulative distribution function z -1 of A (Ho, gτ) is equal to the cumulative distribution of the standard normal distribu- tion (O 1). which is 4 ====))) The purple area of Figure is two times this quantity.
function at x
0.
Figure Illustration of the setup for the feature distributions for Theorem
17

---

Published as a conference paper at ICLR 2025
Any node has expected Ep p. ( -1 1) intra-class neighbors, plus itself, and expected E = 2 inter-class neighbors. the next proof we compute the same quantity with neighbour distributions instead, for more fine-grat ane-grained approximation. The hidden state of a class-1 node after a step of sum aggregation is therefore the sum of & + random variables ~ -N (Mo, of) and &g random variables [N[--o, (Ao, ..) This follows another normal distribution with mean jai == μ (1 (1+ E, Eg) and variance of == og (1 E + En)) Conversely, the hidden state of class-O node i follows normal distribution of mean - _A1 and the same variance of. The decision boundary of perfect classifier is still at 0, but the average proportion of misclassified nodes is now ( ), which depends on p and q. Specifically, it tends to be monotonically decreasing with respect to pł this means that the higher the community structure, the more accurate the classifier can be, because there is more information to utilize.
Let us take /A0 = 1 and 0g = 1 to simplify the calculations. We need to check that 8 Up
|41
0.
01
For N > 2 and p. 10:
N
N
N
A1 1. (1+p
1
9
= 1 - p+
(p q)
2
2
2
N
N
N
of 1. (1+p
1
+ q
p
(p + 4)
2
2
2
11
1 p+ (p 9)
91
1 p 1/4 (p 4)
0
1111
(N 22) - 2)p 3Nq + 2)
<0
0p
01
2/2( ((N 22p++N++22
(N - -2)(((( - -2)p 3Ng 2)>
On the other side,
0 0g
(-11
> 0.
111
N(6 3(N 2)p + Nq)
> + N(6 - 2)p Nq) >
0q
2/2((2 + (N 2)p + Ng)
This proves that, by reducing the community structure (either by decreasing p or increasing q), then the quantity =Mt increases, so the expected proportion of misclassified nodes e(f) = + also
Ø1
increases. In consequence, harms the performance of classifier f-
The graph's 's information provides better separation between the two classes if the intra-class edge probability is high enough. From this we can conclude that reducing the intra-class edge probability not a good strategy to improve the classification performance for any model on the graph.
A.3 PROOF OF THRORRM 3
Proof. We consider another SBM with 2 classes and N nodes in each class, with intra-class edge probability p and inter-class edge probability q. Each node E (O...., NN 1} has again one feature, Ij, aligned with its class label & following a normal distribution: (N Mo. az) for class 0 and N N(Ho,, oi) for class 1. However, now é, corresponds to its community with a fixed probability e -recovering Theorem Thenvrrrn 2 when dé 1.
What the probability of any node such that, after a round of sum aggregation, its modified representation a! is now misclassified (M)? As the two classes are symmetric:
P(M) P(M, Lo) + P(M, L1) P(Lo) P(L))((M)L))
1 P(M + P(M P(M)LO)
2
18

---

Published as a conference paper at ICLR 2025
Then the question becomes the following: what is the probability of node with label Ly being misclassified? It depends whether it belongs to community Co or C1.
P(M)Lo) - P(M, Lo) + P(M, Co) - P(C))4))P(MM Co) P(CILL))(M))L C1) Lo Co) + (1 (L-)))((ML..CC
P(M|Lo,Co) Co) = P(X > 0). We now need to calculate what is the predicted label of a (Lo Co) node after sum aggregation round. For this we need the distribution of its neighbours. We consider the node to have self loop, uses its own feature too.
The number of nodes (Lo, Co) (that are not node i) follows a binomial distribution No B -, 1)). However, for easiness of proof we will approximate by normal distribution, which is appropriate for N large enough: No- ~ NN 1)eb, amount of them connected to node i follows a conditional binomial distribution Hoo ~ B(no. p) No = no, which we again approximate by Hos ~ N (nop, nop(1 p)) No no.
1))a(1 +)). The
The number of nodes (Lg, that are connected to node i follows Ho1 B( no: 9) No = nu, approximated by Ho1 ~ -N(( - -1-no) no)q. ( - 1-no)g -)) No = ng.
Since Hoo and Hot are conditionally independent given No = no. their sum Hg = Hoo Ho1 also follows a normal distribution with parameters given by the sum of their means and variances. Thus, the number total Lo nodes connected to node (except itself) follows Hg ((Ro + \ - no)g, nop(1 (p + ( 1 no)9(1 9)) No no- We are going to get rid of the dependency of No by estimating it by a normal distribution with the mean and variance of the marginal distribution of Ho:
N - 1-
H = EE Ho No]] = B[Nolp +
N
vp + N
N
-1 vb 9
2
2
N
1
(pu) + g(1 - xb))
2
Var[Ho] = E Var Ho No)1 + Var (HoHo)
N - 1 - -[Nool 9(1 - 9)
= E[Nolp(1 - p) +
2
(N
2 1) 1)()
+ Var
Nolp - 4) +
())
N
N
1 2 q(1 9)
-
d/p(1 - p) +
-
2
2
2
(p
2)²
N
-1 1) 1b(1 - xb)
2
N
-1) (1p(1 - p) + (1 - 1))(( - 9) + (p 2) +))
2
The number of nodes (L,,C) follows N1 B), v). approximated by Ni N v. N (1 - v)). The amount of them connected to node follows Hμ ~ ((r,, N1 nı, approximated by Hu ((nig,niq(1 - q)) Ni nn.
. The number of nodes (L,, that are connected to node follows Hio ~ B N1 nı, approximated by Hio NI( n m,) (g m))((1 p)) Ni n.
mi
19

---

Published as a conference paper at ICLR 2025
Similarly to Lu. the number of total L1 nodes connected to node follows H1 ~ NNi1qq
( - n2)p, mig(1 q) + ( "1)p((( - p)) N1 = n1 We will estimate it by normal
distribution with its mean and variance:
N
H = H M1] B[Ni]q + (
E[ND)
2
N
N N 1
2 by +
p
2
N
2 (0(1 1/) + qv)
Var[H]] ([ + Var(BBHH, (N11)
N
p(1 p(1-p)+ + Var (Ni(q- - p) + N 2
E[Nil9(1 - +)+++0+ +
+)++
2
N rbq(1 9) +
.
N
(p -))²² N
v
2 10 v))
2
N (b9(1 9) + (1- pp p) + (p 20 x)))
The representation of node i after one step of sum aggregation is the summation of Ho + 1 (indepen- dent) normal distributions (N ot)) and H₁ (independent) normal distributions N o Therefore:
X (L) ~ (o-ooo1 + ho h1), of + ho + h,)) Ho ho: H1 = h1
Again calculating its mean and variance:
B[X(Lo,c,)l (Lo. |H,, Hill -mo(1 + -
- B[H+])
= -MM 1 +
N
1 -1 (pv) + q(1 - x²) (p(1 - x/)) + qub)
N
Var(X(Lo.Co)] = E[Var(X(Lo.CC
Ho. H1) + Var(EEXX |Ho, Hi))
-1 + E[Ho]] + [) + PJ (ar Ho) + 1))
N
N
= =00
1
-1
(ny) + 9 )) + 2 (p( 1 - x/) + v86))
2
+ m
((*
N
-1)
(dip(1 - p) + - +) 4) + -
v) (p-9)
4))
2
N
+ (wa(1 g) + (1 - ))p(1 - p) + (p 3)²$01 (1 b-)
For a more clear analysis of this formula, we take μu = 1, on = 1 and N large enough:
N
N
E[X (To.
~ (pv + q(1 -1 +) p(1 - +) qpo)
(2 - 1)(p 4)
2
2
N
VarlX((to.Go))
pd + q(1 )))) + p(1 -)- + qu + + 2/2 1)
+ vpp(1 p) + (1 (1 9) + v0g(1 9) + (1 4)p(1 p)
N
2/2 (o+ q + p(1 p) p) + q(1 9) + 2 9) 21 x))
Finally, we have ((X >0 2 >0) 1- +b
N (2 - 1) 9)
$
2
N
(p - p) + q g) + 2(p g)2 - 2)))
2
20

---

Published as a conference paper at ICLR 2025
Algorithm Proxy Spectral Gap based Greedy Graph Addition (PROXYADDMIN)
Require: Graph 9 = (V,E), num. edges to add N, spectral gap A (Cg), second eigenvector of g.
repeat
for (u, u) E E do
Consider 9 = G U (u, v))
Calculate proxy value for the spectral gap of & used in Jamadandi et al. 2004
Ag(Lg) R (C() + ((fu - f.)² A1 (Cg) (S² + (2))
end for
Find the edge that maximizes the proxy: (== = arg min X1 (Cg). (u,D)Eε
Update graph edges: = ((utt(e+))))
Update degrees: du+ = duy + 1.d+t dut +1
Update eigenvectors and eigenvalues accordingly. until N edges added.
Output : Denser graph 9 EV,
Algorithm 2 Proxy Spectral Gap based Greedy Graph Sparsification (PROXYDELMIN)
Require: Graph G = (V,E), num. edges to prune N, spectral gap >1 second eigenvector f.
repeat
for (u, v) E 3 do
Consider 9 = G (u, v).
Calculate proxy value for the spectral gap of & used in Jamadandi et al. 2024
(Cg)) ~= (C(g) - ((fu - f.)² A (Cg) (f" + f:))
end for
Find the edge that minimizes the proxy: (u (u=,07 v-) = arg min A1 (Cg) (a,v)E
Update graph edges:
{(u ))
Update degrees: d,- = d,- 1, d = dv- -1 Update eigenvectors and eigenvalues 9 accordingly. until N edges deleted.
Output Sparse graph & (V,E).
For LoM = P(X > 0). the calculation of the predicted label of a (Lo, C1) node follows exactly the same steps, but exchanging p and q. as the probabilities for nodes to be connected node are now exactly of the opposite community. So we have ((X(LO.CA) > 0)
2/ (2nb 1)(g p)
= 1 - 1-P(X > 0)
p + p(1
p) q(1 - 9) 2(p 2b2 +6))
And P(M) x PP (o..oo) > 0) + v)(1 P(X(LO.G)
> +)) = (1 --4) + (26
P) () > 0).
B ALGORITHMS
B. SPECTRAL GAP MINIMIZATION
We use the algorithms presented in Jamadandi et al. (2024) for adding (ProxyAddMax) and deleting edges (P roxyDee Max) based on proxy of the spectral gap. We modify these algorithms to minimize the gap and call them ProxyAddMin (Alg. I and ProxyDelMin (Alg 2
B.2 COMMUNITY AND FEATURE SIMILARITY ALGORITHMS
We present the three algorithm families proposed in this paper for graph rewiring: ComMa (Algs. FeaSt (Alg. 5) and ComFy (Alg. 6). Each algorithm has addition and a deletion variant.
21

---

Published as a conference paper at ICLR 2025
Furthermore, ComMa has two extra variants for increasing (HigherComMa, Alg. decreasing (LowerComMa, Alg. the community structure.
Algorithm 3 HigherConMaa Increasing community structure. Variants: ADD, DEL
Require: Graph G = E), num. edges to add (ADD) / delete (DEL) N.
Calculate communities (here used Louvain): (Co, ..., Cm) = ConmunixyDerectio(() if ADD then
Consider set of edges to add: = {(u, v) E & Comm [t] = Comm[u]}
else if DEL then Consider set of edges to delete: = { (u, v) E & Comm(u) * Comm[u]] end if
repeat
if ADD then
Randomly and uniformly pick an edge from E Update graph edges: = & {e} (ADD) or & {e} (DEL) end if
until edges modified.
Output : Modified graph 9 = (V,8).
Algorithm Lower Decreasing community structure. Variants: ADD, DEL
Require: Graph 9 = (V, E), num. edges to add (ADD) / delete (DEL) N.
Calculate communities (here used Louvain): (Cu,... ..., .m) = CommunityDetection() if ADD then
Consider set of edges to add: = {1u, v) E 8 Comm(u) * Comm(u]}
else if DEL then Consider set of edges to delete: = { (u, e) E E Comm [u] = Comm(o]] end if
repeat
if ADD then
Randomly and uniformly pick an edge from E Update graph edges: = & {e} (ADD) or & {e) (DEL)
end if
until N edges modified.
Output : Modified graph 9 = (V.
Algorithm 5 FeaSt: Maximizing feature similarity. Variants: ADD, DEL Require: Graph G = (V, E), node features X, num. edges to add (ADD) / delete (DEL) N. Calculate the pairwise cosine similarity of X: sim(u, v).
Calculate the mean of the current graph's 's similarity values: sim if ADD then for (u,v) v) E غ do Calculate the graph's mean similarity in the presence of (u, v): rank(u, v) end for
D(u, sim(u, v)
[e|
simp ++im [8
else DEL then
for (u, E & do
Calculate the graph's mean similarity in the absence of (u, u): rank(u, v)
sim simi 1.
end for
end
Find top N edges in the ranking: Fyy top (rank(u, v)) Update graph edges: & = EN (ADD) or & = E EN (DEL)
Output : Modified graph 9 = (V,E).
22

---

Published as a conference paper at ICLR 2025
Algorithm 6 ComFy: Maximizing feature similarity across communities, Variants: ADD, DEL Require: Graph G = E), node features X, (approx.) num. edges to add (ADD) / delete (DEL) N. Calculate the pairwise cosine similarity of X: sim(u, v).
Calculate communities (here used Louvain): (Cu...., Cm) CommunityDettction(())
Consider pairs of communities: C [(C,, Cÿ) E
for (C,, C₁) E C do
Existing edges between C₁ and Cy: Bay- {(u, v) E & Comm(u) C. Comm [u] Cj}
Calculate the mean of the existing edges' similarities: simij [Bny] ((.)) sim (u, v) if ADD then
Non-existing edges between C₁ Cj: Eij {u,, v) & Comm[uu [u] C2 A Comm [u] Cj}
for (u, 2) Eij do
Calculate the mean similarity in the presence of (u, u): ranksj (u, v) sim:y] Eyy +sim v)
Bgg ++1
end for else if DEL then
for (u, v) E Fuy do
Calculate the mean similarity in the absence of (u, w): rankey(u,
B. sim u.
b
end for end if
1CH1C111 Calculate edge budget: Bii,j) round(N Eyee, CC, c,,
(rank; v)) Find top ji edges in the ranking: Eyj B(BJ) toP (rnne.)))
Update graph edges: & E U E,j
B((.j) (ADD) & = E Eij
B(i (DEL)
end for
Output Modified graph 9 (V, Number of modifications is approximately N.
C DATASETS AND HYPERPARAMETERS
C.I DATASET STATISTICS
provide summary of the datasets used for the experiments ($4). We also provide various metrics such as Edge Label Informativeness (ELI) and Adjusted Homophily score proposed in (Platonov et al. 2023b). The Normalized Mutual Information (NMI), Adjusted Mutual Information (AMI) and Modularit larity score after performing community detection using the Louvain method to understand how informative the graph structure is. The adjustment in AMI is only necessary when comparing between sets of different size. but within a dataset the number of classes does not change. Therefore we can compare the effect of our algorithm by means of the NMI's value. However, the AMI is useful to compare the alignment across different datasets.
In Table 5
C.2 DETAILS OF THE EXPERIMENTS
We use PyTorch Geometric (Fey & Lenssen 2019) and Deep Graph Library (DGL) (Wang al. 2019) for all our experiments. For datasets Cora, Citeseer, Pubmed, Cornell, Texas, Wisconsin, Chameleon, Squirrel and Actor we use 60/20/20 split for train/test/validation respectively. The hyperparameters are tuned on the validation set. Our backbone model is a 2-layered GCN (Kipt & Welling 2017). We report the final test accuracy averaged over 100 splits of the data. For datasets empine Amazon-rating and Minesweeper we use the code base of the authors Platonov et al. (2023c), where the datasets are split 50/25/25 for train/esttvalidattion respectively. Our backbone model here is a 5-layered GCN and the final test accuracy is reported averaged over 10 splits. We report the hyperparameters such as the Normalized Mutual Information (NMI) between the cluster labels and the ground truth labels after community detection (Blondel et al. 2008) before and after rewiring the graph to understand how it affects the community structure- node label alignment. We also report the number of edges added and deleted to effect the required change in test accuracy. The empirical runtimes, in seconds, are presented in seconds in Tables 6 10 Our code is available here: https: thub. com Re at on ML.
23

---

Published as a conference paper at ICLR 2025
Table 5: Dataset statistics.
Dataset
#Nodes
#Edges
NMI
AMI
ELI
Homophily
Modularity
Cora
2708
10138
0.4556
0.4489
0.5802
0.7637
0.8023
Citeseer
3327
7358
0.3270
0.3151
0.4437
0.6620
0.8519
Pubmed
19717
88648
0.1973
0.1966
0,4092
0.6860
0.7671
Cornell
183
277
0.1250
0.0202
0.1556
-0.2201
0.6227
Texas
183
279
0.0673
0.0016
0.19234
-0.2936
0.5548
Wisconsin
251
450
0.0867
0.0351
0.1310
-0.1732
0.6293
Chamelcon
890
8854
0.1035
0.0823
0.0138
0.0295
0.6680
Squirrel
2223
57850
0,0176
0.0153
0.0013
0.0086
0,4451
Actor
7600
26659
0.0044
-0.0002
0.00017
0.00277
0,5113
CS
18333
163788
0,5528
0,5501
0.6467
0.7845
0.7321
Photo
7650
238162
0.6845
0.6835
0.6662
0.7850
0.7363
Physics
34493
495924
0.4376
0.4372
0.7222
0.8724
0.6627
Roman-Empa
22662
32927
0,0214
0.0030
0.1101
-0.0468
0,9887
Amazon-Ratte Ratings
24492
93050
0,0426
0.0381
0.0398
0.1402
0.9645
Minesweeper
10000
39402
0.0011
0.0004
0.0001
0.0094
0.8860
Table 6: Empirical runtimes for FeaSt based rewiring.
Dataset
AvgTestAce
NMIBefore
NMIAfier
EdgesAdded
EdgesDeleted
Rewire Time (6)
Cora
87.73020.390
0.456
0.432
1000
9.333
Cora
90.740=0.390
0.456
0.432
0
500
9.637
Citeseer
78.540+0.34
0.327
0.338
1000
8.549
Citeseer
81.600=0.390
8,422
Pubmed
86.43010.090
0.197
0,206
1000
0
89.224
Pubmed
86.760=00.00
0.197
0.196
0
50
89.745
Comell
59.460:11499
0.125
0.099
7.402
Cornell
51.350=
0.125
0.114
7.525
Texas
54.050=1.55
0.067
0.063
5
0
7.630
Texas
64.86011 140
0.067
0.190
7.568
Wisconsin
Wisconsin
60.000
0.087
0.134
0
50
7,538
Chaneleon
43.260=00622
0.103
0.103
20
0
9.513
Chameleon
20
Squirrel
35.510=0 440
0.018
0.018
14.566
Squirrel
36.40H=0.56
0.018
0.018
0
100
13.219
Actor
31.250+0.22 220
0.005
100
79.587
31.970+0.210
0.004
0.006
78.594
Table 7: Empirical runtimes for FeaSleAd
Dataset
AvgTestAcc
NMIAfter NMIBefore
EdgesAdded
EdgesDeleted
Rewire Time (s)
Cora
85.710+0.360
0.456
0.464
10
10
11.450
Cora
85.710a0.366
0.456
0.464
10
11.450
Citeseer
80.190=0.344p
0.327
0.322
50
10.777
Citeseer
190:00033344
0.327
0.322
50
50
10.777
Pubmed
87.010=0.122
0.197
0.198
1000
1000
97.618
Pubmed
1000
97.618
Comell
54.050a1.66
0.125
0,115
5
8.774
Comell
54.050+1 660
0.125
0.115
8.774
Texas
56.760:1.66 1600
0.067
0.165
100
8.747
Texas
56.760=1.655
0.067
0.165
100
8.747
Wiscousin
58.000+1 1.000=1+.20
0.087
0,120
50
50
8.079
Wisconsin
58.000=1 1.600
0.087
0.120
50
8.079
Chamelean
Chaneleon
44.940=0.770
0.103
0.158
100
100
8,780
Squirrel
35.730+0.480
0.018
0.019
500
500
13.645
Squirrel
35,73020
0.019
500
13.645
Actor
32.630+0.210
0.004
0.008
50
82.668
Actor
32.630+0.210
0.004
0.008
50
50
82.668
24

---

Published as a conference paper at ICLR 2025
Table 8: Empirical runtimes for ComPy
Dataset
AvgTestAce
NMIBefore
NMIAfter
EdgesAdded
EdgesDeleted
Rewire Time (s)
Cora
87.73+0.26
0.4556
0.4580
14.99
Cora
88.13+0.27
0.4556
0.44876
2000
18.39
Citeseer
77.3620.38
0.32701
0.32492
100
11.75
Citeseer
78.07=0.35
0.32701
0.35509
1000
11.86
Pubmed
86,74=0.11 10
0.19726
0,19572
50
0
415.23
Pubmed
86.23+0.11
0,19726
0,20603
2000
415.59
Comeell
67.57=1.68
0.1249
0.0955
9.91
Cornell
70.27+1.50
0.1249
0.1269
9.50
Texas
62.16=1152
0.0672
0.0678
10
9.74
Texas
64.86+1.51
0.0672
0.0915
9.74
Wisconsin
62.00+1.12
0.0866
0.1526
50
0
9,79
Wisconsin
66.00=1.34
0.0866
0,1180
50
10,36
Chameleon
41.57=0.83
0.10349
0,14758
13.98
Chameleon
45.51+0.76
0.10349
0.10340
10.94
Squirrel
36.85+0.38
0.01762
0.01762
17.51
Squirrel
39.10:3.43
0.01762
0.01762
1500
20.98
Actor
32.30=0.25
0,00436
0.00491
500
0
143.81
Actor
31.12#0.19
0,00436
0,01364
2000
141.79
Table 9: Empirical runtimes for HigherComMa based rewiring.
Dataset
AvgTestAce
NMI
EdgesAdded
EdgesDeleted
FinalGap
Rewire Time (s)
Cora
83.64=0.38
0.4531
100
0.004825
0.06
Cora
83.82=0.31
0.4565
127
0.003925
0.05
Citeseer
0.40
0.3252
10
0.001555 0
0.03
Citeseer
77.31=0.41
0.3273
0.001551 10
0.03
Puhmed
85.83=0.11
0.1933
50
0.014013 0
7.47
Pubmed
85.90=0.11
0.1975
0.013990 50
8.67
Cornell
49.03=1.26
0.1283
0.079053 0
0.01
Cornell
49.93=1.34
0.1038
0.000001
0.01
Texas
52.66=1.47
0.0633
0.072213
Texas
48.57=1.53
0.0695
0.062387
0.01
Wisconsin
50.55=1.24
0.0886
0.074916
0.01
Wisconsin
50.32=1.38
0.0866
10
0.068169
0.01
Chameleon
41.23=0.72
0.1536
100
0.006417 0
0.04
Chameleon
40.44=0.69
0.0875
0
20
0.005920
0.04
Squirrel
34.51=0.40
0.0176
20
0.051575 0
0.63
Squirrel
34.6620.39
0.0150
1000
0.050114
0.68
Actor
30.9240.21
0.0080
20
0.032282
6.57
Actor
30.71=0.24
0.0222
0.032679
6.42
Table 10: Empirical runtimes for HiggherCoMMa--adddddtttt based rewiring.
Datuset
AvgTestAcc
NMIAfter
EdgesAdded
EegesDeleted
FinulGap
Rewire Time (s)
Cora
83.820+0.340
0.463
50
100
0.004
0.06
Citeseor
77.320+0.380
0.332
0.000
0.03
Puhmed
85.830+0.110
0.195
100
50
0.014
7.14
Cornell
1889
0.113
10
17
0.000
0.01
Texas
52.440#1..40
0.067
100
10
0.068
0.01
Wisconsin
51.350+1.400
0.091
20
0.069
0.01
Chameleon
41.220+0.750
0.094
0.004
0.04
Squirrel
34.700=0.400
0.016
20
500
0.051
0.82
Actor
30.810+0.196
0.025
100
50
0.032
6.88
25

---

Published as a conference paper at ICLR 2025
Table 11: Empirical runtimes for LowerComMa based rewiring.
Dataset
AvgTestAce
NMIAfter
EdgesAdded
EdgesDelered
FinalGap
Rewire Time (8)
Cora
83.47
0.4604
0.008448
0.693458
Cora
83.61
0.4583
0.004784
0.663406
Citeseer
77.15=0.36
0.3195
10
0.001556
0.686848
Citeseer
77.39=0.37
0.3240
0
4
0,001555
0.697997
Pubmed
85.85=0.090
0.1899
0.014267
13.045066
Puhmed
85.90+0.10
0.1844
0.014069
11.933355
Cornell
11.08
0.0695
100
3. 261
7.787908
Cornell
49.6 49.69+1.43
0,1249
0
0,080970
7. 7.69681 15
Texas
50.29=1.71
0.0516
100
0.201174
8.309750
Wisconsin
50.95=1.29
0.1094
0.089029
8.400457
Wisconsin
50.61
0,0886
0.076910
8.699127
Chameleon
40.61
0.0791
50
0.007699
8,595781
Chameleon
40.43+0.71
0.1034
0
17
0.006315
8. 8.385635
Squirrel
34.48+0.39
0.0207
100
0.056416
10.908470
Squirrel
34.76:00.40
0.0166
12
0.051370
9.688496
Actor
30.79+0.23
0.0055
500
0.070495
17.127213
Actor
30.79+0.22
0.0077
0.032679
15.543629
Table 12: Empirical runtimes for LowerCooMaa+addd-ellee based rewiring.
Datasct
AvgTestAcc
NMIAfter
EdgesAdded
EdgosDeleted
FinalGap
Rewire Time (s)
Cora
83.73=0.32
0.4466
10
2
0.007464
0.660313
Citeseer
77.42+0.38
0,3197
0.001556
0.4274877
Pubmed
85.87=0.10
0.2036
0.014268
13.815228
Cornell
52.3621.52
0.0690
100
0.132826
8.077217
Texas
51.621.53
0,0516
100
0
0,201174
7.848707
Wisconsin
$1.45=1.33
0.1096
5
4
0.078300
7.622503
Chameleon
40.920.66
0.0995
20
17
0.007556
7,997294
Squirrel
34.75=0.41
0.0187
100
0.056383
10.509906
Actor
30.85=0.23
0.0034
0.036560
15.892848
Table 13: Different community detection metrics for various datasets after applying FeaSt.
XMIBefore
NMLAfter
AMIAfer
ModulantyBefore
Modalariy
Chanccosus
0,1035
0.3055
0.0233
0,6680
0,6580
0.0138
0.0295
0U1295
44.94a1177
0,0176
0,0177
0.153
0.4451
0,801325
0.00133
0.0061
0.00669
35.73a1144
04456
04420
0.339
0.580
07537
076455
87. 87.33
0,5570
0.3400
03111
0.3212
0,8519
0.6620
016854
78 38.55e1
Chanceloss
0,1035
0.1047
0.0823
0.8099
0,6680
0.1295
0.1297
47.19H0162
0,0766
0.0154
0.0133
0.4451
0,801325
0.00133
0.00661
0.00865
57.75a11.39
Table 14: Different community detection metrics for various datasets after applying ComFy.
ComFy-Aii
Dutuset
NMIBefore
XMLABer
AMdlBefor
AMIAPer
ModulartyBeforre
Modalariz,Allrr
HomBeoore
HondAfer
13:1365:26
0.3570
0.3297
0,5620
Chanokon
0.1055
B0042
0.6687
0.0785
17.10-0.6
0.0766
8.0176
0.153
00153
0.4551
0.4451
37.75x0130
ComPy
0.3570
81.5740.36
Chamcloon
0.1055
40.51+0644
37.75x0142
C.3 SENSITIVITY TO HYPERPARAMETERS
The hyperparameters used in the experiments are given in Table 15 Roman cemannemmpre, mmazon--attnge and Minesweeper we use the model hyperparameters recommended by the authors (Platonov et al. 2023b). However, found setting the learning rate to 3e instead of 3e yields better results. The GCN hyperparameters on the other datasets are tuned based on the validation set through grid search. As is common, found that the performance of not only our
For the large heterophilic datasets
26

---

Published as a conference paper at ICLR 2025
method but GNNs in general is sensitive to the learning rate but otherwise robust across datasets and architectures. Our rewiring techniques do not require any change of the basic GNN hyperparameters. In fact, we the same
as the baselines. Our rewiring methods come with additional hyperparameter, i.e., the rewiring budget (and thus how many edges are added or deleted). This is true for all the rewiring methods that have been proposed (Topping et al.] [202]] Karhadkar al. 2023
Giraldo et al. 2023 Nguyen et al. 2023; Black et al. 2023] Jamadandi et al. (024)) in the literature. In Table 16 and Table 17 we present results for 4 datasets Cora, Citeseer, Chameleon and Squirrel and how their performance varies with respect to edge modification budgets. While the performance is clearly sensitive to this choice, the rewiring budget seems be task specific but not very architecture specific, as we could use the same budgets for different GNN variants, such as GIN and GraphSAGt:
Table 15: GCN hyperparameters used in the experiments.
Dataset
LR
Dropout
HiddenDimension
Cora
0.01
0.41
128
Citeseer
0.01
0.31
32
Pubmed
0.01
0.41
32
Cornell
0.001
0.51
128
Texas
0.001
0.51
128
Wisconsin
0.001
0.51
128
Chamelcon
0.001
0.21
128
Squirel
0.001
0.51
Actor
0.001
0.51
CS
0.001
0.51
512
Photo
0.01
0.51
512
Physics
0.01
0.51
512
Roman-empire
0,003
0.31
512
Amazon-ratings
0,003
0.31
512
Minesweeper
0.003
0.31
512
Table 16: GCN test accuracy variability for different edge budgets for FeaSt.
GCN-FeaSt
Datnset
EdgesAdded
Accuracy
EdgesDelettd
Accuracy
85. 15.117
10
82,49H 39
79.88:0.41
50
83,7010.34
76
500
R3.90-0.33
500
90.74=0.39
1000
87.73s0.39
1000
85,5110.31
77.36+0.35
$1.60=0.39
50
77.59.0.33
50
74.0610.38 33
Citeseer
75 75.2440).4
100
78.30+0.3
500
75, 94+0.
75, 75.71-4
1000
78.54410.4
1000
75.00 75.0010.35 33
20
43.26tll
42.70s0.66
38, 20:0.
01 68
Chameleon
100
41.0110.66 64
100
35. 96.96660666
500
37. 37.08e0.c
500
40.45
1000
40.4550.62
1000
39.3340.73
20
33 26660 38
34, 3850 40
35.5110.44
Squirrel
100
33.4850.44
36.40:10.66
500
33 26+00.37
500
33,71+0. 39
33.2610..38
32.3610.38
D ADDITIONAL EXPERIMENTS
D.I COMPARISON WITH VARIOUS BASELINES
Arnaiz-Rodrigues et al. 2022 Dong & Kluger 2023) in Table 18 In Bi et al. 2023) the authors suggest to use multi- order moments model neighbor's 's feature distribution and propose MM-GNN to use multi-order moment embedding and an attention mechanism to weight importance certain nodes going beyond single statistic aggregation mechanisms such mean, and sum. In (Amaiz-Rodae Rodriize al.
We compare proposed algorithms with other diverse methods ( al. 2023
27

---

Published as a conference paper at ICLR 2025
Table 17: GCN test accuracy variability for different edge budgets for ComFy
GCN&ComFy
Datnset
FidgesAdded
Accuracy
EdgesDeleted
Accurncy
50
86. 26.72+0.27
500
86.52+0.27
100
87,73+0.26
1000
84.31=0.27
Coru
500
86. 36.1244 2240.32
1500
85.71=0.31
1000
85,11
2000
88.13=0.27
50
77.36+0.38
75,24 38
100
77, 77.66200.38
1000
78.07=0.35
Citeseer
75.47:0.33
1500
76.42:0.36
1000
2000
74.76a0.39
35, 39.00.
100
41 71.57=0.73
38, 20 73
37.08+0.69
Chameleon
50
41.01a0.66 64
1000
44.38:00.9
100
41, 41,57=00.88
1500
46.51=
500
39.33s0.60 0.60
2000
12:1 74
36.85+00.35 38
100
35.51=0.41 411
30, 00.34400.44
33.71+0.40
Squirrel
50
34, 16t50.41
1000
37.08::0441
100
32.81+0033
1500
39.10=0.43
500
34.6110.42
2000
36.85:0.39
2022). the authors propose DiffWire, an inductive way to rewire the graph based on the Lovász bound by formulating two new layers that are interspersed between regular GNN layers. In (Dong & Kluger
2023) the authors propose a way to de-noise the graph by proposing graph propensity score (GPS) and GPS-PE (with positional encoding) methods rewire the graph. Although the authors call their method "graph rewiring", the proposal involves separating edges in the graph as training edges and peessag--aassing edges and use a sule-suue link prediction task to impute edges between nodes. Note that these methods go beyond rewiring-as-4 as----r----- pre-processing' paradigm, which is the case for all our proposed algorithms. We report the results reported in their respective papers, and hence NA for some datasets. Not all code is made available for reproducing the results. We also report our proposed algorithms with different variant of GNNs such as GIN (Xu et al.) 2019) and GraphSAGE (Hamilton et al. 2017b) to emphasize on the fact that rewiring algorithms can be combined with any GNN model. The top performance is highlighted in bold. From the table we can clearly see that our proposed algorithms outperform the chosen diverse baselines on 6 out of 9 datasets.
Table 18: Additional baselines with diverse methods.
Method
Citeseer
Puhmed
Comell
Texas
Wisconsin
Chameloon
Squirel
Actor
MM-GNN
84.31+0.56
73 03300.0
80. N0.26m00.09
NA
NA
NA
63.32 1.31
51.38 + 1.73
NA
GCifDiffWire
$3.6640.66 60
72 26.00.5
86.07=0.10
69.04+222
NA
79.05=2.1
NA
NA
31.98=0.30
GPS
80.510.50 79.510.30 80
71 71.5a00.0
77.740.30
74.623.00
80.0s1.80
77.324.40
41.523.60
43.0a0.90
38.320.70
GPS-PE
71.5100.00
77.710.50
68.611170
15.11
78.821.50
37.611.60
31911.30
OCN-FosSIAdd
87.7310 39
86.43:0.00 39.66110.99
54.00.34
59.46111.0 499
54.0511.51
60.0021.00 1.09
43,261062
39 39.33.1.73
31.2550022
GCN-FenStDel
90.74::0.39
86. 86.76-0.10 10
51.35+1.45 63
64 36661.14 .43
60.00=1.27
42,70H0
36.40H1)99 36
31 17.0...21
GCN Frdd
87.73+0 26
77 36+4) 38
26.74-01.0
67.57+1.4 68
62 16+1.52
62.00=1.12
41,57+0.3
12. 30.3000..2
ComD
$8.1 27
86.23=0.11 78.07+0.35
70.27+ 50
64 16.1151
1..00
45.51=0.76
39. 10:0.44
31.12=0.19
Gid+
87.12+0.5
75.7140.41
88 36-0.11-1
51.35+1 62
70.27++.44
62.00=1.40 .40
42.70H0.64
20114:44
28 28.62-0.23
PaaSiDel
55.31+0 34
73. 17.35+00.44 48
89.83=0.12
59 19.46611.7
72. 12.97+11.4
70.00=1.31
45.51+0.00
40.6740.43
29.21=0.25
GIN+ComPPAAe
64.1060.25 28
75 00000.6
89. 75
62. 1ei6 199
67. 11.5771144 48
1..00
46.07+0.72
38. 38.4300.47
29.74=0.21
GeN
85.7110.37 37
74 21229.0.35 39
88. 18..6600.11
56.7611.60
55
1.42
51.1240.73
40.6720.54
30.33=0.22
26
11.01110.11
11.0811.16
6811.52
80.00
44.9110.78
35.7320:113
37.3720.22
S FesSFee
87.3210 30
42442...22 39
87. 02.6220.11
78, 06..881112 46
0811.41
66.0021.00 1.0
49.1910622
37.7510.39
37. 17.7620.21
Graphi ACit-Co Add
89. 13+0 26
81 37410.36
8M. 11=009
89. 1w.19=11.77
81 D8e1.55
1166
43 43.02H0-77 72
37 30H0.41
35 26-0.22
GrpbSAGF &ommPyy
88.33+0.31
81 60H0.37
88.03 08.03-0.111
78.38+1.41
13.78+1.47
78.00=1.13
45.51+0.64
37.7540.42
36.45=0.22
D.2 SCALABILITY
We present additional results for large homophilic graphs to understand how our proposed algorithms scale with increasing graph size. The statistics for the datasets used is presented in Table 5] We present results on CS, Physics, and Photo (Shchur et al.] 2019) available as Py PyToorc geometric datasets. We train a two-layered GCN with the following hyperparameters, the learning rate (0.001, 0.01} and hidden dimension size = 512. The results are presented in Table 19 Further, we pick the largest dataset among these which is Physics with 34, 493 nodes and 495, 924 edges and run a version of our algorithms which samples the nodes randomly and calculates the feature similarity and rewires only on the subset of those nodes. We use sampling ratio 0.2 to represent 20% of the nodes. The results are presented in Table 20 Clearly from the table,
see that our proposed algorithms are robust,
28

---

Published as a conference paper at ICLR 2025
in that, can bring down the runtime significantly and still obtain comparable accuracy to the full graph.
Table 19: Node classification results on large homophilic graphs.
Dataset
Method
Edges Modified
Rewire Time (s)
Accuracy
GCNBaseline
NA
NA
91.76+0.08
FeaStAdd
500
52.20
90+4000
CS
FeaStDel
10000
53.52
92.71+0006
ComFyAdd
100
318.58
91.98+0.06
ComFyDel
500
331.71
92.30+0.08
GCNBuseline
NA
94.55+0.04
FcaStAdd
100
190.24
94.85+0.00
Physics
FeaStDel
500
192.07
95.01+0.05
ComFyAdd
100
1282.06
95.04+0.05
ComFyDel
500
1300.39
94.69+0.05
GCNBaseline
NA
NA
78.70
FeaStAdd
100
42.63
79. 79.10#0.4 .47
Photo
FeaStDel
10000
40.34
81.10#0.51
ComPyAdd
100
82.49
77.30+0.60
ComFyDel
1000
80.94
81.60:0.49
Table 20: Node classification results Physics dataset with node sampling.
Sampling ratio
Method
Rewire Time
Accuracy
FeaStAdd
190.24
94.8520.05
FeaStDel
192.07
95.01
100
ComFy Add
1282.06
95.04:0.05
ComFyDel
1300.39
94.69+0.05
FeaStAdd
32.60
94.60: 14.6020.05
FeaStDel
33,03
94.8620.04
20
ComFyAdd Add
718.40
94.6240.05
ComFyDel
713.65
94.53+0.05
D.3 RESULTS WITH DIFFERENT GNN VARIANTS
In Table 21 we present results for GIN (Xu et 2019) and GraphSAGE (Hamilton al. 2017a) variants, demonstrating that our rewiring schemes are architecture agnostic and can be used as pre- prepprocsssig step make the input graphs amenable message-passee passsgg...ssng. We also add MLP as baseline.
Table 21: Accuracy node classification with GIN and GraphSAGE.
Method
Com
Citeseer
Puhmed
Comell
Texas
Wiscoesin
Chameleon
Squirrl
Actor
MLP
73.0240.33
70.84.0.51
67.6840.10
73.541:144
76.22.1.45
$1.6811.06
35.7020.69
31.8410.40
36.0510.23
GIN
85.5110
74.53.0.41
37.8411.62
51.0511.61
56.00u1.21
41.5720.64
37.08.0.3
24.2110.22
GIN-FesSLAMI
87.1250.3
75.71=0.41
88. 36x0..111
51.35=1.62
70.27a1.48
62.00:1
42.70:0.64
38 20:0448
28.62:0.23
GiN+FeaS:Del
85.3110.34 34
73.3520.48
89.8320.12
59.4611.75
72.97.1.34
70.00u1.31
45.5120.60
10.6710.43
29.2110.23
GlN-ComFyAdd
$4.10u0.23
75.0010..46
89.7510.14
62.1611.99
67.57a1.48
18.0013333
46.0720.72
38.4310.47
29.7410.21
GoN+ComFyDel
85.7120.37
74.29s0.39
51.1220.73
GraphSAGE
87.7340
77.12=0.31
86.56s0.10
67.5721.36
78.3821.37
76.00+1.18
38.76e0.61
35.9620.38
35.99g0.21
89.7410.26
79.1180.110
86.8410.11
$1.0811.46
75.68.1.52
80.0011.01
44.9120.78
35.7310.43
37.3710.22
GraphS FesStee
87 07.3240.22
$0.42=0.39
87 $7.62a0..0
18.38
$1.08:1.43
86.001=1077
47.19=0.62
37.7540.39
37.76650.1
GraphSAGE ComPPydddd
$1.37=0.36
89.19s1.37
86.00:1.06
43.8220.72
37.30s0.41
35.8660.22
GriphS Cmpph-AGP&Comffee ComfyDee
88 38.3340.31
$1.60:0..37
88.03+0.11
78.38+1.4
83.78+1.47
78.00+1.13
45.51=0.64
37.7540.42
36.4560.22
D.4 OUR ALGORITHMS AGAINST FEATURE NOISE
To understand how proposed algorithm perform in presence of feature noise, artificially add Gaussian noise with 0 mean and standard deviation (0.01, 0.03, 0.05, 0.08, 0. 0.2) controlling the level of noise. We compare proposed algorithms FeaSt and ComFy against the baseline GCN for
29

---

Published as a conference paper at ICLR 2025
increasing feature noise. We add/delete 10 edges. This is shown in Figure for datasets Chameleon and Squirrel. Evidently, our proposed algorithmss are robust to noise perturbations and consistently outperform the baseline by large margin.
110
(a)
(b) FeaStt-Squirel--eetuueeeee
FeassrCChameeon-FFatuueeiii
(d)
ComfyySqqiirdoFFaauuceoiss
Figure We analyse the behaviour of GCNs and our rewiring methods FeaSt and ComFy in presence of feature noise.
D.5 OUR ALGORITHMS AGAINST LABEL. NOISE
To understand how our algorithms perform in presence of label noise, we randomly flip a certain
percentage of labels in the training node before rewiring the graph. We flip {0, 3, 5, 10, 20, 50} percent of the labels and compare the baseline GCN and our methods FeaSt and ComFy with 10 edge additions/deletions. We plot the results in Figure 8, for increasing label noise, we can see that our methods are as robust as the baseline, because they lose performance at the same rate.
D.6 OUR ALGORITIMS ON SBMS WITH LOWER COMMUNITY STRUCTURE
Using the same setups as in the proofs for Theorems 2 and we evaluate the performance of ComMa (Figure 9) and ComFy (Figure 10) SBM graphs with varying levels of community strength, under edge additions or deletions of 0, 50, 200, 500. Classification accuracy is measured via a simple mean aggregation step across four tasks, defined by different levels of alignment between labels and communities: v E 0.7, 0.8, 0.9, 1.0. Results are averaged over 8 seeds.
200,500,
Levels of community strength. For 2-class, n-node SBM with (p.
a la(n! bln(n) is
n
m
known Abbe 2018 Thm. 13) that the community structure is recoverable when Iva vbl > 22.
For 100 and g 0.2, this implies community detection threshold of
0.2n In(n)
+ 2
In(n) 0.56. Values below this threshold can be seen as having low community structure. We analyze four settings: three below and one above the threshold, with p E 0.3, 0.4, 0.5, 0.6.
Behaviour SBMs for ComMa. This particular SBM setup obtains performance gains as com- munity strength increases although this is not guaranteed for all types of graphs and tasks. In this case, HigherComMa (Figure can show advantages, but will suffer when the graph structure cannot be recovered. This is the case for = 0.3, especially with edge additions. However, for p 0.4 and p 0.5 (both still below the threshold), edge additions provide consistent benefits.
30

---

Published as a conference paper at ICLR 2025
(a)
(b) FeaSttSSqinell-Labbll
(c)
(d)
CCufFy--Chameooon--LLdlllii..
Comfyy-Squirdd-LLablllosss
Figure 8: We analyse the behaviour of GCNs and our rewiring methods FeaSt and ComFy in presence of label noise.
For p 0.6, where the community structure becomes clearer, deletions cease to be useful, and performance plateaus as the number of deletions grows.
Behaviour on SBMs ComFy, ComFy (Figure 10p is effective when the community structure is not clear, as it enhances the communities signal via feature denoising (e.g., for = 0.3). As increases, tasks with high alignment (t 1.0) gain little from ComFy, while those with noisier label 0.7) continue to benefit.
alignments (1) 0.8,
Behaviour on SBMs for FeaSt. In this simple setup with only two communities. ComFy's distribu- tion of communities is not required for good performance. In fact, its trends match those of FeaSt, as shown in Figure 11 Yet, Feast shows higher improvements absolute terms (especially high Alignment e 1) due the homophilic setup considered.
These trends align with our theoretical predictions 2..3 and are also consistent with the results observed real-world GNN benchmarks (44)
31

---

Published as a conference paper at ICLR 2025
MeanAccuracy for SBM (0.3,0.2)
MeanAccuracy for SBM (0.4,0.2)
0.75
Alyymerr
0.55
-+- 1.0
- 1.0
0.72
0.72
0.54
0.82
0.01
Rigament
0.725
Algnme 08
0.623
0.702
Aignmart
0.42
0.6
Aignnart 0.1
0.38
-420
-000
200
430
-40
200
200
420
Eages Modiflie by ComMa
Edges Moditled by ComMa
(a) For p 0.3.
(b) For = 0.4.
MeanAccuracy for SBM (0.5,0.2)
MeanAccuracy for SBM (0.6.0.2)
1,000
Akgmmmt 3.0
5.50
2.55
Aigimant
Ag mon
0.89
0.50
3.775
3.750
Algnmant
0.78
A Aghmmn -a-
3.75
0.65
Aggmmmt 2,2
0.65
3.500
203
2t0
400
402
200
420
Edges Modified by ComMa
Edges Modified by ComMa
(c) For 0.5.
(d) For p 0.6.
Figure 9: The effect of ComMa on mean aggregation in SBMs for low levels of community strength. Each figure is different (BM-(p, 0.2). Their rows are different levels of alignment.
MeanAccuracy for SBM (0.3,0.2)
MeanAccuracy for SBM (0.4.0.2)
Aignmurt - 1.0
0.90
Algnnar - 3.0
0.83
0.01
0.75
0.1
Algament
0.3
Alyymenn 0.8
0.3
Alggment 0.7
0.8
Algnnur 0.7
0.7
-100
-2m0
200
<00
-100
-300
203
400
Edges Modified by Comfy
Edges Modified by ComfFy
(a) For p = 0.3.
(b) For p = 0.4.
MeanAccuracy for SBM (0.5,0.2)
MeanAccuracy for SBM (0.6.0.2)
525
2.5
3.75
Algrmmt 3.9
3875
3.055
3850
0.50
Algnmant 5.
6.75
3.755
2,5
0.75
6.6%
-103
-203
400
670
5.55
-103
-203
250
42a
Edges Modiried by Comify
Edges Modified by Comffy
(c) For 0.5.
(d) For p 0.6.
Figure 10: The effect of ComFy on mean aggregation in SBMs for low levels of community strength. Each figure is different SBM-(p, 0.2). Their rows are different levels of alignment.
32

---

Published as a conference paper at ICLR 2025
MeanAccuracy for SBM (0.3,0.2)
MeanAccuracy for SBM (0.4,0.2)
0.09
Algymerr --- 1.0
Algimer
0.80
1.0
0.00
0.75
Aligmment
0.0
A Aignmurt
0.22
Alggmerr 0.7
400
200
203
400
440
200
200
420
Edges Moditied by
Edges Modified by Fea
(a) For p 0.3.
(b) For p = 0.4.
MeanAccuracy for SBM (0.5,0.2)
MeanAccuracy for SBM (0.6.0.2)
0:05
230
0.00
3.6
Aigimaat
2875
A Aggmmn
3.0
A memt -#- 2.5
3.75
3.65
377
400
400
Agnmant 2,2
0.25
630
0.55
4002
200
400
Edges Modified by FeaSt
Edges Modified by FeaSt
(c) For 0.5.
(d) For p 0.6.
Figure 11: The effect of FeaSt on mean aggregation in SBMs for low levels of community strength. Each figure is different SBM-(p, 0.2). Their rows are different levels of alignment.
D.7 ILLUSTRATION OF HEOREM
In Figure 12 we show 3D plots illustrating the expected proportion of misclassified nodes P(M) in Stochastic Block Model (SBM) as described in the setting in Theorem 3 In the plots, when P(M) is low (yellow), performance is better, and when it is high (purple), performance is worse. The plot shows P(M) as a function of alignment vi, and different configurations of (p, q):
12(a) for ab and the theoretical spectral gap formula in the limit p+g
P-g from Theorem
12(b) and 12(c) for p and q given fixed di {0.7, 1.0]. As s increases, the minimum (purple) and maximum (yellow) possible performance extend their range.
[2(d) e2(c) 12( for vó and given fixed values of q E (0.2, 0.7). As the value of increases, the community structure is less pronounced. Therefore, the range of values of p for which performance can achieve 100% (in yellow) becomes more and more narrow.
33

---

Published as a conference paper at ICLR 2025
100
(a) Against and 9-2 p-y
Fixed 0.7.
(c) Fixed d
(d) Fixed g = 0.2.
(c) Fixed g = 0.5.
(f) Fixed g = 0.7.
Figure 12: Plots illustrating the expected proportion misclassified nodes P(M) from Theorem
34


Reviews:
[{"review_id": "YrFkYdkFeg", "reviewer": "Reviewer_zHQo", "summary": "While the existing rewiring technique aims to maximize the spectral gap, this paper aims to minimize the spectral gap.\nThis paper explains the benefit of minimization through the example of a stochastic block model.\nBased on the analysis, this paper proposed three rewiring strategies: comma, feast, and comfy.\nThis paper demonstrates the effectiveness of the proposed methods.", "questions": "See weakness section.", "limitations": "", "rating": 3, "confidence": 3, "soundness": 1, "presentation": 1, "contribution": 1, "strengths": "The extensive experimental results.", "weaknesses": "Thm. 1 seems to be very incremental; in which part do the authors claim the result is novel? The second eigenvalue of the Laplacian of the expected SMB is almost folklore.\n\nRight below the Thm.1, the authors claim as follows; \" increasing q and decreasing p increases the spectral gap but makes the community structure less pronounced, and vice versa\"\n\nHowever, if we believe that the spectral gap is proportional to q-p/q+p, the gap is larger when p=0.3 and q=0.0001 than when p=0.9 and q=0.1. However, it is intuitive that the former provides the more pronounced community structure, albeit the larger spectral gap. If the rest of the authors' observations are based on this result, how can I believe that the larger spectral gap is less pronounced community structure?\n\nThm. 2 seems that the features do not have assumption. However, its proof immediately assumes that the the feature follows normal distribution. Therefore, the proof of the Thm.2 seems  incomplete. \n\nIn Sec. 3, the authors' proposed three algorithms based on the theoretical observations; however, I wasn't able to pull out which part of the algorithm reflects the theoretical observations. Part of which may be due to the algorithms are in Appendix, which also may be the major formatting issue of this paper. \n\n\nSince the theoretical results are not reliable, and the algorithmic improvement is unclear, I vote for rejection.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eS5CiEHce4", "reviewer": "Reviewer_gkN7", "summary": "The paper presents a hybrid graph rewiring method to increase classification performance on node-level classification tasks. Motivated by theoretical finidings on the planted partition model with features, the authors show that the desired edge addition and deletion strategies change deopending on whether the graph structure is homophilic or heterophilic and how strongly the targets are aligned with the structure of the graph. Therefore, the authors present ComFy, which performs the rewiring independently for each pair of communities thereby respecting the graph structure and more evenly spreading the edits over the graph.", "questions": "- How do the proposed methods scale with increasing graph size? (Computing pairwise feature similarity may already be a problem for large graphs.) Are there optimizations or approximations that can make them more efficient for large-scale graphs?\n- How robust are these methods when dealing with noisy or incomplete data? Do they still perform well when node features or labels contain errors?\n- How sensitive to hyperparameters are the models? Both concerning the buget for rewiring and the hyperparameters of the GCN?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Good theoretical motivation through planted partition model.\n- Extensive experiments on many benchmark datasets show the methods efficacy against the competition.", "weaknesses": "- Comfy is actually missing from the main text - not only the algorithm but also a textual explanation is very lacking.\n- Planted partition model with only 2 communities is very simple and does not reflect real-world datasets.\n- The elected competitors are highly related to the proposed method. A More diverse competition would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jFubRU090d", "reviewer": "Reviewer_NZqY", "summary": "In this paper, the authors introduced three novel graph rewiring techniques designed to improve the performance of Graph Neural Networks by focusing on the alignment between the graph structure and the target task. Experiments confirm the effectiveness of these strategies and support theoretical insights.", "questions": "(1) Could the authors further explain the setting of hyper-parameters, such as increasing or deleting the number of edges, and how it affects the performance of the model?\n\n(2) Will the performance of ComFy strategy decrease due to the unclear structure of the original community? The authors should better discuss this situation.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) The author established a systematic theoretical framework through the Random Block Model and analyzed the impact of community strength and graph task alignment on GNN performance. To some extent this paper enriched relevant theoretical research.\n(2) The proposed FeaSt and ComFy  integrate feature similarity into graph rewiring methods, exploring how to optimize the performance of GNN by considering node features.\n(3) In addition to theoretical analysis, the paper also demonstrated the performance changes of GNN under different alignment levels of graph tasks by generating Random Block Model (SBM) graphs with different alignment levels. The proposed methods have a certain degree of scalability.", "weaknesses": "(1) The article is mainly based on the Random Block Model (SBM) for theoretical analysis, but real-world graph data often has more complex structures and dynamic changes, and the assumptions of SBM may not fully capture these complexities.\n(2) The method proposed in the article does not clearly explain and analyze the impact of adding or removing edges on model performance.\n(3) The article did not discuss in detail how the proposed rewiring strategy performs in situations where the community structure is unclear or there is some noise.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BU121OY1k8", "reviewer": "Reviewer_tdhE", "summary": "The authors propose different network rewiring approaches as a preprocessing step to align network structure with downstream tasks. More specifically, they consider adding or removing edges guided by the network's community structure as determined through modularity maximisation with Louvain. They also consider adding and removing links guided by the nodes' attributes. This approach is guided by the idea of presenting graph neural networks, which use the network itself as their computation graph, with more meaningful edges. By doing so, the authors hope to combat issues such as oversmooting and squashing. They evaluate their approach empirically on a set of real-world networks with homophilic and heterophil link patterns. They achieve better node classification performance than some baselines on some of those networks.\n\nI find the paper well written and easy to follow, however, there are a few points that remained unclear to me.", "questions": "- What task is actually considered in the paper? While the authors discuss node classification, it seems very close to community detection to me. In that case, I don't find it surprising that node classification performance improves as the network is modified such that community structure becomes stronger. Could the authors clarify how they are doing node classification? For example, is it done in a semi-supervised fashion where 80% of the nodes have labels and the remaining 20% should be predicted by the GCN, or similar? If that is so, are ground-truth labels required for the approach to work? If labels are not used and node classification is done in an unsupervised fashion, how is it different from community detection?\n- What about using other GNN architectures besides GCN or other aggregation functions besides sum aggregation? Can we expect that the proposed rewiring approaches help in those settings or are they limited to GCN and sum aggregation? I would recommend trying other architectures such as GIN or SAGE, perhaps even a MLP to check whether the rewiring might make graph neural network superfluous.\n- Is there a reason why NMI was used to measure the agreement between community structures and not AMI, which has become the preferred measure in network science because it adjusts for chance?\n- If I understood correctly, rewiring with FeaSt is based on the assumption that there is a correlation between nodes' community memberships and their features. But what if this is not the case? In real-world networks, it could be that the \"wrong\" features have been recorded. Or more generally, how do you determine whether the nodes' features are informative? Is there perhaps a \"simple test\" that can tell the practitioner whether FeaST will work well for their data?\n- Related to the previous question, it seems that, given that there is a strong correlation between nodes' community memberships and their features, ComMa and FeaSt should not be that different. Is that correct?\n- Theorem 1 assumes an SBM with exactly two equally sized blocks. How does the theorem generalise to networks with more blocks that have different sizes? And how well does the proposed insight translate to real networks?\n- In Fig. 4, do the point labels denote the number of added edges?\n- I find that using the Louvain algorithm to detect communities might need some more motivation or at least a discussion of its limitations. For example, modularity maximisation suffers from the well-known resolution limit, which is often \"addressed\" by using a resolution parameter. How does this limitation affect ComMa and ComFy?\n- I think a table summarising the used datasets' statistics should be included in the paper. As of now, it is unclear how large the large networks are.\n\nMinor points\n- I think there is a typo in line 182: \"grain\"\n- The labels in Fig. 3b are somewhat messy and I would suggest cleaning them up a bit so that they don't overlap.\n- I have a hard time imagining what the approximate proportion of misclassified nodes (Theorem 3) looks like. It would have been nice to see a plot.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The motivation behind the work is clear and the authors demonstrate that their contribution improves the performance on one downstream task, namely node classification.\n- The authors' claims are supported with theorems, proofs and extensive empirical experiments.", "weaknesses": "- Many results are presented in the paper, however, I find that it is not always clear what the specific message of each figure and table is. For example, I find that Fig. 1 does not have a strong message, and Fig. 5 could have been summarised more succinctly in a short paragraph.\n- Only one downstream task is considered, namely node classification. Therefore, it remains unclear how the proposed approaches affect the performance in other tasks.\n- While the proposed approach seems to improve node classification performance in some settings, I am concerned that this is only due to the fact that the authors essentially consider community detection, supported by modifying the network such that the communities become clearer.\n- The authors' approach appears to rely on knowing the network's community structure, which is unknown in real-world networks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)