Dear Reviewer $\textcolor{blue}{Q7oz}$,

We sincerely appreciate your valuable and active feedback for improving our work. We hope we have addressed every question. Please feel free to let us know if there still are concerns not resolved to re-evaluate/re-rate our paper.

---

W1/Q1 Comparison to seemingly closely related previous work appears to be lacking

We appreciate your notification about the overlooked work and incorporated it in our general response 1, section 2, and appendix A. While LGNN is indeed a significant prior work first using the non-backtracking operator in the graph, it is essential to emphasize that it does not address the over-squashing issue.

In contrast, our NBA-GNN efficiently resolves redundant messages through non-backtracking, as theoretically demonstrated. The experimental results outlined in the general response 1 underscore the suboptimal performance and high complexity of LGNN in real-world datasets. Therefore, in comparison, our primary contribution lies in bridging the non-backtracking operator with the over-squashing problem, additionally offering superior space and time scalability compared to previous works alleviating over-squashing.

---

W2/Q2 NBA-GNNs are prohibitively expensive and the additional expense in terms of computation time is insufficiently explored

Yes, undoubtedly there is an increase in time complexity compared to GNNs. However, we emphasize our method is superior to other previous works alleviating over-squashing, on average test time per epoch and preprocessing times. From the two tables below, one can easily conclude that our method does not face bottlenecks in time compared to other baselines, irrelevant to the number of layers.

Table 1 - Theoretical & actual time complexity for preprocessing($b$: branching factor, $k$: number of layers, and $d_{avg}$: average degree of nodes)

Table 2 - Average test time per epoch (Tested on a single RTX 3090, the batch size inside the parentheses)

---

W3/Q3 The theoretical result in Theorem 1 is only a weak indication of alleviated over-squashing

We acknowledge that our upper bound may not be sufficiently tight as we discussed in the general response 2. However, our theorem is the first to compare the quantity of over-squashing in GNNs, aligning with different random walks.

We understand your reservations about the strength of our theoretical results despite our assertion of being the first to compare the degree of over-squashing between GNNs using different random walks. We would like to provide additional insights into the unique contributions of our work:

1. Novelty in Comparison Methodology: Our primary contribution lies in introducing a novel approach to compare the degree of over-squashing among GNNs. By aligning with different random walks, we believe we provide a fresh perspective that adds to the existing body of knowledge.

2. Interpretation through Random Walks: While previous works have utilized metrics like curvature or effective resistance to assess graph topology in the sensitivity upper bound, we've taken a distinctive path by interpreting it through the lens of random walks. This allows for a unique and complementary understanding of the graph structure.

3. Realism in Sensitivity Bounds: We acknowledge your point about the challenges of demonstrating the tightness of sensitivity bounds. Our intention is not to set unrealistic assumptions, but rather to provide a theoretical framework that is more aligned with real-world scenarios, where the sensitivity term may not be consistently set to zero.

We would greatly appreciate any specific feedback or suggestions you may have regarding aspects of the theoretical results that could be strengthened or clarified. Your insights are crucial to us, and we are dedicated to addressing any concerns to the best of our ability.

Once again, thank you for your thoughtful evaluation, and we look forward to the possibility of further discussion to enhance the clarity and robustness of our theoretical contributions.

Dear Reviewer $\textcolor{green}{ayH6}$,

We sincerely appreciate your valuable and active feedback for improving our work. We hope we have addressed every question. Please feel free to let us know if there still are concerns not resolved to re-evaluate/re-rate our paper.

---

W1 Mainly it seems the authors do not know about the work LGNN, and the contribution of the article is too small.

We appreciate your notification and kind explanation about LGNN. Indeed, this is a crucial prior work using the non-backtracking operator and we have added details of it as mentioned in general response 1. However, we highlight that LGNN does not make any connection between the non-backtracking update and the message redundancy problem, obviously not alleviating over-squashing. Moreover, because of its k-hop aggregation process within a single layer and sequential updates between the original graph and line graph, LGNN suffers significant computational complexity.

