論文の概要: xNeuSM: Explainable Neural Subgraph Matching with Graph Learnable Multi-hop Attention Networks

• arxiv url: http://arxiv.org/abs/2312.01612v1
• Date: Mon, 4 Dec 2023 04:03:30 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-05 16:22:20.479262
• Title: xNeuSM: Explainable Neural Subgraph Matching with Graph Learnable Multi-hop Attention Networks
• Title（参考訳）: xNeuSM: グラフ学習可能なマルチホップアテンションネットワークによる説明可能なニューラルネットワークサブグラフマッチング
• Authors: Duc Q. Nguyen, Thanh Toan Nguyen, Tho quan
• Abstract要約: サブグラフマッチングは、データベースシステム、生化学、認知科学における幅広い応用において難しい問題である。 従来のグラフマッチングアルゴリズムは正確な結果を提供するが、NP完全問題により大きなグラフインスタンスでは課題に直面している。 本稿では,グラフ学習可能なマルチホップ注意ネットワーク(GLeMA)について紹介する。
• 参考スコア（独自算出の注目度）: 2.084955943646144
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Subgraph matching is a challenging problem with a wide range of applications in database systems, biochemistry, and cognitive science. It involves determining whether a given query graph is present within a larger target graph. Traditional graph-matching algorithms provide precise results but face challenges in large graph instances due to the NP-complete problem, limiting their practical applicability. In contrast, recent neural network-based approximations offer more scalable solutions, but often lack interpretable node correspondences. To address these limitations, this article presents xNeuSM: Explainable Neural Subgraph Matching which introduces Graph Learnable Multi-hop Attention Networks (GLeMA) that adaptively learns the parameters governing the attention factor decay for each node across hops rather than relying on fixed hyperparameters. We provide a theoretical analysis establishing error bounds for GLeMA's approximation of multi-hop attention as a function of the number of hops. Additionally, we prove that learning distinct attention decay factors for each node leads to a correct approximation of multi-hop attention. Empirical evaluation on real-world datasets shows that xNeuSM achieves substantial improvements in prediction accuracy of up to 34% compared to approximate baselines and, notably, at least a seven-fold faster query time than exact algorithms. The source code of our implementation is available at https://github.com/martinakaduc/xNeuSM.
• Abstract（参考訳）: サブグラフマッチングは、データベースシステム、生化学、認知科学における幅広い応用において難しい問題である。 特定のクエリグラフがより大きなターゲットグラフ内に存在するかどうかを判断する。 従来のグラフマッチングアルゴリズムは正確な結果を提供するが、NP完全問題による大きなグラフインスタンスの課題に直面し、実用性を制限する。 対照的に、最近のニューラルネットワークベースの近似はよりスケーラブルなソリューションを提供するが、しばしば解釈可能なノード対応がない。 グラフ学習可能なマルチホップアテンションネットワーク(glema:graph learnable multi-hop attention network)を導入し、固定ハイパーパラメータに頼るのではなく、ホップの各ノードのアテンション係数の減衰を管理するパラメータを適応的に学習します。 ホップ数の関数として,マルチホップ注意のグロマ近似の誤差境界を定式化する理論的解析を提供する。 さらに,各ノードに対する異なる注意減衰因子の学習は,マルチホップ注意の正確な近似につながることを証明した。 実世界のデータセットにおける経験的評価により、xneusmは、近似ベースラインと比較して最大34%の予測精度が大幅に向上し、特に、正確なアルゴリズムよりも7倍速いクエリ時間が得られることが示されている。 実装のソースコードはhttps://github.com/martinakaduc/xneusmで閲覧できます。

関連論文リスト

• Heuristic Learning with Graph Neural Networks: A Unified Framework for Link Prediction [25.87108956561691]
  リンク予測はグラフ学習における基本的なタスクであり、本質的にグラフのトポロジーによって形作られる。 種々の重みを適応・一般化するための統一行列定式化を提案する。 また,この定式化を効率的に実装するためのHuristic Learning Graph Neural Network (HL-GNN)を提案する。
  論文  参考訳（メタデータ） (2024-06-12T08:05:45Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching [68.35685422301613]
  そこで我々はMatchExplainerと呼ばれる新しい非パラメトリックな部分グラフマッチングフレームワークを提案し、説明的部分グラフを探索する。 ターゲットグラフと他のインスタンスを結合し、ノードに対応する距離を最小化することで最も重要な結合部分構造を識別する。 合成および実世界のデータセットの実験は、最先端のパラメトリックベースラインをかなりのマージンで上回り、MatchExplainerの有効性を示す。
  論文  参考訳（メタデータ） (2023-01-07T05:14:45Z)
• Subgraph Matching via Query-Conditioned Subgraph Matching Neural Networks and Bi-Level Tree Search [33.9052190473029]
  サブグラフマッチングは、グラフデータベース検索、バイオメディカル分析、ソーシャルグループ検索などにおける中核的な操作である。 本稿では,クエリと対象グラフのマッチング情報を動的に計算する,新しいエンコーダ・デコーダニューラルネットワークアーキテクチャを提案する。 5つの大きな実世界のターゲットグラフの実験により、N-BLSはサブグラフマッチング性能を大幅に改善できることが示された。
  論文  参考訳（メタデータ） (2022-07-21T04:47:21Z)
• Discovering the Representation Bottleneck of Graph Neural Networks from Multi-order Interactions [51.597480162777074]
  グラフニューラルネットワーク(GNN)は、ノード機能を伝搬し、インタラクションを構築するためにメッセージパッシングパラダイムに依存している。 最近の研究は、異なるグラフ学習タスクはノード間の異なる範囲の相互作用を必要とすることを指摘している。 科学領域における2つの共通グラフ構築法、すなわち、emphK-nearest neighbor(KNN)グラフとemphfully-connected(FC)グラフについて検討する。
  論文  参考訳（メタデータ） (2022-05-15T11:38:14Z)
• Neural Subgraph Matching [57.05893848555512]
  NeuroMatchは、サブグラフマッチングに対する正確で効率的で堅牢な神経アプローチである。 NeuroMatchは、既存の幾何学的アプローチよりも100倍高速で、既存のサブグラフマッチング手法よりも18%精度が高い。
  論文  参考訳（メタデータ） (2020-07-06T22:06:38Z)
• Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
  GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。 高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。 このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
  論文  参考訳（メタデータ） (2020-07-03T09:30:07Z)
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
  現在のグラフニューラルネットワーク(GNN)は、オーバースムーシング(over-smoothing)と呼ばれる問題のため、自分自身を深くするのは難しいことが知られている。 マルチスケールGNNは、オーバースムーシング問題を緩和するための有望なアプローチである。 マルチスケールGNNを含むトランスダクティブ学習アルゴリズムの最適化と一般化を保証する。
  論文  参考訳（メタデータ） (2020-06-15T17:06:17Z)
• GLSearch: Maximum Common Subgraph Detection via Learning to Search [33.9052190473029]
  検索モデルに対するグラフニューラルネットワーク(GNN)に基づく学習手法であるGLSearchを提案する。 このモデルでは2つの入力グラフから1対のノードを選択して一度に拡張する。 我々のGLSearchは、グラフ上の制約で他の多くの問題を解決するために拡張できる可能性がある。
  論文  参考訳（メタデータ） (2020-02-08T10:03:40Z)

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

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