Non-backtracking Graph Neural Networks
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.
Seonghyun Park, Narae Ryu, Gahee Kim, Dongyeop Woo, Se-Young Yun, Sungsoo Ahn
# Non-Backtracking Graph Neural Network

###### Abstract

The celebrated message-passing updates for graph neural networks allow the representation of large-scale graphs with local and computationally tractable updates. However, the local updates suffer from backtracking, i.e., a message flows through the same edge twice and revisits 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 for downstream tasks. In this work, we propose to resolve such a redundancy via the non-backtracking graph neural network (NBA-GNN) that updates a message without incorporating the message from the previously visited node. We further 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. We empirically verify the effectiveness of our NBA-GNN on long-range graph benchmark and transductive node classification problems.

## 1 Introduction

Recently, graph neural networks (GNNs) (Kipf and Welling, 2016; Hamilton et al., 2017; Xu et al., 2019) have shown great success in various applications, including but not limited to, molecular property prediction (Gilmer et al., 2017) and community detection (Bruna and Li, 2017). Such success can be largely attributed to the message-passing structure of GNNs, which provides a computationally tractable way of incorporating the overall graph through iterative updates based on local neighborhoods. However, the message-passing structure also brings challenges due to the parallel updates and memory-less behavior of messages passed along the graph.

In particular, the message flow in a GNN is prone to backtracking, where the message from vertex \(i\) to vertex \(j\) isincorporated in the subsequent message from \(j\) to \(i\), e.g., Figure 1. Since the message-passing iteratively aggregates the information, the GNN inevitably encounters an exponential surge in the number of message flows, proportionate to the vertex degrees. This issue is compounded by backtracking, which accelerates the growth of message flows with redundant information.

Interestingly, despite these challenges, non-backtracking updates--a potential solution--have been largely overlooked in the existing GNN research, while they have been thoroughly investigated for non-GNN message-passing algorithms or random walks (Fitzner and van der Hofstad, 2013; Rappaport et al., 2017) (Figure 1). For example, given a pair of vertices \(i,j\), the belief propagation algorithm (Pearl, 1982) forbids an \(i\to j\) message from incorporating the \(j\to i\) message. Another example is the non-backtracking random walks (Alon et al., 2007) which are non-Markovian walks

Figure 1: Message flows of simple (above) and non-backtracking (below) updates.
that do not traverse the same edge twice and revisit the previous node. Such classic algorithms have demonstrated great success in applications like probabilistic graphical model inference and stochastic block models (Massoulie, 2014; Bordenave et al., 2015; Abbe & Sandon, 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 a graph model (Bordenave et al., 2015).

**Contribution.** In this work, we propose the non-backtracking graph neural network (NBA-GNN) which employs non-backtracking updates on the messages, i.e., forbids the message from vertex \(i\) to vertex \(j\) from being incorporated in the message from vertex \(j\) to \(i\). To this end, we associate the hidden features with transitions between a pair of vertices, e.g., \(h_{j\to i}\), and update them from features associated with non-backtracking transitions, e.g., \(h_{k\to j}\) for \(k\neq i\).

To motivate our work, we formulate "message flows" as the sensitivity of a GNN with respect to walks in the graph. Then we explain how the message flows are redundant; the GNN's sensitivity of a walk with backtracking transitions can be covered by that of other non-backtracking walks. We explain how the redundancy is harmful to the GNN since the number of walks increases exponentially as the number of layers grows and the GNN becomes insensitive to a particular walk information. Hence, reducing the redundancy by only considering non-backtracking walks would benefit the message-passing updates to better recognize each walk's information. We further make a connection from our sensitivity analysis to the over-squashing phenomenon for GNNs (Topping et al., 2022; Black et al., 2023; Di Giovanni et al., 2023) in terms of access time.

Furthermore, we analyze our NBA-GNNs from the perspective of over-squashing and their expressive capability 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 distinguish between graphs originating from the Erdos-Renyi model or the SBM, from the results of (Stephan & Massoulie, 2022; Bordenave et al., 2015). Unlike traditional GNNs that operate on adjacency matrices and necessitate an average degree of at least \(\Omega(\log n)\), NBA-GNN demonstrates the ability to perform node classification with a substantially lower average degree bound of \(\omega(1)\) and \(n^{o(1)}\). 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 state-of-the-art performance on the long-rage graph benchmark. For the node classification tasks, 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 the 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-GNNs to show state-of-the-art performance on the long-range graph benchmark and consistently improve over the conventional GNNs across various tasks.

## 2 Related works

**Non-backtracking algorithms.** Non-backtracking updates have been considered by many classical algorithms (Newman, 2013; Kempton, 2016). For example, belief propagation (Pearl, 1982) infers the marginal distribution on probabilistic graphical models and has demonstrated success for tree graphs (Kim & Pearl, 1983) and graphs with large girth (Murphy et al., 2013). Non-backtracking random walks have shown superior performance over simple random walks in terms of mixing time for regular expander graphs (Alon et al., 2007). They have been shown to yield better recovery for stochastic block models. Furthermore, the non-backtracking matrix 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 and Massoulie, 2022). These properties have also been proven to enhance the performance of non-backtracking PageRank (Arrigo et al., 2019).

