GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring

Q9. Dataset statistics:

We thank the reviewer for the suggestion to include dataset statistics, which we have added in Section C.1, Table 5.

M1. Typo:

We thank the reviewer for finding the typo grain. We have changed it to gain.

M2. Messy labels in Figure 3b:

We have adjusted the positions of labels so that none are overlapping.

M3. Visualization plots for Theorem 3 formula:

We have added a visualization to Section D.7, Figure 12.

We have included 6 plots which show in six 3D snapshots the 4D surface resulting from the proportion of misclassified nodes in Theorem 3. The plot shows $P(M)$ as a function of alignment, and different configurations of $(p,q)$:

• $P(M)$ against alignment and the theoretical spectral gap formula in the limit $-(p-q)/(p+q)$ from Theorem 1.

• $P(M)$ against $p$ and $q$ given fixed alignment $\psi\in$ {0.7, 1.0}. As the alignment increases, the minimum (purple) and maximum (yellow) possible performance extend their range.

• $P(M)$ against alignment and $p$ given fixed values of $q \in$ {0.2, 0.5, 0.7}. As the value of $q$ increases, the community structure is less pronounced. Therefore, the range of values of $p$ for which performance can achieve $100\%$ (in yellow) becomes narrower.

References:

[1] Chen et al. ICLR 2010, Supervised Community Detection with Line Graph Neural Networks.

[2] Shchur et al. Deep Learning on Graphs Workshop, KDD, 2019. Overlapping Community Detection with Graph Neural Networks.

[3] Hansen et al. ICML 2023. Total Variation Graph Neural Networks

[4] Yang et al. ICML 2024. How Graph Neural Networks Learn: Lessons from Training Dynamics

[5] Emmanuel Abbe. Journal of Machine Learning Research 2018. Community detection and stochastic block models: Recent developments

We thank the reviewer for the time and effort that they spent on their review. We are very grateful for their valuable feedback and revised our manuscript accordingly. Below, we provide a point by point response.

W1. Message of figures and tables:

We thank the reviewer for the feedback on the figures and tables. We have revised our manuscript accordingly. For instance, we have substituted Figure 1 by a figure that explains our proposed methods pictorially, which complements the textual descriptions in Sections 1 and 3. We believe that this improves clarity of our methods and of our algorithmic contributions. Figure 5 contains a lot of information that is critical for our main message. For that reason, we have to explain its findings in a longer paragraph.

W2. Other downstream tasks:

Our work focuses on node classification because our analysis accounts for label distributions across the nodes in the graph, and their alignment with the latent community structure. While our methods could in principle also be applied to graph classification, this is beyond our scope, as our theoretical insights provide intuition specifically for node classification. As this is a highly relevant learning setup comprising many different application domains, we believe, this focus is still of high interest to the ICLR community.

W3. Are we only making the community structure more clear?

One of our proposals, ComMa, focuses on rewiring based on community detection only. Yet, our additional proposals FeaSt and ComFy, which take feature similarity into account, outperform this proposal significantly. This shows that we are not only making the community structure more pronounced. Instead, incorporating feature similarity gives us valuable information about the task.

Moreover, the purpose of our theory is to explain why it is not always beneficial to make the community structure clearer. If the alignment between community labels and node labels is not high, it can be better for the performance to make the community structure less pronounced (see Theorem 3). A real world example is given by Cornell, for instance.

More generally, we consider a high variety of GNN benchmarks on which we run our algorithms. The effect of our algorithms on NMI, AMI, Modularity score, Adjusted Homophily and Edge Label Informativeness proposed in [1] before and after rewiring along with the test accuracy of GraphSAGE on Cora, Citeseer, Chameleon, and Squirrel datasets is presented in Tables 13 and 14, which shows that the effect of our feature similarity based rewiring decisions is nuanced. In general, our rewiring decisions that take feature similarity into account lead to performance gains more consistently. On purpose, rewiring usually changes too few edges to have a great impact on the graph topology and its overall community structure. This is why community structure improvement does not seem to be a dominant factor. The obtained performance gains seem to be better explained by improved feature aggregations.

[1] Platonov et. al NeurIPS 2023. Characterizing Graph Datasets for Node Classification: Homophily–Heterophily Dichotomy and Beyond

W4. Unknown real community structure:

