Locality-Aware Graph Rewiring in GNNs

We warmly thank the reviewer for pointing out that our work is clear, well written, and that it is a good contribution to the literature. We would like to address the valid points brought up by the reviewer.

Further motivating sparsity.

In LASER, the rewiring is guided through a connectivity measure that is used to prioritize the edges which would improve the connectivity the most. Consequently, LASER, given a $\rho$ factor, is “discarding” the edges that would affect the connectivity the least, according to the chosen connectivity measure.

Adding an effective resistance rewiring.

We agree with the reviewer that a baseline such as GTR (Black et al, 2023) would fit well in our comparison. We have added the baseline to our experiments, alongside the inclusion of another recent curvature rewiring technique BOFR (Nguyen et al., 2023), as requested by another reviewer. The two are the most recent state-of-the-art rewiring techniques. In Tables 2 and 3, we demonstrate that LASER shows strong performance over these two new baselines as well.

Number of walks in connectivity measure.

We thank the reviewer for the interesting question. We would like to clarify that the node degrees in the bound derived in Proposition 5.1 come from the convolutional part of the GNN model. It is standard practice to normalize such a convolution operation for training stability reasons. Instead, in our connectivity measure $\mu$ we calculate the number of walks from node $u$ to $v$ of length $k$, which requires taking powers of an unormalized adjacency matrix. The two operations are therefore unrelated to each-other.

Instantaneous rewiring.

In previous works such as FOSR and GTR, the authors have shown experimentally that relational types tend to significantly improve the performance of rewiring techniques. As such, we have not included such an ablation study. This can also be motivated from the fact that relational models are always able to recover “instantaneous” models by setting the weight matrices to be equal to each-other. For this reason, they may be considered as strictly more powerful instances than instantaneous models.

Efficient computation of the connectivity and locality measures.

It is indeed true that the sequential snapshots change the topology of the graph which would affect the number of walks. Computing the connectivity measure once, as you have pointed out, gives an important computational speed-up which we wanted to keep for scalability reasons. During the development of the model, we found that such a choice did not have a noticeable impact on the performance

We once again thank the reviewer for supporting our work and for the excellent questions. We are of course happy to keep engaging throughout the rebuttal period.

We sincerely thank the reviewer for the excellent and thorough review. We would like to address the points in full.

Regarding Proposition 5.2.

We thank the reviewer for the feedback on the Proposition. We have followed the suggestion and replaced the informal statement with the precise one from the Appendix. To make things more concrete, we have formulated the result for the case of a graph (pointing out that the size can be taken to be positive to avoid vacuous edge cases) and rewritten the proof in the Appendix (Section A) more explicitly. The discussion surrounding Proposition 5.2 has also been modified in order to improve clarity. Thanks again for the feedback.

Further baselines.

We thank the reviewer for the suggestions. We agree that the paper would benefit from further comparisons. Accordingly, we have added a comparison to GTR (Black et al. 2023) and BORF (Nguyen et al. 2023) in our work. We believe these to be the most direct and relevant recent comparisons to our framework, as these works aim to modify the computational graph as a pre-processing.

Conservation of parameters and tuning.

We thank the reviewer for the valid experimental doubts, we would like to address these in full. All experiments in our work strictly follow the 500k parameter budget limit for LRGB. As for the TUDatasets, we keep the hidden dimension fixed to 64. Furthermore, in the TUDatasets we do not tune on more than 3 snapshots (details in the Appendix). As such the model parameter count remains extremely similar, especially when compared to the relational FOSR, GTR, BOFR, and SDRF models. Therefore, we are certain that the slight increase in parameters does not affect our experimental evaluation.

We agree with the reviewer that fixing the iterations in SDRF and FOSR to 40 may have favoured LASER in our previous evaluation. Therefore, we have included results achieved with a more thorough sweep of the hyper-parameters for SDRF and FOSR, alongside the additional GTR and BOFR benchmarks. We have added detailed information in the Appendix (Section B) on the parameters searched.

New experiment proposed.

We thank the reviewer for the suggestion. Having a sequence of rewirings is a contribution of our work and it is not immediately clear how easily this translates to other rewiring techniques. We agree, however, that this is an interesting experiment and show in the Appendix (Section C.4) that additional snapshots even slightly decrease the performance with FOSR, while tend to improve the performance with LASER.

Minor concern on the literature summary.

