Research map / Graph learning / Knowledge and temporal graphs
Structure Your Data: Towards Semantic Graph Counterfactuals
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.
Proposes model-agnostic semantic graph counterfactual explanations for visual (and audio) classifiers, using scene graphs, GED ground truth, and a siamese GCN to approximate GED for efficient counterfactual retrieval.
Problem
Concept-based counterfactual explanations rely on unstructured concept sets that ignore object multiplicity and relations, and exact graph edit distance between semantic graphs is NP-hard to compute for all input pairs.
Approach
Represent inputs as semantic (scene) graphs and train a siamese GNN with MDS-style loss to regress GED, so counterfactuals are retrieved by embedding similarity with GED computed only for about N/2 training pairs, instead of exact GED for all pairs.
Key results
- On CUB, the GNN-based method reaches P@1 0.19 and binary NDCG@4... versus 0.02 for CVE, and lowest total edits (10.5 vs 13.13 for CVE and 11.73 for SC).
- In a human preference survey, annotators preferred the proposed CEs over SC 48.86% vs 19.32% and over CVE 48.42% vs 26.27% (win vs lose).
- On VG-DENSE, GCN-70K achieves P@1 0.25 and binary P@4 0.49 against ground-truth GED rankings, with GCN outperforming GIN and GAT variants.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use semantic graph counterfactual retrieval instead of pixel-level CVE | CUB counterfactual retrieval · CUB | P@1: 0.02 -> 0.19 | Helped |
| use semantic graph counterfactual retrieval instead of set-based SC | CUB counterfactual retrieval · CUB | total edits: 11.73 -> 10.5 | Helped |
| use semantic graph counterfactuals instead of CVE | CUB human preference survey · CUB | human preference win %: 48.42% win; 26.27% lose | Helped |
| provide graph edits without images during the learning stage (ablation) | Ours machine-teaching experiment · CUB | human test accuracy %: 93.88 -> 89.28 | Hurt |
| use graph-based retrieval instead of SC when methods disagree | VG counterfactual retrieval · VG-DENSE | average top-1 GED: 128.67 -> 122.41 | Helped |
| use graph-based retrieval instead of SC when methods disagree | VG counterfactual retrieval · VG-RANDOM | average top-1 GED: 186.77 -> 180.67 | Helped |
| use GCN instead of GAT (ablation) | GNN similarity component · VG-DENSE | P@4: 0.32 -> 0.37 | Helped |
| use GCN instead of GIN (ablation) | GNN similarity component · VG-DENSE | P@4: 0.27 -> 0.37 | Helped |
| use GCN instead of GAT (ablation) | GNN similarity component · VG-RANDOM | P@4: 0.29 -> 0.30 | Helped |
| use GCN instead of GIN (ablation) | GNN similarity component · VG-RANDOM | P@4: 0.07 -> 0.30 | Helped |
| use GCN instead of GAT (ablation) | GNN similarity component · GQA | P@4: 0.22 -> 0.34 | Helped |
| use GCN instead of GIN (ablation) | GNN similarity component · GQA | P@4: 0.29 -> 0.34 | Helped |
Surprising findings
- GCN outperformed the theoretically more expressive GIN, which the authors attribute to the importance of local neighborhood information in small semantic graphs.
- On VG, about 75% of counterfactuals were identical between the proposed method and SC, so averages are dominated by agreement cases.
Limitations
- Relies on quality of scene graph annotations or automatic scene graph generators, which can introduce errors.
- Evaluation uses approximate GED as the ground truth, and the human studies involve small annotator pools of student volunteers.
Experimental setup
Datasets: CUB Visual Genome GQA Action Genome Places365 Smarty4covid web-crawled creative-commons driver/pedestrian images
Benchmarks: CUB VG-DENSE VG-RANDOM GQA Action Genome
Metrics: P@k binary P@k NDCG@k average number of edits average top-1 GED human preference win rate machine-teaching test accuracy
Baselines: CVE SC Pyramid Match graph kernel GIN GAT Graph kernels (GraKeL)
Builds on: Counterfactual Visual Explanations (CVE) Semantic Counterfactuals (SC) GED approximation via LSAP bipartite matching Multi-Dimensional Scaling loss for graph embeddings
Closest papers by meaning
- V-CECE: Visual Counterfactual Explanations via Conceptual Edits (NeurIPS 2025 · similarity 0.89)
- Graph Inverse Style Transfer for Counterfactual Explainability (ICML 2025 · similarity 0.88)
- Robust Stochastic Graph Generator for Counterfactual Explanations (AAAI 2024 · similarity 0.88)
- COMRECGC: Global Graph Counterfactual Explainer through Common Recourse (ICML 2025 · similarity 0.88)
- Counterfactual Explanations for Misclassified Images: How Human and Machine Explanations Differ (Abstract Reprint) (AAAI 2024 · similarity 0.88)
- Towards Fine-Grained Interpretability: Counterfactual Explanations for Misclassification with Saliency Partition (CVPR 2025 · 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.