論文の概要: Monte Carlo Random Walk Kernel
- arxiv url: http://arxiv.org/abs/2610.40956v1
- Date: Thu, 29 Oct 2026 20:36:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-02 22:05:31.490787
- Title: Monte Carlo Random Walk Kernel
- Title（参考訳）: モンテカルロランダムウォークカーネル
- Abstract要約: 本稿では,MCRWK (Monte Carlo Random Walk Kernel) について述べる。
カーネルの正規化により、MCRWKは共有ウォーク長をサンプリングし、入力グラフ上のランダムウォークを用いてそのコントリビューションを推定する。
我々は、グラフボイジャーに対するMCRWKと、合成および実グラフデータセットにおける古典的なRWK法を評価する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce the Monte Carlo Random Walk Kernel (MCRWK), an estimator whose per-pair cost is independent of graph size and derived directly from the random walk kernel (RWK) expansion. By normalizing the kernel coefficients, MCRWK samples a shared walk length and estimates its contribution using random walks on the input graphs. This gives a simple way to approximate RWK without constructing the product graph. For a fixed expected walk length and efficient neighbor sampling, each pairwise estimate takes $O(m)$ time for $m$ Monte Carlo samples, allowing the sample budget to control the trade-off between runtime and accuracy. We evaluate MCRWK against Graph Voyagers and classical RWK methods on synthetic and real graph datasets. In the reported experiments on large synthetic graphs, MCRWK is faster than Graph Voyagers and, at matched runtime, more accurate. It also has the lowest Gram-matrix runtime on the five real datasets studied. Code and experiments are available at https://github.com/arslan-yam/random_walk_kernels_computations
- Abstract（参考訳）: 本稿では,モンテカルロランダムウォークカーネル (MCRWK) について紹介する。これは1対あたりのコストがグラフサイズに依存しず,ランダムウォークカーネル (RWK) の拡張から直接導出される推定器である。
カーネル係数の正規化により、MCRWKは共有歩行長をサンプリングし、入力グラフ上のランダムウォークを用いてその寄与を推定する。
これにより、積グラフを構築することなく、RWKを近似する簡単な方法が得られる。
固定されたウォーク長と効率的な隣人サンプリングでは、それぞれが$O(m)$時間でモンテカルロのサンプルをサンプリングし、サンプル予算が実行時と精度の間のトレードオフを制御する。
我々は、グラフボイジャーに対するMCRWKと、合成および実グラフデータセットにおける古典的なRWK法を評価する。
大規模な合成グラフに関する報告された実験では、MCRWKはグラフボイジャーよりも高速で、一致したランタイムではより正確である。
また、調査された5つの実際のデータセット上では、Gram-matrixランタイムが最低である。
コードと実験はhttps://github.com/arslan-yam/random_walk_kernels_computationsで公開されている。
関連論文リスト
- Graph Random Features for Scalable Gaussian Processes [52.89901965157282]
離散入力空間上のスケーラブルなガウス過程へのグラフランダム特徴(GRF)の適用について検討する。
我々は、(穏やかな仮定の下で) GRF に対するベイズ的推論が、正確なカーネルに対して$O(N3)$のノード数に対して$O(N3/2)$の時間複雑性を楽しむことを証明した。
論文 参考訳（メタデータ） (2025-09-03T20:13:23Z) - Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs [7.434126318858966]
我々はマルコフ・チェイン・モンテカルロ(MCMC)における履歴駆動型目標(HDT)フレームワークを提案し、離散状態空間におけるランダムウォークアルゴリズムを改善する。
また,HDTは,現在の状態と提案状態の局所的な情報のみを必要とすることにより,軽量な実装を保っていることを示す。
グラフサンプリング実験は、一貫したパフォーマンス向上を示し、メモリ効率の高いLRUキャッシュは、大規模な汎用グラフへのスケーラビリティを保証する。
論文 参考訳（メタデータ） (2025-05-23T18:46:10Z) - Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs [14.049529046098607]
スパースグラフに対する一般ランダムウォークカーネル(RWK)の非バイアス近似のための最初の線形時間複雑性ランダム化アルゴリズムを提案する。
提案手法は,大規模グラフ上での効率的な計算において,最大$mathbf27timesの高速化を実現する。
論文 参考訳（メタデータ） (2024-10-14T10:48:46Z) - Efficient Sampling on Riemannian Manifolds via Langevin MCMC [51.825900634131486]
本稿では,Gibs 分布 $d pi* = eh d vol_g$ over aian manifold $M$ via (geometric) Langevin MCMC。
この結果は、$pi*$ が非指数的であり、$Mh$ が負のリッチ曲率を持つような一般的な設定に適用できる。
論文 参考訳（メタデータ） (2024-02-15T22:59:14Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳（メタデータ） (2022-08-18T09:19:01Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。