論文の概要: node2vec or triangle-biased random walks: stationarity, regularity & recurrence

• arxiv url: http://arxiv.org/abs/2604.13681v1
• Date: Wed, 15 Apr 2026 10:02:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-16 20:38:32.477632
• Title: node2vec or triangle-biased random walks: stationarity, regularity & recurrence
• Title（参考訳）: node2vecまたは三角形バイアスランダムウォーク:定常性、規則性、再発
• Authors: Luca Avena, Gianmarco Bet, Lars Schroeder, Clara Stegehuis,
• Abstract要約: ノード2vecランダムウォークを有向エッジの状態空間へ持ち上げると、有向ウェッジが2つの異なるマルコフ表現をもたらすことを示す。 基礎となる有限あるいは無限グラフ上では、その不変測度のエルゴード性、可逆性、再帰性、キャラクタリゼーションを保証するのに十分である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.
• Abstract（参考訳）: node2vec ランダムウォーク(node2vec random walk)は、グラフの頂点集合上の非マルコフ的ランダムウォークであり、ネットワークの埋め込みと探索に広く用いられている。 このランダムウォークモデルは、3つのパラメータで定義され、それぞれがバックトラックの動きの確率を制御し、三角形内を移動し、残りの隣接ノードに移動する。 数学的観点からすると、node2vecランダムウォークは非バックトラックランダムウォークの非自明な一般化であり、2階マルコフ連鎖のクラスに属する。 アプリケーションで広く使われているにもかかわらず、その長期動作についてはほとんど知られていない。 本研究の目的は、任意のグラフの基本的な性質を探求することである。 この目的のために、ノード2vecランダムウォークを有向エッジの状態空間へ持ち上げると、その漸近解析の鍵となる2つの異なるマルコフ表現が得られることを示す。 これらの表現を用いることで、下層の有限あるいは無限グラフ上で、不変測度のエルゴード性、可逆性、再帰性、キャラクタリゼーションを保証するのに十分な条件が見つかる。 ここでは、ノード2vecランダムウォークの動作が、非バックトラックランダムウォークとは大きく異なることを論じる。 後者はビスト確率性により自然辺マルコフ表現を使用するとき任意のグラフを単純化するが、前者は自然辺マルコフ表現を使用するとき正則グラフを単純化する。 注目すべきことに、この表現はグラフが正則であることと、ある重み付けされたユーリアー性条件が成立することを明らかにしている。

関連論文リスト

• Stationary distribution of node2vec random walks on household models [0.0]
  node2vecランダムウォークを地域構成の世帯モデルグラフ上で検討する。 歩行パラメータを調整することにより、静止分布は、均一、サイズ偏り、あるいは単純なランダムな歩行定常分布の間で補間可能であることを示す。
  論文  参考訳（メタデータ） (2025-02-26T10:48:59Z)
• Generating Graphs via Spectral Diffusion [48.70458395826864]
  本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGGSDを提案する。 合成グラフと実世界のグラフの両方に関する広範な実験は、最先端の代替品に対する我々のモデルの強みを実証している。
  論文  参考訳（メタデータ） (2024-02-29T09:26:46Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  離散グラフオートエンコーダ(DGAE)という新しいフレームワークを導入する。 まず、置換同変オートエンコーダを用いてグラフを離散潜在ノード表現の集合に変換する。 2番目のステップでは、離散潜在表現の集合をソートし、特別に設計された自己回帰モデルを用いてそれらの分布を学習する。
  論文  参考訳（メタデータ） (2023-06-13T12:40:39Z)
• The PWLR Graph Representation: A Persistent Weisfeiler-Lehman scheme with Random Walks for Graph Classification [0.6999740786886536]
  グラフ表現のための永続Weisfeiler-Lehmanランダムウォークスキーム(PWLR)。 我々はWeisfeiler-Lehmanプロシージャの多くの変種を一般化する。
  論文  参考訳（メタデータ） (2022-08-29T08:50:37Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• Het-node2vec: second order random walk sampling for heterogeneous multigraphs embedding [0.9084022224205381]
  Het-node2vecは、異種グラフを埋め込むノード2vecアルゴリズムの拡張である。 我々はHet-node2vecがノードラベルおよびエッジ予測タスクにおける異種グラフの最先端手法に対して同等あるいは優れた性能を達成することを示す。
  論文  参考訳（メタデータ） (2021-01-05T09:38:02Z)
• Space-Time Correspondence as a Contrastive Random Walk [47.40711876423659]
  我々は,ビデオから構築した時空間グラフにおけるリンクの予測として対応をキャストした。 ペアの類似性がランダムウォークの遷移確率を定義する表現を学習する。 我々は、エッジドロップアウトと呼ばれる手法と、テスト時の自己教師付き適応が、オブジェクト中心の対応の転送をさらに改善することを示した。
  論文  参考訳（メタデータ） (2020-06-25T17:56:05Z)
• Learning Representations using Spectral-Biased Random Walks on Graphs [18.369974607582584]
  このプロセスにおける確率バイアスが、プロセスによって選択されたノードの品質にどの程度影響するかを調査する。 我々は、この近傍を正規化ラプラス行列として表されるノードの近傍部分グラフのスペクトルに基づく確率測度として簡潔に捉えた。 我々は,様々な実世界のデータセット上で,最先端ノード埋め込み技術に対する我々のアプローチを実証的に評価した。
  論文  参考訳（メタデータ） (2020-05-19T20:42:43Z)
• Continuous-time quantum walks in the presence of a quadratic perturbation [55.41644538483948]
  連続時間量子ウォークの特性を、$mathcalH=L + lambda L2$という形のハミルトン群で解決する。 低/高接続性および/または対称性を持つパラダイムモデルであるため、サイクル、完全、およびスターグラフを考える。
  論文  参考訳（メタデータ） (2020-05-13T14:53:36Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。