論文の概要: Random Graph Matching with Improved Noise Robustness

• arxiv url: http://arxiv.org/abs/2101.11783v1
• Date: Thu, 28 Jan 2021 02:39:27 GMT
• ステータス: 処理完了
• システム内更新日: 2021-01-31 17:59:00.125877
• Title: Random Graph Matching with Improved Noise Robustness
• Title（参考訳）: ノイズロバスト性向上によるランダムグラフマッチング
• Authors: Cheng Mao, Mark Rudelson, and Konstantin Tikhomirov
• Abstract要約: 本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。 我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。 これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
• 参考スコア（独自算出の注目度）: 2.294014185517203
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph matching, also known as network alignment, refers to finding a bijection between the vertex sets of two given graphs so as to maximally align their edges. This fundamental computational problem arises frequently in multiple fields such as computer vision and biology. Recently, there has been a plethora of work studying efficient algorithms for graph matching under probabilistic models. In this work, we propose a new algorithm for graph matching and show that, for two Erd\H{o}s-R\'enyi graphs with edge correlation $1-\alpha$, our algorithm recovers the underlying matching with high probability when $\alpha \le 1 / (\log \log n)^C$, where $n$ is the number of vertices in each graph and $C$ denotes a positive universal constant. This improves the condition $\alpha \le 1 / (\log n)^C$ achieved in previous work.
• Abstract（参考訳）: ネットワークアライメントとも呼ばれるグラフマッチングは、与えられた2つのグラフの頂点セット間のバイジェクションを見つけ、エッジを最大にアライメントすることを意味します。 この基本的な計算問題は、コンピュータビジョンや生物学などの複数の分野で頻繁に発生します。 近年、確率モデルの下でのグラフマッチングの効率的なアルゴリズムの研究が数多く行われている。 本研究では, グラフマッチングの新しいアルゴリズムを提案し, エッジ相関 1-\alpha$ を持つ2つの Erd\H{o}s-R\'enyi グラフに対して, このアルゴリズムは $\alpha \le 1 / (\log \log n)^C$ が各グラフの頂点数で, C$ は正の普遍定数を表す。 これは前作で達成した $\alpha \le 1 / (\log n)^C$ の条件を改善する。

関連論文リスト

• 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)
• Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
  本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。 これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
  論文  参考訳（メタデータ） (2021-10-11T05:07:50Z)
• Random Subgraph Detection Using Queries [56.96625809888241]
  植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。 任意の(おそらくランダム化される)アルゴリズムは、$mathsfQ = Omega(fracn2k2chi4(p||q)log2n)$アダプティブクエリを生成する必要がある。 次に、$mathsfQ = O(fracn4)を用いて植木部分グラフを検出できる準多項式時間アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-10-02T07:41:17Z)
• Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions [9.29659220237395]
  本稿では,相関クラスタリングの解法を提案する。 我々は高効率な時間と空間の複雑さを持つサブ線形アルゴリズムを得る。 提案手法の主な要素はスパース線グラフ分解への新規な接続である。
  論文  参考訳（メタデータ） (2021-09-29T16:25:02Z)
• Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
  本稿では,グラフマッチングを向上するための信頼度の高いグラフ構造を探索するために,GLAMという共用電子グラフ学習とマッチングネットワークを提案する。 提案手法は,3つの人気ビジュアルマッチングベンチマーク (Pascal VOC, Willow Object, SPair-71k) で評価される。 すべてのベンチマークにおいて、従来の最先端のグラフマッチング手法よりも大きなマージンを達成している。
  論文  参考訳（メタデータ） (2021-09-01T08:24:02Z)
• Correlation detection in trees for partial graph alignment [3.5880535198436156]
  グラフのアライメントは,エッジの大部分を保存する2つのグラフのノード間のマッピングを探索する。 我々のアプローチは、2つのグラフの局所構造を比較し、その近傍が相関グラフに対して「十分近い」場合、2つのノードをマッチングすることである。 この問題は、一対の分岐木が積分布または相関分布から引き出されるかどうかの検定の観点から説明できる。
  論文  参考訳（メタデータ） (2021-07-15T22:02:27Z)
• Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time [1.5644420658691407]
  エッジ重み付きグラフ上での階層的凝集クラスタリング(HAC)アルゴリズムについて検討する。 階層的な集合グラフクラスタリングのためのアルゴリズムフレームワークを定義する。 提案手法は,ポイントデータセットのクラスタリングを20.7～76.5倍の速度で高速化できることを示す。
  論文  参考訳（メタデータ） (2021-06-10T09:29:05Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [77.57736777744934]
  この論文は、広く使用されている加速勾配追跡を再検討し、拡張する。 私たちの複雑さは $cal O(frac1epsilon5/7)$ と $cal O(fracLmu)5/7frac1 (1-sigma)1.5logfrac1epsilon)$ で大幅に改善します。
  論文  参考訳（メタデータ） (2021-04-06T15:34:14Z)
• 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)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。