Controllable GNN Explanations via Multi-Metric Preference Selection

Rachit Verma; Yashraj J. Deshmukh; Anirban Dasgupta

cs.AISep 26, 2026

Controllable GNN Explanations via Multi-Metric Preference Selection

Authors: Rachit Verma, Yashraj J. Deshmukh, Anirban Dasgupta

Organizations: Indian Institute of Technology Gandhinagar

Abstract

Mechanisms for generating GNN explanations are crucial for building trust and mitigating biases in Graph Neural Networks (GNNs), especially in high-stakes scenarios. Most current methods optimize only for fidelity under the sparsity constraint. However, this discounts the need for interpretable explanations (those that consist of familiar motif patterns) and stable explanations (those that remain unchanged under structural perturbations). We propose a novel approach that optimizes GNN explanations across these metrics, exposing their relative weighing as a control. Experiments on various real-world datasets, including MUTAG, BA-2Motif, BAMultiShapes, and PROTEINS, suggest that our method produces higher-fidelity explanations than a state-of-the-art baseline on MUTAG and PROTEINS across all evaluated budgets, and on BA-2Motif at larger budgets, while being faster in the regime of small explanation budgets. They also indicate that our method produces more stable explanations for the MUTAG and BA-2Motif datasets. We also examine the relationship among different metrics via their induced trade-off surface and explore its dependence on the nature of the motif library.

Figures & tables

Panel of Figure 1 — Figure 1: Performance sweeps across explanation budgets and datasets. Our metric-controlled methods against the SubgraphX baseline. (a) Fidelity on native dataset scales. (b) Interpretability. On BA-2Motif, the metric is close to binary, meaning an explanation either fits a planted shape under the budget or it does not, which puts our scores at or near zero at $B\in\{6,8\}$ . (c) Stability under the VGAE index. (d) Stability under the unbounded GNTK kernel; values are unscaled, and cross-panel comparison with (c) is not meaningful.

Configuration	Fidelity	Stability	Fidelity	Stability
	VGAE		GNTK
interp_off	0.5433	44.32	0.5450	78 117
interp_precomputed	0.5449	45.69	0.5374	81 305

Table 1: Motif-prior ablation on MUTAG at

B=12

, under both similarity indices

Figure 2: The trade-off surface under the VGAE similarity index, for both datasets. Rows are datasets, and the columns are three views of the same sweep. Left: sampled weight vectors $(w_{i},w_{f},w_{s})$ on the 2-simplex, coloured by the interpretability of the resulting explanations, with faint rays from the $w_{s}$ apex marking constant $\rho=w_{f}/(w_{i}+w_{f})$ . Centre: scan along $\rho$ at fixed $w_{s}=\tfrac{1}{3}$ , with shaded envelopes giving replicate noise floors. Right: knee construction, each metric min-max-normalized. The two rows behave qualitatively differently. On MUTAG, fidelity rises, and interpretability falls as $\rho$ increases. On BA-2Motif, the two metrics move together so no regime boundaries are identifiable. Section 4 attributes the difference to the composition of each dataset’s motif library.

Dataset	Metric	$R^{2}$ ( $\rho$ only)	95% CI	$R^{2}$ ( $\rho+w_{s}$ )	Gain from $w_{s}$
MUTAG ( $n{=}20$ )	VGAE Fidelity	0.765	[0.592, 0.889]	0.783	+0.018
	VGAE Interpretability	0.922	[0.871, 0.962]	0.930	+0.007
	VGAE Stability	0.678	[0.430, 0.844]	0.682	+0.004
	GNTK Fidelity	0.718	[0.500, 0.865]	0.773	+0.056
	GNTK Interpretability	0.946	[0.903, 0.983]	0.951	+0.005
	GNTK Stability	0.919	[0.848, 0.972]	0.945	+0.026

Table 2: Variance in each output metric explained by

\rho=w_{f}/(w_{f}+w_{i})

alone, versus by

\rho

together with

w_{s}

. Confidence intervals are percentile bootstrap over the

n

runs per index. The MUTAG results indicate that, although stability control is nearly inert because fidelity is strongly correlated with stability, it still plays a role in determining the metrics for the BA-2Motif dataset, since

\rho

alone cannot explain the results.

Panel of Figure 3 — Figure 3: Explanation runtime across budgets (seconds per graph). Our method against SubgraphX as a function of explanation size on (a) MUTAG and (b) BA-2Motif. Both are timed at deployment cost. The two frameworks scale in opposite directions.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Graphs	Split	Seed	Hidden	Optimiser	Epochs	Accuracy (errors)
MUTAG	188	$80/20$	—	300	Adam $3\!\times\!10^{-3}$	50	0.798 (38)
BA-2Motif	1000	$80/20$	—	300	Adam $3\!\times\!10^{-3}$	50	1.000 (0)
BAMultiShapes	1000	$800/200$	12345	64	Adam $1\!\times\!10^{-2}$	100	0.938 (62)
PROTEINS	1113	$890/223$	12345	128	Adam $1\!\times\!10^{-3}$	100	0.845 (172)

