# Structure Your Data: Towards Semantic Graph Counterfactuals

arXiv: https://arxiv.org/abs/2403.06514 · HTML: https://mlsanity.com/paper/2403.06514/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Mar 2024.

## Built on by (most cited first, 6 of 6)

- [V-CECE: Visual Counterfactual Explanations via Conceptual Edits](https://mlsanity.com/paper/2509.16567/) (2025)
- [Semantic Prototypes: Enhancing Transparency Without Black Boxes](https://mlsanity.com/paper/2407.15871/) (2024)
- [SCENIR: Visual Semantic Clarity through Unsupervised Scene Graph Retrieval](https://mlsanity.com/paper/2505.15867/) (2025)
- [HalCECE: A Framework for Explainable Hallucination Detection through Conceptual Counterfactuals in Image Captioning](https://mlsanity.com/paper/2503.00436/) (2025)
- [Through the PRISm: Importance-Aware Scene Graphs for Image Retrieval](https://mlsanity.com/paper/2512.18407/) (2025)
- [U-CECE: A Universal Multi-Resolution Framework for Conceptual Counterfactual Explanations](https://mlsanity.com/paper/2604.08295/) (2026)

## Abstract (arXiv)

Counterfactual explanations (CEs) based on concepts are explanations that consider alternative scenarios to understand which high-level semantic features contributed to particular model predictions. In this work, we propose CEs based on the semantic graphs accompanying input data to achieve more descriptive, accurate, and human-aligned explanations. Building upon state-of-the-art (SoTA) conceptual attempts, we adopt a model-agnostic edit-based approach and introduce leveraging GNNs for efficient Graph Edit Distance (GED) computation. With a focus on the visual domain, we represent images as scene graphs and obtain their GNN embeddings to bypass solving the NP-hard graph similarity problem for all input pairs, an integral part of the CE computation process. We apply our method to benchmark and real-world datasets with varying difficulty and availability of semantic annotations. Testing on diverse classifiers, we find that our CEs outperform previous SoTA explanation models based on semantics, including both white and black-box as well as conceptual and pixel-level approaches. Their superiority is proven quantitatively and qualitatively, as validated by human subjects, highlighting the significance of leveraging semantic edges in the presence of intricate relationships. Our model-agnostic graph-based approach is widely applicable and easily extensible, producing actionable explanations across different contexts.