Finding Counterfactual Evidences for Node Classification Conference: Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2; August 3–7, 2025; Toronto, ON, Canada Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD ’25), Aug
Dazhuo Qiu, Jinwen Chen, Arijit Khan, Yan Zhao, Francesco Bonchi · 2025
Read Finding Counterfactual Evidences for Node Classification Conference: Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2; August 3–7, 2025; Toronto, ON, Canada Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD ’25), Aug by Dazhuo Qiu, Jinwen Chen, Arijit Khan, Yan Zhao, Francesco Bonchi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-11396.txt.
Introduction
Dazhuo Qiu, Jinwen Chen, Arijit Khan, Yan Zhao, and Francesco Bonchi hunt for counterfactual pairs of nodes that expose how graph neural networks classify, in a paper from 2025. Two near-twin nodes that receive different labels reveal what the model truly keys on. Finding such pairs in observational data, without experiments, is the challenge.
Their search algorithms and a new index blend node features with neighborhood structure to find evidence pairs fast. The method works for any graph network, not one specific design. Tests show the pairs can audit fairness and even improve accuracy. Explanations become concrete examples rather than heat maps.
Catalog record
| CREATOR | Dazhuo Qiu, Jinwen Chen, Arijit Khan, Yan Zhao, Francesco Bonchi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-11396
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Finding Counterfactual Evidences for Node Classification Conference: Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2; August 3–7, 2025; Toronto, ON, Canada Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD ’25), August 3–7, 2025, Toronto, ON, Canada DOI: 10.1145/3711896.3736960 ISBN: 979-8-4007-1454-2/2025/08 CCS: Information systems Graph-based database models CCS: Information systems Database query processing Dazhuo Qiu, Jinwen Chen, Arijit Khan, Yan Zhao, Francesco Bonchi Abstract . Counterfactual learning is emerging as an important paradigm, rooted in causality, which promises to alleviate common issues of graph neural networks ( GNNs ), such as fairness and interpretability. However, as in many real-world application domains where conducting randomized controlled trials is impractical, one has to rely on available observational (factual) data to detect counterfactuals. In this paper, we introduce and tackle the problem of searching for counterfactual evidences for the GNN -based node classification task. A counterfactual evidence is a pair of nodes such that, regardless they exhibit great similarity both in the features and in their neighborhood subgraph structures, they are classified differently by the GNN . We develop effective and efficient search algorithms and a novel indexing solution that leverages both node features and structural information to identify counterfactual evidences, and generalizes beyond any specific GNN . Through various downstream applications, we demonstrate the potential of counterfactual evidences to enhance fairness and accuracy of GNNs . 1. Introduction Graph neural networks ( GNNs ) have demonstrated significant performance and representational capacity in solving problems over graph-structured data, fueling a great deal of applications in a variety of domains, ranging from biology to finance, from social media to neuroscience ( Wu et al. 2022 ) . In particular, among various graph machine learning tasks, GNNs have shown significant predominance over other methods in the node classification task, that is, when a unique graph is given as input with some nodes labelled and some are not, and the goal is to predict a label for each unlabeled node. Together with the demonstrated predictive performance, GNNs inherit from the wider class of deep learning methods several limitations which can hinder their adoption, especially in high-stakes application domains ( Dai et al. 2024 ) . Most noticeably, GNNs lack interpretability ( Dai and Wang 2021c ; Yuan et al. 2023 ) and tend to inherit biases present in the training datasets ( Dai and Wang 2021a ; Kose and Shen 2022 ; Dong et al. 2022 ; Wang et al. 2022 ; Dai and Wang 2023 ; Köse and Shen 2024 ; Kose and Shen 2024 ) , potentially leading to discriminatory decisions based on, e.g., gender, race, or other sensitive attributes. The latter issue derives from the fact that, exactly like every other machine learning algorithm, GNNs are trained to reflect the distribution of the training data which often contains historical bias towards sensitive attributes. If not addressed explicitly, the bias contained in the training data can end up being structured in the trained machine learning model ( Hajian et al. 2016 ) . Furthermore, the underlying graph structure and the typical message-passing mechanism of GNNs can further magnify harmful biases ( Dai and Wang 2023 ) . Counterfactual learning is emerging as a paradigm that can alleviate both fairness and interpretability issues ( Guo et al. 2025 ) . The notion of counterfactual is borrowed from causal language and it indicates the possibility of an alternative outcome if some of the premises were different from what were in reality (“counter to the facts”). For instance, in fairness testing, counterfactual examples are created by altering certain sensitive features (e.g., gender or race) of a data point to see if the model’s predictions change. Counterfactuals are also straightforward contrastive example-based explanations of the type: “You were denied a loan. If your income had been £45,000, you would have been offered a loan” ( Wachter et al. 2018 ) . A key challenge for learning causality ( Guo et al. 2021 ) is that, in order to properly determine the causal effect of an action, we need to know both the factual outcome with the observed action and the counterfactual outcome with the unobserved action. However, in many real-world settings it is impractical to conduct randomized controlled trials to get the counterfactual: When this is the case, we only have access to the observational factual data, i.e., the observed action and its corresponding factual outcome. Therefore, it is crucial to develop methods for detecting counterfactuals in the observational data , in order to take the full advantage of counterfactual reasoning in machine learning ( Pearl et al. 2016 ; Guo et al. 2021 ; Kaddour et al. 2022 ; Guo et al. 2025 ) . In this paper, we tackle the problem of searching counterfactual evidences in node classification task . In this setting, a counterfactual evidence for a node v is another node u such that, regardless they exhibit great similarity in their neighborhood subgraph, including the features, they are classified differently by the given GNN . The differences between v ’s and u ’s neighborhood subgraphs, are what define the counterfactual hypothesis for v , i.e., the small changes that would make v being classified differently. The advantage of this type of counterfactual over perturbation-based ones, is that it exists in the factual data : as such it enjoys greater realism and feasibility than counterfactuals produced by perturbation. Figure 1. (Left) The 1-hop neighborhood G of the node of interest, u97 , from German Credit dataset ( Agarwal et al. 2021 ) . Each customer has important features for classification, as shown in the table. (Center) G_{1} is a counterfactual explanation induced from G , highlighting the important parts of the input graph. (Right) u862 is the counterfactual evidence that shares similar node features and surrounding structures ( G_{2} ) with u97 , but has a different classification result. intro example Figure 1 provides a depiction of a counterfactual evidence and its difference from a counterfactual explanation ( Yuan et al. 2023 ) , extracted from the German Credit dataset ( Agarwal et al. 2021 ) . On the left, a node, u97 , is presented together with its 1-hop neighborhood structures ( G ), along with feature values for all the nodes in G . In this case, the GNN classifies u97 positively (loan approved). In the center, a counterfactual explanation for u97 is presented: this is a set of perturbations to the specific data point ( u97 ’s 1-hop neighborhood structure and features), which is sufficient to induce a change in the classification. In this example, the counterfactual explanation (subgraph G_{1} ) is obtained from the data point G by masking three out of four links: such changes would make u97 classified negatively, thus highlighting which are the most important parts of G for the prediction. Instead, a counterfactual evidence is a different node ( u862 on the right), which regardless of having great similarity in the subgraph and associated features, gets a different treatment from u97 . Besides the general importance of finding counterfactuals in the observational data (previously discussed), there are some immediate applications of graph counterfactual evidence that