**Analyzing over-squashing of GNNs.** When a node receives information from a \(k\)-hop neighbor node, an exponential number of messages passes through node representations with fixed-sized vectors. This leads to the loss of information, denoted as _over-squashing_(Alon and Yahav, 2020), and has been formalized in terms of sensitivity (Topping et al., 2022; Di Giovanni et al., 2023). In particular, the sensitivity term is defined as the Jacobian of a node feature at a layer of the GNN with respect to the input node. Researchers have shown how the over-squashing phenomenon can be analyzed by bounding the sensitivity term via curvature (Topping et al., 2022), effective resistance (Black et al., 2023), or access time of random walks (Di Giovanni et al., 2023).

To resolve this issue, prior works have considered graph rewiring methods that add or remove edges to mitigate over-squashing by creating an optimal computation graph. One approach is using topological metrics, e.g., curvature (Topping et al., 2022) or effective resistance (Black et al., 2023). Another line of work uses global aspects, e.g., connecting a virtual global node (Cai et al., 2023) or using graph Transformers (Ying et al., 2021; Kreuzer et al., 2021; Rampasek et al., 2022; Shirzad et al., 2023; He et al., 2023).

**Expressivity of GNNs with the Weisfeiler-Lehman (WL) test.** In the past few years, researchers have conducted significant studies on various aspects of the expressive power of GNNs. One line of research involves comparing GNNs with the WL test (Leman and Weisfeiler, 1968) to assess their expressiveness. For instance, Xu et al. (2019) demonstrated that MPNNs are at best as powerful as the WL test and introduced the graph isomorphism network (GIN), which matches the representational power of the WL test.

**Expressivity of GNNs for the stochastic block model (SBM).** Furthermore, certain studies have analyzed the expressive power of GNNs using variations of the SBM (Holland et al., 1983). Fountoulakis et al. (2022) 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. (2022) investigated the effects of graph convolutions within a network on the XOR-CSBM. These works focused primarily on the probability distribution of node features, such as the distance between the means of feature vectors.

## 3 Non-backtracking graph neural network

### Motivation from sensitivity analysis

We first explain how the conventional message-passing updates are prone to backtracking. To this end, consider a simple, undirected graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) where \(\mathcal{N}(i)\) denotes the neighbor of the node \(i\). Each node \(i\in\mathcal{V}\) is associated with a feature \(x_{i}\). Then the conventional graph neural networks (GNNs), i.e., message-passing neural networks (MPNNs) (Gilmer et al., 2017), iteratively updates the \(t\)-th layer node-wise hidden feature \(h_{i}^{(t)}\) as follows:

\[h_{i}^{(t+1)}=\phi^{(t)}\bigg{(}h_{i}^{(t)},\Big{\{}\psi^{(t)}\left(h_{i}^{(t )},h_{j}^{(t)}\right):j\in\mathcal{N}(i)\Big{\}}\,\bigg{)}, \tag{1}\]

where \(\phi^{(t)}\) and \(\psi^{(t)}\) are architecture-specific non-linear update and permutation invariant aggregation functions, respectively. Our key observation is that the message from the node feature \(h_{i}^{(t)}\) to the node feature \(h_{j}^{(t+1)}\) is reincorporated in the node feature \(h_{i}^{(t+2)}\), e.g., Figure 2(a) shows the computation graph of conventional GNNs where redundant messages are incorporated.

**Sensitivity analysis.** To concretely describe the backtracking nature of message-passing updates, we formulate the sensitivity of the final node feature \(h_{i}^{(T)}\) with respect to the input as follows:

\[\sum_{j\in\mathcal{V}}\frac{\partial h_{i}^{(T)}}{\partial h_{j}^{(0)}}=\sum _{s\in\mathcal{W}(i)}\prod_{t=1}^{T}\frac{\partial h_{s(t)}^{(t)}}{\partial h _{s(t-1)}^{(t-1)}}\,, \tag{2}\]

