EiG-Search: Generating Edge-Induced Subgraphs for GNN Explanation in Linear Time.

Area of Science:

• Artificial Intelligence
• Machine Learning
• Graph Neural Networks

Background:

• Explaining Graph Neural Network (GNN) predictions is vital for safety and trust.
• Subgraph-level explanations offer intuitive insights but often lack efficiency.
• Current methods struggle to balance intuitiveness, efficiency, and transparency.

Purpose of the Study:

• To develop an efficient and comprehensive subgraph-level explanation method for GNNs.
• To address the limitations of node-induced subgraphs in GNN explanations.
• To introduce a training-free approach for GNN interpretability.

Main Methods:

• Introduced EiG-Search, a novel training-free GNN explanation approach.
• Utilized edge-induced subgraphs for more comprehensive explanations.
• Employed a linear-time search with gradient-based edge importance ranking.

Main Results:

• EiG-Search demonstrated superior performance and efficiency over leading baselines.
• Extensive experiments on seven datasets validated the method's effectiveness.
• The approach provides both quantitative and qualitative improvements in GNN explanations.

Conclusions:

• Edge-induced subgraph explanations are more comprehensive than node-induced ones.
• Determining instance-specific subgraph sizes enhances explanation quality.
• EiG-Search offers a promising solution for efficient and transparent GNN interpretability.