論文の概要: Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2507.20226v1
• Date: Sun, 27 Jul 2025 11:10:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-29 16:23:57.278929
• Title: Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks
• Title（参考訳）: アルゴリズムとグラフニューラルネットワークを組み合わせた部分グラフマッチングの改良
• Authors: Shuyang Guo, Wenjin Xie, Ping Lu, Ting Deng, Richong Zhang, Jianxin Li, Xiangping Huang, Zhongyi Liu,
• Abstract要約: ホモモルフィズムは、その構造を保存するグラフの間のキーマッピング技術である。 グラフ準同型のための最初のグラフニューラルネットワークフレームワークであるHFrameを提案する。 HFrameは正確なマッチングアルゴリズムよりも最大101.91倍高速で、平均精度は0.962である。
• 参考スコア（独自算出の注目度）: 23.01521187724899
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Homomorphism is a key mapping technique between graphs that preserves their structure. Given a graph and a pattern, the subgraph homomorphism problem involves finding a mapping from the pattern to the graph, ensuring that adjacent vertices in the pattern are mapped to adjacent vertices in the graph. Unlike subgraph isomorphism, which requires a one-to-one mapping, homomorphism allows multiple vertices in the pattern to map to the same vertex in the graph, making it more complex. We propose HFrame, the first graph neural network-based framework for subgraph homomorphism, which integrates traditional algorithms with machine learning techniques. We demonstrate that HFrame outperforms standard graph neural networks by being able to distinguish more graph pairs where the pattern is not homomorphic to the graph. Additionally, we provide a generalization error bound for HFrame. Through experiments on both real-world and synthetic graphs, we show that HFrame is up to 101.91 times faster than exact matching algorithms and achieves an average accuracy of 0.962.
• Abstract（参考訳）: ホモモルフィズムは、その構造を保存するグラフの間のキーマッピング技術である。 グラフとパターンが与えられたとき、部分グラフ準同型問題は、パターンからグラフへの写像を見つけ、そのパターンの隣接頂点がグラフの隣接頂点にマップされることを保証する。 1対1の写像を必要とする部分グラフ同型とは異なり、同型はパターン内の複数の頂点をグラフ内の同じ頂点にマッピングすることができ、より複雑になる。 我々は,従来のアルゴリズムを機械学習技術と統合した,グラフ準同型のための最初のグラフニューラルネットワークベースのフレームワークであるHFrameを提案する。 HFrameは、パターンがグラフに同型でないグラフペアをより多く区別することで、標準的なグラフニューラルネットワークよりも優れていることを示す。 さらに、HFrameに対して一般化誤差を提供する。 実世界のグラフと合成グラフの両方の実験を通して、HFrameは正確なマッチングアルゴリズムの最大101.91倍の速度を示し、平均精度は0.962である。

関連論文リスト

• HeGMN: Heterogeneous Graph Matching Network for Learning Graph Similarity [3.6560264185068916]
  本稿ではヘテロジニアスグラフマッチングネットワーク(HeGMN)を提案する。 2層マッチング機構からなるエンドツーエンドのグラフ類似性学習フレームワークである。 HeGMNは、すべてのデータセットにおけるグラフ類似性予測の高度なパフォーマンスを一貫して達成する。
  論文  参考訳（メタデータ） (2025-03-11T07:36:35Z)
• PlanE: Representation Learning over Planar Graphs [9.697671872347131]
  この研究はホップクロフトとタージャンの古典的な平面グラフ同型アルゴリズムにインスパイアされている。 PlanEには、実用的な拡張性を維持しながら、平面グラフ上の完全な不変性を学習できるアーキテクチャが含まれている。
  論文  参考訳（メタデータ） (2023-07-03T17:45:01Z)
• Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs [48.79929516665371]
  ホモフィリーなエッジを持つグラフは、同じクラスでノードを接続する傾向がある。 ヘテロフィ的傾向のあるエッジは、異なるクラスを持つノード間の関係を構築する傾向がある。 既存のGNNはトレーニング中にオリジナルのグラフのみを取る。
  論文  参考訳（メタデータ） (2023-06-13T08:06:10Z)
• Graph Mixup with Soft Alignments [49.61520432554505]
  本研究では,画像上での使用に成功しているミキサアップによるグラフデータの増大について検討する。 ソフトアライメントによるグラフ分類のための簡易かつ効果的な混合手法であるS-Mixupを提案する。
  論文  参考訳（メタデータ） (2023-06-11T22:04:28Z)
• CGMN: A Contrastive Graph Matching Network for Self-Supervised Graph Similarity Learning [65.1042892570989]
  自己教師付きグラフ類似性学習のためのコントラストグラフマッチングネットワーク(CGMN)を提案する。 我々は,効率的なノード表現学習のために,クロスビューインタラクションとクロスグラフインタラクションという2つの戦略を用いる。 我々はノード表現をグラフ類似性計算のためのプール演算によりグラフレベル表現に変換する。
  論文  参考訳（メタデータ） (2022-05-30T13:20:26Z)
• Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching [42.55928561326902]
  グラフニューラルネットワーク(GNN)とメッセージパッシングニューラルネットワーク(MPNN)は、サブグラフ構造に対して表現可能であることが証明されている。 サブストラクチャ表現学習を強化するために,デュアルメッセージパッシングニューラルネットワーク(DMPNN)を提案する。
  論文  参考訳（メタデータ） (2021-12-16T10:23:48Z)
• Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
  本稿では,グラフマッチングを向上するための信頼度の高いグラフ構造を探索するために,GLAMという共用電子グラフ学習とマッチングネットワークを提案する。 提案手法は,3つの人気ビジュアルマッチングベンチマーク (Pascal VOC, Willow Object, SPair-71k) で評価される。 すべてのベンチマークにおいて、従来の最先端のグラフマッチング手法よりも大きなマージンを達成している。
  論文  参考訳（メタデータ） (2021-09-01T08:24:02Z)
• Learning on heterogeneous graphs using high-order relations [37.64632406923687]
  メタパスを使わずに異種グラフを学習する手法を提案する。 異種グラフを異なる同種関係型グラフに分解し、それを結合して高階関係型表現を生成する。
  論文  参考訳（メタデータ） (2021-03-29T12:02:47Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)
• High-Order Relation Construction and Mining for Graph Matching [36.880853889521845]
  高次情報を記述するために、反復線グラフが最初に導入された。 本稿では,HGMN(High-order Graph Matching Network)と呼ばれる新しいグラフマッチング手法を提案する。 実用的な制約を課すことで、HGMNは大規模グラフに拡張性を持たせることができる。
  論文  参考訳（メタデータ） (2020-10-09T03:30:02Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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