Fugu-MT 論文翻訳(概要): Matching recovery threshold for correlated random graphs

論文の概要: Matching recovery threshold for correlated random graphs

arxiv url: http://arxiv.org/abs/2205.14650v1
Date: Sun, 29 May 2022 13:04:20 GMT
ステータス: 処理完了
システム内更新日: 2022-05-31 17:53:29.487726
Title: Matching recovery threshold for correlated random graphs
Title（参考訳）: 相関ランダムグラフに対するマッチング回復しきい値
Authors: Jian Ding, Hang Du
Abstract要約: 共通 ErdHos-R'enyi グラフ $mathbfG(n, p)$ から独立にサブサンプリングされた2つの相関グラフに対して、これらの2つのグラフのアンフィグアウトラベルの観測からそれらのエンフィラテントマッチングを回復したい。この結果は,近年のWu,Xu,Yuによる研究において一定の要因を導出する。
参考スコア（独自算出の注目度）: 9.12788494573002
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: For two correlated graphs which are independently sub-sampled from a common Erd\H{o}s-R\'enyi graph $\mathbf{G}(n, p)$, we wish to recover their \emph{latent} vertex matching from the observation of these two graphs \emph{without labels}. When $p = n^{-\alpha+o(1)}$ for $\alpha\in (0, 1]$, we establish a sharp information-theoretic threshold for whether it is possible to correctly match a positive fraction of vertices. Our result sharpens a constant factor in a recent work by Wu, Xu and Yu.
Abstract（参考訳）: 共通の Erd\H{o}s-R\'enyi graph $\mathbf{G}(n, p)$ から独立した2つの相関グラフに対して、これらの2つのグラフの観測からそれらの \emph{latent} 頂点マッチングを復元したい。 p = n^{-\alpha+o(1)}$ for $\alpha\in (0, 1]$ とすると、正の頂点の正の分数に正しく一致するかどうかについての鋭い情報理論しきい値を確立する。この結果は,近年のWu,Xu,Yuによる研究において一定の要因を導出する。

関連論文リスト

Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
論文参考訳（メタデータ） (2024-08-03T20:08:02Z)
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)
Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文参考訳（メタデータ） (2022-08-18T09:19:01Z)
Detection threshold for correlated Erd\H{o}s-R\'enyi graphs via densest subgraphs [9.12788494573002]
ラベルなしノード上の2つのErdHos-R'enyiランダムグラフ間のエッジ相関を検出する問題を解く。我々の研究における重要な新規性は、検出問題とエルドホス=ルネニグラフの最も密度の高い部分グラフの間の興味深い関係である。
論文参考訳（メタデータ） (2022-03-28T08:32:43Z)
AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
論文参考訳（メタデータ） (2021-11-12T07:08:13Z)
Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文参考訳（メタデータ） (2021-10-21T18:43:00Z)
Settling the Sharp Reconstruction Thresholds of Random Graph Matching [19.54246087326288]
2つのエッジ関連ランダムグラフ間の隠れた対応を復元する問題について検討する。 p=n-o(1)$のグラフに対して、鋭いしきい値が存在することが証明される。 sparse ErdHos-R'enyi graphs with $p=n-Theta(1)$ に対して、オール・オー・ナッシング現象はもはや成り立たないことを示す。
論文参考訳（メタデータ） (2021-01-29T21:49:50Z)
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)
Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文参考訳（メタデータ） (2020-12-10T15:40:07Z)
Testing correlation of unlabeled random graphs [18.08210501570919]
ラベルなしノードを持つ2つのランダムグラフ間のエッジ相関を検出する問題について検討する。これは仮説テスト問題として定式化され、ヌル仮説の下では、2つのグラフは独立に生成される。代替として、2つのグラフは、ある潜在ノード対応の下ではエッジ関連であるが、ヌルと同じ辺分布を持つ。
論文参考訳（メタデータ） (2020-08-23T19:19:45Z)

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