Graph Inverse Style Transfer for Counterfactual Explainability

We thank you for the effort made to review our paper, and for the nice score you chose to give it. Thank you for pointing out RCExplainer [2].

W1: Missed Bajaj reference: We were aware of the paper, and decided to reviewed RCExplainer again to see whether we were missing something or not. We cross-validated it with what described in [1] specifically in Table 2 (page 12). As per [1], we confirm that it is a heuristic + learned-based method.

In our related work section, we specifically stated that we concentrate on only learning-based and generative methods, hence the choice of the methods we compared against. However, we see the value of RCExplainer with its multiple learnt linear decision boundaries and then the search over these boundaries to find robust explainers, and will include it in our related work at camera ready.

Unfortunately, the official code doesn't run (the authors load some Huawei third party python packages that aren't available anywhere) even after debugging and trying to port it to the GRETEL framework to have the same evaluation pipeline. Then, we also tried to run an unofficial code repository at https://github.com/idea-iitd/gnn-x-bench/blob/main/source/rcexplainer.py (we are not the authors so anonymity isn't breached if you want to take a look), however, the code doesn't support BBBP, BZR, ENZYMES, MSRC21, and COLORS-3 datasets. It's fine that it doesn't support COLORS-3 since this is multiclass and RCExplainer only does binary classification. However, not supporting the other listed datasets hinders us to compare it against other SoTA and GIST.

I believe a good compromise here is to recognize RCExplainer's validity as a heuristic+learned counterfactual explainer and list it in our related work section and highlight the fact that we only treat pure learned-based approaches. What do you think?

