論文の概要: 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（参考訳）: メッセージパッシングによる高次部分グラフの効率的な属性
- 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のサブグラフを属性化できる新しいアルゴリズムを提案する。
提案アルゴリズムは,分散特性を利用したメッセージパッシング手法により導出され,高次説明のために直接計算量を算出する。
さらに、近隣のグラフの特徴を考慮に入れた部分グラフ属性の一般化を計算するために、効率的なアルゴリズムを適用する。
実験により,提案アルゴリズムの大幅な高速化と,新しい一般化された部分グラフ属性法の有用性と拡張性を示した。
関連論文リスト
- Relevant Walk Search for Explaining Graph Neural Networks [23.612178520096162]
グラフネットワーク(GNN)は、機械学習分析において重要な機械学習ツールとなっている。
GNN(GNN-LRP)の階層的関連性伝搬は、ネットワーク内の重要な情報フローを明らかにするために、エンフウォークの関連性を評価する。
我々は,GNN-LRPの大規模問題への適用性を大幅に低減する,最高時間$K$関連ウォークを求めるエムタイムアルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-05-22T14:21:37Z) - 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) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - 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) - Relation Embedding based Graph Neural Networks for Handling
Heterogeneous Graph [58.99478502486377]
我々は、同種GNNが不均一グラフを扱うのに十分な能力を持つように、シンプルで効率的なフレームワークを提案する。
具体的には、エッジ型関係と自己ループ接続の重要性を埋め込むために、関係1つのパラメータのみを使用する関係埋め込みベースのグラフニューラルネットワーク(RE-GNN)を提案する。
論文 参考訳（メタデータ） (2022-09-23T05:24:18Z) - 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) - Counting Substructures with Higher-Order Graph Neural Networks:
Possibility and Impossibility Results [58.277290855841976]
グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。
新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。
いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
論文 参考訳（メタデータ） (2020-12-06T03:42:54Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。