A Completion-Aware Framework for Impactful Counterfactual Explainability in Graph Neural Networks
Pith reviewed 2026-06-26 11:45 UTC · model grok-4.3
The pith
Coupling factual explainers with missing-edge predictors yields more robust counterfactual explanations for graph neural networks.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central claim is that a completion-aware framework, which augments counterfactual edge additions and removals using link prediction techniques, enhances the quality, robustness, and intuitiveness of local counterfactual explanations in GNNs compared to state-of-the-art methods.
What carries the argument
The completion-aware pipeline that combines factual explainers with missing edge prediction models from link prediction research to guide counterfactual generation.
If this is right
- Explanations avoid unrealistic edge additions by grounding them in predicted missing links.
- Performance gains appear across binary and multi-label graph classification tasks.
- The approach remains model-agnostic and operates at the local level.
- Improvements register on diverse quantitative metrics for real and synthetic graphs.
Where Pith is reading between the lines
- The same coupling could be tested on node-level or graph regression tasks.
- Different link-prediction backbones might further reduce artifacts in sparse graphs.
- The framework may transfer to other graph models that support edge edits.
- A natural next check is whether the method scales to graphs with thousands of nodes without loss of explanation quality.
Load-bearing premise
That integrating missing edge prediction models with factual explainers will produce higher-quality counterfactual explanations without introducing artifacts or reducing robustness on the tested benchmarks.
What would settle it
A head-to-head evaluation on the same benchmarks where the proposed method fails to exceed baselines on quality or robustness metrics or produces explanations with measurably lower fidelity to the original model.
Figures
read the original abstract
In this study, we propose a novel pipeline for generic, model-agnostic, local-level counterfactual explainability in graph neural networks (GNNs). Although counterfactual explainers capable of both adding and removing edges have emerged in recent years, the need for generic and efficient solutions remains unmet, particularly concerning qualitative explanation generation. Our approach couples progress in factual explainability with missing edge prediction models rooted in link prediction research, in order to enhance the quality, robustness and intuitiveness of explanations. A multi-faceted experimental analysis conducted on real-world and synthetic graph classification benchmarks, both binary and multi-label, demonstrates the advancements in comparison to state-of-the-art baselines across diverse metrics.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a completion-aware, model-agnostic pipeline for local counterfactual explainability on GNNs. It augments factual explainers with missing-edge predictors drawn from link-prediction literature so that the resulting explanations can both delete and add edges, with the goal of producing higher-quality, more robust, and more intuitive counterfactuals. A multi-faceted evaluation on real-world and synthetic graph-classification benchmarks (binary and multi-label) is reported to show consistent gains over state-of-the-art baselines across several metrics.
Significance. If the pipeline demonstrably produces valid class-changing counterfactuals whose added edges are both structurally plausible and causally effective, the work would supply a generic, reusable way to improve counterfactual quality by reusing existing link-prediction components. The empirical breadth (multiple datasets, binary/multi-label) would be a modest but useful contribution to the GNN-XAI literature.
major comments (2)
- [§3 and §4] §3 (Proposed Framework) and §4 (Counterfactual Generation): the central claim that link-prediction outputs can be directly substituted into factual explanations to yield higher-quality counterfactuals rests on the unverified assumption that the predicted edges will cross the GNN decision boundary. Link-prediction objectives optimize edge existence, not prediction flip; no explicit verification, filtering, or joint optimization step is described that enforces the counterfactual property. This is load-bearing for all reported gains in quality and robustness.
- [§5] §5 (Experimental Analysis): the multi-faceted evaluation claims advancements over baselines, yet the manuscript provides no quantitative breakdown of how many generated explanations actually change the model prediction versus merely adding plausible edges. Without this metric (or an ablation that isolates the link-prediction component), it is impossible to determine whether the reported improvements reflect genuine counterfactual impact or evaluation artifacts.
minor comments (2)
- [§3] Notation for the factual explainer and the link-prediction module is introduced without a consolidated table of symbols; readers must cross-reference multiple paragraphs.
- [Figure 4] Figure captions for the qualitative examples do not state the original and counterfactual predictions, making it difficult to verify that the displayed graphs are indeed counterfactuals.
Simulated Author's Rebuttal
We thank the referee for the constructive and detailed report. We address each major comment below with clarifications and commitments to revision where the concerns are valid.
read point-by-point responses
-
Referee: [§3 and §4] §3 (Proposed Framework) and §4 (Counterfactual Generation): the central claim that link-prediction outputs can be directly substituted into factual explanations to yield higher-quality counterfactuals rests on the unverified assumption that the predicted edges will cross the GNN decision boundary. Link-prediction objectives optimize edge existence, not prediction flip; no explicit verification, filtering, or joint optimization step is described that enforces the counterfactual property. This is load-bearing for all reported gains in quality and robustness.
Authors: We acknowledge that the manuscript does not describe an explicit verification, filtering, or joint-optimization step that guarantees the link-prediction outputs will flip the GNN prediction. The current pipeline generates candidate graphs by combining factual edge deletions with link-prediction completions and then evaluates the resulting graphs with the target GNN; only those that change the prediction are retained for the reported metrics. While this post-hoc evaluation demonstrates empirical success, the absence of an upfront enforcement mechanism is a legitimate limitation. We will revise §§3–4 to add an explicit verification/filtering step after candidate generation and will report its effect on explanation quality. revision: yes
-
Referee: [§5] §5 (Experimental Analysis): the multi-faceted evaluation claims advancements over baselines, yet the manuscript provides no quantitative breakdown of how many generated explanations actually change the model prediction versus merely adding plausible edges. Without this metric (or an ablation that isolates the link-prediction component), it is impossible to determine whether the reported improvements reflect genuine counterfactual impact or evaluation artifacts.
Authors: The referee correctly notes that the manuscript does not report the raw success rate (fraction of generated candidates that actually flip the prediction) nor an ablation isolating the link-prediction component. All quantitative results are conditioned on valid counterfactuals, which leaves open the possibility that improvements partly reflect selection effects. We will add, in the revised §5, (i) the success-rate statistic across all datasets and (ii) an ablation that removes the link-prediction module and measures the resulting drop in performance, thereby quantifying its isolated contribution. revision: yes
Circularity Check
No circularity: empirical pipeline proposal with no derivations or self-referential steps
full rationale
The paper describes a model-agnostic pipeline that integrates existing factual explainers with link-prediction models for counterfactual generation in GNNs, followed by benchmark experiments. No equations, derivations, or load-bearing self-citations appear in the abstract or high-level description. The central claim is an empirical integration claim rather than a mathematical reduction; the link-prediction component is treated as an external input from prior research, not redefined or fitted in a way that forces the reported outcomes by construction. This is the common case of a self-contained engineering contribution.
Axiom & Free-Parameter Ledger
Reference graph
Works this paper leans on
-
[1]
Scientific Data10(1), 144 (2023)
Agarwal, C., Queen, O., Lakkaraju, H., Zitnik, M.: Evaluating explainability for graph neural networks. Scientific Data10(1), 144 (2023)
2023
-
[2]
Arrar, D., Kamel, N., Lakhfif, A.: A comprehensive survey of link prediction methods. J. Supercomput.80(3), 3902–3942 (Sep 2023). https://doi.org/10.1007/s11227-023-05591-8
-
[3]
IEEE Transactions on NN and Learning Systems34(12), 10334–10345 (2023)
Bacciu, D., Numeroso, D.: Explaining deep graph networks via input perturbation. IEEE Transactions on NN and Learning Systems34(12), 10334–10345 (2023)
2023
-
[4]
In: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
Chakrabarti, D.: Avoiding biases due to similarity assumptions in node embeddings. In: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. p. 56–65. KDD ’22 (2022). https://doi.org/10.1145/3534678.3539287
-
[5]
In: Proceedings of the 37th International Conference on Neural Information Processing Systems
Chen, J., Wu, S., Gupta, A., Ying, R.: D4explainer: in-distribution gnn expla- nations via discrete denoising diffusion. In: Proceedings of the 37th International Conference on Neural Information Processing Systems. NIPS ’23 (2023)
2023
-
[6]
Chen,Z.,Huang,J.,Silvestri,F.,Zhang,Y.,Ahn,H.,Tolomei,G.:Jointfactualand counterfactual explanations for top-k gnn-based recommendations. ACM Trans. Recomm. Syst.4(2) (2025). https://doi.org/10.1145/3731683
-
[7]
In: Proceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis
Chu, Z., Wan, Y., Li, Q., Wu, Y., Zhang, H., Sui, Y., Xu, G., Jin, H.: Graph neural networks for vulnerability detection: A counterfactual explanation. In: Proceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis. p. 389–401 (2024). https://doi.org/10.1145/3650212.3652136
-
[8]
Machine Intelligence Research21(6), 1011–1061 (2024)
Dai, E., Zhao, T., Zhu, H., Xu, J., Guo, Z., Liu, H., Tang, J., Wang, S.: A compre- hensive survey on trustworthy graph neural networks: Privacy, robustness, fairness, and explainability. Machine Intelligence Research21(6), 1011–1061 (2024)
2024
-
[9]
Faber, L., K. Moghaddam, A., Wattenhofer, R.: When comparing to ground truth is wrong: On evaluating gnn explanation methods. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. p. 332–341. KDD ’21 (2021). https://doi.org/10.1145/3447548.3467283
-
[10]
Machine Intelligence Research22(1), 17–59 (2025)
Guo, Z., Wu, Z., Xiao, T., Aggarwal, C., Liu, H., Wang, S.: Counterfactual learning on graphs: A survey. Machine Intelligence Research22(1), 17–59 (2025)
2025
-
[11]
In: International Joint Conference on Artificial Intelligence (2020) Completion-Aware Counterfactual Explanations 17
Hao, Y., Cao, X., Fang, Y., Xie, X., Wang, S.: Inductive link prediction for nodes having only attribute information. In: International Joint Conference on Artificial Intelligence (2020) Completion-Aware Counterfactual Explanations 17
2020
-
[12]
In: International Con- ference on Learning Representations (2026)
Huang, X., Galkin, M., Bronstein, M.M., Ceylan, I.I.: Hyper: A foundation model for inductive link prediction with knowledge hypergraphs. In: International Con- ference on Learning Representations (2026)
2026
-
[13]
In: Proceed- ings of the Sixteenth ACM International Conference on Web Search and Data Mining
Huang, Z., Kosan, M., Medya, S., Ranu, S., Singh, A.: Global counterfactual ex- plainer for graph neural networks. In: Proceedings of the Sixteenth ACM Interna- tional Conference on Web Search and Data Mining. p. 141–149. WSDM ’23 (2023). https://doi.org/10.1145/3539597.3570376
-
[14]
Jiang, J., Leofante, F., Rago, A., Toni, F.: Robust counterfactual expla- nations in machine learning: a survey. In: Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence. IJCAI ’24 (2024). https://doi.org/10.24963/ijcai.2024/894
-
[15]
Kaddour, J., Lynch, A., Liu, Q., Kusner, M.J., Silva, R.: Causal machine learn- ing: A survey and open problems. Found. Trends Optim.9(1–2), 1–247 (2025). https://doi.org/10.1561/2400000052
-
[16]
In: Proceedings of the International Conference on Learning Represen- tations (ICLR) (2017)
Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. In: Proceedings of the International Conference on Learning Represen- tations (ICLR) (2017)
2017
-
[17]
In: Proceedings of the 37th International Conference on Neural Information Processing Systems (2023)
Li, J., Shomer, H., Mao, H., Zeng, S., Ma, Y., Shah, N., Tang, J., Yin, D.: Evaluat- ing graph neural networks for link prediction: current pitfalls and new benchmark- ing. In: Proceedings of the 37th International Conference on Neural Information Processing Systems (2023)
2023
-
[18]
In: Proceedings of the Twelfth International Conference on In- formation and Knowledge Management
Liben-Nowell, D., Kleinberg, J.: The link prediction problem for social networks. In: Proceedings of the Twelfth International Conference on In- formation and Knowledge Management. p. 556–559. CIKM ’03 (2003). https://doi.org/10.1145/956863.956972
-
[19]
Longa, A., Azzolin, S., Santin, G., Cencetti, G., Lio, P., Lepri, B., Passerini, A.: Explaining the explainers in graph neural networks: a comparative study. ACM Comput. Surv.57(5) (2025). https://doi.org/10.1145/3696444
-
[20]
In: Proceed- ings of The 25th International Conference on Artificial Intelligence and Statistics
Lucic, A., Ter Hoeve, M.A., Tolomei, G., De Rijke, M., Silvestri, F.: Cf- gnnexplainer: Counterfactual explanations for graph neural networks. In: Proceed- ings of The 25th International Conference on Artificial Intelligence and Statistics. pp. 4499–4511 (2022)
2022
-
[21]
In: Proceedings of the 34th International Conference on Neural Information Processing Systems
Luo, D., Cheng, W., Xu, D., Yu, W., Zong, B., Chen, H., Zhang, X.: Parameter- ized explainer for graph neural network. In: Proceedings of the 34th International Conference on Neural Information Processing Systems. NIPS ’20 (2020)
2020
-
[22]
Recourse, Repair, Reparation, & Prevention: A Stakeholder Analysis of AI Supply Chains
Ma, J., Takigawa, I., Yamamoto, A.: C2explainer: Customizable mask-based coun- terfactual explanation for graph neural networks. In: Proceedings of the 2025 ACM Conference on Fairness, Accountability, and Transparency. p. 137–149. FAccT ’25 (2025). https://doi.org/10.1145/3715275.3732012
-
[23]
In: Proceedings of the 36th International Conference on Neural Information Processing Systems
Ma, J., Guo, R., Mishra, S., Zhang, A., Li, J.: Clear: generative counterfactual explanations on graphs. In: Proceedings of the 36th International Conference on Neural Information Processing Systems. NIPS ’22 (2022)
2022
-
[24]
In: International Conference on Learning Representations
Mao, H., Li, J., Shomer, H., Li, B., Fan, W., Ma, Y., Zhao, T., Shah, N., Tang, J.: Revisiting link prediction: a data perspective. In: International Conference on Learning Representations. pp. 5124–5159. ICLR ’24 (2024)
2024
-
[25]
Journal of Chemical Information and Modeling52(6), 1686–1697 (2012)
Martins, I.F., Teixeira, A.L., Pinheiro, L., Falcao, A.O.: A bayesian approach to in silico blood-brain barrier penetration modeling. Journal of Chemical Information and Modeling52(6), 1686–1697 (2012)
2012
-
[26]
Artificial intelligence267, 1–38 (2019) 18 M
Miller, T.: Explanation in artificial intelligence: Insights from the social sciences. Artificial intelligence267, 1–38 (2019) 18 M. M. Villia et al
2019
-
[27]
Hierarchical attention transformer networks for long document classification
Numeroso, D., Bacciu, D.: Meg: Generating molecular counterfac- tual explanations for deep graph networks. In: 2021 International Joint Conference on Neural Networks (IJCNN). pp. 1–8 (2021). https://doi.org/10.1109/IJCNN52387.2021.9534266
-
[28]
Prado-Romero, M.A., Prenkaj, B., Stilo, G.: Robust stochastic graph genera- tor for counterfactual explanations. In: 38th AAAI Conference on Artificial In- telligence and 36th Conference on Innovative Applications of Artificial Intelli- gence and 14th Symposium on Educational Advances in Artificial Intelligence. AAAI’24/IAAI’24/EAAI’24 (2024). https://doi...
-
[29]
Prado-Romero,M.A.,Prenkaj,B.,Stilo,G.,Giannotti,F.:Asurveyongraphcoun- terfactual explanations: Definitions, methods, evaluation, and research challenges. ACM Comput. Surv.56(7) (2024). https://doi.org/10.1145/3618105
-
[30]
In: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
Prenkaj, B., Villaizán-Vallelado, M., Leemann, T., Kasneci, G.: Unifying evolution, explanation, and discernment: A generative approach for dynamic graph counter- factuals. In: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. p. 2420–2431. KDD ’24 (2024)
2024
-
[31]
In: Proceedings of the 42nd International Conference on Machine Learning
Prenkaj, B., Zaradoukas, E., Kasneci, G.: Graph inverse style transfer for coun- terfactual explainability. In: Proceedings of the 42nd International Conference on Machine Learning. ICML’25 (2025)
2025
-
[32]
Serra, G., Niepert, M.: L2xgnn: learning to explain graph neural networks. Mach. Learn.113(9), 6787–6809 (2024). https://doi.org/10.1007/s10994-024-06576-1
-
[33]
In:ProceedingsoftheACMWebConference2022.p.1018–1027.WWW’22(2022)
Tan, J., Geng, S., Fu, Z., Ge, Y., Xu, S., Li, Y., Zhang, Y.: Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning. In:ProceedingsoftheACMWebConference2022.p.1018–1027.WWW’22(2022). https://doi.org/10.1145/3485447.3511948
-
[34]
In: DSAA 2023 - The 10th IEEE International Conference on Data Science and Advanced Analytics (2023)
Werner,L.,Layaïda,N.,Genevès,P.,Chlyah,S.:KnowledgeEnhancedGraphNeu- ral Networks for Graph Completion. In: DSAA 2023 - The 10th IEEE International Conference on Data Science and Advanced Analytics (2023)
2023
-
[35]
Journal of the American Statistical Association22(158), 209–212 (1927)
Wilson, E.B.: Probable inference, the law of succession, and statistical inference. Journal of the American Statistical Association22(158), 209–212 (1927)
1927
-
[36]
Data Science and Engineering7(3), 253–278 (2022)
Wu, H., Song, C., Ge, Y., Ge, T.: Link prediction on complex networks: An exper- imental survey. Data Science and Engineering7(3), 253–278 (2022)
2022
-
[37]
Curran Associates Inc., Red Hook, NY, USA (2019)
Ying, R., Bourgeois, D., You, J., Zitnik, M., Leskovec, J.: GNNExplainer: gener- ating explanations for graph neural networks. Curran Associates Inc., Red Hook, NY, USA (2019)
2019
-
[38]
Yuan, H., Yu, H., Gui, S., Ji, S.: Explainability in graph neural networks: A tax- onomic survey. IEEE Trans. Pattern Anal. Mach. Intell.45(5), 5782–5799 (2023). https://doi.org/10.1109/TPAMI.2022.3204236
-
[39]
In: International conference on machine learning
Yuan,H.,Yu,H.,Wang,J.,Li,K.,Ji,S.:Onexplainabilityofgraphneuralnetworks via subgraph explorations. In: International conference on machine learning. pp. 12241–12252 (2021)
2021
-
[40]
In: Pro- ceedings of the 32nd International Conference on Neural Information Processing Systems
Zhang, M., Chen, Y.: Link prediction based on graph neural networks. In: Pro- ceedings of the 32nd International Conference on Neural Information Processing Systems. p. 5171–5181. NIPS’18 (2018)
2018
-
[41]
In: Proceedings of the 14th International Conference on Learning Representations
Zhang, Y., Yang, S.B., Khan, A., Akcora, C.G.: Atex-cf: Attack-informed coun- terfactual explanations for graph neural networks. In: Proceedings of the 14th International Conference on Learning Representations. ICLR ’26 (2026)
2026
-
[42]
In: Proceedings of the aaai conference on artificial intelligence
Zhao, T., Liu, Y., Neves, L., Woodford, O., Jiang, M., Shah, N.: Data augmenta- tion for graph neural networks. In: Proceedings of the aaai conference on artificial intelligence. vol. 35, pp. 11015–11023 (2021) Completion-Aware Counterfactual Explanations 19 A Appendix The Appendix first presents the datasets and their statistics (Section A.1) and then de...
2021
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.