論文の概要: The Power of $D$-hops in Matching Power-Law Graphs
- arxiv url: http://arxiv.org/abs/2102.12975v1
- Date: Tue, 23 Feb 2021 05:36:58 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-27 00:48:32.641830
- Title: The Power of $D$-hops in Matching Power-Law Graphs
- Title（参考訳）: パワーローグラフのマッチングにおける$d$-hopsのパワー
- Authors: Liren Yu, Jiaming Xu, Xiaojun Lin
- Abstract要約: 適切な定義の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。
- 参考スコア（独自算出の注目度）: 20.88345367293753
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies seeded graph matching for power-law graphs. Assume that
two edge-correlated graphs are independently edge-sampled from a common parent
graph with a power-law degree distribution. A set of correctly matched
vertex-pairs is chosen at random and revealed as initial seeds. Our goal is to
use the seeds to recover the remaining latent vertex correspondence between the
two graphs. Departing from the existing approaches that focus on the use of
high-degree seeds in $1$-hop neighborhoods, we develop an efficient algorithm
that exploits the low-degree seeds in suitably-defined $D$-hop neighborhoods.
Specifically, we first match a set of vertex-pairs with appropriate degrees
(which we refer to as the first slice) based on the number of low-degree seeds
in their $D$-hop neighborhoods. This significantly reduces the number of
initial seeds needed to trigger a cascading process to match the rest of the
graphs. Under the Chung-Lu random graph model with $n$ vertices, max degree
$\Theta(\sqrt{n})$, and the power-law exponent $2<\beta<3$, we show that as
soon as $D> \frac{4-\beta}{3-\beta}$, by optimally choosing the first slice,
with high probability our algorithm can correctly match a constant fraction of
the true pairs without any error, provided with only $\Omega((\log
n)^{4-\beta})$ initial seeds. Our result achieves an exponential reduction in
the seed size requirement, as the best previously known result requires
$n^{1/2+\epsilon}$ seeds (for any small constant $\epsilon>0$). Performance
evaluation with synthetic and real data further corroborates the improved
performance of our algorithm.
- Abstract（参考訳）: 本稿では,パワーローグラフに対するシードグラフマッチングについて検討する。
2つのエッジ関連グラフが、有理次数分布を持つ共通親グラフから独立にエッジサンプリングされることを仮定する。
正しく一致した頂点ペアのセットをランダムに選択し、初期種子として明らかにする。
我々のゴールは、2つのグラフ間の残りの潜在頂点対応を回復するために種を用いることである。
既存の1ドルホップ地区での高次種子の使用に焦点を当てたアプローチを出発し、適度に定義された$D$ホップ地区で低次種子を利用する効率的なアルゴリズムを開発しました。
具体的には、まず頂点ペアのセットと適切な度数(第1のスライスと呼ばれる)をマッチングし、ドルドル=ホップの近所の低次種子の数を計算します。
これにより、他のグラフと一致するカスケードプロセスをトリガーするために必要な初期種子の数を大幅に削減できます。
n$頂点, max degree $\Theta(\sqrt{n})$, and the power-law exponent $2<\beta<3$ のChung-Luランダムグラフモデルでは,$D> \frac{4-\beta}{3-\beta}$として,最初のスライスを最適に選択することによって,アルゴリズムは,$\Omega((\log n)^{4-\beta})$初期シーズのみで提供される,誤りのない真のペアの定数を正しく一致させることができることを示した。
この結果はシードサイズ要件を指数関数的に減少させ、最もよく知られた結果には$n^{1/2+\epsilon}$種(小さな定数$\epsilon>0$)が必要となる。
合成データと実データによる性能評価は,アルゴリズムの性能向上をさらに裏付ける。
関連論文リスト
- 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) - Improved High-Probability Regret for Adversarial Bandits with
Time-Varying Feedback Graphs [62.52390282012508]
我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。
提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。
また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-04T04:36:15Z) - Random graph matching at Otter's threshold via counting chandeliers [16.512416293014493]
そこで本研究では,各木に根付いた重み付き木を数えることで構築した類似度スコアに基づく,グラフマッチングの効率的なアルゴリズムを提案する。
これは、明示的な一定の相関で成功し、スパースグラフと密度グラフの両方に適用する最初のグラフマッチングアルゴリズムである。
論文 参考訳（メタデータ） (2022-09-25T20:00:28Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T16:21:31Z) - 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) - Projection-free Graph-based Classifier Learning using Gershgorin Disc
Perfect Alignment [59.87663954467815]
グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。
ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。
代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
論文 参考訳（メタデータ） (2021-06-03T07:22:48Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - 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) - Better Bounds on the Adaptivity Gap of Influence Maximization under
Full-adoption Feedback [15.533908352376853]
影響カスケードによって到達されるノードの期待数を最大化する$k$ノードのセットを探します。
適応性ギャップは $lceil nrceil $ で上界であることを示し、$n$ はグラフ内のノード数である。
また、0-有界グラフ、すなわち無向グラフにおいて、適応性ギャップは少なくとも$frac3e3e3-1approx 3.16$であることを示す。
論文 参考訳（メタデータ） (2020-06-27T14:43:34Z) - Graph Matching with Partially-Correct Seeds [20.998695802214677]
この新しい2ドルのホップアルゴリズムは、グラフがスパースである場合の1ドルホップアルゴリズムよりも、はるかに少ない正しいシードを必要とする。
1ドルのホップアルゴリズムと2ドルのホップアルゴリズムの新たなパフォーマンス保証を組み合わせることで、最もよく知られた結果が得られます。
数値実験は、様々な合成グラフおよび実グラフ上での2ドルホップアルゴリズムの優位性を実証し、我々の理論的な知見を裏付けるものである。
論文 参考訳（メタデータ） (2020-04-08T05:25:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。