論文の概要: Random graph matching at Otter's threshold via counting chandeliers
- arxiv url: http://arxiv.org/abs/2209.12313v1
- Date: Sun, 25 Sep 2022 20:00:28 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-27 17:54:15.274294
- Title: Random graph matching at Otter's threshold via counting chandeliers
- Title（参考訳）: 計数シャンデリアによるオッターしきい値のランダムグラフマッチング
- Authors: Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H. Yu
- Abstract要約: そこで本研究では,各木に根付いた重み付き木を数えることで構築した類似度スコアに基づく,グラフマッチングの効率的なアルゴリズムを提案する。
これは、明示的な一定の相関で成功し、スパースグラフと密度グラフの両方に適用する最初のグラフマッチングアルゴリズムである。
- 参考スコア（独自算出の注目度）: 16.512416293014493
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose an efficient algorithm for graph matching based on similarity
scores constructed from counting a certain family of weighted trees rooted at
each vertex. For two Erd\H{o}s-R\'enyi graphs $\mathcal{G}(n,q)$ whose edges
are correlated through a latent vertex correspondence, we show that this
algorithm correctly matches all but a vanishing fraction of the vertices with
high probability, provided that $nq\to\infty$ and the edge correlation
coefficient $\rho$ satisfies $\rho^2>\alpha \approx 0.338$, where $\alpha$ is
Otter's tree-counting constant. Moreover, this almost exact matching can be
made exact under an extra condition that is information-theoretically
necessary. This is the first polynomial-time graph matching algorithm that
succeeds at an explicit constant correlation and applies to both sparse and
dense graphs. In comparison, previous methods either require $\rho=1-o(1)$ or
are restricted to sparse graphs.
The crux of the algorithm is a carefully curated family of rooted trees
called chandeliers, which allows effective extraction of the graph correlation
from the counts of the same tree while suppressing the undesirable correlation
between those of different trees.
- Abstract（参考訳）: 本稿では,各頂点に根ざした重み付き木群を数えることによって構築した類似度スコアに基づくグラフマッチングの効率的なアルゴリズムを提案する。
2つの Erd\H{o}s-R\'enyi graphs $\mathcal{G}(n,q)$ の辺が潜在頂点対応によって相関している場合、このアルゴリズムは頂点の消滅分数を除く全ての分数と高い確率で正しく一致していることを示し、$nq\to\infty$ とエッジ相関係数 $\rho$ satisfies $\rho^2>\alpha \approx 0.338$ が成り立つ。
さらに、このほぼ正確なマッチングは、情報理論上必要となる余分な条件の下で正確にすることができる。
これは、明示的な定数相関で成功し、疎グラフと密グラフの両方に適用する最初の多項式時間グラフマッチングアルゴリズムである。
対照的に、以前の方法は$\rho=1-o(1)$を必要とするか、スパースグラフに制限される。
このアルゴリズムのcruxは、chandeliersと呼ばれる根付き木の注意深くキュレートされたファミリーであり、異なる木の間の望ましくない相関を抑制しながら、同じ木の数からグラフ相関を効果的に抽出することができる。
関連論文リスト
- A polynomial-time iterative algorithm for random graph matching with
non-vanishing correlation [12.869436542291144]
本稿では,2つの相関した ErdHos--R'enyi グラフと,エッジが潜時対応によって相関している$n$ とをマッチングする効率的なアルゴリズムを提案する。
我々のアルゴリズムは実行時間を持ち、エッジの相関が無くなる限り、潜時マッチングを回復することに成功した。
論文 参考訳（メタデータ） (2023-06-01T00:58:50Z) - Efficient Algorithms for Exact Graph Matching on Correlated Stochastic
Block Models with Constant Correlation [7.914348940034351]
本稿では,グラフとコミュニティ構造をマッチングする効率的なアルゴリズムを提案する。
我々のアルゴリズムは2つの相関ブロックモデル間の正確なマッチングを実現する最初の低次時間アルゴリズムである。
論文 参考訳（メタデータ） (2023-05-31T09:06:50Z) - 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) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳（メタデータ） (2022-08-18T09:19:01Z) - Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF)
我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。
我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
論文 参考訳（メタデータ） (2022-05-28T15:37:03Z) - Testing network correlation efficiently via counting trees [19.165942326142538]
本稿では,2つのネットワークがエッジ関連であるかどうかを潜時対応によって検証する新しい手法を提案する。
テスト統計は、非同型木族に対する符号付き木の共起を数えることに基づいている。
論文 参考訳（メタデータ） (2021-10-22T14:47:20Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Correlation detection in trees for partial graph alignment [3.5880535198436156]
グラフのアライメントは,エッジの大部分を保存する2つのグラフのノード間のマッピングを探索する。
我々のアプローチは、2つのグラフの局所構造を比較し、その近傍が相関グラフに対して「十分近い」場合、2つのノードをマッチングすることである。
この問題は、一対の分岐木が積分布または相関分布から引き出されるかどうかの検定の観点から説明できる。
論文 参考訳（メタデータ） (2021-07-15T22:02:27Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。