DeltaGNN: Graph Neural Network with Information Flow Control

We sincerely thank the reviewer for their thoughtful and detailed feedback, which includes many important points that we are pleased to address. Below, we provide detailed responses to your comments. *Message and Presentation* Over-smoothing and over-squashing are indeed distinct concepts. Both relate to long-range interactions, and both phenomena prevent deep GNNs from effectively capturing LRIs, thereby increasing the difficulty of achieving better node classification accuracy in domains where distant node relationships matter. While over-smoothing causes feature indistinguishability after numerous consecutive aggregations, over-squashing occurs when substantial information collapses into a fixed-size feature vector due to graph bottlenecks. In our work, we highlight the different natures of these two phenomena: over-squashing is topological, whereas over-smoothing happens in deep GNNs, and the speed at which over-smoothing occurs is related to heterophily. Recent works have shown promising results in addressing over-smoothing and heterophily simultaneously by introducing novel node-level metrics [1]. Similarly, we analyze the relationship between these two phenomena to propose a measure that can be leveraged to tackle both. Since graph heterophily results in faster feature over-smoothing as the number of layers increases (this occurs because representations are drawn toward the mean feature vector of dissimilar classes, reducing feature separability and further exacerbating over-smoothing at deeper layers), we propose a novel approach to increase the homophily of a graph through edge-filtering (see Appendices D and G). This slows down feature indistinguishability and indirectly alleviates the effects of over-smoothing. We have updated the manuscript to clarify the relationship between over-smoothing and heterophily, including appropriate references. In the previous version of the manuscript, we incorrectly suggested a causal relationship between over-smoothing and heterophily; we thank the reviewer for pointing this out. There are many ways to measure over-smoothing within a graph. While the Dirichlet energy was initially proposed as a viable measure of over-smoothing, numerous approaches now exist [2]. In our work, we aimed to define over-smoothing in the context of node classification tasks while highlighting its consequences on the feature distinguishability of different labels. As this is not the standard formalization of over-smoothing, the definition in the paper has been rectified. We have included additional citations in the “Related Work” section regarding rewiring algorithms and graph transformers. Our work is strongly inspired by graph-rewiring algorithms, as we aim to propose a more adaptive and integrated solution that leverages topological edge-rewiring while also using layer outputs to learn how to improve model performance. In the manuscript, we highlight the differences between our approach and recent edge-filtering methods. The crucial idea behind our work is to consider embeddings (and their momentum) to understand the graph structure and homophily. In this sense, our approach is not embedding-agnostic, which strongly differs from most popular approaches in the literature [3,4,5]. Consequently, our approach is the first to propose a truly scalable (with linear time complexity concerning the number of nodes) measure that simultaneously addresses over-smoothing and over-squashing. *References:* [1] Yan, Y., Hashemi, M., Swersky, K., Yang, Y. and Koutra, D., 2022, November. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In 2022 IEEE International Conference on Data Mining (ICDM) (pp. 1287-1292). IEEE. [2] Rusch, T.K., Bronstein, M.M. and Mishra, S., 2023. A survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303.10993. [3] Karhadkar, K., Banerjee, P.K. and Montúfar, G., 2022. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. arXiv preprint arXiv:2210.11790. [4] Nguyen, K., Hieu, N.M., Nguyen, V.D., Ho, N., Osher, S. and Nguyen, T.M., 2023, July. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature. In International Conference on Machine Learning (pp. 25956-25979). PMLR. [5] Fesser, L. and Weber, M., 2024, April. Mitigating over-smoothing and over-squashing using augmentations of Forman-Ricci curvature. In Learning on Graphs Conference (pp. 19-1). PMLR.

