A True-to-the-Model Benchmark for Edge-Level Attributions of GNN Explainers

Abstract

Edge-level explainers for Graph Neural Networks (GNNs) aim to identify the most crucial edges that influence the model’s predictions in a node classification task. Benchmarking these explainers is particularly challenging due to the extensive search space of potential explanations and the absence of reliable ground truths for edge importance. Moreover, the evaluation methods which are prominent in the literature rely on assumptions about which subgraphs in the input data influence the classification of a node, yet they provide no guarantee that the model has effectively learned the intended behavior. In this paper, we address these limitations by introducing a white-box GNN model together with a theoretical analysis to identify which edges are truly important, i.e., when removed, they can alter the classification. We demonstrate the effectiveness of this framework on both synthetic and real-world node classification tasks, using metrics that account for the inherent imbalance between the few relevant edges and the many irrelevant ones. Our evaluation reveals two recurring issues in current explainability methods: the frequent misidentification of unimportant edges as important ones, and numerical instability in some attribution techniques. To address these issues, we propose two corrective strategies that significantly enhance the reliability of edge-level attributions: a post-processing method to refine edge rankings and a rescaling of model weights to stabilize numerical outputs. Our work provides valuable insights into the strengths and weaknesses of existing GNN explainers and presents practical solutions to advance the fine-grained explainability of graph-based models.