Our NBA-GNN, on the other hand, resolves redundant messages specifically using the non-backtracking operator. The experiment results in general response 1 highlight the poor performance and high complexity of LGNN in real-world datasets. Therefore, in comparison, our main contribution is bridging the non-backtracking operator to message redundancy problems, with superior space and time scalability compared to previous works alleviating over-squashing.

---

W2 The theoretical analysis the authors propose is quite light

As discussed in the general responses 2 and 3, even though our theoretical analysis may exhibit limited novelty, we want to emphasize our primary contributions on the theoretical side: firstly, the first analysis of specifically connecting the non-backtracking operator with the sensitivity upper bound, and secondly, the establishment of a connection between prior works on the spectrum non-backtracking matrix and GNNs.

---

Q1 They could compare to the conjectured optimal performances given by BP on sparse SBM

Following your advice, we conducted a comparative analysis involving NBA-GNN, BP, and LGNN on two sparse SBMs with distinct parameters: (a) a Binary Assortative SBM (n = 400, C=2, p = 20/n, q = 10/n), and (b) a 5-community Dissociative SBM (n = 400, C=5, p = 0, q = 18/n), where n represents the number of vertices, C is the number of classes, and p and q denote edge probabilities within and across communities, respectively. The table presented below illustrates the average test accuracy across 100 graphs. Notably, BP, known for achieving the information-theoretic threshold, exhibited the best performance, consistent with expectations. Additionally, our NBA-GNN outperformed LGNN in both scenarios.

Table 1 - Average test accuracy on two sparse SBMs

---

Q2 It would have been interesting to consider NBA-GNN on the CSBM since this model has features

Yes, we agree that it would be an interesting extension to our works, as we can explore the impact of node features when analyzing the algorithm's performance, under the conditions inferred in real-world datasets

---

Q3 reference for first used non-backtracking matrix for node classification: arxiv:1306.5550

We thank you for bringing the overlooked work to our attention. We will definitely incorporate it into the related works section.

W4 Space and time complexity increases compared to standard GNNs.

Yes, the space and time complexity increases compared to the backbone GNN. However, NBA-GNN achieves superiority over complexity compared to previous work that alleviates over-squashing. We provide the preprocessing time, test time per epoch, and memory usage below.

Table 1 - Theoretical & actual time complexity for preprocessing($b$: branching factor, $k$: number of layers, and $d_{avg}$: average degree of nodes)

Table 2 - Average test time per epoch (Tested on a single RTX 3090, the batch size inside the parentheses)

Table 3: Memory usage (Single RTX 3090, the batch size inside the parentheses)

---

W5 Experimental evaluation: Table 1 contains the maximum of two variants (NBA, begrudgingly) which seems unfair

Yes, the NBA results presented in Table 1 represent the maximum of non-backtracking and begrudgingly walks. While we have reported this in accordance with the prior work DRew [1], it is worth noting that this approach may be perceived as unfair. We have provided an ablation study in Figure 5(c) for a comparison between two variants on the Peptides-func dataset. In response to the reviewer's request, we have also reported the variants in the peptides-struct dataset (given the absence of dangling nodes in the VOC-SP dataset). Despite these considerations, our results still demonstrate improvements compared to the baselines.

[1] Gutteridge et al., DRew: Dynamically Rewired Message Passing with Delay, ICML 2023

---

Q1 How does the expressivity of NBA-GNNs (e.g., NBA-GIN) compare to GIN?

Building on a similar argument as discussed in the response to W2-2, if we assume that the aggregation and update functions in the layers of NBA-GNN, as specified in equation (3) in our paper, are injective, we can infer that NBA-GNN is at least as powerful as GIN or NBA-GIN.

---

Q4 intuition of begrudgingly backtracking should work better and redundancy

The underlying idea is to address the information loss caused by the excessive reduction of redundancy, particularly in proximity to dangling nodes—those with only one neighbor. When a message reaches a dangling node, it becomes unable to propagate information to other nodes, leading to information loss. To mitigate this, we employ begrudgingly backtracking.

---

Q5 Results for GIN/GCN with LapPE