Appendix

Table 3: Target model training configuration. Accuracy is measured over the full dataset in every case. The last column is the number of graphs the model disagrees with the ground-truth label on, which matters here because the interpretability prior is indexed by the predicted class (Appendix E ).

Dataset	$fid$	$interp$	$\widehat{fid}$	$\widehat{interp}$	$w_{f}\widehat{fid}$	$w_{i}\widehat{interp}$
	Raw		Scaled		Effective
MUTAG	0.425	1.354	4.25	1.354	3.54	$+0.112$
BA-2Motif	0.681	1.103	6.81	1.103	5.67	$+0.092$
BAMultiShapes	0.201	$-179.379$	2.01	$-0.179$	1.67	$-0.015$
PROTEINS	0.312	1.312	3.12	1.312	2.60	$+0.109$

Appendix

Table 4: Effect of the per-dataset normalization, averaged over explanation budgets for the VGAE method, under the reference-corpus prior. Columns 2–3 give the raw metric means, columns 4–5 the same quantities after division by

\sigma_{f}

and

\sigma_{i}

, and columns 6–7 the effective contribution

w\cdot\widehat{\text{metric}}

to the reward under the default controls

(0.833,0.083,0.083)

Phase	s/graph	Role
setup	0.003	model forward passes, normalization constants
stage1_main	1.108	Stage 1 search on the target graph
smoothing	10.642	sampling $M$ perturbations, Stage 1 on the retained $N$
stability_norm	0.001	stability normalization constants
stage2_main	4.260	Stage 2 search on the target graph
stab_eval	10.679	evaluation only : re-samples to score stability

Appendix

Table 5: Per-phase cost of explaining one MUTAG graph, averaged over both similarity indices and all four budgets at

20

graphs per cell. Only stab_eval is excluded from the reported runtimes.

MUTAG
Explainer	Metric	$B{=}6$	$B{=}8$	$B{=}10$	$B{=}12$
GNNExplainer	Fidelity	0.218	0.256	0.285	0.322
GNNExplainer	Interpretability	0.460	0.489	0.498	0.524
GNNExplainer	Stability (VGAE)	0.665	1.248	1.701	2.571
GNNExplainer	Stability (GNTK)	1 280	2 110	3 144	5 647
PGExplainer	Fidelity	0.234	0.256	0.278	0.331

Appendix

Table 6: GNNExplainer and PGExplainer across all budgets and metrics.

Dataset	Method	$B=6$	$B=8$	$B=10$	$B=12$
MUTAG	Ours ( VGAE )	$0.293\pm 0.006$	$0.357\pm 0.010$	$0.462\pm 0.017$	$0.533\pm 0.015$
MUTAG	Ours ( GNTK )	$0.298\pm 0.005$	$0.352\pm 0.005$	$0.462\pm 0.010$	$0.544\pm 0.014$
BA-2Motif	Ours ( VGAE )	$0.433\pm 0.027$	$0.496\pm 0.041$	$0.916\pm 0.061$	$0.955\pm 0.039$
BA-2Motif	Ours ( GNTK )	$0.461\pm 0.001$	$0.523\pm 0.026$	$0.935\pm 0.053$	$0.973\pm 0.025$
BAMultiShapes	Ours ( VGAE )	$0.215\pm 0.004$	$0.234\pm 0.005$	$0.260\pm 0.008$	$0.265\pm 0.007$
BAMultiShapes	Ours ( GNTK )	$0.215\pm 0.003$	$0.233\pm 0.006$	$0.257\pm 0.010$	$0.268\pm 0.007$

Appendix

Table 7: Seed-to-seed fidelity spread (mean

\pm

std over 5 seeds, 20 graphs per run).

Dataset	Method	$B=6$	$B=8$	$B=10$	$B=12$
MUTAG	Ours ( VGAE )	$1.193\pm 0.086$	$1.414\pm 0.086$	$1.472\pm 0.050$	$1.469\pm 0.050$
MUTAG	Ours ( GNTK )	$1.181\pm 0.052$	$1.337\pm 0.033$	$1.419\pm 0.036$	$1.382\pm 0.022$
BA-2Motif	Ours ( VGAE )	$0.073\pm 0.014$	$0.178\pm 0.036$	$1.927\pm 0.067$	$1.949\pm 0.084$
BA-2Motif	Ours ( GNTK )	$0.083\pm 0.006$	$0.135\pm 0.023$	$1.632\pm 0.185$	$1.725\pm 0.038$
BAMultiShapes	Ours ( VGAE )	$-323.4\pm 0.1$	$-323.3\pm 0.0$	$-323.2\pm 0.1$	$-323.2\pm 0.1$
BAMultiShapes	Ours ( GNTK )	$-323.5\pm 0.1$	$-323.3\pm 0.1$	$-323.3\pm 0.1$	$-323.2\pm 0.0$

