NICE: Scale-Stable Perturbations for Graph Neural Network Explanations via Noise Corruption

• Perturbed graphs can shift predictions away from the model’s original operating regime, making prediction changes ambiguous and motivating scrutiny of the perturbation mechanism itself.Prior approaches described in the introduction instead improve explanation scores, explainer optimization, or confidence-aware correction.Source: Introduction · p. 1
• Element-wise Masking suppresses edge-induced messages toward zero, causing deterministic scale contraction that accumulates across layers as Scale Drift, even under oracle explanation scores.This suggests score quality alone does not explain the observed representation shift.Source: Introduction · pp. 1–2
• Noise Corruption replaces zero-directed masking with matched-norm random-direction corruption, preserving expected squared message norm while perturbing information.Its stochastic counterparts can produce different queried predictions across forward passes for a fixed restoration configuration.Source: Introduction · p. 2
• Stochastic Restoration Boundary Learning finds a compact restoration boundary by balancing target-prediction degradation and variation against restoration compactness.The learned gates record restoration degrees, not their prediction-level contributions.Source: Introduction · p. 2
• Boundary-Integrated Gradient attributes individual edges by integrating reductions in stochastic restoration risk along the path from full corruption to the learned boundary.Together, SRB and BIG let NICE locate a compact stochastic boundary and turn its restoration process into explanation scores.Source: Introduction · p. 2
• Across eight benchmarks, NICE improves average Recall and AUC-ROC over the best baseline by 8.67% and 7.57%, respectively, and obtains higher retention fidelity.Source: Introduction · p. 2

Notation

• For graph classification, a GNN predicts a target class from a graph by aggregating edge-induced messages to update node representations.The mean squared norm of edge-induced messages serves as a layer-wise proxy for message scale.Source: Preliminaries · p. 2

Perturb-and-Query Explanation

• Perturb-and-query explainers assign each edge an attribution score by perturbing its message and querying the fixed target GNN.The framework treats each edge as a message-passing edge and represents perturbation through an intervention variable and mechanism.Source: Preliminaries · p. 2

Element-wise Masking

• Conventional element-wise masking uses a multiplicative message mask as the edge attribution score, tying attribution to message suppression and potentially altering propagation scale.The mask coefficient is s_e = ρ_e.Source: Preliminaries · p. 2

Distribution Shift Persists under Oracle Settings

• A clear representation shift persists when perturbations are instantiated from ground-truth explanations, showing that imperfect explanation learning alone cannot account for the shift.The oracle experiment compares representations of the original graph with those from perturbations instantiated directly from the ground-truth explanation.Source: Distribution Shift Persists under… · p. 3, Figure 3 · p. 3

Element-wise Masking Induces Scale Drift

• EM deterministically contracts message scale when it suppresses an edge’s message, and repeated contractions amplify Scale Drift with depth, as seen across layers, datasets, and backbones.The depth-amplification result holds under the stated condition that an edge retains a nonzero fraction of message scale across layers; the empirical pattern is reported across datasets and backbones.Source: Element-wise Masking Induces Scale Drift · pp. 3–4, Figure 3 · p. 3
• Because EM removes both an edge-specific message and its contribution to propagation scale, prediction changes may reflect scale collapse as well as loss of explanatory information.This ambiguity makes queried responses less reliable and motivates perturbations that alter message content without deterministically shrinking message scale.Source: Element-wise Masking Induces Scale Drift · pp. 3–4

Methodology

• NICE combines Noise Corruption (NC), Stochastic Restoration Boundary Learning (SRB), and Boundary-Integrated Gradients (BIG) to perturb messages, learn restoration gates, and derive edge importance scores.The framework replaces zero-directed message suppression with matched-norm stochastic corruption, then measures each edge’s contribution along the restoration path.Source: Methodology · p. 4

Scale-Stable Noise Corruption

• NC replaces zero-directed suppression with matched-norm random-direction corruption, while a gate ρ_e continuously restores each corrupted message toward its clean direction.ρ_e = 0 gives the fully corrupted counterpart and ρ_e = 1 recovers the clean message; the restoration path preserves message scale in expectation and excludes EM’s systematic scale shrinkage.Source: Scale-Stable Noise Corruption · p. 4

Stochastic Restoration Boundary Learning

• SRB seeks the clean-message directions needed to preserve the original target prediction using a one-sided degradation measure that does not penalize preserved or strengthened target-class probability.The measure increases only when support for the original target decision degrades, rather than requiring the complete queried output to match the clean prediction.Source: Stochastic Restoration Boundary Learning · p. 4
• SRB balances stochastic restoration risk against compactness, with risk combining average target-prediction degradation and its noise-induced standard deviation.The coefficient β controls the variation penalty, while λ_rest controls the trade-off between restoring the target prediction and retaining a compact restoration configuration.Source: Stochastic Restoration Boundary Learning · pp. 4–5

