View-based Explanations for Graph Neural Networks

Abstract

Generating explanations for graph neural networks (GNNs) has been studied to understand their behavior in analytical tasks such as graph classification. Existing approaches aim to understand the overall results of GNNs rather than providing explanations for specific class labels of interest, and may return explanation structures that are hard to access, nor directly queryable.We propose GVEX, a novel paradigm that generates Graph Views for EXplanation. (1) We design a two-tier explanation structure called explanation views. An explanation view consists of a set of graph patterns and a set of induced explanation subgraphs. Given a database G of multiple graphs and a specific class label l assigned by a GNN-based classifier M, it concisely describes the fraction of G that best explains why l is assigned by M. (2) We propose quality measures and formulate an optimization problem to compute optimal explanation views for GNN explanation. We show that the problem is ${\Sigma }_P^2$-hard. (3) We present two algorithms. The first one follows an explain-and-summarize strategy that first generates high-quality explanation subgraphs which best explain GNNs in terms of feature influence maximization, and then performs a summarization step to generate patterns. We show that this strategy provides an approximation ratio of 1/2. Our second algorithm performs a single-pass to an input node stream in batches to incrementally maintain explanation views, having an anytime quality guarantee of 1/4 approximation. Using real-world benchmark data, we experimentally demonstrate the effectiveness, efficiency, and scalability of GVEX. Through case studies, we showcase the practical applications of GVEX.

arXiv commentThis paper has been accepted by SIGMOD 2024

References in corpus (22)

• Adam: A Method for Stochastic Optimization
• A Comprehensive Survey on Graph Neural Networks
• Modeling polypharmacy side effects with graph convolutional networks
• Representation Learning on Graphs with Jumping Knowledge Networks
• Hierarchical Graph Representation Learning with Differentiable Pooling
• GNNExplainer: Generating Explanations for Graph Neural Networks
• Predict then Propagate: Graph Neural Networks meet Personalized PageRank
• XGNN: Towards Model-Level Explanations of Graph Neural Networks
• Parameterized Explainer for Graph Neural Network
• OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs
• Graph Neural Networks in Recommender Systems: A Survey
• Explainability in Graph Neural Networks: A Taxonomic Survey
• Accelerating Large Scale Real-Time GNN Inference using Channel Pruning
• GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks
• Grain: Improving Data Efficiency of Graph Neural Networks via Diversified Influence Maximization
• Robust Counterfactual Explanations on Graph Neural Networks
• Accelerating Training and Inference of Graph Neural Networks with Fast Sampling and Pipelining
• Fairness in Streaming Submodular Maximization: Algorithms and Hardness
• A Large-Scale Database for Graph Representation Learning
• GStarX: Explaining Graph Neural Networks with Structure-Aware Cooperative Games
• Towards Prototype-Based Self-Explainable Graph Neural Network
• Efficient Graph Neural Network Inference at Large Scale

Cited by in corpus (2)

• Finding Counterfactual Evidences for Node Classification
• ML-Asset Management: Curation, Discovery, and Utilization