*Theory* Lemmas 1 and 2 are important theoretical results that together motivate the definition of our novel Information Flow Score (IFS). Additional details are provided in Appendix D. Lemma 1 highlights the relationship between $\overline{\Delta_u}$ and graph homophily, demonstrating that high values of $\overline{\Delta_u}$ are associated with low node homophily (an expanded version of the proof is available in Appendix B). To offer the reviewer a more intuitive perspective that motivates these findings, we observe that when a node experiences high values of $\overline{\Delta_u}$, this phenomenon can be linked to the ratio of neighboring nodes with dissimilar features. Under certain assumptions about the distance between the subspaces of the feature space associated with different node classes (assumptions on feature separability), this observation implies that the homophilic ratio of a node must be below a specific threshold. This theoretical result is further supported by our numerical experiment in Appendix G, where we directly compare several topological measures (including our novel Information Flow Score) and analyze changes in the graph's homophilic ratio during edge-filtering in the CORA dataset. The IFS achieves the highest increase in the homophilic ratio, with the results summarized below: | **Methods** | **Original Graph** | **Homophilic Filtered Graph** | **Δ Homophilic Rate** | |----------------------------|--------------------|-------------------------------|------------------------| | Degree Centrality | 0.6676 | 0.7115 | +6.72% | | Eigenvector Centrality | 0.6676 | 0.6937 | +4.05% | | Betweenness Centrality | 0.6676 | 0.7057 | +5.85% | | Closeness Centrality | 0.6676 | 0.7043 | +5.64% | | Forman-Ricci Curvature | 0.6676 | 0.7094 | +6.40% | | Ollivier-Ricci Curvature | 0.6676 | 0.7112 | +6.67% | | Information Flow Score | 0.6676 | 0.7244 | **+8.65%** | On the other hand, Lemma 2 investigates the relationship between $\mathbb{V}_t[\Delta^2_u]$ and graph connectivity, demonstrating that high values of $\mathbb{V}_t[\Delta^2_u]$ are associated with graph bottlenecks. Specifically, high $\mathbb{V}_t[\Delta^2_u]$ values correspond to areas of the graph that quickly converge to fixed feature values, indicating that the node $u$ is highly connected within the graph. As a result, graph bottlenecks coincide with very low values of $\mathbb{V}_t[\Delta^2_u]$. We informally prove Lemma 2 by building on the results of Nguyen et al., reducing the need for abstruse and unnecessary mathematical notations to improve clarity (an expanded version of the proof is included in Appendix C). We hope these intuitions help clarify the roles of Lemmas 1 and 2 in our work. We also suggest that the reviewer refer to Appendix D.2, where we include a numerical experiment that provides additional graphical intuition.

*Experiments* We appreciate the reviewer’s suggestion to consider more challenging heterophilic datasets. Unfortunately, due to time constraints, we are unable to include such experiments at this time. However, we would like to emphasize that we have already demonstrated that our DeltaGNN consistently delivers better performance on graph datasets with varying sizes, topologies, and levels of homophily. Specifically, we showed a reproducible and consistent reduction of the average epoch time by over 30% when using DeltaGNN, proving its scalability across datasets of varying sizes and edge densities. In particular, we benchmarked our model on 10 datasets containing up to 23,660 nodes and 2,809,204 edges. Please refer to Appendix D.2 for additional experiments on size-varying and density-varying graphs. While we agree that some of the benchmarked datasets have been contested in the literature due to their limited graph sizes, we also note that they remain the most widely benchmarked datasets for research related to graph rewiring and long-range interactions. This makes them a fair platform for evaluating our novel methodology. For instance, the works [3,6] you referenced were primarily benchmarked on the “TuDatasets” suite. We have also previously benchmarked our models on datasets such as MUTAG, ENZYMES, COLLAB, REDDIT-BINARY, IMDB-BINARY, and PROTEINS. However, we chose not to include these results due to the high variance in performance and questionable reliability of these datasets. This issue has also been noted by [6] in a recent study, where they state: “First, many of the datasets contain few graphs. For instance, MUTAG contains 188 graphs, meaning that only 18 graphs are part of the test set. Further, REDDIT-BINARY, IMDB-BINARY, and COLLAB do not have node features and are augmented with constant feature vectors. Consequently, it is not immediately clear how much long-range interactions play a role in these tasks, or, in fact, how to even define over-squashing on graphs without (meaningful) features.” For these reasons, we would appreciate clarification regarding which datasets you consider “relevant benchmarks.” This feedback will help us consolidate and expand the variety and reliability of our experimental evaluations in future research. However, for fairness, we believe this request should not detract from acknowledging that our work adhered to the same experimental protocols as most studies in this research area. *Questions:* 1.We updated the equation by extending the definition of the neighborhood to include the node u itself (similarly to related works [4]). 2.Already addressed in previous points. 3.Throughout the paper, we use the term "heterophilic GNN" to refer to a GNN architecture that implements an aggregation paradigm designed to handle heterophilic neighborhoods. In contrast, the term "homophilic GNN" refers to a GNN architecture that implements a standard aggregation paradigm (e.g., mean, sum) optimized for homophilic neighborhoods. This distinction between homophilic and heterophilic aggregation is crucial to avoid the misconception that DeltaGNN employs the same aggregation paradigm for processing both homophilic and heterophilic graphs (see Figure 3). 4/5. “Heterophilic Graph Condensation” is a term we coined to describe the specific step in the DeltaGNN pipeline where we construct a condensed graph that primarily includes heterophilic edges, thereby reintroducing long-range node dependencies. This step is crucial because, as you observed, removing graph bottlenecks may lead to disconnected components and the loss of long-range node dependencies. Additional technical details can be found in lines 362–..., and an illustrative graphic of this process is provided in Figure 3. Finally, we included a numerical experiment in Appendix G where we measure the graph's homophily after edge-filtering and after heterophilic graph condensation. We sincerely thank the reviewer once again for the excellent questions and hope that we have addressed any doubts in the new version of the paper. We would like to emphasize that responding to these points was both challenging—given that they touch on core aspects of our work—and beneficial, as they helped us better articulate our contributions. For these reasons, we are truly grateful for the reviewer’s interest in our work. We look forward to further engagement and hope this encourages an improved score. *References:* [3] Karhadkar, K., Banerjee, P.K. and Montúfar, G., 2022. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. arXiv preprint arXiv:2210.11790. [4] Nguyen, K., Hieu, N.M., Nguyen, V.D., Ho, N., Osher, S. and Nguyen, T.M., 2023, July. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature. In International Conference on Machine Learning. PMLR. [6]: Adrián Arnaiz-Rodríguez, Ahmed Begga, Francisco Escolano, and Nuria Oliver. DiffWire: Inductive Graph Rewiring via the Lovász Bound, LOG 2022.

