論文の概要: Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs

• arxiv url: http://arxiv.org/abs/2406.05428v1
• Date: Sat, 8 Jun 2024 10:17:42 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-11 19:45:22.154897
• Title: Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs
• Title（参考訳）: 部分相関グラフのアライメントに対する情報理論閾値
• Authors: Dong Huang, Xianwen Song, Pengkun Yang,
• Abstract要約: ErdHos-R'enyiグラフモデルでは、ある数を持つ一対の誘導された部分グラフが相関する。 相関ノード数に対する部分回復に最適であることを示す。 可能性の証明として,交差グラフのエッジを2種類の成分に分割する相関関数グラフを提案する。
• 参考スコア（独自算出の注目度）: 7.001453437549302
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the problem of recovering the hidden vertex correspondence between two correlated random graphs. We propose the partially correlated Erd\H{o}s-R\'enyi graphs model, wherein a pair of induced subgraphs with a certain number are correlated. We investigate the information-theoretic thresholds for recovering the latent correlated subgraphs and the hidden vertex correspondence. We prove that there exists an optimal rate for partial recovery for the number of correlated nodes, above which one can correctly match a fraction of vertices and below which correctly matching any positive fraction is impossible, and we also derive an optimal rate for exact recovery. In the proof of possibility results, we propose correlated functional digraphs, which partition the edges of the intersection graph into two types of components, and bound the error probability by lower-order cumulant generating functions. The proof of impossibility results build upon the generalized Fano's inequality and the recovery thresholds settled in correlated Erd\H{o}s-R\'enyi graphs model.
• Abstract（参考訳）: 本稿では、2つの相関したランダムグラフ間の隠れ頂点対応を復元する問題について検討する。 本稿では, 部分相関した Erd\H{o}s-R\'enyi グラフモデルを提案する。 本稿では,潜時関連部分グラフと隠れ頂点対応を復元するための情報理論しきい値について検討する。 相関ノード数に対して,正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の 可能性の証明として,交差グラフのエッジを2種類の成分に分割し,下位累積生成関数によって誤差確率を限定する相関関数グラフを提案する。 不合理性の結果の証明は、一般化されたファノの不等式と、相関した Erd\H{o}s-R\'enyi グラフモデルで解決された回復しきい値に基づいている。

関連論文リスト

• Matching Correlated Inhomogeneous Random Graphs using the $k$-core Estimator [5.685589351789462]
  我々は、両グラフの大きな共通部分グラフを誘導する対応を出力するいわゆるemph$k$-core推定器について検討する。 相関ブロックモデル,Chung-Lu幾何グラフ,および相関ランダムグラフの精度と部分的回復に関する新たな結果を導出するために,我々の一般的な枠組みを専門化している。
  論文  参考訳（メタデータ） (2023-02-10T18:21:35Z)
• Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
  本稿では,元のグラフを表す小さなグラフの作成に焦点をあてる。 我々は、元のグラフを受容体の分布とみなし、受容体が同様の分布を持つ小さなグラフを合成することを目的としている。
  論文  参考訳（メタデータ） (2022-06-28T02:10:05Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF) 我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。 我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
  論文  参考訳（メタデータ） (2022-05-28T15:37:03Z)
• Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities [2.7920304852537527]
  複数の相関ネットワークから潜在コミュニティ構造を学習する作業について考察する。 パラメータ構造における複数の相関グラフを用いて、潜在コミュニティを正確に回復する方法を示す。
  論文  参考訳（メタデータ） (2021-07-14T15:27:15Z)
• Impossibility of Partial Recovery in the Graph Alignment Problem [3.5880535198436156]
  我々は、よく知られたNPハードグラフ同型問題の平均ケースとノイズバージョンを示す。 相関式 Erd"os-R'enyi モデルでは、スパース状態における部分的回復の不可能な結果が証明される。 我々の境界はノイズのない場合(グラフ同型問題)において厳密であり、まだノイズに密接であると予想する。
  論文  参考訳（メタデータ） (2021-02-04T15:26:48Z)
• Settling the Sharp Reconstruction Thresholds of Random Graph Matching [19.54246087326288]
  2つのエッジ関連ランダムグラフ間の隠れた対応を復元する問題について検討する。 p=n-o(1)$のグラフに対して、鋭いしきい値が存在することが証明される。 sparse ErdHos-R'enyi graphs with $p=n-Theta(1)$ に対して、オール・オー・ナッシング現象はもはや成り立たないことを示す。
  論文  参考訳（メタデータ） (2021-01-29T21:49:50Z)
• Hyperbolic Graph Embedding with Enhanced Semi-Implicit Variational Inference [48.63194907060615]
  半単純グラフ変分自動エンコーダを用いて,低次元グラフ潜在表現における高次統計量を取得する。 我々は、階層構造を示すグラフを効率的に表現するために、ポインケア埋め込みを通して潜在空間に双曲幾何学を組み込む。
  論文  参考訳（メタデータ） (2020-10-31T05:48:34Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)
• Factorizable Graph Convolutional Networks [90.59836684458905]
  本稿では,グラフに符号化された相互に絡み合った関係を明示的に解消する新しいグラフ畳み込みネットワーク(GCN)を提案する。 FactorGCNは単純なグラフを入力として取り、それをいくつかの分解グラフに分解する。 提案したFacterGCNは,合成および実世界のデータセットに対して質的かつ定量的に評価する。
  論文  参考訳（メタデータ） (2020-10-12T03:01:40Z)
• Testing correlation of unlabeled random graphs [18.08210501570919]
  ラベルなしノードを持つ2つのランダムグラフ間のエッジ相関を検出する問題について検討する。 これは仮説テスト問題として定式化され、ヌル仮説の下では、2つのグラフは独立に生成される。 代替として、2つのグラフは、ある潜在ノード対応の下ではエッジ関連であるが、ヌルと同じ辺分布を持つ。
  論文  参考訳（メタデータ） (2020-08-23T19:19:45Z)
• Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted Z-graded graphs [62.997667081978825]
  グラフ上の解に対して一次元の解を持ち上げることができる条件を特定する。 位相的に興味深いグラフの簡単な例であっても、対応する非自明なラックス対と関連するユニタリ変換は、Z階数グラフ上のラックス対に持ち上げないことを示す。
  論文  参考訳（メタデータ） (2020-08-11T17:58:13Z)

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

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