Non-backtracking Graph Neural Networks
Authors: Seonghyun Park
Narae Ryu
Gahee Kim
Dongyeop Woo
Se-Young Yun
Sungsoo Ahn
Venue: Accepted by TMLR ()

Abstract: The celebrated message-passing updates for graph neural networks allow representing large-scale graphs with local and computationally tractable updates. However, the updates suffer from backtracking, i.e., a message flowing through the same edge twice and revisiting the previously visited node. Since the number of message flows increases exponentially with the number of updates, the redundancy in local updates prevents the graph neural network from accurately recognizing a particular message flow relevant for downstream tasks. In this work, we propose to resolve such a redundancy issue via the non-backtracking graph neural network (NBA-GNN) that updates a message without incorporating the message from the previously visited node. We theoretically investigate how NBA-GNN alleviates the over-squashing of GNNs, and establish a connection between NBA-GNN and the impressive performance of non-backtracking updates for stochastic block model recovery. Furthermore, we empirically verify the effectiveness of our NBA-GNN on the long-range graph benchmark and transductive node classification problems.

Published in Transactions on Machine Learning Research (09/2024)
Non-backtracking Graph Neural Networks
Seonghyun Park'1, Narae Ryu Gahee Kim², Dongyeop Woo', Se- Young Yun Sungsoo Ahn
{skpork26, dongyeop. woo, sungsoo. www.soo...nn/ae www..ec..k./ppttecc...... (urrya, gakeekim, yunseyoung) @kaist uc.kr POSTECH *KASST
Reviewed on OpenReview: https: // opwreview.. net/ id- 64HdQKnyTc
Abstract
The celebrated message- passggggggnig updates for graph neural networks allow representing large- scale graphs with local and computationally tractable updates. However, the updates suffer from backtracking, i.e., message flowing through the same edge twice and revisiting the previously visited node. Since the number of message flows increases exponentially with the number of updates, the redundancy in local updates prevents the graph neural network from accurately recognizing a particular message flow relevant for downstream tasks. In this work, we propose to resolve such a relundancy issue via. the non-backtracking graph neural network (NBA-GNN) that updates a message without incorporating the message from the previously visited node. We thcoretically investigate how NBA-GNN alleviates the over-squashing of GNNs, and establish a connection between NBA-GNT and the impressive performance of non-backtracking updates for stochastic block model recovery. Furthermore, empirically verify the effectiveness of our NBA-GNN the long- range graph benchmark and transductive node classification problems.
1 Introduction
Recently, graph neural networks (GNNs) (Kipf & Welling, 2017; Hamilton et al., 2017; Xu et al., 2019) have shown great success in various applica- tions, such as molecular property prediction (Gilmer et al., 2017) and community detection (Bruna & Li, 2017). Such success can be largely attributed the message-
Simple
Nan-hackttaacking
geessag-passsng passing structure of GNNs, which provides computationally tractable way of incorporating the overall graph through iterative updates based local neighborhoods. However, the pessage-passing structure also brings challenges due to the paral- updates and memoryless behavior of messages passed along the graph.
Step 1
Step 2
Figure 1: Comparison of two types of message flow.
Step 1: Message flow from node i to node j. Step 2: The simple update includes the message flow from node j back to node i (left) at step 1, while the non- backtracking update removes this redundant message flow (right).
In particular, the message flow in GNN is prone to backtracking, where the message from vertex i to vertex j is reincorporated in the subsequent message from to i, c.g. the left image of step 2 in Figure 1. Since the pessage-passing iteratively aggregates the information, the GNN inevitably encounters an exponential surge in the number message flows, proportionate to the vertex degrees. This issue is compounded by backtracking, which accelerates the growth of message flows with redundant information.
Equal Contribution, Co-coresponding author.

---

Published in Transactions on Machine Learning Research (09/2024)
The effectiveness of non-backtracking updates has been extensively explored in non-GNN mussage-passing algorithms or random walks (Fitzner & van der Hofstad, 2013; Rappaport et al., 2017) (Figure 1). For example, given a pair of vertices i, the belief propagation algorithm (Pearl, 1982) forbids an i - j message from incorporating the j - i message. Researchers have similarly considered non-Markovian walks (Alon et al., 2007); i.e., walks that do not consecutively traverse the same edge twice. Such classic algorithms have demonstrated great success applications such as probabilistic graphical model inference and stochastic block models (Bordenave et al., 2015). In particular, the spectrum of the non-backtracking operator contains more useful information than that of the adjacency matrix in revealing the hidden structure of graph model (Bordenave et al., 2015).
However, despite their promise, non-backtracking updates have received limited attention in the context of GNNss While Chen et al. (2018) have considered combining non-backtrane aanbbcctrrakknng updates with the typical GNN updates, the updates are not designed to prevent backtracking updates, and the analysis is limited to the optimization landscape of linear GNNs. Hence, a thorough investigation of the benefits of non-backtracking updates in GNNs is warranted.
Contribution. In this paper, propose to use non-backtracking graph neural network (NBA-GNN) to resolve the redundant messages, the over-squashing phenomenon. We employ non-backtran non-backtracking updates on the messages, i.e., forbid a message from vertex i to vertex j from being incorporated in the message from vertex j i. To this end, we associate hidden features with transitions between a pair of vertices, e.g., hy-ri and update them from features associated with non-backtracking transitions, e.g., ha- for fi.
To motivate our work, we formulate "message flows" as the sensitivity of a GNN concerning walks in the graph. Then, we explain how the message flows redundant; the GNN's sensitivity of walk with backtracking transitions is covered by other non-backtracking walks. The redundancy harms the GNN since the number of walks increases exponentially as the mumber of layers grows and the GNN becomes insensitive to a particular walk information. Hence, reducing the redundancy by simply considering non-backtracking walks would benefit the peessage-passingg updates to recognize each walk's 's information better. As a motivating example, we provide a connection between our sensitivity analysis to the over-squashing phenomenon for GNN (Topping et al., 2022; Black et al., 2023; Di Giovanni al., 2023) in terms of access time.
Furthermore, we analyze our NBA-GNNs from the perspective of over-squashing and their expressive capa- bility to recover sparse stochastic block models (SBMs). To this end, we prove that NBA-GNN improves the Jacobian-based measure of over-squashing (Topping et al., 2022) compared to its original GNN counterpart.
Next, we investigate NBA-GNN's proficiency in node classification within SBMs and its ability to distin- guish between graphs originating from the Erdös- model or the SBM, from the results of (Stephan & Massoulié, 2022; Bordenave et al., 2015). Unlike traditional GNNs that operate on adjacency matrices and necessitate an average degree of at least 2(log n), NBA-GNN demonstrates the ability to perform node classification with substantially lower average degree bound of (1) and (()),, Furthermore, the algorithm can accurately classify graphs even when the average degree remains constant.
Finally, we empirically evaluate our NBA-GNN on the long-range graph benchmark (Dwivedi et al., 2022) and transductive node classification problems (Sen et al., 2008; Pei et al., 2019). We observe that our NBA-GNN demonstrates competitive performance and even achieves statc-of-tho-art performance on the long-range graph benchmark. For the node classification lasks, we demonstrate that NBA-GNN consistently improves over its conventional GNN counterpart.
To summarize, our contributions are as follows:
We propose NBA-GNN as a solution for the message flow redundancy problem in GNNs.
We analyze how NBA-GNN alleviates over-squashing and is expressive enough to recover sparse stochastic block models with an average degree of o(log n).
We empirically verify our NBA-GNN to show state-of-the-att performance on the longerange graph bench- mark and consistently improve over the conventional GNNs for the transductive node classification tasks.
2

---

Published in Transactions on Machine Learning Research (09/2024)
2
Related works
Non-backtracking Algorithms. Many classical algorithms have considered non-backtracking updates (Newman, 2013; Kempton, 2016). Belief propagation (Pearl, 1982) infers the marginal distribution on probabilistie graphical models, and has demonstrated success for tree graphs (Kim & Pearl, 1983) and graphs with large girth (Murphy al., 1999). Moreover, Mahé et al. (2004) and Aziz et al. (2013) suggested graph kernels between labeled graphs utilizing non-backtracking walks, and Krzakala et al. (2013) first used it for node classification. Furthermore, the non-backtracking has been shown to yield better spectral separation properties, and its eigenspace contains information about the hidden structure of a graph model (Bordenave et al., 2015; Stephan & Massoulié, 2022).
Non-backtracking and GNNs. We also note that there have been similar approaches of applying non- backtracking to GNNs. Chen et al. (2018) first used the non-backtracking operator in GNNs, though they do not prevent backtracking and only target community detection tasks. Also, Chen al. (2022) have computed non-redundant tree for every node to eliminate redundancy, but inevitably sulfers from high complexity. We emphasize the distinction between prior works and our NBA-GNN in Appendix A from the lens of (i) computational complexity and (ii) empirical performance.
Over-squashing of GNNs. When node receives information from k-hop neighbor node, an expo- nential number of messages pass through node reprosentations with fixed-sized vectors. This leads to the loss of information known over-squshhing (Alon & Yahav, 2021), and has been formalized in terms of sensitivity (Topping et al., 2022; Di Giovanni et al., 2023). Hence, sensitivity is defined as the Jacobian of a final node feature at GNN layer to the initial node representation and can be upper bounded via the graph topology. Stemming from this, graph rewiring methods alleviate wver-squshhng by adding or removing edges to compute an optimal graph (Topping et al., 2022; Black et al., 2023; Di Giovanni et al., 2023). Another line of work uses global aspects, e.g., Transformers have been applied to consider global aspects to avoid over-squashing (Ying et al., 2021; Kreuzer et al., 2021; Rampášck al., 2022; Shirzad et al., 2023).
Expressivity of GNNS for the SBM. Certain studies focus on analyzing the expressive power of GNNs using variations of the SBM (Holland et al., 1983). Fountoulakis et al. (2023) established conditions for the existence of graph attention networks (GATs) that can precisely classify nodes in the contextual stochastic block model (CSBM) with high probability. Similarly, Baranwal et al. (2023) investigated the effects of graph convolutions within a network on the XOR-CSBM. The preceding works primarily focused on the probability distribution of node features, such the distance between the means of feature vectors. On the other hand, Kanatsoulis & Ribeiro (2023) analyzed the expressivity utilizing linear a algebraic tools and eigenvalue decomposition of graph operators.
3 Non-backtracking Graph Neural Network
3.1 Motivation from Sensitivity Analysis
We first explain how the conventional message-passing updates are prone to backtracking. To be specific, consider a simple, undirected graph g = (V,E) and let M(()) denote the set of neighbor nodes of the node i. Each node i V is associated with a feature IG. Then, the conventional graph neural networks (GNNs), i.e., peessgg-passsing neural networks (MPNNs) (Gilmer et al., 2017), iteratively update the node-wise hidden feature at the f-th layer (!) as follows:
1 (+1 (+t= = =600
(1)
where ((() and 4i are architecturee-speiffc non-linear update and permutation invariant aggregation func- tions, respectively. Our key observation that the message from node feature (9) the node feature h ((+1) is reincorporated in the node feature h (l+2) GNNs with redundant messages.
e.g., Figure 3a shows the computation graph of conventional
3

---

Published in Transactions on Machine Learning Research (09/2024)
Sensitivity Analysis. To concretely describe the consequences of backtracking in message-passing up- dates, we formulate the sensitivity of the final node feature n,7) with respect to the input as follows:
Σ The JEV on SEW
Oh 5(
Σ
II
(2)
t=) 0h (11))
s(t-1)
where 11 = Di, W(i) denotes the set of 7-step walks ending at node i, and s(l) denotes the 1-th node in the walk & E W(i. Intuitively, this equation shows that a GNN with T layers recognize the graph via aggregation of random walks with length T. Our key observation from Equation (2) is how the feature h!")) is insensitive to the information from an initial node feature h (0) due to the information being "squashed" by the aggregation over the exponential number of walks W(i). A similar analysis has been conducted on how node feature ((4)) is insensitive to the lar-away initial node feature 1 2jj i.e., the over-squashing phenomenon of GNNs (Topping et al., 2022).
Redundancy of walks with backtracking. In particular, a walk 8 randomly sampled from W(1) is likely to contain transition that back- tracks, i.e., s(l) slI+2) 2) for some < T. The walk would be redundant since the informa- tion is contained in two other walks in W(i): and s()),... ................................ ((t)s(t+1), s(L+ 2) = s(), s((3)),....
s(t 10-10 1]
8 43
a
+ 3)
s(t +
as illust rated in Fig- ure 2. This leads to the conclusion that non- backtracking walks, i.c., walks that do not con- lain backuracking transitions, are sufficient to express the information in the walks W(i). Since the exponential number of walks in W(i) causes the GNN to be insensitive to particular walk information, it makes sense to design zon-backtracking GNN that is sensitive to the constrained set of non- non-backtracking walks.
Figure 2: Two non-backtracking walks (right) are sufficient to express information contained in walk with backtrack- ing transition (left).
Relation to Over-squashing. Finally, we point out an intriguing motivation for our work in terms of over-squashing. Di Giovanni et al. (2023) analyzed the lower bound for the Jacobian obstruction that measures the degree of squashing in terms of access time with respect to a simple random walk. They concluded that the degrec of over-squahhing, i.c., the size of Jacobian obstruction, is higher for a pair of nodes with longer access time. Hence, for GNN architecture robust to over-squashing, one could (i) propose random walk that has shorter access time for pair of nodes in the graph, and (ii) design a GNN that aligns with the random walk. Since non- nunbbacttrackng random walks have been empirically shown and believed to generally yield faster access time than simple random walks (Lin & Zhang, 2019; Fasino et al., 2023), one could aim to design a GNN architecture that aligns with the non-backtracking random walks.
However, to the best of our knowledge, there no formal proof of scenarios where non-backtracking random walks yield a shorter access time. As motivating example, we provide a theoretical result comparing the access time of non- non- backtracking and simple random walks for tree graphs. Since non- con-backtracking random walks do not guarantee a walk of a certain length, we make use of begrudgingly backtracking random walks (Rappaport et al., 2017), which modifies non-backtracking random walks to remove "dead ends" for tree graphs. For the full proof, please refer to Appendix B.
Access Time of Random Walks.
Proposition 1. Given a tree G = (V,E) and a pair of nodes i.j E V, the access time of begrudgingly backtracking random walk is equal to or smaller than that of a simple random walk. The equality holds if and only if the walk length 1.
3.2 Method Description
In this section, we present the Non- Bon-BAcctrackinn GNN (NBA-GNN) with the motivation described in Section 3.1. Given an undirected graph G (V,E), our NBA-GNN associates a pair of hidden features
4

---

Published in Transactions on Machine Learning Research (09/2024)
(a) Compulation graph of typical GNN
(b) Computation graph of NBA-GNN
Figure 3: Computation graph of typical GNN and NBA-GNN predicting node "0" (a) Redundant messages
increase the size of the computation graph, proportional to the number of layers. (b) NBA-GNN assigns
pair of features for each edge and updates them via nonbbacktracking message passing. By reducing redundant messages, it results in simplified computation graph compared to typical GNNs.
h Mi-gs hi for each edge {i,j}. Then the non- non-backtracking message passing update for a hidden feature h h defined as follows:
5 = 1000=(h (5(1) -0(0)
- (1/200 (100) (11 : k NN) (oN)))))
where () and eh( are backbone-specifie non-linear update and permutation-invaaiien aggregation functions at the t-th layer, respectively. For example, vi(t) and glt) are multi-layer perceptron and summation over set for the graph isomorphism network (Xu et al., 2019, GIN), respectively. Given the update in Equation (3), one can observe that the message h is never incorporated in the message h (( and hence the update is free from backtracking. Note that line graph neural networks (Chen et al., 2018, LGNN) also applied non-backtracking operators in GNNs. However, it does not address the issuc of redundant messages, as it continues to use the adjacency matrix. Our key contribution is the use of the non-backtraccing operator specifically to tackle the message redundancy issue. Please refer to Appendix A for a detailed comparison.
Initialization and Node-wise Aggregation of Messages. The message at the 0-th layer h is ini- tialized by encoding the node features Fs Fj, and the edge feature Gij using a non-linear function Φ After updating hidden features for each edge based on Equation (3), we apply a permutationninnaaiaan pooling over all the messages for graph-wiss wise predictions. Since we use hidden features for each edge, we construct the node-wise predictions at the final T--th layer as follows:
h = a (p 1 (.02::JEN(() (())
where a non-lincar aggregation function with different weights for incoming edges j i and outgoing edges i + i, is a non-linear aggregation function invariant to the permutation of nodes in Mii). We provide computation graph of NBA-GNN in Figure 3b to summarize algorithm.
Begrudgingly Backtracking Update. While the messages from our update are resistant to backtrack- ing, message A may get trapped in node i for the special case when Niii {z}. To resolve this issue, we introduce a simple trick coined begrudgingly backtracking update (Rappaport et al., 2017) that updates h ( using (t) only when N(i) = {i}. We empirically verify the effectiveness of begrudgingly backtracking updates in Section 5.3.
To better understand our NBA-GNN, we provide an example of non-backtracking passage-passingg updates with GCN backbone (Kipf & Welling, 2017), coined NBA-GCN. The message update at the f-th layer of NBA-GCN can be written as follows:
Implementation.
(NU)
((+1) (1) A J-i h + OGON
1 [G -1 w
Σ
(5)
KEN
5

---

Published in Transactions on Machine Learning Research (09/2024)
where OGNN is an element-wise nonlinear function, e.g., rectified linear unit (Agarap. 2018, ReLU), W( is the weight matrix, and messages are normalized by their number of neighbors [W(j)] 1.
4 Theoretical Analysis
In this section, we provide theoretical analysis of the proposed NBA-GNN framework. To be specific, we show that (a) our NBA-GNNs improve the upper bound for sensitivity- measures of GNN over- squashing and (b) NBA-GNNs can detect the underlying structure of SBMs even for very sparse graphs.
4.1 Sensitivity Analysis on Over-squashing
While Chen et al. (2018) initially introduced the non- bon-backtracking operator in GNNs, they did not explore its theoretical implications. Hence, we first analyze how NBA-GNNs alleviate the over-squashing issue. A well- known quantification to assess the over-squashing effect the sensitivity bound presented in Proposition 2, i.., the Jacobian of node-wise output for another initial node feature. Note that Topping et al. (2022) assumes the node features and hidden representations scalars for better understanding.
Proposition 2 (Sensitivity bounds). (Topping el al,, 2022) Assume MPNN defined in Equalion (1). Let two nodes i E V with distance T. If |ot [| I a and Vi S 3 for 0 S t < T, then the sensitivity bound can be defined as the following:
0hg Oz;
(a"))
(6)
where À denotes the degree-normalizer adjacency matrir.
Over-squashing occurs when the right-hand side of Equation (6) is too small, i.c. the hidden representation of node j becomes insensitive to the initial feature of node i (Topping al., 2022; Di Giovanni et al., 2023). To address this, we interpret the topology, i.e. the adjacency matrix, of the sensitivity bound in terms of the random walk that a GNN aligns with. In the following, we show that a non-backtracking random walk yields a higher sensitivity bound than simple random walks.
For our analysis, we bring the notation of bon-tacktrgcking matrix E {0, 1] and the incidence matrix C E R following Chen et al. (2018) to describe the cresaag-passsin of NBA-GNNs and node-wise aggregation via linear operation, respectively. To be specific, the backtracking matrix B and the incidence matrix C are defined as follows:
B(--R),000)) = {
11 i
(1
orj=iorkii
otherwise
otherwisc
We also define Dout and Din as the matrices representing out-degree and in-degree of NBA-GNNs, respec- tively, capturing the count of outgoing and incoming edges for each edge. These are diagonal matrices with (Dom)))-s)(--+)) Ei_, (()-)))(0-k) and (Din) the normalized non- nan-backtracking matrix augmented with self-loops: B = (Dout + +1 (B + I)Di + +)= Finally, we let Ć as the matrix where C(k-s)), = C(k-ss)i + C(j-b)). Then, one obtains the following sensitivity bound NBA-GNNs.
Ee B(e-)),(---)- Next, we introduce B as
Lemma (Sensitivity bounds of NBA-GNNs). Consider two nodes i,j E with random walk distance T given (T 1)-layer NBA-GNN as described in Equation (3) and Equation (4). Suppose | /V S a, [ Vpll2 B, and [|Vol S7 for 0 stt Then the following holds:
0h; dz, $ (a.3) (C B(T- (
We provide the proof in Appendix C. Lemma states how the over squsshigg effect is controlled by the power of B. Consequently, can infer that increasing the upper bound likely alleviates the over-squashing
6

---

Published in Transactions on Machine Learning Research (09/2024)
effect in GNNs (Topping et al., 2022; Black et al., 2023; Gutteridge et al., 2023) by reshaping the graph topology, i.e., the power of the adjacency matrix in the right-hand side of Equation (6). Additionally, the assumptions on nabla bounds are derived considering the Lipschitz constant of the non-linearity function and the maximum entry value across all weight matrices (Di Giovanni et al., 2023).
From this motivation, we provide an analysis to support our claim that the NBA-GNNs suffer less from the over-squashing effect due to its larger sensitivity bound. The key point is that the sensitivity bounds align with random walk, and the non- non-backtracking random walks result in larger sensitivity bound.
Proposition 3. Consider an MPNN defined as in Equation (1) and a (T 11-lyer NBA-GNN described by Equation (3) and Equation (4). For any pair of nodes i,j E V with distance T, the following inequality holds between sensitivity bounds:
(A) S (Č BTO
For d-regular graphs, BTB decays slower by O(d-"), while (as decays with O(dd+ 0((d+1) 1)-7)
We provide the full proof in Appendix C, based on comparing the degree- normalzee number of non- backtracking and simple walks from node i to node j. To the best of our knowledge, we are the first to compare the degree of over-squashing between GNNs aligned with different types of random walks. Hence, Proposition 3 indicates that NBA-GNNs has a larger sensitivity bound compared to conventional GNNs and suffers less from over-squashing, experimentally shown in Table 1 and Figures 4a and 4b. Moreover, for the sensitivity bound of d-regular graphs, consider the case of multiplying the power of B or A to a ono-hot vector. Since every entry is always identical and smaller in B, all entries from the resulting vector from the non-backtracking matrix will have larger values than those from the adjacency matrix.
4.2 Expressive Power of NBA-GNN on SBMs
In the literature on the expressive capabilities of GNNs, comparisons with the well-known k-WL test are common. However, since the k-WL test only focuses graph isomorphism, i.e. graph level tasks, it is inadequate for measuring the expressive power in node classification tasks. Furthermore, due to the substantial performance gap between the 1-WT, (equivalent to 2-WT.) and 3-WT, tests, many algorithms fall into the range between these two tests, making it more difficult to compare them with each other (Huang & Villar, 2021; Wang et al., 2023). It is also worth noting that comparing GNNs with the WL test does not always accurately reflect their performance on real-world datasets.
To address these issues, several studics have turned to spectral analysis of GNNs. From a spectral viewpoint, GNNs can be seen functions of the eigenvectors and eigenvalues of the given graph. NT & Maehara (2019) showed that GNNs operate as low-pass filters on the graph spectrum, and Balcilar et al. (2020) analyzed the use of various GNNs as filters to extract the relevant graph spectrum and mcasure their expressive power. Moreover, Oono & Suzuki (2020) argue that the expressive power of GNNs is influenced by the topological information contained in the graph spectrum.
The cigenvalues and the corrosponding adjacency matrix eigenvectors play pivotal role in establishing the fundamental limits of community detection in SBM, evidenced by Yun & Proutière (2019). The adjacency matrix exhibits a spectral separation property, and an eigenvector containing information about the assignments of the vertex community becomes apparent (Lei & Rinaldo, 2015). Furthermore, by analyzing the cigenvalues of the adjacency matrix, it is feasible to determine whether a graph originates from the Erdös Réndis-Rényi (ER) model or the SBM (Erdös et al., 2013; Avrachenkov al., 2015). However, these spectral properties are particularly salient when the average degree of the graph satisfics 2(log n). For graphs with average degrees o(logn), vertices with higher degrees predominate, affecting eigenvalues and complicating the discovery of the underlying structure of the graph Meenaych-George et al., 2019).
In contrast, the non-backtracking matrix exhibits several advantagcous properties, even for constant-degroe cases. In Stephan & Massoulié (2022), the non-backtracking matrix demonstrates a spectral separation property and establishes the presence of an eigenvector containing information about vertex community assignments, when the average degree only satisfics w(1) and n(()) Furthermore, Bordenave et al. (2015) have demonstrated that by inspecting the eigenvalues of the non- backtracking matrix, is possible to discern weether a graph originates from the ER model or the SBM, even when the graph's average degree remains
7

---

Published in Transactions on Machine Learning Research (09/2024)
Comparison conventional MPNNS and GNNs in the long-range graph benchmark, with and without Laplacian positional encoding (LapPE), We also denote the relative improvement by Impr.
Table 1:
coptides-fune
Peptides-struct
Pascal VOC-SP
Model
AP f
Impr.
MAE 4
Impr.
F1 1
Impr.
GCN
0.5930 0.0023
0.3496 = 0.0013
0.1268
0.0060
+ NBA
0.6951 0.0024
+17%
0.2656 = 0.0009
+22%
0.2537 + 0.0054
+100%
+ NBA+LapPE
0.7206 0.0028
+22%
0.2472 + 0.0008
+29%
0.3005 = 0.0010
+137%
GIN
0.5498 = 0.0079
0.3547 = 0.0045
0.1265 + 0.0076
+ NBA
0.6961 = 0.00455
+27%
0.2534 = 0.0025
+29%
0.3040 + 0.0119
+140%
+ UBA+LapPE
0.7071 + 0.0067
+29%
0.2424 + 0.0010
+32%
0.3223 = 0.0010
+155%
GatedGCN
0.5864 = 0.0077
0.3420 = 0.0013
0.2873 + 0.0219
+ NBA
0.6429 = 0.0062
+10%
0.2539 = 0.0011
+26%
0.3910 + 0.0010
+36%
+ NBA+L
0.6982 + 0.0014
+19
0.2466 = 0.0012
+28
0.3969 + 0.0027
+388%
constant. This capability enhances NBA-GNN's performance in both node and graph classification tasks, especially in sparse settings. These lines of reasoning lead to the formulation of the following propositions. Proposition 4. (Informal) Assume the uverage degree in the slochastic block model salisfies the condilions of being at least w() and n2(1), In such a scenario, NBA-GN GNN can map from graph G to node labels.
Proposition 5. (Informal) Suppose we have a pair of graphs with constant average degree, one generated from the stochastic block model and the other from the Erdös Rényi model. In this scenario, NBA-GNN is capable of distinguishing between them.
Proposition suggests that even if a given graph is too sparse to extract node class information using GNN with the adjacency matrix, NBA-GNN can still succossfully classify the nodes with probability approaching Similarly, Proposition extends this argument the graph classification problem. The rationale behind these valuable properties of NBA-GNNs in sparse scenarios lies in the fact that the non- backtracking matrix = exhibits similarity to the k-hop adjacency matrix, while A is mainly influenced by high-degrce vertices. This enables NBA-GNNs to extract valuable information from the spectrum of the con-backtrackingg matrix, aiding in the recovery of the hidden structure of the graph. For these reasons, NBA-GNNs would outperform traditional GNNs in both node and graph classification tasks, particularly in sparse graph environments. These propositions integrate prior work on the non-backtracking matrix into GNNs, contributing to deeper understanding of the expressive power within GNN structures. Such an approach has the potential to advance the field by introducing the GNN framework. For in-depth exploration of this argument, please refer to Appendix D.
perspectives and methodologies within
5 Experiment
In this section, assess the effectiveness of NBA-GNNs across multiple benchmarks graph classification, graph regression, and node classification lasks! Additionally, we conduct a detailed comparison, including complexity analysis, with existing methods aiming to reduce redundancy (see Appendix A). Detailed experimental information also provided in Appendix E.
5.1 Long-Range Graph Benchmark
The long-range graph benchmark (Dwivedi et al., 2022, LRGB) considers a set of tasks that require learn- ing long-range interactions. We validate our method using three datasets from the LRGB benchmark: Peptides-func (graph classification), Peptides-struct (graph regression). and PascalVOC-SP (node classi- fication). We adopt performance scores from Dwivedi al. (2022) for GNNs and from each bascline paper:
The code is available

---

Published in Transactions on Machine Learning Research (09/2024)
Table 2: Evaluation of NBA-GNN on LRGB. The first-, second- and third-best results are colored. Scores
within a standard deviation of one another considered equal. Non-reported values are denoted by
Peptides-func Peptides-struct AP
B0c-alVOC-SP
Method
Model
MAE |
F1 1
GCN
0.5930 4 0.0023
0.3496
0.1268
0.0060
GCN+ LapPEE
0.6213 # 0.0080
0.3250 + 0.0180
0.1370
0.0077
GNNs
GIN
0.5498 + 0.0079
0.3547
0.0045
0.1265 = 0.0076
GIN+LapPE
0,5877 # 0.0014
0.3369
0.0026
0.1302
0.0105
GatedGCN
0.5864 +: 0.0077
0.3420 + 0.0013
0.2873
0.0219
GatedGGCNLapPE
0.6069 = 0.0085
0.3357
0.0006
0,2860
0.0085
MixHop-GCN
0.6592 #: 0.0036
0.2921
0.0023
0.2506 = 0.0174
MixHop-GCN
0.6843 = 0.0049
0.2614 + 0,0023
0.2218
Subgraph GNNs
PathNN
0.6816 = 0.0026
0.2545
0.0032
CIN++
0,6569 + 0.0117
0.2523 0.0013
Thansformerr
0.6326 = 0.U1
0.2529 0.0016
0.2694
0.0038
GraphGPS+LapPE
0.6535 = 0.0011
0.2500 + 0.0005
0.3748
0.0109
Transformers
SAN+LappE
0.6384 +: 0.0121
0.2683
0.0043
0.3230 = 0.0039
Exphormer
0,6527 = 0.0013
0.2481
0.0007
0.3966 = 0.0027
Graph MLP-Mixer/ViI
0.6970 +: 0.0090
0.2449
4: 0.0016
0.6469 +: 0.0019
0.3173
0.0007
0.2824
0.0039
DIGL+MPNN-
0.6830 = 0.0026
0.2616
0.0018
0.2921
0.0038
Graph Rewiring
ORew-GCN-Laple
0.7150 = 0.0044
0.2536
+: 0.0015
0.1851
0.0092
0.7126 = 0.0045
0.2606
0.0014
0.2692 = 0.0059
DRew:GatedGGN-LappP
0.6977 = 0.0026
0,2539
0.0007
0.3314
0.0024
State Space Models
Graph-Mamba
0.6739 + 0.0087
0.2478
0.0016
0.4191
0.0126
NBA-GCN
0.6951 = 0.0024
0.2656
0.0009
0,2537
0.0054
LLpPE
0.7207 = 0.0028
0.2472 +: 0.0008
0,3005
0.0010
NBA-GNNs (Ours)
NBA-GIN
0.6961 + 0.0045
0.2775
0.0057
= 0.3040
NBAPG
0.7071 = 0.0067
0.2424 + 0.0010
0.3223
0.0063
NBA-GatedGCN
0.6429 +: 0.0082
0,2539
0.0011
0.3910 : 0.0010
NBA-GatedGGCN+HappP
0.6982 + 0.0014
0.2466
0.0012
0.3969
0.0027
subgraph based GNNs (Abu-El-Haija et al., 2019; Michel et al., 2023; Giusti et al., 2023), graph Trans- formers (Kreuzer et al., 2021; Rampášek et al., 2022; Shirzad et al., 2023; He et al., 2023), graph rewiring methods (Gasteiger et al., 2019; Gutteridge et al., 2023), and state space model (Wang et al., 2024). For NBA-GNNs and NBA-GNNs with begrudgingly backtracking, we report the one with better performance. Furthermore, LapPE, i.c., Laplacian positional encoding (Dwivedi et al., 2023), is applicd as it onhances the performance of NBA-GNNs in common cases.
As one can see in Table 1, NBA-GNNs show improvement regardless of the combined backbone GNNs, i.e., GCN (Kipf & Welling, 2017), GIN (Xu et al., 2019), and GatedGCN (Bresson & Laurent, 2018), aligning with our results in Proposition 3. Specifically, NBA-GCN outperforms GaledGCN, (i) confirming that simply updating both node and edge features does not lead to performance improvement and (ii) showing that non- backtracking is key component for solving long-range interaction tasks. Furthermore, when compared to a variety of recent baselines in Table 2, at least one NBA-GNN shows competitive performance with the best baseline, except for the state space model for PascalVDC-SP. is also noteworthy that the improvement of NBA-GNNG is higher in dense graphs, where PascalVOC-SP has an average degree of while Peptides-fum and Peptides-struct have an average degree of 2.
5.2 Transductive Node Classification Tasks
To validate the effectiveness of non-backtracking in transductive node classification tasks, we conduct exper- iments on three citation networks (Cora, CiteSeer, and Pubmed) (Sen al., 2008) and three heterophilic
9

---

Published in Transactions on Machine Learning Research (09/2024)
Table 3: Comparison of GNNs and their NBA-GNN counterpart on transductive node classification tasks
for citation networks and heterophilic datasets, with and without Laplacian positional encoding (LapPE). We mark the best numbers in bold.
Model
Cora
CiteSeer
PubKed
Texas
Wisconsin
Cornell
GCN
0.0058
0.7532
0.8825=0000422
0.6162 00.0344
0.6059
0.591640.00022
LapPE
0.8592:10.008
0.7572:0.0132
0.881710.0040
0.6216:0.068 0584
0.6000
0.570310.0547
+ NBA
0.8722+0.0096
0.7585=to.0176
0.8826=0.0044
0.7108=0.0pm
0.7471=0.0386
0.6108+000014
LBp-L
0.8720=2.0129
0.7609:0.0188
0.8827=0.0048
0.6811 10,005
0.7471=0.0468
0.6378:200317
GraphSAGE
0.8632:10.0158
0.7559:1.0161
0.8864:10.0030
0.7108
0.7706:10.0400
0.6027:10.625
LapPE
0..100=0.0011
0.7608:2..144
0.8895=20.0047
0.7162
0.76417+0000553
0.618940.0484
+ NBA
0.8702#0.0083
0.7586:to.0213
0.8871#0.0044
0.7270=000000:
0.7765=0.0000
0.6:159=0.0691
LBA-LapPE
0.865020.0120
0..021:0.0172
0.887020.0037
0.7486=0.0611
0.7647:0.0631
0.6378:0.0514
GAT
0.869420.0119
0.706311.0119
0.808710.0046
0.6054:10.088 0338
0,6000
0.4757:10.061
LapPE
0.868620.0152
0.7512:t0.0144
0.8075#0.0045
0.6135
0.6294
0.5108++0.0600
+ NBA
0.872210.0120
0.7549::0.0171
0..029
0.6622:10.014
0.705911.0008
0.5838:20.0556
+ NBA LapPE
0.8692#0.0009
0.7561 #0.0176
0.8822+0.0047
0.6730=0.0345
0.7314=0.0631
0.5781++0.0640
ChebNet
0.8023=1.01100
0.7090
0,8718:000028
0.681110.0555
0.709810.0822
0.6473110.020
LapPE
0..031#0.0199
0.739
0.8701#0.0047
0.6324+0.0000
0.6941
0.6527+0.0506
+ NBA
0.882310.0158
0.7379:10.0099
0.8832:000062
0.7568
0.7490=00.067/
0.6973:0.0483
NBA++apPP
0.8095=0.0211
0.7421
0.8821+0.007
0.72-13
0.7451 +0.00008
0.6757+00.0634
Table 4: Comparison of NBA-GNN architectures and edge representation updating GNN architectures on
transductive node classification tasks. We mark the best numbers in bold.
Model
Cora
CiteSeer
PubMed
Texas
Wisconsin
Cornell
NBA-GON
0.8722:20.0 0095
0.758522.0117
0.8826220.004
0.7108=0.0796
0.7471 1:0 0386
0.6108
NBA-Graphee IBB-GrrphSAAGE
0.8702
0.7586
0.8871 =0.0044
0.0970
0.7765
0.6459
NBA-GAT
0.8722=0.0120
0.75419
0.8829#0.0043
0.6622=0.0014
0.7059
0.5838
GatedGCN
0.8477=0.0166
0.7325
0.867 18671#0.0000
0.6108=0.0652
0.062440.0641
0.5216
EGNN
0.876910.0125
0.7507 0221
0.8769
0.6595=0.0522
0.678410.omg
0.5946
CensNet
0.864822.0088
0.751610.0162
0.8053:10.0076
0.6405=00.010
0..608-10.0163
0.616211.0707
datasets (Texas, Wisconsin, and Cornell) (Pei et al., 2019). We use three conventional GNN architectures GCN (Kipf & Welling, 2017), GraphSAGF. (Hamilton et al., 2017), and GAT (Veličković et al., 2018) and one spectral GNN architecture, ChebNet (Defferrard et al., 2016), as the backbone of NBA-GNN in Ta- ble 3. The results indicate that the non-backtracking update improves the performance of all GNN variants. Furthermore, Table 3 shows significant enhancements in heterophilic datasets. Given that related nodes in heterophilic graphs are often widely separated (Zheng et al., 2022), the ability of NBA-GNN to alleviate over-squshhing plays vital role in classifying nodes in such scenarios.
5.3 Ablation Studies
In this section, conduct ablation studies to empirically verify our framework. For simplicity, we use BA for backtracking GNNs and BG for begrudgingly backtracking GNNs. All experiments are averaged over 3 seeds, and ceper-parraeters for GCN from Tönshoff et al. (2023) are used for a fair comparison.
Non-backtracking vs. Backtracking. We first verify whether the performance improvements indeed stem from the non-backtracking updates. To this end, we compare our NBA-GNN with a backtracking variant, coined BA-GNN. To be clear, BA-GNN allows backtracking update prohibited in NBA-GNN, i.e., using (.) to update (e+1) in Equation (3). From Figures 4a and 4b, NBA-GCN consistently outper- forms the BA-GCN and GCN regardless of the number of layers, aligning with the results of Proposition Intriguingly, one can also observe that. BA-GCN outperforms the naïve backbone, i.e., GCN, consistently.
10

---

Published in Transactions on Machine Learning Research (09/2024)
0.32
0.73
0.3009
0.7207
AP
MAE 4
0.28
Model
BG
0.2591
scooee
0.70
0.7015
0.2472
GCN
0.2068
0.7207
0.2547
0.20
0.16
NBA-9Ch
0.67
GIN
X
0.7071
0.6825
0.2424
0.2479
6
8
10
12
10
15
20
GatedGCN
0.6710
0.2466
Number of layers
Number layers
0.6982
0.2489
(a) F1 changes in number of layers in PascalVOC-SP
(b) for changes in number lay-
(c) Performance of begrudgingly, non-
ers in Peptides-func
backtracking in sparse graphs
Figure 4: Ablation studies on the components of NBA-GNN.
Table 5: Training time and memory usage on the large datasets for the transductive node classification task.
Datasets
Model
Time (8)
Param, (K)
Memory (MiB)
Model
Time (s)
Param. (K)
Memory (MiB)
GCN
12.22
2317
24.01
GCN NBA
3051
158.86
Cora
SAGE
10.74
3104
27.01
SAGE NBA
47.07
3837
161.86
GAT
17.72
3130
27.21
GAT +NBA
58.20
3864
162.06
GCN
15.74
3479
60.08
GCN+NBA
52.44
5375
373.36
CiteSeer
SAGE
14.95
4265
63.68
SAGE NBA
59.94
6161
376.36
GAT
19.68
4292
63.87
GAT NNBA
66.92
6188
376.56
GCN
42.66
1838
47.9
GCN+NBA
242.66
2094
436.9
PubMed
SAGE
56.10
2624
50.9
SAGE-NBA
320.92
2880
439.9
GAT
64.80
2650
51.0
GAT+NBA
416.85
2906
440.0
Begrudgingly Backtracking Updates in Sparse Graphs. Additionally in Figure 4c, we investigate the effect of begrudgingly backtracking in sparse graphs, i.e., Peptides-func, and Peptides-struct. One can see that begrudgingly backtracking is effective in Peptides-fune and shows similar performance in Peptides-struct (Note that the PascalVOC-SP does not have a vertex with degree onc).
Non-backtracking Edge Features Updates. From another point of view, NBA-GNN can be in- terpreted as an architecture only updating edge-wise features using backbone GNN layers. Therefore, we conduct additional experiments validate that the performance improvement truly comes from non- backtracking rather than updating edge features in Table 3. We consider three GNN architectures that also update edge features: GatedGCN (Bresson & Laurent, 2018), EGNN (Gong & Cheng, 2019), and CensNet (Jiang et al., 2020). As seen in Table 4, NBA-GNN outperforms these models most datascts, showing the efTectiveness of non-backtracking over edge feature updales. It is noteworthy that NBA-GNN only updates edge features derived from initial node features, while FGNN and CensNet update both node and edge features from initial node and edge features. We report detailed implementation in Appendix E.3.3.
5.4 Complexity analysis
In this section, analyze the space and time complexity of some basclines and NBA-GNN, All experiments were conducted single RTX 3090.
Space Complexity. NBA-GNNs generate messages for each edge considering directions and pass these messages in a non- non-backtracking matter. This process requires 2|E] messages, and (dazg - E) connections among messages where davg is the average degree of the graph. Although this may seem substantial, it has not been a bottleneck in practice and can mitigated by adjusting the batch size. Moreover, this is DRew, which requires computation over k-hop neighbors (with k being the number of layers). We report the memory usage for the transductive node classification task in Table 5 and the LRGB task in Table 6 (DRew and PathNN could not fit into single GPU due to
relatively less computation compared
11

---

Published in Transactions on Machine Learning Research (09/2024)
Table 6: Average test time (s) per epoch and memory usage for Peptides-func, Peptides-struct,
PascalVOC-SP dataset. Parenthesis refers to the batch size, and the best performance for each dataset is highlighted in bold.
Metric
Dataset
PathNN-SP
PathNN-SP-
PachNN-AP
GraphGPS+LapPE
DRew-GCN+LapPP
NBA-GCN-LapP
Peptidon-
OOM (128)
OOM (128)
OOM (128)
89.70% (128)
46.82% (128)
18.86% (128)
Memory
Peptides-struct
0OM (128)
0OM (128)
0OM (128)
88.08% (128)
46.82% (128)
16.98% (128)
PaacalVOC-SP
N/A
N/A
N/A
45.64% (32)
0OM (32)
47.30% (32)
Peptidee-fune
3.319 (64)
3.158 (61)
5.977 (61)
0.639 (128)
0,933 (128)
0.541 (200)
Test time (8)
Peptides-atruch
2.120 (64)
1.177 (64)
1.372 (61)
0.926 (128)
1.053 (128)
0.532 (128)
PascalVOC-SP
N/A
N/A
N/A
1.307 (32)
6.468 (20)
5.868 (30)
Table 7: Comparison on theoretical and practical time complexity for preprocessing Peptides-fune dataset.
Model
REGNN PathNN-SP
DRew NBA-GNN
Theoretical time complexity
MII/VV - h 1/!
[V] * b
Σ i |1]
dang * |1]
Practical computation time (s)
N/A
666
123
68
memory overflow for PascalVOC-SP). NBA-GNN shows less memory usage compared to graph Transformer architectures, although it consumes more memory than MPNNs.
Time Complexity. We also report the average test time per epoch for LRGB in Table 6. Every experiment has been conducted with the largest batch size that fits the GPU. NBA-GNN shows competitive time compared to other baselines, though it does suffer in graphs with high average degree.
Preprocessing Time Complexity. Finally, we investigate the time complexity of preprocessing in REGNN (Chen et al., 2022), PathNN-SP (Michel et al., 2023), DRew (Gutteridge et al., 2023), and NBA- GNN on the Peptides-fune datasct. To be specific, RFGNN requires k-depth non-rodundant tree, PathNN- SP needs the single shortest path between nodes, and DRew demands the k-hop neighbors information. ABA-GNN requires the computation of the non- non-backtracking edge adjacency, which can be computed in O(EE)), even (E if the data is provided in the form of an adjacency list. We denote as the branch- ing factor, k as the number of layers, and daeg as the average degree of nodes in graph. Inevitably, previous works are dependent on the number of layers, while NBA-GNN remains irrelevant to the number of lay- ers. In Table 7, one can see that NBA-GNN shows superiority in both theoretical time complexity and practical computation time (RFGNN codes were not reported by the authors).
6 Conclusion
We have introduced message-passing framework applicable to any GNN architectures to alleviate over- squashing. As theoretically shown, NBA-GNNs mitigate wvusshiu in terms of sensitivity and enhance their expressive power for both node and graph classification tasks on SBMs. Additionally, have demon- strated that NBA-GNNs achieve competitive performance the LRGB benchmark, and show improvements over conventional GNNs across transductive node classification tasks, even in heterophilic, datasets.
Acknowledgements
S. Park and S. Ahn were supported by Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korca government (MSIT) (No. RS-2019-I111106, Artificial Intelligence Graduate School Progran(PSTTCCH) the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 2022RIC1C111366)) and Basic Science Research Program through the National Rescarch Foundation of Korea (NRF) funded by the Ministry Educa- tion
N. Ryu and S. Yun were supported by Institute of Information & com- munications Technology Planning & Evaluation (ITTP) grant funded by the Korea, government (MSIT)
12

---

Published in Transactions on Machine Learning Research (09/2024)
(No.2019-0-00075, Artificial Intelligence Graduate School Program (KAIST), 10%) and the Institute of In- formation & communications Technology Planning & Evaluation (TTTP) grant funded by the Korea govern- ment (MSIT) (No. 2022-0-00871, Development of Al Autonomy and Knowledge Enhancement for Al Agent Collaboration, 90%).
We thank Soo Yong Lee, Seongsu Kim, Hyosoon Jang, Yunhui Jang, Juwon Hwang, Hyomin Kim, for their valuable comments and suggestions in preparing the early version of the manuscript.
Bibliography
Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):6446-6633 2017.
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyun- yan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning, pp. 21-29. PMLR, 2019.
Abien Fred Agarap. Deep learning using rectified linear units (relu). arXiv preprint Xiv: 803. 08375, 2018.
Noga Alon, Itai Benjamini, Eyal Lubelzky, and Sasha Sodin. Non-backtracking random walks mix faster. Communications in Contemporary Mothematics, 9(04):585-608 603, 2007.
Cri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
Konstantin Avrachenkov, Laura Cottatellucci, and Arun Kadavankandy. Spectral properties of random matrices for stochastic block model. In 2015 13th International Symposium on Modeling and Optimization in Mobile, Ad Hoe, and Wireless Networks (WiOpt), pp. 537 544. IEEE, 2015.
Furqan Aziz, Richard C Wilson, and Edwin R Hancock. Backtrackless walks graph. IEEE transactions on neural nelworks and learning systems, 24(6):977 989, 2013.
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine, Analyzing the expressive power of graph neural networks in spectral perspective. In International Conference Learning Representations, 2020.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Effects of graph convolutions in multi-layer networks. Tn The Fleventh International Conference Learning Representations, 2023.
Florent. Benaych-George Charles Bordenave, and Antti Knowles. Largest eigenvalues sparse inhomoge- neous erdös-rényi graphs. The Annals of Probability, 47(3):1653 1676, 2019.
Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. Understanding oversquashing in gnns through the lens of effective resistance, In International Conference on Machine Learning, pp. 2528 2547.
PMLR, 2023.
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. IEFE, 2015.
Xavier Bresson and Thomas Laurent. Residual gated graph convnets. In International Conference on Learning Representations, 2018.
Joan Bruna and X Li. Community detection with graph neural networks. stat, 1050:27, 2017.
Rongqin Chen, Shenghui Zhang, Ye Li, al. Redundancy-fre message passing for graph neural networks. Aduances in Neural Information Processing Systems, 35:4316-4323 2022.
Zhengdao Chen, Lisha Li, and Joan Bruna. Supervised community detection with line graph neural networks. In International Conference on Learning Representations, 2018.
13

---

Published in Transactions on Machine Learning Research (09/2024)
Michaöl Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. Aduances in neural informalion processing systems, 29, 2016.
Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M Bronstein. On over-squashing in message passing neural networks: The impact of width, depth, and topology. Tn International Conference on Machine Learning, pp. 7865-7885. PMLR, 2023.
Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Advances in Neural Information Processing Systems, 2022.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43): 2023.
László Erdős, Antti Knowles, Horng-Tzer Tzer Yau, and Jun Yin. Spectral statistics of erdös rényi graphs i: Local semicircle law. The Anmals of Probability, pp. 2279-2375, 2013.
Dario Fasino, Arianna Tonetto, and Francesco Tudisco. Hitting times for second-order random walks. Eu- ropean Journal of Applied Mathematics, 34(4):642-666, 2023.
Robert Fitzner and Remco van der Hofstad. Non-backtracking random walk. Journal of Statistical Physics, 150:264 284, 2013.
Kimon Fountoulakis, Amit Levi, Shenghao Yang, Ascem Baranwal, and Aukosh Jagannath. Graph attention retrospective. Journal of Machine Learning Research, 24(246):1-52, 2023.
Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. Advances in neural information processing systems, 32, 2019.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1272- PMT.R, 2017.
Lorenzo Giusti, Toodora Ren, Francesco Coccarelli, Cristian Bodnar, and Pietro Liò. Cin Enhancing topological message passing. arXiv preprint 3rXic:2306.0355 2023.
Liyu Gong and Qiang Cheng, Exploiting edge features for graph neural networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognation, pp. 9211-9219, 2019.
Benjamin Gutteridge, Xiaowen Dong. Michael M Bronstein, and Francesco Di Giovanni. Drew: Dynamically rewired message passing with delay. In International Conference on Machine Learning, pp. 12252-12 12267. PMLR, 2023.
Will Hamilton, Zhitao Ying, and Jure Leskovec, Inductive representation learning on large graphs. NeurIPS, 30, 2017.
Xiaoxin He, Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, and Xavier Bresson. A generalization of vit mit/mlp-mixer to graphs. In International Conference on Machine Learning, pp. 12724-12745. PMLR, 2023.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-133) 1983.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. Advances in neural information processing systems, 33:22118 22133, 2020.
Weihua Hu, Matthias Fcy, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovee. Ogb-Isc: A largo-scale challenge for machine learning on graphs. In Thirty- Conference on Neural Information Processing Systems Dalasets and Benchmarks Track (Round 2), 2021.
14

---

Published in Transactions on Machine Learning Research (09/2024)
Ningyuan Teresa Huang and Soledad Villar. A short tutorial on the weisfeiler-lchman test and its variants. In TCASSP 2021-2021 TEFE International Conference on Acoustics, Speech and Signal Processing (TCASSP), pp. 8533 8537. IEEE, 2021.
Xiaodong Jiang, Ronghang Zhu, Sheng Li, and Pengsheng Ji. Co-embedding of nodes and edges with graph neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
Charilaos 1. Kanatsoulis and Alejandro Ribeiro. Representation power of graph neural networks: Improved expressivity via algebraic analysis, 2023.
Mark Condie Kempton. Non-backtraccing random walks and weighted ihara's theorem. Open Journal of Discrete Mathematics, 2016.
JinHyung Kim and Judea Pearl. computational model for causal and diagnostic reasoning in inference systems. In International Joint Conference on Artificial Intelligence, pp. 0, 1983.
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral atlention. Advances in Neural Information Processing Systems, 34: 21618-21629, 2021.
Florent. Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Leuka Zdeborová, and Pan Zhang. Spectral redemption in clustering sparse networks. Proceedings of the National Academy of Sci- ences, (10(5)):20935 20940,, 2013.
Jing Lei and Alessandro Rinaldo. Consistency of spectral clustering in stochastic block models. The Annals of Statistics, pp. 215-237, 2015.
Yuan Lin and Zhongzhi Zhang. Non-backtracking centrality based random walk networks. The Computer Journal, 62(1):63 80, 2019.
llya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2018.
Pierre Mahé, Nobuhisa Ueda, Tatsuya Akutsu, Jean-Luc Perret, and Jean-Philippe Vert. Extensions of marginalized graph kernels. In Proceedings of the twenty- first international conference on Mochine learning. pp. 70, 2004.
Gaspard Michel, Giannis Nikolentzos, Johannes Lutzeyer, and Michalis Vazirgiannis. Path neural networks: Expressive and accurate graph neural networks. In International Conference on Machine Learning, pp. 24737 24755. PMLR, 2023.
Kevin Murphy, Yair Weiss, and Michael Jordan. Loopy belief propagation for approximate inference: an empirical study. In Proceedings of the Fifteenth conference on Uncertointy in artificial intelligence, pp. 467-475, 1999.
MEJ Newman. Spectral community detection in sparse networks. arXiv preprint arXiv:1308.663: 2013.
Hoang NT and Takanori Machara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprinl ar exii::905.00550 2019.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classifi- cation. In International Conference on Learning Representations, 2020.
Judea Pearl. Reverend bayes on inference engines: A distributed hicrarchical approach. In Proceedings of the AAAI conference artificial intelligence, pp. 133-136, 1982.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In International Conference on Learning Representations, 2019.
15

---

Published in Transactions on Machine Learning Research (09/2024)
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 15:14501-14515 2022.
Brian Rappaport, Anuththari Gamage, and Shuchin Aeron. Faster clustering via. non-backtracking random walks. stat, 1050:26, 2017.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collec- tive classification in network data. AI magazine, 29(3):33-93, 2008.
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop. Ex- phormer: Sparse transformers for graphs. In International Conference on Machine Learning, 2023.
Ludovic Stephan and Laurent Massoulié. Non-backtracking spectra of weighted inhomogeneous random graphs. Mathemalical Statistics and Learning, 5(3):201-277) 2022.
Jan TönsholI, Martin Ritzert, Eran Rosenbluth, and Martin Grohe Where did the gap go? reassessing the long-range graph benchmark. In The Second Learning on Graphs Conference, 2023.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bron- stein. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2022.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph allention networks. In International Conference on Learning Representations, 2018.
Chloc Wang, Oleksii Tsepa, Jun Ma, and Bo Wang. Graph-mamba: Towards long-range graph sequence modeling with selective state spaces. arXiv preprint arXiv:2402.00789, 2024.
Qing Wang, Dillon Chen, Asiri Wijesinghe, Shouheng Li, and Muhammad Farhan. N-wl: new hier- archy of expressivity for graph neural networks. In The Eleventh International Conference on Learning Representations, 2023.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How powerful are graph neural networks? International Conference on Leurning Representations, 2019.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40-48. PMLR, 2016.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yo Yan Liu. Do transformers really perform badly for graph representation? Advances in Newral Information Processing Systems, 34:28877-28888, 2021.
Se- Young Yun and Alexandre Proutière. Optimal cluster recovery in the labeled stochastic block model. Advances in Neural Information Processing Systems, 29, 2016.
Se- Young Yun and Alexandre Proutière. Optimal sampling and clustering in the stochastic block model. Advances in Neural Information Processing Systems, 32, 2019.
Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. Graph neural networks for graphs with heterophily: A survey. arXio preprint arXiv:2202.071 07082, 2022.
16

---

Published in Transactions on Machine Learning Research (09/2024)
Appendix
Appendix
17
A Comparison with Related Works
18
A.1 Line Graph Neural Networks
18
A.2 Redundancy-free Graph Neural Network
18
A.3 Stochastic Block Models
B Proofs for Section 3.1
20
B.1 Preliminaries
................................
20
B.2 Access Time of Simple Random Walks
................................
21
B.3 Access Time of Begrudgingly Backtracking Random Walks
23
B.4 Proof of Proposition
28
C Proofs for Section 4.1
29
C.1 Preliminaries
29
C.2 Proof of Lemma
29
C.3 Proof of Proposition
31
D Proofs for Section 4.2
32
D.1 Proof of Proposition 4
32
D.2 Proof of Proposition
33
D.3 Proof of Lemma 8
33
D.4 Proof of Lemma
34
E Experiment Details
37
E.1 Implementation
................................
37
E.2 Long-Range Graph Benchmark
38
E.3 Transductive Node Classification
39
17

---

Published in Transactions on Machine Learning Research (09/2024)
A
Comparison with Related Works
This section delves into the detailed exploration of key related works, highlighting essential distinctions from our NBA-GNN. In addition, we present simple experiments to prove the superiority of our model.
A.1 Line Graph Neural Networks
Line Graph Neural Networks (LGNN) (Chen et al., 2018) were the pioneers in applying the non- con-backtracking operator to GNNs. However, it docs not resolve redundancy issues, it employs both an adjacency matrix and non-backtracking matrix in layer. In other words, our main contribution over LGNN is in consideration of the non-backtracking operator specifically for the message redundancy problem, in end-to-end manner. Notably, the computational complexity of LGNN is acknowledged to be close to [V] Iog((V) by its authors.
Table Comparison of LGNN and NBA-GCN on Peptides-func.
Model
Training AP f
Test AP
Test time per epoch (s) 4
GPU usage (%) 4
LGNN
0.4202
0.3778
87. $7.761
97.10
NBA-GCN
0.9724
0.7207
0.541
51.18
In our experiments on Peptides-func, compare the performance and complexity of LGNN and NBA- GCN+LapPE, as detailed in Table 8. Given that LGNN was initially proposed using only node degrees for node features, we incorporated an additional node feature encoder, similar to our NBA-GNN setup. Specifically, we used a batch size of 64, hidden dimension of 24, and 4 layers for LGNN. Refer to Appendix E.2 for the hyperparameters of NBA-GCN. The drawbacks of L.GNN terms of time and space complexity become evident when compared to NBA-GNN, while requiring space and time for computing both simple random walks and non-backtracking walks, but result in poor performance.
A.2 Redundancy-free Graph Neural Network
Redundancy-Free Graph Neural Network (RFGNN) (Chen et al., 2022) shares the common motivation with NBA-GNN, aiming to reduce redundant messages in the computation graph. RFGNN achieves this by constructing tree for every node, coined Truncated ePath Tree (TPT). TPT ensures that there are no repeated nodes along the simple path from the root to the leaf, except for the root node which can appear twice in the path. This approach differs significantly from NBA-GNN, which eliminates redundancy by identifying non-backtracking edge adjacency.
In terms of complexity, REGNN known to have space and time complexity of O ( (IV--11) where [V] the number of nodes and is the number of GNN layers. In contrast, NBA-GNN achieves superior complexity with space complexity O(2)E)) and time complexity O(davy El), which remains irrelevant to the number of layers. The preprocessing process time complexity, involved in finding non-backtracking edge adjacency, is ((E This scalability allows NBA-GNN to handle larger graph dataset compared to RFGNN. Furthermore, in theoretical aspects, our work distinguishes itself by providing the sensitivity upper bound of non- bonktacktra updates, rather than comparing the relative inference of paths.
Table 9: Average test accuracy of LGNN, NBA-GNN and BP on two sparse SBMs, where n represents the number of vertices, C' is the number of classes, and p and denote edge probabilities within and across communities, respectively.
Parameters (n, C, C.p.)
Model
LGNN
NBA-GNN
BP
(a) Binary assortative SBM
(400, 2, 20/n, 10/n) (400, 5, 0, 18/n)
0.4885
0.4900
0.5303
(b) 5-community dissociative SBM
0.1821
0.1888
0.2869
18

---

Published in Transactions on Machine Learning Research (09/2024)
A.3 Stochastic Block Models
We also conduct comparative analysis for our method on two sparse Stochastic Block Models (SBMs) with distinct parameters for Belief propagation (BP), and LGNN: (a) a binary assortative SBM (n = 400, == 2, p = 20/n, = 10/n), and (b) a 5-community dissociative SBM (n = 400, = 5, p = 0, 18/n). To be specific, n denotes the number vertices, C denotes the number of classes, and and q denote edge probabilities within and across communities, respectively. Table 9 illustrates the average test accuracy across 100 graphs. Notably, BP, known for achieving the information-theortiic threshold, exhibited the best performance, consistent with expectations. Additionally, NBA-GNN outperforms LGNN in both scenarios.
19

---

Published in Transactions on Machine Learning Research (09/2024)
B Proofs for Section 3.1
In this section, present the findings discussed in Section 3.1. Similar to Di Giovanni et al. (2023), we concentrate on the relationship between over-squashing and access time of non non-backtracking random walks. Our study establishes that the access time using a begrudgingly backtracking random walk (BBRW) is smaller than that simple random walk (SRW) between two nodes, in tree graphs. Also, it is noteworthy that the gap between these two access times increases as the length the walk grows.
In the following, will compare the access times between BBRW and SRW. First, show that the tree graph, the access time equals the sum of access times between neighboring nodes. Note that the access time belween neighboring nodes, which is the cut-point, can be represented in terms of return time. The formulas for return time in Fasino et al. (2023) and Lemma 6 allow us to derive the formulas for access time between neighboring nodes. Finally, we derive and compare the access time of BBRW and SRW, i.c., Proposition
Proposition 1. Given tree G (V,)) and paär of nodes i.j E V, the access time of begrudgingly backlrucking random walk is equal to or smaller than that of a simple random walk. The equalily holds if and only if the walk length I.
B.1 Preliminaries
B.1.1 Simple and Begrudgingly Random Walks
A random walk on a graph = (V is a sequence V-valued random variable xo, X1, X2... where X is chosen randomly from neighborhood of x,. Different types of random walks have different probabilities for selecting neighboring nodes.
Simple random walk (SRW) choose next node j uniformly from the neighbors of current node d:
f J/b if (i,j) e
P(x.+1 = j(x, =t) =
otherwise
On the other hand, begrudgingly backtracking random walk (BBRW) trics to avoid the previous node when there is another option:
when (i,h) E E,, k and (WG) \ (i) 2
P(xn+2 = M|xn+1 = ji i)
when (i,h) E E and (WG) \ (i) =
0
otherwise
B.1.2 Access Time
Consider SRW starting at a node i E V. Let T3 denote the time when a SRW first arrived at node i, T, == min (n 2 0)x,, = i), and T, be the time when a random walk first arrived at node after the first step, T; == min(n > 0|x, = i}. With slight abuse of notation, we define access time t(i,j) from i to j, access time t(i + j. k) from to k where X1 = j. and return time t(i; 9) in graph & follows:
t(i,j) [T X = i]
t(i + j.k) E[T X1 j.xo i]
t(tg) = T X2 =
Similarly, we denote the access time from i to j, access time from i to k with where Xı =j and return time of BBRW as E(i.j), E(i + j, k) and E(i;)), respectively. Note that the first step of BBRW shows the same behavior as the SRW since there is no previous node on the first step.
Finally, for a tree graph G and pair of nodes i,j in Proposition 1, we denote the unique paths between and as (Vo.-..,,p) UN) with i Un- uN- We also let N denote the distance between the nodes and
20

---

Published in Transactions on Machine Learning Research (09/2024)
B.2 Access Time of Simple Random Walks
In this section, derive the access time of simple random walks (SRW) on tree graphs between two nodes and j, i..,, j(,,j). To be specific, we show this in the following process.
We decompose the access time for two nodes and j into a summation of the access time of neigh- boring nodes in the path, i.c., t(Un, ux+1) for n E O,
(Appendix B.2.1 and Lemma 2).
We evaluate the access time of neighboring nodes in the path, e-g., t(Un, Un+ 1), using the number of edges in graph (Appendix B.2.2 and Lemma 3).
3. We formulate the access time of simple random walks (SRW) between two nodes i and j. i.e., t(i,)) (Appendix B.2.3 and Proposition 6).
B.2.1 Decomposition of Access Time
First, we show that the access time is equal to the sum of access times between neighboring nodes. When a random walker travels from to UN, it must pass through all nodes on the paths. Intuitively, We can consider the entire time taken as the summation of the time intervals between when the walker arrived at Un and when it arrived at vn+i-
Lemma 2. Given a free G and path (Vo....,,N,,
N-1 Σ
t(vo, uN)
t(Ung Un+1)
Given a unique path (vo...., UN) between un and un, any walk between (vo, uN) can be decomposed into a series of N - walks between (vo, 21), (vi, 12),... (uN-1, un) such that the walk between (ons en+1) does not contain a node 6n+1 except at the end point. The expected length of cach walk is t(Un, Un+1).
Proof.
To be specific, consider the following decomposition:
N-1
t(Vo, UN) = E. |xo = vn]
=
[T
Te,, |x0 = vo)
(7)
n
From the Markov property of SRW:
To, (x0 vol = t(Uns Un+1).
Finally, we can formulate the access time as the following:
N-
N-1
t(uo, uN) =
E Temm: - To, 1x00 = vo]
Σ n=0
t(uns untz).
0=0
B.2.2 Access Time between Neighbors
Now, we derive the formula for the access time between neighboring nodes.
Lemma 3. Given tree graph and adjacent nodes i,j, the associated access time t(i,)) is defined follows:
t(i.j) - 218(G.))
where E(g) edge set of graph and 9; is the subtree produced by deleting edge (i. and choosing connected component. of i.
21

---

Published in Transactions on Machine Learning Research (09/2024)
Proof. Given random walk from i to that only contains once, every time the walk lands at the node i, the next step can be categorized into two scenarios:
The walk transitions from node i to j based on transitioning with respect the edge (i.j) E & with probability d;- The walk terminates.
The walk fails to reach j and continues the walk in the subtree G until arriving at the node i again. Note that the walk cannot arrive node j without arriving node in prior. In other words, the walk continues for the return time of i concerning the graph Gr.
The two scenarios imply that every time the walk arrives at node i, the walk terminates with probability 1. Then the number of trials follows the geometric distribution and consequently, the average number of trials is d3. In other words, the walk falls into the scenario of type 2, for d; 1 times on average. We have to traverse least one edge (i,j). The expected total penalty is the product of the average failure penally and the average number of failures. Thus,
a.
(1,))= (d. 1)t(((
where t(i; (i) is the return time of with respect the subgraph Gi. Since the return time is the ratio of the sum of the degree to the degree of the node, stated by Fasino et al. (2023), the following equation holds:
C(i: = 2(E(9()1
d; -
which directly implies our conclusion of t(i,)) = 1 2(8(G))
B.2.3 Main Result
Using Lemma 2 and Lemma 3, we arrive at our main result for the access time of SRW on trees.
Proposition 6. Given tree 9 and pair of nodes i.j E V, the following equations hold for the access time of SRW between and U.
N-1
t(i.j) = Σ (1 2(E(G)))) n=0
where E(g) is edge set of graph 9 and On is the sublree produced by deleting edge (Un, vn41) and choosing connected component of Un.
Proof. The proof is a straightforward combination of Lemma 2 and Lemma
N-1 t(un, Un+1) Σ (1+2)E()))
N-1
t(i,j) Σ
n=0
22

---

Published in Transactions on Machine Learning Research (09/2024)
B.3 Access Time of Begrudgingly Backtracking Random Walks
In this section, derive the access time of begrudgingly backtracking random walks BBRW) between two nodes and j, i.e., j(; on tree graphs. At a high level, this section consists of the following order.
We decompose the access time for two nodes vo and un into summations of the access time of neighboring nodes in the path (Appendix B.3.1 and Lemuna 4).
The decomposed term 1. can be formulated using (i) the return time and (ii) the access time between neighboring nodes (Appendix B.3.2 and Lemma 5).
3. The return time of node can be formulated in terms of the number of edges and the degree of node (Appendix B.3.3 and Lemma 6).
4. The access time between neighboring nodes can be formulated using the number of edges and the degree of the node (Appendix B.3.4 and Lemma 7).
5. Finally we formulate the access time of begrudgingly backtracking random walks (BBRW), i.c., j(i,j) (Appendix B.3.5 and Proposition 7).
B.3.1 Decomposition of Access Time
We start by decomposing the access time t(i,j) similar to the one in Lemma 2. However, key difference exists in the BBRW random walk. When the walk first arrives at node to, it previously passed the node Un-1- Therefore, we cannot return to Un-1 upon the first failure to reach ea+1-
Lemma 4. Consider tree graph and path (Uu,...,,,)) UN). Then the access time of BBRW between node uo and un can be derived as follows:
N-1 E(vo, uN) E(ro 01, vo) +
Σ
E(vn-1 Una un+1) (nt1) -1)
Proof. The proof is similar to Lemma. 2 such that we decompose the walk into series of N - walks weew (vo, U1), (e1, o2)..... (UN-1, uN) such that the walk between Un, Un+1 does not contain a node un+1 except at the endpoint. The expected length of cach walk f(en-1 > Ens Pn+1) - Note that E(vn-1 - Uas on+1) counts the length of walk from Un- to Up+1, hence should be substracted to represent the length of walk from on to ta+1-
To be specific, we have noted that Equation (7) holds for general random walks:
N-1 T Te - Tr., Xxo = vo]-
E(Uo, UN) =
n=
Next, when the BBRW random walk reaches on at Tow, it has passed node Pn-1, i.e., NT., = Un-1- Therefore, the random walk after the time t = To,. - the random walk starting at un-1 with the second node being xı = en Therefore,
T Te,, IN0 vol = -6(mn-1 - Un. Un+1) for n 2
B.3.2 Expressing conditioned Access Time Using Subgraph-return Time
Next, formulate the transition--conditioneel access time E(vn-1 -> Un: Un+1)-
23

