Aug 2026· Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2· pp. 390-401· 0 citations· 28 references
Abstract
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.
GraphMind, a model that jointly processes micro- and macro-level structures for novelty prediction and rationale generation, is proposed that significantly outperforms baseline LLMs in both novelty score prediction and rationale generation.
Italo Luis da Silva, Hanqi Yan, Lin Gui et al.· Proceedings of the 32nd ACM...· 1 citation
Counterfactual explanations for graph-structured data seek to determine minimal and realistic modifications required in an input graph to alter a model's prediction to a predefined output. Although counterfactual explainers that support modifying the graph by both adding and removing edges have recently emerged, there is still a lack of general and efficient methods, especially when considering the quality of the generated explanations. Moreover, the problem remains far from solved, as existing methods exhibit different strengths and weaknesses, often trading off between explanation size, coverage and quality. For this reason, it is important to identify where each method performs well and where it falls short, so as to guide future research in the field. Thus, our study compares six state-of-the-art (SOTA) models on a diverse set of real-world and synthetic datasets, covering both binary and multi-class graph and node classification tasks, and evaluates their performance using diverse quantitative and qualitative metrics.
Maria Myrto Villia, Filippos Gouidis, T. Patkos et al.· 0 citations
Temporal graph counterfactual explanations typically change past events to change or invalidate an original prediction, while leaving its replacement unspecified. Yet a user facing a predicted outcome often asks which past conditions would make a particular alternative occur instead. We formulate this destination-specific question as the Specified-Foil Counterfactual: given an original prediction A and a foil B fixed before search, find a low-cost past-event intervention under which the same predictor selects B as top-ranked. Our trace-guided intervention search contrasts the completed execution of A with a reconstructed incomplete execution of B, maps their difference to DELETE, INSERT, REWIRE, RELABEL, and SHIFT operations, and verifies B through exact replay. We instantiate this principle with LiFTER on continuous-time dynamic graphs and TLogic on temporal knowledge graphs. On CTDGs, the method retains 85.7-93.6% of black-box greedy successes while reducing predictor evaluations by 75.0-80.0%; on TKGs, it reaches the specified foil in 74.8% of 600 comparisons. Executable traces thereby become computational structures for constructing conditions of unselected alternatives, rather than records used only to explain predictions already made.
This work proposes Graph Diffusion Counterfactual Explanation via Inversion (GDCE-I), a discrete denoising diffusion model with a novel discrete inversion scheme that enables distribution-aware edits leveraging the whole domain edit space and qualitatively shows that GDCE-I attains interpretable in-distribution solutions.
Scientific papers may relate by problem, method, result, or contribution, but document-level retrievers collapse these into a single similarity score without saying why they are related. Citation- and similarity-based retrieval alone also confines search to the neighbourhood of what is already known, whereas generative retrieval generates document identifiers directly, enabling the exploratory retrieval that scientific discovery depends on. We connect papers in a graph whose edges are typed by these four facets, derived from facet items and citation signals, and distil it into a generative retriever whose identifiers are the papers'own facet text. Two graph properties do not survive naive distillation. First, because every training pair is an edge, naive enumeration indexes just 84% of the corpus. Coverage-aware distillation makes every paper learnable through a reverse-neighbour fallback, a minimum-coverage threshold, and edge-importance weighting. Second, constrained decoding guarantees that every generated identifier is a valid paper, but not that the graph connects it to the query. Graph-weighted reciprocal rank fusion scales each candidate's rank term by its query-candidate edge weight, dropping unsupported ones. On LitWeave, our constructed corpus of 11,359 NLP papers, Graft recovers 91% of its graph teacher's Recall@20 with no nearest-neighbour index or encoder at inference, and outperforms the graph teacher on query papers outside the corpus. It reproduces the graph's own facet labels at 0.922 precision, so every returned paper arrives labelled with the facet that surfaced it rather than an opaque score.
Italo Luis da Silva, Hanqi Yan, Yujing Wang et al.· 0 citations
This paper introduces a novel task, graph textual summarization, which aims to generate natural language descriptions that capture both the semantic content and structural characteristics of graph data based on large language models (LLMs). Unlike traditional summarization tasks for text, images, or videos, summarizing graph data presents unique challenges due to its abstract and non-intuitive nature. We develop a comprehensive benchmark construction framework and construct three diverse benchmark datasets, including text-attributed graphs (TAGs), knowledge graphs (KGs), and heterogeneous attributed graphs (HAGs). To facilitate empirical studies, we deliver three representative benchmark datasets: SurveyGraphSum, consisting of 7835 citation graphs from survey papers across 10 major domains and 56 subdomains; BookGraphSum, containing 6175 knowledge graphs extracted from 186 books; and E-comGraphSum, with 912 heterogeneous graphs from real-world e-commerce networks, each representing a fraud group with 14 node types, 19 relation types, and 9 numerical attributes related to user behavior and interactions. In addition, we propose a unified evaluation framework that assesses both linguistic quality and factual consistency, providing a comprehensive approach to evaluating generated summaries for content fidelity and accuracy. By formalizing the task, releasing benchmark datasets, and proposing an evaluation framework, we aim to advance research in graph textual summarization and promote methods that produce accurate, informative, and human-readable summaries for complex graphs.
Xiaoxuan Gou, Weiguo Zheng, Hanqing Guo et al.· Proceedings of the 32nd ACM...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
