pith. sign in

arxiv: 2604.13681 · v1 · submitted 2026-04-15 · 🧮 math.PR · cs.LG

node2vec or triangle-biased random walks: stationarity, regularity & recurrence

Luca Avena , Gianmarco Bet , Lars Schroeder , Clara Stegehuis This is my paper

Pith reviewed 2026-05-10 12:51 UTC · model grok-4.3

classification 🧮 math.PR cs.LG
keywords node2vecrandom walksgraph regularityEulerianityMarkov chainsstationarityrecurrencenetwork embedding
0
0 comments X p. Extension

The pith

Lifting node2vec random walks to directed wedges shows a graph is regular precisely when it meets a weighted Eulerianity condition.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The node2vec random walk is a second-order process on graph vertices that uses three parameters to control backtracking, triangle steps, and other moves. Lifting it to the space of directed wedges produces a Markov chain whose stationarity and reversibility properties can be analyzed directly. This wedge representation simplifies exactly on regular graphs and yields an if-and-only-if link between regularity and a weighted Eulerianity condition on the graph. The same lifting supplies mild conditions that guarantee ergodicity, reversibility, recurrence, and an explicit invariant measure. A reader would care because the result supplies both a probabilistic characterization of regular graphs and concrete tools for studying the long-run behavior of a widely used embedding method whose properties had remained largely uncharted.

Core claim

The node2vec random walk admits two Markovian lifts, one to directed edges and one to directed wedges. The wedge lift turns out to be the natural state space on regular graphs; its reversibility and stationary measure exist if and only if the graph satisfies a weighted Eulerianity condition. Under mild assumptions that make the lifted chains ergodic, this yields an explicit invariant measure for the original walk and establishes recurrence or transience on finite and infinite graphs. The same analysis shows that the walk behaves qualitatively differently from the non-backtracking walk, which simplifies on arbitrary graphs via its edge representation.

What carries the argument

The Markov chain obtained by lifting the node2vec walk onto the space of directed wedges, whose transition probabilities incorporate the triangle bias and whose stationary distribution encodes regularity via a weighted Eulerianity condition.

If this is right

  • The long-run distribution of the node2vec walk is given explicitly by the stationary measure of the wedge chain once regularity holds.
  • Ergodicity and recurrence of the walk follow from standard Markov-chain criteria applied to the wedge lift.
  • On non-regular graphs the edge lift remains available but does not simplify the stationary measure in the same way.
  • The equivalence supplies a probabilistic test for regularity that can be checked by simulating the wedge chain.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Simulating the wedge chain and testing whether its empirical measure satisfies the Eulerianity condition could serve as a statistical probe for regularity in large networks.
  • For embedding algorithms on irregular graphs, the edge lift may be preferable to the wedge lift to avoid the regularity mismatch.
  • The same lifting technique might extend to other second-order walks and yield analogous characterizations for other graph properties such as degree regularity or bipartiteness.
  • On infinite regular lattices the wedge representation could be used to compute return probabilities or mixing times in closed form.

Load-bearing premise

The underlying finite or infinite graph satisfies mild conditions that make the lifted chains on directed edges and directed wedges ergodic and reversible.

What would settle it

A concrete finite regular graph together with node2vec parameters for which the wedge-lifted chain fails to possess a stationary distribution that satisfies the weighted Eulerianity condition.

Figures

Figures reproduced from arXiv: 2604.13681 by Clara Stegehuis, Gianmarco Bet, Lars Schroeder, Luca Avena.