We appreciate that the reviewer found our work interesting and our ideas novel. Below, we address the questions and concerns raised, which we believe have strengthened our work. *(Weakness 1): “The role of long-range interactions”* We thank the reviewer for the compelling questions as they present important and interesting points to further discuss. **While it is true that some graph transformers perform poorly on node classification tasks involving large heterophilic graphs, this does not imply that LR interactions in such tasks are of marginal importance**. In fact, as it has been observed in [1]: *“... when applied to graphs with 10K or more nodes, the self-attention of graph transformers is subjected to much more noise, which makes learning meaningful long-range interactions difficult”*. In general, when processing large or heterophilic graphs, understanding global patterns and long-range dependencies is harder due to the higher amount of noise. Moreover, recent works on node classification tasks outline that positional/structural information (for example Laplacian Positional Encoding) may be enough to get SOTA performance [1]. Including positional/structural information in the node feature vectors is a way of encoding global and relative structural context to nodes in Graph Neural Networks, which is another way of tackling the long-range dependencies problem. Indeed, long-range interactions are useful to improve node classification accuracies but in some domains models may struggle to properly capture them. *(Weakness 2): “Over-smoothing and heterophily”* We appreciate the reviewer’sobservation and we would like to clarify the statement made in the manuscript. We concur that there is no causal relationship between over-smoothing and heterophily as these two problems are classically defined as independent phenomena. However, recent works have shown promising results trying to tackle over-smoothing and heterophily simultaneously by introducing novel node-level metrics [2]. Similarly, here, we are analysing the relationship between these two phenomena to propose a measure which can be leveraged to tackle **both**. Since **graph heterophily results in a faster features over-smoothing as the number of layers increases** (this happens because representations are drawn toward the mean feature vector of dissimilar classes, reducing feature separability and further exacerbating the over-smoothing problem at deeper layers), we propose a novel approach which increases the homophily of a graph through a edge-filtering (see Appendix D and G) slowing down feature indistinguishability and indirectly alleviating the effects of over-smoothing. We updated the manuscript relaxing the contested statement. Indeed, we are happy to further discuss this point if the reviewer finds it appropriate. *Questions:* *“First and Second Delta Embeddings”* We are glad to hear that the reviewer found our contribution original. The First and Second delta embeddings are indeed key innovative concepts in our work. The First delta embeddings $\Delta^t_u$ is a sequence which measures the aggregation velocity at every layer of the GNN. The concept of aggregation velocity is the physical interpretation of the rate of change of the node embeddings throughout the aggregation within a GNN layer. **The higher this number, the faster a node embedding moves within the feature space at a certain time t**. The Second delta embeddings $(\Delta^2)^t_u$ is defined as the differences of $\Delta^t_u$ over time. This object measures the aggregation acceleration of the feature vectors over time. **The higher this number, the faster a node embedding converges within the feature space at a certain time t**. To give a graphical intuition we included a numerical experiment on a small graph of CT scans of liver tumours extracted from a MedMNIST medical dataset [3], where we depict how the first differences of the embeddings $\Delta^t_u$ and second differences $(\Delta^2)^t_u$ vary throughout a 4 layer DeltaGNN architecture (see Appendix D.2). *References:* [1] Müller, L., Galkin, M., Morris, C. and Rampášek, L., 2023. Attending to graph transformers. arXiv preprint arXiv:2302.04181. [2] Yan, Y., Hashemi, M., Swersky, K., Yang, Y. and Koutra, D., 2022, November. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In 2022 IEEE International Conference on Data Mining (ICDM) (pp. 1287-1292). IEEE. [3] Yang, J., Shi, R., Wei, D., Liu, Z., Zhao, L., Ke, B., Pfister, H. and Ni, B., 2023. Medmnist v2-a large-scale lightweight benchmark for 2d and 3d biomedical image classification. Scientific Data, 10(1), p.41.

