On Explainability of Graph Neural Networks via Subgraph Explorations

Abstract

We consider the problem of explaining the predictions of graph neural networks (GNNs), which otherwise are considered as black boxes. Existing methods invariably focus on explaining the importance of graph nodes or edges but ignore the substructures of graphs, which are more intuitive and human-intelligible. In this work, we propose a novel method, known as SubgraphX, to explain GNNs by identifying important subgraphs. Given a trained GNN model and an input graph, our SubgraphX explains its predictions by efficiently exploring different subgraphs with Monte Carlo tree search. To make the tree search more effective, we propose to use Shapley values as a measure of subgraph importance, which can also capture the interactions among different subgraphs. To expedite computations, we propose efficient approximation schemes to compute Shapley values for graph data. Our work represents the first attempt to explain GNNs via identifying subgraphs explicitly and directly. Experimental results show that our SubgraphX achieves significantly improved explanations, while keeping computations at a reasonable level.

arXiv commentAccepted by ICML 2021

References in corpus (10)

• Neural Message Passing for Quantum Chemistry
• Categorical Reparameterization with Gumbel-Softmax
• SmoothGrad: removing noise by adding noise
• Higher-Order Explanations of Graph Neural Networks via Relevant Walks
• Parameterized Explainer for Graph Neural Network
• Supervised Community Detection with Line Graph Neural Networks
• XFake: Explainable Fake News Detector with Visualizations
• Multi-Objective Molecule Generation using Interpretable Substructures
• DIG: A Turnkey Library for Diving into Graph Deep Learning Research
• Node2Seq: Towards Trainable Convolutions in Graph Neural Networks

Cited by in corpus (11)

• Graph-Based Deep Learning for Medical Diagnosis and Analysis: Past, Present and Future
• A Survey on Graph-Based Deep Learning for Computational Histopathology
• Advances of Machine Learning in Materials Science: Ideas and Techniques
• A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability
• Robust Counterfactual Explanations on Graph Neural Networks
• Position-Aware Subgraph Neural Networks with Data-Efficient Learning
• Generating Post-hoc Explanations for Skip-gram-based Node Embeddings by Identifying Important Nodes with Bridgeness
• Reconstruction for Powerful Graph Representations
• Towards Automated Evaluation of Explanations in Graph Neural Networks
• Ensembles of Random SHAPs
• Reimagining GNN Explanations with ideas from Tabular Data