where \(h_{i}^{(0)}=x_{i}\), \(\mathcal{W}(i)\) denotes the set of \(T\)-step walks ending at node \(i\), and \(s(t)\) denotes the \(t\)-th node in the walk \(s\in\mathcal{W}(i)\). Intuitively, this equation shows that a GNN with \(T\) layer recognizes
the graph via aggregation of random walks with length \(T\). Our key observation from Equation (2) is on how the feature \(h_{i}^{(T)}\) is insensitive to the information to an initial node feature \(h_{j}^{(0)}\), due to the information being "squashed" by the aggregation over the exponential number of walks \(\mathcal{W}(i)\). A similar analysis has been conducted on how a node feature \(h_{i}^{(T)}\) is insensitive to the far-away initial node feature \(h_{j}^{(0)}=x_{j}\), i.e., the over-squashing phenomenon of GNNs (Topping et al., 2022).

**Redundancy of walks with backtracking.** In particular, a walk \(s\) randomly sampled from \(\mathcal{W}(i)\) is likely to contain a transition that backtracks, i.e., \(s(t)=s(t+2)\) for some \(t<T\). Then the walk \(s\) would be redundant since the information is contained in two other walks in \(\mathcal{W}(i)\): \(s(0),\ldots,s(t+1)\) and \(s(0),\ldots,s(t+1),s(t)=s(t+2),s(t+3),...,s(T)\). See Figure 2 for an illustration. This idea leads to the conclusion that non-backtracking walks, i.e., walks that do not contain backtracking transitions, are sufficient to express the information in the walks \(\mathcal{W}(i)\). Since the exponential number of walks in \(\mathcal{W}(i)\) causes the GNN to be insensitive to a particular walk information, it makes sense to design a non-backtracking GNN that is sensitive to the constrained set of non-backtracking walks. We note that similar concepts of redundancy for GNNs have been studied in prior works (Jia et al., 2020; Chen et al., 2022).

**Relation to over-squashing.** Finally, we point out an intriguing motivation for our work in terms of over-squashing. In particular, we note that Di Giovanni et al. (2023) analyzed the lower bound for the Jacobian obstruction that measures the degree of over-squashing in terms of access time with respect to a simple random walk. They conclude that the degree of over-squashing, i.e., the size of Jacobian obstruction, is higher for a pair of nodes with longer access time.

Hence, to design a GNN architecture robust to the over-squashing phenomenon, one could (i) propose a random walk that has shorter access time in general for a pair of nodes in the graph and (ii) design a GNN that aligns with the optimized random walk. Non-backtracking random walks have been empirically shown and believed to generally yield faster access time than simple random walks (Lin and Zhang, 2019; Fasino et al., 2023). Hence, one could aim to design a GNN architecture that aligns with the non-backtracking random walks.

However, to the best of our knowledge, there is no formal proof of scenarios where non-backtracking random walks yield smaller access time. As a motivating example, we provide a theoretical result comparing the access time of non-backtracking and simple random walks for tree graphs.

**Proposition 1**.: _Given a tree \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) and a pair of nodes \(i,j\in\mathcal{V}\), the access time of begrudgingly backtracking random walk is equal or smaller than that of a simple random walk, where the equality holds if and only if the random walk length is 1._

The begrudgingly backtracking random walk (Rappaport et al., 2017) modifies non-backtracking random walks to remove "dead ends" for tree graphs. Please refer to Appendix A for the proof.

### Method description

In this section, we present our **Non-BA**cktracking GNNs (NBA-GNN) with the motivation described in Section 3.1. Given an undirected graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\), our NBA-GNN associates a pair of hidden features \(h_{i\to j}^{(t)},h_{j\to i}^{(t)}\) for each edge \(\{i,j\}\). Then the non-backtracking message passing update for a hidden feature \(h_{j\to i}^{(t)}\) is defined as follows:

\[h_{j\to i}^{(t+1)}=\phi^{(t)}\bigg{(}h_{j\to i}^{(t)};\Big{\{}\psi^{(t)} \left(h_{k\to j}^{(t)},h_{j\to i}^{(t)}\right):k\in\mathcal{N}(j)\setminus\{ i\}\Big{\}}\,\bigg{)}, \tag{3}\]

where \(\phi^{(t)}\) and \(\psi^{(t)}\) are backbone-specific non-linear update and permutation-invariant aggregation functions at the \(t\)-th layer, respectively. For example, \(\psi^{(t)}\) and \(\phi^{(t)}\) are multi-layer perceptron and summation over a set for the graph isomorphism network (Xu et al., 2019), respectively. Given the

