When exploring a network using a classical random walk, a walker at node $A$ steps to an adjacent node $B$. On the very next step, there is a high probability that the walker will step right back to node $A$. This immediate back-and-forth oscillation is known as tottering.
While simple to implement, standard random walks suffer from severe sampling redundancy because they spend significant computational budget trapped in these local, uninformative loops. Across graph kernels, embedding frameworks, and decentralized optimization, this redundancy introduces noise, inflates similarity metrics, and slows down convergence.
To solve this, a growing body of research replaces standard walks with non-backtracking graph exploration. By enforcing a simple constraint—prohibiting a walker from immediately returning to the node it just visited—these methods unlock dramatic improvements in sampling efficiency, representation expressiveness, and spectral accuracy.
The Tottering Problem and Structural Noise
To understand why standard random walks fail, consider how information propagates through a network. As noted by Bison (2025), graph-based information propagation frequently moves back and forth across the same edges, introducing uninformative noise and bias into extracted features. In representation learning, this behavior can cause over-smoothing, making distinct node features indistinguishable.
This redundancy is particularly destructive in walk-based graph kernels, which measure the similarity between two graphs by counting their shared walk sequences. As Bai et al. (2023) and Bai et al. (2024) observe, classical random walks repeatedly capture redundant information from paths or edges connected to the same vertex. This tottering effect artificially inflates similarity scores based on local edge density rather than reflecting meaningful, large-scale structural patterns (Bai et al. (2015); Mutzel (2012)).
From a computational perspective, traditional graph exploration via random walks results in high sampling redundancy due to frequent node revisits and biased path distributions (Chen et al. (2019)). This inefficiency forces algorithms to collect excessively large datasets to achieve accurate graph representations.
The Non-Backtracking Constraint
The core mechanism of non-backtracking graph exploration is a simple topological constraint: given a path sequence $\dots \to v_{t-1} \to v_t \to v_{t+1}$, the walker is restricted such that $v_{t+1} \neq v_{t-1}$.
Standard Walk (Tottering): A ⇄ B ⇄ A ⇄ B
Non-Backtracking Walk: A → B → C → D
This constraint acts as a minimal form of short-term memory or directional momentum. As Loukas (2019) explains, preventing an agent from immediately returning to its previous position encourages forward momentum and forces the exploration of new nodes.
By eliminating immediate reversals, the algorithm avoids generating invalid or redundant samples, leading to faster convergence when estimating local structural properties (Chen et al. (2016)). Within a fixed sampling budget, a non-backtracking walk is guaranteed to explore a larger portion of the graph's unique structural paths (Wang (2024)).
Why It Works: Variance Reduction and Efficiency
The primary mathematical reason non-backtracking walks outperform standard walks is variance reduction. In any Monte Carlo sampling or optimization task over a graph, successive states in a standard random walk are highly correlated because the walker gets locally trapped.
Hu et al. (2022) proved this connection rigorously by bridging Markov Chain Monte Carlo (MCMC) theory and Stochastic Gradient Descent (SGD). They demonstrated that preventing an optimizer from immediately returning to a previously visited node reduces the asymptotic variance of gradient estimates, yielding a lower mean squared error during decentralized optimization over network graphs.
Researchers have extended this intuition to even stronger memory-driven constraints:
- Self-Repellent Walks: Doshi et al. (2024) showed that random walks designed to actively avoid previously visited nodes can achieve lower sampling variance than independent and identically distributed (i.i.d.) sampling, because the walk's history forces uniform coverage of the graph topology.
- Ensemble Repulsion: Instead of a single walker avoiding its own history, Reid et al. (2024) introduced a technique where an ensemble of walkers is forced to choose different paths at each step. This negative correlation between walkers universally reduces estimator variance across any graph topology.
- Antithetic Termination: Reid et al. (2023) achieved variance reduction in graph kernel approximations by negatively correlating the lengths of random walk pairs, ensuring efficient sampling of the underlying kernel space.
De-noising Graph Representations
By filtering out tottering paths, non-backtracking methods provide a cleaner, more expressive signal for machine learning models.
In graph classification and similarity matching, restricting walks from immediately backtracking ensures that the evaluated paths capture meaningful directional information and avoid redundant cycles (Matsui et al. (2008); Šnajder et al. (2013)). For instance, in inexact subgraph matching, backtrackless walks force the exploration of new structural paths, providing a robust estimation of higher-order structural context even in the presence of noise (Dutta et al. (2017)).
This structural clarity is equally vital for node embeddings and Graph Neural Networks (GNNs). Traditional random walks allow immediate backtracking, which introduces noise that tends to obscure the distinct boundaries between communities and makes it difficult to isolate critical bottleneck nodes (Jiang et al. (2018)). Enforcing non-backtracking constraints ensures that sampled sequences provide a diverse and informative view of the connectivity structure (Chen et al. (2023)), enhancing the information density of path-based graph representations (Wang et al. (2024)).
A similar principle applies to matrix estimation and collaborative filtering on sparse graphs. To prevent estimation bias and redundant information loops, the algorithm designed by Yu et al. (2022) constructs rooted breadth-first search trees where each vertex along a path is unique. This structure ensures that the neighborhood aggregation process avoids backtracking entirely, maintaining the statistical independence of observations during similarity calculations.
Tighter Spectral Bounds in Loopy Graphs
Beyond sampling and embeddings, non-backtracking exploration fundamentally alters the mathematical tractability of graphical models. Standard graph algorithms rely on the adjacency matrix, which counts all paths—including those that endlessly backtrack through loops. In highly connected or loopy graphs, this overcounting distorts spectral approximations.
Saade et al. (2017) demonstrated that restricting path counting to non-backtracking walks significantly improves the tightness of upper bounds for partition functions in ferromagnetic systems like the Ising model. By shifting the mathematical focus from a node-based adjacency matrix to a non-backtracking operator (which tracks transitions between directed edges), the spectral approximation excludes local back-and-forth paths. This eliminates overcounting in loopy graphs while keeping the underlying linear algebra completely tractable.
Key Foundational Work
Extensions of marginalized graph kernels (2004) — contributed 2 concept elements to this direction.
Kernel on Bag of Paths For Measuring Similarity of Shapes (2007) — contributed 1 concept elements to this direction.