論文の概要: Matrix Concentration for Random Signed Graphs and Community Recovery in the Signed Stochastic Block Model

• arxiv url: http://arxiv.org/abs/2412.20620v1
• Date: Sun, 29 Dec 2024 23:49:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-31 16:02:18.946623
• Title: Matrix Concentration for Random Signed Graphs and Community Recovery in the Signed Stochastic Block Model
• Title（参考訳）: 確率ブロックモデルにおけるランダム符号グラフの行列濃度とコミュニティ回復
• Authors: Sawyer Jack Robertson,
• Abstract要約: エッジとその記号が任意のノードから無作為に無作為に加算されるグラフを考える。 この結果を用いて,摂動符号ブロックモデルから得られたグラフについて検討する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: We consider graphs where edges and their signs are added independently at random from among all pairs of nodes. We establish strong concentration inequalities for adjacency and Laplacian matrices obtained from this family of random graph models. Then, we apply our results to study graphs sampled from the signed stochastic block model. Namely, we take a two-community setting where edges within the communities have positive signs and edges between the communities have negative signs and apply a random sign perturbation with probability $0< s <1/2$. In this setting, our findings include: first, the spectral gap of the corresponding signed Laplacian matrix concentrates near $2s$ with high probability; and second, the sign of the first eigenvector of the Laplacian matrix defines a weakly consistent estimator for the balanced community detection problem, or equivalently, the $\pm 1$ synchronization problem. We supplement our theoretical contributions with experimental data obtained from the models under consideration.
• Abstract（参考訳）: エッジとその記号が任意のノードから無作為に無作為に加算されるグラフを考える。 この系統のランダムグラフモデルから得られた隣接行列とラプラシア行列に対して強い濃度不等式を確立する。 そして,この結果を用いて,符号付き確率ブロックモデルから得られたグラフについて検討する。 すなわち、コミュニティ内のエッジには正の兆候があり、コミュニティ間のエッジには負の兆候があり、確率が0<s <1/2$のランダムなサイン摂動を適用する。 この設定では、まず、対応するラプラシア行列のスペクトルギャップは、高い確率で2s$近くに集中し、次に、ラプラシア行列の第1固有ベクトルの符号は、バランスの取れたコミュニティ検出問題に対する弱い一貫した推定器、または等価に$\pm 1$同期問題を定義する。 検討中のモデルから得られた実験データについて理論的貢献を補足する。

関連論文リスト

• Robust Graph-Based Semi-Supervised Learning via $p$-Conductances [49.0776396776252]
  本研究では,データラベルが不足している,あるいは破損しているような状況下でのグラフに対する半教師付き学習の課題について検討する。 我々は、$p$-laplace と Poisson の学習方法を一般化した $p$-conductance learning という手法を提案する。 コンピュータビジョンと引用データセットの実証実験結果から,本手法が低ラベルレート, 劣化ラベル, 部分ラベルレジームにおける最先端の精度を実現することを示す。
  論文  参考訳（メタデータ） (2025-02-13T01:11:25Z)
• Distributional Matrix Completion via Nearest Neighbors in the Wasserstein Space [8.971989179518216]
  わずかに観察された経験的分布の行列を考えると、観測された行列と観測されていない行列の両方に関連する真の分布をインプットしようと試みる。 最適輸送のツールを用いて、最も近い隣人法を分布設定に一般化する。
  論文  参考訳（メタデータ） (2024-10-17T00:50:17Z)
• Testing Dependency of Weighted Random Graphs [4.0554893636822]
  本研究では,2つのランダムグラフ間のエッジ依存性を検出するタスクについて検討する。 一般のエッジウェイト分布に対して、最適テストが情報理論上可能か不可能となるしきい値を確立する。
  論文  参考訳（メタデータ） (2024-09-23T10:07:41Z)
• Community Detection in the Multi-View Stochastic Block Model [47.43048484980115]
  本稿では,無神論的な観点から,複数の潜在的相関グラフ上でのコミュニティ検出の問題について考察する。 我々はまず,同じノードの集合上で相関グラフを生成するために設計された多視点情報ブロックモデル (MVSBM) と呼ばれるランダムグラフモデルを考案した。
  論文  参考訳（メタデータ） (2024-01-17T13:39:38Z)
• Sparsification of the regularized magnetic Laplacian with multi-type spanning forests [8.30255326875704]
  磁気ラプラシアン$Delta$,すなわち,エッジの少ない部分グラフに基づくスペクトル近似のスペーサーについて検討する。 ラプラシアン接続の自然推定器の選択に関する統計的保証を提供する。 本稿では,角度同期型ランキングとグラフに基づく半教師付き学習の2つの実用的応用について検討する。
  論文  参考訳（メタデータ） (2022-08-31T12:23:53Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• Robustness of Community Detection to Random Geometric Perturbations [16.575947847660778]
  我々は、頂点間の接続が、潜在(かつ観測されていない)ランダムな幾何グラフによって摂動されるブロックモデルを考える。 目的は、スペクトル法がランダムグラフの存在(あるいはそうでない)に非依存であっても、この種のノイズに対して堅牢であることを証明することである。
  論文  参考訳（メタデータ） (2020-11-09T10:15:40Z)
• Testing correlation of unlabeled random graphs [18.08210501570919]
  ラベルなしノードを持つ2つのランダムグラフ間のエッジ相関を検出する問題について検討する。 これは仮説テスト問題として定式化され、ヌル仮説の下では、2つのグラフは独立に生成される。 代替として、2つのグラフは、ある潜在ノード対応の下ではエッジ関連であるが、ヌルと同じ辺分布を持つ。
  論文  参考訳（メタデータ） (2020-08-23T19:19:45Z)
• The Generalized Lasso with Nonlinear Observations and Generative Priors [63.541900026673055]
  我々は、幅広い測定モデルで満たされるガウス下測度を仮定する。 この結果から, 局所埋込特性を仮定して, 均一回復保証まで拡張できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-22T16:43:35Z)
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees [106.91654068632882]
  半パラメトリック指数族分布におけるパラメータの統計的推定問題として、両部グラフを考察し、その表現学習問題を定式化する。 提案手法は, 地中真理付近で強い凸性を示すため, 勾配降下法が線形収束率を達成できることを示す。 我々の推定器は指数族内の任意のモデル誤特定に対して頑健であり、広範な実験で検証されている。
  論文  参考訳（メタデータ） (2020-03-02T16:40:36Z)

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

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