Figure 2: Two non-backtracking walks (right) are sufficient to express information in a walk with backtracking transition.
update in Equation (3), one can observe that the message \(h^{(t)}_{i\to j}\) is never incorporated in the message \(h^{(t+1)}_{j\to i}\), and hence the update is free from backtracking.

**Initialization and node-wise aggregation of messages.** The message at the \(0\)-th layer \(h^{(0)}_{i\to j}\) is initialized by encoding the node features \(x_{i},x_{j}\), and the edge feature \(e_{ij}\) using a non-linear function \(\phi\). After updating hidden features for each edge based on Equation (3), we apply permutation-invariant pooling over all the messages for graph-wise predictions. Since we use hidden features for each edge, we construct the node-wise predictions at the final layer as follows:

\[h_{i}=\sigma\left(\rho\left\{h^{(T)}_{j\to i}:j\in\mathcal{N}(i) \right\},\rho\left\{h^{(T)}_{i\to j}:j\in\mathcal{N}(i)\right\} \right), \tag{4}\]

where \(\sigma\) is a non-linear aggregation function with different weights for incoming edges \(j\to i\) and outgoing edges \(i\to j\), \(\rho\) is a non-linear aggregation function invariant to the permutation of nodes in \(\mathcal{N}(i)\). We provide a computation graph of NBA-GNNs in Figure 2(b) to summarize our algorithm.

**Begrudgingly backtracking update.** While the messages from our update are resistant to backtracking, a message \(h^{(t)}_{j\to i}\) may get trapped in node \(i\) for the special case when \(\mathcal{N}(i)=\{j\}\). To resolve this issue, we introduce a simple trick coined begrudgingly backtracking update (Rappaport et al., 2017) that updates \(h^{(t+1)}_{i\to j}\) using \(h^{(t)}_{j\to i}\) only when \(\mathcal{N}(i)=\{j\}\). We empirically verify the effectiveness of begrudgingly backtracking updates in Section 5.3.

**Implementation.** To better understand our NBA-GNN, we provide an example of non-backtracking message-passing updates with a GCN backbone (Kipf and Welling, 2016), coined NBA-GCN. The message update at the \(t\)-th layer of NBA-GCN can be written as follows:

\[h^{(t+1)}_{j\to i}=h^{(t)}_{j\to i}+\sigma_{\text{GCN}}\left( \frac{1}{|\mathcal{N}(j)|-1}\textbf{W}^{(t)}\sum_{k\in\mathcal{N}(j)\setminus \{i\}}h^{(t)}_{k\to j}\right), \tag{5}\]

where \(\sigma_{\text{GCN}}\) is an element-wise nonlinear function, e.g., rectified linear unit (Agarap, 2018), \(\textbf{W}^{(t)}\) is the weight matrix, and the messages are normalized by their population \(|\mathcal{N}(j)|-1\).

## 4 Theoretical analysis

In this section, we analyze the proposed NBA-GNN framework. To be specific, we show that (a) our NBA-GNN improves the upper bound for sensitivity-based measures of GNN over-squashing and (b) NBA-GNNs can detect the underlying structure of SBMs even for very sparse graphs.

### Sensitivity analysis on over-squashing

We first analyze how NBA-GNNs alleviate the over-squashing issue. To this end, following Topping et al. (2022), we use the Jacobian of node-wise output with respect to another node initial feature as

Figure 4: Begrudgingly backtracking update (solid).

Figure 3: Computation graph of typical GNN (a) and NBA-GNN predicting node “0”. (a) For typical GNNs, redundant messages in typical GNNs increase size of the computation graph. (b) NBA-GNN assigns a pair of features for each edge updates them via non-backtracking updates. For node-wise prediction, e.g., for “0”, at the last layer, we aggregate messages on the edges connected to the node.
a way to assess over-squashing effect. We first derive the Jacobian quantification of over-squashing for the NBA-GNNs, and then demonstrate that the upper bound for Jacobian is larger than that of the conventional GNNs derived by Topping et al. (2022).

To derive our analysis, we introduce the non-backtracking matrix \(B\in\{0,1\}^{2|\mathcal{E}|\times 2|\mathcal{E}|}\) and the incidence matrix \(C\in\mathbb{R}^{2|\mathcal{E}|\times|\mathcal{V}|}\) which describe the NBA-GNN message-passing 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_{(\ell\to k),(j\to i)}=\begin{cases}1&\text{if }k=j,\ell\neq i\\ 0&\text{otherwise}\end{cases},\qquad C_{(k\to j),i}=\begin{cases}1&\text{if }j=i \text{ or }k=i\\ 0&\text{otherwise}\end{cases}.\]

