論文の概要: Graph2Region: Efficient Graph Similarity Learning with Structure and Scale Restoration

• arxiv url: http://arxiv.org/abs/2510.00394v1
• Date: Wed, 01 Oct 2025 01:10:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-03 14:32:17.186018
• Title: Graph2Region: Efficient Graph Similarity Learning with Structure and Scale Restoration
• Title（参考訳）: Graph2Region: 構造とスケール復元によるグラフ類似性学習の効率化
• Authors: Zhouyang Liu, Yixin Chen, Ning Liu, Jiezhong He, Dongsheng Li,
• Abstract要約: グラフ類似性はグラフ検索などのグラフ関連タスクにおいて重要であり、最大共通部分グラフ(MCS)やグラフ編集距離(GED)などのメトリクスが一般的に使用される。 最近のニューラルネットワークに基づくアプローチは、計算負担を軽減するために埋め込み空間における類似度スコアを近似している。 グラフ2Region (G2R) と呼ばれる新しい幾何学的グラフ埋め込み法を提案する。
• 参考スコア（独自算出の注目度）: 23.884990933878726
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph similarity is critical in graph-related tasks such as graph retrieval, where metrics like maximum common subgraph (MCS) and graph edit distance (GED) are commonly used. However, exact computations of these metrics are known to be NP-Hard. Recent neural network-based approaches approximate the similarity score in embedding spaces to alleviate the computational burden, but they either involve expensive pairwise node comparisons or fail to effectively utilize structural and scale information of graphs. To tackle these issues, we propose a novel geometric-based graph embedding method called Graph2Region (G2R). G2R represents nodes as closed regions and recovers their adjacency patterns within graphs in the embedding space. By incorporating the node features and adjacency patterns of graphs, G2R summarizes graph regions, i.e., graph embeddings, where the shape captures the underlying graph structures and the volume reflects the graph size. Consequently, the overlap between graph regions can serve as an approximation of MCS, signifying similar node regions and adjacency patterns. We further analyze the relationship between MCS and GED and propose using disjoint parts as a proxy for GED similarity. This analysis enables concurrent computation of MCS and GED, incorporating local and global structural information. Experimental evaluation highlights G2R's competitive performance in graph similarity computation. It achieves up to a 60.0\% relative accuracy improvement over state-of-the-art methods in MCS similarity learning, while maintaining efficiency in both training and inference. Moreover, G2R showcases remarkable capability in predicting both MCS and GED similarities simultaneously, providing a holistic assessment of graph similarity. Code available at https://github.com/liuzhouyang/Graph2Region.
• Abstract（参考訳）: グラフ類似性はグラフ検索などのグラフ関連タスクにおいて重要であり、最大共通部分グラフ(MCS)やグラフ編集距離(GED)などのメトリクスが一般的に使用される。 しかし、これらのメトリクスの正確な計算はNP-Hardであることが知られている。 最近のニューラルネットワークベースのアプローチでは、埋め込み空間における類似度スコアを近似して計算負担を軽減するが、高価な対のノード比較を必要とするか、グラフの構造的およびスケール的な情報を効果的に活用できない。 これらの問題に対処するために,グラフ2Region (G2R) と呼ばれる幾何学的グラフ埋め込み手法を提案する。 G2Rはノードを閉じた領域として表現し、埋め込み空間内のグラフ内の隣接パターンを復元する。 グラフのノードの特徴と隣接パターンを取り入れることで、G2Rはグラフ領域、すなわちグラフ埋め込みを要約する。 したがって、グラフ領域間の重複はMCSの近似として機能し、類似したノード領域と隣接パターンを示す。 さらに, MCS と GED の関係を解析し, GED 類似性のプロキシとして解離部分を用いることを提案する。 この分析により、局所的および大域的構造情報を組み込んだMCSとGEDの同時計算が可能となる。 グラフ類似性計算におけるG2Rの競合性能を実験的に評価する。 MCSの類似性学習における最先端手法に比べて60.0\%の精度向上を実現し、トレーニングと推論の両面で効率性を維持している。 さらに、G2RはMCSとGEDの類似性を同時に予測する優れた能力を示し、グラフの類似性を総合的に評価する。 コードはhttps://github.com/liuzhouyang/Graph2Regionで公開されている。

関連論文リスト