Boundary-Integrated Gradient

• BIG converts the learned restoration boundary into edge attributions by integrating how each edge’s restoration changes stochastic restoration risk along the path.The integral is approximated with a Riemann sum over T uniformly spaced points.Source: Boundary-Integrated Gradient · p. 5

Experimental Setup

• The evaluation uses a GIN graph classifier, reports Precision, Recall, F1, AUC-ROC, and Fidelity, and averages results over five random seeds.It covers graph-classification benchmarks with annotated explanatory substructures and compares reference, white-box, and black-box explainers; NICE uses 16 NC samples and 16 BIG integration steps by default.Source: Experimental Setup · p. 6

Overall Explanation Effectiveness (RQ1)

• NICE ranks first on F1, Recall, and AUC-ROC, exceeding the strongest baseline by averages of 6.42%, 8.67%, and 7.57%, respectively.Under small explanation budgets, NICE also better preserves target predictions; the performance gap narrows as more edges are retained.Source: Overall Explanation Effectiveness (RQ1) · p. 6

Diagnosing Scale Drift and Evaluating NC (RQ2)

• EM’s message-scale contraction persists or widens across layers, while NC stays closer to clean computation; NC reduces representation distance by 70.9% and prediction degradation by 78.8%.The scale pattern occurs across representative datasets and GCN and GIN backbones; the reductions persist with ground-truth and sparsity-matched random scores.Source: Diagnosing Scale Drift and Evaluating… · pp. 6–7, Table 2 · p. 6, Figure 5 · p. 7

Ablation Study (RQ3 & RQ4)

• Removing SRB’s variation penalty increases mean prediction degradation by 61% and its standard deviation by 217%; removing compactness increases restoration ratio by 211% and decreases AUC by 6.9%.BIG accumulates each edge’s contribution to reducing stochastic restoration risk along the restoration path, producing a sharper ranking over ground-truth explanatory edges than restoration gates alone.Source: Ablation Study (RQ3 & RQ4) · p. 7, Table 3 · p. 7, Figure 7 · p. 7
• Increasing β improves stability across NC samples but can reduce attribution quality, while increasing λrest makes the boundary more compact but can compromise target-prediction restoration.Performance quickly saturates as NC sample count and BIG integration steps increase, while runtime continues to grow, supporting the default settings as a favorable trade-off.Source: Ablation Study (RQ3 & RQ4) · p. 7, Figure 6 · p. 7

Conclusion

• Experiments demonstrate stronger explanation performance while validating the Scale Drift diagnosis and Noise Corruption’s scale-stability.The conclusion reports these outcomes without specifying benchmark comparisons or quantitative results.Source: Conclusion · p. 7
• Element-wise Masking couples information corruption with deterministic scale contraction that accumulates across message-passing layers.The conclusion identifies this confounding effect as Scale Drift.Source: Conclusion · p. 7
• Noise Corruption defines a scale-stable restoration space through matched-norm random-direction corruption.Source: Conclusion · p. 7
• NICE learns a compact stochastic restoration boundary through SRB.Source: Conclusion · p. 7
• NICE converts the restoration process into explanation scores through BIG.Source: Conclusion · p. 7
• The work revisits distribution shift in Perturb-Query GNN explanation from the perspective of the perturbation mechanism.Source: Conclusion · p. 7

A. Notation

• The main notation is summarized in Tables 4 and 5; Table 4 presents Part 1.Source: A. Notation · p. 10, Table 4 · p. 10

Proof of Theorem 1

• Theorem 1’s proof isolates element-wise masking’s direct effect by holding incoming representations fixed and comparing the resulting message scales.The scale comparison is derived after applying mask coefficients to the messages.Source: Proof of Theorem 1 · p. 10
• Theorem 1’s scale inequality is strict when an edge contributes positively and its mask coefficient is below one.The proof identifies the corresponding term as strictly positive under these conditions.Source: Proof of Theorem 1 · p. 11

Proof of Corollary 2

• For an edge e masked with a fixed coefficient ρ_e in (0, 1), suppose its contribution satisfies e ≥ η > 0 at every layer l = 1, …, L.Source: Proof of Corollary 2 · p. 11
• The cumulative log-scale drift grows at least linearly with the number of message-passing layers under Corollary 2’s conditions.The proof sums the per-layer inequality; its linear coefficient is strictly positive.Source: Proof of Corollary 2 · p. 11

