math.PRApr 15, 2026

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

Authors: Luca Avena, Gianmarco Bet, Lars Schroeder, Clara Stegehuis

Organizations: Universit`a degli Studi di Firenze, Italy · University of Twente, Netherlands

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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.

Figures & tables

Figure 1: Illustration of the transition rates of a node2vec random walk.
Figure 2: Illustration of the in-and out-neighbors of a fixed wedge ww
Figure 3: Example graph for studying bistochasticity on the directed edges
Figure 4: Example for a non-regular graph where ( WDB ) is fulfilled
More in this topic

Markov Models

Markov models describe systems that evolve probabilistically, with future behavior determined by the current state and transition rules.

See all 93 papers

Explore similar work

CardsList
Jul 12, 2026

Learning from Local Walks on Dynamic Graphs with Bandit Feedback

We study stochastic multi-armed bandits on dynamic graphs, where arms correspond to the vertices of a network with time-varying edges. In this setting, the learner is restricted to local movement, selecting only its current node or an immediate neighbor at each round. This constraint decouples best-arm identification from exploitation: even after the optimal arm is identified, the learner may remain unable to reach it through the evolving topology. We identify a process-agnostic structural condition, based on sliding-window mixing, that ensures the graph's intrinsic walk remains stable for both exploration and navigation. Under this regime, we analyze a family of local explore-then-commit algorithms and establish sublinear expected regret. Our framework includes a reward-aware strategy, for which we prove a worst-case safety theorem and a separate performance gain theorem.

Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni +1

Department of Computer Science, University of Colorado, Boulder, CO 80309, USA · INRIA, Paris, France

Multi-Armed BanditsGraph BanditsExploration-Exploitation TradeoffBandit Learning
AskPDF
Oct 20, 2025

The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions

Novel Markov Chain Monte Carlo (MCMC) methods have enabled the generation of large ensembles of redistricting plans modeled as a graph partitioning problem. However, existing algorithms such as Reversible Recombination (RevReCom) and Metropolized Forest Recombination (MFR) have strong preferences for distributions related to the spanning tree measure. In this paper we introduce the Marked Edge Walk (MEW), a novel Markov chain proposal for sampling from the space of graph partitions. The walk operates on the space of spanning trees with marked edges, allowing for calculable transition probabilities for use in the Metropolis-Hastings algorithm. Empirical results on real-world dual graphs show convergence under a broad class of target distributions less constrained by spanning tree counts, including policy-based distributions, such as competitiveness on New Hampshire that are independent of spanning trees, and compactness and partisan symmetry distributions on New Hampshire and Texas that, while related to spanning trees, can now be properly targeted with a smaller degree of spanning tree bias, which represents an advancement in flexible ensemble generation.

Atticus McWhorter, Daryl DeFord

Department of Mathematics, Dartmouth College, 1 College Street, Hanover, 03755, NH, USA · Department of Mathematics and Statistics, Vassar College, 124 Raymond Avenue, Poughkeepsie, 12604, NY, USA

Markov Chain Monte CarloGraph Partitioning
AskPDF
Mar 5, 2026

Robust Node Affinities via Jaccard-Biased Random Walks and Rank Aggregation

Estimating node similarity is a fundamental task in network analysis and graph-based machine learning, with applications in clustering, community detection, classification, and recommendation. We propose TopKGraphs, a method based on start-node-anchored random walks that bias transitions toward nodes with structurally similar neighborhoods, measured via Jaccard similarity. Rather than computing stationary distributions, walks are treated as stochastic neighborhood samplers, producing partial node rankings that are aggregated using robust rank aggregation to construct interpretable node-to-node affinity matrices. TopKGraphs provides a non-parametric, interpretable, and general-purpose representation of node similarity that can be applied in both network analysis and machine learning workflows. We evaluate the method on synthetic graphs (stochastic block models, Lancichinetti-Fortunato-Radicchi benchmark graphs), k-nearest-neighbor graphs from tabular datasets, and a curated high-confidence protein-protein interaction network. Across all scenarios, TopKGraphs achieves competitive or superior performance compared to standard similarity measures (Jaccard, Dice), a diffusion-based method (personalized PageRank), and an embedding-based approach (Node2Vec), demonstrating robustness in sparse, noisy, or heterogeneous networks. These results suggest that TopKGraphs is a versatile and interpretable tool for bridging simple local similarity measures with more complex embedding-based approaches, facilitating both data mining and network analysis applications.

Bastian Pfeifer, Michael G. Schimek

Institute for Medical Informatics, Statistics and Documentation, Medical University Graz, Austria.

Graph Representation Learning
AskPDF