For the experimental section (S4) we use a community detection algorithm (in this case Louvain) to estimate the latent community structure. The performance of our rewiring depends less on the quality of this algorithm but more on the alignment between the detected community structure with the node labels (see Theorem 3). For graphs without a clear community structure, this is not a problem. ComFy would still provide benefits, as it still follows the feature similarity maximization principle, yet, more locally in comparison with FeaSt.

Q1. Considered task: node classification:

We focus in this paper on node classification tasks in a semi-supervised setting. The concrete splits are stated in Appendix C. To boost the performance of GNNs on these tasks, we propose three different graph rewiring methods (as pre-processing strategies). Thus, a rewired graph is provided as input to a GNN learning algorithm, which learns to perform a node classification task.

It is not our objective to improve community detection. We only employ community detection (concretely the Lovain algorithm) to inform our graph rewiring (specifically ComMA and ComFy).

Q4. Uninformative/noisy features:

We agree that real-world graphs will exhibit a variety of behaviors such as noisy graph structure and features that might be noisy or less informative which will all have different effects on the generalization performance of GNNs. In practice, we would have to evaluate different models and rewiring strategies on a validation set to identify which works best in our setting.

In general, if node features are noisy or less informative, the performance of most GNNs should suffer. To analyze how our rewiring algorithms fare in the presence of feature noise, we present ablations for datasets Chameleon, and Squirrel, where we vary the amount of Gaussian noise added to the node features, and then train a GCN. As expected, the performance of the baseline GCN drops significantly. While our proposed algorithms FeaSt and ComFy are more robust to noise compared to the baseline. This is shown in plots added to section D.4 (Figure 7). In D.5 (Figure 8), we also plot the results for label noise. We randomly flip {0,3,5,10,20,50} percent of training labels and train GCN with both ComFy and FeaSt. From the figures, we can see that our proposed algorithms are robust to both feature and label noise, they consistently start at a higher test accuracy and decrease but still maintain a significant margin compared to the baseline.

Q5. Difference between ComMa and FeaSt:

ComMa and FeaSt are different even if community labels and features are highly correlated, because they rewire according to different principles. The difference also depends on the feature distribution, not only the node labels.

ComMa draws edges to rewire randomly but respects the community structure in doing so. In contrast, FeaSt ranks edges according to their contribution to feature similarity without respecting the community structure. Thus, its edge modifications could be very clustered. Thus, ComMa rewires in a more distributed way. ComFy shares the distributed rewiring with ComMa but still ranks edges locally according to feature similarity.

As a consequence, ComFy would be more similar to ComMa if features were distributed so that a feature similarity based ranking would result in similar rewiring decisions as a random ranking.

Q6. Extension of theory to more blocks or different sizes:

The concept of alignment between the task and the blocks still holds for more blocks and different sizes, and it is equally relevant for model performance. The fact that the spectral gap maximization destroys community strength still holds. We have extended Theorem 1’s proof to more blocks and blocks of different size in Section A.1.1. We can furthermore see how that translates to real-world datasets in Figure 4 and Section 2.4, where we run spectral based rewiring methods and calculate the accuracy versus the alignment (Fig. 4) and the number of same-class and same-community edges modified (Section 2.4).

Q7. Meaning of point labels in Figure 4:

The reviewer’s assumption is correct. We have added the information in the figure caption for better clarity. We thank the reviewer for pointing this out.

Q8. Choice of Louvain algorithm and relation to resolution limit:

Our rewiring proposals can be combined with any community detection algorithm of choice. We picked Louvain, as it scales to large graphs, is readily implemented in the Python package networkX, and can utilize GPUs. While the Louvain method sometimes produces badly connected communities, this caveat is not problematic in our setting, as we do not perform any rewiring in this case. We do not necessarily require community structure of high resolution, as we are more interested in larger communities, in which feature similarity comparisons of the edges lead to a meaningful ranking or edges for rewiring.

To still analyze the impact of the community detection resolution limit, we have added Figures 9-11 to the Appendix D.6, which analyzes the impact of our proposed rewiring algorithms in our theoretical setting. We discuss scenarios below and above the community detection threshold. As our theory suggests, we find that ComMa, which relies solely on community structure, fares well in situations of pronounced community structure and good alignment between community and node labels. However, its performance deteriorates when the community structure is weak or not well detectable. In these scenarios, our proposals that take feature similarity into account induce higher performance gains, as feature similarity also carries signals about node labels and thus which nodes should be connected. This nicely motivates our methods, as it explains why it can be beneficial to combine topological information and features in rewiring decisions. If either information is less reliable or noisy, the other datasource still carries relevant information that can guide the rewiring.