*“Lemma 1 and 2”* Lemma 1 and 2 are important theoretical results which motivate the definition of our novel Information Flow Score. Lemma 1 highlights the relationship between $\overline{\Delta_u}$ and the graph homophily, demonstrating that high values of $\overline{\Delta_u}$ are linked to low node homophily (a detailed proof is included in Appendix B). On the other hand, Lemma 2 investigates the relationship between $\mathbb{V}_t[\Delta^2_u]$ and the graph connectivity, demonstrating that high values of $\mathbb{V}_t[\Delta^2_u]$ are linked to graph bottlenecks (an informal proof is included in Appendix C). Here, we would like to give the reviewer a more intuitive observation which motivates these facts. When a node experiences high values of $\overline{\Delta_u}$ this phenomenon can be linked to the ratio of neighbouring nodes with dissimilar features. Under certain assumptions on the distance between the subspaces of the feature space associated with the node classes, this fact can be used to show that the homophilic ratio of a node must be lower than a certain threshold. Similarly, high values of $\mathbb{V}_t[\Delta^2_u]$ can be linked to areas of the graph converging quickly to fixed feature values, which shows that the node $u$ must be highly connected within the graph. As a result, graph bottlenecks must coincide with very low values of $\mathbb{V}_t[\Delta^2_u]$. We hope these simple intuitions are helpful to understand these mechanics. We also suggest the reviewer have a look at Appendix D.2 where we included a numerical experiment which may give an additional graphical intuition to this topic. *“Information Flow Score equation”* Equation 2 defines the Information Flow Score, our **novel measure** designed to **detect areas of the graph affected by over-smoothing and over-squashing**. From Lemma 1, we know that a high value of $\overline{\Delta_u}$ is likely associated with a low homophilic ratio, and from Lemma 2, a low $\mathbb{V}_t[\Delta^2_u]$ indicates proximity to an edge bottleneck. Consequently, the score is defined as a fraction involving these two terms. This ensures that nodes with low values of our measure are likely to correspond to regions where over-smoothing and over-squashing occur. Since, in some applications, we may prioritize detecting bottlenecks over heterophilic edges (or vice versa), we introduce two multipliers, $l$ and $m$, to adjust the weights of the mean and variance in the final score. In our case, we aim to detect both with equal priority, so we set “$m = 1$” and “$l = 1$”. To ensure that the score remains well-defined, regardless of the delta values; and to prevent it from exploding when the deltas are close to zero, we added 1 to both the numerator and denominator. An additional advantage of adding 1 is that isolated nodes will receive a score of one, which is relatively low. As a result, training the model to rewire the graph while maximizing the overall score will encourage the model to remove edges while still preserving sparsity. A detailed analysis of the implementation of the Information Flow Score can be found in Appendix D. *“Heterophilic aggregation in DeltaGNN”* Throughout the paper, we use the term "heterophilic aggregation" to refer to an aggregation method designed to handle highly heterophilic neighborhoods.. In contrast, the term “homophilic aggregation” refers to a standard aggregation paradigm (e.g., mean, sum) that primarily supports homophilic neighborhoods. This distinction between homophilic and heterophilic aggregation is crucial to avoid the misconception that DeltaGNN should employ the same aggregation paradigm for processing both homophilic and heterophilic graphs.

