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

• arxiv url: http://arxiv.org/abs/2007.00533v5
• Date: Thu, 13 Jan 2022 09:07:04 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-14 23:02:34.183524
• Title: Partial Recovery in the Graph Alignment Problem
• Title（参考訳）: グラフアライメント問題における部分回復
• Authors: Georgina Hall and Laurent Massouli\'e
• Abstract要約: エッジオーバーラップを最大化するノード間の1対1のマッピングである2つのグラフが与えられた場合、回復する問題を考察する。 この問題は、よく知られたグラフ同型問題のノイズバージョンと見なすことができる。 我々は、ある追加仮定の下で$nqs=Theta(1)$ regimeで部分的回復を達成することができることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we consider the graph alignment problem, which is the problem of recovering, given two graphs, a one-to-one mapping between nodes that maximizes edge overlap. This problem can be viewed as a noisy version of the well-known graph isomorphism problem and appears in many applications, including social network deanonymization and cellular biology. Our focus here is on partial recovery, i.e., we look for a one-to-one mapping which is correct on a fraction of the nodes of the graph rather than on all of them, and we assume that the two input graphs to the problem are correlated Erd\H{o}s-R\'enyi graphs of parameters $(n,q,s)$. Our main contribution is then to give necessary and sufficient conditions on $(n,q,s)$ under which partial recovery is possible with high probability as the number of nodes $n$ goes to infinity. In particular, we show that it is possible to achieve partial recovery in the $nqs=\Theta(1)$ regime under certain additional assumptions.
• Abstract（参考訳）: 本稿では,エッジオーバーラップを最大化するノード間の1対1のマッピングである2つのグラフの復元問題であるグラフアライメント問題を考察する。 この問題は、よく知られたグラフ同型問題のノイズバージョンと見なすことができ、ソーシャルネットワークの匿名化や細胞生物学を含む多くの応用に現れる。 ここでの焦点は部分回復(英語版)、すなわち、すべてのグラフよりもグラフのノードのごく一部で正しい1対1の写像を探すことであり、問題に対する2つの入力グラフはパラメータ $(n,q,s)$ の Erd\H{o}s-R\enyi グラフと相関していると仮定する。 我々の主な貢献は、$(n,q,s)$に対して必要かつ十分な条件を与えることである。 特に、ある追加の仮定の下で$nqs=\Theta(1)$ regimeで部分的回復を達成することが可能であることを示す。

関連論文リスト

• Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs [48.79929516665371]
  ホモフィリーなエッジを持つグラフは、同じクラスでノードを接続する傾向がある。 ヘテロフィ的傾向のあるエッジは、異なるクラスを持つノード間の関係を構築する傾向がある。 既存のGNNはトレーニング中にオリジナルのグラフのみを取る。
  論文  参考訳（メタデータ） (2023-06-13T08:06:10Z)
• Graph Mixup with Soft Alignments [49.61520432554505]
  本研究では,画像上での使用に成功しているミキサアップによるグラフデータの増大について検討する。 ソフトアライメントによるグラフ分類のための簡易かつ効果的な混合手法であるS-Mixupを提案する。
  論文  参考訳（メタデータ） (2023-06-11T22:04:28Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Graph Neural Network Bandits [89.31889875864599]
  グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。 この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。 グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
  論文  参考訳（メタデータ） (2022-07-13T18:12:36Z)
• 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)
• Correlation detection in trees for partial graph alignment [3.5880535198436156]
  グラフのアライメントは,エッジの大部分を保存する2つのグラフのノード間のマッピングを探索する。 我々のアプローチは、2つのグラフの局所構造を比較し、その近傍が相関グラフに対して「十分近い」場合、2つのノードをマッチングすることである。 この問題は、一対の分岐木が積分布または相関分布から引き出されるかどうかの検定の観点から説明できる。
  論文  参考訳（メタデータ） (2021-07-15T22:02:27Z)
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
  各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。 この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。 我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
  論文  参考訳（メタデータ） (2021-02-16T08:36:19Z)
• 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)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)

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

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