Explaining GNN Explanations with Edge Gradients DOI: 10.1145/3711896.3736947 Conference: Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2; August 3–7, 2025; Toronto, ON, Canada. Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mini
Jesse He, Akbar Rafiey, Gal Mishne, Yusu Wang · 2025
Read Explaining GNN Explanations with Edge Gradients DOI: 10.1145/3711896.3736947 Conference: Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2; August 3–7, 2025; Toronto, ON, Canada. Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mini by Jesse He, Akbar Rafiey, Gal Mishne, Yusu Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-01048.txt.
Introduction
Jesse He, Akbar Rafiey, Gal Mishne, and Yusu Wang examine how explanations of graph neural networks are themselves explained in a 2025 study. Graph networks predict from connected data, and many tools claim to show which parts of a graph drove a prediction. Comparisons of those tools disagree, and many explainers struggle on harder architectures and tasks, leaving the field unsettled.
The authors analyze explanations in two settings: subgraphs of the input offered as reasons, and layer-by-layer accounts inside the network. Edge gradient information anchors their closer look. Careful theory about explainers is needed before their outputs can be trusted in science or medicine.
Catalog record
| CREATOR | Jesse He, Akbar Rafiey, Gal Mishne, Yusu Wang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-01048
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Explaining GNN Explanations with Edge Gradients DOI: 10.1145/3711896.3736947 Conference: Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2; August 3–7, 2025; Toronto, ON, Canada. Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD ’25), August 3–7, 2025, Toronto, ON, Canada ISBN: 979-8-4007-1454-2/25/08 CCS: Computing methodologies Neural networks CCS: Computer systems organization Neural networks CCS: Mathematics of computing Computing most probable explanation Jesse He, Akbar Rafiey, Gal Mishne, Yusu Wang Abstract . In recent years, the remarkable success of graph neural networks (GNNs) on graph-structured data has prompted a surge of methods for explaining GNN predictions. However, the state-of-the-art for GNN explainability remains in flux. Different comparisons find mixed results for different methods, with many explainers struggling on more complex GNN architectures and tasks. This presents an urgent need for a more careful theoretical analysis of competing GNN explanation methods. In this work we take a closer look at GNN explanations in two different settings: input-level explanations, which produce explanatory subgraphs of the input graph, and layerwise explanations, which produce explanatory subgraphs of the computation graph. We establish the first theoretical connections between the popular perturbation-based and classical gradient-based methods, as well as point out connections between other recently proposed methods. At the input level, we demonstrate conditions under which GNNExplainer can be approximated by a simple heuristic based on the sign of the edge gradients. In the layerwise setting, we point out that edge gradients are equivalent to occlusion search for linear GNNs. Finally, we demonstrate how our theoretical results manifest in practice with experiments on both synthetic and real datasets. KDD Availability Link: The source code of this paper has been made publicly available at https://doi.org/10.5281/zenodo.15485808 . 1. Introduction In response to the emergence of Graph Neural Networks (GNNs) for machine learning on graph-structured data, there has been a recent surge of methods aimed to explain GNNs. While explainability has been studied extensively in other domains ( Bach et al. 2015 ; Ribeiro et al. 2016 ; Lundberg and Lee 2017 ; Selvaraju et al. 2017 ; Sundararajan et al. 2017 ; Ancona et al. 2018 ; Adebayo et al. 2018 ) , only recently have methods been proposed to deal with GNNs and the unique challenges posed by graph-structured input. In addition to the input node features, GNNs also use the given graph structure to make predictions. Therefore, explainability methods are tasked with identifying important subgraphs . In this work we focus on post-hoc explainers, which explain the predictions of a fixed, trained GNN. We also focus on instance-based explanation, where each prediction is explained separately, irrespective of the model’s behavior on other samples. Finally, we focus on explanations in terms of the graph topology rather than the node features. Although a number of empirical comparisons have been performed between various methods ( Faber et al. 2021 ; Amara et al. 2022 ; Agarwal et al. 2023 ; Longa et al. 2025 ) , the state of the art remains unclear. The efficacy of different methods is mixed across comparisons on different tasks with different GNN models. For example, saliency maps are consistently a strong baseline, often outperforming more sophisticated methods despite their simplicity ( Amara et al. 2022 ) . In addition, while most explainability methods are evaluated on the straightforward Graph Convolutional Network (GCN) ( Kipf and Welling 2017 ) , Longa et al. 2025 find that other popular architectures such as Graph Isomorphism Networks (GIN) ( Xu et al. 2018a ) are substantially more difficult for explainers. Moreover, some methods are brittle on real data despite strong performance on synthetic datasets with clear ground-truth explanations. Alarmingly, Agarwal et al. ( Agarwal et al. 2022 ) find that on some datasets, existing methods may struggle to outperform even randomly selecting edges in terms of unfaithfulness. These findings present an urgent need for a clearer theoretical understanding of GNN explainers. While some gradient and decomposition-based methods have been unified in other settings ( Ancona et al. 2018 ) , the novelty of many GNN-specific methods means that there is very little unified theory. Our analysis helps both to clarify the state of explainability in GNNs and to suggest additional avenues for future research. Our contributions are as follows: (1) We identify conditions under which GNNExplainer produces explanations which are similar to a simple gradient-based heuristic ( Section 4.1 ). (2) Using a decomposition of the computation graph into paths, we show that Layerwise Occlusion and Layerwise Gradients are equivalent for linear GNNs ( Section 4.3 ). (3) Leveraging this path decomposition, we also obtain a new interpretation of AMP-ave ( Xiong et al. 2023 ) , a recent algorithm to approximate relevant paths for a GNN. We use this interpretation to describe a simple algorithm that performs an exact computation. We also draw a connection to GOAt ( Lu et al. 2024b ) , another recently proposed decomposition method ( Section 5 ). (4) We validate our analysis through extensive experiments on synthetic and real data. We also demonstrate that our simple algorithm for computing relevant paths outperforms AMP-ave ( Section 6 ). Taken together, our results show that explanability for GNNs remains closely tied to the behavior of gradient-based methods, which are simple and easy to compute. As the need for explainable GNNs continues to grow, we hope this work will provide a more unified perspective on the design space of possible explanation methods. 2. Related Works Numerous explainability methods have been proposed for GNNs, and they are often often grouped into several distinct categories: Gradient-based methods such as saliency maps ( Pope et al. 2019 ) , Gradient \odot Input ( Shrikumar et al. 2017 ) , or Integrated Gradients ( Sundararajan et al. 2017 ) use backpropagation to compute a function of the network gradients with respect to the node input features or the adjacency matrix. Decomposition-based methods attempt to decompose the output in terms of the inputs. They may also use backpropagation to compute attributions, as in CAM ( Zhou et al. 2016 ) , LRP ( Bach et al. 2015 ; Schnake et al. 2021 ) , or DeepLIFT ( Shrikumar et al. 2017 ) , or they may use other strategies based on knowledge of the network like DEGREE ( Feng et al. 2022 ) and GOAt ( Lu et al. 2024b ) . Perturbation-based methods study how the network prediction changes as the input changes. The most simple is Occlusion search ( Zeiler and Fergus 2014 ) , but recently more sophisticated methods have become popular for GNNs such as GNNExplainer ( Ying et al. 2019 ) , PGExplainer ( Luo et al. 2020 ) , and GraphMask ( Schlichtkrull et al. 2022 ) . Search-based methods such as SubgraphX ( Yuan et al. 2021 ) , sGNN-LRP ( Xiong et al. 2022 ) , and EiG-Search ( Lu et al. 2024a ) attempt to build an explanatory subgraph by performing a heuristic search over the space of possible subgraphs. Surrogate-based methods like GraphLIME ( Huang et al. 2023 ) and PGM-Explainer ( Vu and Thai 2020 ) train a simpler interpretable model which behaves similarly to the target