---

Published in Transactions on Machine Learning Research (09/2024)
gi
a Figure of nodes k; in B.3.2
(b) Subtree G. produced by deleting edge (i, j) and choosing con- nected components to node
Figure 5: References for section B.3.2
Lemma 5. Given tree G (V,E) and three nodes j, and k such that (..)).i.k) E,
E(i + j.b) - t(j,k) di --
2
(9)
dj
dj'
where t(i: H) is return time of node i in subgraph H. and Gj is the subtree produced by deleting edge (i,j) and choosing connected components of
Proof. We start with establishing basic equalities for access time BBRW.
The first cquality describes how the access time of a random walk from i ->> j k can be expressed by its subset 1, where # due to the non-backtracking property,
1 ビ(i d, -1
Σ
1 - ú(j 11
(10)
IENOMUL
The next equality describes how the access time from j to & can be decomposed by considering subsequent transitions to some in the neighborhood of j.
E(G,)) = dj (EN()
Σ E(j 1,))
(11)
When plugging in Equation (11) into Equation (10), one can see that we need to consider 1 i, k for t(j k,).. In the case of k it is trivially 1. For the case of i, ie., t(j i,),, it can be defined follow:
Eli + i, = + (d, 1)E((; G.) + E(i + k))
(12)
This is similar to Equation (8), where G; describes how the walk from j - to h can be divided into two scenarios: (i) continues the walk Gi or (ii) i transitions into j with probability 1/(d; - 1).
Starting from Equation (10), one can derive the following relationship:
E(1 + j.k)
1+
E
E(j E(j-
dj -1
dj --1
(EN
1
+
Σ
E(j 1,k) E(j i
EG - k k:)
d
-1
dz
LIEN()
1
1
(jE(j.A) -E(J -i,k) - :]
d
dz -1
(c) 1
d,t(),k) k))
-(d: - 1-)(1)))())))) - E(6 - j.k)
dp
24

