Finding Counterfactual Evidences for Node Classification

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.

Accepted by KDD 2025

References in corpus (8)

• A Comprehensive Survey on Graph Neural Networks
• Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks
• Learning and Evaluating Graph Neural Network Explanations based on Counterfactual and Factual Reasoning
• A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability
• Multilevel Graph Matching Networks for Deep Graph Similarity Learning
• Robust Counterfactual Explanations on Graph Neural Networks
• View-based Explanations for Graph Neural Networks
• Counterfactual Learning on Graphs: A Survey