mlsanityData to 14 Oct 2026

Generating Robust Counterfactual Witnesses for Graph Neural Networks

arXiv 2404.19519 ↗First posted 30 Apr 2024cs.LG cs.DBcited by 4

Not on the map. Why?

Abstract (arXiv)

This paper introduces a new class of explanation structures, called robust counterfactual witnesses (RCWs), to provide robust, both counterfactual and factual explanations for graph neural networks. Given a graph neural network M, a robust counterfactual witness refers to the fraction of a graph G that are counterfactual and factual explanation of the results of M over G, but also remains so for any "disturbed" G by flipping up to k of its node pairs. We establish the hardness results, from tractable results to co-NP-hardness, for verifying and generating robust counterfactual witnesses. We study such structures for GNN-based node classification, and present efficient algorithms to verify and generate RCWs. We also provide a parallel algorithm to verify and generate RCWs for large graphs with scalability guarantees. We experimentally verify our explanation generation process for benchmark datasets, and showcase their applications.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 30 of its 48 references that are in the map. First posted on arXiv 30 Apr 2024.

Builds on

30 of 48 references.

References · 30

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2018How Powerful are Graph Neural Networks?cited by 4,393
  5. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  6. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  7. 2013Visualizing and Understanding Convolutional Networkscited by 2,290
  8. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 993
  9. 2018Link Prediction Based on Graph Neural Networkscited by 832
  10. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 787
  11. 2019GNNExplainer: Generating Explanations for Graph Neural Networkscited by 737
  12. 2020Parameterized Explainer for Graph Neural Networkcited by 426
18 more
  1. 2020Explainability in Graph Neural Networks: A Taxonomic Surveycited by 384
  2. 2018Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generationcited by 364
  3. 2018AllenNLP: A Deep Semantic Natural Language Processing Platformcited by 347
  4. 2021On Explainability of Graph Neural Networks via Subgraph Explorationscited by 281
  5. 2020XGNN: Towards Model-Level Explanations of Graph Neural Networkscited by 211
  6. 2020GraphLIME: Local Interpretable Model Explanations for Graph Neural Networkscited by 209
  7. 2020Interpreting Graph Neural Networks for NLP With Differentiable Edge Maskingcited by 153
  8. 2017Predicting multicellular function through multi-layer tissue networkscited by 138
  9. 2021CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networkscited by 119
  10. 2020Scalable Graph Neural Networks via Bidirectional Propagationcited by 87
  11. 2022Learning and Evaluating Graph Neural Network Explanations based on Counterfactual and Factual Reasoningcited by 79
  12. 2021Robust Counterfactual Explanations on Graph Neural Networkscited by 72
  13. 2019Certifiable Robustness to Graph Perturbationscited by 62
  14. 2022GStarX: Explaining Graph Neural Networks with Structure-Aware Cooperative Gamescited by 42
  15. 2021Accelerating Large Scale Real-Time GNN Inference using Channel Pruningcited by 41
  16. 2019Layerwise Relevance Visualization in Convolutional Text Graph Classifierscited by 32
  17. 2022Global Counterfactual Explainer for Graph Neural Networkscited by 30
  18. 2024View-based Explanations for Graph Neural Networkscited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 1.

4 papers.

  1. 2026ATEX-CF: Attack-Informed Counterfactual Explanations for Graph Neural Networkscited by 2
  2. 2025COMRECGC: Global Graph Counterfactual Explainer through Common Recoursecited by 1
  3. 2025Towards Comprehensive and Prerequisite-Free Explainer for Graph Neural Networkscited by 0
  4. 2025ARM-Explainer -- Explaining and improving graph neural network predictions for the maximum clique problem using node features and association rule miningcited by 0