論文の概要: Graph Similarity Computation via Interpretable Neural Node Alignment
- arxiv url: http://arxiv.org/abs/2412.12185v1
- Date: Fri, 13 Dec 2024 10:23:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-18 14:01:03.854417
- Title: Graph Similarity Computation via Interpretable Neural Node Alignment
- Title(参考訳): 解釈可能なニューラルノードアライメントによるグラフ類似性計算
- Authors: Jingjing Wang, Hongjie Zhu, Haoran Xie, Fu Lee Wang, Xiaoliang Xu, Yuxiang Wang,
- Abstract要約: GED(Graph Edit Distance)とMCS(Maximum Common Subgraphs)は、グラフの類似性を評価するために一般的に使用されるメトリクスである。
ディープラーニングモデルはよく知られたブラックボックス'であるため、典型的な1対1のノード/サブグラフアライメントプロセスは見ることができない。
我々は,ノードアライメント基底真理情報に頼ることなく,新しい解釈可能なニューラルノードアライメントモデルを提案する。
- 参考スコア(独自算出の注目度): 19.34487413883093
- License:
- Abstract: \Graph similarity computation is an essential task in many real-world graph-related applications such as retrieving the similar drugs given a query chemical compound or finding the user's potential friends from the social network database. Graph Edit Distance (GED) and Maximum Common Subgraphs (MCS) are the two commonly used domain-agnostic metrics to evaluate graph similarity in practice. Unfortunately, computing the exact GED is known to be a NP-hard problem. To solve this limitation, neural network based models have been proposed to approximate the calculations of GED/MCS. However, deep learning models are well-known ``black boxes'', thus the typically characteristic one-to-one node/subgraph alignment process in the classical computations of GED and MCS cannot be seen. Existing methods have paid attention to approximating the node/subgraph alignment (soft alignment), but the one-to-one node alignment (hard alignment) has not yet been solved. To fill this gap, in this paper we propose a novel interpretable neural node alignment model without relying on node alignment ground truth information. Firstly, the quadratic assignment problem in classical GED computation is relaxed to a linear alignment via embedding the features in the node embedding space. Secondly, a differentiable Gumbel-Sinkhorn module is proposed to unsupervised generate the optimal one-to-one node alignment matrix. Experimental results in real-world graph datasets demonstrate that our method outperforms the state-of-the-art methods in graph similarity computation and graph retrieval tasks, achieving up to 16\% reduction in the Mean Squared Error and up to 12\% improvement in the retrieval evaluation metrics, respectively.
- Abstract(参考訳): グラフ類似性計算は、クエリ化学物質を投与した類似薬物の検索や、ソーシャルネットワークデータベースからユーザーの潜在的友人を見つけるなど、多くの実世界のグラフ関連アプリケーションにおいて必須のタスクである。
グラフ編集距離(Graph Edit Distance, GED)と最大共通部分グラフ(Maximum Common Subgraphs, MCS)は、グラフの類似性を評価するために一般的に使用される2つのドメインに依存しないメトリクスである。
残念ながら、正確なGEDの計算はNPハード問題であることが知られている。
この制限を解決するために、GED/MCSの計算を近似するためにニューラルネットワークに基づくモデルが提案されている。
しかし、ディープラーニングモデルは 'black box'' としてよく知られており、GED と MCS の古典計算では典型的な1対1のノード/サブグラフアライメントプロセスは見られない。
既存の手法はノード/サブグラフのアライメント(ソフトアライメント)の近似に注意を払っているが、1対1のノードアライメント(ハードアライメント)はまだ解決されていない。
このギャップを埋めるために,本研究では,ノードアライメント基底真理情報に頼ることなく,新しい解釈可能なニューラルノードアライメントモデルを提案する。
まず、古典的GED計算における二次代入問題は、ノード埋め込み空間に特徴を埋め込むことによって線形アライメントに緩和される。
第二に、最適1対1ノードアライメント行列を教師なしで生成するために、Gumbel-Sinkhornモジュールが提案されている。
実世界のグラフデータセットにおける実験結果から,本手法はグラフ類似性計算やグラフ検索タスクにおける最先端手法よりも優れており,平均二乗誤差の最大16倍,評価指標の最大12倍の改善が達成されている。
関連論文リスト
- You do not have to train Graph Neural Networks at all on text-attributed graphs [25.044734252779975]
我々は、同じクラスからのテキストエンコーディングがしばしば線形部分空間に集約されるという観察に乗じて、線形GNNモデルであるTrainlessGNNを紹介した。
実験の結果、私たちのトレインレスモデルは、従来の訓練済みのモデルにマッチするか、超えられることがわかった。
論文 参考訳(メタデータ) (2024-04-17T02:52:11Z) - Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。
提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
論文 参考訳(メタデータ) (2024-01-12T17:57:07Z) - MATA*: Combining Learnable Node Matching with A* Algorithm for
Approximate Graph Edit Distance Computation [12.437507185260577]
正確なグラフ編集距離(GED)計算はNP完全であることが知られている。
グラフニューラルネットワーク(GNN)とA*アルゴリズムに基づく近似GED計算のためのデータ駆動型ハイブリッドアプローチMATA*を提案する。
論文 参考訳(メタデータ) (2023-11-04T09:33:08Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳(メタデータ) (2023-06-14T09:21:15Z) - Graph Mixup with Soft Alignments [49.61520432554505]
本研究では,画像上での使用に成功しているミキサアップによるグラフデータの増大について検討する。
ソフトアライメントによるグラフ分類のための簡易かつ効果的な混合手法であるS-Mixupを提案する。
論文 参考訳(メタデータ) (2023-06-11T22:04:28Z) - Seq-HGNN: Learning Sequential Node Representation on Heterogeneous Graph [57.2953563124339]
本稿では,シーケンシャルノード表現,すなわちSeq-HGNNを用いた新しい異種グラフニューラルネットワークを提案する。
Heterogeneous Graph Benchmark (HGB) と Open Graph Benchmark (OGB) の4つの広く使われているデータセットについて広範な実験を行った。
論文 参考訳(メタデータ) (2023-05-18T07:27:18Z) - Graph Neural Networks with Feature and Structure Aware Random Walk [7.143879014059894]
典型的な好適なグラフでは、エッジを指向する可能性があり、エッジをそのまま扱うか、あるいは単純に非指向にするかは、GNNモデルの性能に大きな影響を与える。
そこで我々は,グラフの方向性を適応的に学習するモデルを開発し,ノード間の長距離相関を生かした。
論文 参考訳(メタデータ) (2021-11-19T08:54:21Z) - COLOGNE: Coordinated Local Graph Neighborhood Sampling [1.6498361958317633]
グラフノードのような個別の未順序オブジェクトを実数値ベクトルで置き換えることは、グラフデータから学ぶための多くのアプローチの中心である。
ノードベクトル表現の座標がグラフノードであるような離散ノード埋め込みを学習する問題に対処する。
これにより、ノードにもともと存在するすべての属性が保存されているため、グラフの解釈可能な機械学習アルゴリズムを設計する扉が開く。
論文 参考訳(メタデータ) (2021-02-09T11:39:06Z) - Line Graph Neural Networks for Link Prediction [71.00689542259052]
実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。
このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。
本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。
特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
論文 参考訳(メタデータ) (2020-10-20T05:54:31Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。