論文の概要: Community Detection in the Multi-View Stochastic Block Model

• arxiv url: http://arxiv.org/abs/2401.09510v1
• Date: Wed, 17 Jan 2024 13:39:38 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-19 18:58:24.343272
• Title: Community Detection in the Multi-View Stochastic Block Model
• Title（参考訳）: 多視点確率ブロックモデルにおけるコミュニティ検出
• Authors: Yexin Zhang, Zhongtian Ma, Qiaosheng Zhang, Zhen Wang, Xuelong Li
• Abstract要約: 本稿では,無神論的な観点から,複数の潜在的相関グラフ上でのコミュニティ検出の問題について考察する。 我々はまず,同じノードの集合上で相関グラフを生成するために設計された多視点情報ブロックモデル (MVSBM) と呼ばれるランダムグラフモデルを考案した。
• 参考スコア（独自算出の注目度）: 47.43048484980115
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper considers the problem of community detection on multiple potentially correlated graphs from an information-theoretical perspective. We first put forth a random graph model, called the multi-view stochastic block model (MVSBM), designed to generate correlated graphs on the same set of nodes (with cardinality $n$). The $n$ nodes are partitioned into two disjoint communities of equal size. The presence or absence of edges in the graphs for each pair of nodes depends on whether the two nodes belong to the same community or not. The objective for the learner is to recover the hidden communities with observed graphs. Our technical contributions are two-fold: (i) We establish an information-theoretic upper bound (Theorem~1) showing that exact recovery of community is achievable when the model parameters of MVSBM exceed a certain threshold. (ii) Conversely, we derive an information-theoretic lower bound (Theorem~2) showing that when the model parameters of MVSBM fall below the aforementioned threshold, then for any estimator, the expected number of misclassified nodes will always be greater than one. Our results for the MVSBM recover several prior results for community detection in the standard SBM as well as in multiple independent SBMs as special cases.
• Abstract（参考訳）: 本稿では,情報理論の観点から,複数の潜在的相関グラフに対するコミュニティ検出の問題について考察する。 私たちはまず、同じノード群(濃度$n$)で相関グラフを生成するように設計されたマルチビュー確率ブロックモデル(mvsbm)と呼ばれるランダムグラフモデルを発表した。 n$ノードは、同じサイズの2つの非結合なコミュニティに分割される。 各ノードのグラフにエッジが存在するか存在しないかは、2つのノードが同じコミュニティに属しているかどうかに依存する。 学習者の目標は、観察されたグラフで隠れたコミュニティを回復することである。 私たちの技術貢献は2つあります。 i) MVSBMのモデルパラメータが一定の閾値を超えると,コミュニティの正確な回復が達成可能であることを示す情報理論上界(Theorem~1)を確立する。 (ii) 逆に、mvsbm のモデルパラメータが上記のしきい値を下回るとき、任意の推定器に対して、期待される誤分類されたノード数が常に1より大きいことを示す情報理論的下限 (theorem~2) を導出する。 MVSBMは, 標準SBMおよび複数の独立SBMにおいて, コミュニティ検出に先立ついくつかの結果を得た。

関連論文リスト

• Differentially private exact recovery for stochastic block models [16.810982345283687]
  ネットワークがプライベートな場合のブロックモデル(SBM)の回復可能性問題について検討する。 我々のプライベートアルゴリズムは、入力グラフのサイズに対して時間w.r.t.を実行し、非プライベート設定の回復しきい値と一致する。
  論文  参考訳（メタデータ） (2024-06-04T12:38:05Z)
• Fundamental limits of community detection from multi-view data: multi-layer, dynamic and partially labeled block models [7.778975741303385]
  現代のネットワーク分析におけるマルチビューデータのコミュニティ検出について検討する。 我々は,データと潜在パラメータ間の相互情報を特徴付ける。 コミュニティ検出のための近似メッセージパッシングに基づく反復アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-01-16T07:13:32Z)
• OrthoReg: Improving Graph-regularized MLPs via Orthogonality Regularization [66.30021126251725]
  グラフニューラルネットワーク(GNN)は現在、グラフ構造データのモデリングにおいて支配的である。 グラフ正規化ネットワーク(GR-MLP)はグラフ構造情報をモデル重みに暗黙的に注入するが、その性能はほとんどのタスクにおいてGNNとほとんど一致しない。 GR-MLPは,最大数個の固有値が埋め込み空間を支配する現象である次元崩壊に苦しむことを示す。 次元崩壊問題を緩和する新しいGR-MLPモデルであるOrthoRegを提案する。
  論文  参考訳（メタデータ） (2023-01-31T21:20:48Z)
• Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks [54.225220638606814]
  本稿では,属性グラフの擬似測度,ツリー・モーバー距離(TMD)を提案し,その一般化との関係について検討する。 まず、TMDはグラフ分類に関連する特性をキャプチャし、単純なTMD-SVMは標準のGNNと競合することを示す。 第2に、分散シフトの下でのGNNの一般化とTMDを関連付け、そのようなシフト下での性能低下とよく相関していることを示す。
  論文  参考訳（メタデータ） (2022-10-04T21:03:52Z)
• Explicit Pairwise Factorized Graph Neural Network for Semi-Supervised Node Classification [59.06717774425588]
  本稿では,グラフ全体を部分的に観測されたマルコフ確率場としてモデル化するEPFGNN(Explicit Pairwise Factorized Graph Neural Network)を提案する。 出力-出力関係をモデル化するための明示的なペアワイズ要素を含み、入力-出力関係をモデル化するためにGNNバックボーンを使用する。 本研究では,グラフ上での半教師付きノード分類の性能を効果的に向上できることを示す。
  論文  参考訳（メタデータ） (2021-07-27T19:47:53Z)
• Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
  本稿では,d-uniform hypergraph block model(d-HSBM)の正確な回復の基本的な限界について検討する。 精度の高いしきい値が存在し、正確な回復がしきい値の上に達成でき、その下には不可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-11T03:39:08Z)
• Permutation-equivariant and Proximity-aware Graph Neural Networks with Stochastic Message Passing [88.30867628592112]
  グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。 置換等価性と近接認識性は、GNNにとって非常に望ましい2つの重要な特性である。 既存のGNNは、主にメッセージパッシング機構に基づいており、同時に2つの特性を保存できないことを示す。 ノードの近さを保つため,既存のGNNをノード表現で拡張する。
  論文  参考訳（メタデータ） (2020-09-05T16:46:56Z)
• Community Detection in Bipartite Networks with Stochastic Blockmodels [0.0]
  バイパーティイトネットワークでは、あるタイプのノードは、他のタイプのノードとの共通の接続パターンに従ってグループ化される。 これにより、ブロックモデル(SBM)が2部構成のコミュニティ検出の直感的な選択となる。 我々はSBMの非パラメトリックな定式化とそれに対応するアルゴリズムを導入し、二部ネットワークのコミュニティを効率的に見つける。
  論文  参考訳（メタデータ） (2020-01-22T05:58:19Z)
• Pair-Matching: Links Prediction with Adaptive Queries [7.22341371511072]
  グラフが2つのコミュニティを持つブロックモデル(SBM)に従って生成される場合、サブ線形後悔が達成可能であることを示す。 この論文は, コミュニティの数が2より多い場合に, 最適後悔に関する予想によって締めくくられる。
  論文  参考訳（メタデータ） (2019-05-17T15:57:37Z)

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

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