Chiseling the Graph: An Edge-Sculpting Method for Explaining Graph Neural Networks

Abstract Graph Neural Networks (GNNs) leverage the structural properties of the graph to inform the architecture of the neural network, thus achieving improved accuracy in graph learning tasks. However, like many neural network models, GNNs face a significant challenge with interpretability. To mitigate this issue, recent works have developed post-hoc instance-level explanation methods that focus on identifying minimal and sufficient subgraphs which strongly influence GNN predictions. Approaches that build on the graph information bottleneck principle (GIB) to quantify minimality and sufficiency have received particular attention, and have been used in several state-of-the-art explanation mechanisms. This work identifies several fundamental issues in such quantifications, particularly a signaling issue in the sufficiency, and a redundancy issue in the minimality quantifications. These may lead to explanations that do not accurately reflect the rationale behind GNN decisions. To overcome these challenges, we propose a new objective function and explainer architecture, dubbed the SculptEdgeX. The SculptEdgeX framework assesses the sufficiency of an input subgraph by generating an in-distribution supergraph and evaluating its prediction accuracy when processed by the GNN. This involves an initial densification process that adds edges to the input graph, followed by a selective edge removal step — called edge sculpting — to produce an in-distribution supergraph. To ensure the in-distribution property, we pre-train a calibrator network that parametrizes the underlying distribution of a given graph, hence enabling us to compare the distribution parameters with those of the original input distribution. We validate our method through extensive experiments on both synthetic and real-world datasets, demonstrating the effectiveness of SculptEdgeX in producing informative explanations.