A Comparative Study of Counterfactual Explainers for Graph Neural Networks Enabling Multiple Types of Graph Edit
Maria Myrto Villia, Filippos Gouidis, Theodore Patkos, Panos Trahanias
cs.LG
Quick verdict
Benchmarks six counterfactual explainers for GNNs incl. add+remove methods; useful first head-to-head, but single-run stats and table anomalies weaken rigor.
Summary
This SETN 2026 paper reports the first head-to-head comparison of six counterfactual explanation methods for graph neural networks that can both add and delete edges: CF2, D4Explainer, RSGG-CE, GIST, the global GCFExplainer, and an exhaustive Random baseline. Evaluation spans seven graph classification datasets (four synthetic BA-motif variants, BBBP, Twitter, Graph-SST5) and four node classification datasets (BA-Shapes, Tree-Cycles, Cora, PubMed), measuring validity, fidelity, explanation size, minimality, motif proximity, and runtime. No method dominates: CF2 attains the best motif proximity on most synthetic datasets but lower validity on real data; RSGG-CE trains fastest (0.6-14.5 s) with strong minimality; D4Explainer is accurate but needs up to about 110,569 s of training on Graph-SST5; GIST produces impractically large explanations; and the removal-only CF-GNNExplainer stays highly valid for node classification. Key limitations: results are single runs without variance estimates or significance tests; the text claims BA-Shapes has five classes while Table 2 reports four; Table 7 contains out-of-range values; node-classification coverage is thin, with D4Explainer absent on Cora and PubMed; and no code release is stated.
Review complete
Assessment at a glance
5
risk flags identified
● high 1
● medium 2
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- No single counterfactual explainer consistently performs best across validity, efficiency, explanation size, minimality, and motif proximity (Sections 4.4, 6).
- Quality metrics beyond validity and fidelity - motif proximity and minimality - are essential, since high-validity methods like the Random baseline and GCFExplainer score poorly on them (Tables 4-5).
- Even on simple synthetic data where the prediction hinges on one motif, most explainers fail to consistently target their edits at that motif (Table 4).
- Runtime differs by orders of magnitude across explainers (RSGG-CE 0.6-14.5 s vs D4Explainer up to ~110,569 s training, Table 6), making efficiency a decisive practical criterion.
- Methods applicable to both graph and node classification show a performance drop on node classification, while removal-only CF-GNNExplainer remains highly valid there (Section 5, Tables 7-10).
Strengths
First head-to-head comparison of the add+remove explainer generation
Section 1/2.2 correctly observes that D4Explainer, RSGG-CE and GIST were each evaluated only against removal-only baselines and never against each other; this paper fills that gap and extends the authors' earlier evaluation [31] from graph-only to graph+node classification.
Metric suite goes beyond validity/fidelity to expose quality blind spots
Motif Proximity (Table 4) shows that even on trivial synthetic data most methods edit outside the ground-truth motif (e.g., RSGG-CE 0.27, GIST 0.30 vs CF2 0.97 on BA-4Motifs), and the Random baseline's low motif proximity despite perfect validity shows validity alone is a misleading headline metric - a genuinely useful negative result.
Runtime transparency with order-of-magnitude separations
New synthetic probes for multi-class and incomplete motifs
Full per-dataset hyperparameter disclosure
Weaknesses
No statistical rigor: single runs, no dispersion, no significance testing
Internal inconsistencies in node-classification reporting
Random baseline's perfect minimality is definitional, not empirical
Thin and partial node-classification coverage
No code release and the authors' own method is not benchmarked
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This SETN 2026 conference paper (arXiv 2609.05113, FORTH/Crete) positions itself as the first head-to-head comparison of counterfactual explainers (CfX) for GNNs that can both add and delete edges - a capability gap the authors argue recent surveys [10, 16, 26] and per-method evaluations left unaddressed. It extends the authors' own prior study [31] (DR-CFGNN) from graph-only to graph plus node classification. Motivation is concrete: Section 3's drug-drug interaction example shows why explanations sometimes require edge *additions* (a missing interaction with drug C), which subgraph-based explainers cannot express. Systems compared on graph classification: CF2, D4Explainer, RSGG-CE, GIST, GCFExplainer (global reference), and an exhaustive Random baseline; on node classification: CF2, D4Explainer, CF-GNNExplainer. Central claims: (1) no explainer dominates across validity, efficiency, size, minimality, motif proximity; (2) quality metrics beyond validity/fidelity are necessary; (3) standardized benchmarks are lacking.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What does this paper compare?
It benchmarks six counterfactual explanation methods for graph neural networks - CF2, D4Explainer, RSGG-CE, GIST, the global GCFExplainer, and an exhaustive Random search baseline - most of which can both add and delete edges, across seven graph-classification datasets (BA-motif variants, BBBP, Twitter, Graph-SST5) and four node-classification datasets (BA-Shapes, Tree-Cycles, Cora, PubMed), using validity, fidelity, explanation size, minimality, motif proximity, and runtime.
Which counterfactual GNN explainer is best according to the study?
None dominates. CF2 gives the best motif proximity on most synthetic datasets but lower validity on real data; RSGG-CE trains fastest (0.6-14.5 s) with strong minimality; D4Explainer is accurate but trains up to about 110,569 seconds (~31 hours) on Graph-SST5; GIST produces impractically large explanations; and the edge-removal-only CF-GNNExplainer remains highly valid for node classification.
Is code available for this paper?
The paper text contains no code or repository link. However, Appendix A discloses per-dataset hyperparameters for every method, and the datasets used (BA-motifs, BBBP, Twitter, Graph-SST5, Cora, PubMed) are all public.
What are the main limitations of the study?
Results come from single runs with no variance estimates or significance tests; the node-classification table contains apparent numerical inconsistencies (validity values above 1, and a claim of five BA-Shapes classes against four in the dataset table); node coverage is thin, with D4Explainer missing entirely on Cora and PubMed; and no code release is announced.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- In the extracted text, cell values of Tables 3 and 7 are interleaved into ambiguous number runs; per-cell number citations were therefore restricted to cleanly delimited tables (4, 5, 6, 8, 9, 10) and prose-stated figures.
- The out-of-range Table 7 values cited above (e.g., 1.10, 2.73) may be PDF-extraction/layout artifacts rather than errors in the published paper; they are flagged as reviewer questions, not confirmed defects.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.