We also let \(D\) denote the degree matrix of NBA-GNN counting the number of outgoing edges for each edge, i.e., it is a diagonal matrix with \(D_{(j\to i),(j\to i)}=\sum_{\ell\to k}B_{(j\to i),(\ell\to k)}\) for each index \(j\to i\). Next, we define \(\widehat{B}\) as the normalized non-backtracking matrix augmented with self-loops, i.e., \(\widehat{B}=(D+I)^{-\frac{1}{2}}(B+I)(D+I)^{-\frac{1}{2}}\). Finally, we let \(\tilde{C}\) denote a matrix where \(\tilde{C}_{(k\to j),i}=C_{(k\to j),i}+C_{(j\to k),i}\). Then, one obtains the following sensitivity bound of NBA-GNN.

**Lemma 1**.: _Consider two nodes \(i,j\in\mathcal{V}\) with distance \(T\) given a \((T-1)\)-layer NBA-GNN as described in Equation (3) and Equation (4). Suppose \(|\nabla\phi^{(t)}|,|\nabla\sigma|\leq\alpha\), \(|\nabla\psi^{(t)}|,|\nabla\rho|\leq\beta\), and \(|\nabla\phi|\leq\gamma\) for \(0\leq t<T\). Then the following holds:_

\[\left\|\frac{\partial h_{j}}{\partial x_{i}}\right\|\leq(\alpha\beta)^{T} \gamma(\tilde{C}^{\top}\widehat{B}^{(T-1)}\tilde{C})_{j,i}.\]

We provide the proof in Appendix B. Lemma 1 states how _the over-squashing effect is controlled by the power of \(\widehat{B}\)_. Consequently, one can infer that increasing the upper bound likely leads to mitigation of the GNN over-squashing effect (Topping et al., 2022).

From this motivation, we provide an analysis to support our claim on how the NBA-GNN suffers less from over-squashing effect due to its larger sensitivity bound.

**Theorem 1**.: _Let \(\widehat{A}\) denote the degree-normalized matrix. Then, for any pair of nodes \(i,j\in\mathcal{V}\) with distance \(T\), the sensitivity bound of NBA-GNN is larger than that of conventional GNNs (Topping et al., 2022), i.e., \((\tilde{C}^{\top}\widehat{B}^{T-1}\tilde{C})_{j,i}\geq(\widehat{A}^{T})_{j,i}\). For \(d\)-regular graphs, \((\tilde{C}^{\top}\widehat{B}^{T-1}\tilde{C})_{j,i}\) decays slower by \(O(d^{-T})\), while \((\widehat{A}^{T})_{j,i}\) decays with \(O((d+1)^{-T})\)._

Note that \((\alpha\beta)^{T}(\widehat{A}^{T})_{j,i}\) provides an upper bound for the sensitivity term in conventional GNNs (Topping et al., 2022). We provide the proof in Appendix B. Our proof is based on comparing the degree-normalized number of non-backtracking and simple walks from node \(i\) to node \(j\).

### Expressive power of NBA-GNN in the lens of SBMs