*“Interaction-Decoupling in DeltaGNN”* We thank the reviewer for the insightful observation. Yes, it is correct. The proposed dual paradigm is introduced to improve node distinguishability by increasing the graph homophily and consequently slowing down the effects of over-smoothing (this last implication follows from Lemma 1). The effectiveness of this approach can also be appreciated by comparing the accuracy of DeltaGNN with its ablations (see Table 1). Moreover, Figure 8 (in Appendix G) depicts the rate of change of the graph homophily during the edge-rewiring (comparing our approach with six popular connectivity measures) showing superior performance of our model while consolidating our theoretical findings. (we summarize here our results) | **Methods** | **Original Graph** | **Homophilic Filtered Graph** | **Δ Homophilic Rate** | |----------------------------|--------------------|-------------------------------|------------------------| | Degree Centrality | 0.6676 | 0.7115 | +6.72% | | Eigenvector Centrality | 0.6676 | 0.6937 | +4.05% | | Betweenness Centrality | 0.6676 | 0.7057 | +5.85% | | Closeness Centrality | 0.6676 | 0.7043 | +5.64% | | Forman-Ricci Curvature | 0.6676 | 0.7094 | +6.40% | | Ollivier-Ricci Curvature | 0.6676 | 0.7112 | +6.67% | | Information Flow Score | 0.6676 | 0.7244 | **+8.65%** | *“Additional comparisons and experiments”* We would like to point out that **the main point of our work is to show a novel graph rewiring-inspired approach** for **simultaneously alleviating over-smoothing and over-squashing**, proposing a novel connectivity measure called Information Flow Score and architecture named DeltaGNN. For this reason, we believe that focusing on rewiring baselines is fair (which is aligned with recent works on this topic [4]). To strengthen our comparison we also included existing state-of-the-art graph-transformer baselines and heterophily-based methods such as NAGphormer [5] and H2GCN [6], even though these approaches are architecturally very different from ours and also computationally more expensive. As a result, we struggle to see how including additional comparisons with SOTA methods on heterophilic graphs could further strengthen our contributions. Additionally, we appreciate the reviewer’s suggestion to consider more challenging heterophilic datasets. Unfortunately, due to time constraints, we are unable to add such experiments at this time. We have already shown that our Delta GNN produces consistently better performance on graph datasets with varying sizes, topologies, and homophily. Specifically, we showed a reproducible and consistent reduction of the average epoch time of >30% when using DeltaGNN, proving its scalability with datasets of varying sizes and edge densities. **Specifically, we benchmarked our model on 10 datasets with up to 23660 nodes and 2’809’204 edges** (which is still considerably higher than some ogb datasets, like ogb-arxiv which includes on average graphs with ~1,166,243 edges). Please refer to Appendix D.2 for additional experiments on size-varying and density-varying graphs. In future research, we will consider including such datasets to improve experimental variety. We are happy to further discuss this point if necessary We thank once again the reviewer for the excellent questions. We really appreciate the detailed feedback and numerous references. Discussing such topics was truly beneficial to better articulate our contributions and we are happy to further engage with the reviewer. *References:* [4] Topping, J., Di Giovanni, F., Chamberlain, B.P., Dong, X. and Bronstein, M.M., 2021. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:2111.14522. [5] Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. Nagphormer: A tokenized graph transformer for node classification in large graphs. arXiv preprint arXiv:2206.04910, 2022. [6] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793–7804, 2020.

