Fugu-MT 論文翻訳(概要): Impossibility of Partial Recovery in the Graph Alignment Problem

論文の概要: Impossibility of Partial Recovery in the Graph Alignment Problem

arxiv url: http://arxiv.org/abs/2102.02685v1
Date: Thu, 4 Feb 2021 15:26:48 GMT
ステータス: 処理完了
システム内更新日: 2021-02-05 16:33:49.966654
Title: Impossibility of Partial Recovery in the Graph Alignment Problem
Title（参考訳）: グラフアライメント問題における部分回復の可能性
Authors: Luca Ganassali, Laurent Massouli\'e, Marc Lelarge
Abstract要約: 我々は、よく知られたNPハードグラフ同型問題の平均ケースとノイズバージョンを示す。相関式 Erd"os-R'enyi モデルでは、スパース状態における部分的回復の不可能な結果が証明される。我々の境界はノイズのない場合(グラフ同型問題)において厳密であり、まだノイズに密接であると予想する。
参考スコア（独自算出の注目度）: 3.5880535198436156
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Random graph alignment refers to recovering the underlying vertex correspondence between two random graphs with correlated edges. This can be viewed as an average-case and noisy version of the well-known NP-hard graph isomorphism problem. For the correlated Erd\"os-R\'enyi model, we prove an impossibility result for partial recovery in the sparse regime, with constant average degree and correlation, as well as a general bound on the maximal reachable overlap. Our bound is tight in the noiseless case (the graph isomorphism problem) and we conjecture that it is still tight with noise. Our proof technique relies on a careful application of the probabilistic method to build automorphisms between tree components of a subcritical Erd\"os-R\'enyi graph.
Abstract（参考訳）: ランダムグラフアライメントは、相関エッジを持つ2つのランダムグラフ間の基礎となる頂点対応を回復することを意味します。これは、よく知られたNPハードグラフ同型問題の平均ケースおよびノイズバージョンと見なすことができる。相関式 Erd\"os-R\'enyi モデルでは、スパース状態における部分的回復の不可能な結果が一定平均度と相関で証明され、最大到達可能オーバーラップの一般有界性も証明される。私たちの境界はノイズレスの場合(グラフ同型問題)でタイトであり、まだノイズとタイトであると仮定します。この証明手法は、erd\"os-r\'enyiグラフの木の成分間の自己同型を構築するための確率的手法の注意深い応用に依存している。

関連論文リスト

Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs [7.001453437549302]
ErdHos-R'enyiグラフモデルでは、ある数を持つ一対の誘導された部分グラフが相関する。相関ノード数に対する部分回復に最適であることを示す。可能性の証明として,交差グラフのエッジを2種類の成分に分割する相関関数グラフを提案する。
論文参考訳（メタデータ） (2024-06-08T10:17:42Z)
Generation is better than Modification: Combating High Class Homophily Variance in Graph Anomaly Detection [51.11833609431406]
異なるクラス間のホモフィリー分布の差は、ホモフィリックグラフやヘテロフィリックグラフよりも著しく大きい。我々は、この現象を定量的に記述した、クラスホモフィリーバリアンスと呼ばれる新しい計量を導入する。その影響を軽減するために,ホモフィリーエッジ生成グラフニューラルネットワーク(HedGe)と呼ばれる新しいGNNモデルを提案する。
論文参考訳（メタデータ） (2024-03-15T14:26:53Z)
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)
Casting graph isomorphism as a point set registration problem using a simplex embedding and sampling [0.0]
グラフは、単純な埋め込みとサンプリングを用いて、十分な次元でセットされた点として表すことができる。それらの同型は、グラフの点集合形式の間の完全登録の存在に対応する。等値類に関する関連する考えは、グラフの正準化がグラフ同型問題に取り組む上で重要なツールであることを示している。
論文参考訳（メタデータ） (2021-11-15T12:16:21Z)
Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。三角凸分解はその上部に対応する変換によって保証されることを示す。
論文参考訳（メタデータ） (2021-09-17T17:46:12Z)
A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
論文参考訳（メタデータ） (2021-02-16T08:36:19Z)
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)
Line Graph Neural Networks for Link Prediction [71.00689542259052]
実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
論文参考訳（メタデータ） (2020-10-20T05:54:31Z)
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)

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