PaperlayerView exact revision on arXiv

Source-linked AI summary

Controllable GNN Explanations via Multi-Metric Preference Selection

Rachit Verma, Yashraj J. Deshmukh, Anirban Dasgupta

arXiv:2609.32436v2cs.AIcs.LG

TL;DR

GNN explainers commonly prioritize fidelity, although explanation quality also includes interpretability and stability. This paper introduces a two-stage method with practitioner-controlled weights across those metrics. The method is comparable to a state-of-the-art explainer and is reported to be more stable on two of three evaluated datasets.

  • Problem

    Most existing GNN explainers optimize fidelity alone, although explanation quality is also evaluated through interpretability and stability.

    Source: §1 · p. 1

  • Method

    The method formalizes fidelity, interpretability, and stability and uses a two-stage optimization procedure with practitioner-controlled relative metric weights.

    Source: §1 · p. 2

  • Results

    The method is comparable to a state-of-the-art explainer and more stable on 2 of 3 evaluated datasets; it has higher fidelity than SubgraphX on MUTAG at all budgets and BA-2Motif at larger budgets.

    Source: §1 · p. 2, Comparison with a State-of-the-art… · p. 7, §6 · p. 12

  • Takeaways & Limitations

    Exposing metric weights lets practitioners inspect and choose a point on the trade-off among fidelity, interpretability, and stability.

    Source: §1 · p. 2

    A weighted-sum objective can recover only points on the convex hull of attainable trade-offs, leaving solutions in concave regions unreachable at every weighting.

    Source: §5 · p. 11

Abstract

from arXiv · show

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.

1 Introduction

The introduction argues that GNN explainers should optimize fidelity, interpretability, and stability together rather than prioritize fidelity alone. It presents practitioner-controlled weighting and a two-stage method, with benchmark comparisons and trade-off analysis as central contributions.

1 Introduction

  • Existing GNN explainers predominantly optimize fidelity, despite explanation quality also being evaluated through stability and interpretability.The introduction describes the operational value of each metric as dependent on practitioner requirements and domain constraints.Source: §1 · p. 1
  • The framework exposes relative weights for fidelity, interpretability, and stability as practitioner-set metric-importance controls.The paper frames these metrics as instance- and model-dependent in their correlations, with no universally optimal trade-off.Source: §1 · pp. 1–2
  • Interpretability is quantified through human-understandable motifs, while stability concerns resistance to topology-preserving perturbations.Fidelity follows a formulation combining the quality drop when the explanation is removed with the quality of the explanation graph itself.Source: §1 · p. 2
  • A two-stage procedure first optimizes fidelity and interpretability, then refines candidate explanations for stability under structural perturbations.The perturbation strategy is designed to preserve core topological and feature properties of the target graph.Source: §1 · p. 2
  • The work formalizes fidelity, interpretability, and stability, maps trade-off surfaces on MUTAG and BA-2Motif, and compares runtime with SubgraphX.The runtime analysis characterizes the settings in which the proposed approach is faster.Source: §1 · p. 2
  • The method achieves higher fidelity than SubgraphX on MUTAG at all budgets and BA-2Motif at larger budgets, with only suggestive gains on PROTEINS.The reported MUTAG and larger-budget BA-2Motif margins exceed the measured seed-to-seed spread of both methods.Source: §1 · p. 2

2 Related Work

Prior GNN explainers differ in whether they score individual features, search connected subgraphs, or match motifs and exemplars. Although some methods consider multiple explanation properties, the literature described here generally fixes their relative weights.

Attribution and subgraph search

  • Early explainers score individual nodes and edges, while later approaches search connected subgraphs, motifs, counterparts, or dataset-wide exemplars.Examples include GNNExplainer, PGExplainer, GISST, SubgraphX, MotifExplainer, MatchExplainer, and GNNXemplar.Source: §2 · pp. 2–3
  • The paper's motif-based interpretability draws on motif-centric evaluation while treating the motif library as a practitioner-supplied input.The related-work passage contrasts this with MotifExplainer, which extracts motifs from a predefined library using attention.Source: §2 · pp. 2–3

The evaluation–optimization gap

  • Zorro jointly considers validity, sparsity, and perturbation robustness but fixes their relative importance in a scalar objective.The passage contrasts this with the paper's practitioner-facing controls, which expose the scalarization weights for inspection and selection.Source: §2 · p. 3

3 Methodology

The method searches for connected, budget-limited explanations using a weighted fidelity–interpretability objective, then refines candidates to account for stability under graph perturbations. It uses motif matching to quantify interpretability and similarity-based sampling to construct perturbations.