We appreciate that the reviewer found our work interesting and our ideas novel. Below, we address the questions and concerns raised, which we believe have strengthened our work. *(Weakness 1) “Large homophilic and heterophilic graphs”* We agree with the reviewer that additional experiments on larger datasets would be beneficial for further supporting our strong results on varying datasets with different disparate topologies. Unfortunately, due to our limited hardware capacity, as many ICLR research groups, we struggle to properly tune and fit GNN models in datasets with hundreds of thousands of nodes in a reasonable time frame. **For fairness, we believe that this request should not deter reviewers from acknowledging the merits of such works when they are evaluated on small-to-large scale graph data —but not very large ones such as ogb**. We have already shown that our Delta GNN produces consistently better performance on graph datasets with varying sizes, topologies, and homophily. Specifically, we showed a reproducible and consistent reduction of the average epoch time of >30% when using DeltaGNN, proving its scalability with datasets of varying sizes and edge densities. **Specifically, we benchmarked our model on 10 datasets with up to 23660 nodes and 2’809’204 edges** (which is still considerably higher than some ogb datasets, like ogb-arxiv which includes on average graphs with ~1,166,243 edges). Please refer to Appendix D.2 for additional experiments on size-varying and density-varying graphs. *(Weakness 2/3) “Graph filters and additional comparisons”* We would like to point out that **one of the key main contributions of our work is to show a novel graph rewiring-inspired approach for alleviating over-smoothing and over-squashing**, proposing a novel connectivity measure called Information Flow Score and a novel architecture named DeltaGNN. For this reason, we believe that focusing on rewiring baselines is fair (which is aligned with recent works on this topic [1]). To strengthen our comparison we also included existing state-of-the-art graph-transformer baselines and heterophily-based methods such as NAGphormer [2] and H2GCN [3], even though these approaches are architecturally very different from ours and also computationally more expensive. As a result, we struggle to see how including additional comparisons such as Graph Filters could be beneficial for our research. We are happy to further discuss this point if the reviewer finds it appropriate. *(Weakness 4) “MLP baseline”* We appreciate the reviewer’s observations and we agree that including a comparison against MLP could provide further insights into the performance of DeltaGNN. The manuscript has been updated and a table summarizing the performance disparity is reported below. | **Methods** | **CORA** | **Citeseer** | **PubMed** | **Cornell** | **Texas** | **Wisconsin** | |-----------------------------|------------------------------------|---------------------------------------|-------------------------------------|-------------------------------------|-----------------------------------|-------------------------------------| | MPL | 70.32±2.68 | 68.64±1.98 | 86.46±0.35 | 71.62±5.57 | **77.83±5.24** | **82.15±6.93** | | DeltaGNN *(best version)* | **87.29±0.52** | **79.90±0.79** | **89.98±0.24** | **75.67±1.91** | 74.05±3.08 | 80.00±0.88 | *References:* [1] Topping, J., Di Giovanni, F., Chamberlain, B.P., Dong, X. and Bronstein, M.M., 2021. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:2111.14522. [2] Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. Nagphormer: A tokenized graph transformer for node classification in large graphs. arXiv preprint arXiv:2206.04910, 2022. [3] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793–7804, 2020.

*(Question 1) “Memory consumption”* While DeltaGNN proved to be very efficient in terms of time complexity showing the best results (see Table 2), it also results in a higher memory footprint (on average x2.4 compared to a simple GCN) due to its dual architecture which inherently requires more learnable parameters. On the other hand, this additional complexity is independent of the graph size, this can be appreciated in Table 7, where the memory disparity between DeltaGNN and GCN remains the same also when benchmarking “Organ-S (dense)” which has 25’221 nodes and 2’494’750 edges. Additionally, we want to emphasize that, as demonstrated in the paper, our model remains more scalable in terms of memory consumption compared to graph transformers and state-of-the-art heterophily-based methods. *(Question 2) “Challenging heterophilic datasets”* In order to ensure a **fair and comprehensive benchmark** we considered **graphs with varying sizes** (from as low as 183 nodes up to 25’221), **densities** (from as low as 295 edges up to 2’809’204) and **homophilic ratios** (from as low as 0.09 up to 0.81). Since the Squirrel and Chameleon datasets have sizes, densities, and homophily ratios that fall well within these ranges, we chose to benchmark our model on additional datasets with more diverse characteristics to better evaluate its generalizability. However, we appreciate the reviewer’s suggestion as we will indeed, in future research, consider including such datasets to improve experimental variety. *(Question 3) “Minor typos”* We appreciate the reviewer’s observations and confirm that all minor issues highlighted in the review are solved in the last uploaded version of the manuscript. We thank the reviewer for the excellent questions and hope the revised paper addresses their concerns. We look forward to further engagement and hope this encourages an improved score.

