Graph Counterfactual Explainable AI via Latent Space Traversal

Venue: NLDL_org_2025_Conference
Published: 2024-09-08 22:59:05

Abstract: Explaining the predictions of a deep neural network is a nontrivial task, yet high-quality explanations for predictions are often a prerequisite for practitioners to trust these models. \textit{Counterfactual explanations} aim to explain predictions by finding the ``nearest'' in-distribution alternative input whose prediction changes in a pre-specified way. However, it remains an open question how to define this nearest alternative input, whose solution depends on both the domain (e.g. images, graphs, tabular data, etc.) and the specific application considered. For graphs, this problem is complicated i) by their discrete nature, as opposed to the continuous nature of state-of-the-art graph classifiers; and ii) by the node permutation group acting on the graphs. We propose a method to generate counterfactual explanations for any differentiable black-box graph classifier, utilizing a case-specific permutation equivariant graph variational autoencoder. We generate counterfactual explanations in a continuous fashion by traversing the latent space of the autoencoder across the classification boundary of the classifier, allowing for seamless integration of discrete graph structure and continuous graph attributes. We empirically validate the approach on three graph datasets, showing that our model is consistently high performing and more robust than the baselines.

Main paper: 
 background: 
 Counterfactual explanations for graph classifiers take as input a graph and aim to return a minimally altered version of the graph whose class label has been altered. In other words, counterfactual explanations answer the question: "What is the easiest way to change the graph G to alter its classification". For these explanations to be maximally interpretable, in the sense that the factual and counterfactual graph need to be aligned, the pipeline should be permutation equivariant: If the ordering of the input graph nodes is changed, we would like the output graph nodes to be altered accordingly. In this way, any natural alignment between the input and output graphs is preserved.Counterfactual Explanations highlight essential, yet in-sample, changes in input features that affect the outcome of a predictive model, offering valuable insights into the model's decisions. Several approaches exist for tabular [9, 10] and image data [11] , as well as graph data [12, 13] . Early works introduce and address key aspects such as sparsity [14, 15] , actionability [16, 17] , diversity [18, 19] and causality [20, 21] . Recent research focuses on maintaining counterfactuals close to the data manifold, which is usually approximated with generative models such as autoencoders [22, 23] , flow- [24, 25] , and diffusion models [26] [27] [28] [29] . In the context of graphs, both model-level [30, 31] and instance-level [32, 33] counterfactual explanations have been proposed. Generating counterfactual explanations based on a VAE has previously been proposed by [33] , where a counterfactual prediction loss enables the decoder to generate counterfactual explanations. In this work, we construct instance-level explanations using a permutation equivariant graph variational autoencoder by traversing the latent space appropriately, and without explicitly introducing a loss for counterfactual Fig. 1 shows the complete counterfactual pipeline. • V ∈ R n×d V is a real-valued matrix that con-146 tains the node attributes.• A ∈ {0, 1} n×n is a Boolean matrix indicating the existence of edges, the adjacency matrix.• E ∈ R n×n×d E is a real-valued matrix that contains the edge features if they exist.Note that in this representation, n is chosen to be the same for all graphs, and graphs containing less than n nodes are zero-padded. This ensures that batching of graphs can be done during model training even if a dense graph representation is employed. Furthermore, while our experiments only consider categorical node and edge attributes, the framework extends to continuous attributes. 