In the literature on the expressive capabilities of GNNs, comparisons with the well-known \(k\)-WL test are common. However, even when certain models surpass the \(k\)-WL test in performance, evaluating their relative merits remains a nontrivial task. Furthermore, due to the substantial performance gap between the 1-WL and 3-WL tests, many algorithms fall into a range between these two tests, making it more difficult to compare them with each other. 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 studies have turned to spectral analysis of GNNs. From a spectral viewpoint, GNNs can be seen as functions of the eigenvectors and eigenvalues of the given graph. NT & Meahara (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 measure 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 eigenvalues and the corresponding adjacency matrix eigenvectors play a pivotal role in establishing the fundamental limits of community detection in SBM, as evidenced by Abbe et al. (2015), Abbe & Sandon (2015), Hajek et al. (2016), Yun & Proutiere (2016), and Yun & Proutiere (2019).
The adjacency matrix exhibits a spectral separation property, and an eigenvector containing information about the assignments of the vertex community becomes apparent (Lei and Rinaldo, 2015). Furthermore, by analyzing the eigenvalues of the adjacency matrix, it is feasible to determine whether a graph originates from the Erdos-Renyi (ER) model or the SBM (Erdos et al., 2013; Avrachenkov et al., 2015). However, these spectral properties are particularly salient when the average degree of the graph satisfies \(\Omega(\log n)\). For graphs with average degrees \(o(\log n)\), vertices with higher degrees predominate, affecting eigenvalues and complicating the discovery of the underlying structure of the graph (Benaych-Georges et al., 2019).

In contrast, the non-backtracking matrix exhibits several advantageous properties even for constant-degree cases. In (Stephan and Massoulie, 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 satisfies \(\omega(1)\) and \(n^{o(1)}\). Furthermore, Bordenave et al. (2015) have demonstrated that by inspecting the eigenvalues of the non-backtracking matrix, it is possible to discern whether a graph originates from the ER model or the SBM, even when the graph's average degree remains constant. This capability sets NBA-GNNs apart and enhances their performance in both node and graph classification tasks, especially in sparse settings. These lines of reasoning lead to the formulation of the following theorem.

**Theorem 2**.: _(**Informal**) Assume that the average degree in the stochastic block model satisfies the conditions of being at least \(\omega(1)\) and \(n^{o(1)}\). In such a scenario, the NBA-GNN can map from graph \(\mathcal{G}\) to node labels._

**Theorem 3**.: _(**Informal**) Suppose we have a pair of graphs with a constant average degree, one generated from the stochastic block model and the other from the Erdos-Renyi model. In this scenario, the NBA-GNN is capable of distinguishing between them._

For an in-depth exploration of this argument, please refer to Appendix C. The rationale behind these valuable properties of the non-backtracking matrix \(B\) in sparse scenarios lies in the fact that the matrix \(B^{k}\) exhibits similarity to the \(k\)-hop adjacency matrix, while \(A^{k}\) is mainly influenced by high-degree vertices. For these reasons, NBA-GNNs would outperform traditional GNNs in both node and graph classification tasks, particularly in sparse graph environments.

## 5 Experiment

In this section, we assess the effectiveness of NBA-GNNs across multiple benchmarks on graph classification, graph regression, and node classification tasks. Our method shows competitive performance compared to graph Transformers within long-range graph benchmarks, and robust improvements in handling transductive node classification tasks. We also conduct ablation studies to verify our method, and provide experimental details in Appendix D.

\begin{table}
\begin{tabular}{l c c c c c} \hline \hline \multirow{2}{*}{**Model**} & \multicolumn{2}{c}{**Peptides-func**} & \multicolumn{2}{c}{**Peptides-struct**} & \multicolumn{2}{c}{**Pascal VOC-SP**} \\ \cline{2-5}  & AP \(\uparrow\) & Imp. & MAE \(\downarrow\) & Imp. & F1 \(\uparrow\) & Imp. \\ \hline GCN & 0.5930 \(\pm\) 0.0023 & & 0.3496 \(\pm\) 0.0013 & & 0.1268 \(\pm\) 0.0006 & \\ + NBA & 0.6951 \(\pm\) 0.0024 & +17\% & 0.2656 \(\pm\) 0.0009 & +22\% & 0.2537 \(\pm\) 0.0054 & +100\% \\ + NBA+LapPE & **0.7206 \(\pm\) 0.0028** & +22\% & **0.2472 \(\pm\) 0.0008** & +29\% & **0.3005 \(\pm\) 0.0010** & +137\% \\ \hline GIN & 0.5498 \(\pm\) 0.0079 & & 0.3547 \(\pm\) 0.0045 & & 0.1265 \(\pm\) 0.0076 & \\ + NBA & 0.6961 \(\pm\) 0.0045 & +27\% & 0.2534 \(\pm\) 0.0025 & +29\% & 0.3040 \(\pm\) 0.0119 & +140\% \\ + NBA+LapPE & **0.7071 \(\pm\) 0.0067** & +29\% & **0.2424 \(\pm\) 0.0010** & +32\% & **0.3223 \(\pm\) 0.0010** & +155\% \\ \hline GatedGCN & 0.5864 \(\pm\) 0.0077 & & 0.3420 \(\pm\) 0.0013 & & 0.2873 \(\pm\) 0.0219 & \\ + NBA & 0.6429 \(\pm\) 0.0062 & +10\% & 0.2539 \(\pm\) 0.0011 & +26\% & 0.3910 \(\pm\) 0.0010 & +36\% \\ + NBA+LapPE & **0.6982 \(\pm\) 0.0014** & +19\% & **0.2466 \(\pm\) 0.0012** & +28\% & **0.3969 \(\pm\) 0.0027** & +38\% \\ \hline \hline \end{tabular}
\end{table}
Table 1: Comparison of conventional MPNNs and GNNs in the long-range graph benchmark, with and without Laplacian positional encoding. We also denote the relative improvement by Imp.
### Long-range graph benchmark

The long-range graph benchmark (LRGB) (Dwivedi et al., 2022) is a set of tasks that require learning long-range interactions. We validate our method using three datasets from the LRGB benchmark: graph classification (Peptides-func), graph regression (Peptides-struct), and node classification (PascalVOC-SP). We use performance scores from (Dwivedi et al., 2022) and from each baseline papers: subgraph based GNNs (Abu-El-Haija et al., 2019; Michel et al., 2023; Giusti et al., 2023), graph Transformers (Kreuzer et al., 2021; Rampasek et al., 2022; Shirzad et al., 2023; He et al., 2023), and graph rewiring methods (Gasteiger et al., 2019; Gutteridge et al., 2023). For NBA-GNNS and NBA-GNNs with bergudingly backtracking, we report the one with better performance. Furthermore, LapPE, i.e., Laplacian positional encoding (Dwivedi et al., 2020), is applied, as it enhances 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 and Welling, 2016), GIN (Xu et al., 2019), and GatedGCN (Bresson and Laurent, 2017). Furthermore, even against a variety of baselines in Table 2, at least one NBA-GNNs shows competitive performance with the best baseline in LRGB. Also, it is noteworthy that the improvement of NBA-GNNs is higher in dense graphs, PascalVOC-SP having an average degree of 8 while Peptides-func, Peptides-struct has an average degree of 2.

### Transductive node classification tasks

We conduct experiments on three citation networks (Cora, CiteSeer, and Pubmed) (Sen et al., 2008), and three heterophilic datasets (Texas, Wisconsin, and Cornell) (Pei et al., 2019) for transductive node classification. In our experiments, we employed various GNN architectures (Kipf and Welling, 2016; Hamilton et al., 2017; Velickovic et al., 2018; Li et al., 2016), along with their corresponding NBA versions, as illustrated in Table 3. The results indicate that the NBA operation improves the performance of all GNN variants. Specifically, it demonstrates significant enhancements, particularly on heterophilic datasets. Given that related nodes in heterophilic graphs are often widely

\begin{table}
\begin{tabular}{l l c c c} \hline \hline
**Method** & **Model** & \begin{tabular}{c} Peptides-func \\ AP \\ \end{tabular} & \begin{tabular}{c} Peptides-struct \\ MAE \(\downarrow\) \\ \end{tabular} & 
\begin{tabular}{c} VOC-SP \\ F1 \\ \end{tabular} \\ \hline \multirow{4}{*}{GNNs} & GCN & \(0.5930\pm 0.0023\) & \(0.3496\pm 0.0013\) & \(0.1268\pm 0.0060\) \\  & GIN & \(0.5498\pm 0.0079\) & \(0.3547\pm 0.0045\) & \(0.1265\pm 0.0076\) \\  & GatedGCN & \(0.5869\pm 0.0077\) & \(0.3420\pm 0.0013\) & \(0.2873\pm 0.0219\) \\  & GatedGCN+PE & \(0.6069\pm 0.0045\) & \(0.3357\pm 0.0066\) & \(0.2860\pm 0.0085\) \\ \hline \multirow{4}{*}{Subgraph GNNs} & MixHop-GCN & \(0.6592\pm 0.0066\) & \(0.2921\pm 0.0023\) & \(0.2506\pm 0.0133\) \\  & MixHop-GCN+LapPE & \(0.6843\pm 0.0049\) & \(0.2614\pm 0.0023\) & \(0.2218\pm 0.0174\) \\  & PathNN & \(0.6816\pm 0.0046\) & \(0.2545\pm 0.0032\) & - \\  & CIN++ & \(0.6569\pm 0.0117\) & \(0.2523\pm 0.0013\) & - \\ \hline \multirow{4}{*}{Transformers} & Transformer+LapPE & \(0.6326\pm 0.0126\) & \(0.2529\pm 0.0016\) & \(0.2694\pm 0.0098\) \\  & GraphGPS+LapPE & \(0.6535\pm 0.0041\) & \(0.2500\pm 0.0005\) & \(0.3748\pm 0.0119\) \\  & SAN+LapPE & \(0.6384\pm 0.0012\) & \(0.2683\pm 0.0043\) & \(0.3230\pm 0.0039\) \\  & Explorer & \(0.6527\pm 0.0043\) & \(0.2481\pm 0.0007\) & \(0.3966\pm 0.0207\) \\  & Graph MLP-Mixer/ViT & \(0.6970\pm 0.0080\) & \(0.2449\pm 0.0016\) & - \\ \hline \multirow{4}{*}{Rewiring methods} & DIGI+MPNN & \(0.6469\pm 0.0019\) & \(0.3173\pm 0.0067\) & \(0.2824\pm 0.0039\) \\  & DIGI+MPNN+LapPE & \(0.6530\pm 0.0056\) & \(0.2616\pm 0.0018\) & \(0.2921\pm 0.0038\) \\  & DRw-GCN+LapPE & \(0.7150\pm 0.0044\) & \(0.2536\pm 0.0015\) & \(0.1851\pm 0.0022\) \\  & DRw-GIN+LapPE & \(0.7126\pm 0.0045\) & \(0.2606\pm 0.0014\) & \(0.2692\pm 0.0059\) \\  & DRw-GatedGCN+LapPE & \(0.6977\pm 0.0026\) & \(0.2539\pm 0.0067\) & \(0.3314\pm 0.0024\) \\ \hline \multirow{4}{*}{**NBA-GNNs (Ours)**} & NBA-GCN & \(0.6951\pm 0.0024\) & \(0.2656\pm 0.0009\) & \(0.2537\pm 0.0054\) \\  & NBA-GCN+LapPE & \(0.7270\pm 0.0028\) & \(0.2472\pm 0.0088\) & \(0.3005\pm 0.0010\) \\ \cline{1-1}  & NBA-GIN & \(0.6961\pm 0.0045\) & \(0.2775\pm 0.0057\) & \(0.3040\pm 0.0119\) \\ \cline{1-1}  & NBA-GIN+LapPE & \(0.7071\pm 0.0077\) & \(0.2424\pm 0.0010\) & \(0.3223\pm 0.0063\) \\ \cline{1-1}  & NBA-GatedGCN & \(0.6429\pm 0.0062\) & \(0.2539\pm 0.0011\) & \(0.3910\pm 0.0010\) \\ \cline{1-1}  & NBA-GatedGCN+LapPE & \(0.6982\pm 0.0014\) & \(0.2466\pm 0.0012\) & \(0.3969\pm 0.0277\) \\ \hline \hline \end{tabular}
\end{table}
Table 2: Evaluation of NBA-GNN on the LRGB benchmark. We color the first-, second- and third-best results. Performance within a standard deviation of one another is considered equal. Non-reported values are denoted by -.
separated (Zheng et al., 2022), the ability of NBA-GNN to alleviate over-squashing plays a vital role in classifying nodes in such scenarios.

### Ablation studies

Here, we 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. We use hyper-parameters for GCN from Tonshoff et al. (2023).

Non-backtracking vs. backtracking GNNs.We first verify whether the performance improvements indeed stem from the non-backtracking updates. To this end, we compare our NBA-GNN with the backtracking variant, termed BA-GNN, which similarly assigns a pair of hidden features for each edge but allows backtracking update, i.e., use \(h_{i\to j}^{(\ell)}\) for updating \(h_{j\to i}^{(\ell+1)}\). We report the corresponding result in Figures 4(a) and 4(b). Here, one can observe how NBA-GNN outperforms the BA-GNN consistently with varying numbers of layers. Intriguingly, one can also observe that BA-GNN outperforms the naive backbone, i.e., GCN, consistently.
graph classification tasks on SBMs. Additionally, we demonstrate that NBA-GNNs achieve competitive performance on the LRGB benchmark and outperform conventional GNNs across various tasks.

**Limitations.** The space complexity of our framework is larger than the conventional GNNs. It creates \(2|\mathcal{E}|\) messages considering directions, and \(\sum_{i\in\mathcal{V}}\binom{d_{i}}{d_{2}}\) connections between them where \(d_{i}\) is the degree of a node \(i\). Therefore, investigation of space complexity reduction for our work would be an interesting future work.

**Ethics Statement.** The authors are committed to upholding the ICLR Code of Ethics and maintaining the highest ethical standards in research and scholarly activities. Additionally, it is crucial to acknowledge the potential ethical considerations associated with the utilization of our model. Although the model can offer valuable insights and advantages, there exists a possibility of misuse or unintended consequences. For instance, it could be exploited to extract sensitive information, such as affiliations or political inclinations, from social networks. Therefore, it is important to apply such models carefully and actively work towards preventing any adverse side effects. Responsible implementation is essential to ensure that the potential benefits of our work are maximized while minimizing any potential risks or adverse implications.

**Reproducibility.** The code for all experiments conducted in this paper is included in the accompanying zip file. We also provide comprehensive proofs for the theoretical analysis in Appendices A, B, and C. Further information about the experiments, including details about the datasets and models, can be found in Section 5. For a deeper dive into experiment specifics such as hyperparameter settings, please refer to Appendix D.
