Source-linked AI summary
Robust Counterfactual Explanations on Graph Neural Networks
Mohit Bajaj, Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang, Peter Cho-Ho Lam, Yong Zhang
TL;DR
GNN explanations are important in high-stakes applications, but robust, intuitive counterfactual explanations remain needed. RCExplainer models decision logic shared across similar graphs and produces edge subsets whose removal changes predictions; the authors report superior benchmark performance across several measures.
Problem
Method
RCExplainer models shared decision regions and trains a neural network to select edges so the induced subgraph preserves the input prediction while removing those edges changes it.
Source: §1 · p. 2, §4.3.2 · p. 6Results
The authors report superior performance over state-of-the-art methods on fidelity, robustness, accuracy, and efficiency.
Source: §1 · p. 2Takeaways & Limitations
Removing the selected edge set produces a remainder graph whose prediction changes significantly from the input graph’s prediction.
Source: §4.3.2 · p. 6The method focuses on GNNs with piecewise linear activation functions, such as MaxOut and ReLU.
Source: §3 · p. 3
Abstract
from arXiv · showhide
Massive deployment of Graph Neural Networks (GNNs) in high-stake applications generates a strong demand for explanations that are robust to noise and align well with human intuition. Most existing methods generate explanations by identifying a subgraph of an input graph that has a strong correlation with the prediction. These explanations are not robust to noise because independently optimizing the correlation for a single input can easily overfit noise. Moreover, they do not align well with human intuition because removing an identified subgraph from an input graph does not necessarily change the prediction result. In this paper, we propose a novel method to generate robust counterfactual explanations on GNNs by explicitly modelling the common decision logic of GNNs on similar input graphs. Our explanations are naturally robust to noise because they are produced from the common decision boundaries of a GNN that govern the predictions of many similar input graphs. The explanations also align well with human intuition because removing the set of edges identified by an explanation from the input graph changes the prediction significantly. Exhaustive experiments on many public datasets demonstrate the superior performance of our method.
1 Introduction
The paper targets GNN explanations that are both counterfactual and robust to noise, proposing RCExplainer to model decision logic shared across similar graphs. It reports superior performance across fidelity, robustness, accuracy, and efficiency.
1 Introduction
- GNN explanations matter for trust in high-stakes applications, and counterfactual explanations identify edges whose removal significantly changes a prediction.The paper motivates counterfactual questions with molecular prediction and recommendation examples.Source: §1 · pp. 1–2
- Existing GNN explanation methods can identify correlated subgraphs that neither change predictions when removed nor remain stable under slight input changes.The paper attributes fragility to independently optimizing each input explanation, which can overfit noise.Source: §1 · p. 2
- RCExplainer models GNN decision logic with regions formed by linear boundaries shared across multiple same-class graphs, supporting explanations robust to individual-sample noise.The regions are found by an unsupervised method.Source: §1 · p. 2
- Its loss trains a neural network to select a small edge subset whose induced subgraph preserves the input prediction while its removal changes the prediction significantly.The retained subgraph lies within the decision region; the remainder lies outside it.Source: §1 · p. 2
- The authors report superior performance over state-of-the-art methods on fidelity, robustness, accuracy, and efficiency.The experiments compare the methods comprehensively.Source: §1 · p. 2
2 Related work
Prior GNN explanation approaches include model-level and instance-level methods, but many do not ensure counterfactual behavior or robustness. RCExplainer directly optimizes these properties while drawing on decision logic shared across similar graphs.
2 Related work
- Model-level explanations synthesize class-associated artificial graphs, but an input may not contain them and removing them need not change its prediction.The paper distinguishes these general behavior summaries from explanations of a specific input graph.Source: §2 · p. 2
- GNNExplainer and PGExplainer optimize mutual-information-based objectives, while CF-GNNExplainer [24] optimizes counterfactual behavior per instance but ignores explanation-prediction correlation.MEG [30] produces counterfactual explanations for compound prediction but relies heavily on domain knowledge, limiting general applicability.Source: §2 · p. 3
- Gradient-based methods may be misleading due to noisy gradients, while attention-based explanations require altered GNN architectures and may not reflect the original model faithfully.The paper also distinguishes adversarial attacks, which change predictions without necessarily explaining the original prediction [51] [43] [10].Source: §2 · p. 3
- Most instance-level methods are not necessarily counterfactual or robust: removing a correlated explanation may leave the prediction unchanged, and per-instance optimization can overfit noise.The paper identifies these weaknesses as consequences of GNN non-convexity and independent optimization.Source: §2 · p. 3
- RCExplainer directly optimizes an explanation’s counterfactual property and prediction correlation, deriving it from common linear boundaries across many similar graph instances.This contrasts with methods that optimize each instance independently.Source: §2 · p. 3
3 Problem Formulation
The formulation defines a robust counterfactual explanation as a small set of input-graph edges whose removal most reduces confidence in the original prediction and whose identity remains stable under noise. The stated scope is GNNs with piecewise linear activations.
3 Problem Formulation
- A graph G = {V, E} has nodes V and edges E, with its edge structure represented by a binary adjacency matrix A.A_ij is 1 when nodes v_i and v_j are connected and 0 otherwise.Source: §3 · p. 3
- The formulation focuses on GNNs with piecewise linear activations, including MaxOut and ReLU families.The model maps a graph to a probability distribution over classes.Source: §3 · p. 3
- A robust counterfactual explanation is a small edge subset whose removal maximizes the drop in original-prediction confidence and that stays stable when edges and node features are perturbed by random noise.The definition frames counterfactuality and noise stability as the two requirements.Source: §3 · pp. 3–4
4 Method
RCExplainer models shared GNN decision logic across graphs, then trains an edge-selection network to produce explanations that preserve the input prediction but change it when the selected edges are removed.
4.1 Modelling Decision Regions
- Convex regions induced by GNN linear boundaries cover many same-class graphs, capturing shared decision logic intended to reduce overfitting to individual-graph noise.Source: §4.1 · p. 4
4.2 Extracting Decision Regions
- Because enumerating all boundaries is intractable, RCExplainer samples boundaries, greedily selects a feasible region, and peels covered graphs off to find further regions.Source: §4.2 · p. 5
4.3 Producing Explanations
- The method uses edges as explanations because GNNs make decisions by aggregating messages passed on edges, which can provide insight into their decision logic.Source: §4.3 · p. 6
4.3.1 The Neural Network Model
- The explanation network scores edges from their endpoint embeddings, sets nonexistent edges to zero, and selects edges with scores above 0.5.Source: §4.3.1 · p. 6
4.3.2 Training Model fθ
- Training uses continuous proxy graphs to preserve the selected subgraph's prediction while making its edge-deleted remainder counterfactual, with sparsity and near-binary mask regularization.Source: §4.3.2 · pp. 6–7
- Inference takes O(|E|) time on an input graph, needs no retraining for unseen graphs, and is reported as significantly faster than methods [47].Source: §4.3.2 · p. 7
5 Experiments
Experiments compare RCExplainer with state-of-the-art methods on graph and node classification; the reported main-text results focus on graph classification across fidelity, robustness, and efficiency. RCExplainer leads the reported fidelity and robustness comparisons, and its inference time is comparable to PGExplainer.
5.1 Fidelity
- RCExplainer achieves the best fidelity at every sparsity level and the best robustness AUC on all datasets.The fidelity comparison uses matched sparsity levels; robustness is evaluated under varying levels of noise.Source: Figure 1 · p. 8, §5.1 · p. 8, Figure 2 · p. 9
5 Experiments
- The experiments cover graph classification on BA-2motifs, Mutagenicity, and NCI1, while the paper reports node-classification results in Appendix F.Fidelity comparisons use explanations at the same sparsity level; reported main-text results focus on graph-classification fidelity, robustness, and efficiency.Source: §5 · p. 8, §5.1 · p. 8
5.1 Fidelity
- CF-GNNExplainer performs best among the other methods on fidelity, while RCExplainer significantly outperforms the RCExp-NoLDB ablation.The authors attribute CF-GNNExplainer’s fidelity to its counterfactual optimization and report that RCExplainer’s decision-region LDBs improve fidelity.Source: §5.1 · p. 8, §5 · p. 8
5.2 Robustness Performance
- RCExplainer is as efficient as PGExplainer and significantly faster than GNNExplainer, PGM-Explainer, SubgraphX, and CF-GNNExplainer on Mutagenicity.Inference time is measured on unseen graph samples; Table 1 reports average time for one graph sample.Source: §5.2 · p. 9, Table 1 · p. 9
6 Conclusion
RCExplainer extracts GNN decision boundaries and trains a neural network with a counterfactual loss to produce explanations. The method is presented as robust on synthetic and real-life benchmarks, with its current scope limited to piecewise-linear GNNs.
6 Conclusion
- RCExplainer extracts decision boundaries and uses a counterfactual loss to train a neural network that produces explanations with strong counterfactual characteristics.The boundaries are shared across multiple samples of the same predicted class, supporting explanations that do not overfit an individual sample’s noise.Source: §6 · pp. 9–10
- Experiments on synthetic and real-life benchmark datasets support the efficacy of the method.Source: §6 · p. 10
- The method is scoped to piecewise-linear GNNs; extension to other GNN families and link prediction remains future work.Source: §6 · p. 10
- The authors identify possible privacy exposure and misuse of the method’s ideas to improve adversarial attacks as risks without adequate protections.They state these risks may be mitigated through awareness and proactive measures.Source: §6 · p. 10
A Illustration of RCExplainer’s training
The appendix illustrates RCExplainer’s training and adaptations for node classification and class-pair-specific explanations. For individual boundaries, the method identifies motifs that distinguish the two classes.
A Illustration of RCExplainer’s training
- RCExplainer training extracts and processes decision boundaries from graph-embedding features after the last graph convolution, then trains an explanation network on edge activations to predict an adjacency-matrix mask using counterfactual loss.Source: Figure 3 · p. 13
B Node classification
- For node classification, the method extracts boundaries from node embeddings and generates explanations on the node’s k-hop computation graph, selecting edges with mask values above 0.5.The number of hops k equals the number of graph convolution layers.Source: B Node classification · p. 13
C Interpreting individual boundaries
- Restricting explanation to the boundary between two target classes identifies the motif distinguishing them; removing that motif lowers confidence in the original class and raises confidence in the target class.On the three-class synthetic dataset, explanations for boundaries B12 and B13 identify different class-specific motifs.Source: C Interpreting individual boundaries · p. 14, Figure 4 · p. 14
D Proof: Decision region extraction is an instance of SCSC optimization
The proof recasts decision-region extraction as a Submodular Cover Submodular Cost (SCSC) problem. It establishes submodularity by showing how adding a boundary changes sample coverage.
D Proof: Decision region extraction is an instance of SCSC optimization
- The optimization is framed as an SCSC problem by expressing coverage and non-coverage terms through functions g′(P) and h′(P).The covered samples are class-c samples; the constraint also refers to samples outside class c.Source: D Proof: Decision region extraction is… · pp. 14–15
- Adding a linear decision boundary can remove class-c samples from the induced polytope, with the reduction in coverage represented by the change in g′.The proof compares this reduction for nested boundary sets P and Q.Source: D Proof: Decision region extraction is… · p. 15
- For nested sets of boundaries, the proof states that adding a new boundary removes at least as many samples from the polytope induced by P as from the one induced by Q, establishing submodularity of g′; it likewise establishes submodularity of h′.Source: D Proof: Decision region extraction is… · p. 15
E Implementation details
The experiments use dataset-specific GCNs and public baseline implementations, with RCExp-NoLDB as a local variant that omits decision-boundary training. Training uses a shared split and optimizer setup with selected parameters varying by task and dataset.
E Implementation details
- Table 2 reports dataset properties and test accuracy for the corresponding trained GCN models.Experiments ran on a Linux machine with an Intel i7-8700K CPU and Nvidia GeForce GTX 1080 Ti GPU.Source: Table 2 · p. 15, E Implementation details · pp. 15–16
- Experiments use public implementations and authors’ default parameters for baselines, with a 80/10/10% random training, validation, and test split.The cited implementations include GNNExplainer and SubgraphX; their licenses are noted separately.Source: E Implementation details · pp. 15–16
- RCExp-NoLDB uses the RCExplainer setup without LDBs, and its confidence loss encourages the original class on the masked graph but not on the remainder graph.The confidence loss is jointly minimized with sparsity and discreteness regularizers.Source: E Implementation details · pp. 15–16
- Training uses Adam at learning rate 0.001 for 600 epochs, with task- and dataset-specific λ, β, and μ settings and 50 sampled LDBs per class.The authors report that 50 sampled boundaries suffice for greedy selection to cover all samples of a class.Source: E Implementation details · p. 16
F Additional experiments
Additional experiments evaluate explanation fidelity, robustness to graph noise, and node accuracy, alongside synthetic-dataset accuracy. The reported comparisons favor RCExplainer, with a qualification that node-accuracy comparisons use an approximation for several methods.
F Additional experiments
- Fidelity measures the original-class confidence drop after masking the explanation, while sparsity measures the fraction of graph edges omitted from it.Because SubgraphX and PGM-Explainer do not rank edge importance, fidelity comparisons use samples with similar sparsity; the reported samples are positive-labeled.Source: F Additional experiments · p. 16
- For k = 4 and k = 12, RCExplainer outperforms other methods by a large margin on BA-2motifs and NCI1 in noise-robustness AUC.The measure compares noisy-graph explanations against the original explanation’s top-k edges; Figure 5 results average 10 runs.Source: F Additional experiments · p. 16, Figure 5 · p. 17
- Noise robustness AUC treats the original explanation’s top-k edges as positives and compares them with the explanation for a label-preserving noisy graph.Noise includes feature perturbations and random edge additions or deletions; node accuracy is also reported because some baselines lack edge weights for the AUC comparison.Source: F Additional experiments · p. 16
- Despite an approximate extension for node-level accuracy, RCExplainer significantly outperforms all methods for k = 2, 4, and 8.The approximation is needed because several explanation methods do not rank nodes by importance; Figure 6 reports averages across 10 runs.Source: Figure 6 · p. 17, F Additional experiments · p. 18
- RCExplainer achieves close-to-optimal AUC on all four synthetic node-classification datasets, where motifs serve as approximate explanation ground truth.PGM-Explainer lacks edge weights for this AUC evaluation, and CF-GNNExplainer results are limited to those available from prior work.Source: Table 3 · p. 18, F Additional experiments · p. 18
G Hyperparameter analysis
The hyperparameter analysis examines how sampled decision boundaries and λ affect fidelity. Fidelity saturates at 50 sampled boundaries on BA-Community, while λ = 0.1 performs best on BA-2motifs.
G Hyperparameter analysis
- On BA-2motifs, λ = 0.1 gives the best fidelity and λ = 0.9 the worst.The authors attribute the poor result at λ = 0.9 to the counterfactual loss term Lopp receiving too little weight; Figure 8 plots fidelity versus sparsity across λ values.Source: G Hyperparameter analysis · p. 18, Figure 8 · p. 19
- On BA-Community, fidelity improves as sampled LDBs increase from 10 to 50 and then saturates.Figure 7 examines fidelity versus sparsity across different numbers of sampled boundaries; the authors attribute saturation to sufficient boundaries for greedy selection to form a good decision region.Source: G Hyperparameter analysis · p. 18, Figure 7 · p. 19
H Qualitative results
Qualitative examples show RCExplainer identifying motifs in node- and graph-classification cases, including cases where other structures or motifs could mislead an explanation.
H Qualitative results
- RCExplainer identifies the relevant community motif despite another house-structure containing the query node, and highlights N–C edges in mutagenic compounds.Masking those edges breaks NO2 groups from the carbon ring and pushes the prediction toward “Non-Mutagenic”; Table 4 shows the compared methods’ explanations.Source: H Qualitative results · p. 19, Table 4 · p. 20