invariance and equivariance to permutation: 
 Having defined the graph representation, we define how the permutation group S n of order n acts on a graph G ∈ G. Specifically for a permutation σ ∈ S n we denote the permutation matrix associated with this element as P σ . In this case, we will simply define the group action asσ • G := (P σ B, P σ V, P σ AP ⊤ σ , P σ EP ⊤ σ ). (1)That is, the rows and columns of A and E are permuted, whereas only the rows of B and V are permuted.It is widely acknowledged that predictive graph models should incorporate the notions of invariance and equivariance [41] . In the case of classification, a graph classifier should not depend on the node ordering. The graph classification model C : G → {0, 1} considered in this paper is therefore designed to be invariant, that is,C(σ • G) = C(G) for any G ∈ G and σ ∈ S n .Likewise, we design the autoencoder to be equivariant to permutation. Thus, the encoder F : G → R n and decoder D : R n → G should have the property, that for any G ∈ G:D(F(σ • G)) = σ • Ḡ for all σ ∈ S n .(EQUATIONWhere Ḡ denotes the reconstruction of G. For graph autoencoders, equivariance is crucial: We need input and output graphs to be aligned when computing the loss during training. This also applies to assessing counterfactual graph explanations.Several ways of creating equivariant layers can be considered, but for the networks in this paper, we consider a specific basic building block consisting of: A linear equivariant layer as specified by Maron et al. [39] and a non-linearity consisting of node-and edge-wise aggregations implemented as convolutions with a kernel size of one and the ReLU activation function. Batch normalization is applied before the activation. We will refer to this construction as an equivariant/invariant module depending on the applied equivariant/invariant linear layer. The linear al. [37] , Pan and Kondor [38] , and Thiede et al. [42] for further uses of this type of layer.We design a PEGVAE similar to Hansen et al. [8] .We employ a standard Gaussian prior on the latent space variable, i.e. p(z) = N (z | 0, 1), and let q ϕ (z | G) denote the approximate posterior also being Gaussian, and where ϕ refers to the parameters of the encoder as is custom when dealing with VAEs. Specifically, we factorize the likelihood p θ (G | z) as:EQUATIONwhere θ = {θ B , θ V , θ A , θ E } refers to the parameters of the decoder. Thus, when sampling a new graph from p(G), we first sample the prior p(z), then p(B | z), etc., until a graph has been obtained. This factorization makes it easier to sample valid graphs than if p(G | z) were modeled directly: We can constrain edges to be sampled between nodes that exist, and assign classes only to nodes and edges that exist. We now minimize the negative evidence lower bound (ELBO), which is given by, i.e.:EQUATIONwhere KL( • ∥ • ) denotes the Kullback-Leibler divergence. Here, the negative log-likelihood works as a reconstruction loss, and the KL-loss works as regularization. Since the prior is Gaussian with mean zero, and thus has a symmetric density, the node ordering will not affect the size of this term. In practice, we tune the KL-loss with a hyperparameter β ∈ [0, 1] [43] by optimizing,E z∼q ϕ (z|G) [-log p θ (G | z)]+β•KL(q ϕ (z | G) ∥ p(z)).The exact architecture of the permutation equiv-234 ariant VAE as well as any hyperparameters used 235 during training can be found in Appendix A.1.2.As the PEGVAE is permutation equivariant, the 238 graph classifier C : G → {0, 1} is designed to be 239 permutation invariant as the prediction should not 240 be affected by node ordering. Following Bronstein 241 et al. [41] , this feature is obtained by composing a 242 number of equivariant layers followed by an invariant 243 global pooling layer. The output of this global pool-244 ing layer can be viewed as a graph embedding, which 245 is passed to a fully connected neural network to ob-246 tain probabilistic class predictions. The architecture 247 of the classifier, as well as the hyperparameters used 248 during training, can be found in Appendix A.1.1.Latent Space TraversalGiven a factual graph G F we generate counterfactual 252 explanations for the class prediction. First, a latent 253 encoding z F of G F is found by evaluating F(G F ). 254 Secondly, a counterfactual graph G CF is generated 255 by iterative updates using gradient descent with a 256 learning rate of ϵ > 0, defined as: can be made to batches of counterfactuals by using 298 a mask. This ensures that after the desired label has been achieved, then no more updates will be done to the latent code. Also note, that to ensure that the algorithm does terminate it runs for N ∈ N steps, and not until the classifier assigns the desired label to the generated graph.EQUATIONInput: G F and N ≥ 0 Output: G CF z 0 ← F(G F ); y D ← 1 -y F ; i ← 1; while i ≤ N do G CF i ← D(z i ); y i ← C(G CF i ); if y i = y D then mask ← 0; else mask ← 1; end z i+1 ← z i -ϵ • ∇L(z i , y D ) • mask; i ← i + 1; end G CF ← G CF N ; return G CF 
data: 
 We evaluate our method using three molecular graph datasets: NCI1 [45] , Mutagenicity [46] [47] [48] and AIDS [47, 49] , where graph nodes represent atoms and edges represent bonds. Each dataset poses a binary classification task: Whether the molecule is active against HIV or not (AIDS), whether it is mutagenic or not (Mutagenicity), and whether the molecule is anticancer (NCI1). We follow the graph pre-processing and filtering of Huang et al. [50] , including only molecules with nodes occurring with a frequency larger than 50 in the dataset to avoid imbalance. Furthermore, as our architecture relies on a dense graph representation, we only consider graphs with fewer than 50 nodes (Mutagenicity, NCI1) and 30 nodes (AIDS). Each dataset is divided into training, validation, and test sets, with 10% allocated to test and validation. Additional information can be found in Tab. A.1 in Appendix A.The counterfactuals quality of the counterfactuals are evaluated as a trade-off between identity preservation, i.e, the degree to which the generated counterfactual graph resembles the factual graph, and validity, i.e, whether the generated counterfactual is indeed a valid candidate for the desired class.Identity Preservation. Three identity preservation measures are used. Graph Edit Distance (GED), measures the graph distance between factual and counterfactual graphs. Latent Euclidean Distance (LED) refers to the Euclidean distance between the latent representation of two graphs. Cosine Similarity (CS) is computed between the graph embeddings extracted from the classifier.Validity. Two validity measures are used. Flip-Ratio (FR) refers to the number proportion of generated counterfactual explanations, which are assigned the desired class by the classifier. On top of that, we measure the Signed Increase in Confidence (SIC), referring to the increase or decrease classifier's confidence for the desired class. Specifically, we compute p d CF -p d F , where p d CF , p d F ∈ [0, 1] are classifier's output, that the generated factual and counterfactual graphs belong to the desired class. We include several baseline counterfactual methods.First, counterfactual explanations can be generated naively by decoding random samples from p(z). We refer to this method as Random. That is, we first sample from the prior p(z) and subsequently from As this work is preliminary, and since we investigate whether it is viable to generate counterfactual explanations based on traversal of a latent space of a VAE without having to explicitly train it for generating counterfactual explanations, all the methods used for comparison are based on the generating counterfactuals from the latent space of the same VAE. We will refer to the method outlined in Section 2.5 as Classifier Guided Counterfactuals (CGCF). Source code for running each baseline will be publicly available at http://ANON-REPO-URL/.Tab. we also see, that this method consistently performs 399 poorly in terms of validity, underscoring the fact 400 that a trade-off is present, and the evaluation of the 401 method based on the table alone is not sufficient.Fig. 2 depicts the trade-off between identity preser-403 vation (columns) and validity (rows) for each dataset. 404 The curve is constructed by computing the aver-405 age validity score from all samples with an identity 406 preservation score below a certain threshold, given 407 by the x-axis. Note that we only compute the av-408 erage after having made 10 observations with the 409 validity below the threshold given by the x-axis be-410 fore we compute an average to remove noise. In the 411 case of the Flip-Ratio this can be interpreted as an 412 estimate for the probability of the counterfactual 413 graph having successfully flipped the class of its 414 factual graph, given that the level of identity preser-415 vation is below a certain threshold. We observe that 416 the classifier-guided counterfactuals achieve trade-417 offs competitive with all baselines, and outperform 418 on NCI1 and Mutagenicity. One should note, that to 419 make the interpretation of the plots the same (high 420 values being desirable, and low values being undesire-421 able) we consider the negative cosine similarity. The 422 histograms of Fig. 2 show the distribution of identity 423 preservation scores of the generated counterfactuals 424 for each score. On AIDS, the Decoded Mean of k-NN and CGCF 428 achieve good validity scores, as well as good trade-429 offs between identity preservation and validity. How-430 ever, only the CGCF proves to be robust across all 431 datasets considered here. It For the PEGVAE trained on the Aids dataset a learning rate of 0.001 was used, along a learning rate scheduler configured to halfing the learning rate if the validation loss had not improved for 150 epochs. In total training ran for 2000 epochs. For the tradeoff between the KL-loss and the reconstruction loss β = 0.1 was chosen. Additionally, to avoid posterior collapse, the β was increased gradually during a burn-in period. For the NCI1 and Mutagenicity datasets a similar training setup was employed with the sole change that we set β = 0.5.G CF = arg min G dist(G, G F ) such that C(G F ) ̸ = C(G) = y D forFor the Classifier Guided CF method optimization was done using an Adam optimizer with a learning rate of 0.05 for 1 000 iterations and λ = 1 used for regularization. The hyperparameter τ used for the Gumbel-Softmax was also set to 1. This parameter determines how close an approximation the Gumbel-Softmax is to the desired discrete, categorical distribution as opposed to a uniform distribution assigning equal probability mass to all classes. For the Decoded Mean of k-NN method, we choose k = 10.  
: 
 sentation. Guided by the classifier, we traverse this latent space to obtain graphs that are semantically similar to the input graph but whose prediction has been altered in a predetermined way. This allows us to answer questions such as "How do we most easily alter a given chemical molecule to improve a specific chemical property?" or "How should a given social network change to reduce its fraud risk score?". We evaluate our approach on three commonly used datasets of molecular graphs. 
 
 Appendix:  


Decision: The authors propose a method to generate counterfactual examples of GNN decisions by pushing the output to cross the decision boundary line. Nevertheless, the reviewers and the authors qualify the results as preliminary as the method could be improved.

I, therefore, recommend accepting the paper for a poster session.

Reviews: review: title: title: Clear approach to counterfactual explanations for graph classifiers
paper_summary: paper_summary: This paper presents a method that produces counterfactual explanations for graph classifiers. At the core of the method, there is a VAE, which allows the authors to avoid the tricky problem of defining a distance on the space of graphs by moving into VAE's latent space instead.
main_review: main_review: My rating was positive even before the rebuttal phase, when some of my concerns were addressed. I see that other weaknesses, pointed out by other reviewers, were also addressed. So I confirm my initial rating.
strength_weakness: strength_weakness: **Clarity**:
- I would recommend to the authors to take the opportunity of this review to fix a few typos. There are not many and they don't affect the overall comprehensibility. I'll make a couple of examples here. Sometimes the latent variable $z$ is written in bold (see eq. 4), sometimes it's not (see section 2.5). Lines 265, 267 and 270 have extra parentheses.
- There are some parts of the paper that could be a bit clearer, maybe you can make use of the extra page to expand and clarify them. 
  - In line 046 you talk about "*dataset-specific* permutations equivariant GVAE", but it's not clear to me what makes it dataset-specific. 
  - In line 064 you talk about the necessity for explanations to be "maximally interpretable", without specifying what that means. 
  - You introduce the difference between equivariance and invariance quite early in the paper (lines 96-98), maybe you could specify that you will explain it better in section 2.2.
  - In line 099 it's not clear to me the difference between graph level and population level embeddings, and how that impacts the equivariance of the representation.
  - As a topological distance, you use the graph edit distance. Any reason why you use this specific one instead of others?
  - It's a bit unclear to me what the Signed Increase in Confidence is. Maybe you could expand it a bit better?
- The readability of table 1 could be improved, for example:
  - by introducing acronyms for the metrics, so that you can increase the font size;
  - by using bold numbers also in the part related to the fidelity to indicate the best-performing methods.
- The readability of figure 2 could be improved, for example:
  - by making them larger;
  - introducing the acronyms (GED is not explicitly defined in the text);
  - "Mean Absolute Difference" is not defined within the text and "Latent Cossimilarity" has a different name in text;
  - maybe you could show only one dataset with larger figures, and move the others in the appendix?
  - how should the histograms be interpreted?
- Since the very beginning of the paper I was expecting to see some factual and counterfactual graphs plotted somewhere. It's good to have numbers and metrics, but maybe one example could help ground the discussion.
- You mention that Nearest Neighbor counterfactuals have low validity because they will be *often* misclassified by the classifier. I understand that it can happen, but why does it happen often?

**Reproducibility**

The method and the architectures employed are described in quite detail, but I think it's necessary to have a link to the GitHub repository. Unless it was removed for anonymity, I strongly recommend adding it.

**Incremental contributions**

Could you maybe clarify how does your work relate with the one of [1]?

[1] Ma, Jing, et al. "Clear: Generative counterfactual explanations on graphs." Advances in neural information processing systems 35 (2022): 25895-25907.
title: title: This paper presents several intriguing ideas but my current assessment is just below the acceptance threshold.
paper_summary: paper_summary: This paper presents several intriguing ideas. Firstly, it introduces a generative modeling method called PEGVAE, which utilizes VAE for graph instances. Unlike image instances, graph instances require a guarantee of permutation invariance during the learning process. This aspect, which has not been considered in traditional image-based VAEs, is likely to engage readers' interest. The authors effectively detail this novel framework in sections 1.Introduction and 2.1-2.2.

Secondly, the paper proposes an innovative approach for iteratively identifying counterfactual latent representations by utilizing gradients derived from a classifier when input graphs are classified. The quality of the discovered counterfactuals is evaluated using two explainability principles: fidelity and validity.
main_review: main_review: Thank you for your efforts in addressing my questions. Your response is comprehensive and I would like to change my decision to accept this paper for NLDL 2025. Please ensure that the answer regarding the first inquiry, which relates to point 2 in my initial comments, is included in the camera-ready version.
strength_weakness: strength_weakness: Points to improve:

1. Syntax errors and typos: The manuscript contains numerous syntax errors and typographical mistakes. I urge the authors to thoroughly proofread the entire document to improve clarity. Some errors I noted include:
L175: \rightarrow should be \leftarrow
L197: Appendix B is missing
L199: N(0|1) should be N(0, 1)
L204: Eq. (3): p(E|B,V,E) should be p(E|B,V,A)

2. Algorithmic representation of the process: Including an algorithmic representation of the process would greatly enhance readers' understanding. Currently, the method by which the PEGVAE-classifier is trained (whether end-to-end or separately) and how counterfactual samples are identified for specific instances is not clearly delineated. Additionally, the batching of graphs should be included in the algorithmic description.

3. Discussion section: The discussion is somewhat lacking. It would be beneficial to explore whether graph instances belonging to the same class exhibit similar counterfactuals. Moreover, if latent features are altered using gradients obtained from intentionally misclassified instances within a pre-trained PEGVAE-Classifier setup, what would the reconstructed graphs look like? Addressing these questions would add depth to the analysis.

4. Quality of counterfactual explanations: On L406, the statement that "generative models do not guarantee quality counterfactual explanations" raises a question about whether PEGVAE falls into this category as well. This remark could diminish the persuasive power of the paper. Instead, I recommend visualizing the generated graph samples and including a more detailed examination and analysis of the contexts in which they are produced. If further experiments are conducted in the meantime, it would be beneficial to include those results during this review process.
title: title: preliminary but sensible contribution
paper_summary: paper_summary: The paper introduces a pipeline for generating (in-distribution) counterfactual
explanations of GNN decisions.  An equivariant generative graph model is used
for the purpose.  Specifically, the idea is to model a generative distribution
over in-distribution graphs as a VAE;  the output of this VAE is fed to the
classifier;  a counterfactual is computed by traversing the latent space (via
gradient ascent/descent) in a direction that crosses the decision boundary.
An empirical evaluation is carried out against three simple but reasonable
baselines on three data sets.
main_review: main_review: I was quite positive about the paper to begin with, and the rebuttal has managed to clarify the few issues I had pointed out.
strength_weakness: strength_weakness: - There already exist works for generating counterfactuals that rely on
generative models in the context of non-relational data.  It would make sense to
mention a couple, and to explain that for graphs the problem is more challenging
due to equivariance etc.

- Section 2.1: it would have helped to provide a basic intuition behind the
layers by Maron et al.

- The notion of "fidelity" (aka "faithfulness" in the literature) normally
  refers to the degree by which an explanation is faithful to the reasoning
  process of a model, see for instance [1].  I would refrain from using the same
  name for a different quantity: it is confusing.

- The choice of competitors is limited and the experiments are run using a single
  GNN model; hinting at the fact that this is an
  (understandably) preliminary work.

- In a similar vein, it would make sense to discuss the direct competitors more
  in details and compare (both conceptually and empirically) against them.


**Suggestions**:

- Please name your method.  It makes it easier to reference it in future work.
  You can also use it in the plots to make it easier to identify your proposed
  approach (the dark blue bar).

- Using $\mathcal{C}$ for the GNN classifier and $\mathcal{F}-\mathcal{D}$ for
the encoder-decoder is a bit odd - calligraphic math symbols are normally used
for denoting sets (as you do for the set of graphs).

- For conditional distribution, consider using $\mid$ instead of $|$.

- Figure 1 should probably be in page 2 (because it helps to figure out what
  latent space is being traversed.)

[1] Agarwal, C., Zitnik, M., & Lakkaraju, H. (2022, May). Probing gnn explainers: A rigorous theoretical and empirical analysis of gnn explanation methods. In International Conference on Artificial Intelligence and Statistics (pp. 8969-8996). PMLR.

- The description of the classifier should probably be an experimental detail,
  while it currently resides in the Method section.

- What is the reason for reporting the distance in latent space?  Does it matter
for practical purposes?