Yes, there are. As one can see in Table 1 in the paper, we have provided the results for GCN, GIN with and without LapPE, and LapPE. As the reviewer assumed, the LapPE indeed enhances the performance for long-range tasks. M1 The caption of Figure 3 contains several repetitions Thank you for your careful review. We have modified Figure 3 and its caption to make it clear.

---

M1 The caption of Figure 3 contains several repetitions

Thank you for your careful review. We have modified Figure 3 and its caption to make it clear.

Dear Reviewer $\textcolor{lime}{apAV}$,

We sincerely appreciate your valuable and active feedback for improving our work. We hope we have addressed every question. Please feel free to let us know if there still are concerns not resolved to re-evaluate/re-rate our paper.

---

W1, Q2 The authors do not sufficiently discuss closely related works

We appreciate your notification and explanation about closely related works. We have discussed them in the general response 1, related works section, and added the detailed difference in Appendix A, as mentioned in general response 1. We clarify the distinction as follows:

Mahé et al.: We note that the construction of the graph in Mahé uses both node and edge representation, while ours only uses edge-wise representation for non-backtracking. Moreover, CINs [1, 2] could be considered an extent of Mahe et al., with message-passing between different dimension cell complexes.

LGNN (Chen et al. `19): A notable distinction between NBA-GNN and LGNN is that LGNN employs the non-backtracking operator inside a layer. When layers are stacked, redundancy is not addressed at all, and consequently cannot alleviate over-squashing. However, NBA-GNN keeps the non-backtracking characteristic across all layers to reduce redundant messages and theoretically shows that the sensitivity upper bound is bigger.

RFGNN (Chen et al. `22): We agree that the motivation is very similar. However, while RFGNN constructs a tree of non-backtracking paths from all nodes, NBA-GNN considers non-backtracking by edge adjacency through all layers. Thanks to this, while RFGNN suffers from a space and time complexity of $\mathcal{O} (\vert V \vert^{k+1})$, our NBA-GNN only requires $d_{avg} \vert\mathcal{E}\vert$, irrelevant to the number of layers $k$. This allows our NBA-GNN scalable to larger graph datasets, compared to RFGNN. Furthermore, in terms of theory, our work differs by stating the sensitivity upper bound of non-backtracking update, not comparing the relative inference of paths.

[1] Bodnar et al., Weisfeiler and Lehman Go Cellular: CW Networks

[2] Giusti et al., CIN++: Enhancing topological message passing

---

W2-1 Analysis of expressive power - The exact learning task in thm2, how to interpret “can accurately map graph $\mathcal{G}$ to node labels"?

The learning task of theorem 2 is the node classification. In this theorem, we are discussing the ability of NBA-GNNs that classify each node in one graph, even in the very sparse case.

---

W2-2 Analysis of expressive power - It is unclear whether standard GNNs with WL expressivity cannot solve these learning tasks, at least theoretically

From the WL perspective, NBA-GNN is as powerful as the WL test (and other equivalently powerful GNN structures such as GIN) under the assumption that the aggregation and update functions in the layers of NBA-GNN, as specified in equation (3) in our paper, are injective. To illustrate this, consider the scenario where NBA-GNN maps graphs $G$ and $H$ to identical embeddings. In this case, an order of oriented edges $e_i\in E_{G}$, and $d_i\in E_{H}$ exists, satisfying $f(e_i)=f(d_i)$, where $f$ is the non-backtracking message passing update function. This implies that {$j|e_j\in N(e_i)$}={$j|d_j\in N(d_i)$} holds for any given $i$. By the definition of oriented edges, there also exists an order of vertices $u_i\in V_{G}$, and $v_i\in V_{H}$ such that {$j|u_j\in N(u_i)$}={$j|v_j\in N(v_i)$} for all $i$. Consequently, the 1-WL test determines that $G$ and $H$ are isomorphic, establishing that NBA-GNN is equally powerful as the WL test.

