論文の概要: 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$ の条件を改善する。

関連論文リスト

• Efficient Graph Matching for Correlated Stochastic Block Models [7.320365821066744]
  2つのバランスの取れたコミュニティを持つ相関ブロックモデルの学習問題について検討する。 我々の主な成果は、この設定におけるグラフマッチングのための最初の効率的なアルゴリズムである。 我々はこれを情報理論的に可能であれば、正確なグラフマッチングのための効率的なアルゴリズムに拡張する。
  論文  参考訳（メタデータ） (2024-12-03T18:36:45Z)
• Graph Mixup with Soft Alignments [49.61520432554505]
  本研究では,画像上での使用に成功しているミキサアップによるグラフデータの増大について検討する。 ソフトアライメントによるグラフ分類のための簡易かつ効果的な混合手法であるS-Mixupを提案する。
  論文  参考訳（メタデータ） (2023-06-11T22:04:28Z)
• A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation [12.869436542291144]
  本稿では,2つの相関した ErdHos--R'enyi グラフと,エッジが潜時対応によって相関している$n$ とをマッチングする効率的なアルゴリズムを提案する。 我々のアルゴリズムは実行時間を持ち、エッジの相関が無くなる限り、潜時マッチングを回復することに成功した。
  論文  参考訳（メタデータ） (2023-06-01T00:58:50Z)
• Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach [9.13755431537592]
  本稿では,相関クラスタリング問題を$O(mtimesleft(2+ alpha (G) right)+n)$から$O(m+n)$に近似する複雑性を,完全符号グラフに対して$varepsilon$とする。 提案手法は,元のアルゴリズムと同じ出力を与え,そのアルゴリズムをフルダイナミックな設定で実装できるようにする。
  論文  参考訳（メタデータ） (2023-01-01T10:57:36Z)
• 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)
• Verification and search algorithms for causal DAGs [11.038866111306728]
  クレーム因果グラフの正しさを確認するために、最小サイズの原子介入のセットを特徴づける。 我々は,ノード依存の介入コストと境界サイズ介入の設定に対して,その結果を一般化する。 この結果は、一般の未重み付きグラフ上での検証サイズに対する非自明な近似を保証する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2022-06-30T15:52:30Z)
• 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)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)
• Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
  既存のディープニューラルネットワーク手法では、隣接行列を構築することで、$Omega(n2)$複雑さを必要とする。 我々は,この空間を利用して完全隣接行列を生成する新しい自己回帰モデルBiGGを開発した。 トレーニング中、この自己回帰モデルは$O(log n)$同期ステージで並列化できる。
  論文  参考訳（メタデータ） (2020-06-28T04:37:57Z)

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

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