論文の概要: Path convergence of Markov chains on large graphs
- arxiv url: http://arxiv.org/abs/2308.09214v2
- Date: Sun, 15 Oct 2023 16:35:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-18 03:59:10.575634
- Title: Path convergence of Markov chains on large graphs
- Title（参考訳）: 大きなグラフ上のマルコフ連鎖の経路収束
- Authors: Siva Athreya, Soumik Pal, Raghav Somani, Raghavendra Tripathi
- Abstract要約: グラフのサイズが無限大になるにつれて、プロセスのランダムな軌跡は測度値グラフの空間上の決定論的曲線に収束することを示す。
このアプローチの新たな特徴は、ある制限状態におけるメトロポリス連鎖に対して正確な指数収束速度を提供することである。
- 参考スコア（独自算出の注目度）: 3.693375843298262
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider two classes of natural stochastic processes on finite unlabeled
graphs. These are Euclidean stochastic optimization algorithms on the adjacency
matrix of weighted graphs and a modified version of the Metropolis MCMC
algorithm on stochastic block models over unweighted graphs. In both cases we
show that, as the size of the graph goes to infinity, the random trajectories
of the stochastic processes converge to deterministic curves on the space of
measure-valued graphons. Measure-valued graphons, introduced by Lov\'{a}sz and
Szegedy in \cite{lovasz2010decorated}, are a refinement of the concept of
graphons that can distinguish between two infinite exchangeable arrays that
give rise to the same graphon limit. We introduce new metrics on this space
which provide us with a natural notion of convergence for our limit theorems.
This notion is equivalent to the convergence of infinite-exchangeable arrays.
Under suitable assumptions and a specified time-scaling, the Metropolis chain
admits a diffusion limit as the number of vertices go to infinity. We then
demonstrate that, in an appropriately formulated zero-noise limit, the
stochastic process of adjacency matrices of this diffusion converges to a
deterministic gradient flow curve on the space of graphons introduced
in\cite{Oh2023}. A novel feature of this approach is that it provides a precise
exponential convergence rate for the Metropolis chain in a certain limiting
regime. The connection between a natural Metropolis chain commonly used in
exponential random graph models and gradient flows on graphons, to the best of
our knowledge, is new in the literature as well.
- Abstract（参考訳）: 有限非ラベルグラフ上の自然確率過程の2つのクラスを考える。
これらは重み付きグラフの隣接行列上のユークリッド確率最適化アルゴリズムと、重み付きグラフ上の確率ブロックモデル上のメトロポリスMCMCアルゴリズムの修正版である。
どちらの場合も、グラフのサイズが無限大になるにつれて、確率過程のランダムな軌跡は測度値グラフンの空間上の決定論的曲線に収束することを示す。
測度値グラフは lov\'{a}sz と szegedy によって \cite{lovasz2010decorated} で導入され、同じグラフェン極限をもたらす2つの無限交換可能な配列を区別できるグラフの概念を洗練したものである。
我々はこの空間の新しいメトリクスを導入し、極限定理に対する収束の自然な概念を提供する。
この概念は無限交換可能配列の収束と同値である。
適切な仮定と特定の時間スケーリングの下で、メトロポリス連鎖は、頂点の数が無限大になるにつれて拡散限界を認める。
次に、適切に定式化されたゼロノイズ極限において、この拡散の隣接行列の確率過程は、始点{oh2023} に導入されたグラトン空間上の決定論的勾配フロー曲線に収束することを示す。
このアプローチの新たな特徴は、ある制限状態におけるメトロポリス連鎖に対して正確な指数収束速度を提供することである。
指数的ランダムグラフモデルでよく使われる自然のメトロポリス連鎖とグラトン上の勾配流の間の関係は、我々の知る限りでは、文献でも新しいものである。
関連論文リスト
- Graph Generation via Spectral Diffusion [51.60814773299899]
本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGRASPを提案する。
具体的には、固有ベクトルと固有値のサンプリングにデノナイジングモデルを用い、グラフラプラシアン行列と隣接行列を再構成する。
我々の置換不変モデルは各ノードの固有ベクトルに連結することでノードの特徴を扱える。
論文 参考訳（メタデータ） (2024-02-29T09:26:46Z) - Generalized Graphon Process: Convergence of Graph Frequencies in
Stretched Cut Distance [30.279435887366578]
スパースグラフ列は、従来のカット距離の定義の下で自明なグラフオンに収束する。
我々は、スパースグラフ列の収束を記述するために、一般化グラフと拡張カット距離の概念を利用する。
その結果,スパースグラフ間の移動学習の可能性が示唆された。
論文 参考訳（メタデータ） (2023-09-11T06:34:46Z) - Curve Your Attention: Mixed-Curvature Transformers for Graph
Representation Learning [77.1421343649344]
本稿では,一定曲率空間の積を完全に操作するトランスフォーマーの一般化を提案する。
また、非ユークリッド注意に対するカーネル化されたアプローチを提供し、ノード数とエッジ数に線形に時間とメモリコストでモデルを実行できるようにします。
論文 参考訳（メタデータ） (2023-09-08T02:44:37Z) - Graphon Pooling for Reducing Dimensionality of Signals and Convolutional
Operators on Graphs [131.53471236405628]
グラフ空間における[0, 1]2の分割上のグラフとグラフ信号の誘導的グラフ表現を利用する3つの方法を提案する。
これらの低次元表現がグラフとグラフ信号の収束列を構成することを証明している。
我々は,層間次元減少比が大きい場合,グラノンプーリングは文献で提案した他の手法よりも有意に優れていることを観察した。
論文 参考訳（メタデータ） (2022-12-15T22:11:34Z) - Stochastic optimization on matrices and a graphon McKean-Vlasov limit [26.906770707395832]
同じ置換を用いて行と列の置換の下で不変である適当な関数の大きい対称行列の空間上の勾配降下を考える。
行列の次元が無限大になるにつれて、これらのランダム曲線の決定論的極限を確立する。
論文 参考訳（メタデータ） (2022-10-02T04:54:49Z) - High-dimensional limit theorems for SGD: Effective dynamics and critical
scaling [6.950316788263433]
我々は、勾配降下(SGD)の要約統計の軌跡に対する極限定理を証明する。
下記の有効弾道力学が人口減少の勾配流と一致するステップサイズにおける重要なスケーリング体制を示す。
この実効力学の固定点について、対応する拡散極限は極めて複雑であり、さらに退化することもある。
論文 参考訳（メタデータ） (2022-06-08T17:42:18Z) - Capturing Graphs with Hypo-Elliptic Diffusions [7.704064306361941]
ランダムウォークの分布はグラフラプラシアンを用いて定義された拡散方程式に従って進化することを示す。
この結果、テンソル値のグラフ作用素が新しくなり、これは下楕円グラフラプラシアン (Laplacian) と呼ばれる。
本手法は,長距離推論を必要とするデータセット上のグラフ変換器と競合するが,エッジ数では線形にしかスケールしないことを示す。
論文 参考訳（メタデータ） (2022-05-27T16:47:34Z) - Score-based Generative Modeling of Graphs via the System of Stochastic
Differential Equations [57.15855198512551]
本稿では,連続時間フレームワークを用いたグラフのスコアベース生成モデルを提案する。
本手法は, トレーニング分布に近い分子を生成できるが, 化学価数則に違反しないことを示す。
論文 参考訳（メタデータ） (2022-02-05T08:21:04Z) - Gradient flows on graphons: existence, convergence, continuity equations [27.562307342062354]
確率測度上のワッサーシュタイン勾配流は、様々な最適化問題に多くの応用を見出した。
辺重みの適当な関数のユークリッド勾配流は、グラノン空間上の曲線によって与えられる新しい連続極限に収束することを示す。
論文 参考訳（メタデータ） (2021-11-18T00:36:28Z) - Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
多層グラフクラスタリングは、グラフノードをカテゴリまたはコミュニティに分割することを目指しています。
与えられた多層グラフの層をクラスタリングに親しみやすい埋め込みを提案する。
実験の結果,本手法は著しい改善をもたらすことがわかった。
論文 参考訳（メタデータ） (2021-03-30T17:36:40Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。