論文の概要: Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities

• arxiv url: http://arxiv.org/abs/2107.06767v1
• Date: Wed, 14 Jul 2021 15:27:15 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-15 14:05:34.779398
• Title: Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities
• Title（参考訳）: correlationd stochastic block model:正確なグラフマッチングとコミュニティ回復への応用
• Authors: Miklos Z. Racz, Anirudh Sridhar
• Abstract要約: 複数の相関ネットワークから潜在コミュニティ構造を学習する作業について考察する。 パラメータ構造における複数の相関グラフを用いて、潜在コミュニティを正確に回復する方法を示す。
• 参考スコア（独自算出の注目度）: 2.7920304852537527
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the task of learning latent community structure from multiple correlated networks. First, we study the problem of learning the latent vertex correspondence between two edge-correlated stochastic block models, focusing on the regime where the average degree is logarithmic in the number of vertices. We derive the precise information-theoretic threshold for exact recovery: above the threshold there exists an estimator that outputs the true correspondence with probability close to 1, while below it no estimator can recover the true correspondence with probability bounded away from 0. As an application of our results, we show how one can exactly recover the latent communities using multiple correlated graphs in parameter regimes where it is information-theoretically impossible to do so using just a single graph.
• Abstract（参考訳）: 複数の相関ネットワークから潜在コミュニティ構造を学習する作業を検討する。 まず, 2つのエッジ相関確率ブロックモデル間の潜在頂点対応を学習する問題を, 平均次数が頂点数で対数であるような状態に着目して検討する。 我々は、正確な回復のための正確な情報理論上の閾値を導出する:しきい値の上には、確率と1に近い確率との真の対応を出力する推定子が存在するが、その下には、0から離れた確率と真の対応を回復できない。 この結果の応用として,単一のグラフだけでは情報理論上不可能であるパラメータレジームにおいて,複数の相関グラフを用いて潜在コミュニティを正確に回復できることを示す。

関連論文リスト

• Graph-Dictionary Signal Model for Sparse Representations of Multivariate Data [49.77103348208835]
  グラフの有限集合がラプラシアンの重み付き和を通してデータ分布の関係を特徴付けるグラフ辞書信号モデルを定義する。 本稿では,観測データからグラフ辞書表現を推論するフレームワークを提案する。 我々は,脳活動データに基づく運動画像復号作業におけるグラフ辞書表現を利用して,従来の手法よりも想像的な動きをよりよく分類する。
  論文  参考訳（メタデータ） (2024-11-08T17:40:43Z)
• Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs [7.001453437549302]
  ErdHos-R'enyiグラフモデルでは、ある数を持つ一対の誘導された部分グラフが相関する。 相関ノード数に対する部分回復に最適であることを示す。 可能性の証明として,交差グラフのエッジを2種類の成分に分割する相関関数グラフを提案する。
  論文  参考訳（メタデータ） (2024-06-08T10:17:42Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF) 我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。 我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
  論文  参考訳（メタデータ） (2022-05-28T15:37:03Z)
• Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold [3.6052935394000234]
  ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。 ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。 パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-05-24T00:03:25Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Exact Community Recovery in Correlated Stochastic Block Models [6.746400031322727]
  複数の相関ネットワークから潜在コミュニティ構造を学習する問題について検討する。 本研究の主な成果は,複数の相関グラフを用いた正確なコミュニティ回復のための正確な情報理論しきい値の導出である。 コミュニティリカバリとグラフマッチング文献からアルゴリズムを慎重に合成する新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-29T16:44:38Z)
• Graphon-aided Joint Estimation of Multiple Graphs [24.077455621015552]
  観測結果から複数のネットワークのトポロジを推定する問題を考察する。 これは非パラメトリックなモデルであり、潜在的に異なるサイズのグラフを描画することができる。
  論文  参考訳（メタデータ） (2022-02-11T15:20:44Z)
• Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
  本稿では,d-uniform hypergraph block model(d-HSBM)の正確な回復の基本的な限界について検討する。 精度の高いしきい値が存在し、正確な回復がしきい値の上に達成でき、その下には不可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-11T03:39:08Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)
• Residual Correlation in Graph Neural Network Regression [39.54530450932135]
  我々は条件付き独立仮定が予測力を著しく制限していることを示します。 この問題を解釈可能かつ効率的なフレームワークで解決する。 我々のフレームワークは、競合するベースラインよりもかなり高い精度を実現している。
  論文  参考訳（メタデータ） (2020-02-19T16:32:54Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。