論文の概要: EiG-Search: Generating Edge-Induced Subgraphs for GNN Explanation in Linear Time
- arxiv url: http://arxiv.org/abs/2405.01762v2
- Date: Thu, 16 May 2024 14:55:47 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-17 18:15:48.779446
- Title: EiG-Search: Generating Edge-Induced Subgraphs for GNN Explanation in Linear Time
- Title（参考訳）: EiG-Search: 線形時間でのGNN説明のためのエッジ誘発サブグラフの生成
- Authors: Shengyao Lu, Bang Liu, Keith G. Mills, Jiao He, Di Niu,
- Abstract要約: グラフニューラルネットワーク(GNN)の複雑な探索プロセスによる説明において,既存の部分グラフレベルの説明器の多くは,効率上の課題に直面している。
本稿では,エッジによる部分グラフ説明の誘導が,他の部分グラフ推論手法よりも包括的であることを明らかにする。
我々は、エッジ誘導サブグラフに対して効率的な線形時間探索アルゴリズムを用い、エッジを勾配に基づく重要度でランク付けする。
- 参考スコア（独自算出の注目度）: 30.44473492282072
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Understanding and explaining the predictions of Graph Neural Networks (GNNs), is crucial for enhancing their safety and trustworthiness. Subgraph-level explanations are gaining attention for their intuitive appeal. However, most existing subgraph-level explainers face efficiency challenges in explaining GNNs due to complex search processes. The key challenge is to find a balance between intuitiveness and efficiency while ensuring transparency. Additionally, these explainers usually induce subgraphs by nodes, which may introduce less-intuitive disconnected nodes in the subgraph-level explanations or omit many important subgraph structures. In this paper, we reveal that inducing subgraph explanations by edges is more comprehensive than other subgraph inducing techniques. We also emphasize the need of determining the subgraph explanation size for each data instance, as different data instances may involve different important substructures. Building upon these considerations, we introduce a training-free approach, named EiG-Search. We employ an efficient linear-time search algorithm over the edge-induced subgraphs, where the edges are ranked by an enhanced gradient-based importance. We conduct extensive experiments on a total of seven datasets, demonstrating its superior performance and efficiency both quantitatively and qualitatively over the leading baselines.
- Abstract（参考訳）: グラフニューラルネットワーク(GNN)の予測を理解し,説明することは,安全性と信頼性を高める上で重要である。
字幕レベルの説明は直感的なアピールのために注目を集めている。
しかし、既存の部分グラフレベルの説明者は、複雑な探索プロセスのため、GNNの説明において効率上の課題に直面している。
重要な課題は、透明性を確保しながら、直感性と効率性のバランスを見つけることです。
さらに、これらの説明者は、通常ノードによってサブグラフを誘導し、サブグラフレベルの説明に直観的でない非連結ノードを導入するか、多くの重要なサブグラフ構造を省略する。
本稿では,エッジによる部分グラフ説明の誘導が,他の部分グラフ推論手法よりも包括的であることを明らかにする。
また、異なるデータインスタンスが異なる重要なサブ構造を含む可能性があるため、各データインスタンスのサブグラフ説明サイズを決定する必要があることも強調します。
これらの考察に基づいて,EeG-Searchというトレーニング不要のアプローチを導入する。
我々は、エッジ誘導サブグラフに対して効率的な線形時間探索アルゴリズムを用い、エッジを勾配に基づく重要度でランク付けする。
合計7つのデータセットに対して広範な実験を行い、その優れた性能と、主要なベースラインに対して定量的かつ定性的に効率を示す。
関連論文リスト
- NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - Improving Expressivity of GNNs with Subgraph-specific Factor Embedded
Normalization [30.86182962089487]
グラフニューラルネットワーク(GNN)は、グラフ構造化データを扱うための学習アーキテクチャの強力なカテゴリとして登場した。
我々は SUbgraph-sPEcific FactoR Embedded Normalization (SuperNorm) と呼ばれる専用プラグアンドプレイ正規化方式を提案する。
論文 参考訳（メタデータ） (2023-05-31T14:37:31Z) - DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
我々は,GNN予測に対する忠実な説明を提供するためにDGREEを提案する。
GNNの情報生成と集約機構を分解することにより、DECREEは入力グラフの特定のコンポーネントのコントリビューションを最終的な予測に追跡することができる。
また,従来の手法で見過ごされるグラフノード間の複雑な相互作用を明らかにするために,サブグラフレベルの解釈アルゴリズムを設計する。
論文 参考訳（メタデータ） (2023-05-22T10:29:52Z) - Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph
Matching [68.35685422301613]
そこで我々はMatchExplainerと呼ばれる新しい非パラメトリックな部分グラフマッチングフレームワークを提案し、説明的部分グラフを探索する。
ターゲットグラフと他のインスタンスを結合し、ノードに対応する距離を最小化することで最も重要な結合部分構造を識別する。
合成および実世界のデータセットの実験は、最先端のパラメトリックベースラインをかなりのマージンで上回り、MatchExplainerの有効性を示す。
論文 参考訳（メタデータ） (2023-01-07T05:14:45Z) - Faithful Explanations for Deep Graph Models [44.3056871040946]
本稿では,グラフニューラルネットワーク(GNN)の忠実な説明について述べる。
これは、特徴属性やサブグラフ説明を含む既存の説明方法に適用される。
第3に,元のGNNへの忠実度を確実に最大化する新しい説明法である,畳み込みコア(KEC)を用いたEmphk-hop Explanationを導入する。
論文 参考訳（メタデータ） (2022-05-24T07:18:56Z) - MotifExplainer: a Motif-based Graph Neural Network Explainer [19.64574177805823]
本稿では,グラフにおける重要なモチーフ,繰り返し,統計的に重要なパターンを同定し,グラフニューラルネットワーク(GNN)を説明する新しい手法を提案する。
提案手法は,ノード,エッジ,正規部分グラフに基づく手法よりも,人間に理解可能な説明を提供する。
論文 参考訳（メタデータ） (2022-02-01T16:11:21Z) - On Explainability of Graph Neural Networks via Subgraph Explorations [48.56936527708657]
本稿では,グラフニューラルネットワーク(GNN)を説明するための新しい手法,SubgraphXを提案する。
我々の研究は,GNNのサブグラフを明示的に識別する最初の試みである。
論文 参考訳（メタデータ） (2021-02-09T22:12:26Z) - Learning the Implicit Semantic Representation on Graph-Structured Data [57.670106959061634]
グラフ畳み込みネットワークにおける既存の表現学習手法は主に、各ノードの近傍を知覚全体として記述することで設計される。
本稿では,グラフの潜在意味パスを学習することで暗黙的な意味を探索する意味グラフ畳み込みネットワーク(sgcn)を提案する。
論文 参考訳（メタデータ） (2021-01-16T16:18:43Z) - Parameterized Explainer for Graph Neural Network [49.79917262156429]
グラフニューラルネットワーク(GNN)のためのパラメータ化説明器PGExplainerを提案する。
既存の研究と比較すると、PGExplainerはより優れた一般化能力を持ち、インダクティブな設定で容易に利用することができる。
合成データセットと実生活データセットの両方の実験では、グラフ分類の説明に関するAUCの相対的な改善が24.7%まで高い競争性能を示した。
論文 参考訳（メタデータ） (2020-11-09T17:15:03Z) - Subgraph Neural Networks [14.222887950206662]
本稿では,不整合部分グラフ表現を学習するためのサブグラフニューラルネットワークSubGNNを紹介する。
SubGNNは、挑戦的なバイオメディカルデータセットで非常によく機能する。
論文 参考訳（メタデータ） (2020-06-18T13:54:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。