Q2. More diverse GNN architectures:

To clarify, we use a 2- layered GCN (which uses mean aggregation) as our backbone architecture for all our experiments. Our proposed rewiring methods are designed to help pre-process the input graph before feeding it into a GNN, thus our algorithms can be used in conjunction with any kind of GNN model and is not restricted to any specific GNN variant. To explore the impact of our methods on other GNN architectures, we have added Table 21 below and in Section D.3 of our manuscript. It reports results for FeaSt and ComFy on GIN (sum aggregation, 2-layered) and GraphSAGE (which uses max aggregation, 2-layered) for different datasets. Our proposals lead to significant performance gains in all cases, demonstrating the versatility of our methods.

Table 21

Q3. NMI vs. AMI:

We thank the reviewer for the suggestion to use the adjusted version of mutual information. We note that we solely use the NMI in order to compare how our algorithm changes the alignment (between class labels and community labels) within a specific dataset. 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, so it is a valuable addition to our paper and we have added a discussion in the Appendix C.1. In Tables 13 and 14 we report the NMI, AMI, Modularity score, Adjusted Homophily and Edge Label Informativeness proposed in [1] before and after rewiring using FeaSt and ComFy and the test accuracy of GraphSAGE on Cora, Citeseer, Chameleon, and Squirrel datasets. In general, AMI shows similar trends as the NMI.

[1] Platonov et. al NeurIPS 2023. Characterizing Graph Datasets for Node Classification: Homophily–Heterophily Dichotomy and Beyond

Could please acknowledge and respond to the rebuttal.

Q2. (cont.)

Table 14. Different community detection metrics before and after rewiring using ComFy.

Q2. (cont.)

Real world graphs: Below and in Tables 13 and 14, we present a comparison of various metrics such as NMI, AMI and modularity score, Adjusted Homophily and Edge Label Informativeness proposed in [1] before and after rewiring along with the test accuracy of GraphSAGE on Cora, Citeseer, Chameleon, and Squirrel datasets. Accordingly, feature similarity based rewiring decisions are not impacting the community structure significantly. On purpose, we do not rewire sufficiently many edges to change the graph topology so that the community structure is barely altered. Yet, the few edge alterations seem to improve the overall feature aggregation. This could also explain why our rewiring methods that take feature similarity into account achieve higher performance gains overall.

References:

[1] Emmanuel Abbe. Journal of Machine Learning Research 2018. Community detection and stochastic block models: Recent developments

[2] Platonov et. al NeurIPS 2023. Characterizing Graph Datasets for Node Classification: Homophily–Heterophily Dichotomy and Beyond

Table 13. Different community detection metrics before and after rewiring using FeaSt.

Q1. (cont.)

GCN Performance wrt edge budgets for FeaSt (Table 16)

GCN Performance wrt edge budgets for ComFy (Table 17)

Q2. Sensitivity to community strength:

To study the sensitivity of our algorithms to the community strength (which we measure by the modularity score), we have added a theoretical investigation, where we can control the ground truth community strength, and report the modularity of our real world datasets to study performance trends.

SBM: We have furthermore added Section D.6 (Figures 9-11) to the appendix, which analyzes the impact of our proposed rewiring algorithms in our theoretical setting. We discuss scenarios below and above the community detection threshold. As our theory suggests, we find that ComMa, which relies solely on community structure, fares well in situations of pronounced community structure and good alignment between community and node labels. However, its performance deteriorates when the community structure is weak or not well detectable. In these scenarios, our proposals that take feature similarity into account induce higher performance gains, as feature similarity also carries signals about node labels and thus which nodes should be connected. This nicely motivates our methods, as it explains why it can be beneficial to combine topological information and features in rewiring decisions. If either information is less reliable or noisy, the other data source still carries relevant information that can guide the rewiring.

We thank the reviewer for the time and effort that they spent on their review. We are very grateful for their valuable feedback and revised our manuscript accordingly. Below, we provide a point by point response.

W1. Theory for SBM:

We agree that our theory focuses on the SBM, which does not capture all complexities of real world data (which also varies across datasets). However, our theory fulfills its purpose. It introduces a theoretically tractable minimal setting that provides basic insights into the mechanisms of how graph rewiring can boost GNN performance. Our theoretical results thus motivate the algorithms, which we propose, that achieve superior performance on real world datasets, as our extensive experiments demonstrate.

W2. The impact of adding and deleting edges on model performance:

Our theory captures the impact of adding and deleting edges by increasing or decreasing $p$ and $q$, respectively. Theorem 3 states how model performance is influenced by these factors.

We have furthermore added Figures 9-11 to Appendix D.6, which analyzes the impact of our proposed rewiring algorithms in our theoretical setting. As our theory suggests, we find that ComMa, which relies solely on community structure, fares well in situations of pronounced community structure and good alignment between community and node labels. However, its performance deteriorates when the community structure is weak. In these scenarios, our proposals that take feature similarity into account, induce higher performance gains, as feature similarity also carries signals about node labels and thus which nodes should be connected.

Furthermore, our experiments distinguish the cases of adding and deleting edges. Thus, their impact on the performance in comparison with baselines can be evaluated in detail. Our methods generally lead to significant performance gains. As a general trend, we observe that ComFy edge deletions tend to perform particularly well on heterophilic graphs, while FeaSt deletions often win in homophilic settings. Yet, also edge additions are competitive. In Table 16 and 17 we present how the test accuracy varies with respect to different edge modifications for Cora, Citeseer, Chameleon and Squirrel datasets.

W3. Sensitivity to low community structure and noise:

Even in case of less pronounced community structure, our algorithms FeaSt and ComFy still improve the feature similarity, as shown in the experimental section (S4). The Squirrel, Actor, and Texas datasets have the overall lowest modularity among the considered real world benchmarks (see Table 5). Accordingly, FeaSt achieves the highest performance on Squirrel and Texas overall, ignoring the community structure. ComFy, which also takes community structure into consideration, performs slightly better on Actor. In particular situations of less informative community structure motivate our proposal to guide rewiring by feature similarity (and not only community structure).

Robustness to noise:

We have added ablations to Sections D.4 and D.5 that study the robustness of our method ComFy and FeaSt with respect to different degrees of feature and label noise. We plot the GCN test accuracy vs feature and label noise and compare with GCN+FeaSt and GCN+ComFy both additions and deletions on chameleon and squirrel datasets. Gaussian noise with different noise level {0,0.01,0.03,0.05,0.08,0.1,0.2} is added to the node features and for label noise we randomly flip {0,3,5,10,20,50} percent of training labels. We generally find that our method responds to noise similarly as the baseline. Yet, as it starts from a higher accuracy (at 0 noise) it also maintains a higher level of performance when we increase the noise.

Q1. Sensitivity to hyperparameters:

The GCN hyperparameters are tuned based on the validation set through a grid search. We have added corresponding tables in Section C.3 (Tables 15,16,17). As is common, we found that the performance of not only our 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 use the same ones as the baselines. Our rewiring methods come with an additional hyperparameter, i.e., the rewiring budget (and thus how many edges are added or deleted). Tables 15 and 16 in the manuscript (and the table below) 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 to be task specific but not very architecture specific, as we could use the same budgets for different GNN variants, such as GIN and GraphSAGE.

Q1. (cont.):

Results on Large Homophilic Graphs (Table 19)

Results on Node Sampling (Table 20)

Q2. Robustness of methods:

We have added ablations to Sections D.4 and D.5 that study the robustness of our method ComFy and FeaSt with respect to different degrees of feature and label noise. We plot the GCN test accuracy vs feature and label noise and compare with GCN+FeaSt and GCN+ComFy both additions and deletions on chameleon and squirrel datasets. Gaussian noise with different noise level {0,0.01,0.03,0.05,0.08,0.1,0.2} is added to the node features and for label noise we randomly flip {0,3,5,10,20,50} percent of training labels. We generally find that our method responds to noise similarly as the baseline. Yet, as it starts from a higher accuracy (at 0 noise) it also maintains a higher level of performance when we increase the noise.

Q3. Sensitivity to hyperparameters:

The GCN hyperparameters are tuned based on the validation set through a grid search. We have added corresponding tables in Section C.3 (Tables 15,16,17). As is common, we found that the performance of not only our 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 use the same ones as the baselines. Our rewiring methods come with an additional hyperparameter, i.e., the rewiring budget (and thus how many edges are added or deleted). Tables 14 and 15 in the manuscript (and the table below) 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 to be task specific but not very architecture specific, as we could use the same budgets for different GNN variants, such as GIN and GraphSAGE.

W3. (cont.):

Table 21: Our methods are applied to a more diverse set of architectures (GIN, GraphSAGE) which also correspond to other kinds of aggregation (sum and max). This demonstrates that our rewiring schemes are architecture agnostic and can be applied to diverse setups.