---

Published in Transactions on Machine Learning Research (09/2024)
where (a) is from Equation (10), (6) is from Equation (11) and E(j + ke k) 1, (c) is from Equation (12).
Now, by multiplying d,- - on both sides, we get
(d, 1 E(( {(i - 1) = -djt(j,k) - - 1)E(( - E(i - j. k) -
d,t(j,k) - - 1))(( - [(( - j. -1 -1) -2.
Thus, can conclude for i(i - j. k) 1:
d: 4-1 1 E(: - dj
E(i + j.k) - =(],k)
d2
7
B.3.3 Return Time with respect to Subgraph
Now, we formulate the return time {(i; 9) for tree-graph G. Considering the return time, prove that the return time of BBRW is less than or equal to that of SRW.
Lemma 6. Given a free G = (V,E) and a node i, the return time of i for a BBRW is the following:
2/E
E(i:)) d;
Proof. Consider the tree as a rooted tree where the root is i. In the following, we will use mathematical induction based on the tree height of i.
First, consider the base case where the height of the tree is 1. Then, whatever we choose as the next node
X1 from Xo i, return to i at the second transition (i.c., X2 = i) since all the neighbors of i are leaf node. Since d, = |8| for tree with height 1, E(igg) = 2 = 21 d.
Now, assume that the lemma holds for the tree with height less than k 2 1. It suffices to show that the lemma also holds for tree with height k ++1 and its root i. From the same perspective in the proofs of the Lemma 3, we can view the random walk returning to as follows:
We choose a node x1 from (() uniformly. Then, from node I, we return to to reach i. (i.e., we have to pay penalty amounts return time of t)
2. In node I, we try to reach i by selecting edge (I, with probability ब- Thus, the average number of failures is di - 2.
3. If we fail to reach from I, we should return to I for next chance to reach i. i.e., an average failure penalty amounts to a return time of 7 in the subtree with root I.
Hence,
1 1/ 1 de (
(di-2)+11) +1 )} =2+
E(i:g) 1
Σ
2+ Σ
d; E(19))) (di 1), (EN(()
LEN())
where E(1; 9t) is the return time from node for graph 9 and Gr denotes the subtree with root. 1, respectively.
25

---

Published in Transactions on Machine Learning Research (09/2024)
Since the subtree with root I has height less than k. E(L 2E(GG))
Therefore,
d;
((:g))=0)
1
Σ
El: (di -)
di (EN(()
=2+ 1
2|((0))
Σ
(di 1)
di (EN())
2 + di
1
Σ 2(E(9))
(EN(()
2 + EiEv(o) [(()))
di
2/
di
B.3.4 Access Time between Neighbors
For access time between neighbors, we achieve a similar result to Lemma 3.
Lemma 7. Given a tree 9 and adjacent nodes i,j,
d, -1 =(+
d,
where E(G) is edge set of graph 9, and G2 is the subtree produced by deleting edge (i,j) and choosing connected component of i.
Proof. We follow the same perspective of the proofs in Lemma
We first analyze the success probability for each trial, which is d, since there is no previous node. After the first trial, the success probability is fixed to //h. On each trial, the average failure penalty amounts to E(i; G.), which is the return time of i on subtree Gi.
Thus, the average number of trials until first success is,
(Average number of trial) de + d=
(1+(4:-1)
d,
The average number of failures as follows: (Average number of failure) (Average number of trial)
+ d, -
d, (1 + d; 1)
di
(d: - 1)2
Thus, the expected total penalty is as follows:
(d; - 1)2
(Expected total ponalty) = E((:
d,
Since E(i; 2[119.] d,-1 by Lemma 6, E(u,v) 1 2|E(G.)) d
26

---

Published in Transactions on Machine Learning Research (09/2024)
B.3.5 Main Result
Finally, we show that the access time of BBRW between two nodes and j, i.e, t(i,)), in Proposition 7. Proposition 7. Given a tree 9 and a pair of nodes i, the following equations hold for the access time of BBRW between i and j.
N-1 t(t,j) = Σ ==0
dun -1 dun
N
2|E(Gn-1)]
N-1
1+218((9n)
Σ dua
den
where E(G) is the edge set of 9 and In is the subtree produced by deleting edge (Uns Un+1) and choosing connected component of Un.
Proof. By Lemma 4 and Equation (9) of Lemma 5,
f(vn-1 + Uni un+1) -1 }
t(vo, uN) = t(vo, 01) +
don -
2
=E(eo, 01) +
E(vn, unt1)
t(un-1)
dun
dun
n=l
N-1
d
N-1
E(Un) Un+1]
E(Un-1)
den
dr
dr -1
N-1
21E
N-1 2
1+
dun.
d
dr..
R=0
27

---

Published in Transactions on Machine Learning Research (09/2024)
B.4 Proof of Proposition 1
Finally, compare the access time of two random walks in tree. Recall Proposition 1.
Proposition 1. Given tree (V,E) and paár of nodes i.j E V, the access time of begrudgingly backtracking random walk is equal to or smaller than that of simple random walk. The equality holds if and only if the walk length is 1.
Proof. Let E()) be the edge set of 9 and 9n be the subtree produced by deleting edge (en, Un+1) and choosing connected component of en. Then,
N-1
dun -1 2|
N 2 (G 11)
= E(Vo, UN) t(v0: uN)
Σ
1
du
dua
n=0
N-1
2
Σ
(1+2)E((N)))
do
N-1
2(E(gn)l
21
N-1
2
50.
du,
d
dy
R=1
Therefore the access time of two nodes always less or equal in begrudgingly backtracking random walks than simple random walks, where equality holds for random walks with length 1.
28

---

Published in Transactions on Machine Learning Research (09/2024)
C Proofs for Section 4.1
C.1 Preliminaries
Let G be a graph with set of vertices V, a set of edges & E V2, We use x; to denote the node-wise feature for E V, and di for the degree of node i V. The adjacency matrix A E RRxx encodes the connectivity of graph G. For node i E V, we define the set of incident outgoing edges of i as (i), the set of incident incoming edges of i as Nº (i), and let (t) (+)(t)) U (i) be the set of all incident edges of node i. Also, recall the non-backtracking matrix B E (0, ) 2 and the incidence matrix C E TR
B(E-A), = {
if = otherwise
C(k-s) {1 if i =
otherwise
We also define Dout and Din as the out-degree and in-degree matrices of NBA-GNN, respectively, counting the number of outgoing and incoming edges for each edge. These are diagonal matrices with (Dau)) (-.)))))))))))) = Ee+ ((j-s))(eeR) and (Dn))G-n),G--)) Ee- (ie-))).(--i); for cach index i. Next, we introduce B the normalized non-backtracking matrix augmented with self-loops: B = (Dout + T> + T) + T)- Then one obtains the following sensitivity bound of NBA-GNN. We also let Ć denote matrix where C(e+j),+ = C(--s),+ + C(-+k),
Consequently, express NBA-GNN updates:
B(G-R),G-WW (n ((2))))))) (K,E)EE
h h = ((0))
Σ
(13)
where (( and vs(t) corresponds to the update and the aggregation as described in Equation (3). Next, the node-wise aggregation step can be described as follows:
h: =
Σ (GAAEEE
Ca--S) (1))))) E
Cij-k), (1
(SA)EE
C.2 Proof of Lemma
The original sensitivity bound from Topping et al. (2022) for a hidden representation of node j and an initial feature of node is defined as the following: Proposition 2 (Sensitivity bounds). (Topping el al., 2022) Assume an MPNN defined in Equation (1). Let two nodes i.j V with distance T. If Voll ||, I and ( I 3 for 0 s T, then the sensitivity bound can be defined the following:
0h!") (T)
S {aa)) 333
(6)
Oz;
where À denotes the degree-normalized adjacency matrir.
Now, we show that the sensitivity bound for non-backtracking GNNs can be defined as following, Follow- ing Topping et al. (2022), we assume the node features and hidden representations are scalar for better understanding.
Lemma (Sensitivity bounds of NBA-GNNs). Consider two nodes i,j E V with a random walk distance T given a (T 1)llayer NBA-GNN as described in Equation (3) and Equation (4). Suppose | [], |Vol,, I a, | 1 Vpll, $ B, and ||Vol, Sy for 0 OSt sttt. T. Then the following holds:
0h,
dr: {a 7(T B
29

---

Published in Transactions on Machine Learning Research (09/2024)
Proof. Just straight calculation using the chain rule is enough to derive the above upper bound.
0h 0x;
S1o02p
Σ
k-t
(T-1)
+ 0100sp
Σ
ah (T-1) dz,
k-t
dzi
K-LEN. (
(-FENT
kh (I-1)
01002p
Σ
R-ol
Szi
A (
(T-1)
S aB
Σ I-EENNT
(14)
Oz:
(1)
where the bound for the derivatives were [o S a, 1I Vpll, s B.
Thus considering the message update from Equation (13),
0h k 0101T-21 2)
(T-1)
0h 0h
(T
Ol (T
020
E
BR k-st
Or.
dz.
Ox:
M-MEN. (b)
(T-2)
020lT-2)
Oz,
W W-FENN (K)
Oh (T-2)
Ohi Ōr;
since the distance between node and node j is least T, therefore
Now, let the path from node to node j as s(i,j), where 8, denotes the 1-th node in the walk 8, i.e., Sp = 11 = j. Using the bound of the derivative of functions, we can iterate like the following.
oh R-
dr,
(T-2) a do,
< 03
Σ
B - 1 k-rl
W-BEN. (k)
(0) th 1 ,z,
< (1:3)--1
Σ
B 180-81811800 -55
Bx-- 2
(0) Oh 2.1 Oz:
(a
Σ
II
(Samm)r)Ess(.)) t=1
T-1
S T1
Σ
II t=1
1
B
(15)
Substitute the incquality Equation (15) into Equation (14) to get the final result. Then, we can get
0h,
5 (ag))
Σ
II B -0)))))))))))
0x:
(So.... (e((i.)
= (a (C pT BT 1))a
since paths be expressed using the power of adjacency-type matrix.
30

---

Published in Transactions on Machine Learning Research (09/2024)
C.3 Proof of Proposition 3
We have defined the sensilivity bound for NBA-GNNs. Now, we show that the sensitivity bound of NBA- GNNs are bigger than the sensitivity bound of GNNs.
Proposition 3. Consider an MPNN defined as in Equation (1) and a (T - 1)-laerr NBA-GNN described
by Equation (3) and Equation (4). For any pair of nodes i.j E V with distance T, the following inequality holds between sensilivily bounds:
(A 3o S (Õ BT BT-O0),
For d-regular graphs,
CTBT-100)s decays slower by O(d while (A") decays with O(d + 1)-
Proof. Identical to the notations above, we denote the list of nodes from node to node j as path s(i,))
where s(i.j) = (so = 1, ST-1,, j).
jj
Σ
Ano.os ... Āor 1858
T-1
Σ
(d: + (d.+1) 1 + +1)
II 1=1
(de, + 1)-!
(80 (T()..)))))
(Č BT)
Σ
dso
Ban 110.1111111 052
Bar 2 185 1888
dor
(ea (E(((.))))
Σ
dso
1 d=1 dar-
dar
Σ
dao
2 der
(80 (e(((.))))
Now, for path (so 87 11:-=1 =j),
T-1 (d,, + 1) S di dd
T-1
(di + 1)- + 1)=
II
ded
Each term in (T) is larger than (a)),,, thus (ČT BT (A is trivial.
For d-regular graphs d: d, Vi E V. Therefore the sensitivity bound can can be written as following:
AA' ja (d+1)-" (OT C
C) = d
So (TTBT-1)) decays slower by Old-T), while (A)), decays with O(dd + +1) -))
31

