Game-theoretic Counterfactual Explanation for Graph Neural Networks

• URL: http://arxiv.org/abs/2402.06030v1
• Date: Thu, 8 Feb 2024 20:07:43 GMT
• Title: Game-theoretic Counterfactual Explanation for Graph Neural Networks
• Authors: Chirag Chhablani, Sarthak Jain, Akshay Channesh, Ian A. Kash, Sourav Medya
• Abstract summary: Graph Neural Networks (GNNs) have been a powerful tool for node classification tasks in complex networks. Counterfactual explanations (CFE) have shown promise in enhancing the interpretability of machine learning models. We propose a semivalue-based, non-learning approach to generate CFE for node classification tasks.
• Score: 13.583604117327697
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Graph Neural Networks (GNNs) have been a powerful tool for node classification tasks in complex networks. However, their decision-making processes remain a black-box to users, making it challenging to understand the reasoning behind their predictions. Counterfactual explanations (CFE) have shown promise in enhancing the interpretability of machine learning models. Prior approaches to compute CFE for GNNS often are learning-based approaches that require training additional graphs. In this paper, we propose a semivalue-based, non-learning approach to generate CFE for node classification tasks, eliminating the need for any additional training. Our results reveals that computing Banzhaf values requires lower sample complexity in identifying the counterfactual explanations compared to other popular methods such as computing Shapley values. Our empirical evidence indicates computing Banzhaf values can achieve up to a fourfold speed up compared to Shapley values. We also design a thresholding method for computing Banzhaf values and show theoretical and empirical results on its robustness in noisy environments, making it superior to Shapley values. Furthermore, the thresholded Banzhaf values are shown to enhance efficiency without compromising the quality (i.e., fidelity) in the explanations in three popular graph datasets.

Related papers

• BAED: a New Paradigm for Few-shot Graph Learning with Explanation in the Loop [14.41672697491523]
  Few-Shot Graph Learning (FSGL) approaches have been developed over the years.<n>This paper introduces the first explanation-in-the-loop framework for the FSGL problem, called BAED.
  arXiv  Detail & Related papers  (2026-03-02T14:56:39Z)
• QGShap: Quantum Acceleration for Faithful GNN Explanations [0.48998185508205744]
  We introduce QGShap, a quantum computing approach that leverages amplitude amplification to achieve quadratic speedups in coalition evaluation.<n>Unlike classical sampling or surrogate methods, our approach provides fully faithful explanations without approximation trade-offs for tractable graph sizes.
  arXiv  Detail & Related papers  (2025-12-01T16:19:15Z)
• BetaExplainer: A Probabilistic Method to Explain Graph Neural Networks [1.798554018133928]
  Graph neural networks (GNNs) are powerful tools for conducting inference on graph data. Many interpretable GNN methods exist, but they cannot quantify uncertainty in edge weights. We proposed BetaExplainer which addresses these issues by using a sparsity-inducing prior to mask unimportant edges.
  arXiv  Detail & Related papers  (2024-12-16T16:45:26Z)
• Interpretable Graph Neural Networks for Heterogeneous Tabular Data [2.8084422332394423]
  IGNH handles both categorical and numerical features, while constraining the learning process to generate exact feature attributions. A large-scale empirical investigation is presented, showing that the feature attributions provided by IGNH align with Shapley values that are computed post hoc.
  arXiv  Detail & Related papers  (2024-08-14T16:49:25Z)
• Fast and Simple Explainability for Point Cloud Networks [4.013156524547072]
  We propose a fast and simple explainable AI (XAI) method for point cloud data. It computes pointwise importance with respect to a trained network downstream task.
  arXiv  Detail & Related papers  (2024-03-12T14:51:23Z)
• Chasing Fairness in Graphs: A GNN Architecture Perspective [73.43111851492593]
  We propose textsfFair textsfMessage textsfPassing (FMP) designed within a unified optimization framework for graph neural networks (GNNs) In FMP, the aggregation is first adopted to utilize neighbors' information and then the bias mitigation step explicitly pushes demographic group node presentation centers together. Experiments on node classification tasks demonstrate that the proposed FMP outperforms several baselines in terms of fairness and accuracy on three real-world datasets.
  arXiv  Detail & Related papers  (2023-12-19T18:00:15Z)
• Interpretable Graph Neural Networks for Tabular Data [18.30325076881234]
  IGNNet constrains the learning algorithm to produce an interpretable model. A large-scale empirical investigation is presented, showing that IGNNet is performing on par with state-of-the-art machine-learning algorithms.
  arXiv  Detail & Related papers  (2023-08-17T12:35:02Z)
• Look beyond labels: Incorporating functional summary information in Bayesian neural networks [11.874130244353253]
  We present a simple approach to incorporate summary information about the predicted probability. The available summary information is incorporated as augmented data and modeled with a Dirichlet process. We show how the method can inform the model about task difficulty or class imbalance.
  arXiv  Detail & Related papers  (2022-07-04T07:06:45Z)
• FlowX: Towards Explainable Graph Neural Networks via Message Flows [59.025023020402365]
  We investigate the explainability of graph neural networks (GNNs) as a step toward elucidating their working mechanisms. We propose a novel method here, known as FlowX, to explain GNNs by identifying important message flows. We then propose an information-controlled learning algorithm to train flow scores toward diverse explanation targets.
  arXiv  Detail & Related papers  (2022-06-26T22:48:15Z)
• Invertible Neural Networks for Graph Prediction [22.140275054568985]
  In this work, we address conditional generation using deep invertible neural networks. We adopt an end-to-end training approach since our objective is to address prediction and generation in the forward and backward processes at once.
  arXiv  Detail & Related papers  (2022-06-02T17:28:33Z)
• Bayesian Graph Contrastive Learning [55.36652660268726]
  We propose a novel perspective of graph contrastive learning methods showing random augmentations leads to encoders. Our proposed method represents each node by a distribution in the latent space in contrast to existing techniques which embed each node to a deterministic vector. We show a considerable improvement in performance compared to existing state-of-the-art methods on several benchmark datasets.
  arXiv  Detail & Related papers  (2021-12-15T01:45:32Z)
• Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking [63.49779304362376]
  Graph neural networks (GNNs) have become a popular approach to integrating structural inductive biases into NLP models. We introduce a post-hoc method for interpreting the predictions of GNNs which identifies unnecessary edges. We show that we can drop a large proportion of edges without deteriorating the performance of the model.
  arXiv  Detail & Related papers  (2020-10-01T17:51:19Z)
• Diversity inducing Information Bottleneck in Model Ensembles [73.80615604822435]
  In this paper, we target the problem of generating effective ensembles of neural networks by encouraging diversity in prediction. We explicitly optimize a diversity inducing adversarial loss for learning latent variables and thereby obtain diversity in the output predictions necessary for modeling multi-modal data. Compared to the most competitive baselines, we show significant improvements in classification accuracy, under a shift in the data distribution.
  arXiv  Detail & Related papers  (2020-03-10T03:10:41Z)
• Learning to Hash with Graph Neural Networks for Recommender Systems [103.82479899868191]
  Graph representation learning has attracted much attention in supporting high quality candidate search at scale. Despite its effectiveness in learning embedding vectors for objects in the user-item interaction network, the computational costs to infer users' preferences in continuous embedding space are tremendous. We propose a simple yet effective discrete representation learning framework to jointly learn continuous and discrete codes.
  arXiv  Detail & Related papers  (2020-03-04T06:59:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.