Additional baselines with GIN, GraphSAGE and MLP (Table 21).

References :

[1] Bi et al. ACM, WSDM 2023., MM-GNN: Mix-Moment Graph Neural Network towards Modeling Neighborhood Feature Distribution.

[2] A. Arnaiz-Rodriguez et al.,Proceedings of the First Learning on Graphs Conference (LoG 2022), PMLR 198, Virtual Event, December 9–12, 2022 DiffWire: Inductive Graph Rewiring via the Lovász Bound.

[3] Dong et al. ICML 2023., Towards Understanding and Reducing Graph Structural Noise for GNNs.

Q1. Scaling with graph size:

Our run time analysis states how our algorithms scale with the number of nodes and edges of a graph. We have included the statistics of their number of nodes and edges in a new Table 5 (Section C.1). All these state that running our algorithms is usually feasible on large scale graphs. But do our methods also lead to performance gains on large graphs? To answer these questions, we have added Section D.2, where we present results on 3 large homophilic datasets (Table 19) - CS, Physics and Photo [4]. We report results for FeaSt and ComFy along with the edges modified and the time taken to rewire the graph.

As a general remark, if required, we could further speed up our algorithms by sampling a subgraph and focus our rewiring on this subgraph. The algorithms would still perform relatively well, as there still are edges to be modified that can improve performance. Below and in Table 20 we present the results for a specific large homophilic graph, Physics, which has 34,493 nodes and 495,924 edges. We choose the same best-performing budget hyperparameter from Table 13 and present results for 20% sampling ratio.

References:

[4] Shchur et al. Relational Representation Learning Workshop (R2L 2018), NeurIPS 2018 Pitfalls of Graph Neural Network Evaluation.

W3. (cont.):

Diverse methods (Table 18)

We thank the reviewer for the time and effort that they spent on their review. We are very grateful for their valuable feedback and revised our manuscript accordingly. Below, we provide a point by point response.

W1. Explanation of ComFy:

In the textual explanation for ComFy in Section 3, we were missing a link to its pseudocode “(Alg. 6)” presented in Appendix B. We thank the reviewer for pointing it out, we have now added the reference.

Moreover, we have decided to include a new Figure 1 that explains all the methods pictorially, which complements the textual descriptions in Sections 1 and 3. We agree with Reviewer tdhE that the old Figure 1 was less informative. We believe that this improves clarity of our proposed methods and our contributions.

W2. Simplicity of planted partition model:

For clarity, we have focused our theory on the simplest case of two communities, as it is sufficient to provide us with all relevant insights and intuition. Nevertheless, the theory is generalizable to more communities and we have added a corresponding extension of Theorem 1 to Appendix A.1.1, after its original proof.

Moreover, we have shown that the same principles and intuition transfer to real world datasets in our experiments, as our proposed methods lead to significant performance gains.

W3. Diversity of competition:

Our work focuses on graph rewiring as a pre-processing step to boost GNN performance. This has the advantage that it is computationally relatively efficient. Accordingly, we have compared our proposals with state-of-the-art methods that were designed for the same purpose. In total, these define 7 baselines. Other methods to boost GNN performance are not necessarily competing but could also be seen as complementary, as they can be combined with our rewiring approach.

Yet, to compare the effect of different algorithmic strategies, we have added the following comparisons to the manuscript: Table 18 in Section D.1 and Table 21 in Section D.3, where we also added additional GNN variants such as GIN and GraphSAGE and comparison with [1,2,3], which are not strictly rewiring for pre-processing but also alter the graph structure.

[1] suggests multi-order moments to model a neighbor’s feature distribution and propose MM-GNN to use a multi-order moment embedding and an attention mechanism to weight importance of certain nodes going beyond single statistic aggregation mechanisms such as mean, max and sum. Note that the underlying GNN architecture is generally more powerful than a GCN.

[2] proposes DiffWire, an inductive way to rewire the graph based on the Lovasz bound, which they use as inspiration to define novel GNN layers.

[3] introduce a way to de-noise the graph based on a graph propensity score (GPS) and GPS-PE (with positional encoding). Although the authors call their method ``graph rewiring", it actually involves separating edges in the graph as training edges and message-passing edges and propose a self-supervised link prediction task to impute edges between nodes. We report the results of the respective papers, and hence have NA for some datasets. Code has not been shared for most methods.

We find our proposals to be competitive on 6 out of 9 tested datasets.

W4. Details on algorithms:

