Counterfactual Analysis on Large Graphs

Counterfactual analysis aims to identify minimal and semantically meaningful changes that alter a model's prediction. Existing perturbation approaches generate counterfactuals by directly editing nodes, edges, or attributes, often producing explanations that are model-dependent and detached from the underlying data distribution. In this paper, we introduce Counterfactual Subgraph Retrieval (CF-SGR), a dataset-grounded formulation that retrieves from a large graph subgraphs that are structurally and semantically similar to a query but induce different predictions under the same model, yielding domain-valid and verifiable counterfactual explanations. To solve CF-SGR, we propose Concept-guided Counterfactual Subgraph Retrieval (CCSGR), which operates in a shared multi-scale graph concept space aligned with a trained GNN and replaces fine-grained node-level edits with concept-level reasoning. CCSGR performs retrieval via concept-based filtering, robustness-aware ranking, and diversity-aware selection, enabling scalable and non-redundant search over large graphs. We provide theoretical guarantees on correctness, robustness, and efficiency and demonstrate that CCSGR improves retrieval quality by up to 40% while achieving speedups of 20× on large-scale graphs across six real-world datasets spanning five domains.