論文の概要: Efficient Graph Matching for Correlated Stochastic Block Models
- arxiv url: http://arxiv.org/abs/2412.02661v1
- Date: Tue, 03 Dec 2024 18:36:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-04 15:41:50.172416
- Title: Efficient Graph Matching for Correlated Stochastic Block Models
- Title（参考訳）: 相関確率ブロックモデルに対する効率的なグラフマッチング
- Authors: Shuwen Chai, Miklós Z. Rácz,
- Abstract要約: 2つのバランスの取れたコミュニティを持つ相関ブロックモデルの学習問題について検討する。
我々の主な成果は、この設定におけるグラフマッチングのための最初の効率的なアルゴリズムである。
我々はこれを情報理論的に可能であれば、正確なグラフマッチングのための効率的なアルゴリズムに拡張する。
- 参考スコア（独自算出の注目度）: 7.320365821066744
- License:
- Abstract: We study learning problems on correlated stochastic block models with two balanced communities. Our main result gives the first efficient algorithm for graph matching in this setting. In the most interesting regime where the average degree is logarithmic in the number of vertices, this algorithm correctly matches all but a vanishing fraction of vertices with high probability, whenever the edge correlation parameter $s$ satisfies $s^2 > \alpha \approx 0.338$, where $\alpha$ is Otter's tree-counting constant. Moreover, we extend this to an efficient algorithm for exact graph matching whenever this is information-theoretically possible, positively resolving an open problem of R\'acz and Sridhar (NeurIPS 2021). Our algorithm generalizes the recent breakthrough work of Mao, Wu, Xu, and Yu (STOC 2023), which is based on centered subgraph counts of a large family of trees termed chandeliers. A major technical challenge that we overcome is dealing with the additional estimation errors that are necessarily present due to the fact that, in relevant parameter regimes, the latent community partition cannot be exactly recovered from a single graph. As an application of our results, we give an efficient algorithm for exact community recovery using multiple correlated graphs in parameter regimes where it is information-theoretically impossible to do so using just a single graph.
- Abstract（参考訳）: 2つのバランスの取れたコミュニティを持つ相関確率ブロックモデルにおける学習問題について検討する。
我々の主な成果は、この設定におけるグラフマッチングのための最初の効率的なアルゴリズムである。
平均次数が頂点数で対数的である最も興味深い状態において、このアルゴリズムは、エッジ相関パラメータ $s$ satisfies $s^2 > \alpha \approx 0.338$, ここで$\alpha$はオッターの木数定数である。
さらに、情報理論的に可能であれば、これを正確なグラフマッチングのための効率的なアルゴリズムに拡張し、R\'acz と Sridhar (NeurIPS 2021) の開問題を正に解決する。
筆者らのアルゴリズムは, チャンデリアと呼ばれる大木群の中心的な部分グラフ数に基づく, 近頃のMao, Wu, Xu, Yu (STOC 2023) のブレークスルー処理を一般化する。
私たちが克服する大きな技術的課題は、関連するパラメーター状態において、潜在コミュニティ分割が単一のグラフから正確に回復できないという事実から、必然的に存在する推定エラーに対処することです。
本研究の応用として,1つのグラフだけでは情報理論上不可能なパラメータ構造において,複数の相関グラフを用いて,正確なコミュニティ回復のための効率的なアルゴリズムを提案する。
関連論文リスト
- A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。
我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
論文 参考訳（メタデータ） (2024-03-21T11:57:16Z) - Efficiently matching random inhomogeneous graphs via degree profiles [11.485620556026571]
最小平均次数が少なくとも$Omega(log2 n)$である限り、効率的なマッチングアルゴリズムが見つかる。
等級プロファイルによるマッチングアルゴリズムの着想と拡張により、最小平均次数が少なくとも$Omega(log-2 n)$である限り、効率的なマッチングアルゴリズムが得られる。
論文 参考訳（メタデータ） (2023-10-16T14:25:43Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - Efficient Algorithms for Exact Graph Matching on Correlated Stochastic
Block Models with Constant Correlation [7.914348940034351]
本稿では,グラフとコミュニティ構造をマッチングする効率的なアルゴリズムを提案する。
我々のアルゴリズムは2つの相関ブロックモデル間の正確なマッチングを実現する最初の低次時間アルゴリズムである。
論文 参考訳（メタデータ） (2023-05-31T09:06:50Z) - Random graph matching at Otter's threshold via counting chandeliers [16.512416293014493]
そこで本研究では,各木に根付いた重み付き木を数えることで構築した類似度スコアに基づく,グラフマッチングの効率的なアルゴリズムを提案する。
これは、明示的な一定の相関で成功し、スパースグラフと密度グラフの両方に適用する最初のグラフマッチングアルゴリズムである。
論文 参考訳（メタデータ） (2022-09-25T20:00:28Z) - Active-LATHE: An Active Learning Algorithm for Boosting the Error
Exponent for Learning Homogeneous Ising Trees [75.93186954061943]
我々は、$rho$が少なくとも0.8$である場合に、エラー指数を少なくとも40%向上させるアルゴリズムを設計し、分析する。
我々の分析は、グラフの一部により多くのデータを割り当てるために、微小だが検出可能なサンプルの統計的変動を巧みに活用することに基づいている。
論文 参考訳（メタデータ） (2021-10-27T10:45:21Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Learnable Graph Matching: Incorporating Graph Partitioning with Deep
Feature Learning for Multiple Object Tracking [58.30147362745852]
フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。
既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。
そこで本研究では,学習可能なグラフマッチング手法を提案する。
論文 参考訳（メタデータ） (2021-03-30T08:58:45Z) - Random Graph Matching with Improved Noise Robustness [2.294014185517203]
本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。
我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。
これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
論文 参考訳（メタデータ） (2021-01-28T02:39:27Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。