More details on the algorithms are presented on Page 8. To clarify the exposition of our algorithms in the paper, we have included a new Fig. 1 (in exchange of the previous Fig. 1, which we and Reviewer tdhE deemed not very illustrative). The new Fig. 1 explains our proposed methods pictorially in a table. We believe that this improves the clarity of our algorithmic contributions. In case that issues with clarity remain, we would be happy to address them. We assure the reviewer that our theoretical results are reliable. All proofs are provided in the appendix.

We thank the reviewer for the time and effort that they spent on their review. We are very grateful for their valuable feedback and revised our manuscript accordingly. Below, we provide a point by point response.

W1. Novelty and role of Theorem 1:

Theorem 1 is not our main contribution but necessary to derive the rest of the paper’s arguments. It states how the spectral gap is linked to the graph’s community strength. It implies, for instance, that instead of rewiring to optimize the spectral gap, it would be a valid and computationally more efficient approach to rewire according to the community structure. Furthermore, if spectral gap maximization is applied iteratively without taking the initial community structure into account (as proposed in the literature), the community structure might get destroyed in the process. And this, as shown in the following theorems, may have adverse consequences for model performance.

W2. How the spectral gap depends on $p$ and $q$:

Our statements are correct, but we acknowledge that the factor (q-p)/(q+p) is difficult to interpret intuitively, because it is negative. To highlight this fact, we have instead written it as -(p-q)/(q+p) in our revised draft. It does imply that a larger spectral gap corresponds to less pronounced community structure. Figure 3a also confirms this statement empirically. Note the perfect anti-correlation between community structure and the spectral gap.

But let us verify this also in your given example.

If one calculates the spectral gap of the normalized Laplacian (using nx.normalized_laplacian_matrix, np.linalg.eigh) and the community strength (using nx.algorithms.community.modularity_max.greedy_modularity_communities and nx.algorithms.community.modularity), on each graph setting (generated by nx.stochastic_block_model with 1000 nodes) we obtain (averaged over 10 seeds):

• p=0.3, q=0.0001, spectral gap: 0.001, -(p-q)/(p+q): -0.999, modularity (community strength): 0.500

• p=0.9, q=0.1, spectral gap: 0.199, -(p-q)/(p+q): -0.800, modularity (community strength):: 0.400

The spectral gap and -(p-q)/(p+q) are larger for p=0.9, q=0.1, but the community strength is lower. Therefore, our theorem is in line with this case.

W3. Assumptions of Thm. 2:

We thank the reviewer for pointing this out. We have added an extra sentence to Theorem 2. Theorem 2 is supposed to have the same assumptions as Theorem 3 (except for how the labels are distributed with respect to the blocks).

W4. Relation between theoretical insights and algorithms:

Our theory and proposed algorithms study the interplay of community structure and node features in guiding graph rewiring as a pre-processing technique to improve GNN performance.

We propose ComMa as a fast and parallel alternative to spectral gap rewiring methods, as our theory implies a connection between increasing (/decreasing) the spectral gap and reducing (/strengthening) the community structure. ComMa rewired based on the community structure of the original graph (and does not require repeated computations of the spectral gap or the community structure) and is therefore computationally more efficient than Greedy spectral maximization (/minimization).

However, our theory also points out limitations of graph rewiring techniques that solely rely on the graph topology (like the community structure) and do not take features or node labels into account. They can only succeed if the community structure and node labels are statistically dependent and thus the alignment between community and node labels is high. The additional Figure 9 in Appendix D.6 corroborates this point, as it analyzes how ComMa struggles if the alignment is insufficient or the community structure is statistically difficult to detect.

Node features provide additional information that is available even before training a model. In our theoretical SBM setting (and usually also in practice), their similarity also carries information about node labels. Features can provide valuable signals, especially, when the community structure is less reliable. Our other two rewiring methods (FeaSt and ComFy) therefore take those features into account. This is why they fare better in situations when community structure is less reliable (see Figure 10).

While FeaSt relies solely on features, our theory (and the rewiring literature) suggest that there can be value in accounting for community structure. For that reason, ComFy combines community structure and feature similarity information in a joint rewiring criterion. Respecting the latent community structure, which we discover with Louvain (but any other community detection algorithm could be used instead), we maximize feature similarity locally to still perform task-specific rewiring. Thus, ComFy brings all our arguments together. ComMa and FeaSt can also be interpreted as ablations that study the impact of community structure and feature similarity as isolated rewiring criteria.

Could please acknowledge and respond to the rebuttal.