GNN-EGG: Graph neural network explanations via graph generation

Graph Neural Networks (GNNs) provide a means for modeling inherently graphical data, such as transportation, social, and molecular networks, but also for enhancing and reducing unstructured data, including text and images. A potential shortcoming is that their predictions are opaque-a black box-hindering broader adoption and refinement. In this paper, we propose a novel architecture-agnostic algorithm, GNN-EGG (Graph Neural Network Explanations via Graph Generation), for GNN classifiers. As a model-level post-hoc explanation method, GNN-EGG can learn the data generating distribution for each class of graphs. The primary contribution of this work is the use of a differentiable approximation to Graph Edit Distance (GED) in the loss function. This term enables us to ensure consistency in both the graph space and the embedding space for our representative examples. It also reduces the random baseline issue where completely random graphs can still yield similar embeddings and strong predictions as reported in previous work. We benchmark our algorithm against the current state-of-the-art models using the mutagenic molecules dataset (MUTAG) and apply our method to a large-scale GNN for malignancy detection in digital pathology tasks. The official implementation of this method can be found at this GitHub repository.