Figure 1
Figure 1. Figure 1: Illustration of the transition rates of a node2vec random walk. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of the in-and out-neighbors of a fixed wedge [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Example graph for studying bistochasticity on the directed edges [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Example for a non-regular graph where (WDB) is fulfilled [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
read the original abstract

The node2vec random walk is a non-Markovian random walk on the vertex set of a graph, widely used for network embedding and exploration. This random walk model is defined in terms of three parameters which control the probability of, respectively, backtracking moves, moves within triangles, and moves to the remaining neighboring nodes. From a mathematical standpoint, the node2vec random walk is a nontrivial generalization of the non-backtracking random walk and thus belongs to the class of second-order Markov chains. Despite its widespread use in applications, little is known about its long-run behavior. The goal of this paper is to begin exploring its fundamental properties on arbitrary graphs. To this aim, we show how lifting the node2vec random walk to the state spaces of directed edges and directed wedges yields two distinct Markovian representations which are key for its asymptotic analysis. Using these representations, we find mild sufficient conditions on the underlying finite or infinite graph to guarantee ergodicity, reversibility, recurrence and characterization of the invariant measure. As we discuss, the behavior of the node2vec random walk is drastically different compared to the non-backtracking random walk. While the latter simplifies on arbitrary graphs when using its natural edge Markovian representation thanks to bistochasticity, the former simplifies on regular graphs when using its natural wedge Markovian representation. Remarkably, this representation reveals that a graph is regular if and only if a certain weighted Eulerianity condition holds.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 0 minor

Summary. The paper lifts the node2vec random walk (a second-order Markov chain controlled by backtracking, triangle-bias, and other-neighbor parameters) to Markov chains on directed edges and directed wedges. Under mild sufficient conditions on finite or infinite graphs, the lifted chains are ergodic and reversible, the invariant measure is characterized, and recurrence is established. The central result is that the wedge-lifted chain satisfies a weighted Eulerianity condition for all wedges if and only if the underlying graph is regular; this explains why the node2vec walk simplifies on regular graphs (in contrast to the non-backtracking walk, which simplifies via its edge representation on arbitrary graphs).

Significance. If the lifting derivations and equivalence hold, the work supplies the first rigorous long-run analysis of node2vec, a model widely used in network embedding yet previously lacking probabilistic foundations. The regularity-Eulerianity characterization is a clean algebraic insight that may prove useful beyond this model, and the explicit contrast with non-backtracking walks clarifies when each second-order walk admits simple stationary behavior.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and insightful summary of our work, as well as for recognizing its significance in providing the first rigorous long-run analysis of node2vec walks. We appreciate the recommendation for minor revision and will address any editorial or clarification points in the revised manuscript.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's central result—that a graph is regular if and only if a weighted Eulerianity condition holds on the lifted directed-wedge chain—follows from an explicit algebraic derivation: the transition probabilities of the wedge-lifted Markov chain are written down, the global balance equations are formed, and these equations are shown to be satisfied for every wedge precisely when all vertex degrees are identical. This equivalence is obtained directly from the definitions of the node2vec transition rules and the standard lifting construction; it does not rely on any fitted parameters, self-referential definitions, or load-bearing self-citations. The mild ergodicity assumptions are used only to guarantee existence of the invariant measure so that the balance equations can be stated; they do not enter the algebraic equivalence itself. The derivation is therefore self-contained and independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based solely on the abstract, the central claims rest on the domain assumptions that the node2vec walk admits Markovian lifts to directed-edge and directed-wedge spaces and that standard ergodicity theorems apply to these lifted chains on finite or infinite graphs. No free parameters or invented entities are introduced.

axioms (2)
  • domain assumption The node2vec random walk admits a Markovian representation on the space of directed edges.
    This lift is invoked to perform the asymptotic analysis described in the abstract.
  • domain assumption The node2vec random walk admits a Markovian representation on the space of directed wedges.
    This second lift is key to the regularity characterization and simplification on regular graphs.

pith-pipeline@v0.9.0 · 5566 in / 1430 out tokens · 59836 ms · 2026-05-10T12:51:54.132506+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    Aldous and J

    D. Aldous and J. A. Fill.Reversible Markov Chains and Random Walks on Graphs. 2002

    work page 2002

  2. [2]

    Non-backtracking random walks mix faster

    N. Alon et al. “Non-backtracking random walks mix faster”.Communications in Contemporary Math- ematics09.04 (2007), pp. 585–603

    work page 2007

  3. [3]

    Barot, S

    A. Barot, S. Bhamidi, and S. Dhara.Community detection using low-dimensional network embedding algorithms. arXiv:2111.05267. 2021

    work page arXiv 2021

  4. [4]

    CUTOFF FOR NON-BACKTRACKING RANDOM WALKS ON SPARSE RANDOM GRAPHS

    A. Ben-Hamou and J. Salez. “CUTOFF FOR NON-BACKTRACKING RANDOM WALKS ON SPARSE RANDOM GRAPHS”.The Annals of Probability(2017)

    work page 2017

  5. [5]

    Lifting Markov chains to speed up mixing

    F. Chen, L. Lov´ asz, and I. Pak. “Lifting Markov chains to speed up mixing”. In:Proceedings of the thirty-first annual ACM symposium on Theory of Computing. STOC ’99. New York, NY, USA: Association for Computing Machinery, 1999, pp. 275–281

    work page 1999

  6. [6]

    Exploring complex networks through random walks

    L. d. F. Costa and G. Travieso. “Exploring complex networks through random walks”.Physical Review E75.1 (2007), p. 016102

    work page 2007

  7. [7]

    On the spectral analysis of second-order Markov chains

    P. Diaconis and L. Miclo. “On the spectral analysis of second-order Markov chains”.Annales de la facult´ e des sciences de Toulouse Math´ ematiques22.3 (2013), pp. 573–621. 23

    work page 2013

  8. [8]

    Hitting times for second-order random walks

    D. Fasino, A. Tonetto, and F. Tudisco. “Hitting times for second-order random walks”.European Journal of Applied Mathematics34.4 (2023), pp. 642–666

    work page 2023

  9. [9]

    Non-backtracking random walk

    R. Fitzner and R. van der Hofstad. “Non-backtracking random walk”.Journal of Statistical Physics 150.2 (2013), pp. 264–284

    work page 2013

  10. [10]

    Glover et al.Effects of Backtracking on PageRank

    C. Glover et al.Effects of Backtracking on PageRank. arXiv:2211.13353. 2026

    work page arXiv 2026

  11. [11]

    ItemRank: A Random-Walk Based Scoring Algorithm for Recommender En- gines

    M. Gori and A. Pucci. “ItemRank: A Random-Walk Based Scoring Algorithm for Recommender En- gines”. In:International Joint Conference on Artificial Intelligence. 2007

    work page 2007

  12. [12]

    node2vec: Scalable Feature Learning for Networks

    A. Grover and J. Leskovec. “node2vec: Scalable Feature Learning for Networks”. In:Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD ’16. New York, NY, USA: Association for Computing Machinery, 2016, pp. 855–864

    work page 2016

  13. [13]

    Reversibility of the non-backtracking random walk

    J. Hermon. “Reversibility of the non-backtracking random walk”.Annales de l’Institut Henri Poincar´ e, Probabilit´ es et Statistiques55.4 (2019), pp. 2295–2319

    work page 2019

  14. [14]

    Convergence of a second order Markov chain

    S. Hu and L. Qi. “Convergence of a second order Markov chain”.Applied Mathematics and Computation 241 (2014), pp. 183–192

    work page 2014

  15. [15]

    Non-backtracking random walks and a weighted Ihara’s theorem

    M. Kempton. “Non-backtracking random walks and a weighted Ihara’s theorem”.Open journal of Discrete Mathematics06 (2016), pp. 207–226

    work page 2016

  16. [16]

    Lyons and Y

    R. Lyons and Y. Peres.Probability on Trees and Networks. Cambridge Series in Statistical and Prob- abilistic Mathematics. Cambridge: Cambridge University Press, 2017

    work page 2017

  17. [17]

    A Random Walks View of Spectral Segmentation

    M. Meil˘ a and J. Shi. “A Random Walks View of Spectral Segmentation”. en. In:International Work- shop on Artificial Intelligence and Statistics. PMLR, 2001, pp. 203–208

    work page 2001

  18. [18]

    Analysis of node2vec random walks on networks

    L. Meng and N. Masuda. “Analysis of node2vec random walks on networks”.Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences476.2243 (2020), p. 20200447

    work page 2020

  19. [19]

    Sampling directed graphs with random walks

    B. Ribeiro et al. “Sampling directed graphs with random walks”. In:2012 Proceedings IEEE INFO- COM. 2012, pp. 1692–1700

    work page 2012

  20. [20]

    Stationary distribution of node2vec random walks on household mod- els

    L. Schroeder and C. Stegehuis. “Stationary distribution of node2vec random walks on household mod- els”.Journal of Complex Networks13.5 (2025), cnaf028

    work page 2025

  21. [21]

    Random matrices, nonbacktracking walks, and orthogonal polynomials

    S. Sodin. “Random matrices, nonbacktracking walks, and orthogonal polynomials”.Journal of Math- ematical Physics48 (2007), pp. 123503–123503. 24

    work page 2007