論文の概要: Graph Matching with Partially-Correct Seeds
- arxiv url: http://arxiv.org/abs/2004.03816v2
- Date: Tue, 5 Jan 2021 17:32:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-15 09:39:34.689004
- Title: Graph Matching with Partially-Correct Seeds
- Title（参考訳）: 部分修正種子を用いたグラフマッチング
- Authors: Liren Yu, Jiaming Xu, and Xiaojun Lin
- Abstract要約: この新しい2ドルのホップアルゴリズムは、グラフがスパースである場合の1ドルホップアルゴリズムよりも、はるかに少ない正しいシードを必要とする。
1ドルのホップアルゴリズムと2ドルのホップアルゴリズムの新たなパフォーマンス保証を組み合わせることで、最もよく知られた結果が得られます。
数値実験は、様々な合成グラフおよび実グラフ上での2ドルホップアルゴリズムの優位性を実証し、我々の理論的な知見を裏付けるものである。
- 参考スコア（独自算出の注目度）: 20.998695802214677
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph matching aims to find the latent vertex correspondence between two
edge-correlated graphs and has found numerous applications across different
fields. In this paper, we study a seeded graph matching problem, which assumes
that a set of seeds, i.e., pre-mapped vertex-pairs, is given in advance. While
most previous work requires all seeds to be correct, we focus on the setting
where the seeds are partially correct. Specifically, consider two correlated
graphs whose edges are sampled independently from a parent \ER graph
$\mathcal{G}(n,p)$. A mapping between the vertices of the two graphs is
provided as seeds, of which an unknown $\beta$ fraction is correct. We first
analyze a simple algorithm that matches vertices based on the number of common
seeds in the $1$-hop neighborhoods, and then further propose a new algorithm
that uses seeds in the $2$-hop neighborhoods. We establish non-asymptotic
performance guarantees of perfect matching for both $1$-hop and $2$-hop
algorithms, showing that our new $2$-hop algorithm requires substantially fewer
correct seeds than the $1$-hop algorithm when graphs are sparse. Moreover, by
combining our new performance guarantees for the $1$-hop and $2$-hop
algorithms, we attain the best-known results (in terms of the required fraction
of correct seeds) across the entire range of graph sparsity and significantly
improve the previous results in
\cite{10.14778/2794367.2794371,lubars2018correcting} when $p\ge n^{-5/6}$. For
instance, when $p$ is a constant or $p=n^{-3/4}$, we show that only
$\Omega(\sqrt{n\log n})$ correct seeds suffice for perfect matching, while the
previously best-known results demand $\Omega(n)$ and $\Omega(n^{3/4}\log n)$
correct seeds, respectively. Numerical experiments corroborate our theoretical
findings, demonstrating the superiority of our $2$-hop algorithm on a variety
of synthetic and real graphs.
- Abstract（参考訳）: グラフマッチングは、2つのエッジ相関グラフ間の潜在頂点対応を見つけることを目的としており、様々な分野にまたがる多くの応用を見出している。
本稿では,あらかじめマップされた頂点対の種集合が事前に与えられることを前提として,シードグラフマッチング問題について検討する。
これまでのほとんどの作業では、すべての種子を正す必要がありますが、種子が部分的に正しい設定に焦点を合わせています。
具体的には、エッジが親グラフ $\mathcal{G}(n,p)$ から独立にサンプリングされる2つの相関グラフを考える。
2つのグラフの頂点間の写像は、未知の$\beta$区切りが正しい種子として提供される。
まず、1ドルのホップ地区の共通種数に基づいて頂点にマッチする単純なアルゴリズムを分析し、さらに2ドルのホップ地区の種を利用する新しいアルゴリズムを提案する。
我々は1ドルホップアルゴリズムと2ドルホップアルゴリズムの両方に完全一致するという漸近的でないパフォーマンス保証を確立し、新しい2ドルホップアルゴリズムはグラフがスパースである場合の1ドルホップアルゴリズムよりもはるかに少ない正しいシードを必要とすることを示す。
さらに、$$$hopと$$$$$hopアルゴリズムの新たな性能保証を組み合わせることで、グラフスパーシティの全範囲にわたって、最もよく知られた結果(正しい種子の必要な割合)を達成し、$p\ge n^{5/6}$の場合に、以前の結果を大幅に改善します。
例えば、$p$が定数または$p=n^{-3/4}$の場合、完全整合には$\Omega(\sqrt{n\log n})$ correct seed sufficeしか必要とせず、これまでよく知られていた結果は$\Omega(n)$と$\Omega(n^{3/4}\log n)$ correct seedを要求する。
数値実験は、様々な合成グラフおよび実グラフ上での2ドルホップアルゴリズムの優位性を実証し、我々の理論的な結果を裏付けるものである。
関連論文リスト
- Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。
我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。
提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
論文 参考訳（メタデータ） (2024-08-03T20:08:02Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - 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 at Otter's threshold via counting chandeliers [16.512416293014493]
そこで本研究では,各木に根付いた重み付き木を数えることで構築した類似度スコアに基づく,グラフマッチングの効率的なアルゴリズムを提案する。
これは、明示的な一定の相関で成功し、スパースグラフと密度グラフの両方に適用する最初のグラフマッチングアルゴリズムである。
論文 参考訳（メタデータ） (2022-09-25T20:00:28Z) - Verification and search algorithms for causal DAGs [11.038866111306728]
クレーム因果グラフの正しさを確認するために、最小サイズの原子介入のセットを特徴づける。
我々は,ノード依存の介入コストと境界サイズ介入の設定に対して,その結果を一般化する。
この結果は、一般の未重み付きグラフ上での検証サイズに対する非自明な近似を保証する最初のアルゴリズムである。
論文 参考訳（メタデータ） (2022-06-30T15:52:30Z) - Seeded graph matching for the correlated Gaussian Wigner model via the projected power method [5.639451539396459]
グラフマッチングアルゴリズムとして,Emphprojected Power Method (PPM) の性能解析を行った。
PPM は定数 $sigma$ の反復でも機能し、(Mao et al. 2023) のスパース相関エルドス・レニー(CER) モデルに対する解析を (dense) CGW モデルに拡張する。
論文 参考訳（メタデータ） (2022-04-08T14:31:26Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - The Power of $D$-hops in Matching Power-Law Graphs [20.88345367293753]
適切な定義のD$ホップ地区における低次種子を利用する効率的なアルゴリズムを開発した。
Chung-Luランダムグラフモデルにおいて、$n$頂点, max degree$Theta(sqrtn)$, and the power-law exponent $2beta3$, we show that as soon as $D> frac4-beta3-beta$, by optimally select the first slice, with high probability our algorithm can correct with a constant fraction of the true pairs。
論文 参考訳（メタデータ） (2021-02-23T05:36:58Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。