論文の概要: Efficient Higher-order Subgraph Attribution via Message Passing

• arxiv url: http://arxiv.org/abs/2605.22385v1
• Date: Thu, 21 May 2026 12:16:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-22 20:14:18.562478
• Title: Efficient Higher-order Subgraph Attribution via Message Passing
• Title（参考訳）: メッセージパッシングによる高次部分グラフの効率的な属性
• Authors: Ping Xiong, Thomas Schnake, Grégoire Montavon, Klaus-Robert Müller, Shinichi Nakajima,
• Abstract要約: GNN-LRPのような高階の解釈スキームは、異なる機能がどのように相互作用するかを明らかにする強力なツールとして登場した。 線形時間でGNN-LRPでサブグラフを属性化できる新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 23.932427893302826
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Explaining graph neural networks (GNNs) has become more and more important recently. Higher-order interpretation schemes, such as GNN-LRP (layer-wise relevance propagation for GNN), emerged as powerful tools for unraveling how different features interact thereby contributing to explaining GNNs. GNN-LRP gives a relevance attribution of walks between nodes at each layer, and the subgraph attribution is expressed as a sum over exponentially many such walks. In this work, we demonstrate that such exponential complexity can be avoided. In particular, we propose novel algorithms that enable to attribute subgraphs with GNN-LRP in linear-time (w.r.t. the network depth). Our algorithms are derived via message passing techniques that make use of the distributive property, thereby directly computing quantities for higher-order explanations. We further adapt our efficient algorithms to compute a generalization of subgraph attributions that also takes into account the neighboring graph features. Experimental results show the significant acceleration of the proposed algorithms and demonstrate the high usefulness and scalability of our novel generalized subgraph attribution method.
• Abstract（参考訳）: 最近、グラフニューラルネットワーク(GNN)の説明がますます重要になっている。 GNN-LRP (layer-wise relevance propagation for GNN) のような高次解釈スキームは、異なる機能がどのように相互作用するかを明らかにする強力なツールとして登場し、GNNの説明に寄与した。 GNN-LRPは各層におけるノード間のウォークの関連付けを与え、サブグラフの属性は指数関数的に多くのウォークの和として表される。 本研究では,このような指数関数的複雑性を回避できることを実証する。 特に,線形時間(ネットワーク深度)でGNN-LRPのサブグラフを属性化できる新しいアルゴリズムを提案する。 提案アルゴリズムは,分散特性を利用したメッセージパッシング手法により導出され,高次説明のために直接計算量を算出する。 さらに、近隣のグラフの特徴を考慮に入れた部分グラフ属性の一般化を計算するために、効率的なアルゴリズムを適用する。 実験により,提案アルゴリズムの大幅な高速化と,新しい一般化された部分グラフ属性法の有用性と拡張性を示した。

関連論文リスト

• Iterative Graph Neural Network Enhancement via Frequent Subgraph Mining of Explanations [0.0]
  我々は、説明強化グラフ学習(EEGL)と呼ばれるノード分類のためのグラフニューラルネットワーク(GNN)のためのXAIベースのモデル改善アプローチを定式化する。 目的は、説明を用いてGNNの予測性能を改善することである。 EEGLは、学習された"バニラ"GNNから始まる反復的な自己改善アルゴリズムであり、頻繁にサブグラフマイニングを使用して説明サブグラフの関連パターンを見つける。
  論文  参考訳（メタデータ） (2024-03-12T17:41:27Z)
• MAG-GNN: Reinforcement Learning Boosted Graph Neural Network [68.60884768323739]
  特定の研究の行は、GNNの表現性を向上させるためにサブグラフ情報を使用するサブグラフGNNを提案し、大きな成功を収めた。 このような効果は、すべての可能な部分グラフを列挙することによって、GNNの効率を犠牲にする。 本稿では,強化学習(RL)により強化されたGNNである磁気グラフニューラルネットワーク(MAG-GNN)を提案する。
  論文  参考訳（メタデータ） (2023-10-29T20:32:21Z)
• Deep Graph Neural Networks via Posteriori-Sampling-based Node-Adaptive Residual Module [65.81781176362848]
  グラフニューラルネットワーク(GNN)は、近隣情報収集を通じてグラフ構造化データから学習することができる。 レイヤーの数が増えるにつれて、ノード表現は区別不能になり、オーバー・スムーシング(over-smoothing)と呼ばれる。 我々は,textbfPosterior-Sampling-based, Node-distinguish Residual Module (PSNR)を提案する。
  論文  参考訳（メタデータ） (2023-05-09T12:03:42Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Two-level Graph Neural Network [15.014364222532347]
  2レベルGNN(TL-GNN)と呼ばれる新しいGNNフレームワークを提案する。 これは、サブグラフレベル情報とノードレベル情報とをマージする。 実験により、TL-GNNは既存のGNNよりも優れ、最先端のパフォーマンスを達成することが示された。
  論文  参考訳（メタデータ） (2022-01-03T02:15:20Z)
• Learning Graph Neural Networks with Approximate Gradient Descent [24.49427608361397]
  ラベルがノードまたはグラフに添付されているかどうかに応じて、2種類のグラフニューラルネットワーク(GNN)が調査されます。 gnnトレーニングアルゴリズムの設計と解析のための包括的なフレームワークを開発した。 提案アルゴリズムは,GNNの根底にある真のパラメータに対する線形収束率を保証する。
  論文  参考訳（メタデータ） (2020-12-07T02:54:48Z)
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification [70.50751397870972]
  FastGATは、スペクトルスペーシフィケーションを用いて、注目に基づくGNNを軽量にし、入力グラフの最適プルーニングを生成する手法である。 我々は,ノード分類タスクのための大規模実世界のグラフデータセット上でFastGATを実験的に評価した。
  論文  参考訳（メタデータ） (2020-06-15T22:07:54Z)
• Higher-Order Explanations of Graph Neural Networks via Relevant Walks [3.1510406584101776]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データを予測するための一般的なアプローチである。 本稿では,GNNを高次展開を用いて自然に説明できることを示す。 本稿では,テキストデータの感情分析,量子化学における構造・不適切な関係,画像分類に関する実践的な知見を抽出する。
  論文  参考訳（メタデータ） (2020-06-05T17:59:14Z)
• Binarized Graph Neural Network [65.20589262811677]
  我々は二項化グラフニューラルネットワークを開発し、二項化ネットワークパラメータを用いてノードのバイナリ表現を学習する。 提案手法は既存のGNNベースの埋め込み手法にシームレスに統合できる。 実験により、提案された二項化グラフニューラルネットワーク、すなわちBGNは、時間と空間の両方の観点から、桁違いに効率的であることが示されている。
  論文  参考訳（メタデータ） (2020-04-19T09:43:14Z)

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

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