Proof of Proposition 3

• Proposition 3 derives the corrupted message’s squared norm by expanding it and using the sphere-sampled corruption’s symmetry around the origin.The corrupted counterpart is sampled uniformly from the sphere and has fixed norm almost surely.Source: Proof of Proposition 3 · p. 11
• Noise corruption preserves the squared message norm in expectation for every restoration gate ρ ∈ [0, 1].The proof obtains this result by taking expectations of the expanded squared norm.Source: Proof of Proposition 3 · p. 11

C. Datasets and Target GNNs

• The eight benchmarks use atoms as nodes, bonds as edges, and annotated chemical-pattern bonds as ground-truth explanations for NICE’s edge-level attributions.The first four are widely used molecular explanation benchmarks; the remaining four are selected B-XAIC tasks.Source: C. Datasets and Target GNNs · pp. 11–12
• Target GINs achieve high predictive accuracy across all eight tasks, supporting evaluation of explanation quality rather than classifier failure.Each dataset has an independently trained GIN with hidden dimension 32, optimized using Adam and cross-entropy; the highest-validation-accuracy checkpoint is evaluated on the held-out test set.Source: C. Datasets and Target GNNs · p. 12

Molecular Explanation Benchmarks

• Mutagenicity labels compounds by mutagenic activity and uses nitro and amino groups as explanations; Benzene labels molecules containing a benzene ring and annotates each detected ring (Kazius, McGuire, and Bursi 2005; Agarwal et al. 2023).The datasets contain 4,337 and 12,000 graphs, respectively; disjoint benzene rings are each considered valid explanations.Source: Molecular Explanation Benchmarks · p. 12
• Alkane-Carbonyl positives contain both an unbranched alkane chain and a carbonyl, while Fluoride-Carbonyl positives contain both fluorine and carbonyl groups (Agarwal et al. 2023).Explanations comprise the annotated chain and carbonyl for Alkane-Carbonyl, and the fluorine atom, carbonyl group, and corresponding bonds for Fluoride-Carbonyl.Source: Molecular Explanation Benchmarks · p. 12

B-XAIC Tasks

• B-XAIC derives 50,000 molecules from ChEMBL 35 and splits them into 40,000 training, 5,000 validation, and 5,000 test graphs with atom- and bond-level pattern annotations (Proszewska, Danel, and Rymarczyk 2025).The four tasks share this collection, whose graphs average 34.56 atoms, but use different prediction targets and explanations.Source: B-XAIC Tasks · p. 12
• Indole predicts whether a molecule contains an indole group—a benzene ring fused with pyrrole—while PAINS labels molecules positive when they contain at least one of diverse alert patterns.For both tasks, atoms and bonds of the detected structure form the ground-truth explanation. Positive-label ratios are approximately 36.94% for Indole and 32.88% for PAINS.Source: B-XAIC Tasks · pp. 12–13
• Rings-Count predicts whether a molecule contains more than four rings, requiring detection and counting; participating ring atoms and bonds are ground-truth explanations, and approximately 30.06% of molecules are positive.Rings-Max predicts whether a molecule has a ring with more than six atoms; qualifying ring atoms and bonds are ground-truth explanations. Its positive-label ratio is approximately 5.54%, making it the most imbalanced of the four selected B-XAIC tasks.Source: B-XAIC Tasks · p. 13

D. Related Work

• Perturb-Query explainers infer graph-element importance from target-GNN responses to perturbations, often using multiplicative edge or message suppression; NICE revisits this mechanism.NICE treats matched-scale restoration as distinct from smoothing edge deletion, measuring how restoring clean-message directions contributes to the original prediction.Source: D. Related Work · p. 13
• Prior shift remedies change generated graphs, representations, proxy queries, or optimization; NICE instead controls the scale ambiguity caused by multiplicative masking.Related work also examines faithfulness evaluation under perturbation-induced distribution shift (Bajaj et al. 2021).Source: D. Related Work · p. 13

BIG-Based Explanation Generation

• BIG integrates stochastic restoration-risk gradients from fully direction-corrupted messages to the learned boundary, attributing edges by their contribution to restoring the target prediction.Its path is linear in restoration-gate space, and restoring an edge that reduces risk receives a positive contribution.Source: D. Related Work · p. 13, BIG-Based Explanation Generation · p. 14

E. Implement Details

• The implementation section covers SRB optimization, BIG-based explanation generation, and experimental configurations.Source: E. Implement Details · p. 13

