論文の概要: Robust random graph matching in dense graphs via vector approximate message passing

• arxiv url: http://arxiv.org/abs/2412.16457v1
• Date: Sat, 21 Dec 2024 03:15:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-24 16:00:03.792583
• Title: Robust random graph matching in dense graphs via vector approximate message passing
• Title（参考訳）: ベクトル近似メッセージパッシングによる高密度グラフのロバストランダムグラフマッチング
• Authors: Zhangsong Li,
• Abstract要約: 本稿では,2つの相関したガウスウィグナー行列の一致回復問題と潜在対応性に着目する。 我々のアルゴリズムは,n1-o(1)$の任意の逆摂動の下で頑健な,最初の効率的なランダムグラフマッチング型アルゴリズムである。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: In this paper, we focus on the matching recovery problem between a pair of correlated Gaussian Wigner matrices with a latent vertex correspondence. We are particularly interested in a robust version of this problem such that our observation is a perturbed input $(A+E,B+F)$ where $(A,B)$ is a pair of correlated Gaussian Wigner matrices and $E,F$ are adversarially chosen matrices supported on an unknown $\epsilon n * \epsilon n$ principle minor of $A,B$, respectively. We propose a vector-approximate message passing (vector-AMP) algorithm that succeeds in polynomial time as long as the correlation $\rho$ between $(A,B)$ is a non-vanishing constant and $\epsilon = o\big( \tfrac{1}{(\log n)^{20}} \big)$. The main methodological inputs for our result are the iterative random graph matching algorithm proposed in \cite{DL22+, DL23+} and the spectral cleaning procedure proposed in \cite{IS24+}. To the best of our knowledge, our algorithm is the first efficient random graph matching type algorithm that is robust under any adversarial perturbations of $n^{1-o(1)}$ size.
• Abstract（参考訳）: 本稿では,一対のガウスウィグナー行列と潜在頂点対応との整合性に着目する。 特に、この問題の頑健なバージョンは、我々の観測が摂動入力$(A+E,B+F)$であり、$(A,B)$は相関したガウスウィグナー行列の対であり、$E,F$は、未知の$\epsilon n * \epsilon n$ principle minor of $A,B$で、逆選択された行列である。 ベクトル-近似メッセージパッシング(ベクター-AMP)アルゴリズムを提案し、相関式$\rho$と$(A,B)$と$\epsilon = o\big( \tfrac{1}{(\log n)^{20}} \big)$との多項式時間で成功する。 本研究の主な手法は, \cite{DL22+, DL23+} で提案した反復ランダムグラフマッチングアルゴリズムと, \cite{IS24+} で提案したスペクトル浄化法である。 我々の知る限り、我々のアルゴリズムは、n^{1-o(1)}$の任意の逆摂動の下で頑健である最初の効率的なランダムグラフマッチング型アルゴリズムである。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering [18.29151197560866]
  我々は[Makarychev, Makarychev and Vijayaraghavan, STOC'12] の半ランダムグラフモデルを考える。 時間アルゴリズムは、カットされた$(A, B)$がサイズ$Omega(alpha)$である限り、alphad Cutの問題を最大$O(alpha)$ [MMV'12]に近似することが知られている。 この問題の微細な複雑さについて検討し,[MMV'12]と同じような性能を示す最初のニア線形時間サブルーチンを提示する。
  論文  参考訳（メタデータ） (2024-06-07T11:40:54Z)
• The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime [0.0]
  2つの相関したランダムな幾何グラフのマッチングの問題に触発され、潜在ノード置換によって相関した2つのガウス幾何学モデルのマッチング問題を研究する。 A_i,j=langle X_i,X_j rangle$, $B_i,j=langle Y_i,Y_j rangle$ で与えられるエッジウェイトを持つ2種類の(相関した)重み付き完全グラフを考える。
  論文  参考訳（メタデータ） (2024-02-23T04:58:54Z)
• Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
  我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。 特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。 主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
  論文  参考訳（メタデータ） (2023-12-14T12:53:34Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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