Problem Formulation

  • The explanation objective is difficult to optimize directly because its stability term is recursive, so the method substitutes a tractable surrogate.The surrogate applies fidelity and interpretability weights in the first-stage objective.Source: Problem Formulation · pp. 3–4

Stage 1: Fidelity and Interpretability Optimization

  • Stage 1 maximizes fidelity and interpretability weighted by wf and wi, running on the target graph and each sampled perturbation.The target explanation invokes this stage N + 1 times in total.Source: Problem Formulation · p. 4

Fidelity Characterization

  • Fidelity combines the confidence change after removing an explanation with how well the explanation alone preserves the target-class confidence.Its two components are combined by a weighted harmonic mean, which penalizes extreme disparities between them.Source: Problem Formulation · p. 4

Interpretability Quantification

  • Interpretability scores how well user-defined motif queries match an explanation, using an embedding-based containment penalty and motif-class correlation priors.The prior is computed from motif occurrence statistics across class-specific dataset coresets; the resulting interpretability score can be signed.Source: Problem Formulation · pp. 4–5

Metric normalization

  • Because fidelity and interpretability have different native scales, the method rescales them before applying their importance weights.The controls act on rescaled metrics, while reported metric values remain on their native scales.Source: Problem Formulation · p. 5

Search and budget semantics

  • Both optimization stages use MCTS over connected subgraphs, with sparsity enforced as a search constraint rather than an objective penalty.A state is a node set inducing a connected subgraph, and each action adds one node.Source: Problem Formulation · p. 5

Perturbed Graph Sampling and Graph Similarity

  • Perturbations are drawn by random walks, then filtered to retain the N candidates most similar to the target graph.The method considers VGAE node embeddings with greedy bipartite matching and GNTK, which captures multi-hop neighborhood structures and node features.Source: Problem Formulation · pp. 5–6

Formulation of the Stability Metric

  • The stability estimator compares an explanation with Stage 1 explanations from the target and its perturbed copies, weighting them by their Stage 1 quality.The passage notes that this construction makes stability a similarity-weighted composition of fidelity and interpretability rather than an independently defined property.Source: Problem Formulation · p. 6

4 Experiments and Results

Across four binary graph-classification datasets, the experiments compare the metric-controlled method with SubgraphX and examine metric trade-offs, stability, motif-prior effects, and runtime. Results vary by dataset and metric, while the trade-off analysis links the observed regimes to motif-library properties.

Comparison with a State-of-the-art Method

  • The proposed methods lead SubgraphX in fidelity on MUTAG at every budget and on BA-2Motif at larger budgets; PROTEINS results are suggestive, while SubgraphX leads on BAMultiShapes.On BA-2Motif, SubgraphX leads at B ∈{6, 8} and the proposed methods at B ∈{10, 12}; the PROTEINS margins do not clear the noise floor.Source: Figure 1 · p. 7, Comparison with a State-of-the-art… · p. 7
  • Interpretability favors SubgraphX at every MUTAG budget, while the proposed method leads on BAMultiShapes and PROTEINS; synthetic-dataset scores can change abruptly at motif-size thresholds.On BA-2Motif, SubgraphX leads at the two smallest budgets, but the apparent reversal at larger budgets is unresolved.Source: Comparison with a State-of-the-art… · p. 8
  • VGAE stability favors the proposed methods on every dataset, while GNTK favors them on MUTAG and BA-2Motif but SubgraphX on BAMultiShapes; PROTEINS is omitted for computational cost.Only comparisons within the same similarity index are meaningful because stability inherits the index’s scale.Source: Figure 1 · p. 7, Comparison with a State-of-the-art… · p. 8
  • On MUTAG at B = 12, removing the motif library yields fidelity differences of 0.0016 under VGAE and 0.0076 under GNTK, both within one standard deviation of seed variation.The authors conclude that no motif-library effect on fidelity is detectable at this sample size, not that its effect is zero.Source: Comparison with a State-of-the-art… · p. 9, Table 1 · p. 9
  • On MUTAG, increasing ρ raises fidelity while lowering interpretability, with three regions separated near ρ = 0.27 and ρ = 0.64.The dataset’s varied, graded motif-label associations make the objectives compete.Source: Comparison with a State-of-the-art… · p. 10
  • On BA-2Motif, fidelity and interpretability move together, so the scan identifies no regimes by ρ; the planted shape determines the label and aligns the objectives.The two metrics are positively correlated, unlike the opposing MUTAG trends.Source: Comparison with a State-of-the-art… · p. 10
  • Adding the explicit stability weight explains little extra metric variance on MUTAG but improves explanatory fit on BA-2Motif, where ρ alone is insufficient.On MUTAG, ρ alone explains R2 ∈[0.678, 0.946] and adding ws yields ∆R2 ≤0.056; on BA-2Motif, adding ws gives ∆R2 = +0.199 for VGAE Fidelity and +0.135 for VGAE Interpretability.Source: Comparison with a State-of-the-art… · p. 10, Table 2 · p. 11
  • The proposed method is 1.9× to 26.7× faster than SubgraphX across the two datasets and explanation sizes, with speedup widening as explanations shrink.At B = 6, the reported speedups are 3.9× on MUTAG and 29.9× on BA-2Motif.Source: Comparison with a State-of-the-art… · p. 10, Figure 3 · p. 11

