論文の概要: Sampling on Metric Graphs
- arxiv url: http://arxiv.org/abs/2512.02175v1
- Date: Mon, 01 Dec 2025 20:11:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-12-03 21:04:45.591469
- Title: Sampling on Metric Graphs
- Title（参考訳）: Metric Graphsのサンプリング
- Authors: Rajat Vadiraj Dwaraknath, Lexing Ying,
- Abstract要約: 距離グラフ上でブラウン運動をシミュレートする最初のアルゴリズムを提案する。
また,距離グラフをサンプリングするための最初のアルゴリズムも取得する。
提案アルゴリズムは,DuMuXの有限体積法における安定限界よりもはるかに大きい時間ステップで,安定なシミュレーションを実行できる。
- 参考スコア（独自算出の注目度）: 15.544139471623623
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Metric graphs are structures obtained by associating edges in a standard graph with segments of the real line and gluing these segments at the vertices of the graph. The resulting structure has a natural metric that allows for the study of differential operators and stochastic processes on the graph. Brownian motions in these domains have been extensively studied theoretically using their generators. However, less work has been done on practical algorithms for simulating these processes. We introduce the first algorithm for simulating Brownian motions on metric graphs through a timestep splitting Euler-Maruyama-based discretization of their corresponding stochastic differential equation. By applying this scheme to Langevin diffusions on metric graphs, we also obtain the first algorithm for sampling on metric graphs. We provide theoretical guarantees on the number of timestep splittings required for the algorithm to converge to the underlying stochastic process. We also show that the exit probabilities of the simulated particle converge to the vertex-edge jump probabilities of the underlying stochastic differential equation as the timestep goes to zero. Finally, since this method is highly parallelizable, we provide fast, memory-aware implementations of our algorithm in the form of custom CUDA kernels that are up to ~8000x faster than a GPU implementation using PyTorch on simple star metric graphs. Beyond simple star graphs, we benchmark our algorithm on a real cortical vascular network extracted from a DuMuX tissue-perfusion model for tracer transport. Our algorithm is able to run stable simulations with timesteps significantly larger than the stable limit of the finite volume method used in DuMuX while also achieving speedups of up to ~1500x.
- Abstract（参考訳）: メトリックグラフ(Metric graph)は、標準グラフのエッジを実線のセグメントに関連付け、グラフの頂点でこれらのセグメントをグルリングすることによって得られる構造である。
結果として得られる構造は、グラフ上の微分作用素と確率過程の研究を可能にする自然な計量を持つ。
これらの領域におけるブラウン運動は、その生成器を用いて理論的に広く研究されている。
しかし、これらのプロセスをシミュレートする実用的なアルゴリズムに関する作業は少ない。
ユーラー・丸山法に基づく確率微分方程式の離散化を時間分解することで、計量グラフ上のブラウン運動をシミュレートする最初のアルゴリズムを導入する。
このスキームを計量グラフ上のランゲヴィン拡散に適用することにより、計量グラフ上でサンプリングする最初のアルゴリズムも得られる。
アルゴリズムが基礎となる確率過程に収束するのに要する時間ステップ分割の回数に関する理論的保証を提供する。
また、シミュレーション粒子の出口確率は、時間ステップがゼロになるにつれて基礎となる確率微分方程式の頂点端ジャンプ確率に収束することを示した。
最後に,本手法は並列化性が高いため,単純な星距離グラフ上でPyTorchを用いたGPU実装よりも最大8000倍高速なカスタムCUDAカーネルの形で,高速なメモリ対応実装を提供する。
単純な星グラフの他に、トレーサー輸送のためのDuMuX組織灌流モデルから抽出した実際の皮質血管網にアルゴリズムをベンチマークする。
提案アルゴリズムは,DuMuXの有限体積法における安定限界よりもはるかに大きな時間ステップで安定なシミュレーションを実行できると同時に,最大1500倍の高速化を実現することができる。
関連論文リスト
- Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs [14.049529046098607]
スパースグラフに対する一般ランダムウォークカーネル(RWK)の非バイアス近似のための最初の線形時間複雑性ランダム化アルゴリズムを提案する。
提案手法は,大規模グラフ上での効率的な計算において,最大$mathbf27timesの高速化を実現する。
論文 参考訳（メタデータ） (2024-10-14T10:48:46Z) - Sparse Training of Discrete Diffusion Models for Graph Generation [45.103518022696996]
SparseDiffは、ほとんど全ての大きなグラフがスパースであるという観察に基づく、新しい拡散モデルである。
エッジのサブセットを選択することで、SparseDiffは、ノイズ発生過程とノイズ発生ネットワーク内のスパースグラフ表現を効果的に活用する。
本モデルでは,小規模・大規模両方のデータセットにおいて,複数のメトリクスにわたる最先端性能を示す。
論文 参考訳（メタデータ） (2023-11-03T16:50:26Z) - Scalable Bayesian Structure Learning for Gaussian Graphical Models Using Marginal Pseudo-likelihood [2.312692134587988]
連続時間(生死)および離散時間(可逆ジャンプ)マルコフ連鎖モンテカルロ(MCMC)アルゴリズムを開発し、グラフ空間の後方を効率的に探索する。
アルゴリズムは巨大なグラフ空間にスケールし、1000以上のノードを持つグラフの並列探索を可能にする。
論文 参考訳（メタデータ） (2023-06-30T20:37:40Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - Algorithms for perturbative analysis and simulation of quantum dynamics [0.0]
我々はダイソン級数とマグナス展開の両方を計算・利用するための汎用アルゴリズムを開発した。
モデルパラメータ空間の領域における忠実度を近似するためにこれらのツールの使い方を実証する。
計算前のステップを,元法よりも少ない項数で多変数展開問題と表現できることを示す。
論文 参考訳（メタデータ） (2022-10-20T21:07:47Z) - Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via
GDPA Linearization [59.87663954467815]
アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。
本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。
実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
論文 参考訳（メタデータ） (2021-09-10T07:01:15Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - A Study of Performance of Optimal Transport [16.847501106437534]
本稿では,ネットワークの単純化と拡張パスに基づくアルゴリズムが,数値行列スケーリング法より一貫して優れていることを示す。
古典的なKuhn-Munkresアルゴリズムを改良した新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-05-03T20:37:05Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。