PaperlayerView exact revision on arXiv

Source-linked AI summary

Parameterized Explainer for Graph Neural Network

Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, Xiang Zhang

arXiv:2011.04573v1cs.LGcs.AI

TL;DR

GNN explanations are difficult to generalize because leading methods independently tailor local subgraph and feature explanations to single instances. PGExplainer parameterizes explanation generation with a deep neural network for collective explanations, and experiments report up to 24.7% AUC improvement over the leading method for graph classification.

  • Problem

    Existing GNN explanation methods focus on customized local explanations for single instances, limiting global understanding, generalization, and inductive use.

  • Method

    PGExplainer uses a parameterized deep neural network and shared generation process to collectively explain multiple GNN instances.

  • Results

    24.7% improvement in AUC over the SOTA method is reported for explaining graph classification, alongside consistent and accurate explanations and significant speed-up.

  • Takeaways & Limitations

    PGExplainer provides global-view explanations that can generalize to new instances without retraining and support inductive use across GNN models.

  • Takeaways & Limitations

    The method can increase the risk of attacks on GNNs and automation bias because extracted important subgraphs may expose behavior or encourage undue trust.

Abstract

from arXiv · show

Despite recent progress in Graph Neural Networks (GNNs), explaining predictions made by GNNs remains a challenging open problem. The leading method independently addresses the local explanations (i.e., important subgraph structure and node features) to interpret why a GNN model makes the prediction for a single instance, e.g. a node or a graph. As a result, the explanation generated is painstakingly customized for each instance. The unique explanation interpreting each instance independently is not sufficient to provide a global understanding of the learned GNN model, leading to a lack of generalizability and hindering it from being used in the inductive setting. Besides, as it is designed for explaining a single instance, it is challenging to explain a set of instances naturally (e.g., graphs of a given class). In this study, we address these key challenges and propose PGExplainer, a parameterized explainer for GNNs. PGExplainer adopts a deep neural network to parameterize the generation process of explanations, which enables PGExplainer a natural approach to explaining multiple instances collectively. Compared to the existing work, PGExplainer has better generalization ability and can be utilized in an inductive setting easily. Experiments on both synthetic and real-life datasets show highly competitive performance with up to 24.7\% relative improvement in AUC on explaining graph classification over the leading baseline.

1 Introduction

GNNs are effective on graph-structured data but difficult to interpret because their predictions combine node features and graph topology. PGExplainer addresses the limitations of instance-specific explanations by parameterizing explanation generation for collective, generalizable explanations, achieving up to 24.7% AUC improvement over the leading method.

  • GNNs use message passing to capture node features and graph topology for tasks including node classification, graph classification, and link prediction.
  • Explaining GNN predictions requires uncovering important subgraphs and features, but graph structure makes robust and efficient explanation difficult.
  • GNNExplainer produces customized explanations independently for individual nodes or graphs, limiting generalization and making inductive use difficult.
  • PGExplainer parameterizes explanation generation with a deep neural network whose shared parameters support collective, model-level explanations across instances.
  • 24.7% improvement in AUC over the SOTA method is reported for explaining graph classification, with consistent and accurate explanations and significant speed-up.

2 Related work

Related work covers GNN architectures, explanation methods, and graph generation. Existing explanation approaches generally focus on individual predictions, while PGExplainer uses probabilistic graph generation to explain GNNs.

  • Graph neural networks: GNNs propagate and aggregate neighbor information to learn node or graph representations for downstream prediction tasks.
  • Explaining GNNs: Interpretability methods for neural networks include whitebox and blackbox families, with forward and backward propagation used in whitebox mechanisms.
  • Explaining GNNs: GNNExplainer extracts subgraphs and important features by maximizing mutual information with a GNN prediction, but generates explanations independently for each instance.
  • Graph generation: Graph-generation methods model random graphs or graphs with properties such as distances, degree distributions, spectral properties, or training-graph characteristics.

3 Background

