論文の概要: Non-Convex Exact Community Recovery in Stochastic Block Model
- arxiv url: http://arxiv.org/abs/2006.15843v4
- Date: Mon, 27 Sep 2021 12:03:04 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-15 15:07:58.882554
- Title: Non-Convex Exact Community Recovery in Stochastic Block Model
- Title（参考訳）: 確率ブロックモデルにおける非凸エクササイズコミュニティ回復
- Authors: Peng Wang, Zirui Zhou, Anthony Man-Cho So
- Abstract要約: 近年,対称ブロックモデル(SBM)に基づくグラフのコミュニティ検出が注目されている。
この問題の対数的疎度構造において、提案した2段階法は、$mathcalO(nlog2n/loglog n)$ timeにおいて、情報理論の限界まで正確に2つのコミュニティを復元できることを示す。
また, 提案手法の有効性を実証し, 理論的発展を補完するために, 合成データセットと実データセットの両方で数値実験を行った。
- 参考スコア（独自算出の注目度）: 31.221745716673546
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Community detection in graphs that are generated according to stochastic
block models (SBMs) has received much attention lately. In this paper, we focus
on the binary symmetric SBM -- in which a graph of $n$ vertices is randomly
generated by first partitioning the vertices into two equal-sized communities
and then connecting each pair of vertices with probability that depends on
their community memberships -- and study the associated exact community
recovery problem. Although the maximum-likelihood formulation of the problem is
non-convex and discrete, we propose to tackle it using a popular iterative
method called projected power iterations. To ensure fast convergence of the
method, we initialize it using a point that is generated by another iterative
method called orthogonal iterations, which is a classic method for computing
invariant subspaces of a symmetric matrix. We show that in the logarithmic
sparsity regime of the problem, with high probability the proposed two-stage
method can exactly recover the two communities down to the
information-theoretic limit in $\mathcal{O}(n\log^2n/\log\log n)$ time, which
is competitive with a host of existing state-of-the-art methods that have the
same recovery performance. We also conduct numerical experiments on both
synthetic and real data sets to demonstrate the efficacy of our proposed method
and complement our theoretical development.
- Abstract（参考訳）: 確率的ブロックモデル(sbms)に従って生成されたグラフにおけるコミュニティ検出が近年注目されている。
本稿では,まず各頂点を2つの等サイズのコミュニティに分割し,各頂点をそれぞれのコミュニティメンバーシップに依存する確率で接続することにより,n$の頂点グラフをランダムに生成する二項対称SBMに着目し,関連する正確なコミュニティ回復問題を考察する。
この問題の最大形は非凸かつ離散的であるが、投影パワー反復と呼ばれる一般的な反復手法を用いてこの問題に取り組むことを提案する。
本手法の高速収束を保証するため,対称行列の不変部分空間を計算するための古典的手法である直交反復法と呼ばれる別の反復法によって生成される点を用いて初期化する。
対数スパルシリティ理論において,提案する2段階法は,同一のリカバリ性能を持つ既存手法のホストと競合する$\mathcal{o}(n\log^2n/\log\log n)$ time において,情報理論上の限界まで,正確に2つのコミュニティを回復できることを示す。
また, 合成データと実データの両方について数値実験を行い, 提案手法の有効性を実証し, 理論的展開を補完する。
関連論文リスト
- Representation and De-interleaving of Mixtures of Hidden Markov Processes [3.7348616912887445]
隠れマルコフ過程(HMP)の混合物の分離は、一般的にその表現モデルに依存する。
本稿では,HMPの混合物に対する新しい表現モデルとそれに対応するインターリーブ法を提案する。
論文 参考訳（メタデータ） (2024-06-01T12:24:23Z) - An Optimization-based Deep Equilibrium Model for Hyperspectral Image
Deconvolution with Convergence Guarantees [71.57324258813675]
本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。
新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。
導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
論文 参考訳（メタデータ） (2023-06-10T08:25:16Z) - Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。
6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2022-05-21T01:47:17Z) - Exact Community Recovery over Signed Graphs [27.2776492470422]
2つの同じ大きさのコミュニティを持つサイン付きグラフ上でのコミュニティリカバリの問題について検討する。
提案手法は,符号付きブロックモデルの最大推定値(MLE)に基づく。
対数次数法では,提案アルゴリズムは基礎となるコミュニティをほぼ直線的に復元することができる。
論文 参考訳（メタデータ） (2022-02-22T05:03:25Z) - A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。
提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
論文 参考訳（メタデータ） (2021-10-07T17:51:10Z) - Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable
Approach for Continuous Markov Random Fields [53.31927549039624]
断片的な離散化は既存の離散化問題と矛盾しないことを示す。
この理論を2つの画像のマッチング問題に適用する。
論文 参考訳（メタデータ） (2021-07-13T12:31:06Z) - Improving Metric Dimensionality Reduction with Distributed Topology [68.8204255655161]
DIPOLEは、局所的、計量的項と大域的、位相的項の両方で損失関数を最小化し、初期埋め込みを補正する次元推論後処理ステップである。
DIPOLEは、UMAP、t-SNE、Isomapといった一般的な手法よりも多くの一般的なデータセットで優れています。
論文 参考訳（メタデータ） (2021-06-14T17:19:44Z) - Free Energy Node Embedding via Generalized Skip-gram with Negative
Sampling [34.12821919995092]
教師なしノード埋め込みフレームワークの2段階の改善を提案する。
一方,最短経路と通勤時間距離を補間する自由エネルギー距離に基づいてノード類似性を符号化することを提案する。
一方,任意の類似度行列に一般化する損失関数に基づく行列分解法を提案する。
論文 参考訳（メタデータ） (2021-05-19T14:58:13Z) - Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
本稿では,d-uniform hypergraph block model(d-HSBM)の正確な回復の基本的な限界について検討する。
精度の高いしきい値が存在し、正確な回復がしきい値の上に達成でき、その下には不可能であることを示す。
論文 参考訳（メタデータ） (2021-05-11T03:39:08Z) - Jointly Modeling and Clustering Tensors in High Dimensions [6.072664839782975]
テンソルの合同ベンチマークとクラスタリングの問題を考察する。
本稿では,統計的精度の高い近傍に幾何的に収束する効率的な高速最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-04-15T21:06:16Z) - Community Detection in the Stochastic Block Model by Mixed Integer
Programming [3.8073142980733]
Degree-Corrected Block Model (DCSBM) は、コミュニティ構造を持つランダムグラフを生成する一般的なモデルである。
DCSBMに基づくコミュニティ検出の標準的なアプローチは、最大推定(MLE)により観測されたネットワークデータを生成する可能性が最も高いモデルパラメータを探索することである。
本稿では,モデルパラメータと最大確率のコミュニティ割当を観測グラフから確実に求める数学的計画式と厳密解法を提案する。
論文 参考訳（メタデータ） (2021-01-26T22:04:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。