Q1: Where are MUTAG and NCI1?: We excluded all those datasets from TUDataset (https://chrsmrrs.github.io/datasets/docs/datasets/) that do not have any node attributes. As per GNNs message passing mechanism, the nodes share their feature vectors with their neighbors, hence then having meaningful embeddings. Given a graph $G=(X,A)$, GIST overshoots to $G^e=(X^e,A^e)$ whose node features $X^e$ go through TransConv layers. If $X^e$ are missing, then the conv. layer doesn't produce anything meaningful to then estimate the edge probabilities (see Fig. 2). To surpass this hurdle, we added 7 features regarding centralities: node degree, betweeness, closeness, harmonic centrality, clustering coefficient, Katz centrality, Laplacian centrality. In this way, at least we have something interesting to work with and not rely only on the topology of the graphs. Here are the performance against SoTA in terms of validity and fidelity on 5-fold cross-validations where the oracle $\Phi$ is a 3-layer GCN with test accuracy of 86.8% for MUTAG. Unfortunately, even after hypeparam optimization was done on NCI1 with the introduced node features, any kind of GCN (with any layer) and UGFormer [3] with the hyperparameter search space introduced in the original paper do not reach more than 40% of accuracy in the test set. We ran experiments with these oracles for NCI1, however the fidelity of the explainers was negative, which suggests that the explainers are actually doing adversarial attacks rather than explanations on the oracle [1]. Hence, we decided to discard NCI1 and show only MUTAG. We want to point out that these two datasets aren't suitable for benchmarking purposes since, again, message passing mechanisms in GNNs rely on node feature aggregations on the neighbors. These two datasets don't have node features, and we are a bit puzzled how SoTA methods used them to compare against each other.

[1] Prado-Romero et al. A Survey on Graph Counterfactual Explanations: Definitions, Methods, Evaluation, and Research Challenges. ACM CSUR 2024.

[2] Bajaj et al. Robust counterfactual explanations on graph neural networks. NeurIPS'21

[3] Nguyen et al. Universal graph transformer self-attention networks.WWW'22

We thank you for the effort made to review GIST. It's unfortunate you didn't see its value during your original review. With the following, we tackle the weaknesses you mentioned, and hope to convince you of the paper's value.

W1: Intermediate graph $G^e$, and improved accuracy: $G^e$ is obtained by overshooting the decision boundary of the oracle $\Phi$. This process is described in Sec. B and is referenced in Sec. 4. To reiterate, we take the dataset and divide the instances into sets containing of the same class according to $\Phi$. Then, for each input $G$ with label $y = \Phi(G)$, we take all the sets whose label isn't $y$, unify and shuffle them. Lastly, we pick the first instance from this shuffled set, and that's $G^e$. This simple yet effective mechanism guarantees the counterfactual begins from the correct region (i.e., $G^e$ is already on the other side of $\Phi$'s boundary w.r.t. the input $G$). As a consequence, if we don't use the backtracking mechanism, and just return $G^e$ as the counterfactual, we'd have validity (aka explanation accuracy) equal to 1. However, $G^e$ might be far from $G$, and we don't want that. That's why GIST walks back towards $G$ and minimizes the spectral difference (Fig 8 for Graph Edit Distance). By going back, GIST needs to learn not to recross $\Phi$'s boundary and get an invalid counterfactual produced, however this might happen due to poor boundary definition. We will acknowledge this limitation and make what mentioned above clearer at camera ready by allocating space via shrinking Sec. 5.3 as per XATo.

W3: Node embeddings: I don't understand completely; I'll try my best here. Fig. 2 shows our architecture that takes in input a graph $G=(X \in \mathbb{R}^{n\times d},A)$ which is overshot to $G^e = (X^e \in \mathbb{R}^{n \times d},A^e)$. $X^e$ get then fed to the TransConv layers that project them to a latent space $\hat{X}^e \in \mathbb{R}^\ell$. The latent features are only used to estimate edge probabilities for the counterfactual candidate $G^*$. What I think you meant is whether the node embeddings in $\mathbb{R}^\ell$ are then injected on the nodes of the selected incident edges via the Gumbel + Bernoulli sampling. The short answer is "no". Thus, one can't trace how the embeddings are "transformed". However, a simple fix would do the trick: when we have $\hat{X}^e$, we can add a decoder network $h: \mathbb{R}^\ell → \mathbb{R}^d$ - e.g., learned GCN - to map the embeddings back to the input space, and train this network jointly with Eq. 12 by summing, for instance, $|X-g(\hat{X}^e)|_1$. In this way, we can see which embeddings contribute to the lowest difference (a desideratum of counterfactuality [1]) between $X$ and $g(\hat{X}^e)$. By doing this, we obtain a sparsity ↓ (Sec. E) as follows for org. GIST (up) and GIST with the embedding decoder (down). If you think this is valuable, we can add it at camera ready, in the appendix.

W4: Community & IMDB-M: Community was synthetically ad-hoc generated in CLEAR. This is why we can't reproduce the same dataset as in that paper. So, we opted to choose TreeCycles and BAShapes to cover RSGG-CE [2] and CF-GNNExp. [3] which were already supported in the GRETEL framework [4]. The results for IMDB-M on 5-fold cross-validations are here. Note that we ran CLEAR from scratch and the reported validity (0.45) isn't the one reported in the original paper (0.96). GIST is the best in terms of validity and fidelity w.r.t. a 3-layer GCN whose test accuracy is 48%. Here, we are using the version of GIST without node embeddings for consistency with what reported for the other datasets in the paper (Sec. G.2).

iRand doesn't produce any valid counterfactuals, hence its fidelity cannot be measured. Also, all the methods have a low fidelity due to the oracle's "horrible" classification skills. We tried UGFormer [5], as the best SoTA in IMDB-M, however we got a test accuracy of 33% with the same hyperparams as in the original paper, instead of the reported 89.2% on paperswithcode.

[1] Wachter et al. Counterfactual explanations without opening the black box: Automated decisions and the GDPR.

[2] Prado-Romero et al. Robust stochastic graph generator for counterfactual explanations.AAAI'24

[3] Lucic et al. Cf-gnnexplainer: Counterfactual explanations for graph neural networks.AISTATS'22

[4] Prado-Romero & Stilo. Gretel: Graph counterfactual explanation evaluation framework.CIKM'22

[5] Nguyen et al. Universal graph transformer self-attention networks.WWW'22

Oh, this is awesome. Thanks for reading the paper and not using an LLM to generate your review :-)

Your suggestions will better our paper. The proofs will be much shorter and clarifications on counterfactuality more thorough. Sec. 5.3 contains the two most important evaluation metrics as per [1]. We'll put the GED (now in Sec.G.1) in the main paper.

Just interpolation; no insights for counterfactuals: While the literature advocates for "hard-core" generative models, GIST learns to backtrack from a dataset example $G^e$ toward $G$. We agree that the main contribution is interpolation, but, it's applicability is suitable for counterfactuality as shown in the experiments. Interpolating $G$ and $G^e$ guarantees $G^*$ is in-distribution, which promotes plausability [2]. We'll clarify this better at camera ready, and measure plausability.

Why Laplacian?: Laplacians capture global structural patterns, e.g., connectivity and symmetry, that are largely invariant to specific node identities. This follows a similar rationale to neural style transfer in images, where Gram matrices of feature activations are used to model style since they encode correlation patterns among features rather than spatial arrangements. Additionally, using the Laplacian aligns with prior work in spectral graph theory, where the eigenvalues and eigenvectors of the Laplacian are shown to be robust descriptors of global structure, and have been used in graph matching [3] and generation [4].

Eq. 50?: $Q: \mathcal{G}\times \Phi→\mathcal{G}$ (we missed this). We put $\arg \min$ to emulate a for-loop on $U$. This means we take the first $G^e \in U$. In hindsight this is also confusing to us. We'll change it to $k^*=\min [ k\in[1,n]|\Phi(G)\neq \Phi(G_k) ]\; \forall G_k \in U$, and $G^e = G_{k^*}$

Similarity metric, objective func and GED: By using $G$ as a pulling factor governed by $\alpha$ to produce $G^*$, the similarity is already addressed in the objective although not explicitly as in the desideratum in [2]. In principle, the more $G^*$ goes toward $G$, the lower the edit distance should be, as well as the validity (Fig. 3). We do report GED (Fig. 8, Tab 5-12): GIST is better than CF-GNNExp (our main competitor in validity), though it's not the best across the board due to our choice of $\alpha = 0.9$. Lower $\alpha$ would improve similarity at the cost of validity, a trade-off we make explicit.

SoTA hyperparams: We used the hyperparams reported in their original papers. We can optimize them for validity, but this would require months of optimizations. We can optimize them for one dataset (e.g., BAShapes) and use the same for the rest. Do you think this is a good compromise?

Sec. 5.2 and $\alpha=1$: We aim to balance validity and similarity. Setting $\alpha=1$ would ignore the counterfactual signal, leading to perfect validity but poor GED, as $\mathcal{L}_{style}$​ becomes zero, and no learning (backtracking) is happening. Our formulation indirectly encourages similarity through $\alpha$, which controls how much $G$ influences $G^*$. The analysis in Sec. 5.2 is necessary to demonstrate how this trade-off affects GED, even if it's not an explicit loss term.

Fig. 4: The zeros are indeed paddings to compute the spectral differences, which need the adj and degree matrices to be of same dimensions. To account for different graph sizes, we could use the Wasserstein distance of the eigenvalues instead of L1. This would need further theoretical investigation. We'll clarify this in the figure's caption.

Spectral analysis for $\alpha=0.5$: Your intuition is right; when $\alpha=0.5$, GIST struggles between preserving content and matching style. We computed the frobenius norms (expected vs. produced) as in Fig. 6 for $\alpha=0.5$ on AIDS and get an error of 0.537, two orders higher than with $\alpha=0.9$. We also emulate Fig. 5 with $\alpha=0.5$ and obtain an error of 0.013 instead of 0.005 as with $\alpha=0.9$. Lastly, for Fig. 4 we have an error of 0.043 instead of $2.051\times10^{-3}$. Unfortunately, we can't show images here, but we'll include this analysis in the appendix, and mention it in a new limitation section.

Switch content and style: Taking style from $G^e$ and content from $G$ would attempt to generate a graph structurally similar to a perturbed counterfactual but semantically identical to the original, which defeats the purpose of generating counterfactuals, since semanticity usually drives $\Phi$'s prediction. GIST is designed to minimally deviate from $G$ structurally, but still flip the class as in $G^e$.

[1] Prado-Romero et al. A survey on graph counterfactual explanations: definitions, methods, evaluation, and research challenges.CSUR'23

[2] Guidotti.Counterfactual explanations and how to find them: literature review and benchmarking.

[3] Yan et al. A short survey of recent advances in graph matching.ICMR'16

[4] Dwivedi et al. Benchmarking Graph Neural Networks.JMLR'23

We thank you for the effort made to review our paper, and for the nice score you chose to give it. With the following, we hope to answer your questions, and convince you of the value of GIST.

W2: Specific user studies. We want to point out that the scope of this paper was not to involve users (in fact, none of them are present in the paper) in assessing the goodness of the produced counterfactuals since graph counterfactuals can be quite complicated to illustrate, especially when many edges/nodes are being added/removed from the original instance (see W1 for a proposal of qualitative analysis).

W1: Detailed analysis of GIST vs. SoTA beyond numerical results. As per [3] - the most-up-to-date survey in graph counterfactuality - all methods, besides those designed specifically for molecule explanations where illustrations are possible and very clean visually, use the quantitative metrics we used (see Sec. E & G.2). However, we found in the literature (e.g., [1,2] seem to be consistent in styling) an interesting and visually-pleasing way to show the differences between the original instance and counterfactual produced by illustrating their adjacency matrices. We will extend this way of visualizing also for node feature perturbations since GIST supports this mechanism, differently from the abovecited papers. We believe this would add value to the quantitative measures we provided in the paper, and would appreciate your input in this regard.

Q1: How scalable is GIST in large-scale real-world graphs?

In Sec. F, we have a time complexity analysis that treats both densely- and sparsely-memorized graphs. To reiterate, since GIST needs to find an eigenvalue decomposition to compute the Laplacian, for dense graphs we have a complexity of $\mathcal{O}(n^3)$ where $n$ is the number of nodes in a graph, and for sparse graphs it amounts to $\mathcal{O}(k(n+m))$ where $m$ is the number of edges and $k$ is the number of eigenvalues to find. Since $k$ is a constant, then this amounts to $\mathcal{O}(n+m)$. Since our implementation uses sparsely-memorized graphs, and from Table 3 in Sec. D you can see that most graphs are sparse anyway ($m<<n^2$ on avg), the execution time is linear on the number of nodes $n$ and edges $m$. Thus, scaling GIST to huge graphs is not expensive, even in real-world graphs that are generally sparse.

Q2: GIST vs. causal-based explainers: To the best of our knowledge, only CLEAR [4] is a causal-based explainer. We included it on our experiments and GIST consistently performs better across the board in validity (Tab. 1) and fidelity (Tab. 2) and counterfactual similarity with the input in terms of Graph Edit Distance (see Fig. 8). This is also because CLEAR, when producing a counterfactual candidate, it gives a fully-connected stochastic graph which then it needs to match to the input. Note, that graph matching is an NP-hard problem and there are some approximations which undermine CLEAR's performances. GIST, on the other hand, is very simple and understandable: overshoot the oracle $\Phi$'s decision boundary and backtrack via graph transformers.

Q3: Real-world applications. One compelling real-world application of GIST is drug repurposing. Suppose we have a known drug A that effectively treats disease $d_1$. Our goal is to discover a new drug B that treats a different disease $d_2$, potentially by modifying A. However, directly identifying B is often difficult and financially expensive. GIST could help by first exploring compounds that are far from A - those that may not initially preserve A’s chemical properties but show efficacy against $d_2$ (albeit with more side effects). From there, GIST can iteratively "walk back" toward A, gradually optimizing for lower side effects while preserving therapeutic relevance to $d_2$. This path - from distant molecular candidates back toward A - could lead to a novel compound B that is both effective for $d_2$ and safer. We find this direction highly promising and plan to investigate it further. However, applying GIST to drug discovery requires close collaboration with chemists and pharmaceutical experts, as well as human-in-the-loop evaluation to ensure the physical plausibility of generated compounds. Such interdisciplinary work would also naturally address the need for domain-specific user studies, which is a point you raised in your original review.

[1] Prado-Romero et al. Robust stochastic graph generator for counterfactual explanations. AAAI'24 (page 15-16, Figs. 10-11 of the suppl. material on arXiv)

[2] Prenkaj et al. Unifying Evolution, Explanation, and Discernment: A Generative Approach for Dynamic Graph Counterfactuals. KDD'24 (Figs. 7-8)

[3] Prado-Romero et al. A survey on graph counterfactual explanations: definitions, methods, evaluation, and research challenges. ACM CSUR'24.

[4] Ma, et al. CLEAR: Generative counterfactual explanations on graphs. NeurIPS'22.