論文の概要: Exact recovery and sharp thresholds of Stochastic Ising Block Model
- arxiv url: http://arxiv.org/abs/2004.05944v3
- Date: Wed, 14 Oct 2020 07:21:59 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-14 00:28:46.272743
- Title: Exact recovery and sharp thresholds of Stochastic Ising Block Model
- Title（参考訳）: 確率Ising Block Modelの厳密な回復とシャープしきい値
- Authors: Min Ye
- Abstract要約: ブロックモデル(SBM)とIsing Block Model(SIBM)の自然な構成を提案する。
SIBMでは、グラフをIsingモデルの基盤となるグラフとして$G$とみなし、そこから$m$、すなわちサンプルを引き出す。
目的は、Isingモデルによって生成されたサンプルからSBM内の2つのクラスターを正確に回収することである。
- 参考スコア（独自算出の注目度）: 18.084742915848175
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The stochastic block model (SBM) is a random graph model in which the edges
are generated according to the underlying cluster structure on the vertices.
The (ferromagnetic) Ising model, on the other hand, assigns $\pm 1$ labels to
vertices according to an underlying graph structure in a way that if two
vertices are connected in the graph then they are more likely to be assigned
the same label. In SBM, one aims to recover the underlying clusters from the
graph structure while in Ising model, an extensively-studied problem is to
recover the underlying graph structure based on i.i.d. samples (labelings of
the vertices).
In this paper, we propose a natural composition of SBM and the Ising model,
which we call the Stochastic Ising Block Model (SIBM). In SIBM, we take SBM in
its simplest form, where $n$ vertices are divided into two equal-sized clusters
and the edges are connected independently with probability $p$ within clusters
and $q$ across clusters. Then we use the graph $G$ generated by the SBM as the
underlying graph of the Ising model and draw $m$ i.i.d. samples from it. The
objective is to exactly recover the two clusters in SBM from the samples
generated by the Ising model, without observing the graph $G$. As the main
result of this paper, we establish a sharp threshold $m^\ast$ on the sample
complexity of this exact recovery problem in a properly chosen regime, where
$m^\ast$ can be calculated from the parameters of SIBM. We show that when $m\ge
m^\ast$, one can recover the clusters from $m$ samples in $O(n)$ time as the
number of vertices $n$ goes to infinity. When $m<m^\ast$, we further show that
for almost all choices of parameters of SIBM, the success probability of any
recovery algorithms approaches $0$ as $n\to\infty$.
- Abstract（参考訳）: 確率ブロックモデル(SBM)は、頂点上の下層のクラスタ構造に従ってエッジが生成されるランダムグラフモデルである。
一方、(強磁性)イジングモデルでは、2つの頂点がグラフに連結されている場合、同じラベルが割り当てられる可能性が高いように、基礎となるグラフ構造に従って頂点に$\pm 1$のラベルを割り当てる。
SBMでは、Isingモデルにおいて、基礎となるクラスタをグラフ構造から復元することを目的としており、その基盤となるグラフ構造をi.d.サンプル(頂点のラベル)に基づいて復元することが広く研究されている。
本稿では,SBMとIsingモデルの自然な構成を提案し,これをSIBM(Stochastic Ising Block Model)と呼ぶ。
SIBMでは、SBMを最も単純な形式で、$n$頂点を2つの等サイズのクラスタに分割し、エッジをクラスタ内の確率$p$とクラスタ間の$q$と独立に接続する。
次に、SBM が生成したグラフ $G$ をイジングモデルの基盤となるグラフとし、そこから $m$ i.i.d. サンプルを引き出す。
目的は、グラフを$G$で観測することなく、Isingモデルによって生成されたサンプルからSBM内の2つのクラスタを正確に回収することである。
本論文の主旨として, sibm のパラメータから $m^\ast$ を計算可能な, 適切に選択された条件において, この厳密な回復問題のサンプル複雑性に基づいて, 鋭い閾値 $m^\ast$ を定式化する。
すると、$m\ge m^\ast$のとき、$m$のサンプルから$o(n)$の時間でクラスタを復元できる。
m<m^\ast$の場合、SIBMのパラメータのほとんどすべての選択に対して、リカバリアルゴリズムの成功確率は、$0$ as $n\to\infty$に近づく。
関連論文リスト
- Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。
我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。
提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
論文 参考訳（メタデータ） (2024-08-03T20:08:02Z) - Hierarchical cycle-tree packing model for $K$-core attack problem [0.0]
ここでは、この挑戦的な最適化問題に対して、階層的なサイクルツリーパッキングモデルを導入している。
統計物理学のレプリカ対称キャビティ法を用いて,このモデルを解析する。
関連する階層的サイクルツリー誘導攻撃(tt hCTGA)は、通常のランダムグラフに対するほぼ最適な攻撃解を構築することができる。
論文 参考訳（メタデータ） (2023-03-02T06:47:33Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳（メタデータ） (2022-08-18T09:19:01Z) - Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。
近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。
副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
論文 参考訳（メタデータ） (2022-02-22T04:14:45Z) - Causal Inference Despite Limited Global Confounding via Mixture Models [4.721845865189578]
そのようなモデルの有限$k$-mixtureは、図式的により大きなグラフで表される。
空でないDAGの混合を学習するための最初のアルゴリズムを与える。
論文 参考訳（メタデータ） (2021-12-22T01:04:50Z) - AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph
Convolution [79.44066256794187]
我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。
アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。
理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
論文 参考訳（メタデータ） (2021-11-12T07:08:13Z) - Improving Robustness and Generality of NLP Models Using Disentangled
Representations [62.08794500431367]
スーパービジョンニューラルネットワークはまず入力$x$を単一の表現$z$にマップし、次に出力ラベル$y$にマッピングする。
本研究では,非交叉表現学習の観点から,NLPモデルの堅牢性と汎用性を改善する手法を提案する。
提案した基準でトレーニングしたモデルは、広範囲の教師付き学習タスクにおいて、より堅牢性とドメイン適応性を向上することを示す。
論文 参考訳（メタデータ） (2020-09-21T02:48:46Z) - Block Model Guided Unsupervised Feature Selection [32.21728295212875]
リンクデータに対するグラフ駆動型教師なし特徴選択のための新しい手法を提案する。
まず、グラフ上にブロックモデルを構築し、次に特徴選択にブロックモデルを使用するという、新しいアプローチを取ります。
実験結果から,本手法は実世界の複数の公開データセット上での最先端の手法であることがわかった。
論文 参考訳（メタデータ） (2020-07-05T16:19:47Z) - Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
既存のディープニューラルネットワーク手法では、隣接行列を構築することで、$Omega(n2)$複雑さを必要とする。
我々は,この空間を利用して完全隣接行列を生成する新しい自己回帰モデルBiGGを開発した。
トレーニング中、この自己回帰モデルは$O(log n)$同期ステージで並列化できる。
論文 参考訳（メタデータ） (2020-06-28T04:37:57Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。