論文の概要: The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions
- arxiv url: http://arxiv.org/abs/2510.17714v2
- Date: Mon, 27 Oct 2025 16:20:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-28 15:28:14.425189
- Title: The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions
- Title（参考訳）: マーク付きエッジウォーク:グラフ分割のサンプリングのための新しいMCMCアルゴリズム
- Authors: Atticus McWhorter, Daryl DeFord,
- Abstract要約: 可変分布下でのグラフ分割空間からのサンプリングのための新しいMCMCアルゴリズムを提案する。
このウォークは、縁がマークされた木々の空間で動作し、計算可能な遷移確率を可能にする。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Novel Markov Chain Monte Carlo (MCMC) methods have enabled the generation of large ensembles of redistricting plans through graph partitioning. However, existing algorithms such as Reversible Recombination (RevReCom) and Metropolized Forest Recombination (MFR) are constrained to sampling from distributions related to spanning trees. We introduce the marked edge walk (MEW), a novel MCMC algorithm for sampling from the space of graph partitions under a tunable distribution. The walk operates on the space of spanning trees with marked edges, allowing for calculable transition probabilities for use in the Metropolis-Hastings algorithm. Empirical results on real-world dual graphs show convergence under target distributions unrelated to spanning trees. For this reason, MEW represents an advancement in flexible ensemble generation.
- Abstract（参考訳）: 新しいマルコフ・チェイン・モンテカルロ法(MCMC)により、グラフ分割による計画の再制限の大規模なアンサンブルの生成が可能となった。
しかし、RevReCom(Reversible Recombination)やMetropolized Forest Recombination(MFR)といった既存のアルゴリズムは、分布木に関する分布のサンプリングに制約されている。
本稿では,グラフ分割の空間からチューナブルな分布をサンプリングする新しいMCMCアルゴリズムであるマークエッジウォーク(MEW)を紹介する。
このウォークは縁がマークされた木々の空間で動作し、メトロポリス・ハスティングスアルゴリズムで使用するための計算可能な遷移確率を可能にする。
実世界の双対グラフに関する実証的な結果は、分散木とは無関係な対象分布下での収束を示す。
このため、MEWはフレキシブルアンサンブル生成の進歩を表している。
関連論文リスト
- 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) - Scaling up Dynamic Edge Partition Models via Stochastic Gradient MCMC [33.08344607564694]
エッジ分割モデル (EPM) は静的グラフ構造データから重なり合うコミュニティ構造を抽出する生成モデルである。
多くの魅力的な性質があるにもかかわらず、EMMの推論は通常、マルコフ連鎖モンテカルロ (MCMC) 法を用いて行われ、大規模なネットワークデータに適用されないようにしている。
論文 参考訳（メタデータ） (2024-02-29T15:19:35Z) - M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning
of Mixture Graph Matching and Clustering [57.947071423091415]
本稿では,理論収束を保証する学習自由度アルゴリズムであるM3Cを提案する。
我々は、新しいエッジワイド親和性学習と擬似ラベル選択を組み込んだ教師なしモデルUM3Cを開発した。
提案手法は,最先端のグラフマッチングと混合グラフマッチングとクラスタリングの手法を精度と効率の両面で優れている。
論文 参考訳（メタデータ） (2023-10-27T19:40:34Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - Spanning tree methods for sampling graph partitions [0.7658085223797904]
分割プランはグラフの連結部分集合へのバランスの取れた分割と見なすことができる。
RevReComは、ReComが元々近似するために設計された単純で自然な分布に収束する。
論文 参考訳（メタデータ） (2022-10-04T06:18:33Z) - Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
本稿では,元のグラフを表す小さなグラフの作成に焦点をあてる。
我々は、元のグラフを受容体の分布とみなし、受容体が同様の分布を持つ小さなグラフを合成することを目的としている。
論文 参考訳（メタデータ） (2022-06-28T02:10:05Z) - A new perspective on probabilistic image modeling [92.89846887298852]
本稿では,密度推定,サンプリング,トラクタブル推論が可能な画像モデリングのための新しい確率論的手法を提案する。
DCGMMは、CNNのように、ランダムな初期条件からSGDによってエンドツーエンドに訓練することができる。
本研究は,近年のPCおよびSPNモデルと,推論,分類,サンプリングの観点から比較した。
論文 参考訳（メタデータ） (2022-03-21T14:53:57Z) - Bayesian Structure Learning with Generative Flow Networks [85.84396514570373]
ベイズ構造学習では、データから有向非巡回グラフ(DAG)上の分布を推定することに興味がある。
近年,ジェネレーティブ・フロー・ネットワーク(GFlowNets)と呼ばれる確率モデルのクラスが,ジェネレーティブ・モデリングの一般的なフレームワークとして紹介されている。
DAG-GFlowNetと呼ばれる本手法は,DAGよりも後方の正確な近似を提供する。
論文 参考訳（メタデータ） (2022-02-28T15:53:10Z) - Bayesian structure learning and sampling of Bayesian networks with the R
package BiDAG [0.0]
BiDAGはマルコフ連鎖モンテカルロ法(MCMC)を実装し、ベイジアンネットワークの構造学習とサンプリングを行う。
このパッケージには、最大 a posteriori (map) グラフを検索し、データが与えられた後続分布からグラフをサンプリングするツールが含まれている。
論文 参考訳（メタデータ） (2021-05-02T14:42:32Z) - Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
ハイブリッドモンテカルロ(Hybrid Monte Carlo)は、複素連続分布からサンプリングする強力なマルコフ連鎖モンテカルロ法である。
本稿では,SurVAEフローを用いたモンテカルロ法の拡張に基づく新しい手法を提案する。
本稿では,統計学,計算物理学,機械学習など,様々な分野におけるアルゴリズムの有効性を実証し,代替アルゴリズムと比較した改良点を考察する。
論文 参考訳（メタデータ） (2021-02-04T02:21:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。