論文の概要: Efficient Algorithms for Exact Graph Matching on Correlated Stochastic
Block Models with Constant Correlation
- arxiv url: http://arxiv.org/abs/2305.19666v1
- Date: Wed, 31 May 2023 09:06:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-01 17:39:12.711943
- Title: Efficient Algorithms for Exact Graph Matching on Correlated Stochastic
Block Models with Constant Correlation
- Title（参考訳）: 定数相関を持つ相関確率ブロックモデルにおける厳密なグラフマッチングの効率的なアルゴリズム
- Authors: Joonhyuk Yang, Dongpil Shin, and Hye Won Chung
- Abstract要約: 本稿では,グラフとコミュニティ構造をマッチングする効率的なアルゴリズムを提案する。
我々のアルゴリズムは2つの相関ブロックモデル間の正確なマッチングを実現する最初の低次時間アルゴリズムである。
- 参考スコア（独自算出の注目度）: 7.914348940034351
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of graph matching, or learning vertex correspondence,
between two correlated stochastic block models (SBMs). The graph matching
problem arises in various fields, including computer vision, natural language
processing and bioinformatics, and in particular, matching graphs with inherent
community structure has significance related to de-anonymization of correlated
social networks. Compared to the correlated Erdos-Renyi (ER) model, where
various efficient algorithms have been developed, among which a few algorithms
have been proven to achieve the exact matching with constant edge correlation,
no low-order polynomial algorithm has been known to achieve exact matching for
the correlated SBMs with constant correlation. In this work, we propose an
efficient algorithm for matching graphs with community structure, based on the
comparison between partition trees rooted from each vertex, by extending the
idea of Mao et al. (2021) to graphs with communities. The partition tree
divides the large neighborhoods of each vertex into disjoint subsets using
their edge statistics to different communities. Our algorithm is the first
low-order polynomial-time algorithm achieving exact matching between two
correlated SBMs with high probability in dense graphs.
- Abstract（参考訳）: 本稿では,2つの相関確率ブロックモデル(SBM)間のグラフマッチングや頂点対応の学習について考察する。
グラフマッチング問題は、コンピュータビジョン、自然言語処理、バイオインフォマティクスなど様々な分野で発生し、特に、グラフと固有のコミュニティ構造とのマッチングは、相関したソーシャルネットワークの非匿名化に関係している。
様々な効率的なアルゴリズムが開発されている相関型erdos-renyi(er)モデルと比較して、一定のエッジ相関の正確なマッチングを達成するためにいくつかのアルゴリズムが証明されているが、相関付きsbmの正確なマッチングを達成するための低次多項式アルゴリズムは知られていない。
本研究では,Mao et al. (2021) のアイデアをコミュニティを持つグラフに拡張することにより,各頂点から根付いた分割木の比較に基づいて,グラフとコミュニティ構造をマッチングする効率的なアルゴリズムを提案する。
分割木は、それぞれの頂点の大きな近傍を、それぞれのエッジ統計を用いて異なるコミュニティに分割する。
本アルゴリズムは,2つの相関sbmと高密度グラフの確率の高いマッチングを実現する,最初の低次多項式時間アルゴリズムである。
関連論文リスト
- Optimizing the Induced Correlation in Omnibus Joint Graph Embeddings [14.008892752201593]
相関-OMNI問題と平坦相関問題について検討する。
相関-OMNI問題において、埋め込み空間における最適相関を誘導する一般化オムニバス重みの行列を推定するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-09-26T05:22:16Z) - Differentiable Proximal Graph Matching [40.41380102260085]
微分可能近位グラフマッチング(DPGM)と呼ばれる近位演算子に基づくグラフマッチングアルゴリズムを提案する。
アルゴリズム全体をグラフ親和性行列からノード対応の予測への微分可能な写像とみなすことができる。
数値実験により、PGMは様々なデータセット上で既存のグラフマッチングアルゴリズムより優れていることが示された。
論文 参考訳（メタデータ） (2024-05-26T08:17:13Z) - M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning
of Mixture Graph Matching and Clustering [57.947071423091415]
本稿では,理論収束を保証する学習自由度アルゴリズムであるM3Cを提案する。
我々は、新しいエッジワイド親和性学習と擬似ラベル選択を組み込んだ教師なしモデルUM3Cを開発した。
提案手法は,最先端のグラフマッチングと混合グラフマッチングとクラスタリングの手法を精度と効率の両面で優れている。
論文 参考訳（メタデータ） (2023-10-27T19:40:34Z) - Random graph matching at Otter's threshold via counting chandeliers [16.512416293014493]
そこで本研究では,各木に根付いた重み付き木を数えることで構築した類似度スコアに基づく,グラフマッチングの効率的なアルゴリズムを提案する。
これは、明示的な一定の相関で成功し、スパースグラフと密度グラフの両方に適用する最初のグラフマッチングアルゴリズムである。
論文 参考訳（メタデータ） (2022-09-25T20:00:28Z) - CGMN: A Contrastive Graph Matching Network for Self-Supervised Graph
Similarity Learning [65.1042892570989]
自己教師付きグラフ類似性学習のためのコントラストグラフマッチングネットワーク(CGMN)を提案する。
我々は,効率的なノード表現学習のために,クロスビューインタラクションとクロスグラフインタラクションという2つの戦略を用いる。
我々はノード表現をグラフ類似性計算のためのプール演算によりグラフレベル表現に変換する。
論文 参考訳（メタデータ） (2022-05-30T13:20:26Z) - Reinforcement Learning Based Query Vertex Ordering Model for Subgraph
Matching [58.39970828272366]
グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。
マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。
本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
論文 参考訳（メタデータ） (2022-01-25T00:10:03Z) - Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。
提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文 参考訳（メタデータ） (2022-01-05T13:37:27Z) - Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
本稿では,グラフマッチングを向上するための信頼度の高いグラフ構造を探索するために,GLAMという共用電子グラフ学習とマッチングネットワークを提案する。
提案手法は,3つの人気ビジュアルマッチングベンチマーク (Pascal VOC, Willow Object, SPair-71k) で評価される。
すべてのベンチマークにおいて、従来の最先端のグラフマッチング手法よりも大きなマージンを達成している。
論文 参考訳（メタデータ） (2021-09-01T08:24:02Z) - Factorizable Graph Convolutional Networks [90.59836684458905]
本稿では,グラフに符号化された相互に絡み合った関係を明示的に解消する新しいグラフ畳み込みネットワーク(GCN)を提案する。
FactorGCNは単純なグラフを入力として取り、それをいくつかの分解グラフに分解する。
提案したFacterGCNは,合成および実世界のデータセットに対して質的かつ定量的に評価する。
論文 参考訳（メタデータ） (2020-10-12T03:01:40Z) - CoSimGNN: Towards Large-scale Graph Similarity Computation [5.17905821006887]
グラフニューラルネットワーク(GNN)はこのタスクにデータ駆動型ソリューションを提供する。
既存のGNNベースの手法は、それぞれ2つのグラフを埋め込んだり、グラフ全体のクロスグラフインタラクションをデプロイしたりするが、まだ競合する結果が得られない。
このフレームワークは,まず適応的なプーリング操作で大きなグラフを埋め込んで粗くし,最後に類似点を求めるために粗いグラフにきめ細かな相互作用を展開させる。
論文 参考訳（メタデータ） (2020-05-14T16:33:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。