論文の概要: Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)

• arxiv url: http://arxiv.org/abs/2506.02825v1
• Date: Tue, 03 Jun 2025 12:54:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-04 21:47:35.679233
• Title: Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)
• Title（参考訳）: エッジ相関のない漸近完全シードグラフマッチング(および推論への応用)
• Authors: Tong Qi, Vera Andersson, Peter Viechnicki, Vince Lyzinski,
• Abstract要約: シード多重グラフマッチングのためのOmniMatchアルゴリズムを提案する。 我々は,多数のシミュレーションおよびシャッフルグラフ仮説テストの文脈において,アルゴリズムの有効性を実証する。
• 参考スコア（独自算出の注目度）: 2.313664320808389
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present the OmniMatch algorithm for seeded multiple graph matching. In the setting of $d$-dimensional Random Dot Product Graphs (RDPG), we prove that under mild assumptions, OmniMatch with $s$ seeds asymptotically and efficiently perfectly aligns $O(s^{\alpha})$ unseeded vertices -- for $\alpha<2\wedge d/4$ -- across multiple networks even in the presence of no edge correlation. We demonstrate the effectiveness of our algorithm across numerous simulations and in the context of shuffled graph hypothesis testing. In the shuffled testing setting, testing power is lost due to the misalignment/shuffling of vertices across graphs, and we demonstrate the capacity of OmniMatch to correct for misaligned vertices prior to testing and hence recover the lost testing power. We further demonstrate the algorithm on a pair of data examples from connectomics and machine translation.
• Abstract（参考訳）: シード多重グラフマッチングのためのOmniMatchアルゴリズムを提案する。 RDPG ($d$-dimensional Random Dot Product Graphs) の設定において、穏やかな仮定の下で、OmniMatch と$s$の種を漸近的に効率よく整列させることは、エッジ相関がなくても、複数のネットワークにわたって$O(s^{\alpha})$unseed vertices -- for $\alpha<2\wedge d/4$ -- に対して$O(s^{\alpha})$unseed vertices -- が成立することを証明する。 我々は,多数のシミュレーションおよびシャッフルグラフ仮説テストの文脈において,アルゴリズムの有効性を実証する。 シャッフルテスト環境では,グラフ間の頂点のずれやシャッフルによってテスト能力が失われ,テスト前の頂点の誤りを正すOmniMatchの能力を示す。 さらに、コネクトロミクスと機械翻訳の2つのデータ例でアルゴリズムを実証する。

関連論文リスト

• Optimal community detection in dense bipartite graphs [0.0]
  我々は、n_1×n$の高次元二部グラフにおいて、密連結頂点のコミュニティを検出する問題を考える。 我々は,最小信号強度$delta*$の非漸近的上界および下界を,必要かつ十分であり,かつ,最小のタイプ1とタイプ2の誤差でテストが存在することを保証する。 提案試験は, 隣接行列の非線形統計値と, 独立性のある解析値を組み合わせたものである。
  論文  参考訳（メタデータ） (2025-05-23T20:58:55Z)
• Collaborative non-parametric two-sample testing [55.98760097296213]
  目標は、null仮説の$p_v = q_v$が拒否されるノードを特定することである。 グラフ構造を効率的に活用する非パラメトリックコラボレーティブ2サンプルテスト(CTST)フレームワークを提案する。 提案手法は,f-divergence Estimation, Kernel Methods, Multitask Learningなどの要素を統合する。
  論文  参考訳（メタデータ） (2024-02-08T14:43:56Z)
• SimMatchV2: Semi-Supervised Learning with Graph Consistency [53.31681712576555]
  半教師付き学習アルゴリズムSimMatchV2を導入する。 グラフの観点からラベル付きデータとラベルなしデータの間の様々な一貫性の規則化を定式化する。 SimMatchV2は、複数の半教師付き学習ベンチマークで検証されている。
  論文  参考訳（メタデータ） (2023-08-13T05:56:36Z)
• Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching [68.35685422301613]
  そこで我々はMatchExplainerと呼ばれる新しい非パラメトリックな部分グラフマッチングフレームワークを提案し、説明的部分グラフを探索する。 ターゲットグラフと他のインスタンスを結合し、ノードに対応する距離を最小化することで最も重要な結合部分構造を識別する。 合成および実世界のデータセットの実験は、最先端のパラメトリックベースラインをかなりのマージンで上回り、MatchExplainerの有効性を示す。
  論文  参考訳（メタデータ） (2023-01-07T05:14:45Z)
• Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
  我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。 提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。 また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T04:36:15Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF) 我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。 我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
  論文  参考訳（メタデータ） (2022-05-28T15:37:03Z)
• Seeded graph matching for the correlated Gaussian Wigner model via the projected power method [5.639451539396459]
  グラフマッチングアルゴリズムとして,Emphprojected Power Method (PPM) の性能解析を行った。 PPM は定数 $sigma$ の反復でも機能し、(Mao et al. 2023) のスパース相関エルドス・レニー(CER) モデルに対する解析を (dense) CGW モデルに拡張する。
  論文  参考訳（メタデータ） (2022-04-08T14:31:26Z)
• Random Graph Matching with Improved Noise Robustness [2.294014185517203]
  本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。 我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。 これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
  論文  参考訳（メタデータ） (2021-01-28T02:39:27Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)

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

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