Distill n' Explain: explaining graph neural networks using simple surrogates
This addresses the need for efficient and faithful explanations in GNNs, which is crucial for domains like social networks or bioinformatics, though it is incremental as it builds on existing distillation and explanation techniques.
The paper tackles the problem of explaining node predictions in graph neural networks (GNNs) by proposing Distill n' Explain (DnX), which uses a simpler surrogate GNN learned via knowledge distillation to break the bond between GNN complexity and explanation cost, resulting in methods that outperform state-of-the-art explainers while being orders of magnitude faster.
Explaining node predictions in graph neural networks (GNNs) often boils down to finding graph substructures that preserve predictions. Finding these structures usually implies back-propagating through the GNN, bonding the complexity (e.g., number of layers) of the GNN to the cost of explaining it. This naturally begs the question: Can we break this bond by explaining a simpler surrogate GNN? To answer the question, we propose Distill n' Explain (DnX). First, DnX learns a surrogate GNN via knowledge distillation. Then, DnX extracts node or edge-level explanations by solving a simple convex program. We also propose FastDnX, a faster version of DnX that leverages the linear decomposition of our surrogate model. Experiments show that DnX and FastDnX often outperform state-of-the-art GNN explainers while being orders of magnitude faster. Additionally, we support our empirical findings with theoretical results linking the quality of the surrogate model (i.e., distillation error) to the faithfulness of explanations.