pith. sign in

arxiv: 2606.22033 · v1 · pith:PPGARYDLnew · submitted 2026-06-20 · 💻 cs.LG · cs.AI

A Completion-Aware Framework for Impactful Counterfactual Explainability in Graph Neural Networks

Pith reviewed 2026-06-26 11:45 UTC · model grok-4.3

classification 💻 cs.LG cs.AI
keywords counterfactual explainabilitygraph neural networkslink predictiongraph completionmodel-agnostic explanationslocal explanationsgraph classificationedge prediction
0
0 comments X

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.

The paper proposes a pipeline for generating local counterfactual explanations in GNNs that integrates factual explainability techniques with missing edge prediction models drawn from link prediction. The goal is to produce explanations of higher quality, greater robustness, and improved intuitiveness than prior methods that add or remove edges without such guidance. Experiments on real-world and synthetic graph classification benchmarks, covering both binary and multi-label settings, show gains over state-of-the-art baselines on multiple metrics. A sympathetic reader would care because clearer, more reliable explanations help users understand and trust GNN decisions on structured data.

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

These are editorial extensions of the paper, not claims the author makes directly.

  • 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

Figures reproduced from arXiv: 2606.22033 by Filippos Gouidis, Maria Myrto Villia, Panos Trahanias, Theodore Patkos.

Figure 1
Figure 1. Figure 1: Overview of the DR-CFGNN pipeline. Φ(GF ) = Φ(G). Similarly, a counterfactual explainer ΨΦ,CF (·) aims to find one or more graphs GCF , which have minimal and reasonable changes to G and lead to a different prediction, i.e., Φ(GCF ) = yCF such that Φ(GCF ) ̸= Φ(G). This typically involves an optimization process via the minimization of a loss func￾tion capturing the distance between the prediction of the i… view at source ↗
Figure 2
Figure 2. Figure 2: Sampling probabilities (Eq. 4) for de￾termining the number of edges removal (α = 1.7, β = 1) and edges addition (α = .2, β = 3) [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 4
Figure 4. Figure 4: Validity After Noise and well-targeted explanations. All variants not only outperform state-of-the￾art baselines but also achieve exceptionally high minimality scores. The perfect score of the Random baseline is due to its search strategy, which stops as soon as a valid counterfactual is found, starting from the smallest edit sets. An additional desirable characteristic of CfXs is robustness, i.e., the val… view at source ↗
Figure 5
Figure 5. Figure 5: Counterfactual examples generated by the model with the +OH module, [PITH_FULL_IMAGE:figures/full_fig_p026_5.png] view at source ↗
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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

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)
  1. [§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.
  2. [§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)
  1. [§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.
  2. [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

2 responses · 0 unresolved

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
  1. 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

  2. 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

0 steps flagged

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

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are described in the abstract; the work is presented as an engineering pipeline rather than a theoretical derivation.

pith-pipeline@v0.9.1-grok · 5650 in / 985 out tokens · 20401 ms · 2026-06-26T11:45:11.459639+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

42 extracted references · 17 canonical work pages

  1. [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)

  2. [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. [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)

  4. [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. [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)

  6. [6]

    ACM Trans

    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. [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. [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)

  9. [9]

    Moghaddam, A., Wattenhofer, R.: When comparing to ground truth is wrong: On evaluating gnn explanation methods

    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. [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)

  11. [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

  12. [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)

  13. [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. [14]

    2024 , isbn =

    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. [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. [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)

  17. [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)

  18. [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. [19]

    ACM Comput

    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. [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)

  21. [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)

  22. [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. [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)

  24. [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)

  25. [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)

  26. [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

  27. [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. [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. [29]

    ACM Comput

    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. [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)

  31. [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)

  32. [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. [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. [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)

  35. [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)

  36. [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)

  37. [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)

  38. [38]

    IEEE Trans

    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. [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)

  40. [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)

  41. [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)

  42. [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...