5 Limitations and Future Work

The paper identifies limits of its weighted-sum objective and proposes stability-focused and domain-informed directions for follow-up work.

5 Limitations and Future Work

  • A weighted sum can recover only points on the convex hull of the attainable trade-off set, leaving concave regions unreachable at every weighting.Chebyshev or ε-constraint formulations are proposed as possible extensions.Source: §5 · pp. 11–12
  • A direct Stage 1 stability term is identified as the largest proposed change, while stability–fidelity relations across model expressivity remain open.The authors also suggest restricting search to a learned manifold of realistic inputs.Source: §5 · p. 12
  • The work positions GNN explainability as a customizable human-in-the-loop system, with domain knowledge needed for similarity, encoding, search pruning, and hyperparameter tuning.Source: §5 · p. 12

6 Conclusion

The paper presents a controllable multi-metric GNN explainer and finds its results comparable to a state-of-the-art method on existing metrics. The trade-off patterns differ by dataset, and the authors identify limitations and future research directions.

6 Conclusion

  • The two-stage pipeline exposes relative weights for fidelity, interpretability, and stability, and proposes formulations for interpretability and stability.Source: §6 · p. 12
  • The method is comparable to a state-of-the-art method on existing metrics and more stable on 2 of the 3 evaluated datasets.Source: §6 · p. 12
  • MUTAG’s trade-off surface reduces to a fidelity-to-interpretability ratio with nearly inert stability control, whereas BA-2Motif’s two metrics align and stability control has significant weight.Source: §6 · p. 12

A Reproducibility Statement

The reproducibility statement describes a shared experimental codebase, fixed target-model setup, and auxiliary components used in the explanation pipeline.

A Reproducibility Statement

  • A single codebase supports the reported results, with a seed flag controlling randomness and CPU experiments run using two threads per task.The supplementary repository includes the explainer, metric definitions, baseline harness, motif libraries, correlation statistics, and trained target models.Source: A Reproducibility Statement · p. 14

B Target Models

  • Target models are three-layer GIN classifiers with sum pooling and a linear readout; the paper reports full-dataset accuracy and makes no state-of-the-art claim for them.PROTEINS uses batch normalization in its MLPs, unlike the other three models; models were trained with held-out splits.Source: B Target Models · p. 14

C Auxiliary Components

  • The pipeline uses VGAE and GNTK for graph similarity and NeuroMatch for soft subgraph containment; neither auxiliary component sees class labels.VGAE learns from edge reconstruction, GNTK has no fitted parameters, and NeuroMatch is trained on subgraph-isomorphism outcomes.Source: C Auxiliary Components · p. 15
  • NeuroMatch uses a non-negative order-embedding representation, making its order relation well defined for scoring subgraph containment.Source: C Auxiliary Components · p. 15

D Experimental Parameters

The appendix specifies search, perturbation, normalization, kernel, and runtime settings for the experiments. Its normalization analysis shows that the default reward remains substantially more fidelity-heavy than the nominal weights imply.