GNNs learn representations through repeated message passing along graph edges. Each layer computes edge messages, aggregates them at nodes, updates node representations, and uses final representations for downstream tasks.

  • GNNs propagate and aggregate information along input-graph edges to learn node representations.
  • For each edge, a GNN computes a message from the previous-layer representations of its incident nodes.
  • At the aggregation step, each node combines messages received from its neighboring nodes.
  • At the updating step, each node representation is updated using the aggregated message and the node’s own representation.
  • The final GNN-layer hidden representation serves as the node representation for node or graph classification and link prediction.

4 The PGExplainer

PGExplainer learns shared, parameterized edge explanations for GNN predictions, enabling collective and inductive explanations while optimizing a mutual-information objective through differentiable graph sampling.

  • Method scope: PGExplainer focuses on explaining graph structures and is designed to interpret different kinds of GNNs.Unlike GNNExplainer, it does not explain node features; the method targets structural explanations.
  • Learning objective: The learning objective identifies an explanatory subgraph Gs by maximizing mutual information between the GNN prediction and the underlying graph structure.Gs is treated as the prediction-relevant portion of the original graph, while ΔG contains remaining task-irrelevant edges.
  • Learning objective: Because directly optimizing among 2^M candidate subgraphs is intractable, PGExplainer assumes conditionally independent edge selections using a Gilbert random graph relaxation.Each edge is modeled as a binary selection variable, with its own probability of appearing in the explanatory graph.
  • Reparameterization: Continuous edge weights and the binary concrete reparameterization trick enable gradient-based optimization of sampled explanatory graphs.The temperature controls the approximation; as τ approaches zero, the relaxed graph approaches the Bernoulli graph, while positive temperature smooths the objective.
  • Global explanation network: A parameterized explanation network computes edge-distribution variables from the original graph and node representations, sharing parameters across the instance population.For graph classification, each graph is an instance; node classification uses task-specific explanation generation because node explanations may have diverse structures.
  • Computational complexity: PGExplainer explains a new graph with |E| edges in O(|E|) time, whereas GNNExplainer retrains per instance in O(T|E|).The shared explanation network also supports inductive explanations without retraining the explainer.

5 Experimental study

Experiments evaluate PGExplainer on synthetic and real-life datasets using qualitative and quantitative comparisons with established baselines. PGExplainer achieves strong explanation accuracy and substantially faster inference for new instances.

  • Datasets: The study evaluates node and graph classification explanations on four synthetic node datasets, one synthetic graph dataset, and MUTAG.The datasets include BA-Shapes, BA-Community, Tree-Cycles, Tree-Grids, BA-2motifs, and MUTAG.
  • Baselines and setup: The comparisons include GNNExplainer, GRAD, ATT, and Gradient, with post-hoc methods applied after training GNN models.GNNExplainer provides explanations independently for each instance, while ATT uses jointly optimized self-attention layers.
  • Qualitative evaluation: PGExplainer correctly identifies complete ground-truth motifs across datasets, whereas GNNExplainer sometimes omits important edges or highlights nondiscriminative structures.In MUTAG, PGExplainer identifies both NO2 groups, while GNNExplainer includes carbon rings and only part of an NO2 group.
  • Quantitative evaluation: 13.0% accuracy gains in node classification and 24.7% in graph classification are reported for PGExplainer over the compared methods.AUC is computed by treating motif edges as positive examples and non-motif edges as negative examples.
  • Efficiency evaluation: 108 times faster computation is achieved by PGExplainer than GNNExplainer when explaining new instances.The explanation network is shared across instances, and the trained method can explain new instances in the inductive setting.
  • Additional experiments: Further experiments examine inductive performance and the effects of regularization terms in the Appendix.

6 Conclusion

PGExplainer provides a global understanding of GNN models by collectively explaining multiple instances. It learns important underlying subgraphs and supports efficient explanation in inductive settings.

  • PGExplainer collectively explains multiple instances to provide a global understanding of arbitrary GNN models and machine learning tasks.
  • PGExplainer leverages GNN representations to learn subgraphs important to GNN predictions.
  • Its inductive explanation capacity improves efficiency and makes the method more practical for real-life applications.

Broader impact

