On Explainability of Graph Neural Networks via Subgraph Explorations

By Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, Shuiwang Ji. International Conference on Machine Learning, 2021

537 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/123139463809b5acf98b95d4c8e958be334a32b5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Xiangnan He
2. Xiang Wang
3. Tat-seng Chua
4. Klaus‐Robert Müller 
5. Dawei Yin
6. Fei Sun
7. Bin Cui
8. Shiwen Wu

Citations in the corpus

• Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanism (2022, methodology): “, 2020a) or Monte Carlo tree search (Yuan et al., 2021).”
• Graph Neural Networks in Recommender Systems: A Survey (2020, background): “Themethods can be divided into two categories: the instance-levelmethods provide example-specific explanations by identifying important input features for its prediction [3, 123, 194]; the model-level methods provide high-level interpretations and a generic understanding of how deep graph models wor”
• GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks (2020, methodology): “For example, [9] was proposed to utilize mutual information to find a subgraph with associated features for interpreting GNN models; PGExplainer [16] learns a parameterized model to predict whether an edge is important; SubgraphX [17] explains GNNs by exploring and identifying important subgraphs; G”
• Discovering Invariant Rationales for Graph Neural Networks (2022, methodology): “Two research lines of rationalization have recently emerged in GNNs. Post-hoc explainability (Ying et al., 2019; Luo et al., 2020; Yuan et al., 2021; Wang et al., 2021c) attributes a model’s prediction to the input graph with a separate explanation method, while intrinsic interpretability…”
• Higher-Order Explanations of Graph Neural Networks via Relevant Walks (2020, methodology): “[32] proposes a Monte-Carlo tree search to find relevant sub-”
• Explainability in Graph Neural Networks: A Taxonomic Survey (2020, methodology): “PGExplainer [47], and SubgraphX [48], etc.”