論文の概要: Exact Community Recovery over Signed Graphs

• arxiv url: http://arxiv.org/abs/2202.12255v1
• Date: Tue, 22 Feb 2022 05:03:25 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-25 18:16:50.980561
• Title: Exact Community Recovery over Signed Graphs
• Title（参考訳）: サイン付きグラフによるコミュニティの回復
• Authors: Xiaolu Wang, Peng Wang, Anthony Man-Cho So
• Abstract要約: 2つの同じ大きさのコミュニティを持つサイン付きグラフ上でのコミュニティリカバリの問題について検討する。 提案手法は,符号付きブロックモデルの最大推定値(MLE)に基づく。 対数次数法では,提案アルゴリズムは基礎となるコミュニティをほぼ直線的に復元することができる。
• 参考スコア（独自算出の注目度）: 27.2776492470422
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Signed graphs encode similarity and dissimilarity relationships among different entities with positive and negative edges. In this paper, we study the problem of community recovery over signed graphs generated by the signed stochastic block model (SSBM) with two equal-sized communities. Our approach is based on the maximum likelihood estimation (MLE) of the SSBM. Unlike many existing approaches, our formulation reveals that the positive and negative edges of a signed graph should be treated unequally. We then propose a simple two-stage iterative algorithm for solving the regularized MLE. It is shown that in the logarithmic degree regime, the proposed algorithm can exactly recover the underlying communities in nearly-linear time at the information-theoretic limit. Numerical results on both synthetic and real data are reported to validate and complement our theoretical developments and demonstrate the efficacy of the proposed method.
• Abstract（参考訳）: 符号付きグラフは、正および負のエッジを持つ異なる実体間の類似性と異性関係を符号化する。 本稿では,符号付き確率ブロックモデル (SSBM) が生み出す符号付きグラフに対するコミュニティ復元の問題について検討する。 提案手法は,ssbmの最大確率推定(mle)に基づいている。 既存の多くのアプローチとは異なり、我々の定式化は符号付きグラフの正の辺と負の辺を不等に扱うべきであることを明らかにする。 次に,正規化mleを解くための単純な二段階反復アルゴリズムを提案する。 対数次数法では,提案アルゴリズムは情報理論の限界において,基礎となるコミュニティをほぼ直線的に正確に復元できることが示されている。 合成データと実データの両方に関する数値的な結果を報告し, 提案手法の有効性を実証し, 理論的発展を補完する。

関連論文リスト

• ExDBN: Exact learning of Dynamic Bayesian Networks [2.2499166814992435]
  本稿では,データから因果学習を行うためのスコアベースの学習手法を提案する。 提案手法は, 最大25の時系列の小型・中規模の合成インスタンスに適用した場合, 優れた結果が得られた。 バイオサイエンスとファイナンスにおける2つの興味深い応用は、この方法を直接適用することで、高度に正確でグローバルに収束した解法を開発する機会をさらに強調するものである。
  論文  参考訳（メタデータ） (2024-10-21T15:27:18Z)
• Vector-Valued Least-Squares Regression under Output Regularity Assumptions [73.99064151691597]
  最小二乗回帰問題を無限次元出力で解くために,還元ランク法を提案し,解析する。 提案手法の学習バウンダリを導出し、フルランク手法と比較して統計的性能の設定を改善する研究を行う。
  論文  参考訳（メタデータ） (2022-11-16T15:07:00Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。 この問題は楕円分布のペナルティ化された最大推定値として表される。 楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
  論文  参考訳（メタデータ） (2022-10-21T13:19:45Z)
• Making Linear MDPs Practical via Contrastive Representation Learning [101.75885788118131]
  マルコフ決定過程(MDP)における次元性の呪いに、低ランク表現を利用することで対処することが一般的である。 本稿では,効率的な表現学習を可能にしつつ,正規化を自動的に保証する線形MDPの代替的定義について考察する。 いくつかのベンチマークにおいて、既存の最先端モデルベースおよびモデルフリーアルゴリズムよりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-07-14T18:18:02Z)
• Exact Community Recovery in Correlated Stochastic Block Models [6.746400031322727]
  複数の相関ネットワークから潜在コミュニティ構造を学習する問題について検討する。 本研究の主な成果は,複数の相関グラフを用いた正確なコミュニティ回復のための正確な情報理論しきい値の導出である。 コミュニティリカバリとグラフマッチング文献からアルゴリズムを慎重に合成する新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-29T16:44:38Z)
• Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations [57.15855198512551]
  本稿では,連続時間フレームワークを用いたグラフのスコアベース生成モデルを提案する。 本手法は, トレーニング分布に近い分子を生成できるが, 化学価数則に違反しないことを示す。
  論文  参考訳（メタデータ） (2022-02-05T08:21:04Z)
• A Probabilistic Graph Coupling View of Dimension Reduction [5.35952718937799]
  クロスエントロピーを用いた隠れグラフの結合に基づく統一統計フレームワークを提案する。 既存のペアワイズ類似性DR法は,グラフの事前選択に際し,我々のフレームワークから検索可能であることを示す。 我々のモデルはこの問題に対処するために活用され拡張され、新しいリンクはラプラシア固有写像とPCAで描画される。
  論文  参考訳（メタデータ） (2022-01-31T08:21:55Z)
• Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities [2.7920304852537527]
  複数の相関ネットワークから潜在コミュニティ構造を学習する作業について考察する。 パラメータ構造における複数の相関グラフを用いて、潜在コミュニティを正確に回復する方法を示す。
  論文  参考訳（メタデータ） (2021-07-14T15:27:15Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  結合ネットワークトポロジ推論は、異種グラフ信号から複数のグラフラプラシア行列を学習する標準的な問題を表す。 新規な構造化融合正規化に基づく一般グラフ推定器を提案する。 提案するグラフ推定器は高い計算効率と厳密な理論保証の両方を享受できることを示す。
  論文  参考訳（メタデータ） (2021-03-05T04:42:32Z)
• GELATO: Geometrically Enriched Latent Model for Offline Reinforcement Learning [54.291331971813364]
  オフライン強化学習アプローチは、近近法と不確実性認識法に分けられる。 本研究では,この2つを潜在変動モデルに組み合わせることのメリットを実証する。 提案したメトリクスは、分布サンプルのアウトの品質と、データ内のサンプルの不一致の両方を測定します。
  論文  参考訳（メタデータ） (2021-02-22T19:42:40Z)
• Non-Convex Exact Community Recovery in Stochastic Block Model [31.221745716673546]
  近年,対称ブロックモデル(SBM)に基づくグラフのコミュニティ検出が注目されている。 この問題の対数的疎度構造において、提案した2段階法は、$mathcalO(nlog2n/loglog n)$ timeにおいて、情報理論の限界まで正確に2つのコミュニティを復元できることを示す。 また, 提案手法の有効性を実証し, 理論的発展を補完するために, 合成データセットと実データセットの両方で数値実験を行った。
  論文  参考訳（メタデータ） (2020-06-29T07:03:27Z)

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

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