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^2_P$-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.

GVEX 提出了一种新颖的图解释范式，设计了一个两层的解释结构，包括图模式和感知解释子图，利用高质量的解释子图来对图神经网络进行解释，并通过两个算法实现了高效和可扩展的解释生成。