We sincerely thank the reviewer for their thoughtful feedback and appreciate that you found our ideas to be both novel and impactful. Below, we provide detailed responses to your comments. *(Weakness 1-2): “Node embeddings”* The concept of aggregation velocity is the physical interpretation of the rate of change of the node embeddings throughout the aggregation within a GNN layer. **The higher this number, the faster a node embedding moves within the feature space at a certain time t**. To give a graphical intuition we included a numerical experiment on a small graph of CT scans of liver tumours extracted from a MedMNIST medical dataset, where we depict how the first differences of the embeddings $\Delta^t_u$ and second differences $(\Delta^2)^t_u$ vary throughout the 4th layer DeltaGNN architecture (see Appendix D.2). $\Delta^t_u$ is assumed to be a non-negative (non necessarily monotonically decreasing) sequence converging to zero defined over $\mathbb{R}$ (this has also been clarified in Lemma 1). When we compute $(\Delta^2)^t_u$ we simply measure how this sequence varies over time, as a result, the distance between $\Delta^{t}_u$ and $\Delta^{t-1}_u$ is mathematically well defined. However, arguing whether this is conceptually correct is considerably more challenging; we appreciate this insightful objection. While in general, directly comparing node features belonging to different spaces is conceptually wrong, if we determine some **invariant** belonging to the architecture which is preserved throughout the layers, it is fair to compare how a related property changes between these. In this case, we know that the sequence $\Delta^t_u$ converges to zero for some GNN architectures and this holds for all the layer’s feature spaces. **As a result, comparing how this property changes over time is conceptually consistent**. This approach is fairly common in literature when we want to understand how a feature-dependent property changes between different layers or architectures, for instance, when measuring how feature separability changes throughout a neural network’s layers [1]. *(Weakness 3): “Implementation of IFC”* We agree that providing implementation details in the main text would enhance clarity and accessibility for readers. We have now moved that section to the main body of the paper. With the updated version the functioning of the score hill ascent should also be more intuitive for the reader. *(Weakness 4): “Figure 2 clarity”* We improved the labelling of the subgraphs of Figure 2. In the subgraphs, the different curves in the feature density-feature value plots highlight how feature densities of different node classes compare before and after feature disentanglement. In the paper, the term “graph score” is used to indicate the “mean node score” of the graph. Both aspects have been clarified in the paper to improve clarity and consistency in notation. *(Weakness 5-6): “Lemma 1”* We appreciate the detailed feedback of Lemma 1. We removed the term “valid” introducing additional mathematical notation which, in our opinion, improved clarity. Additionally, **we expanded the final part of the proof** where we state the connection between $\Delta_u^t$, $U(\mathcal{H}_u)_u$ and the node homophilic ratio. *(Weakness 7): “Minor issues”* We appreciate the reviewer’s observations and confirm that all the minor issues highlighted in the review are solved in the last version of the manuscript. *(Question 1): “IFS on sum-aggregating GNNs”* We thank the reviewer for the insightful observation. Yes, it is correct. When we use our novel metric IFS on sum-aggregating GNNs like GIN, our assumption regarding the convergence of the sequence $\Delta^t_u$ is not respected in general (see appendix B). As a result, the aggregation velocity will fail to distinguish between different node homophilic rates. Additionally, sum-based aggregations provoke substantial changes in the feature embeddings, as a result will experience high values of $\Delta_u^t$ which will produce a high $U(\mathcal{H}_u)_u = \max_{s \in S} \Delta^t_u$ and finally high threshold $\rho \geq \max_{v \in \mathcal{V}, h \in [\mathcal{H},1]} U(h_v)_v$. However, as described in the paper, **a high threshold $\rho$ results in a bad distinction between nodes with different homophilic ratios**. We thank once again the reviewer for their excellent and detailed feedback. Your insightful questions and suggestions have helped us refine our contributions further. We hope that we have fully addressed your points and concerns. Please let us know if this remains unclear or if you consider any other discussion points to be open. We are of course happy to keep engaging with the reviewer throughout the process. *References:* [1] Schilling, A., Maier, A., Gerum, R., Metzner, C. and Krauss, P., 2021. Quantifying the separability of data classes in neural networks. Neural Networks, 139, pp.278-293.

