論文の概要: CoSimGNN: Towards Large-scale Graph Similarity Computation

• arxiv url: http://arxiv.org/abs/2005.07115v7
• Date: Wed, 17 Aug 2022 02:20:15 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-03 04:46:30.179427
• Title: CoSimGNN: Towards Large-scale Graph Similarity Computation
• Title（参考訳）: CoSimGNN: 大規模グラフ類似性計算を目指して
• Authors: Haoyan Xu, Runjian Chen, Yueyang Wang, Ziheng Duan, Jie Feng
• Abstract要約: グラフニューラルネットワーク(GNN)はこのタスクにデータ駆動型ソリューションを提供する。 既存のGNNベースの手法は、それぞれ2つのグラフを埋め込んだり、グラフ全体のクロスグラフインタラクションをデプロイしたりするが、まだ競合する結果が得られない。 このフレームワークは,まず適応的なプーリング操作で大きなグラフを埋め込んで粗くし,最後に類似点を求めるために粗いグラフにきめ細かな相互作用を展開させる。
• 参考スコア（独自算出の注目度）: 5.17905821006887
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The ability to compute similarity scores between graphs based on metrics such as Graph Edit Distance (GED) is important in many real-world applications. Computing exact GED values is typically an NP-hard problem and traditional algorithms usually achieve an unsatisfactory trade-off between accuracy and efficiency. Recently, Graph Neural Networks (GNNs) provide a data-driven solution for this task, which is more efficient while maintaining prediction accuracy in small graph (around 10 nodes per graph) similarity computation. Existing GNN-based methods, which either respectively embeds two graphs (lack of low-level cross-graph interactions) or deploy cross-graph interactions for whole graph pairs (redundant and time-consuming), are still not able to achieve competitive results when the number of nodes in graphs increases. In this paper, we focus on similarity computation for large-scale graphs and propose the "embedding-coarsening-matching" framework CoSimGNN, which first embeds and coarsens large graphs with adaptive pooling operation and then deploys fine-grained interactions on the coarsened graphs for final similarity scores. Furthermore, we create several synthetic datasets which provide new benchmarks for graph similarity computation. Detailed experiments on both synthetic and real-world datasets have been conducted and CoSimGNN achieves the best performance while the inference time is at most 1/3 of that of previous state-of-the-art.
• Abstract（参考訳）: グラフ編集距離(GED)のようなメトリクスに基づいたグラフ間の類似度スコアを計算する能力は、現実の多くのアプリケーションにおいて重要である。 正確なGED値の計算は通常NPハード問題であり、従来のアルゴリズムは精度と効率のトレードオフが不十分である。 最近、グラフニューラルネットワーク(GNN)は、このタスクに対してデータ駆動型ソリューションを提供しており、より効率的であり、小さなグラフ(グラフ当たり約10ノード)の類似性計算において予測精度を維持する。 既存のGNNベースの手法は、それぞれ2つのグラフ(低レベルなクロスグラフ相互作用の欠如)を埋め込んだり、グラフペア全体のクロスグラフインタラクションをデプロイしたり(冗長性と時間を要する)、グラフ内のノード数が増加すると競合する結果が得られない。 本稿では,大規模グラフの類似度計算に焦点をあて,適応的なプーリング操作でまず大きなグラフを埋め込んで粗くし,最後に類似度スコアを得るために粗いグラフにきめ細かなインタラクションを展開させる「埋め込み・粗いマッチング」フレームワークCoSimGNNを提案する。 さらに,グラフ類似性計算のための新しいベンチマークを提供する合成データセットを複数作成する。 合成と実世界の両方のデータセットに関する詳細な実験が行われ、CoSimGNNは最高のパフォーマンスを達成している。

関連論文リスト

• Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
  ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる 本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。 我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
  論文  参考訳（メタデータ） (2024-05-27T17:52:12Z)
• Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Training [22.411609128594982]
  本稿では,畳み込みグラフを作成するためのCoarsening Via Convolution Matching (CONVMATCH)アルゴリズムと,高度にスケーラブルなA-CONVMATCHを提案する。 実世界のリンク予測とノード分類グラフデータセットを用いたCONVMATCHの評価を行った。
  論文  参考訳（メタデータ） (2023-12-24T16:07:14Z)
• Efficient Heterogeneous Graph Learning via Random Projection [65.65132884606072]
  不均一グラフニューラルネットワーク(HGNN)は、異種グラフを深層学習するための強力なツールである。 最近のプリ計算ベースのHGNNは、一時間メッセージパッシングを使用して不均一グラフを正規形テンソルに変換する。 我々はRandom Projection Heterogeneous Graph Neural Network (RpHGNN) というハイブリッド計算前HGNNを提案する。
  論文  参考訳（メタデータ） (2023-10-23T01:25:44Z)
• Co-attention Graph Pooling for Efficient Pairwise Graph Interaction Learning [19.58671020943416]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データからの処理と学習に有効であることが証明されている。 グラフプーリングにおけるコアテンションを用いた相互作用表現抽出のための,新しい,効率的なグラフレベルアプローチを提案する。 筆者らの手法であるCAGPool(Co-Attention Graph Pooling)は,従来の手法と比較して,分類処理と回帰処理の両面での競合性能を示す。
  論文  参考訳（メタデータ） (2023-07-28T07:53:34Z)
• Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
  グラフニューラルネットワーク(GNN)は、構造データのモデリングにおいて強力な能力を示している。 GMPTと呼ばれる新しいグラフマッチングベースのGNN事前学習フレームワークを提案する。 提案手法は,完全自己指導型プレトレーニングと粗粒型プレトレーニングに適用できる。
  論文  参考訳（メタデータ） (2022-03-03T09:53:53Z)
• Scalable Graph Neural Networks for Heterogeneous Graphs [12.44278942365518]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データを学習するためのパラメトリックモデルの一般的なクラスである。 最近の研究は、GNNが主に機能をスムースにするためにグラフを使用しており、ベンチマークタスクで競合する結果を示していると主張している。 本研究では、これらの結果が異種グラフに拡張可能かどうかを問うとともに、異なるエンティティ間の複数のタイプの関係を符号化する。
  論文  参考訳（メタデータ） (2020-11-19T06:03:35Z)
• Multilevel Graph Matching Networks for Deep Graph Similarity Learning [79.3213351477689]
  グラフ構造オブジェクト間のグラフ類似性を計算するためのマルチレベルグラフマッチングネットワーク(MGMN)フレームワークを提案する。 標準ベンチマークデータセットの欠如を補うため、グラフグラフ分類とグラフグラフ回帰タスクの両方のためのデータセットセットを作成し、収集した。 総合的な実験により、MGMNはグラフグラフ分類とグラフグラフ回帰タスクの両方において、最先端のベースラインモデルより一貫して優れていることが示された。
  論文  参考訳（メタデータ） (2020-07-08T19:48:19Z)
• Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
  GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。 高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。 このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
  論文  参考訳（メタデータ） (2020-07-03T09:30:07Z)
• Graph Partitioning and Graph Neural Network based Hierarchical Graph Matching for Graph Similarity Computation [5.710312846460821]
  グラフ類似性は、下流アプリケーションを容易にするために、1組のグラフ間の類似度スコアを予測することを目的としている。 この問題を効果的に解決するために,PSimGNNと呼ばれるグラフ分割とグラフニューラルネットワークに基づくモデルを提案する。 PSimGNNはグラフ類似度メトリックとして近似グラフ編集距離(GED)を用いてグラフ類似度計算タスクにおける最先端の手法より優れている。
  論文  参考訳（メタデータ） (2020-05-16T15:01:58Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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