• Disentangled Graph Representation Based on Substructure-Aware Graph Optimal Matching Kernel Convolutional Networks [4.912298804026689]
  グラフは関係データを効果的に特徴付け、グラフ表現学習法を駆動する。 最近の不整合グラフ表現学習は、グラフデータの独立因子を分離することにより、解釈可能性を高める。 本稿では,この制限に対処するグラフ最適マッチングカーネル畳み込みネットワーク(GOMKCN)を提案する。
  論文  参考訳（メタデータ） (2025-04-23T02:26:33Z)
• Graph Similarity Computation via Interpretable Neural Node Alignment [19.34487413883093]
  GED(Graph Edit Distance)とMCS(Maximum Common Subgraphs)は、グラフの類似性を評価するために一般的に使用されるメトリクスである。 ディープラーニングモデルはよく知られたブラックボックス'であるため、典型的な1対1のノード/サブグラフアライメントプロセスは見ることができない。 我々は,ノードアライメント基底真理情報に頼ることなく,新しい解釈可能なニューラルノードアライメントモデルを提案する。
  論文  参考訳（メタデータ） (2024-12-13T10:23:27Z)
• Graph Edit Distance Learning via Different Attention [11.79198639644178]
  本稿では,新しいグラフレベル融合モジュールdifferate Attention(DiffAtt)を提案する。 DiffAttは2つのグラフレベルの埋め込みの違いを注目のメカニズムとして使用し、2つのグラフのグラフ構造の違いをキャプチャする。 DiffAtt に基づいた新しい GSC 手法である Graph Edit Distance Learning via Different Attention (REDRAFT) を提案する。
  論文  参考訳（メタデータ） (2023-08-26T13:05:01Z)
• CGMN: A Contrastive Graph Matching Network for Self-Supervised Graph Similarity Learning [65.1042892570989]
  自己教師付きグラフ類似性学習のためのコントラストグラフマッチングネットワーク(CGMN)を提案する。 我々は,効率的なノード表現学習のために,クロスビューインタラクションとクロスグラフインタラクションという2つの戦略を用いる。 我々はノード表現をグラフ類似性計算のためのプール演算によりグラフレベル表現に変換する。
  論文  参考訳（メタデータ） (2022-05-30T13:20:26Z)
• GraphDCA -- a Framework for Node Distribution Comparison in Real and Synthetic Graphs [72.51835626235368]
  2つのグラフを比較するとき、ノード構造的特徴の分布は、グローバルグラフ統計よりも有益である、と我々は主張する。 本稿では,各ノード表現セットのアライメントに基づいてグラフ間の類似性を評価するフレームワークGraphDCAを提案する。
  論文  参考訳（メタデータ） (2022-02-08T14:19:19Z)
• Inverse Graph Identification: Can We Identify Node Labels Given Graph Labels? [89.13567439679709]
  グラフ識別(GI)は、グラフ学習において長い間研究されており、特定の応用において不可欠である。 本稿では,逆グラフ識別(Inverse Graph Identification, IGI)と呼ばれる新しい問題を定義する。 本稿では,グラフアテンションネットワーク(GAT)を用いたノードレベルのメッセージパッシング処理を,GIのプロトコルの下でシンプルかつ効果的に行う方法を提案する。
  論文  参考訳（メタデータ） (2020-07-12T12:06:17Z)
• Multilevel Graph Matching Networks for Deep Graph Similarity Learning [79.3213351477689]
  グラフ構造オブジェクト間のグラフ類似性を計算するためのマルチレベルグラフマッチングネットワーク(MGMN)フレームワークを提案する。 標準ベンチマークデータセットの欠如を補うため、グラフグラフ分類とグラフグラフ回帰タスクの両方のためのデータセットセットを作成し、収集した。 総合的な実験により、MGMNはグラフグラフ分類とグラフグラフ回帰タスクの両方において、最先端のベースラインモデルより一貫して優れていることが示された。
  論文  参考訳（メタデータ） (2020-07-08T19:48:19Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)
• CoSimGNN: Towards Large-scale Graph Similarity Computation [5.17905821006887]
  グラフニューラルネットワーク(GNN)はこのタスクにデータ駆動型ソリューションを提供する。 既存のGNNベースの手法は、それぞれ2つのグラフを埋め込んだり、グラフ全体のクロスグラフインタラクションをデプロイしたりするが、まだ競合する結果が得られない。 このフレームワークは,まず適応的なプーリング操作で大きなグラフを埋め込んで粗くし,最後に類似点を求めるために粗いグラフにきめ細かな相互作用を展開させる。
  論文  参考訳（メタデータ） (2020-05-14T16:33:13Z)

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

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