論文の概要: Settling the Sharp Reconstruction Thresholds of Random Graph Matching
- arxiv url: http://arxiv.org/abs/2102.00082v1
- Date: Fri, 29 Jan 2021 21:49:50 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-02 17:05:52.182375
- Title: Settling the Sharp Reconstruction Thresholds of Random Graph Matching
- Title（参考訳）: ランダムグラフマッチングにおけるシャープリコンストラクションスレッショルドの設定
- Authors: Yihong Wu and Jiaming Xu and Sophie H. Yu
- Abstract要約: 2つのエッジ関連ランダムグラフ間の隠れた対応を復元する問題について検討する。
p=n-o(1)$のグラフに対して、鋭いしきい値が存在することが証明される。
sparse ErdHos-R'enyi graphs with $p=n-Theta(1)$ に対して、オール・オー・ナッシング現象はもはや成り立たないことを示す。
- 参考スコア（独自算出の注目度）: 19.54246087326288
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies the problem of recovering the hidden vertex correspondence
between two edge-correlated random graphs. We focus on the Gaussian model where
the two graphs are complete graphs with correlated Gaussian weights and the
Erd\H{o}s-R\'enyi model where the two graphs are subsampled from a common
parent Erd\H{o}s-R\'enyi graph $\mathcal{G}(n,p)$. For dense graphs with
$p=n^{-o(1)}$, we prove that there exists a sharp threshold, above which one
can correctly match all but a vanishing fraction of vertices and below which
correctly matching any positive fraction is impossible, a phenomenon known as
the "all-or-nothing" phase transition. Even more strikingly, in the Gaussian
setting, above the threshold all vertices can be exactly matched with high
probability. In contrast, for sparse Erd\H{o}s-R\'enyi graphs with
$p=n^{-\Theta(1)}$, we show that the all-or-nothing phenomenon no longer holds
and we determine the thresholds up to a constant factor. Along the way, we also
derive the sharp threshold for exact recovery, sharpening the existing results
in Erd\H{o}s-R\'enyi graphs.
The proof of the negative results builds upon a tight characterization of the
mutual information based on the truncated second-moment computation and an
"area theorem" that relates the mutual information to the integral of the
reconstruction error. The positive results follows from a tight analysis of the
maximum likelihood estimator that takes into account the cycle structure of the
induced permutation on the edges.
- Abstract（参考訳）: 本稿では,二つの辺相関ランダムグラフ間の隠れ頂点対応を回復する問題について検討する。
2つのグラフがガウス重み付き完備グラフであるガウスモデルと、2つのグラフが共通の親 Erd\H{o}s-R\'enyi graph $\mathcal{G}(n,p)$ からサブサンプリングされるエルド\H{o}s-R\'enyiモデルに焦点を当てる。
p=n^{-o(1)}$ の高密度グラフに対して、よりシャープなしきい値が存在することを証明し、上述の頂点の消滅分数を除いて全てと正しく一致することができ、下記の任意の正の分数に正しく一致するようなグラフは不可能である、すなわち「オール・オア・ナッシング」相転移と呼ばれる現象である。
さらに驚くべきことに、ガウスの設定では、すべての頂点は高い確率で正確に一致させることができる。
対照的に、sparse erd\h{o}s-r\'enyi graphs with $p=n^{-\theta(1)}$ に対し、all-or-nothing 現象はもはや存在せず、定数因子まで閾値を決定する。
また, erd\h{o}s-r\'enyiグラフの既存の結果をシャープにすることで, 正確な回復のための鋭いしきい値も導出する。
否定的な結果の証明は、切断された第2モーメント計算に基づく相互情報の厳密な特徴付けと、相互情報と再構成誤差の積分を関連付ける「領域定理」に基づいている。
正の結果は、エッジ上の誘発された置換のサイクル構造を考慮に入れた最大可能性推定器の厳しい分析から生じる。
関連論文リスト
- Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs [7.001453437549302]
ErdHos-R'enyiグラフモデルでは、ある数を持つ一対の誘導された部分グラフが相関する。
相関ノード数に対する部分回復に最適であることを示す。
可能性の証明として,交差グラフのエッジを2種類の成分に分割する相関関数グラフを提案する。
論文 参考訳（メタデータ） (2024-06-08T10:17:42Z) - Finding the Missing-half: Graph Complementary Learning for
Homophily-prone and Heterophily-prone Graphs [48.79929516665371]
ホモフィリーなエッジを持つグラフは、同じクラスでノードを接続する傾向がある。
ヘテロフィ的傾向のあるエッジは、異なるクラスを持つノード間の関係を構築する傾向がある。
既存のGNNはトレーニング中にオリジナルのグラフのみを取る。
論文 参考訳（メタデータ） (2023-06-13T08:06:10Z) - Contrastive Graph Clustering in Curvature Spaces [74.03252813800334]
本研究では,CONGREGATE という新しいグラフクラスタリングモデルを提案する。
幾何学的クラスタリングを支援するため、理論的に基底とした不均一曲率空間を構築した。
次に、拡張不要な再重み付きコントラスト的アプローチでグラフクラスタをトレーニングする。
論文 参考訳（メタデータ） (2023-05-05T14:04:52Z) - Matching Correlated Inhomogeneous Random Graphs using the $k$-core
Estimator [5.685589351789462]
我々は、両グラフの大きな共通部分グラフを誘導する対応を出力するいわゆるemph$k$-core推定器について検討する。
相関ブロックモデル,Chung-Lu幾何グラフ,および相関ランダムグラフの精度と部分的回復に関する新たな結果を導出するために,我々の一般的な枠組みを専門化している。
論文 参考訳（メタデータ） (2023-02-10T18:21:35Z) - Graph Signal Sampling for Inductive One-Bit Matrix Completion: a
Closed-form Solution [112.3443939502313]
グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。
キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。
オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
論文 参考訳（メタデータ） (2023-02-08T08:17:43Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳（メタデータ） (2022-08-18T09:19:01Z) - Matching recovery threshold for correlated random graphs [9.12788494573002]
共通 ErdHos-R'enyi グラフ $mathbfG(n, p)$ から独立にサブサンプリングされた2つの相関グラフに対して、これらの2つのグラフのアンフィグアウトラベルの観測からそれらのエンフィラテントマッチングを回復したい。
この結果は,近年のWu,Xu,Yuによる研究において一定の要因を導出する。
論文 参考訳（メタデータ） (2022-05-29T13:04:20Z) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳（メタデータ） (2021-09-17T17:46:12Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳（メタデータ） (2021-05-03T16:36:27Z) - Impossibility of Partial Recovery in the Graph Alignment Problem [3.5880535198436156]
我々は、よく知られたNPハードグラフ同型問題の平均ケースとノイズバージョンを示す。
相関式 Erd"os-R'enyi モデルでは、スパース状態における部分的回復の不可能な結果が証明される。
我々の境界はノイズのない場合(グラフ同型問題)において厳密であり、まだノイズに密接であると予想する。
論文 参考訳（メタデータ） (2021-02-04T15:26:48Z) - Testing correlation of unlabeled random graphs [18.08210501570919]
ラベルなしノードを持つ2つのランダムグラフ間のエッジ相関を検出する問題について検討する。
これは仮説テスト問題として定式化され、ヌル仮説の下では、2つのグラフは独立に生成される。
代替として、2つのグラフは、ある潜在ノード対応の下ではエッジ関連であるが、ヌルと同じ辺分布を持つ。
論文 参考訳（メタデータ） (2020-08-23T19:19:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。