SRB Training Stage

• SRB uses edge representations from a frozen pretrained target GNN to predict restoration gates, shared across message-passing layers, and updates only explainer parameters.The edge-level gate is the learned restoration degree, not the final attribution.Source: SRB Training Stage · pp. 13–14
• SRB estimates target-prediction restoration risk from independent matched-norm corruption samples, resampling noise at every optimization step.This trains the explainer over the corruption distribution rather than a fixed noise set.Source: SRB Training Stage · p. 14
• SRB balances accurate, stable target-prediction restoration across NC samples against compactness, with the compactness penalty normalized by edge count.The normalization prevents graph size from changing the penalty’s effective strength.Source: SRB Training Stage · p. 14

BIG-Based Explanation Generation

• BIG ranks candidate edges by attribution score and maps paired directed messages to one bond attribution for undirected molecular graphs.Top-k edges are retained for threshold-dependent metrics, while scores are used directly for ranking-based metrics.Source: BIG-Based Explanation Generation · p. 14

Experimental Configuration

• Each dataset uses an independently trained GIN with hidden dimension 32, Adam, cross-entropy, learning rate 0.01, batch size 2,048, and up to 1,000 epochs; the best-validation-accuracy checkpoint is frozen for explanation.ReduceLROnPlateau halves the learning rate after 100 consecutive epochs without validation-loss improvement.Source: Experimental Configuration · p. 15
• NICE uses Adam at learning rate 0.001, N = 16 NC samples, β = 0.1, λrest = 1.0, and T = 16 BIG integration steps; explanation results average five random seeds.Experiments ran on four NVIDIA GeForce RTX 3090 24 GiB GPUs.Source: Experimental Configuration · p. 15
• NICE preserves target predictions particularly well under compact explanation budgets on Alkane-Carbonyl and Fluoride-Carbonyl, with the fidelity gap narrowing as more edges are retained.Higher values indicate better model faithfulness.Source: Figure 8 · p. 15

Explanation Performance (Precision)

• NICE reaches 57.42% macroaverage Precision, beating ConfExplainer by 4.14 percentage points and ranking in the top two on seven of eight datasets.On Indole, NICE raises Precision from 60.38% to 72.29%; it is slightly behind ConfExplainer and ReFine on PAINS. Together with Recall and F1 results in Table 1, the results indicate improved ground-truth edge coverage without substantially reduced selectivity.Source: F. Additional Experimental Results · p. 15

Additional fidelity results

• On Alkane-Carbonyl, NICE leads at Top-10%; on Fluoride-Carbonyl, it substantially outperforms baselines at Top-10% and Top30%.The highest-ranked edges preserve most of the target prediction when only a small part of the graph is retained, while several baselines catch up as retention increases.Source: F. Additional Experimental Results · p. 15

Controlled configurations

• The comparison holds edge selection fixed using identical GT or sparsity-matched Rand configurations instantiated under EM and NC, isolating perturbation effects from explanation quality.Eligible graphs are correctly classified positive test graphs with non-empty ground-truth explanations; Rand matches the number of undirected chemical bonds.Source: G. Further Analysis of Perturbation… · pp. 15–16

Prediction Confidence Results

• Figure 9 shows NC largely retains clean high target-class confidence across four datasets, while EM shifts more samples low, including near-zero modes on Benzene and Rings-Count.The comparison uses the same ground-truth explanation under both perturbation primitives, so the difference reflects the primitive rather than edge-selection quality.Source: Figure 9 · p. 16, G. Further Analysis of Perturbation… · p. 17

Results

• For Drepr, NC is lower in seven of eight configurations and ties EM on Benzene GT; the largest reductions are 41.56% on Mutag GT and 45.45% on Benzene Rand.These results indicate that NC more consistently keeps internal representations closer to clean computation.Source: Table 9 · p. 16, G. Further Analysis of Perturbation… · pp. 16–17
• For Dpred, NC slightly lowers degradation on Mutag and Benzene under GT, raises it moderately on Alkane-Carbonyl and Fluoride-Carbonyl, and raises it on all four Rand datasets.Expected squared message-norm preservation controls one source of shift, but stochastic direction changes leave prediction effects dependent on the model’s local decision boundary and sensitivity.Source: G. Further Analysis of Perturbation… · p. 17
• NC defines a scale-controlled corruption and restoration space, not a guarantee that every fixed corruption configuration preserves the target prediction; this motivates SRB’s learned restoration boundary.The boundary explicitly minimizes target-prediction degradation under NC-induced uncertainty.Source: G. Further Analysis of Perturbation… · p. 17