The method is positioned as a way to improve the transparency of GNN applications while also introducing security and human-factors risks. These impacts are especially relevant to decision-critical applications such as drug discovery and diagnosis.

  • PGExplainer can provide local-fidelity explanations while improving global understanding of GNN models.
  • In decision-critical applications such as drug discovery and diagnosis, explanations may increase transparency and help alleviate safety and fairness risks.
  • Because PGExplainer extracts subgraphs important to GNN behavior, disturbing those parts can significantly change predictions, creating attack risk.
  • Greater interpretability may also cause automation bias, including undue trust in GNN models.

Supplementary Material: Parameterized Explainer for

The supplementary algorithms train a shared explanation network for node and graph classification. They compute GNN representations, generate edge-distribution parameters, sample subgraphs, evaluate predictions, and update explanation-network parameters.

  • Node classification: For each node and training epoch, PGExplainer computes edge-distribution parameters, samples K graphs, obtains updated predictions, and updates the explanation network using the loss.
  • Node classification: For node classification, the algorithm extracts each target node’s L-hop local computation graph before computing its GNN representation and prediction.The local computation graph is determined by the number of GNN layers.
  • Graph classification: During graph-classification training, PGExplainer computes edge-distribution parameters, samples K subgraphs, evaluates predictions, and updates parameters by backpropagation.
  • Graph classification: For graph classification, the algorithm first computes node embeddings and graph labels for each input graph using the trained GNN.Computation graphs are unnecessary because each graph is treated as an instance.

B. Hardware and implementations in experiments

The experiments use a Linux machine with an Nvidia GeForce RTX 2070 SUPER GPU and TensorFlow 2.0.0. Each dataset uses a shared trained GNN for posthoc comparison, with PGExplainer configured through a shared explanation-network architecture and fixed training settings.

  • Experiments run on Linux with an Nvidia GeForce RTX 2070 SUPER GPU with 8GB memory, CUDA 10.2, and driver version 440.64.00.
  • PGExplainer is implemented with TensorFlow 2.0.0, while each dataset’s trained GNN is shared by ATT, GNNExplainer, and PGExplainer.
  • Table 3 reports the accuracy performance of the GNN models.
  • The explanation network uses FC(#input, 64, ReLU)-FC(20, 1, Linear), with 60 inputs for node classification and 40 for graph classification.
  • PGExplainer training uses Adam with initial learning rate 3.0 × 10^-3, size regularization 0.05, entropy regularization 1.0, and 30 epochs.

C. Additional experiments

Additional experiments are conducted to obtain deeper insights into PGExplainer.

  • The paper conducts extensive experiments to gain deeper insights into PGExplainer.

C.1 Inductive performance

PGExplainer’s explanation network is shared across the population, allowing inference without retraining and supporting inductive explanations. As more instances are trained, testing AUC increases while standard deviation decreases, and shared motifs are detected more robustly.

  • The shared explanation network allows PGExplainer to infer explanations without retraining and gives it better generalization power than GNNExplainer.
  • PGExplainer is more efficient in the inductive setting because its explanation network is shared across the population.
  • Testing AUC increases as more instances are trained, verifying PGExplainer’s effectiveness in the inductive setting.
  • More training instances lead to smaller standard deviation, and PGExplainer detects shared motifs with higher robustness.
  • PGExplainer achieves relatively good performance with a small number of trained instances, supporting its use on large datasets.

C.2 Effects of regularization terms

Additional experiments examine size, entropy, and connectivity regularization. PGExplainer remains competitive without size or entropy regularization on most synthetic datasets, while connectivity regularization encourages connected explanatory subgraphs.

  • Effects of size and entropy constraint: Visualization on synthetic datasets shows that PGExplainer tends to extract small and compact explanatory graphs.
  • Effects of size and entropy constraint: PGExplainer achieves competitive performance without size or entropy regularization on all synthetic datasets except BA-Community.
  • Effects of size and entropy constraint: On BA-Community, the entropy constraint plays an important role.
  • Effects of connectivity constraint: The connectivity study uses a noisy BA-Shapes dataset with 0.2N noisy edges and varies λc from 0 to 10 for single-instance explanations.
  • Effects of connectivity constraint: Without an explicit connectivity constraint, PGExplainer may select several disconnected edges; with the constraint, it tends to provide a connected subgraph.
Loading 2011.04573v1…