論文の概要: Graph Alignment via Birkhoff Relaxation
- arxiv url: http://arxiv.org/abs/2503.05323v1
- Date: Fri, 07 Mar 2025 11:01:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-10 12:22:52.091674
- Title: Graph Alignment via Birkhoff Relaxation
- Title（参考訳）: バーコフ緩和によるグラフアライメント
- Authors: Sushil Mahavir Varma, Irène Waldspurger, Laurent Massoulié,
- Abstract要約: 本稿では,バーコフ緩和,QAPの密接な凸緩和,およびその性能に関する理論的保証について分析する。
最適解である$Xstar$は、小さな$sigma$に対して$Pistar$の小さな摂動から、$sigma$として$Pistar$と十分に分離された状態への遷移が大きくなることを示す。
- 参考スコア（独自算出の注目度）: 7.761414660999871
- License:
- Abstract: We consider the graph alignment problem, wherein the objective is to find a vertex correspondence between two graphs that maximizes the edge overlap. The graph alignment problem is an instance of the quadratic assignment problem (QAP), known to be NP-hard in the worst case even to approximately solve. In this paper, we analyze Birkhoff relaxation, a tight convex relaxation of QAP, and present theoretical guarantees on its performance when the inputs follow the Gaussian Wigner Model. More specifically, the weighted adjacency matrices are correlated Gaussian Orthogonal Ensemble with correlation $1/\sqrt{1+\sigma^2}$. Denote the optimal solutions of the QAP and Birkhoff relaxation by $\Pi^\star$ and $X^\star$ respectively. We show that $\|X^\star-\Pi^\star\|_F^2 = o(n)$ when $\sigma = o(n^{-1.25})$ and $\|X^\star-\Pi^\star\|_F^2 = \Omega(n)$ when $\sigma = \Omega(n^{-0.5})$. Thus, the optimal solution $X^\star$ transitions from a small perturbation of $\Pi^\star$ for small $\sigma$ to being well separated from $\Pi^\star$ as $\sigma$ becomes larger than $n^{-0.5}$. This result allows us to guarantee that simple rounding procedures on $X^\star$ align $1-o(1)$ fraction of vertices correctly whenever $\sigma = o(n^{-1.25})$. This condition on $\sigma$ to ensure the success of the Birkhoff relaxation is state-of-the-art.
- Abstract（参考訳）: グラフアライメントの問題を考えると、エッジオーバーラップを最大化する2つのグラフ間の頂点対応を見つけることが目的である。
グラフアライメント問題は2次代入問題 (QAP) の例であり、ほぼ解決できる最悪の場合でもNPハードであることが知られている。
本稿では,Birkhoffの緩和,QAPの厳密な凸緩和,および入力がガウスウィグナーモデルに従えば,その性能に関する理論的保証を示す。
具体的には、重み付き隣接行列はガウス直交アンサンブルと1/\sqrt{1+\sigma^2}$の相関関係を持つ。
QAP とバーホフ緩和の最適解は、それぞれ $\Pi^\star$ と $X^\star$ で記述する。
我々は、$\|X^\star-\Pi^\star\|_F^2 = o(n)$ if $\sigma = o(n^{-1.25})$ and $\|X^\star-\Pi^\star\|_F^2 = \Omega(n)$ when $\sigma = \Omega(n^{-0.5})$を示す。
したがって、最適解である$X^\star$は、小さな$\Pi^\star$に対する小さな摂動から、$\Pi^\star$から十分に分離された$\Pi^\star$への遷移は、$n^{-0.5}$よりも大きくなる。
この結果から、$X^\star$ 上の単純な丸め手順は、$\sigma = o(n^{-1.25})$ のときに正しく1-o(1)$ の頂点を整列することを保証できる。
バーコフ緩和の成功を確実にするための$\sigma$のこの条件は最先端である。
関連論文リスト
- Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs [0.0]
2つの問題に対して計算硬度を示す。
我々の証明の主な要素の1つは、2つの確率測度の間の近位関係を導出することである。
このフレームワークは、異なるタスク間のリダクションを実行するための便利なツールを提供する。
論文 参考訳（メタデータ） (2025-02-14T00:24:51Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - A note on estimating the dimension from a random geometric graph [2.3020018305241337]
グラフの隣接行列にアクセスする際に、基礎空間の次元$d$を推定する問題について検討する。
また、密度の条件がなければ、$d$の一貫した推定子は$n r_nd to infty$と$r_n = o(1)$が存在することを示す。
論文 参考訳（メタデータ） (2023-11-21T23:46:44Z) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳（メタデータ） (2023-04-17T10:38:08Z) - Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。
近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。
副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
論文 参考訳（メタデータ） (2022-02-22T04:14:45Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。
これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
論文 参考訳（メタデータ） (2021-10-11T05:07:50Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - The planted matching problem: Sharp threshold and infinite-order phase
transition [25.41713098167692]
ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。
任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
論文 参考訳（メタデータ） (2021-03-17T00:59:33Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳（メタデータ） (2020-11-24T22:39:21Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。