Appendix

Table 8: Seed-to-seed interpretability spread (mean

\pm

std over 5 seeds, 20 graphs per run).

Dataset	Method	$B=6$	$B=8$	$B=10$	$B=12$
MUTAG	Ours ( VGAE )	$29.4\pm 0.8$	$35.5\pm 0.7$	$40.9\pm 1.4$	$46.0\pm 1.1$
MUTAG	Ours ( GNTK )	$14\,898\pm 241$	$30\,827\pm 485$	$53\,563\pm 1\,163$	$80\,839\pm 2\,670$
BA-2Motif	Ours ( VGAE )	$12.4\pm 1.3$	$15.8\pm 1.4$	$18.4\pm 1.8$	$19.8\pm 1.7$
BA-2Motif	Ours ( GNTK )	$1\,764\pm 82$	$2\,735\pm 716$	$3\,695\pm 246$	$4\,890\pm 661$
BAMultiShapes	Ours ( VGAE )	$9.387\pm 0.839$	$10.4\pm 0.6$	$10.9\pm 1.0$	$12.1\pm 0.9$
BAMultiShapes	Ours ( GNTK )	$1\,795\pm 120$	$2\,774\pm 116$	$3\,607\pm 230$	$4\,937\pm 390$

Appendix

Table 9: Seed-to-seed stability spread (mean

\pm

std over 5 seeds, 20 graphs per run).

Figure 4: The trade-off surface under the GNTK similarity index , plotted exactly as Figure 2 . The agreement between this figure and Figure 2 rules out an artifact of the similarity index.

GNN Explainability

Graph neural network explainability studies how to identify and communicate the features, nodes, edges, and subgraphs behind graph-model predictions.

See all 80 papers

Beyond Trained Models: Compiling GNNs for a Sound Explainer Benchmark
Oct 2, 2026Steve Azzolin, Francesco Paolo Nerini, Stefano Teso +4GNN Explainability Explainability Evaluation
University of Trento Trento, Italy
Measuring What Matters: A Unified Evaluation Framework for GNN Explainability
Jul 6, 2026Francesco Paolo Nerini, Mirko Zaffaroni, Paolo Baracco +2Explainability Evaluation GNN Explainability
Sapienza University of Rome, Rome, Italy · Intesa Sanpaolo AI Research, Turin, Italy · Anti Financial Crime Digital Hub, Turin, Italy +1
CIExplainer++: Generating Causal and Interpretable Explanations for Graph Neural Networks
Jun 17, 2026Francisco Caldas, Sahil Satish Kumar, Ruben Belo +1Natural Language Explanation Generation Causal Interpretability
NOVA LINCS, NOVA School of Science and Technology, Lisbon, Portugal

Oct 2, 2026J/K move · Enter open · S save

Beyond Trained Models: Compiling GNNs for a Sound Explainer Benchmark

Steve Azzolin, Francesco Paolo Nerini, Stefano Teso, Francesco Bonchi+3

University of Trento Trento, Italy

GNN Explainability Explainability Evaluation

Open paper AskPDF arXiv

Explainers for Graph Neural Networks (GNNs) are commonly evaluated by their plausibility, i.e., how well their explanations recover a predefined ground truth, such as a motif planted in the data. This protocol implicitly assumes that a GNN trained on such data relies on the intended motif. Although prior work has questioned this assumption, plausibility remains widespread. First, we show that the assumption is violated on several widely used benchmarks, where, e.g., degree statistics alone suffice to solve the task. Then, we remove this confounder by replacing training with compilation. We achieve this by introducing

\mathsf{Gracr}

, the first compiler translating graded modal logic formulas into GNN weights, yielding models that replicate the behaviour of the corresponding formulas. Since the behaviour of the model is now known by construction, we can define its ground truth explanation formally and compute it exactly. Building on this, we introduce

\mathsf{Gracr}\mathsf{Bench}

, a benchmark of compiled GNNs for the evaluation of explainers against this exact ground truth. Experiments on eleven explainers across six tasks show its effectiveness for fine-grained diagnostic evaluation: notably, we discover that most explainers are not robust to indirect influences or alternative implementations of the same formula. These results position

\mathsf{Gracr}\mathsf{Bench}

as a novel, rigorous evaluation setting for graph post-hoc explainability.

Abstract

GNN Explainability

Explore similar work

Beyond Trained Models: Compiling GNNs for a Sound Explainer Benchmark

Measuring What Matters: A Unified Evaluation Framework for GNN Explainability

CIExplainer++: Generating Causal and Interpretable Explanations for Graph Neural Networks