---

Published in Transactions on Machine Learning Research (09/2024)
D Proofs for Section 4.2
To assess the expressive capabilities, we initially make an assumption about the graphs, considering that it is generaled from the Stochastic Block Model (SBM), which is defined as follows:
Definition 1. Stochastic Block Model (SBM) is generated using parameters (n, K, P), where n de- notes the number of vertices, K is the number of communities, a (ai...., ag) represents the probability of each verter being assigned to communities VK, and Pij denotes the probability of an edge (u, w) E E between V; and w E V/.
Numerous studies have focused on the problem of achieving exact recovery of communities within the SBM. However, these investigations typically address scenarios in which the average degree is at least the order of Ω nIogn) (Abbe, 2017). It is well-ostablished that the information-thoorete limit in such cases can be reached through the utilization of the spectral method, as demonstrated by Yun & Proutière (2016). In contrast, when dealing with a graph characterized by the average degree much smaller, specifically o (log n), recovery using the graph spectrum becomes a more challenging endeavor. This difficulty arises due to the fact that the n² ( largest cigenvalues and their corresponding eigenvectors are influenced by the high-dogree vertices, discussed in Benaych- Georges et al. (2019).
However, real-world benchmark datasets often fall within the category of very sparse graphs For example, the citation network dataset discussed in Sen et al. (2008) has an average degree of less than three. In such scenarios, relying solely on an adjacency matrix may not be an efficient approach for uncovering the hidden graph structure. Fortunately, an alternative strategy is available by utilizing a non-backtracking matrix.
D.1 Proof of Proposition 4
Let's rephrase the formal version of Proposition 4 as follows:
Proposition 4. Consider a Stochastic Block Model (SBM) with parameters (2) where (a + b) satisfies the conditions of being at least w(1) and nol1) In such a scenario, the non non-backtracking gruph neural network can accuralely map from gruph G to node labels, with the probability of error decreasing to 0 as n + SC.
In Stephan & Massoulié (2022), the authors demonstrate that the con-backtracking matrix exhibits valuable properties when the average degree of vertices in the graph satisfies w11) and n1(1), When K = 2, we define function (vr) for V, such that a()) if is in the first class, and ((v) -1 in the second class.
Then, they establish the following proposition:
Proposition 8. (Stephan & Massoulié, 2022) Suppose have a SBM with parameters (n, 2, ( (4 :)) In this case, we have two eigenvolues μ사 > #2 of ndiag(a)), and the eigenvector Φ2 corresponding to #2, where w-th component is set to au). Then, for any n larger than an absolute constant, the eigenvalues A and X2 of the non con-backtrucking matria B satisfies -ul = o(1), and all other eigenvalues of B are confined in a circle with radius (1 + o(1))
a+b 2
Also, there exists an eigenwector D2 of the non-backtracking matria
B associated with X2 such that
(22.z)
2
1
(a b) b)2 + +o(1) = 1- 10)=;aab)b)
where E2 = [T | T E {0, 2mmx Tei = 1(e2 = i and o E {0, 10,1 0 = 1 if the verles i is in the j-th
Te
community, and 0 otherwise.
The proposition above highlights that the non-backtracking matrix possesses a spectral separation property, even in the case of very sparse graphs. Moreover, the existence of an eigenvector U2 such that (v2, &2) = 1-o(1) suggests that this eigenvector contains information about the community index of vertices. The foundation for these advantagoous properties of the non-backtracking matrix B in sparse scenarios can be attributed to the observation that the matrix 8 shares similaritics with the k-hop adjacency matrix, while A is predominantly influenced by high-degree vertices. Consequently, we establish the following lemma:
32

---

Published in Transactions on Machine Learning Research (09/2024)
Lemma 8. Suppose have SBM with parameters defined in Proposition 8. Then, there crists function of the eigenvectors of the non-backtrucking matria that can accuralely recover the original community index of vertices.
The proof for Lemma 8 can be found in Appendix D.3 In the following, we will demonstrate that the non- backtracking GNN can compute an approximation to the top eigenvectors mentioned in Lemma 8. To achieve this, we first require the following lemma:
Lemma 9. Assuming that the non- non-backtracking matria B has set of orthonormal eigenvectors Vs with corresponding eigenvalues X > > AK 2 Ax+1 2 ... Xam, then there erists a sequence of convolutional layers the non-bucklracking GNNs capable of compuling the eigeneeclors of the non-bucklrrucking malria.
For the proof of Lemma 9, please refer to Appendix D.4. With this lemma in mind, we can observe that a soquence of convolutional layers, followed by multilayer perceptron, can approximate the function outlined in Lemma 8, leveraging the universal approximation theorem. This argument leads Proposition
D.2 Proof of Proposition 5
Let's rephrase the formal version of Proposition 5 as follows:
Proposition 5. Consider two graphs, one generated from a SBM (g) with parameters 2,, (3, 4) (a 2))
n
and the other from an Rrdös-Réngi model (Hl with parameters (n, h) for some constants b, 1. When (a b)² > 2(a + b), the non-buckkracking graph newral network is capable of dislinguishing between G and H with probability tending to 1 as + 00.
To establish Proposition 5, we rely on the following Proposition from Bordenave et al. (2015):
Proposition 9. (Bordenave el al., 2015) Suppose we have two graphs G and H as defined in the formal statement of Theorem 5. Then, the eigenvalues (BB of the non- non-backtrucking matrix salisfy the following:
a+b X (Bg)
a-b + o(1) and [bx(Bo] s - o(1) for k>
aabb
+ o(1), (2(b) 2
2
(B c o(1) and |a2(B)) o(1)
Proposition 9 informs us that by examining the distribution of eigenvalues, can discern whether a graph originates from the Erdós Rényi model or the SBM. Leveraging Lemma 9, we can obtain the top two normalized eigenvectors of the non-backtracking matrix using convolutional layers, denoted as and v2. Applying the non-backtrackinn convolutional layer to these vectors yields resulting vectors with nornrs corresponding to (B). Consequently, we can distinguish between the two graphs, 9 and H. by examining the output of the convolutional layer in the bockbacktra GNN.
D.3 Proof of Lemma 8
Proof. Let us revisit the matrix T, defined as Te: = 1(e2 = i}, and its pseudo-inverse denoted as T D-'TT, where is a diagonal matrix containing the degrees of vertices on the diagonal. Considering the definition of & provided in Proposition 8, we can deduce the label of vertex e. Specifically, if (T+ 0, it implies that the vertex belongs to the first class; otherwise, it belongs to the other class.
Additionally, we are aware that || (T+v2 - T+))), ll2 Of b)) as indicated in Proposition 8, considering the property that the sum of each row of T is equal to 1. Consequently, by examining the signs of elements in the vector T22 we can classify nodes without encountering any misclassified oncs.
33

---

Published in Transactions on Machine Learning Research (09/2024)
D.4 Proof of Lemma 9
Proof. Suppose we have arbitrary vectors F1,. and a matrix X [21,,.., Tyl R2mxx which has 21,..., 2 as columns. Without loss of generality, we assume that f S 2m and | = 1. Let 2; = =i= di vi for S S S. f. We will prove the lemma by showing that if we multiply X by B and repeatedly apply the Cram-Schhiitt orthnormalization to the columns the resulting matrix, the j-th column of the resulting matrix converges towards the direction of Vy. Further, we will show that there exists a series of convolutional layers equivalent to this process.
First, need to show B* æ1 converges to the direction of 11. B 21 can be expressed as:
Bhn A1 (ffl + o0 (d2) &
A2m
V2 ... + +c2m
(1)
V2m
b1
A1
Let's fix 0 and take Ko such that for all &: 2 Ko, the inequality define the following for brevity:
[1
A2
de 4m
holds. Furthermore, we
for l = 1.
(1)
(6)
where us (1)
GB( (K (111)) for l22
|| 112
Then, the distance between ej
(k)
and sign
(1) is is
c1
(K)
sign
c
(1)
V1
(c)
9 +
Eim
(A
(2e)
v2
sign
Ci
(1)
V1
2
D
111
sign
c
Dv1
D
-1c
+D
6
2
(6)
V
Σ
12
2m
A1
As
2k
(c)
(1)
e
+
D
2
(d)
6,
where (a) stems from defining V (a (c())22 + 2mm
2k (c(0)32 as D, (b) and (d) are obtained from the clc and for (c) we use the incquality / x22 + y² s |æ|| + lv]-
assumption
x.
Am
Moreover, we assume that for all S < L and any et > 0, there exists Ke such that for all k > K
ce -iig
c vi
ce. To simplify the notations, define Ko maxigest Ke and 2 c
(R) (N)
sign (10) Us for all f. Then, we must show there exists Kr. such that for all K =2
(k) || < <e. With no
loss of generality, let's assume that sign
for all E. Furthermore, let us fix ez. > 0 and ez = min(1,
34

---

Published in Transactions on Machine Learning Research (09/2024)
(8) for 8 < L. Then, "I
for k 2 Ko can be writlen as
(k+1)
Be(
E(e (c( (c (
"
ict.
BeL (K)
Σ
(1,, Be ) (2( Be
Be u + (mr + 2, 2(++1) )e (((tt)))
(us
Be
De - Ni
124
where (a) comes from the definition // (2) (4,t)) Be u + (vs + 22 2,(+11), )2 (k+1)
)2
Additionally, let dmax be the maximum degree of vertices in g. For any vector x E R2m with an --ro less than E2: the following inequality holds:
Bell2
Σ i
Σ bisety
<
2 Σ
Σ
big
S Cadmax 2m.
(16)
f
Thus, using (16), we can deduce that | 1/2 S 3Leddmax / 2m.
In contrast, for any integer > 0, uz.
(k+p) is
L
(k+p)
Σ 12
(us,
Be Be (ktD-1)) 1)00) (ctp)
1L
(v,, Bel ()+ Aby2, - By 20
(ktp)
Vs.
Vi
(1
i2b
32h
1
Ac(Ms Be Belito-211 - (Vi, Bui BUL vs - 12 (k+p)
(k 1) 11
121.
(ur Be ( 1ii0s
(vr, ( 10p0-22)yu vi (14p)
11 1)
( (k 1)
12L
(u, Bei (e( )
W (1+
F21.
1
Σ
(ve, By (K+s 11 11 m1) (k+p)
(k+s)
)=1
122
(ps, 1 m
(1++) uy
12r.
E(m
(mi Byl. (K+t) 11 22 28- 2s) ((+D))
(k+t)) ub
122
(4) CoX2
(VL, Bee (1) yu +
Σ
(Mr, Be( (1= p-1
126
]Σ Cj
(vr,, 11 - 1/. (k+p)
12 1=1
35

---

Published in Transactions on Machine Learning Research (09/2024)
where (a) stems from the definitions Co
and Cj
" 1k1))
Now, define e (k+p))
Then,
CoA2 (Mz Be
Eisr 2i Cj (1r Byt
Byt. (k+s-1) 111111))1111 1 1x- v.) yr.
(k+p)
(Uey Ac( (8))
Ai p-1
E eletp) VL
( Be (k)))
AL
14
Co (VL, (
(17)
Take Po such that less than ez/4.
Ai
Pa-1
1
4(2 Bel then, the eo-m of the second term of Equation (17) is
Bel
Mcanwhile, the e-norm of the third term in Equation (17) is upper-bounded by
3Lendmax 2 Cilmax 2m
15 1p-2
+ 1)
+1
Co.t. (vi, Be
di
-
126
where C= max]=1 Cj.
Therefore, we take cp < <CoAp,-' Bel.)e
(Odmaxv Eizr
1.
+ 1)
(k+p)
12 22m
A.-1
we can get
VL
2
cL/2 for p > Po- Finally, the upper bound of
2
is
2
(K)
(k+p) (k+p))
+ ++|1/ 2 UL
1
EL
(0)
(k+p)
1
er
2
62
where (a) follows from ()+p)
L
8 (k-p)
and (b) is obtained from the inequality 1 4 S
(k(tp) 5
1 + 2
36

---

Published in Transactions on Machine Learning Research (09/2024)
E
Experiment Details
In this section, we provide details of NBA-GNN implementation and experiments.
E.1
Implementation
E.1.1 Message Initialization and Aggregation
For message initialization and final aggregation messages, we have proposed functions Ø, o, p. To specific, the message initialization can be written follows:
(if esy exists)
(0) n
x,)
(otherwise)
For our experiments, we use concatenation for o, weighted sums for o, and average for p.
E.1.2 Non-backtracking Updates
Here, we provide the details of using the non non-backtracking operator in our NBA-GNNS. To begin, let's revisit the non-backtracking matrix B E {0, |2|8|x2 El from Section 4.1 defined as follows:
{1 {
if = ji otherwise
B(--)),0000) =
Returning our NBA-GNN, the non-backtracking message passing update for hidden feature h n at the (L+ 1)-th layer, introduced in Section 3.2, is expressed as follows:
(1/111) (1) (10)) (12)) NG) (O))))))
((+1) j-b =0(1)
(3)
where (( and e)()) are backbone-specifie non-linear update and permutation-invariaa aggregation functions at the t-th layer, respectively. Using the non- backtracking matrix B, we can rewrite Equation (3) as following:
H(+1) = -5100 H1.) (H v:(0) (B H0 T HT())
where H()) E (2216xdd xd are edge-wise features, i.e., each row representing h n
E.1.3 Implementation Example
Now, the NBA-GNN implementation example in Section 3 using GCN (Kipf & Welling, 2017) as backbone, can be written the following:
(1+1) = 1 WG)
W
Σ
(0) P
RENGIEE
Recall the out-degree and in-degree matrices of NBA-GNN, denoted as Dout and Din, where (Dot))--s).--1) = Ee ((-+),((--)) and (Dm))-+))004) = E. ((c-s)),--i)) for each index j + i. We also introduced the normalized non-backtracking matrix augmented with self-loops B (Dout I)- 3 (B+ I)Di.n + 1 In summary, Equation (5) can be expressed as follows:
H(++1) = (1
Hence, the message passing update in NBA-GCN is equivalent the multiplication of non-backtracking operator and edge-wise representations constructed from node-wise features.
37

---

Published in Transactions on Machine Learning Research (09/2024)
E.2
Graph Benchmark
E.2.1
Dataset Statistics
From LRGB (Dwivedi et al., 2022), experiment for 3 tasks: graph classification (Peptides-func), graph regression (Peptides-struct), and node classification (PascalVOC-SP), We provide the datasct statistics in Table 10. Note that for PascalVOC-SP, we use SLIC compactness of 30, and edge weights are based only on super-pixels coordinates following the recent work (Gutteridge et al., 2023).
Table 10: Statistics of dalasets in LRGB.
Total Graphs
Total
Avg
Mean Deg-
Total Edges
Avg Edges
Avg Path.
Avg
Dataset Splits
Dataset
Nodes
Nodes
Short.
Diameter
POC-S1VOC-SP
11,355
5,443,545
479.40
8.00
43,348,360
3,835.17
8.05 1 0.18
19.40 1: 0.65
75/12.5
Peptides-func
15,535
2,344,839
150.94
2.04
4,773,974
307.30
20.89
1 9.79
56.99 1 28.72
70/15/15
Peptides-struct
15,535
2,344,839
150.94
2.04
4,773,974
307.30
20.89
+ 9.79
56.99 1 28.72
70/15/15
E.2.2 Experiments Details
All experiment results are averaged over three runs (seod 0~-2) and trainod for 300 epochs, with a 500k parameter budget. Baseline scores laken from the LRGB (Dwivedi et. al., 2022), Table 1 of DRew (Gutteridge et al., 2023), and papers of each work.
We use an AdamW optimizer (Loshchilov & Hutter, 2018) with Ir decay=0.1, min Ir=1e-5, momen- tum=0.9, and base learning rate 1r=0.001 (0.0005 for PascalVOC-SP).
We use cosine scheduler with reduce factor=0.5, schedule patience=10 10 with 50 warm-up.
Laplacian positional encoding was used with hidden dimension 16 and layers.
We use the " "Atom Encoder", "Bond Encoder" for Peptides-fuu func, Peptides-struce from based on OGB molecular feature (Hu al., 2020; 2021), and the "VOCNode Encoder", "VOCEdge Encoder" for PascalVOC-SP.
PascalVDC-SP results in Figure 4a all use the same setup described above.
Peptides-func results in Figures 4b and 4c all use the same setup described above.
GCN results in Figures 4a to 4c use the hyperparameters from Tönshoff et al. (2023).
We searched the following range of hyperparameters, and reported the best in Table 11.
We searched layers to 12 for PascalVOC-SP 2, layers 5 to 20 for Peptides-func and Peptides-struct.
The hidden dimension was chosen by the maximum number in the parameter budget.
Dropout was searched from 0.0~0.8 for PascalVOC-SP in steps of 0.1, and 0.1w00.4 in stops of 0.1 for Peptides-func and Peptides-struct.
We used the batch size of 30 for PascalVOC-SP on GPU memory, and 200 for Peptides- funncc and Peptides-struct.
38

---

Published in Transactions on Machine Learning Research (09/2024)
Table 11: Best hyperparameters for each NBA-GNN and dataset in LRGB.
Model
Dataset
Param.
Layers
hidden dim.
dropout
Batch size
epochs
PascalVOC-SP
472k
12
180
0.7
30
200
NBA-GCN
Peptides-func
510k
186
200
300
Peptides-struct
505k
20
144
0.1
200
300
PascalVOC-SP
472k
200
NBA-GIN
Peptides-fune
502k
10
144
0.1
200
300
Peptides-struck
503k
10
144
0.1
200
300
VOC-SP
486k
10
96
0.25
30
200
NBA-GatelGCN
Peptides-futt func
51lk
10
96
0.1
200
300
Peptides-struch
511k
8
108
200
300
E.3
Transductive Node Classification
E.3.1 Dataset statistics
We conducted experiments involving three citation networks (Cora, CiteSeer, and Pubmed in Sen el al. (2008)), and three heterophilic datasets (Texas, Wisconsin, and Cornell in Pei et al. (2019)), focusing transductive node classification. Our reported results in Table 3 are the averages obtained from 10 different seed runs to ensure robustness and reliability.
For the citation networks, we employed the dataset splitting procedure outlined in Yang et al. (2016). contrast, for the heterophilic datasets, we randomly divided the nodes of each class into training (60%), validation (20%), and testing (20%) sets. We provide more details of dataset statistics in Table 12.
E.3.2 Experiment Details
The training duration spanned 1,000 epochs for citation networks and 100 epochs for heterophilic datasets. Following training, we selected the best epoch based on validation accuracy for evaluation on the test dataset. We used the AdamW optimizer (Loshchilov & Hutter, 2018) with a learning rate of 3e-5. The model's hid- den dimension and dropout ratio were set to 512 and 0.2, respectively, consistent across all datasets, after fine-tuning these hyperparameters on the Cora dataset. Additionally, we conducted optimization for the number of convolutional layers within the set f1,2,3, 4,5). The results revealed that the optimal mum- ber of layers is typically three for most of the models and datasets. However, there exceptions, such as CiteSeer MenSeer--atedGCCN CraphSSAGE+NBA-PPA
Wisconsin- (GraphSAGG-+NBAA GraphSAGE+NNAA-PAA SA and Cornell- (rrnelll(GraapSSAGEE, GraphSAGE++NBA GraphSAGG--NAA-PPH where the optimal number of layers is found to be four. Furthermore, for Cora- Cora-(Graphsia (GrapSAACE+NAA-PP)) GAT+NBA), CireSeor-GrapSSGGE-
aabbeed-(GraphSAAe
the optimal number of layers is determined to be five.
Table 12: Statistics of the datasets for the transductive node classification task
Total Graphs
Num Nodes
Num Edges
Dim Features
Num Classes
Dataset
Cora
1
2,708
10,556
1,433
7
CiteSeer
3,327
9,104
3,703
6
PubMed
1
19,717
88,648
500
3
Texas
1
183
309
1,703
5
Wisconsin
1
251
499
1,703
5
Cornell
1
183
295
1,703
5
39

---

Published in Transactions on Machine Learning Research (09/2024)
E.3.3 Baseline implementation
In Section 5.3, we compared NBA-GNNs with several baselines to verify the effectiveness of non-backtracking updates. Three baselines that updale edge features were considered: GatedGCN (Bresson Laurent, 2018), EGNN (Gong & Cheng, 2019), and CensNet (Jiang al., 2020). Though these baselines update edge features, the six datascts used for transductive node classification do not have initial edge features. Basod each paper and its code, used the pairwise cosine similarities between corresponding node features edge features for CensNet, and encoded each directed edge into vector V E {0, for EGNN. Additionally, we utilize the attention-based EGNN model, referred to as EGNN(A) in the original paper.
40


Reviews:
[{"review_id": "OgVD3JOcig", "reviewer": "Reviewer_ixiA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\n- Implementing non-backtracking updates offers a novel solution to addressing the redundancy issue in GNNs.\n\n- The paper conducts a comprehensive theoretical analysis, demonstrating that NBA-GNN enhances the upper bound for sensitivity-based measures of GNN over-squashing and can identify the underlying structure of SBMs, even in very sparse graphs.\n\n- The experiments on two benchmarks show that the proposed GNN can improve existing GNN baselines.\n\nCons:\n\n- The study aims to address the redundancy problem in GNNs. However, the experiments lack direct comparisons or specific case studies demonstrating that the proposed non-backtracking updates effectively reduce redundancy. In my view, the discussions in Appendix A do not adequately support this claim.\n\n- The baselines presented in Tables 2 and 3 appear outdated. The criteria for selecting these baselines are unclear, which weakens the soundness of the work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces the non-backtracking graph neural network (NBA-GNN) to address the redundancy issue in message-passing updates of traditional GNNs. The authors propose a method that prevents messages from revisiting previously visited nodes, thereby reducing over-squashing and improving performance on long-range graph benchmarks and node classification tasks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The explanation for “Step 1” in Figure 1 is missing, making it challenging for readers to grasp the distinction between “Step 1” and “Step 2”. It would be better to add more explanations.\n\n- Consider including an experiment or case study to demonstrate how the proposed update can effectively reduce redundancy, if feasible.\n\n- It would be better to standardize the baselines for the two tasks in experiments, if feasible. Otherwise, please clarify the criteria used for selecting these baselines.", "broader_impact_concerns": "NA.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tFb9ThE3C3", "reviewer": "Reviewer_pxoD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n1. The paper is well-written and clearly structured. \n\n2. This is a welcome take on the over-squashing problem in GNNs. I believe that imposing non-backtracking constraints is a good idea, be it using the architecture proposed in the paper, or thinking of alternative solutions.\n\n3. Appendix A is a nice addition to the paper, I would definitely move it inside the main text! You should take advantage of the fact that it is a journal paper ...\n\n### Weaknesses\n\n1. The novelty of the method is not that obvious with respect to previous works such as Chen et al. (2019). Still, the paper provides a refined version of the idea, allowing true non-backtracking flow, and I believe this is sufficiently \"novel\" in this sense for TMLR.\n\n2. The lack of discussion (except for two sentences) of the expresivity of NBA-GNN w.r.t $k$-WL tests undermines the expressivity claims of the paper.\n\n3. The authors should discuss if the assumptions in Lemma 1 are \"reasonable\" or \"natural\".\n\n4. The statement of Theorem 1 is too informal. Also calling \"theorem\" the content in Theorem 2 & 3 seems a bit of an overstatement. They are immediate consequences of Lemma 9 if I read correctly the appendix.\n\n5. I think a discussion is missing after Theorem 1. Can we believe this bounds to be optimal? Does this decay can be observed on $d$-regular graph? What happens for almost regular graph? \n\n6. The organization of the proof section is not optimal. There is some forward reference to results proved afterwards (e.g. Lemma 9 depends on Lemma 10)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission analyzes Non-Backtracking Graph Neural Networks (NBA-GNN) in the line of Chen al. (2019) (but refined). These networks address the redundancy in message passing of typical MPGNNs by preventing messages from backtracking to previously visited nodes. This approach reduces redundancy, alleviates the over-squashing phenomenon, and enhances the expressive power of GNNs, particularly in distinguishing structures within sparse stochastic block models. Empirical validations demonstrate that NBA-GNNs moderatly outperform conventional GNNs in various graph-related tasks.\n\nDespite several flaws that I describe below, I believe that the paper is a good fit for TMLR. The paper is well-written and structured, and the idea of NBA-GNN is interesting.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "p6:  Can you confirm that |.| is the L2-norm and ||.|| is the spectral (or Frobenius I have a doubt) norm? If I am not mistaken the Jacobian considered is of size $p_T \\times p_0$ where $p_i$ are the sizes of the features.\n\np6: You do not define what is a sensitivity bound. I guess this is the r.h.s of the equation in Lemma 1.\n\np28: third line of eq 14. that's a lot of dots!\n\np31: the notation $f(\\leq 2m)$ is a bit confusing.\n\np32: You simplify a lot the big block of equation by naming the numerator.\n\nall documents: please check typography (display equation environment should be ponctuated for instance).", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CnVL83SGSy", "reviewer": "Reviewer_P53w", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n- The idea appears effective, albeit simple. It seems to be an interesting generalization \nof the non-backtracking random walks to message passing. \n- Theoretical results are derived. \n- Some experimental results show the effectiveness of the proposed technique to some extent. \n\n\nWeaknesses: \n- Experimental evaluations use limited baselines and datasets.\n- Some experimental details are missing. \n- The insights from theoretical results or their significance on the algorithms or \nparameter configurations or tuning are not so clear. Theoretical results and \npractical side, e.g., the use of the algorithm on experiments, seem disconnected.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a non-backtracking (NBA) technique for message passing in graph neural networks. \nIt considers updating edge features and building non-redundant computation graphs for the message passing neural networks (MPNNs).", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The following comments or suggestions need to be considered. \n\n1. The evaluation is expected to be enhanced. Several baseline methods have been considered, including GCN, GINE, and GateGCN, to show the effectiveness of \nthe proposed technique. These models are standard, but more and recent models are  expected to be considered. Moreover, these baseline models appear to be mainly \nbased on updating of node features. Because the proposed NBA-MPNN is mainly based on updating of edge features, which might be complementary to the updating of node features, it is unclear if the experimental improvement is mainly due to the NBA, or due to the message passing over edge features. I would suggest the authors to consider also the following models as baselines, which are mainly based on or consist of updating of (multi-dimensional) edge features: \n\n- “Co-embedding of nodes and edges with graph neural networks,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.\n- \"Exploiting edge features for graph neural networks,” in 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019. \n- \"Graph transformer networks,” in Advances in Neural Information Processing Systems, 2019.\n- \"Graph-mamba: Towards long-range graph sequence modeling with selective state spaces,\" arXiv preprint, 2024.  \n\n\n2. Please clearly state what insights or what impacts the theoretical results give/have on the algorithm or experiments.  \n\n3. In the experimental part, the partitioning of the LRBG such as Peptides-func, -struct, and Pascal-VOC is specified. Please specify because the performance is impacted by the partitioning ratios. \n\nBased on the review results, I would recommend review again after major revision.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper was appreciated by the reviewers that had many questions and suggestions. Those suggestions were very well taken into account by the authors in the revision which was appreciated by the reviewers. All reviewers believe that the paper should be accepted and I concur.
Decision: Accept (poster)