However, while we explore the previous works on the expressivity of GNNs, we found that the WL test has some limitations in that it cannot measure the expressive power concerning node classification tasks, and still, it is difficult to compare the proposed algorithms due to the wide performance gap between the 1-WL and 3-WL tests. Therefore, we focus on the spectral analysis in this work to analyze the theoretical performance of NBA-GNNs.

---

W3, Q3 Can NBA-GNN be extended to avoid redundancy in cycles by non-backtracking within $k$ hop?

No, NBA-GNN considers redundancy by two consecutive steps in a random walk. Efficiently resolving redundancy occurred by cycles is an interesting future work, since the VOC-SP dataset contains a massive number of cycles.

Dear Reviewer $\textcolor{red}{WPCH}$,

We sincerely appreciate your valuable and active feedback for improving our work. We hope we have addressed every question. Please feel free to let us know if there still are concerns not resolved to re-evaluate/re-rate our paper.

---

W1 The paper lacks a detailed description of the non-backtracking operator

We discussed the non-backtracking operator in the sensitivity analysis, section 4.1. However, as the reviewer suggested, providing a detailed description of using the non-backtracking operator in NBA-GNNs can enhance comprehension. To address this, we added a detailed description in Appendix E regarding the application of the non-backtracking operator in NBA-GNNs.

---

W2 Preprocessing time, run time, and memory usage

We thank reviewer $\textcolor{red}{WPCH}$ for suggesting a fair comparison with baselines, considering the complexity of our method. Our method achieves superior results in all three terms, preprocessing time, run time, and memory usage compared to previous works suggested to alleviate over-squashing.

• Preprocessing time

We compared the preprocessing time of the peptides-functional dataset. Our preprocessing time is approximately half of DRew, and 1/10 of PathNN-SP as shown in the table below. It is also worth noting that the preprocessing time of previous methods is proportional to the number of layers, NBA-GNN is irrelevant to the number of layers.

Table 1 - Theoretical & actual time complexity for preprocessing($b$: branching factor, $k$: number of layers, and $d_{avg}$: average degree of nodes)

• Running time, memory usage

The average test time per epoch and memory usage have been measured, by reducing the batch size of previous methods except GCN since the paper’s parameters did not fit on a single RTX 3090. We use 8 layers, a hidden dimension of 120 for all experiments, and have written the batch size inside the parentheses.

Table 2 - Average test time per epoch (Tested on a single RTX 3090)

Table 3 - Memory usage (Single RTX 3090)

---

Q1 What is the performance of NBA-GNN on the other two datasets in LRGB?

We attempted additional experiments for PCQM and Pascal-SP. However, we note that these datasets are quite large compared to peptides and VOC-SP, with approximately 8 to 10 times more data. Regrettably, we only present the experiment results of NBA-GCN on PCQM, one can still see that the performance does not vary much even without tuning.

Table 4 - PCQM PCQM results without tuning

M3. A detailed explanation of computational complexity

To incorporate your comment, we provide extensive investigation on the increase in computational complexity incurred by our idea.

Table 1 - Theoretical & actual time complexity for preprocessing ($b$: branching factor, $k$: number of layers, and $d_{avg}$: average degree of nodes)

Table 2 - Average test time per epoch (Tested on a single RTX 3090, the batch size inside the parentheses)

One can observe that our NBA-GNN indeed increases the computational cost, but our method still achieves superior time complexity over previous works that alleviate over-squashing.

Dear Reviewer $\textcolor{violet}{w5ts}$,

We sincerely appreciate your valuable and active feedback for improving our work. We hope we have addressed every question. Please feel free to let us know if there still are concerns not resolved to re-evaluate/re-rate our paper.

---

W1/W2. The paper misses important related works (Chen et al., ICLR 2019)

Thank you for pointing out a significant related work. To incorporate your comment, we conceptually and empirically compare our work and the suggested work (in our General Response 1, Sections 2, and Appendix A). In comparison to the reference (Chen et al., ICLR 2019), our contribution is the consideration of the non-backtracking operator specifically for the message redundancy problem, rather than proposing a novel/first non-backtracking architecture in GNNs.

---

W3-1. Proposition 1 only works for trees, being too far away from the setup of NBA-GNNs