This is an accurate description of the literature landscape thus far. We fully agree with your point of view, even though we may have summarized some of the references in the interest of space. If you believe there are certain points where it is worth making such clarification explicit, we would be happy to add it.

Minor concern on the locality measure.

Thank you for this observation. We agree that we could make our point of view more explicit. Rather than “information”, preserving locality in our work mainly refers to preserving the inductive bias afforded by the input graph topology, according to which features that are associated with nearby nodes should interact “more easily” or “more often” than those associated with distant nodes. Naturally, we are tacitly assuming here that the graph-structure we are given in the first place is somewhat aligned with the downstream task in order for this claim to be valid. This is why “some metric”, mentioned above, should capture a notion of distance on the graph that we believe to be, in most cases, aligned with the task. We have rephrased a few points (see e.g. the paragraph `Instantaneous vs Sequential Rewiring’ or the discussion above the new statement of Proposition 5.2) of the submission to emphasize that “locality” is a “bias” we aim to preserve in most tasks we believe GNNs to be useful for.

We again thank the reviewer for the great questions. We hope that with our rebuttal and the improvements we have made to the paper, we have addressed the concerns found regarding the proposition and the experiments, and that this may convince the reviewer to increase the score. We are of course very happy to keep engaging during the rebuttal period.

We are happy to hear that the reviewer found our work to be well-motivated and our ideas novel. Below we answer the questions posed by the reviewer, which we believe have helped to strengthen our work.

Why must we respect locality?

We thank the reviewer for the important question. Preserving locality is a natural inductive bias to have whenever we assume that the graph-structure associated with the data is aligned with the downstream task. For instance, molecular systems observe long-range interactions that decay with the distance, in the form of Coulomb electrostatic forces. This behaviour also naturally appears in social networks, transaction networks, or more generally in physical systems, in which interactions that are nearby are more likely to be important for a given task. Accordingly, given a budget of edges to be added, it is sensible to prioritise adding connections between nodes that are closer.

To make this intuition more concrete, in Proposition 5.2 we have argued that methods that do not preserve the locality bias, may alter the distance matrix associated with the graph quite more significantly. We have added a detailed section in the Appendix (Section C.4) alongside a pointer within the main section to tackle this point more extensively within the paper as we agree that this is an important aspect of our work. In this new section, we touch upon concrete examples, and provide a further ablation that supports this view.

Other rewirings (DRew and SP-MPNN).

We would like to point out that SP-MPNN can be seen as a special case of LASER where we take $\rho=1$ and force the weight matrices associated with each hop to simply be a convex combination of learnable coefficients. The advantage of our approach, which extends SP-MPNN, is that it provides a tradeoff between performance and efficiency since we can more easily control the sparsity of the computational graph through the factor $\rho$. Concerning the framework of DRew, we highlight that the main purpose of that work is showing that introducing delay can be particularly beneficial when exploring deep models. Because of that, their evaluation on LRGB does not stick to the convention of 5-layers architecture – which instead we have adopted here. Considering that the main goal of this project is showing how to condition spatial-rewiring on more global (spectral) properties, we believe that focusing on spectral and curvature-based rewiring baselines is fair. To strengthen our comparison to existing state-of-the-art baselines that follow our exact paradigm, we have added an additional spectral baseline (GTR, Black et al. 2023) and an additional curvature baseline (BORF, Nguyen et al. 2023) to our experiments, as suggested by some of the other reviewers.

Edge prediction.

We agree that edge prediction is a less natural task for rewiring techniques but included it regardless as an interesting experiment to cover the different types of tasks GNNs are used for (graph-level, node-level, and edge-level predictions).

Scalability of LASER.

While matrix multiplication has cubic run-time, it is a highly parallel operation that scales extremely well on modern hardware. It is numerically more stable than matrix inversion (used for effective resistance based rewirings such as GTR, which is also cubic), and significantly cheaper than curvature computation (used by SDRF and BORF). We show in the Appendix (Section D) that we are able to scale easily to graphs of 100k nodes and ~1 million edges, unlike SDRF and FOSR. We point out that the other rewiring operations rely on optimization libraries such as Numba and Multiprocessing, while we avoid such an approach as we found LASER to be extremely efficient and scalable regardless. We also finally emphasize that such an operation is done only once as a pre-processing step.

What does 2|E|R(v, u) stand for?

Thanks for this question, we will clarify the notation in the text. |E| is the number of edges and R(v, u) is the effective resistance between nodes v and u. The equation CT(v, u) = 2|E|R(v, u) is a well known result and relates the commute time between v and u CT(v, u) to the effective resistance between v and u R(v, u).

Once again we thank the reviewer for the excellent questions and hope that our reply persuades the reviewer to increase the score. We are of course happy to keep engaging with the reviewer throughout the process.

We thank the reviewer for the excellent comments and questions, below we would like to address them in full.

Other baselines.

We thank the reviewer for pointing out further baselines. We agree that the work would be strengthened via the addition of more baselines. Accordingly, we have added to our experiments a comparison to GTR (Black et al, 2023), and BORF (Nguyen et al, 2023). We believe that these techniques are the most comparable to ours as they are designed to augment the graph through pre-processing. Transformer based methods are not directly comparable to our technique as they require significantly more computation. In fact, even the most recent state-of-the-art rewiring techniques GTR and BORF do not compare with Transformers-based architectures in their evaluation and compare against the same benchmarks present in our own work.

Poor results.

We politely disagree with the statement and believe the results to be validating our point. We kindly ask for further clarification as to why you believe the results to be poor. In fact, when it comes to comparing with similar methods that also aim at adding edges more “surgically”, the LASER framework consistently outperforms or is on par with the other baselines in the worst-case scenario. Even with the new added baselines, this claim still holds. More concretely, in Table 2 LASER beats all baselines consistently. In Table 3, LASER achieves a mean rank of 1.67, with the second best model achieving a mean rank of 3.20.

Spectral methods are not local.

We thank the reviewer for the interesting question. We would like to clarify that in our work spectral rewirings refer to methods that aim to rewire the graph based on spectral quantities, which is not a local mechanism. This is because rewiring through quantities such as increasing spectral gap or decreasing commute time accounts for the global topology of the graph, meaning that the edges to be added end up minimizing spectral (not spatial) quantities and hence may, quite often, violate any spatial constraint. Put differently, the edges added through such methods will tend to be very non-local. This is something that has also been pointed out in Di Giovanni et al., ICML 2023. Architectures such as DiffWire aim to address this problem by adding additional components to the model. We emphasize that, instead, in our work, as in FOSR, SDRF, GTR, and BORF, the goal is to directly modify the computational graph of any existing MPNN, instead of proposing a completely different architecture.

Is there any study through parameter k?

If this question is referring to parameter $k$ in Equation 8, then this parameter simply indicates that we want to consider walks of length $k$ on our graph as our connectivity measure. In general, we want $k > L$ and we also set $k$ to be a power of 2 as this leads to more efficient matrix multiplication algorithms due to efficient factorization of the multiplication. As such, we fix $k=8$ in our work as a tradeoff between $k=4$ which would be too close to $L$ and $k=16$ which would be unnecessarily large. We found the network to be rather insensitive to this choice as long as $k$ was large enough.

Can there be an attention mechanism between the snapshots.

We thank the reviewer for the suggestion. We agree that this is something that could definitely be a future direction of our snapshot framework. It is indeed natural to explore how to best aggregate different snapshots together. In our work, we take an approach inspired by Temporal GNNs, but other approaches such as attention mechanisms, could be explored in future work.

We thank once again the reviewer for the comments and hope that we have clarified doubts in the new version of the paper, with a significantly stronger experimental section. We hope that this is able to convince the reviewer to increase the score. We are of course happy to keep engaging with the reviewer.

We would like to thank you again for engaging with our work and for providing valuable feedback.

Following your suggestions, we have added to Table 3 DiffWire as a baseline. Furthermore, we ran a full grid search for LASER over the number of snapshots $\\{ 2, 3 \\}$ and $\rho$ in $\\{0.1, 0.25, 0.5\\}$. We highlight that previously we had only used a random subset of $3$ configurations. We emphasize that this is a grid search of size $6$, which is now the same grid search size used for FOSR, SDRF, GTR, and BORF. For fairness and to avoid snooping, we ran this grid search on all the TUDataset tasks for LASER, explaining why most columns changed for LASER. We provide additional hyper-parameter details in the Appendix (Section B). We report the improved results in the newly uploaded PDF.

We sincerely hope that with these additional results, we have addressed your remaining concerns and that this may convince you to raise your score. We would like to once again thank you for your efforts in reviewing our work. We are happy to answer any further questions.