D Experimental Parameters

  • Each target graph yields 25 random-walk perturbations, of which the 10 most similar are retained, so Stage 1 runs 11 times per graph.Search uses 20 MCTS simulations per move, exploration constant 10, rollout depth 100, and a budget limiting induced-subgraph edges.Source: D Experimental Parameters · p. 15
  • Fidelity and interpretability are divided by dataset-specific constants, while stability is divided by 1000 for GNTK and left unscaled for VGAE.The constants are chosen from raw metric means; normalization brings the two metrics within a factor of 2.2–8.4 of each other.Source: D Experimental Parameters · pp. 15–16
  • 3.56 against 0.146 on MUTAG and 5.88 against 0.096 on BA-2Motif are the default effective reward contributions, yielding ratios of 24:1 and 61:1, respectively.The table reports raw and normalized metric means alongside weighted contributions under default controls.Source: D Experimental Parameters · p. 16, Table 4 · p. 16
  • The GNTK uses four aggregation blocks and two fully connected ReLU layers per block, sums final-block tangent values across node pairs, and disables jumping knowledge.Its specification also uses degree scaling; the implementation’s aggregation convention differs numerically from the reference despite the same receptive field.Source: D Experimental Parameters · p. 16
  • Reported runtimes include all Stage 1 invocations, perturbation sampling, and Stage 2 search, but exclude perturbation resampling used only to compute stability scores.The excluded phase is stab_eval, as identified in the per-phase MUTAG cost table.Source: D Experimental Parameters · p. 17, Table 5 · p. 17

E Motif Libraries and Correlation Priors

The section describes dataset-specific motif libraries and a labelled reference-corpus prior, then details motif-counting and matching constraints, the two-stage search inputs, and SubgraphX stability variants.

E Motif Libraries and Correlation Priors

  • Motif libraries are supplied per dataset: molecular sets use functional groups and rings, synthetic sets use planted shapes, and PROTEINS uses secondary-structure arrangements.Source: E Motif Libraries and Correlation Priors · p. 17
  • The prior uses true labels from a reference corpus held out from evaluated graphs, while the target model’s predicted class indexes motif contrasts, keeping each graph’s own label out of its explanation.Motifs more common in the predicted class receive positive weight and those more common in the opposite class receive negative weight.Source: E Motif Libraries and Correlation Priors · p. 17
  • A motif’s per-class count is its mean number of subgraph isomorphisms per graph, normalized by library size, so k-star counts grow combinatorially with node degree.On BAMultiShapes, the star statistic reaches 6098.22 while the other two motifs stay below 2.7, making the contrast −3237.94 dominant.Source: E Motif Libraries and Correlation Priors · p. 17
  • Matcher-visible duplicates in MUTAG and PROTEINS have identical statistics; in MUTAG, ignored bond order makes the duplicated motif count twice and doubles its interpretability weight.The reported pairs are ethyl ≡ ethene and benzene_ring ≡ cyclic_butyl in MUTAG, and beta_hairpin ≡ core_clique_helix in PROTEINS.Source: E Motif Libraries and Correlation Priors · pp. 17–18

F The Two-Stage Pipeline

  • The two-stage pipeline takes a target graph and model, budget, metric controls, motif library and prior, similarity function, and sampling sizes, and returns an explanation subgraph.Source: F The Two-Stage Pipeline · p. 19

G The SubgraphX-VGAE and SubgraphX-GNTK Variants

  • For stability scoring, SubgraphX is rerun unchanged on each perturbed graph; VGAE and GNTK variants differ only in perturbation sampling and similarity, so target-graph explanations remain identical.Accordingly, the fidelity and interpretability panels show one SubgraphX curve, while stability panels show two.Source: G The SubgraphX-VGAE and… · p. 19

H Additional Notes on the Experimental Results

These notes qualify how to compare stability scores, interpret the motif-prior ablation, and read the mask-based baseline sweep.

H Additional Notes on the Experimental Results

I Additional Baselines: Full Sweep

  • Top-B mask selections can be disconnected, unlike the connectivity-constrained SubgraphX and proposed searches, so the sweep informs hard-budget metric behavior rather than general explanation-quality rankings.The passage says this depresses all three metrics for mask-based methods, most severely interpretability and next stability.Source: I Additional Baselines: Full Sweep · p. 20

J Seed Variance

The appendix estimates run-to-run variation on fixed dataset subsamples and cautions against treating those estimates as full-dataset error bars; it also reports agreement between GNTK and Figure 2’s trade-off surface.

J Seed Variance

  • Three-seed reruns on fixed 20-graph subsamples cover every budget and both similarity indices, with metric controls at their defaults.Source: J Seed Variance · p. 20
  • Subsample means do not reproduce full-dataset values or provide error bars; with three seeds, standard deviations are imprecise and indicate only the noise scale.Source: J Seed Variance · p. 20
  • Figure 4’s GNTK trade-off surface agrees with Figure 2, which the passage says rules out an artifact of the similarity index.Source: Figure 4 · p. 23

K Trade-off Surface for the GNTK metric

The section presents the Figure 2 trade-off-surface figure for the GNTK metric.

K Trade-off Surface for the GNTK metric

Loading 2609.32436v2…