Yes, proposition 1 only holds for trees. However, we note that this proposition is only a motivating example to use non-backtracking, not a theoretical claim that NBA-GNN can mitigate over-squashing. We point out additional references [1,2] that investigate faster access time of non-backtracking walks compared to conventional random walks.

[1] Yuan Lin and Zhongzhi Zhang. Non-backtracking centrality based random walk on networks. The Computer Journal, 62(1):63–80, 2019.

[2] Dario Fasino, Arianna Tonetto, and Francesco Tudisco. Hitting times for second-order random walks. European Journal of Applied Mathematics, 34(4):642–666, 2023.

---

W3-2. Lemma 1 and Theorem 1 only provide upper bounds on the sensitivity.

Yes, theorem 1 only provides the upper bound for the sensitivity analysis. However, as mentioned in the general response 2, we would like to emphasize that the contribution of Theorem 1 is being the first to compare the degree of over-squashing between GNNs, aligning with different random walks.

---

W3-3. For moderate-to-large degree d, the decay rates of the two sensitivity upper bounds will become very close. Moreover, this finding is not in agreement with the empirical findings from Table 1.

Thank you for the insightful comment. Indeed, our analysis of the regular graphs is more meaningful for graphs with a small degree. Nonetheless, we believe this result to be meaningful since many real-world graphs, e.g., community and molecular graphs, are sparse. Also, we believe that one cannot compare the performance improvements in different datasets in an apple-to-apple way, e.g., VOC-SP performance may be more susceptible to over-squashing in GNNs compared to the peptides-func dataset.

---

W3-4. The theoretical analysis in Section 4.2 is not very novel

While one might perceive it that way, our analysis is novel since it integrates earlier works on the non-backtracking matrix into GNNs. This integration has the potential to pave the way for advancements in the field, suggesting new perspectives that could lead to innovative insights and methodologies within the GNN framework.

---

M1. References on the expressivity of GNNs from spectral considerations

Thank you once again for bringing the overlooked work to our attention. We will certainly incorporate it into the related works section of our paper. The study by Kanatsoulis and Ribeiro introduces a novel approach to analyzing the expressivity of GNNs, utilizing linear algebraic tools and eigenvalue decomposition of graph operators. Their work showcases that GNNs have the capability to generate distinctive outputs for graphs with varying eigenvalues.

---

M2. The paper can be quite wordy, and repeat many of the same observations

We will review the manuscript to ensure that the repetitions are necessary for the overall coherence of the paper.

3. Lack of novelty in Theorems 2, 3 ($\textcolor{violet}{w5ts}$, $\textcolor{green}{ayH6}$, $\textcolor{lime}{apAV}$)

In Theorems 2 and 3, we demonstrate the expressive capabilities of NBA-GNNs. Previous research has shown that the spectrum of the non-backtracking matrix possesses a valuable property for revealing hidden structures, even in very sparse settings. Specifically, [1] demonstrates the non-backtracking matrix's spectral separation property and the presence of an eigenvector containing information about the community index of vertices. Additionally, [2] reveals that analyzing the distribution of eigenvalues allows us to distinguish whether a graph originates from the Erdős–Rényi model or the SBM.

Building on these foundational works, we establish the existence of a function of the spectrum of the non-backtracking matrix that can accurately recover its hidden structure. We also demonstrate that a series of convolutional layers in NBA-GNNs can act as this function by approximating the spectrum of the non-backtracking matrix. This shows the theoretical evidence of enhanced expressive power of NBA-GNNs in both node and graph classification tasks.

While this approach may not seem entirely novel, it contributes to a deeper understanding of the expressive power within GNN structures by establishing connections between prior research on the non-backtracking matrix and GNNs.

[1] Ludovic Stephan and Laurent Massoulié. Non-backtracking spectra of weighted inhomogeneous random graphs. Mathematical Statistics and Learning, 5(3):201–271, 2022.

[2] Charles Bordenave, Marc Lelarge, and Laurent Massoulié. Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 1347–1357. IEEE, 2015.