揭示node2vec随机游走的长期行为规律，解析其在图上的遍历性与平稳分布。
node2vec or triangle-biased random walks: stationarity, regularity & recurrence
- 通过有向边和有向楔子空间构建马尔可夫表示，分析node2vec的渐近性质。
- 在有限或无限图上给出保证遍历、可逆、常返性的温和条件。
- 发现正则图等价于加权欧拉性条件，揭示其与非回溯游走的本质差异。
node2vec随机游走是一种在图顶点集上的非马尔可夫随机游走，广泛用于网络嵌入与探索。该模型由三个参数控制：回溯、三角形内移动及剩余邻接节点移动的概率。从数学角度看，它是非回溯随机游走的非平凡推广，属于二阶马尔可夫链。尽管应用广泛，其长期行为尚不清楚。本文旨在探索其在任意图上的基本性质。为此，我们通过将node2vec随机游走提升到有向边和有向楔子状态空间，获得两种不同的马尔可夫表示，为渐近分析提供关键工具。利用这些表示，我们给出了在有限或无限图上保证遍历性、可逆性、常返性及不变测度刻画的温和充分条件。值得注意的是，与非回溯游走不同，后者在任意图上通过自然的边马尔可夫表示简化（得益于双随机性），而前者在正则图上通过自然的楔子马尔可夫表示简化。更惊人的是，该表示揭示了图是正则的当且仅当某个加权欧拉性条件成立。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。