We appreciate that the reviewer found our work interesting and our ideas novel. Below, we address the questions and concerns raised, which we believe have strengthened our work. *(Weakness 1) “The rationale behind heterophilic graphs.”* We thank the reviewer for the interesting questions as these are very important and interesting points you made. We would like to clarify that the purpose of the proposed DeltaGNN is to demonstrate the effectiveness of our novel approach called Information Flow Control (IFC) by introducing a scalable framework for **long-range and short-range interaction detection**. Moreover, the proposed IFC score has many applications. On the other hand, the IFC module is responsible for preventing over-smoothing and over-squashing, as demonstrated by our theoretical results (Appendix B, C) and numerical experiments (Appendix D). Moreover, as highlighted in the manuscript, the accuracy of our metric in distinguishing between homophilic and heterophilic nodes is correlated to “the maximum distance between the subspaces of M associated with the node classes” (where M is the feature space). Feature separability is domain-specific and more importantly dataset-specific, and prevents our method from getting perfect results. A more comprehensive discussion on this matter can be found in Appendix G, where we analyse the change in graph homophily ratio during the edge-filtering showing that our score can improve the graph homophilic ratio by +8.65% (Table 8). While this is far from being a perfect result, our approach proves to be **superior to all common graph topological measures** (while being less computationally expensive - Table 3) and represents an important step towards understanding how over-smoothing and over-squashing can be prevented from affecting GNNs accuracy. The presence of heterophilic graphs within DeltaGNN ensures the detection of long-range interactions and is not responsible for solving either over-smoothing or over-squashing (see Figure 3). Throughout our work, we consider exclusively node classification tasks, since our theoretical results assume the existence of node labels. In this specific task, the presence of non-existing node interactions within the heterophilic graph do not raise concerns as we are not trying to predict graph-level information (adding new edges is a fairly common technique to improve GNN node classification accuracy [1]). The learned features of the heterophilic graph detect how distant areas of the graph interact and are an essential component of our model, as it is supported by the lower classification accuracy of the ablated versions of DeltaGNN (see the performance of “GCN + rewiring(IFS)” in Table 1). We hope this is useful to clarify this point. *(Weakness 2) “Numerical evidence.”* We thank the reviewer for the suggestion. Indeed, the requested experiment can be found in Appendix G, where we directly compare several topological measures (including our novel Information Flow Score - IFS) and analyse the change of the graph homophilic ratio during the edge-filtering in the CORA dataset. The **IFS shows the highest increase in the homophilic rate**, with results reported below. | **Methods** | **Original Graph** | **Homophilic Filtered Graph** | **Δ Homophilic Rate** | |----------------------------|--------------------|-------------------------------|------------------------| | Degree Centrality | 0.6676 | 0.7115 | +6.72% | | Eigenvector Centrality | 0.6676 | 0.6937 | +4.05% | | Betweenness Centrality | 0.6676 | 0.7057 | +5.85% | | Closeness Centrality | 0.6676 | 0.7043 | +5.64% | | Forman-Ricci Curvature | 0.6676 | 0.7094 | +6.40% | | Ollivier-Ricci Curvature | 0.6676 | 0.7112 | +6.67% | | Information Flow Score | 0.6676 | 0.7244 | **+8.65%** | Additionally, in Appendix D we included a numerical experiment on a small graph of CT scans of liver tumours extracted from a MedMNIST medical dataset, where we analyse how the connectivity of the graph and the node scores change during the edge-filtering (see Figure 5, 6). **This evidence not only supports the effectiveness of our approach in alleviating over-squashing but also its generalizability in domains which are distant from commonly tested areas, such as citation networks**, and include **large and noisy node features** [1]. *References* [1] Nguyen, K., Hieu, N.M., Nguyen, V.D., Ho, N., Osher, S. and Nguyen, T.M., 2023, July. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature. In International Conference on Machine Learning (pp. 25956-25979). PMLR.

*(Weakness 3) “New experiments on large datasets.”* We agree with the reviewer that additional experiments on larger datasets would be beneficial for further supporting our strong results on varying datasets with different disparate topologies. Unfortunately, due to our limited hardware capacity, as many ICLR research groups, we struggle to properly tune and fit GNN models in datasets with hundreds of thousands of nodes in a reasonable time frame. **For fairness, we believe that this request should not deter reviewers from acknowledging the merits of such works when they are evaluated on small-to-large scale graph data —but not very large ones such as ogb**. We have already shown that our Delta GNN produces consistently better performance on graph datasets with varying sizes, topologies, and homophily. Specifically, we showed a reproducible and consistent reduction of the average epoch time of >30% when using DeltaGNN, proving its scalability with datasets of varying sizes and edge densities. **Specifically, we benchmarked our model on 10 datasets with up to 23660 nodes and 2’809’204 edges** (which is still considerably higher than some ogb datasets, like ogb-arxiv which includes on average graphs with ~1,166,243 edges). *(Question 1) “Implementation of the edge filtering.”* $\Theta_t\left(\mathbf{A}^{t-1}, K(t, \theta)\right.$, Score $\left.^t\right)$ indicates an edge-filtering operation filtering K(t,\theta) edges based on the Information Flow Score at time t (Score^t). In our experiments, we offered two implementations for K(t,\theta), one **constant** (which will result in a fixed number of edges filtered at every layer of the architecture), and one **linear** (where the number of filtered edges increases with the depth of the architecture). In both cases, we removed the edges associated with the lowest scores. (additional details on the implementation can be found in Appendix F.1). We thank once again the reviewer for the excellent questions and hope that we have clarified doubts in the new version of the paper. We hope that this is able to convince the reviewer to increase their score. We are of course happy to keep engaging with the reviewer throughout the process.