論文の概要: Exact Matching of Random Graphs with Constant Correlation
- arxiv url: http://arxiv.org/abs/2110.05000v1
- Date: Mon, 11 Oct 2021 05:07:50 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-12 21:00:12.349021
- Title: Exact Matching of Random Graphs with Constant Correlation
- Title（参考訳）: 定数相関を持つランダムグラフの完全マッチング
- Authors: Cheng Mao, Mark Rudelson, Konstantin Tikhomirov
- Abstract要約: 本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。
これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
- 参考スコア（独自算出の注目度）: 2.578242050187029
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper deals with the problem of graph matching or network alignment for
Erd\H{o}s--R\'enyi graphs, which can be viewed as a noisy average-case version
of the graph isomorphism problem. Let $G$ and $G'$ be $G(n, p)$
Erd\H{o}s--R\'enyi graphs marginally, identified with their adjacency matrices.
Assume that $G$ and $G'$ are correlated such that $\mathbb{E}[G_{ij} G'_{ij}] =
p(1-\alpha)$. For a permutation $\pi$ representing a latent matching between
the vertices of $G$ and $G'$, denote by $G^\pi$ the graph obtained from
permuting the vertices of $G$ by $\pi$. Observing $G^\pi$ and $G'$, we aim to
recover the matching $\pi$. In this work, we show that for every $\varepsilon
\in (0,1]$, there is $n_0>0$ depending on $\varepsilon$ and absolute constants
$\alpha_0, R > 0$ with the following property. Let $n \ge n_0$,
$(1+\varepsilon) \log n \le np \le n^{\frac{1}{R \log \log n}}$, and $0 <
\alpha < \min(\alpha_0,\varepsilon/4)$. There is a polynomial-time algorithm
$F$ such that $\mathbb{P}\{F(G^\pi,G')=\pi\}=1-o(1)$. This is the first
polynomial-time algorithm that recovers the exact matching between vertices of
correlated Erd\H{o}s--R\'enyi graphs with constant correlation with high
probability. The algorithm is based on comparison of partition trees associated
with the graph vertices.
- Abstract（参考訳）: 本稿では、Erd\H{o}s--R\enyiグラフに対するグラフマッチングやネットワークアライメントの問題を扱う。
G$ と $G'$ を $G(n, p)$ Erd\H{o}s--R\enyi グラフとし、それらの隣接行列と同一視する。
G$ と $G'$ は $\mathbb{E}[G_{ij} G'_{ij}] = p(1-\alpha)$ と相関していると仮定する。
置換 $\pi$ は$G$ と $G'$ の頂点間の潜在マッチングを表すもので、$G^\pi$ は$G$ の頂点を$\pi$ で置換することによって得られるグラフである。
G^\pi$ と $G'$ を観測すると、一致する $\pi$ を回復する。
この研究では、すべての$\varepsilon \in (0,1]$ に対して、$\varepsilon$ と絶対定数 $\alpha_0, r > 0$ に依存する$n_0>0$ が存在することを示す。
n \ge n_0$, $(1+\varepsilon) \log n \le np \le n^{\frac{1}{r \log \log n}}$, and $0 < \alpha < \min(\alpha_0,\varepsilon/4)$ とする。
多項式時間アルゴリズム $f$ が存在して、$\mathbb{p}\{f(g^\pi,g')=\pi\}=1-o(1)$ となる。
これは、相関した erd\h{o}s--r\'enyi グラフの頂点と高い確率との正確なマッチングを回復する最初の多項式時間アルゴリズムである。
このアルゴリズムは、グラフ頂点に関連する分割木の比較に基づいている。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。
我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。
提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
論文 参考訳（メタデータ） (2024-08-03T20:08:02Z) - 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) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - 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) - Local Correlation Clustering with Asymmetric Classification Errors [12.277755088736864]
相関クラスタリング問題では、エッジを"similar"と"dissimilar"とラベルした完全な重み付きグラフ$G$が与えられる。
クラスタリングの$mathcalC$ of graph $G$の場合、同じエッジが$mathcalC$、エンドポイントが別のクラスタに属している場合は$mathcalC$、エンドポイントが同じクラスタに属している場合は$mathcalC$と一致しない。
我々は$pgeq 1$に対する不一致ベクトルの$ell_p$ノルムを最小化するクラスタリングを生成する。
論文 参考訳（メタデータ） (2021-08-11T12:31:48Z) - A common variable minimax theorem for graphs [3.0079490585515343]
我々は、$mathcalG$の全てのグラフに対して滑らかな非定数関数が存在するかどうかを同時に理解し、それが存在するかどうかをどうやって見つけるかという問題を研究する。
論文 参考訳（メタデータ） (2021-07-30T16:47:25Z) - Algorithms and Hardness for Linear Algebra on Geometric Graphs [14.822517769254352]
グリーンガードとロークリンの有名な高速多重極法における次元$dの指数的依存は改善できないことを示す。
これは高速多重極法について証明された最初の公式な制限である。
論文 参考訳（メタデータ） (2020-11-04T18:35:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。