論文の概要: Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Tests
- arxiv url: http://arxiv.org/abs/2607.09087v2
- Date: Tue, 14 Jul 2026 16:07:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-15 14:59:31.82147
- Title: Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Tests
- Title（参考訳）: ほぼ4次時間でほぼ完全に回復する:局所木相関試験によるランクベースグラフマッチング
- Abstract要約: 本稿では,相関した $textErds-Rényi$ (ER) グラフペアモデルに基づくグラフマッチングについて検討する。
本稿では,n2+o(1)の時間複雑性を持つグラフマッチングアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 27.444325804941773
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies graph matching under the correlated $\text{Erdős-Rényi}$ (ER) graph pair model. This model first samples an $\mathrm{ER}(n,\fracλ{ns})$ base graph, whose edges are then independently subsampled twice with probability $s$ to produce two correlated $\mathrm{ER}(n,\fracλ{n})$ graphs. We propose a graph matching algorithm that has $n^{2+o(1)}$ time complexity and achieves almost exact recovery with high probability under the assumptions $λ=(\log n)^{α+o(1)}$ for some $α\in(0,1)$ and $s\in(\sqrt{C_{\mathrm{Otter}}},1]$, where $C_{\mathrm{Otter}}\approx 0.338$ is Otter's tree-counting constant. This is the first algorithm with almost quadratic time complexity in this regime of $λ$, while the best known result in this regime is the chandelier-counting algorithm with time complexity $O(n^{c(s)})$, where $c(s)\rightarrow \infty$ as $s$ approaches $\sqrt{C_\mathrm{Otter}}$ from above. The proposed algorithm is based on local tree correlation tests. It uses a rank-based algorithm to match the vertex pairs instead of threshold-based rules in the literature. This avoids the need of computing an explicit threshold, which is computationally difficult to obtain. To prove the almost exact recovery result, we establish a new analysis of tree correlation tests in the diverging-degree regime, where both the mean degree and the tree depth grow with $n$. Based on this new result, we establish the existence of a threshold for a threshold-based graph matching algorithm via local tree correlation tests. Finally, we couple the performance of the rank-based algorithm with the threshold-based algorithm to show almost exact recovery.
- Abstract（参考訳）: 本稿では、相関した $\text{Erd's-Rényi}$ (ER) グラフペアモデルの下でグラフマッチングを研究する。
このモデルはまず$\mathrm{ER}(n,\fracλ{ns})$基底グラフをサンプリングし、そのエッジは2つの相関した$\mathrm{ER}(n,\fracλ{n})$グラフを生成する確率$s$で独立に2つのサブサンプリングされる。
例えば、ある$α\in(0,1)$と$s\in(\sqrt{C_{\mathrm{Otter}}},1]$に対して、$C_{\mathrm{Otter}}\approx 0.338$はオッターのツリーカウント定数である。
これは、この状態においてほぼ2次時間複雑性を持つ最初のアルゴリズムであり、この状態における最もよく知られた結果は、時間複雑性を持つチャンデリアカウントアルゴリズムである$O(n^{c(s)})$, where $c(s)\rightarrow \infty$ as $s$ approach $\sqrt{C_\mathrm{Otter}}$である。
提案アルゴリズムは局所木相関試験に基づく。
ランクベースのアルゴリズムを使用して、文献のしきい値ベースのルールの代わりに頂点ペアをマッチングする。
これにより、計算が困難である明示的なしきい値を計算する必要がなくなる。
ほぼ正確な回復結果を示すために,平均度と樹深の双方がn$で成長する発散度体制において,木相関試験の新たな解析方法を確立した。
この新たな結果に基づいて,局所木相関試験によるしきい値に基づくグラフマッチングアルゴリズムのしきい値の存在を確立した。
最後に、ランクに基づくアルゴリズムとしきい値に基づくアルゴリズムを組み合わせ、ほぼ正確に回復することを示す。
関連論文リスト
- High-Dimensional Procrustes Matching via Tree Counts [5.464035038606368]
Procrustes matching problem(英語版)は、2つの集合を整列する$[n]$の未知の置換を復元するように要求する。
gtrsim maxlog n/d,sqrtlog n/n$ のとき、正確な回復が可能であることを示す。
また,木数計算アルゴリズムには条件2 > sqrt$ が必要であることを示唆する低次優位計算を行う。
論文 参考訳（メタデータ） (2026-07-09T14:33:47Z) - Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。
フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文 参考訳（メタデータ） (2026-07-08T17:49:40Z) - Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
この研究は、パーソナライズされたPageRank計算を高速化するために、ネストした進化したセットプロセスに基づく新しいフレームワークを提案する。
このような局所化手法の時間複雑性は、PPRベクトルの$epsilon$-approximationを得るために$mintildemathcalO(R2/epsilon2), tildemathcalO(m)$によって上界となることを示す。
論文 参考訳（メタデータ） (2025-10-09T09:47:40Z) - 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) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An
Index-based Approach [9.13755431537592]
本稿では,相関クラスタリング問題を$O(mtimesleft(2+ alpha (G) right)+n)$から$O(m+n)$に近似する複雑性を,完全符号グラフに対して$varepsilon$とする。
提案手法は,元のアルゴリズムと同じ出力を与え,そのアルゴリズムをフルダイナミックな設定で実装できるようにする。
論文 参考訳（メタデータ） (2023-01-01T10:57:36Z) - Random graph matching at Otter's threshold via counting chandeliers [16.512416293014493]
そこで本研究では,各木に根付いた重み付き木を数えることで構築した類似度スコアに基づく,グラフマッチングの効率的なアルゴリズムを提案する。
これは、明示的な一定の相関で成功し、スパースグラフと密度グラフの両方に適用する最初のグラフマッチングアルゴリズムである。
論文 参考訳（メタデータ） (2022-09-25T20:00:28Z) - Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
カワラバヤシとソープは、単純なグラフ $G = (V,E)$ の最小カットに対して、ほぼ自明な時間決定論的アルゴリズムを与えた。
重み付きグラフの$(1+varepsilon)$-KTパーティションを見つけるために、線形に近い時間ランダム化アルゴリズムを与える。
論文 参考訳（メタデータ） (2021-11-02T05:26:10Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - 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) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。