論文の概要: A polynomial-time iterative algorithm for random graph matching with
non-vanishing correlation
- arxiv url: http://arxiv.org/abs/2306.00266v1
- Date: Thu, 1 Jun 2023 00:58:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-02 18:50:02.988677
- Title: A polynomial-time iterative algorithm for random graph matching with
non-vanishing correlation
- Title（参考訳）: 非消滅相関を用いたランダムグラフマッチングのための多項式時間反復アルゴリズム
- Authors: Jian Ding, Zhangsong Li
- Abstract要約: 本稿では,2つの相関した ErdHos--R'enyi グラフと,エッジが潜時対応によって相関している$n$ とをマッチングする効率的なアルゴリズムを提案する。
我々のアルゴリズムは実行時間を持ち、エッジの相関が無くなる限り、潜時マッチングを回復することに成功した。
- 参考スコア（独自算出の注目度）: 7.343886246061388
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose an efficient algorithm for matching two correlated
Erd\H{o}s--R\'enyi graphs with $n$ vertices whose edges are correlated through
a latent vertex correspondence. When the edge density $q= n^{- \alpha+o(1)}$
for a constant $\alpha \in [0,1)$, we show that our algorithm has polynomial
running time and succeeds to recover the latent matching as long as the edge
correlation is non-vanishing. This is closely related to our previous work on a
polynomial-time algorithm that matches two Gaussian Wigner matrices with
non-vanishing correlation, and provides the first polynomial-time random graph
matching algorithm (regardless of the regime of $q$) when the edge correlation
is below the square root of the Otter's constant (which is $\approx 0.338$).
- Abstract（参考訳）: 本稿では,2つの相関した Erd\H{o}s--R\enyi グラフと,エッジが潜在頂点対応によって相関する$n$頂点とのマッチングアルゴリズムを提案する。
定数$\alpha \in [0,1)$に対して、エッジ密度$q=n^{- \alpha+o(1)}$のとき、我々のアルゴリズムは多項式実行時間を持ち、エッジ相関が消滅しない限り遅延マッチングを回復することに成功した。
これは、2つのガウス・ウィグナー行列と非バニッシュ相関をマッチングする多項式時間アルゴリズムの以前の研究と密接に関連しており、エッジ相関がオッター定数の平方根以下(約0.338$)である場合、最初の多項式時間ランダムグラフマッチングアルゴリズム($q$の条件によらず)を提供する。
関連論文リスト
- Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - A polynomial time iterative algorithm for matching Gaussian matrices
with non-vanishing correlation [7.343886246061388]
本稿では, 2つのガウス行列間の相関が消えない限り, 繰り返しマッチングアルゴリズムを提案する。
その結果、相関が任意に小さいとき、グラフマッチングタイプの問題を解く最初のアルゴリズムとなる。
論文 参考訳（メタデータ） (2022-12-28T03:30:47Z) - Random graph matching at Otter's threshold via counting chandeliers [16.512416293014493]
そこで本研究では,各木に根付いた重み付き木を数えることで構築した類似度スコアに基づく,グラフマッチングの効率的なアルゴリズムを提案する。
これは、明示的な一定の相関で成功し、スパースグラフと密度グラフの両方に適用する最初のグラフマッチングアルゴリズムである。
論文 参考訳（メタデータ） (2022-09-25T20:00:28Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - Sublinear Time and Space Algorithms for Correlation Clustering via
Sparse-Dense Decompositions [9.29659220237395]
本稿では,相関クラスタリングの解法を提案する。
我々は高効率な時間と空間の複雑さを持つサブ線形アルゴリズムを得る。
提案手法の主な要素はスパース線グラフ分解への新規な接続である。
論文 参考訳（メタデータ） (2021-09-29T16:25:02Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time [1.5644420658691407]
エッジ重み付きグラフ上での階層的凝集クラスタリング(HAC)アルゴリズムについて検討する。
階層的な集合グラフクラスタリングのためのアルゴリズムフレームワークを定義する。
提案手法は,ポイントデータセットのクラスタリングを20.7～76.5倍の速度で高速化できることを示す。
論文 参考訳（メタデータ） (2021-06-10T09:29:05Z) - Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。
我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
論文 参考訳（メタデータ） (2021-04-06T15: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) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。