論文の概要: Harnessing Multiple Correlated Networks for Exact Community Recovery
- arxiv url: http://arxiv.org/abs/2412.02796v1
- Date: Tue, 03 Dec 2024 19:56:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-05 15:06:24.763963
- Title: Harnessing Multiple Correlated Networks for Exact Community Recovery
- Title(参考訳): コミュニティ・リカバリのための複数関連ネットワークのハーネス
- Authors: Miklós Z. Rácz, Jifan Zhang,
- Abstract要約: 複数の相関ネットワークから潜在コミュニティ構造を学習する問題について検討する。
Gaudio、R'acz、Sridhar(COLT 2022)の最近の研究により、正確なコミュニティ回復のための正確な情報理論しきい値が決定された。
- 参考スコア(独自算出の注目度): 6.092631511453874
- License:
- Abstract: We study the problem of learning latent community structure from multiple correlated networks, focusing on edge-correlated stochastic block models with two balanced communities. Recent work of Gaudio, R\'acz, and Sridhar (COLT 2022) determined the precise information-theoretic threshold for exact community recovery using two correlated graphs; in particular, this showcased the subtle interplay between community recovery and graph matching. Here we study the natural setting of more than two graphs. The main challenge lies in understanding how to aggregate information across several graphs when none of the pairwise latent vertex correspondences can be exactly recovered. Our main result derives the precise information-theoretic threshold for exact community recovery using any constant number of correlated graphs, answering a question of Gaudio, R\'acz, and Sridhar (COLT 2022). In particular, for every $K \geq 3$ we uncover and characterize a region of the parameter space where exact community recovery is possible using $K$ correlated graphs, even though (1) this is information-theoretically impossible using any $K-1$ of them and (2) none of the latent matchings can be exactly recovered.
- Abstract(参考訳): 本研究では,複数の相関ネットワークから潜在コミュニティ構造を学習する問題について検討し,2つのバランスの取れたコミュニティを持つエッジ関連確率ブロックモデルに着目した。
Gaudio, R\'acz, Sridhar (COLT 2022) の最近の研究は、2つの相関グラフを用いて正確なコミュニティ回復のための正確な情報理論しきい値を決定し、特に、コミュニティ回復とグラフマッチングの微妙な相互作用を示した。
ここでは、2つ以上のグラフの自然な設定について研究する。
主な課題は、複数のグラフにまたがって情報を集約する方法を理解することである。
本研究の主な成果は,Gaudio,R\'acz,Sridhar (COLT 2022) の質問に答え,一定の数の相関グラフを用いて,正確なコミュニティ回復のための正確な情報理論閾値を導出する。
特に、$K {\displaystyle \geq 3} のすべての$K {\displaystyle \geq 3} に対して、(1) が情報理論上不可能であるにもかかわらず、正確なコミュニティ回復が可能なパラメータ空間の領域を発見して特徴付ける。
関連論文リスト
- Efficient Graph Matching for Correlated Stochastic Block Models [7.320365821066744]
2つのバランスの取れたコミュニティを持つ相関ブロックモデルの学習問題について検討する。
我々の主な成果は、この設定におけるグラフマッチングのための最初の効率的なアルゴリズムである。
我々はこれを情報理論的に可能であれば、正確なグラフマッチングのための効率的なアルゴリズムに拡張する。
論文 参考訳(メタデータ) (2024-12-03T18:36:45Z) - Community Detection in the Multi-View Stochastic Block Model [47.43048484980115]
本稿では,無神論的な観点から,複数の潜在的相関グラフ上でのコミュニティ検出の問題について考察する。
我々はまず,同じノードの集合上で相関グラフを生成するために設計された多視点情報ブロックモデル (MVSBM) と呼ばれるランダムグラフモデルを考案した。
論文 参考訳(メタデータ) (2024-01-17T13:39:38Z) - Community Detection with Known, Unknown, or Partially Known Auxiliary
Latent Variables [21.35141858359507]
実際には、コミュニティメンバシップは、観測グラフのエッジ間の依存性を完全に説明していません。
補助潜在変数を持つブロックモデルと検閲ブロックモデルに従うグラフについて検討する。
半定値プログラミングにより、各最大精度の正確な回復しきい値まで、正確なリカバリが可能であることを示す。
論文 参考訳(メタデータ) (2023-01-08T21:09:03Z) - Explainable Sparse Knowledge Graph Completion via High-order Graph
Reasoning Network [111.67744771462873]
本稿では,スパース知識グラフ(KG)のための新しい説明可能なモデルを提案する。
高次推論をグラフ畳み込みネットワーク、すなわちHoGRNに結合する。
情報不足を緩和する一般化能力を向上させるだけでなく、解釈可能性も向上する。
論文 参考訳(メタデータ) (2022-07-14T10:16:56Z) - Exact Community Recovery in Correlated Stochastic Block Models [6.746400031322727]
複数の相関ネットワークから潜在コミュニティ構造を学習する問題について検討する。
本研究の主な成果は,複数の相関グラフを用いた正確なコミュニティ回復のための正確な情報理論しきい値の導出である。
コミュニティリカバリとグラフマッチング文献からアルゴリズムを慎重に合成する新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-03-29T16:44:38Z) - Question-Answer Sentence Graph for Joint Modeling Answer Selection [122.29142965960138]
我々は,質問文,質問文,回答文のペア間のスコアを計算するための最先端(SOTA)モデルを訓練し,統合する。
オンライン推論は、目に見えないクエリのAS2タスクを解決するために実行される。
論文 参考訳(メタデータ) (2022-02-16T05:59:53Z) - Correlated Stochastic Block Models: Exact Graph Matching with
Applications to Recovering Communities [2.7920304852537527]
複数の相関ネットワークから潜在コミュニティ構造を学習する作業について考察する。
パラメータ構造における複数の相関グラフを用いて、潜在コミュニティを正確に回復する方法を示す。
論文 参考訳(メタデータ) (2021-07-14T15:27:15Z) - QD-GCN: Query-Driven Graph Convolutional Networks for Attributed
Community Search [54.42038098426504]
QD-GCNは、ACS問題を解決するために、コミュニティ構造とノード属性を統一するエンドツーエンドフレームワークである。
本稿では、QD-GCNが既存の属性付きコミュニティ検索アルゴリズムを効率性と有効性の両方で上回ることを示す。
論文 参考訳(メタデータ) (2021-04-08T07:52:48Z) - Spatial-spectral Hyperspectral Image Classification via Multiple Random
Anchor Graphs Ensemble Learning [88.60285937702304]
本稿では,複数のランダムアンカーグラフアンサンブル学習(RAGE)を用いた空間スペクトルHSI分類手法を提案する。
まず、各選択されたバンドのより記述的な特徴を抽出し、局所的な構造と領域の微妙な変化を保存するローカルバイナリパターンを採用する。
次に,アンカーグラフの構成に適応隣接代入を導入し,計算複雑性を低減した。
論文 参考訳(メタデータ) (2021-03-25T09:31:41Z) - A Thorough View of Exact Inference in Graphs from the Degree-4
Sum-of-Squares Hierarchy [37.34153902687548]
各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。
この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。
我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
論文 参考訳(メタデータ) (2021-02-16T08:36:19Z) - Factorizable Graph Convolutional Networks [90.59836684458905]
本稿では,グラフに符号化された相互に絡み合った関係を明示的に解消する新しいグラフ畳み込みネットワーク(GCN)を提案する。
FactorGCNは単純なグラフを入力として取り、それをいくつかの分解グラフに分解する。
提案したFacterGCNは,合成および実世界のデータセットに対して質的かつ定量的に評価する。
論文 参考訳(メタデータ) (2020-10-12T03:01:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。