Research map / Graph learning / GNN architectures
COMRECGC: Global Graph Counterfactual Explainer through Common Recourse
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Formalizes global common-recourse counterfactual explanations for GNNs (FCR/FC problems) and proposes ComRecGC, a multi-head vertex-reinforced random walk plus DBSCAN clustering to find a small set of shared recourses covering reject graphs.
Problem
Global counterfactual explanations for GNN binary graph classifiers typically yield many instance-specific counterfactuals that are hard to interpret; the problem of finding a small set of common recourse transformations shared across many reject graphs is unexplored for GNNs.
Approach
Defines common recourse as graph-embedding difference vectors that lie within a threshold of a shared center vector, and finds them via a multi-head vertex-reinforced random walk in graph-edit space guided by a GNN's counterfactual probability, followed by DBSCAN clustering and greedy max-coverage selection.
Key results
- On the FCR problem, ComRecGC reaches 44.9% coverage on NCI1 vs 21.4% for GCFExplainer, 52.6% on Mutagenicity vs 20.6%, 35.2% on AIDS vs 14.2%, and 47.3% on Proteins vs 32.8%.
- On the FC problem, ComRecGC achieves 33.4% / 46.7% / 24.3% / 39.6% coverage across NCI1, Mutagenicity, AIDS, Proteins, outperforming GCFExplainer (14.7%, 11.9%, 14.2%, 29.8%).
- Compared with global graph counterfactual explainers using 10 explanations, ComRecGC attains 39.4% coverage on Mutagenicity and 18.0% on Proteins, the best among compared methods.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use ComRecGC instead of GCFExplainer | FCR · NCI1 | coverage: 21.4% -> 44.9% | Helped |
| use ComRecGC instead of GCFExplainer | FCR · Mutagenicity | coverage: 20.6% -> 52.6% | Helped |
| use ComRecGC instead of GCFExplainer | FCR · AIDS | coverage: 14.2% -> 35.2% | Helped |
| use ComRecGC instead of GCFExplainer | FCR · Proteins | coverage: 32.8% -> 47.3% | Helped |
| use ComRecGC instead of LocalRWExplainer (NCI1 and Mutagenicity) or GCFExplainer (AIDS and Proteins) | FC · NCI1, Mutagenicity, AIDS, Proteins | coverage: 19.0% -> 33.4%; 18.2% -> 46.7%; 14.2% -> 24.3%; 29.8% -> 39.6% | Helped |
| remove clustering (ablation) | ComRecGC · FCR / NCI1 | coverage: 42.9% -> 10.1% | Hurt |
| remove clustering (ablation) | ComRecGC · FCR / Mutagenicity | coverage: 51.8% -> 8.2% | Hurt |
| remove clustering (ablation) | ComRecGC · FCR / AIDS | coverage: 34.7% -> 13.6% | Hurt |
| remove clustering (ablation) | ComRecGC · FCR / Proteins | coverage: 46.4% -> 33.9% | Hurt |
| add multi-head random walk (ablation) | ComRecGC · FCR / NCI1 | coverage: 21.4% -> 42.9% | Helped |
| add multi-head random walk (ablation) | ComRecGC · FCR / Mutagenicity | coverage: 20.6% -> 51.8% | Helped |
| add multi-head random walk (ablation) | ComRecGC · FCR / AIDS | coverage: 14.2% -> 34.7% | Helped |
Surprising findings
- Removing the clustering step drops coverage sharply (e.g., NCI1 from 42.9% to 10.1%), showing clustering is critical.
- Raising the counterfactual threshold theta to 0.15 made DBSCAN intractable on several datasets, with coverage gains limited on AIDS.
Limitations
- Parameters theta and Delta are dataset-dependent and hard to tune; theta=0.15 made clustering intractable.
- Random walk in graph-edit space ignores chemical feasibility, so generated counterfactual molecules may not be realistic.
- Coverage gains over the global baseline are small on the 10-explanation comparison for NCI1 and AIDS (ComRecGC is comparable, not superior).
Experimental setup
Datasets: Mutagenicity NCI1 AIDS Proteins
Benchmarks: Mutagenicity NCI1 AIDS Proteins
Metrics: coverage cost (total recourse length)
Baselines: GCFExplainer LocalRWExplainer Dataset Counterfactuals RCExplainer CFF explainer
Builds on: GCFExplainer vertex reinforced random walk Greed graph embedding for GED
Closest papers by meaning
- GnnXemplar: Exemplars to Explanations - Natural Language Rules for Global GNN Interpretability (NeurIPS 2025 · similarity 0.89)
- Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks (ICLR 2024 · similarity 0.89)
- Structure Your Data: Towards Semantic Graph Counterfactuals (ICML 2024 · similarity 0.88)
- Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective (ICML 2025 · similarity 0.88)
- GraphTrail: Translating GNN Predictions into Human-Interpretable Logical Rules (NeurIPS 2024 · similarity 0.88)
- RegExplainer: Generating Explanations for Graph Neural Networks in Regression Tasks (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.