論文の概要: Correlation detection in trees for partial graph alignment

• arxiv url: http://arxiv.org/abs/2107.07623v1
• Date: Thu, 15 Jul 2021 22:02:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2021-07-19 14:42:36.302128
• Title: Correlation detection in trees for partial graph alignment
• Title（参考訳）: 部分グラフアライメントのための木の相関検出
• Authors: Luca Ganassali, Laurent Massouli\'e, Marc Lelarge
• Abstract要約: グラフのアライメントは,エッジの大部分を保存する2つのグラフのノード間のマッピングを探索する。 我々のアプローチは、2つのグラフの局所構造を比較し、その近傍が相関グラフに対して「十分近い」場合、2つのノードをマッチングすることである。 この問題は、一対の分岐木が積分布または相関分布から引き出されるかどうかの検定の観点から説明できる。
• 参考スコア（独自算出の注目度）: 3.5880535198436156
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider alignment of sparse graphs, which consists in finding a mapping between the nodes of two graphs which preserves most of the edges. Our approach is to compare local structures in the two graphs, matching two nodes if their neighborhoods are 'close enough': for correlated Erd\H{o}s-R\'enyi random graphs, this problem can be locally rephrased in terms of testing whether a pair of branching trees is drawn from either a product distribution, or a correlated distribution. We design an optimal test for this problem which gives rise to a message-passing algorithm for graph alignment, which provably returns in polynomial time a positive fraction of correctly matched vertices, and a vanishing fraction of mismatches. With an average degree $\lambda = O(1)$ in the graphs, and a correlation parameter $s \in [0,1]$, this result holds with $\lambda s$ large enough, and $1-s$ small enough, completing the recent state-of-the-art diagram. Tighter conditions for determining whether partial graph alignment (or correlation detection in trees) is feasible in polynomial time are given in terms of Kullback-Leibler divergences.
• Abstract（参考訳）: 本稿では,2つのグラフのノード間のマッピングを探索し,ほとんどのエッジを保存するスパースグラフのアライメントを検討する。 相関する Erd\H{o}s-R\'enyi ランダムグラフに対して、この問題は、一対の分岐木が積分布から引かれるか、あるいは相関分布から引かれるかのテストの観点から局所的に言い換えることができる。 この問題に対する最適テストの設計を行い, グラフアライメントのためのメッセージ通過アルゴリズムを考案し, 多項式時間での帰納, 正のマッチングされた頂点の分数, 失う不一致分数を導出する。 グラフ内の平均次数$\lambda = o(1)$ と相関パラメータ $s \in [0,1]$ とすると、この結果は$\lambda s$ で十分大きく、そして 1-s$ で十分小さくなり、最新の最先端の図が完成する。 多項式時間において部分グラフアライメント(あるいは木内の相関検出)が可能であるかどうかを決定するための厳密な条件は、クルバック・リーブラの発散によって与えられる。

関連論文リスト

• Graph Fourier MMD for Signals on Graphs [67.68356461123219]
  本稿では,グラフ上の分布と信号の間の新しい距離を提案する。 GFMMDは、グラフ上で滑らかであり、期待差を最大化する最適な目撃関数によって定義される。 グラフベンチマークのデータセットと単一セルRNAシークエンシングデータ解析について紹介する。
  論文  参考訳（メタデータ） (2023-06-05T00:01:17Z)
• Matching Correlated Inhomogeneous Random Graphs using the $k$-core Estimator [5.685589351789462]
  我々は、両グラフの大きな共通部分グラフを誘導する対応を出力するいわゆるemph$k$-core推定器について検討する。 相関ブロックモデル,Chung-Lu幾何グラフ,および相関ランダムグラフの精度と部分的回復に関する新たな結果を導出するために,我々の一般的な枠組みを専門化している。
  論文  参考訳（メタデータ） (2023-02-10T18:21:35Z)
• Random graph matching at Otter's threshold via counting chandeliers [16.512416293014493]
  そこで本研究では,各木に根付いた重み付き木を数えることで構築した類似度スコアに基づく,グラフマッチングの効率的なアルゴリズムを提案する。 これは、明示的な一定の相関で成功し、スパースグラフと密度グラフの両方に適用する最初のグラフマッチングアルゴリズムである。
  論文  参考訳（メタデータ） (2022-09-25T20:00:28Z)
• 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)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF) 我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。 我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
  論文  参考訳（メタデータ） (2022-05-28T15:37:03Z)
• Approximating the Log-Partition Function [16.59989033959959]
  基礎となるグラフ構造の性質を通じて近似比を定量化する手法を提案する。 グラフの有効抵抗を最小に抑えた平方根の逆に等しい近似比を実現するニアリニアタイム変量を提供する。
  論文  参考訳（メタデータ） (2021-02-19T22:57:32Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)
• 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)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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