Paper deep dive
NICE: Scale-Stable Perturbations for Graph Neural Network Explanations via Noise Corruption
Ziluowen Luo, Jun Yin, Ruochen Liu, Ming Cheng, Shirui Pan, Chengqi Zhang, Senzhang Wang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 8/23/2026, 1:18:11 AM
Summary
The paper introduces NICE, a framework for Graph Neural Network (GNN) explanations that addresses 'Scale Drift' caused by Element-wise Masking (EM). NICE uses Noise Corruption (NC) to perturb messages while preserving scale, learns a Stochastic Restoration Boundary (SRB), and generates attributions via Boundary-Integrated Gradient (BIG).
Entities (7)
Relation Signals (5)
NICE → uses → Noise Corruption
confidence 97% · As a scale-stable alternative to EM, we introduce Noise Corruption (NC)... Building on NC, we propose NICE
Element-wise Masking → causes → Scale Drift
confidence 95% · EM suppresses edge-induced messages toward zero, causing deterministic scale contraction... a phenomenon we term Scale Drift.
NICE → learns → Stochastic Restoration Boundary
confidence 94% · NICE... learns a Stochastic Restoration Boundary (SRB) under NC-induced uncertainty
Boundary-Integrated Gradient → converts → Stochastic Restoration Boundary
confidence 93% · Boundary-Integrated Gradient (BIG) converts this boundary into edge attributions
Noise Corruption → preserves → message scale
confidence 92% · NC... perturbs each message through matched-norm random-direction corruption while preserving the expected squared message norm.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Post-hoc Graph Neural Network (GNN) explainers commonly follow a Perturb-Query paradigm, inferring the importance of graph elements based on queried predictions to perturbed inputs. However, such perturbations often introduce substantial distribution shift, undermining the reliability of the queried predictions used to derive explanations. While existing efforts mainly improve perturbed graphs or stabilize model predictions on them, we revisit the perturbation mechanism itself. We show that the widely used Element-wise Masking(EM) suppresses edge-induced messages toward zero, causing deterministic scale contraction that accumulates across message-passing layers, a phenomenon we term Scale Drift. Consequently, prediction changes under EM may conflate information corruption with deviations in propagation scale. As a scale-stable alternative to EM, we introduce Noise Corruption (NC), which perturbs each message through matched-norm random-direction corruption while preserving the expected squared message norm. Building on NC, we propose NICE, a Noise Corruption-based explanation framework, which learns a Stochastic Restoration Boundary (SRB) under NC-induced uncertainty, balancing target-prediction restoration against compactness. Furthermore, Boundary-Integrated Gradient (BIG) converts this boundary into edge attributions by accumulating each edge's contribution to reducing restoration risk along the restoration path. Experiments across multiple benchmarks demonstrate stronger explanation performance and model faithfulness while confirming that NC substantially reduces the Scale Drift induced by masking.
Tags
Links
- Source: https://arxiv.org/abs/2608.16038v1
- Canonical: https://arxiv.org/abs/2608.16038v1
Trouble viewing inline? Open PDF directly →
Full Text
87,494 characters extracted from source content.
Expand or collapse full text
NICE: Scale-Stable Perturbations for Graph Neural Network Explanations via Noise Corruption Ziluowen Luo Jun Yin Ruochen Liu Ming Cheng Shirui Pan Chengqi Zhang Senzhang Wang Abstract Post-hoc Graph Neural Network (GNN) explainers commonly follow a Perturb-Query paradigm, inferring the importance of graph elements based on queried predictions to perturbed inputs. However, such perturbations often introduce substantial distribution shift, undermining the reliability of the queried predictions used to derive explanations. While existing efforts mainly improve perturbed graphs or stabilize model predictions on them, we revisit the perturbation mechanism itself. We show that the widely used Element-wise Masking (EM) suppresses edge-induced messages toward zero, causing deterministic scale contraction that accumulates across message-passing layers, a phenomenon we term Scale Drift. Consequently, prediction changes under EM may conflate information corruption with deviations in propagation scale. As a scale-stable alternative to EM, we introduce Noise Corruption (NC), which perturbs each message through matched-norm random-direction corruption while preserving the expected squared message norm. Building on NC, we propose NICE, a Noise Corruption-based explanation framework, which learns a Stochastic Restoration Boundary (SRB) under NC-induced uncertainty, balancing target-prediction restoration against compactness. Furthermore, Boundary-Integrated Gradient (BIG) converts this boundary into edge attributions by accumulating each edge’s contribution to reducing restoration risk along the restoration path. Experiments across multiple benchmarks demonstrate stronger explanation performance and model faithfulness while confirming that NC substantially reduces the Scale Drift induced by masking. Introduction Graph Neural Networks (GNNs) have achieved remarkable success across a wide range of graph learning tasks (14; 19). However, the decision logic of GNNs remains difficult to understand due to the highly entangled message-passing process over graph structures. Post-hoc GNN explainers therefore aim to identify the graph elements or structures most responsible for a target prediction (29; 15; 25; 32; 26). A broad family of post-hoc explainers follow a Perturb-Query paradigm. As illustrated by Figure 1, an explainer (i) generates element-wise scores, (i) uses them to perturb edge-induced messages during propagation and (i) updates them using the queried predictions (23; 31). The reliability of the resulting explanations thus relys on whether the prediction changes faithfully reflect the message affected by perturbation. This assumption is fragile because perturbed graphs can introduce substantial distribution shift, moving the queried predictions away from the model’s original operating regime and making the resulting prediction changes ambiguous (35; 8; 9). To alleviate this issue, existing methods mainly focus on improving explanation quality through better generation of explanation scores and explainer optimization. For example, they aim to make explanation subgraphs structurally more natural (6), closer to the original graph distribution (7), or equipped with confidence-aware correction mechanisms (33). However, a crucial factor remains underexplored: whether the observed distribution shift is already introduced by the perturbation mechanism itself, before the resulting signals are used to optimize the explainer. Figure 1: Rethinking where the distribution shift enters the Perturb-Query pipeline. Existing efforts focus on ① or ③ (e.g. ProxyExplainer (7)), while this work focuses on ② the perturbation mechanism itself. To isolate whether the perturbation mechanism itself contributes to this shift, we design an experiment using ground-truth explanations as oracle baseline and compare the resulting graph representations with those of the original graph. The discrepancy persists under oracle scores, suggesting that score quality alone does not explain the observed shift. We identify this effect to Element-wise Masking (EM), the default mechanism used to instantiate explanation scores during message passing. As show on the left of Figure 2, EM suppresses edge-induced messages toward zero, coupling information corruption with deterministic scale contraction. As this contraction accumulates across layers, the perturbed computation progressively departs from the clean message-scale regime, a phenomenon we term Scale Drift. Hence, these findings motivate us to explore an alternative perturbation mechanism that corrupts the information carried by messages without explicitly reducing their scale. To this end, we introduce Noise Corruption (NC), a message-level perturbation mechanism that replaces zero-directed masking with matched-norm stochastic corruption. As show on the right of Figure 2, NC combines each clean message with a scale-matched corrupted counterpart through a restoration gate, perturbing the information it carries while preserving its expected squared norm. It therefore defines a scale-stable corruption and restoration space that avoids the deterministic scale collapse of EM. However, since the corrupted counterparts are sampled stochastically, a fixed restoration configuration can produce different queried predictions across forward passes. NC thus provides the perturbation space, but not yet a stable explanation. Figure 2: Comparison NC with EM in the message passing. Building on NC, we propose NICE, a Noise Corruption based explanation framework to address two remaining questions separately: how much messages should be jointly restored under stochastic corruption and how their restoration should be attributed to individual edges. First, Stochastic Restoration Boundary Learning (SRB) learns a compact boundary by balancing the degradation and variation of the original target prediction against restoration compactness. Since the learned gates record restoration degrees rather than their prediction-level contributions, Boundary-Integrated Gradient (BIG) integrates the reduction in stochastic restoration risk along the path from the fully corrupted state to the learned boundary. NICE thus first locates a compact stochastic boundary and then converts the restoration process into attributions. Our main contributions as follows: 1. We identify Scale Drift as a previously overlooked confounding factor in Perturb-Query paradigm, showing that it arises from the widely used masking mechanism. 2. We propose Noise Corruption (NC), a scale-stable alternative which replaces zero-directed masking with matched-norm random-direction corruption, thereby defining a scale-stable corruption and restoration space. 3. Building on NC, we propose NICE, a noise corruption based explanation paradigm that first learns Stochastic Restoration Boundary and then generates explanation scores through Boundary Integrated Gradient. 4. 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. Figure 3: Preliminary experimental results. (a) t-SNE visualization of graph embeddings from the original graph and the same ground-truth explanation instantiated with EM and NC. (b)-(c) Message scale distribution shift across GCN and GIN. (d) Layer-wise mean scale under different perturbation mechanisms. (e) Cross-dataset summary of message-scale statistics. Preliminaries Notation. Let G=(,ℰ)G=(V,E) be an input graph where =v1,v2,…,vnV=\v_1,v_2,…,v_n\ denotes the node set and ℰ⊆×E ×V represents the edge set. In this work, we focus on explaining for graph classification tasks that GNN f(G)∈ℝCf(G) ^C was trained to output its prediction y∗=argmaxcfc(G)y^*= _cf_c(G). At layer l, the GNN computes edge-induced messages and aggregates them to update node representations. For an edge eij=(vi,vj)∈ℰe_ij=(v_i,v_j) , we denote the message between them as i↔j(l)=ϕ(l)(i(l),j(l),eij),m_i j^(l)=φ^(l)(h_i^(l),h_j^(l),e_ij), (1) where (l)h^(l) denotes layer-l node representations and ϕ(l)φ^(l) is the message function. We use the mean squared norm of edge-induced messages as a layer-wise proxy for message scale. (l)(G)=(u,v)∈ℰ[‖u↔v(l)‖22].S^(l)(G)=E_(u,v) [ \|m_u v^(l) \|_2^2 ]. (2) Perturb-and-Query Explanation. Without lossing generality (1; 12), we focus on edge-level explanation that the goal is to assigns each edge e∈ℰe an attribution score se∈[0,1]s_e∈[0,1] to indicate its contribution to the target prediction y∗y^*. A broad family of explainers follows the perturb-and-query paradigm that estimate edge importance by perturbing graph components and querying the response of the fixed target GNN. Since GNN predictions are produced through message passing, we formulate perturbation at the message level. For simplicity, we regard each edge e=(vi,vj)∈ℰe=(v_i,v_j) as a message-passing edge and write e(l):=i↔j(l)m_e^(l):=m_i j^(l). A generic perturbation mechanism operating at the message-passing level can be written as ~e(l)=Ψρe(l)(e(l)), m_e^(l)= _ _e^(l) (m_e^(l) ), (3) where ρe∈[0,1] _e∈[0,1] is an intervention variable controlling how much the message induced by edge e is perturbed and Ψρe(l) _ _e^(l) denotes the corresponding perturbation mechanism. Element-wise Masking. In conventional perturb-query explainers, the intervention variable is commonly implemented as a multiplicative mask on the induced message: ΨEM,ρe(l)(e(l))=ρee(l). _EM, _e^(l) (m_e^(l) )= _em_e^(l). (4) The learned mask coefficient is directly used as the attribution score, i.e., se=ρes_e= _e. This coupling makes edge attribution operationally tied to multiplicative message suppression. In this work, we show that this perturbation mechanism can systematically alter the propagation scale of the target GNN. Rethinking the Perturbation Mechanism In this section, we revisit the distribution shift in perturb-query explanation from the perspective of the perturbation mechanism itself. We first show that shift persists even when perturbations are instantiated from oracle explanations, suggesting that the issue can’t be attributed solely to poor quality. We then trace this shift to element-wise masking which deterministically contracts message scale during propagation. This phenomenon which we call Scale Drift, motivates the need for a scale-stable message perturbation mechanism. Distribution Shift Persists under Oracle Settings Existing efforts mainly attribute unreliable model responses on perturbed graphs to the quality of generated explanations or to the naturalness of perturbed graphs. Accordingly, prior efforts mainly improve the learned explanation scores, make perturbed graphs closer to the data distribution or stabilize the queried model responses after perturbation (27; 6). However, these treatments don’t isolate whether the observed shift is caused by imperfect explanation or by the perturbation mechanism itself. Oracle Experiments. To disentangle these two possibilities, we remove the uncertainty from explanation learning by using ground-truth explanations as oracle explanations. Specifically, we instantiate perturbation directly from the ground-truth explanation and compare the resulting graph representations with those of the original graph. As shown in Figure 3(a), a clear representation shift still appears even under this oracle setting. This observation suggests that the discrepancy is not merely a byproduct of imperfect explanation learning. Even when the selected explanatory structure is correct, the way it is instantiated as a perturbation can still move the target GNN away from its original representation regime. We therefore turn to the perturbation mechanism shared by existing perturb-query explainers. Element-wise Masking Induces Scale Drift Under deletion-oriented perturbations as defined in Eq. 4, reducing message scale is a natural consequence of suppressing an edge. The ambiguity arises when the resulting prediction change is interpreted directly as the information contribution of that edge, because EM jointly removes the edge-specific message signal and its contribution to propagation scale. Scale Drift. This effect is visible in Figure 3 (b,c). Under the same explanation, EM systematically shifts the message scale distribution toward smaller values compared with the original graph. As the contracted messages are repeatedly transformed and propagated across layers, the perturbed computation gradually departs from the original propagation regime. We term this progressive mismatch as Scale Drift. Let ~EM(l)(G) S_EM^(l)(G) denotes the layer-l message scale of the EM-perturbed computations. We denote ηe(l) _e^(l) as the fraction of layer-l scale carried by the message induced by edge e: ηe(l):=‖me(l)‖22/∑a∈ℰ‖ma(l)‖22. _e^(l):=\|m_e^(l)\|_2^2/ _a \|m_a^(l)\|_2^2. (5) The following theorem formalizes EM-induced Scale Drift. Theorem 1 (Layer-wise Scale Contraction under EM). For any layer l, applying EM with coefficients ρe∈[0,1]e∈ℰ\ _e∈[0,1]\_e yields SEM(l)(G)S(l)(G)≤1−∑e∈ℰ(1−ρe2)ηe(l) S_EM^(l)(G)S^(l)(G)≤ 1- _e (1- _e^2) _e^(l) (6) The contraction is strict whenever there exists an edge e such that ηe(l)>0 _e^(l)>0 and ρe<1 _e<1. Proof. See Appendix B. Theorem 1 shows that EM introduces a deterministic scale contraction whenever a message with nonzero scale is suppressed. Repeated contractions across layers lead to the following depth-dependent result. Corollary 2 (Depth-amplified Scale Drift under EM). Under the conditions of Theorem 1, suppose an edge e satisfies ρe∈(0,1) _e∈(0,1) and ηe(l)≥η¯>0 _e^(l)≥ η>0 for all l=1,…,Ll=1,…,L. Then, −∑l=1LlogSEM(l)(G)S(l)(G)≥−Llog[1−(1−ρe2)η¯].- _l=1^L S_EM^(l)(G)S^(l)(G)≥-L \! [1-(1- _e^2) η ]. (7) Hence, the drift grows at least linearly with deeper layers. Proof. See Appendix B. Corollary 2 shows how repeated layer-wise contractions accumulate with depth, providing a mechanism-level explanation for the depth-amplified scale discrepancy observed in Figure 3(d). Empirical Evidence. We empirically examine the above mechanism in Figure 3. Under the same oracle explanation, EM consistently shifts the message-norm distribution toward smaller values than the original graph as shown in (b) and (c). This local contraction further develops into a layer-wise scale gap. As shown in (d), the discrepancy between EM and the original graph becomes more pronounced across GNN layers which is consistent with the depth-amplified behavior. The same pattern also appears across datasets and backbones in (e), suggesting that Scale Drift is not an isolated artifact but a recurring consequence observed across the datasets. Taken together, the oracle analysis, theoretical result, and empirical evidence show that EM introduces a confounding factor into perturb-query explanation. A prediction change under EM may not only reflect the removal of explanatory information, but also arise from the collapse of propagation scale. This ambiguity weakens the reliability of queried model responses, motivating a scale-stable perturbation mechanism that perturbs edge-induced message content without deterministically shrinking message scale. Metric Method Mutag Benzene Alkane Fluoride Indole PAINS R-Count R-Max Rank F1 Random 20.06± 0.55 30.80± 0.40 8.90± 1.09 24.52± 0.43 29.49± 0.10 29.00± 0.23 41.23± 0.08 34.95± 0.47 10 Saliency 49.00± 0.07 47.29± 0.01 0.00± 0.00 48.09± 0.00 50.03± 0.00 49.97± 0.01 37.97± 0.01 46.97± 0.00 6 GuidedBP 37.50± 0.00 45.31± 0.01 15.17± 0.00 41.68± 0.00 42.67± 0.00 51.66± 0.01 38.77± 0.01 47.03± 0.00 5 GNNExplainer 31.79± 1.90 25.88± 1.00 32.16± 2.21 30.95± 0.49 42.22± 0.50 38.97± 0.04 51.50± 0.09 45.80± 1.01 8 PGExplainer 51.67± 0.24 64.96± 0.18 26.39± 0.00 61.79± 0.40 46.65± 0.03 45.98± 0.00 52.65± 0.00 53.17± 0.00 3 Refine 43.60± 0.82 42.88± 0.31 11.48± 0.00 30.36± 2.42 37.39± 0.06 54.18± 0.07 53.73± 0.00 51.67± 0.00 4 D4Explainer 30.68± 0.57 61.91± 0.22 26.58± 0.77 28.25± 1.02 36.29± 0.43 40.50± 0.10 50.96± 0.18 46.80± 1.38 9 ProxyExplainer 36.33± 0.00 49.52± 0.01 14.28± 0.00 38.22± 0.00 38.53± 0.12 37.18± 0.02 50.83± 0.00 51.29± 0.02 7 ConfExplainer 52.19± 0.00 73.45± 0.01 24.99± 0.00 49.97± 0.06 57.82± 0.00 56.04± 0.00 53.27± 0.00 51.97± 0.00 2 NICE (Ours) 53.90± 0.15 78.49± 0.04 27.31± 0.12 65.49± 0.05 68.66± 0.00 59.38± 0.01 59.47± 0.00 58.37± 0.00 1 Recall Random 39.52± 1.33 32.71± 0.31 33.89± 4.29 35.55± 0.73 29.93± 0.13 29.88± 0.34 30.00± 0.06 40.11± 0.32 10 Saliency 90.13± 0.12 50.85± 0.02 0.00± 0.00 69.21± 0.00 53.34± 0.00 54.70± 0.01 27.67± 0.00 57.19± 0.00 5 GuidedBP 70.89± 0.00 48.52± 0.01 56.19± 0.00 57.89± 0.00 44.17± 0.00 53.26± 0.00 28.26± 0.00 56.94± 0.00 7 GNNExplainer 59.37± 3.67 50.71± 2.01 59.99± 4.20 59.65± 1.68 45.68± 0.37 41.29± 0.14 37.99± 0.40 53.24± 1.44 6 PGExplainer 91.52± 0.29 66.77± 0.24 94.69± 0.00 84.97± 0.58 49.43± 0.05 49.43± 0.05 37.89± 0.00 57.87± 0.00 4 Refine 40.24± 0.19 44.72± 0.28 89.38± 0.00 67.07± 1.80 35.91± 0.05 55.58± 0.08 40.62± 0.01 60.03± 0.00 3 D4Explainer 57.15± 1.18 96.83± 0.08 93.95± 1.11 43.15± 1.49 35.30± 0.33 39.79± 0.16 35.40± 0.52 52.26± 0.92 8 ProxyExplainer 56.82± 0.00 52.24± 0.01 50.00± 0.00 56.42± 0.00 38.63± 0.07 40.36± 0.01 35.98± 0.00 57.06± 0.03 9 ConfExplainer 87.99± 0.00 76.38± 0.01 93.36± 0.00 67.91± 0.01 59.87± 0.00 57.56± 0.01 40.26± 0.00 61.17± 0.00 2 NICE (Ours) 93.92± 0.12 82.60± 0.08 97.64± 0.51 88.50± 0.05 76.56± 0.00 61.93± 0.00 44.26± 0.01 68.42± 0.00 1 AUC Random 55.47± 0.72 51.94± 0.24 52.05± 2.24 53.33± 0.40 49.94± 0.08 49.97± 0.21 50.01± 0.11 50.47± 0.19 10 Saliency 84.86± 0.02 64.17± 0.01 34.32± 0.00 73.46± 0.00 66.32± 0.00 67.33± 0.01 45.95± 0.00 67.37± 0.00 4 GuidedBP 73.85± 0.00 62.59± 0.01 63.76± 0.00 66.99± 0.00 60.33± 0.00 66.93± 0.00 46.85± 0.01 67.17± 0.00 8 GNNExplainer 66.84± 2.07 61.68± 1.10 67.22± 2.37 66.78± 1.00 60.92± 0.27 58.12± 0.08 62.97± 0.17 65.33± 0.83 9 PGExplainer 85.55± 0.17 76.40± 0.14 84.03± 0.00 83.50± 0.35 63.84± 0.03 64.44± 0.00 63.53± 0.00 69.15± 0.00 3 Refine 56.38± 0.13 60.44± 0.19 60.18± 0.00 69.99± 1.04 54.79± 0.04 68.90± 0.05 65.65± 0.03 69.91± 0.00 6 D4Explainer 65.40± 0.66 71.36± 0.08 83.68± 0.62 57.74± 0.85 64.08± 0.24 57.36± 0.10 63.25± 0.66 65.09± 0.69 7 ProxyExplainer 66.44± 0.00 65.38± 0.00 60.54± 0.00 65.64± 0.00 76.43± 0.06 57.26± 0.01 63.38± 0.00 68.18± 0.02 5 ConfExplainer 84.24± 0.00 82.74± 0.01 83.25± 0.00 73.34± 0.01 71.66± 0.00 69.93± 0.01 75.49± 0.01 70.71± 0.00 2 NICE (Ours) 87.08± 0.11 86.62± 0.04 85.59± 0.27 85.86± 0.03 82.94± 0.00 76.49± 0.01 83.17± 0.01 84.15± 0.00 1 Table 1: Explanation performance of NICE. We retain the Top30% edges and compare them against ground-truth edges. Results are reported as Mean ± Standard Deviation. The best is bold, and the second-best is underlined. Methodology In this section, We present NICE, a Noise Corruption-based framework that reformulates edge explanation as a stochastic restoration process. Rather than suppressing edge-induced messages toward zero, NICE starts from matched-norm corrupted counterparts and examines how clean-message directions should be restored to recover the original target prediction. Procedurally, NICE consists of three components. First, it defines a scale-stable perturbation space through Noise Corruption (NC), which replaces multiplicative suppression with matched-norm stochastic corruption. Second, Stochastic Restoration Boundary Learning (SRB) interprets the NC coefficient as a restoration gate and learns a compact boundary that preserves the target prediction under stochastic corruption. Third, since this boundary specifies a restoration configuration, Boundary-Integrated Gradients (BIG) decodes it into importance scores by measuring the element-wise contribution along the restoration path. Scale-Stable Noise Corruption The diagnosis above suggests that a desirable alternative should perturb the information carried by edge-induced messages without deterministically shrinking their scale defined in Eq. (2). To this end, NICE introduces Noise Corruption (NC), which replaces zero-directed suppression with matched-norm random-direction corruption. For the message e(l)∈ℝdlm_e^(l) ^d_l induced by edge e at layer l, we sample a corrupted counterpart from the sphere with the same norm: ϵe(l)∼e(l):=Unif(∈ℝdl:‖2=‖e(l)‖2). ε_e^(l) _e^(l):=Unif ( \z ^d_l:\|z\|_2=\|m_e^(l)\|_2 \ ). (8) We use NCP_NC to denote the joint distribution of all corrupted counterparts sampled across edges and message-passing layers in one NC forward pass. Given a restoration gate ρe∈[0,1] _e∈[0,1], NC corrupts the message with the noise: ΨNC,ρe(l)(e(l))=ρee(l)+1−ρeϵe(l). _NC, _e^(l) (m_e^(l) )= _em_e^(l)+ 1- _e ε_e^(l). (9) Here, ρe _e controls how far the message is restored toward its clean direction: ρe=0 _e=0 gives a fully corrupted counterpart, whereas ρe=1 _e=1 recovers the clean message. Therefore, Varying ρe _e defines a continuous restoration path within the matched-norm corruption space. The proposition shows that the restoration path satisfies the scale-stability requirement. Proposition 3 (Scale-Stable Restoration Path under NC). For any fixed message e(l)m_e^(l) and restoration gate ρe∈[0,1] _e∈[0,1], ϵe(l)[‖ΨNC,ρe(l)(e(l))‖22]=‖e(l)‖22.E_ ε_e^(l) [ \| _NC, _e^(l) (m_e^(l) ) \|_2^2 ]= \|m_e^(l) \|_2^2. (10) Proof. The result follows by expanding Eq. (9) and the full proof is provided in Appendix B. By preserving message scale in expectation, NC excludes the systematic scale-shrinkage factor introduced by EM, allowing queried prediction changes to be more directly attributed to the perturbation of edge-induced message information. However, NC alone does not specify an explanation. What remains is to identify a compact configuration of restoration gates whose queried behavior remains sufficiently close to the original target decision under stochastic noise corruption. Stochastic Restoration Boundary Learning Building on the NC restoration path, we formulate the above problem as Stochastic Restoration Boundary Learning (SRB). For the input graph G=(,ℰ)G=(V,E) and its target prediction y∗y^*, we seeks a joint restoration configuration =ρee∈E ρ=\ _e\_e∈ E. As defined in Eq. (9), each ρe _e controls how far the corresponding edge-induced message is restored from its corrupted counterpart toward its clean direction. The objective is to restore only the clean-message directions necessary for maintaining the original target prediction. Restoration Sufficiency under NC. For a fixed restoration configuration ρ, the queried prediction remains stochastic due to each NC forward pass draws corrupted counterparts from NCP_NC. For one NC samples ϵ∼NC ε _NC, let f(G,,ϵ)f(G; ρ, ε) denote the corresponding target-class probability. We measure how well ρ restores the target predictions through We the one-sided target-prediction degradation: dy∗(,ϵ)=[logfy∗(G)−logfy∗(,ϵ)]+.d_y^*( ρ, ε)= [ f_y^*(G)- f_y^*( ρ, ε) ]_+. (11) The deviation is zero when the corrupted computation preserves or strengthens the target-class probability, and increases only when support for the original prediction degrades. It therefore evaluates restoration sufficiency with respect to the target decision without requiring the complete queried output to reproduce the clean prediction. The same restoration configuration may induce different deviations across noise realizations. We account for both their average magnitude and sampling-induced variation through the stochastic restoration error ℛy∗()=ϵ[dy∗(,ϵ)]+βStdϵ[dy∗(,ϵ)],R_y^*( ρ)=E_ ε [d_y^*( ρ, ε) ]+β\,Std_ ε [d_y^*( ρ, ε) ], (12) where β≥0β≥ 0 controls the penalty on corruption-induced variation. A small ℛ()R( ρ) indicates that the target behavior is restored both accurately and consistently under NC. Restoration boundary learning. SRB balances stochastic restoration risk against restoration compactness by: ℒSRB()=ℛy∗()+λrest‖1,L_SRB( ρ)=R_y^*( ρ)+ _rest\| ρ\|_1, (13) where λrest≥0 _rest≥ 0 controls the trade-off between restoring the target prediction and retaining a compact restoration configuration. The resulting stochastic restoration boundary is ⋆=argmin∈[0,1]|ℰ|ℒSRB(). ρ = _ ρ∈[0,1]^|E|L_SRB( ρ). (14) In practice, we estimate ℛy∗()R_y^*( ρ) using N independent NC samples. Let ϵ(n)∼NC ε^(n) _NC and dn=dy∗(,ϵ(n))d_n=d_y^*( ρ, ε^(n)) for n=1,…,Nn=1,…,N. The empirical restoration risk is ℛ^y∗(N)()=d¯N+β1N∑n=1N(dn−d¯N)2,d¯N=1N∑n=1Ndn. R_y^*^(N)( ρ)= d_N+β 1N _n=1^N(d_n- d_N)^2, d_N= 1N _n=1^Nd_n. (15) At each optimization step, we resample the N noise realizations and optimize the empirical counterpart of Eq. 13 by backpropagating through ℛ^y∗(N)() R_y^*^(N)( ρ). Boundary-Integrated Gradient Although SRB yields a compact restoration boundary ⋆ ρ , each ρe⋆ _e only records how much the clean-message direction of edge e is restored under the global restoration objective. To bridge this gap, we propose Boundary-Integrated Gradient (BIG), which integrates this contribution from the fully corrupted state to the learned boundary along: (t)=t⋆,t∈[0,1]. ρ(t)=t ρ , t∈[0,1]. (16) The attribution score of edge e is then computed as seBIG=−ρe⋆∫01∂ℛy∗()∂ρe|=(t)dt.s_e^BIG=- _e _0^1 . _y^*( ρ)∂ _e |_ ρ= ρ(t)dt. (17) The gradient measures how restoring edge e changes the stochastic restoration risk, while the integration accumulates this effect along the restoration path. In practice, we approximate the integral in Eq. 17 using a Riemann sum over T uniformly spaced points along the restoration path, where T denotes the number of integration steps. Experimental Study We design our experiments to answer following questions. RQ1: How effective is NICE in terms of agreement with ground-truth and model faithfulness? RQ2: How do EM and NC differ in their effects on message scale and the resulting explanations? RQ3: Under stochastic NC, can SRB learn a compact restoration boundary that restores the target behavior consistently across noise realizations? RQ4: Is BIG necessary for decoding the learned restoration boundary? Figure 4: Fidelity under different sparsity budgets. We vary the explanation sparsity from Top10% to Top90% and measure the resulting Fidelity. Higher values indicate that the explanation better preserves the target model prediction. Experimental Setup Datasets. Following prior work (24), we We evaluate on eight graph-classification benchmarks with annotated explanatory substructures, including four widely used molecular datasets namely Mutagenicity (Mg), Benzene (Bz), Alkane-Carbonyl (AC) and Fluoride-Carbonyl (FC) (2). Additionally include seven tasks from the more challenging B-XAIC benchmark, namely Indole, PAINS, Rings-Count and Rings-Max (17). Details are provided in Appendix C. Baselines. Three types of baselines are adopted. (1) Reference explainers: GTExplainer which returns the ground-truth explanations as an oracle reference and Random explains randomly as a weak reference. (2) White-box explainers: gradient-based methods including Saliency (20) and GuidedBackprop (21). (3) Black-box explainers: methods follow the Perturb-Query paradigm, including GNNExplainer (11), PGExplainer (5), ReFine (25), D4Explainer (6), ProxyExplainer (7), ConfExplainer (33). More details see Appendix D. Evaluation Protocol. We train a GIN classifier as the target model for graph-classification tasks and explain its predictions. We implement explanation evaluation align with IDEA (28) and reporting Precision, Recall, F1 and AUC-ROC. To assess whether explanations remain faithful to the target model, we further report the widely used Fidelity (35; 16). Implementation Details. Following PGExplainer (15), we parameterize each restoration gate with an MLP over its edge representation and obtain ρe∈[0,1] _e∈[0,1]. The parameters are optimized using Adam with a learning rate of 0.0010.001. By default, we use 1616 NC samples to estimate the restoration risk, set β=0.1β=0.1 and λrest=1.0 _rest=1.0 and approximate BIG with 1616 integration steps. Results are averaged over 55 random seeds. Details are provided in Appendix E. Figure 5: Layer-wise message scale under the same GTExplainer configuration. EM causes persistent message-scale contraction, whereas NC remains closer to the clean computation across datasets and GNN backbones. Overall Explanation Effectiveness (RQ1) We evaluate NICE from two complementary perspectives. Drepr↓D_repr Dpred↓D_pred Dataset Method GT Rand GT Rand R-Count EM 0.31± 0.09 0.63± 0.22 0.57± 0.15 0.59± 0.12 NC 0.07± 0.02 0.08± 0.02 0.02± 0.01 0.04± 0.04 Imp. 77.42% 87.30% 96.49% 93.22% R-Max EM 0.45± 0.10 0.61± 0.11 0.36± 0.16 0.48± 0.18 NC 0.16± 0.03 0.16± 0.04 0.14± 0.05 0.13± 0.06 Imp. 64.44% 73.77% 61.11% 72.92% Table 2: Controlled comparison of EM and NC under GTExplainer and Random. DreprD_repr and DpredD_pred measure representation distance and target-prediction normalized degradation. Imp. denotes the relative reduction ratio. Agreement with Ground-Truth Explanations. Table 1 shows that NICE ranks first on F1, Recall, and AUC-ROC, outperforming the strongest baseline by an average of 6.42%6.42\%, 8.67%8.67\%, and 7.57%7.57\% respectively. Consistent gains are observed regardless of whether tasks are easy or challenging. In particular, the higher Recall and AUC indicate that NICE improves both the coverage and ranking of ground-truth edges, rather than relying on a favorable selection threshold. Faithfulness under Varying Sparsity. Figure 4 shows that NICE is particularly advantageous under small explanation budgets. This indicates that its highest-ranked edges preserve most of the target prediction with only a compact subgraph. As more edges are retained, the performance gap narrows because large budgets reduce the influence of ranking quality. Diagnosing Scale Drift and Evaluating NC (RQ2) We use the same explanations to examine the effects on message scale, graph representations and queried predictions. Depth-amplified Scale Drift under EM. As shown in Figure 5, EM contracts message scale from the first layer and this discrepancy persists or widens through subsequent message-passing layers. This pattern appears across representative datasets and both GCN and GIN backbones, confirming that Scale Drift is a systematic consequence of multiplicative masking rather than an isolated perturbation at a single layer. In contrast, NC remains substantially closer to the clean message-scale trajectory, validating its scale-stable ability. Figure 6: Hyperparameter sensitivity of SRB and BIG. We study the effects of the variation coefficient β, compactness coefficient λrest _rest, NC sample number N, and BIG integration steps T on performance, stability, compactness, and runtime. Representation and prediction effects. Table 2 further compares EM and NC under ground-truth and sparsity-matched random scores. NC reduces the normalized representation distance by 70.9%70.9\% and the target-prediction degradation by 78.8%78.8\%. Importantly, these improvements persist under random scores, indicating that they arise from the perturbation mechanism instead of explanation quality alone. Together, the results show that EM-induced scale drift is accompanied by larger representation and prediction deviations, while NC keeps the perturbed computation closer to the clean regime. Ablation Study (RQ3 & RQ4) We examine whether SRB learns compact restoration boundary and how BIG converts them into attribution scores. Why SRB is necessary. Table 3 verifies the dual objectives of SRB. Removing the variation penalty increases the mean prediction degradation by 61%61\% and its standard deviation by 217%217\%, showing that variation aware optimization boosts restoration quality and stability across NC samples. Without compactness regularization, the restoration ratio increases by 211%211\%, while AUC decreases by 6.9%6.9\%. Thus, restoring more messages can not yield superior explanations; compactness is essential for preventing over-restored boundary. From SRB to BIG. Figure 7 compares the learned restoration boundary ⋆ ρ with sBIGs^BIG on the same graph. While each ρ⋆ρ records how far edge e is restored at the learned boundary. BIG instead accumulates the contribution of the edge to reducing stochastic restoration risk along the restoration path, yielding a sharper ranking over the ground-truth explanatory edges. This comparison illustrating how it converts the joint restoration boundary into edge-level attributions. Sensitivity and Efficiency. Figure 6(a–b) shows clear trade-offs in SRB. Increasing β improves stability across NC samples, whereas an excessively large value reduces attribution quality. Similarly, increasing λrest _rest yields a more compact boundary but eventually compromises target-prediction restoration. Figure 6(c–d) shows that performance quickly saturates as the numbers of NC samples and BIG integration steps increase, whereas runtime continues to grow, supporting the default settings as a favorable trade-off. Figure 7: Case study. Gate scores indicate restoration degrees, whereas BIG more clearly highlights edges. Method Mean ↓ Std. ↓ Rest.↓ AUC ↑ Full SRB 0.23± 0.06 0.06± 0.02 0.27± 0.11 0.87± 0.00 w/o Var. 0.37± 0.08 0.19± 0.07 0.41± 0.13 0.83± 0.06 w/o Comp. 0.25± 0.11 0.09± 0.04 0.84± 0.42 0.81± 0.02 Table 3: Analysis of SRB. Results are averaged over Benzene. Conclusion This work revisits distribution shift in Perturb-Query GNN explanation from the perspective of the perturbation mechanism. We identify Scale Drift, showing that Element-wise Masking couples information corruption with deterministic scale contraction that accumulates across message-passing layers. To avoid this confounding effect, we introduce Noise Corruption, which defines a scale-stable restoration space through matched-norm random-direction corruption. Building on this space, NICE first learns a compact stochastic restoration boundary through SRB and then converts the restoration process into explanation scores through BIG. Experiments demonstrate stronger performance while validating the Scale Drift diagnosis and the scale-stability of NC. References Abrate and Bonchi (2021) C. Abrate and F. Bonchi Counterfactual graphs for explainable classification of brain networks. In ACM SIGKDD Conference on Knowledge Discovery & Data Mining, p. 2495–2504. Cited by: Perturb-and-Query Explanation.. Agarwal et al. (2023) C. Agarwal, O. Queen, H. Lakkaraju, and M. Zitnik Evaluating Explainability for Graph neural Networks. Scientific Data 10. Cited by: Appendix C, Appendix C, Appendix C, Experimental Setup. Bajaj et al. (2021) M. Bajaj, L. Chu, Z. Y. Xue, J. Pei, L. Wang, P. C. Lam, and Y. Zhang Robust counterfactual explanations on graph neural networks. Advances in Neural Information Processing Systems 34, p. 5644–5655. Cited by: Appendix D. Baldassarre and Azizpour (2019) F. Baldassarre and H. Azizpour Explainability techniques for graph convolutional networks. arXiv preprint arXiv:1905.13686. Cited by: Appendix D. Burkart and Huber (2021) N. Burkart and M. F. Huber A survey on the explainability of supervised machine learning. Journal of Artificial Intelligence Research 70, p. 245–317. Cited by: Experimental Setup. Chen et al. (2023) J. Chen, S. Wu, A. Gupta, and R. Ying D4Explainer: In-distribution Explanations of Graph Neural Network via Discrete Denoising Diffusion. In Proceedings of the International Conference on Neural Information Processing Systems, Cited by: Appendix D, Introduction, Distribution Shift Persists under Oracle Settings, Experimental Setup. Chen et al. (2024) Z. Chen, J. Zhang, J. Ni, X. Li, Y. Bian, M. M. Islam, A. Mondal, H. Wei, and D. Luo Generating In-Distribution Proxy Graphs for Explaining Graph Neural Networks. In Proceedings of the International Conference on Machine Learning, Cited by: Appendix D, Figure 1, Introduction, Experimental Setup. Fang et al. (2023a) J. Fang, W. Liu, Y. Gao, Z. Liu, A. Zhang, X. Wang, and X. He Evaluating post-hoc explanations for graph neural networks via robustness analysis. In Advances in Neural Information Processing Systems, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.), Vol. 36, p. 72446–72463. External Links: Link Cited by: Appendix D, Introduction. Fang et al. (2023b) J. Fang, X. Wang, A. Zhang, Z. Liu, X. He, and T. Chua Cooperative explanations of graph neural networks. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, p. 616–624. Cited by: Introduction. Ghorbani et al. (2019) A. Ghorbani, J. Wexler, J. Y. Zou, and B. Kim Towards automatic concept-based explanations. Advances in Neural Information Processing Systems 32. Cited by: Appendix D. Guo et al. (2023) Z. Guo, T. Xiao, C. Aggarwal, H. Liu, and S. Wang Counterfactual learning on graphs: a survey. arXiv preprint arXiv:2304.01391. Cited by: Experimental Setup. He et al. (2022) W. He, M. N. Vu, Z. Jiang, and M. T. Thai An explainer for temporal graph neural networks. In GLOBECOM 2022-2022 IEEE Global Communications Conference, p. 6384–6389. Cited by: Perturb-and-Query Explanation.. Kazius et al. (2005) J. Kazius, R. McGuire, and R. Bursi Derivation and Validation of Toxicophores for Mutagenicity Prediction. Journal of Medicinal Chemistry 48(1). Cited by: Appendix C. Kipf (2016) T. Kipf Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907. Cited by: Introduction. Luo et al. (2020) D. Luo, W. Cheng, D. Xu, W. Yu, B. Zong, H. Chen, and X. Zhang Parameterized Explainer for Graph Neural Network. In Proceedings of the International Conference on Neural Information Processing Systems, Cited by: Appendix D, Introduction, Experimental Setup. Magister et al. (2021) L. C. Magister, D. Kazhdan, V. Singh, and P. Liò Gcexplainer: human-in-the-loop concept-based explanations for graph neural networks. arXiv preprint arXiv:2107.11889. Cited by: Experimental Setup. Proszewska et al. (2025) M. Proszewska, T. Danel, and D. Rymarczyk B-xaic dataset: benchmarking explainable ai for graph neural networks using chemical data. External Links: 2505.22252, Link Cited by: Appendix C, Experimental Setup. Schlichtkrull et al. (2021) M. Schlichtkrull, N. D. Cao, and I. Titov Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking. In International Conference on Learning Representations, Cited by: Appendix D. Shi et al. (2022) F. Shi, Y. Cao, Y. Shang, Y. Zhou, C. Zhou, and J. Wu H2-fdetector: a gnn-based fraud detector with homophilic and heterophilic connections. In Proceedings of the ACM web conference 2022, p. 1486–1494. Cited by: Introduction. Simonyan et al. (2014) K. Simonyan, A. Vedaldi, and A. Zisserman Deep inside convolutional networks: visualising image classification models and saliency maps. External Links: 1312.6034, Link Cited by: Appendix D, Experimental Setup. Springenberg et al. (2015) J. T. Springenberg, A. Dosovitskiy, T. Brox, and M. Riedmiller Striving for simplicity: the all convolutional net. External Links: 1412.6806, Link Cited by: Experimental Setup. Sundararajan et al. (2017) M. Sundararajan, A. Taly, and Q. Yan Axiomatic attribution for deep networks. In International Conference on Machine Learning, p. 3319–3328. Cited by: Appendix D. Tan et al. (2022) J. Tan, S. Geng, Z. Fu, Y. Ge, S. Xu, Y. Li, and Y. Zhang Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning. In Proceedings of the ACM Web Conference 2022, p. 1018–1027. Cited by: Introduction. Wang et al. (2023) S. Wang, J. Yin, C. Li, X. Xie, and J. Wang V-InFoR: A Robust Graph Neural Networks Explainer for Structurally Corrupted Graphs. In Proceedings of the International Conference on Neural Information Processing Systems, Cited by: Appendix D, Experimental Setup. Wang et al. (2021) X. Wang, Y. Wu, A. Zhang, X. He, and T. Chua Towards Multi-Grained Explainability for Graph Neural Networks. In Proceedings of the International Conference on Neural Information Processing Systems, Cited by: Appendix D, Introduction, Experimental Setup. Wu et al. (2021) H. Wu, W. Chen, S. Xu, and B. Xu Counterfactual supporting facts extraction for explainable medical record based diagnosis with graph network. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, p. 1942–1955. Cited by: Introduction. Wu et al. (2022) Y. Wu, X. Wang, A. Zhang, X. He, and T. Chua Discovering Invariant Rationales for Graph Neural Networks. In International Conference on Learning Representations, Cited by: Distribution Shift Persists under Oracle Settings. Yin et al. (2026) J. Yin, S. Wang, Z. Luo, P. Huo, H. Yan, H. Miao, C. Li, S. Pan, and C. Zhang Paradigm shift of GNN explainer from label space to prototypical representation space. In The Fourteenth International Conference on Learning Representations, External Links: Link Cited by: Appendix D, Experimental Setup. Ying et al. (2019a) Z. Ying, D. Bourgeois, J. You, M. Zitnik, and J. Leskovec GNNExplainer: Generating Explanations for Graph Neural Networks. In Proceedings of the International Conference on Neural Information Processing Systems, Cited by: Introduction. Ying et al. (2019b) Z. Ying, D. Bourgeois, J. You, M. Zitnik, and J. Leskovec Gnnexplainer: generating explanations for graph neural networks. Advances in neural information processing systems 32. Cited by: Appendix D. Yuan et al. (2023) H. Yuan, H. Yu, S. Gui, and S. Ji Explainability in graph neural networks: a taxonomic survey. IEEE Trans. Pattern Anal. Mach. Intell. 45 (5), p. 5782–5799. External Links: ISSN 0162-8828, Link, Document Cited by: Introduction. Yuan et al. (2021) H. Yuan, H. Yu, J. Wang, K. Li, and S. Ji On explainability of graph neural networks via subgraph explorations. In International Conference on Machine Learning, p. 12241–12252. Cited by: Appendix D, Introduction. Zhang et al. (2025) J. Zhang, X. Liu, D. Luo, and H. Wei Is your explanation reliable: confidence-aware explanation on graph neural networks. Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2. External Links: Link Cited by: Appendix D, Introduction, Experimental Setup. Zhang et al. (2023) J. Zhang, D. Luo, and H. Wei MixupExplainer: Generalizing Explanations for Graph Neural Networks with Data Augmentation. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Cited by: Appendix D. Zheng et al. (2024) X. Zheng, F. Shirani, T. Wang, W. Cheng, Z. Chen, H. Chen, H. Wei, and D. Luo Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks. In International Conference on Learning Representations, Cited by: Appendix D, Introduction, Experimental Setup. Appendix A A. Notation The main notation is summarized in Table 4 and Table 5. Symbol Description Graph and target GNN G=(,ℰ)G=(V,E) Input graph with node set V and edge set ℰE. =v1,…,vnV=\v_1,…,v_n\ Set of nodes in graph G. ℰ⊆×E ×V Set of edges in graph G. viv_i The i-th node in graph G. eij=(vi,vj)e_ij=(v_i,v_j) Edge between nodes viv_i and vjv_j. C Number of prediction classes. L Number of message-passing layers in GNN. l Index of a layer, l∈1,…,Ll∈\1,…,L\. dld_l Dimension of a message at layer l. i(l)h_i^(l) Representation of node viv_i at layer l. ϕ(l)φ^(l) Message function at layer l. i↔j(l)m_i j^(l) Message between nodes viv_i and vjv_j at layer l. e(l)m_e^(l) Clean message induced by edge e at layer l. f Fixed target GNN being explained. f(G)∈ℝCf(G) ^C Prediction of the target GNN on graph G. fc(G)f_c(G) Predicted score or probability for class c. y⋆y Target class explained by explainer. Explanation and perturbation se∈[0,1]s_e∈[0,1] Attribution score assigned to edge e. =see∈Es=\s_e\_e∈ E Collection of edge-attribution scores. ρe∈[0,1] _e∈[0,1] Intervention coefficient over edge e. =ρee∈E ρ=\ _e\_e∈ E Joint intervention/restoration configuration. Ψρe(l) _ _e^(l) Generic perturbation operator at layer l. ~e(l) m_e^(l) Perturbed message induced by e at layer l. ΨEM,ρe(l) _EM, _e^(l) Element-wise Masking controlled by ρe _e. ΨNC,ρe(l) _NC, _e^(l) Noise Corruption operator controlled by ρe _e. Message scale and Scale Drift (l)(G)S^(l)(G) Layer-wise message scale at layer l. EM(l)(G)S_EM^(l)(G) Layer-wise message scale under EM. NC(l)(G)S_NC^(l)(G) Layer-wise message scale under NC. ηe(l) _e^(l) Fraction of message scale carried by edge e. EM(l)(G)/(l)(G)S_EM^(l)(G)/S^(l)(G) Relative scale retained under EM. Table 4: Summary of notation (Part 1). Appendix B B. Proofs Symbol Description Noise Corruption ϵe(l) ε_e^(l) Matched-norm random corruption of e(l)m_e^(l). e(l)P_e^(l) Distribution of the corrupted message ϵe(l) ε_e^(l). ϵ ε Collection of corruption variables sampled. NCP_NC Joint distribution of corruption variables. f(G,,ϵ)f(G; ρ, ε) GNN prediction under restoration configuration ρ and NC realization ϵ ε. Stochastic Restoration Boundary Learning [x]+[x]_+ Positive-part operator defined as max(x,0) (x,0). dy⋆(,ϵ)d_y ( ρ, ε) Target-prediction degradation under NC. ℛy⋆()R_y ( ρ) Stochastic restoration risk of ρ. β Coefficient of the variation penalty. λrest _rest Coefficient of the compactness penalty. ⋆ ρ Learned stochastic restoration boundary. ρe⋆ _e Restoration degree at the learned boundary. N Number of NC samples. ϵ(n) ε^(n) The n-th independently sampled noise. dnd_n The n-th target-prediction degradation. d¯N d_N Mean target-prediction degradation. ℛ^y⋆(N)() R_y ^(N)( ρ) Estimated empirical restoration risk. ‖1\| ρ\|_1 Regularization boundary compactness. Boundary-Integrated Gradient t∈[0,1]t∈[0,1] The continuous restoration path. (t) ρ(t) Restoration configuration at position t. T Number of numerical integration steps. seBIGs_e^BIG BIG attribution of edge e. Operators and diagnostic metrics ∥⋅∥2\|·\|_2 Euclidean norm. ∥⋅∥1\|·\|_1 ℓ1 _1 norm. ϵ[⋅]E_ ε[·] Expectation over NC realizations. Stdϵ[⋅]Std_ ε[·] Standard deviation over NC realizations. DreprD_repr Graph representations distance. DpredD_pred Degradation of the target prediction. Rest.Rest. Average restoration boundary. Table 5: Summary of notation (Part 2). Statistic Graphs Average Nodes Average Edges Node Features Classes Train/Test Mutag 1,768 ~29.15 ~60.83 14 2 1597/177 Benzene 12,000 ~20.58 ~43.64 14 2 10800/1200 Alkane 1,125 ~21.39 ~45.38 14 2 1012/113 Fluoride 8,671 ~21.36 ~45.37 14 2 7803/868 B-XAIC 5,000 ~34.60 ~75.19 11 2 45000/5000 Table 6: The statistics of the evaluated datasets and the split. Proof of Theorem 1 Recall that the layer-wise message scale is defined as (l)(G)=1|ℰ|∑a∈ℰ‖a(l)‖22.S^(l)(G)= 1|E| _a \|m_a^(l) \|_2^2. (18) To isolate the direct effect of EM at layer l, we hold the incoming layer representations fixed and apply the mask coefficients ρaa∈ℰ\ _a\_a to the resulting messages. By Eq. (4), the masked message induced by edge a is ~a(l)=ρaa(l). m_a^(l)= _am_a^(l). (19) Therefore, the corresponding message scale is EM(l)(G) _EM^(l)(G) =1|ℰ|∑a∈ℰ‖~a(l)‖22 = 1|E| _a \| m_a^(l) \|_2^2 =1|ℰ|∑a∈ℰρa2‖a(l)‖22. = 1|E| _a _a^2 \|m_a^(l) \|_2^2. (20) Dividing Eq. (20) by Eq. (18) gives EM(l)(G)(l)(G) S_EM^(l)(G)S^(l)(G) =∑a∈ℰρa2‖a(l)‖22∑a∈ℰ‖a(l)‖22 = _a _a^2\|m_a^(l)\|_2^2 _a \|m_a^(l)\|_2^2 =∑a∈ℰρa2ηa(l), = _a _a^2 _a^(l), (21) where ηa(l)=‖a(l)‖22∑b∈ℰ‖b(l)‖22. _a^(l)= \|m_a^(l)\|_2^2 _b \|m_b^(l)\|_2^2. (22) Since ∑a∈ℰηa(l)=1 _a _a^(l)=1, we have ∑a∈ℰρa2ηa(l) _a _a^2 _a^(l) =∑a∈ℰ[1−(1−ρa2)]ηa(l) = _a [1-(1- _a^2) ] _a^(l) =1−∑a∈ℰ(1−ρa2)ηa(l). =1- _a (1- _a^2) _a^(l). (23) Because ρa∈[0,1] _a∈[0,1] and ηa(l)≥0 _a^(l)≥ 0, every term (1−ρa2)ηa(l)(1- _a^2) _a^(l) is non-negative. Hence, EM(l)(G)(l)(G)=1−∑a∈ℰ(1−ρa2)ηa(l)≤1. S_EM^(l)(G)S^(l)(G)=1- _a (1- _a^2) _a^(l)≤ 1. (24) Moreover, the inequality is strict whenever there exists an edge a such that ηa(l)>0 _a^(l)>0 and ρa<1 _a<1, because the corresponding term (1−ρa2)ηa(l)(1- _a^2) _a^(l) is then strictly positive. This completes the proof. □ Proof of Corollary 2 Suppose that an edge e is masked with a fixed coefficient ρe∈(0,1) _e∈(0,1) and satisfies ηe(l)≥η¯>0,l=1,…,L. _e^(l)≥ η>0, l=1,…,L. (25) Theorem 1 gives, for every layer l, EM(l)(G)(l)(G) S_EM^(l)(G)S^(l)(G) =1−∑a∈ℰ(1−ρa2)ηa(l) =1- _a (1- _a^2) _a^(l) ≤1−(1−ρe2)ηe(l) ≤ 1-(1- _e^2) _e^(l) ≤1−(1−ρe2)η¯. ≤ 1-(1- _e^2) η. (26) The first inequality follows because all omitted terms are non-negative. Define q=1−(1−ρe2)η¯.q=1-(1- _e^2) η. (27) Since ρe∈(0,1) _e∈(0,1) and η¯>0 η>0, we have 0<q<10<q<1. Because the function −logx- x is monotonically decreasing on (0,∞)(0,∞), Eq. (26) implies −logEM(l)(G)(l)(G)≥−logq.- S_EM^(l)(G)S^(l)(G)≥- q. (28) Summing the above inequality over l=1,…,Ll=1,…,L yields EM(L) _EM^(L) =−∑l=1LlogEM(l)(G)(l)(G) =- _l=1^L S_EM^(l)(G)S^(l)(G) ≥−Llogq ≥-L q =−Llog[1−(1−ρe2)η¯]. =-L [1-(1- _e^2) η ]. (29) The right-hand side is linear in L with a strictly positive coefficient because q∈(0,1)q∈(0,1). Therefore, the cumulative log-scale drift grows at least linearly with the number of message-passing layers. □ Proof of Proposition 3 For brevity, let =e(l)m=m_e^(l), ϵ=ϵe(l) ε= ε_e^(l), and ρ=ρeρ= _e. By the definition of NC, ΨNC,ρ(l)()=ρ+1−ρϵ. _NC,ρ^(l)(m)= ρ\,m+ 1-ρ\, ε. (30) Expanding its squared norm gives ‖ΨNC,ρ(l)()‖22 \| _NC,ρ^(l)(m) \|_2^2 =ρ‖22+(1−ρ)‖ϵ‖22 =ρ\|m\|_2^2+(1-ρ)\| ε\|_2^2 +2ρ(1−ρ)⊤ϵ. +2 ρ(1-ρ)m ε. (31) The corrupted counterpart is sampled uniformly from the sphere :‖2=‖2. \z:\|z\|_2=\|m\|_2 \. (32) Therefore, ‖ϵ‖22=‖22\| ε\|_2^2=\|m\|_2^2 (33) almost surely. Moreover, the uniform distribution on a sphere is symmetric around the origin, and hence ϵ[ϵ]=.E_ ε[ ε]=0. (34) Consequently, ϵ[⊤ϵ]=⊤ϵ[ϵ]=0.E_ ε[m ε]=m E_ ε[ ε]=0. (35) Taking expectation on both sides of Eq. (31), we obtain ϵ[‖ΨNC,ρ(l)()‖22] _ ε [ \| _NC,ρ^(l)(m) \|_2^2 ] =ρ‖22+(1−ρ)‖22 =ρ\|m\|_2^2+(1-ρ)\|m\|_2^2 =‖22. =\|m\|_2^2. (36) Thus, NC preserves the squared message norm in expectation for every restoration gate ρ∈[0,1]ρ∈[0,1]. □ Dataset Target Acc. (%) Positive Ratio (%) Ground-Truth Explanation GT Edge Ratio (%) Mean ± Std. Mutagencity 100.00 36.20 NO2NO X_ [t]2 and NH2NH X_ [t]2 groups 3.78±6.853.78± 6.85 Benzene 93.17 50.00 Benzene ring 13.17±13.6013.17± 13.60 Alkane 100.00 33.33 Alkane chain and C−OC to0.0pt 0.86108pt$-$ -0.86108pt$-$O group 1.46±2.101.46± 2.10 Fluoride 96.31 17.61 Fluorine atom and C−OC to0.0pt 0.86108pt$-$ -0.86108pt$-$O group 2.69±6.042.69± 6.04 Indole 98.68 36.70 Fused benzene–pyrrole structure 11.54±16.8511.54± 16.85 PAINS 91.84 32.94 Detected PAINS alert substructure 10.34±17.0110.34± 17.01 Rings-Count 94.10 30.20 Annotated ring structures 61.00±16.3861.00± 16.38 Rings-Max 96.16 5.65 Ring containing more than six atoms 46.48±17.1546.48± 17.15 Table 7: Predictive performance of the target GINs and statistics of the ground-truth explanations. The GT edge ratio is the proportion of ground-truth explanatory edges among all edges, averaged over the graphs included in explanation evaluation. Appendix C C. Datasets and Target GNNs We evaluate NICE on eight molecular graph-classification benchmarks with ground-truth explanatory structures. The first four are widely used molecular explanation benchmarks, while the remaining four are selected tasks from the B-XAIC benchmark. In all datasets, atoms are represented as graph nodes and chemical bonds as graph edges. Since NICE produces edge-level attributions, we use the annotated bonds belonging to the corresponding chemical patterns as ground-truth explanatory edges. The dataset details are introduced as follows and the dataset statistics are summarized in Table 6. For each dataset, we train an independent GIN classifier as the target model to be explained. Each model uses a hidden dimension of 3232 and is optimized with Adam for at most 1,0001,000 epochs using a learning rate of 0.010.01 and a batch size of 2,0482,048. We employ cross-entropy loss and reduce the learning rate by a factor of 0.50.5 when the validation loss does not improve for 100100 consecutive epochs. The checkpoint with the highest validation accuracy is selected, after which its performance is evaluated once on the held-out test set. Table 7 reports the predictive accuracy of the resulting target GINs together with the positive-label ratio and ground-truth explanation statistics. For each evaluated graph G, we define the ground-truth edge ratio as rGT(G)=|ℰGT(G)||ℰ(G)|,r_GT(G)= |E_GT(G)||E(G)|, (37) where ℰGT(G)E_GT(G) denotes its ground-truth explanatory edges. We report the mean and standard deviation of rGT(G)r_GT(G) over the graphs included in explanation evaluation. The target GINs attain high predictive accuracy across the eight tasks, ensuring that the subsequent experiments evaluate explanation quality rather than classifier failure. Molecular Explanation Benchmarks Mutagenicity. Mutagenicity (13) contains 4,3374,337 molecular graphs labeled according to whether the corresponding compound exhibits mutagenic activity. The annotated nitro and amino functional groups (NO2NO_2 and NH2NH_2) serve as the ground-truth explanations. The dataset contains on average 30.3230.32 nodes and 30.7730.77 edges per graph. Benzene. Benzene (2) is a binary classification dataset containing 12,00012,000 molecular graphs sampled from ZINC15. The task is to determine whether a molecule contains at least one benzene ring. The atoms and bonds forming each detected benzene ring are annotated as the ground-truth explanation. When a molecule contains multiple disjoint benzene rings, each ring is regarded as a valid explanatory structure. The graphs contain on average 20.5820.58 nodes and 43.6543.65 edges. Alkane-Carbonyl. Alkane-Carbonyl (2) contains 4,3264,326 molecular graphs. A molecule receives a positive label when it simultaneously contains an unbranched alkane chain and a carbonyl (C=OC=O) group. The ground-truth explanation is defined as the union of the annotated alkane chain and carbonyl group. The average graph contains 21.1321.13 nodes and 44.9544.95 edges. Fluoride-Carbonyl. Fluoride-Carbonyl (2) consists of 8,6718,671 molecular graphs. A positive molecule must contain both a fluorine atom and a carbonyl (C=OC=O) group. The fluorine atom, the carbonyl group, and their corresponding annotated bonds jointly form the ground-truth explanation. The graphs contain on average 21.3621.36 nodes and 45.3745.37 edges. B-XAIC Tasks B-XAIC (17) is constructed from ChEMBL 35, which contains approximately 2.52.5 million drug-like molecules. Invalid and duplicated SMILES strings are removed, and solvents and counterions are discarded to retain one molecular graph per example. Weighted sampling is then used to obtain 50,00050,000 molecules, which are divided into training, validation, and test sets of 40,00040,000, 5,0005,000, and 5,0005,000 graphs, respectively. The resulting molecular graphs contain 34.5634.56 atoms on average. Each molecule is associated with binary task labels and with atom- and bond-level annotations for the detected chemical patterns. The four tasks below therefore share the same molecular collection but differ in their prediction targets and ground-truth explanations. Indole. The Indole task predicts whether a molecule contains an indole group, i.e., a bicyclic structure consisting of a benzene ring fused with a pyrrole ring. Detecting this relatively large pattern requires information to be propagated across multiple atoms. For positive molecules, the atoms and bonds forming the indole structure constitute the ground-truth explanation. Approximately 36.94%36.94\% of the B-XAIC molecules receive a positive label for this task. PAINS. The PAINS task detects pan-assay interference compounds, whose characteristic substructures are known to produce false-positive outcomes in high-throughput screening. Unlike tasks defined by a single motif, PAINS involves a diverse collection of chemically distinct alert patterns. A molecule is labeled positive when it contains at least one of these patterns, and the atoms and bonds belonging to the detected PAINS substructure form the ground-truth explanation. The positive-label ratio is approximately 32.88%32.88\%. Rings-Count. The Rings-Count task predicts whether a molecule contains more than four rings. It therefore requires not only detecting ring structures but also counting their occurrences within the molecular graph. The atoms and bonds participating in the ring structures relevant to the count are provided as ground-truth explanation annotations. Approximately 30.06%30.06\% of the molecules are positive for this task. Rings-Max. The Rings-Max task predicts whether a molecule contains a ring with more than six atoms. In contrast to Rings-Count, which concerns the number of rings, this task requires determining the size of individual ring structures. For positive instances, the atoms and bonds forming the qualifying large ring constitute the ground-truth explanation. This is the most imbalanced of the four selected B-XAIC tasks, with a positive-label ratio of approximately 5.54%5.54\%. Appendix D D. Related Work Post-hoc GNN Explanation Post-hoc GNN explainers aim to identify the nodes, edges, or subgraphs responsible for a prediction of a trained GNN. Gradient-based methods directly measure prediction sensitivity with respect to graph features or structures (4; 20), whereas search- and decomposition-based methods construct explanatory subgraphs or decompose predictions into structural contributions (32; 18). A prominent line follows the Perturb-Query paradigm, in which graph elements are perturbed and their importance is inferred from the response of the target GNN. GNNExplainer learns an instance-specific soft mask by maximizing mutual information (30), while PGExplainer amortizes mask generation across graph instances (15). ReFine further introduces class-aware explanation generation to capture contrastive structures (25). Despite their different score-generation and optimization strategies, many Perturb-Query explainers instantiate continuous scores through multiplicative suppression of edges or their induced messages. NICE belongs to this general paradigm but revisits the message-level perturbation mechanism used to query the target GNN. Distribution Shift in Perturb-Query Explanation Perturbing a graph may move the queried input or its internal representation away from the operating regime of the target GNN, making prediction changes difficult to interpret (8; 35). Existing methods address this issue at different stages of the explanation pipeline. D4Explainer formulates explanation generation as a discrete denoising process to improve the in-distribution property of generated graphs (6). Mixup-based methods combine explanatory structures with base graphs to reduce the discrepancy between explanation subgraphs and the original data distribution (34). V-InFoR learns robust graph representations under structural corruption (24), while ProxyExplainer constructs in-distribution proxy graphs for querying the target model (7). More recently, IDEA aligns input graphs and explanations in a prototypical representation space (28), and ConfExplainer corrects unreliable query signals through confidence-aware optimization (33). Related studies also revisit how faithfulness should be evaluated when graph perturbations themselves introduce distribution shift (3). These approaches primarily improve the generated explanations, their representations, or the optimization and evaluation of queried predictions. This work examines a complementary source of ambiguity: multiplicative masking simultaneously suppresses edge-specific message signals and contracts propagation scale. We therefore do not regard NC as a smoother approximation to edge deletion. Instead, NICE defines a scale-controlled restoration intervention that measures how restoring clean-message directions contributes to the original target prediction under matched expected message scale. Path-Based Attribution Path-based attribution methods accumulate gradients along a continuous path from a reference state to the input, with Integrated Gradients being a representative approach (22). In graph explanation, gradients with respect to edge weights have also been connected theoretically to perturbation-based and occlusion-based explanations under specific model assumptions (10). BIG adopts the path-integration principle but differs in both its path and attribution objective. It integrates gradients of stochastic restoration risk in the restoration-gate space, from the fully direction-corrupted state to the boundary learned by SRB. Consequently, BIG attributes each edge’s contribution to target-prediction restoration rather than its input sensitivity or deletion effect. Appendix E E. Implement Details This section provides the optimization procedure of Stochastic Restoration Boundary Learning (SRB), the explanation-generation procedure based on Boundary-Integrated Gradient (BIG), and the configurations used in our experiments. Algorithm 1 BIG-Based Explanation Generation 0: Graph G, frozen target GNN f, trained explainer g⋆g_ θ , NC sample number M, and integration steps T 0: Edge-level attribution BIGs^BIG 1: Perform a clean forward pass and obtain y∗=argmaxcfc(G)y^*= _cf_c(G) 2: Compute edge representations ee∈ℰ\z_e\_e 3: Compute the restoration boundary ρe⋆=σ(g⋆(e)) _e =σ(g_ θ (z_e)) 4: for k=1,…,Tk=1,…,T do 5: Set (k)=kT⋆ ρ^(k)= kT ρ 6: Estimate ℛ^y∗((k)) R_y^*( ρ^(k)) using M independent NC samples 7: Compute ∇ℛ^y∗((k)) _ ρ R_y^*( ρ^(k)) 8: end for 9: Compute BIG=−⋆⊙1T∑k=1T∇ℛ^y∗((k))s^BIG=- ρ 1T _k=1^T _ ρ R_y^*( ρ^(k)) 10: Map message-level scores to graph edges and rank them in descending order 11: return BIGs^BIG SRB Training Stage Explainer parameterization. The target GNN is pretrained and remains frozen throughout explainer optimization. For each edge e, we obtain an edge representation ez_e from the hidden representations produced by the target GNN and parameterize its restoration gate as ρe=σ(g(e)), _e=σ (g_ θ(z_e) ), (38) where g_ θ is a multilayer perceptron and σ(⋅)σ(·) is the sigmoid function. The same edge-level restoration gate is used across all message-passing layers. Only the parameters θ of the explainer are updated during SRB training. Stochastic restoration risk estimation. For each graph G, we first perform a clean forward pass to obtain its original target prediction y∗=argmaxcfc(G)y^*= _cf_c(G) (39) and the corresponding target-class probability py∗(G)p_y^*(G). Given the restoration configuration =ρee∈ℰ ρ=\ _e\_e , we sample N independent collections of matched-norm corrupted messages: ϵ(n)∼NC,n=1,…,N. ε^(n) _NC, n=1,…,N. (40) Each collection defines one independent NC forward pass. For the n-th NC sample, the one-sided target-prediction degradation is dn=[logpy∗(G)−logpy∗(,ϵ(n))]+.d_n= [ p_y^*(G)- p_y^* ( ρ, ε^(n) ) ]_+. (41) The empirical stochastic restoration risk is computed as ℛ^y∗(N)()=d¯N+β1N∑n=1N(dn−d¯N)2, R_y^*^(N)( ρ)= d_N+β 1N _n=1^N (d_n- d_N )^2, (42) where d¯N=1N∑n=1Ndn. d_N= 1N _n=1^Nd_n. (43) The NC samples are resampled at every optimization step. Consequently, the explainer is optimized over the distribution of matched-norm corruptions rather than a fixed set of noise samples. Batch-level optimization. For a mini-batch ℬB, we optimize ℒℬ=1|ℬ|∑G∈ℬ[ℛ^y∗(N)(G)+λrest‖G‖1|ℰG|].L_B= 1|B| _G [ R_y^*^(N)( ρ_G)+ _rest \| ρ_G\|_1|E_G| ]. (44) The first term encourages accurate and stable target-prediction restoration across NC samples, whereas the second term penalizes unnecessary restoration. Normalizing the compactness term by the number of edges prevents graph size from changing its effective strength. The explainer parameters are optimized using Adam. After training, the learned restoration configuration for a graph is G⋆=σ(g⋆(e))e∈ℰG. ρ _G= \σ (g_ θ (z_e) ) \_e _G. (45) Each ρe⋆ _e represents the restoration degree of edge e at the learned stochastic restoration boundary; it is not directly used as the final edge attribution. BIG-Based Explanation Generation Once SRB training is complete, the explainer parameters and the target GNN are both fixed. For each graph, we first compute its restoration boundary ⋆ ρ and then use BIG to convert the joint restoration process into edge-level attributions. Restoration path. We construct a linear path in the restoration-gate space: (t)=t⋆,t∈[0,1]. ρ(t)=t ρ , t∈[0,1]. (46) The starting point (0)= ρ(0)=0 corresponds to fully direction-corrupted messages, whereas (1)=⋆ ρ(1)= ρ reaches the learned restoration boundary. The path is linear in the gate space; because NC uses ρe _e in the message transformation, it is not a linear interpolation in the message-vector space. Numerical integration. We approximate the BIG integral using a right-endpoint Riemann sum with T uniformly spaced path points: tk=kT,(k)=tk⋆,k=1,…,T.t_k= kT, ρ^(k)=t_k ρ , k=1,…,T. (47) At every path point, we estimate the gradient of stochastic restoration risk with respect to the restoration gates. The resulting attribution is s^eBIG=−ρe⋆T∑k=1T∂ℛ^y∗()∂ρe|=(k). s_e^BIG=- _e T _k=1^T . ∂ R_y^*( ρ)∂ _e |_ ρ= ρ^(k). (48) The factor ρe⋆ _e accounts for the total displacement of edge e from the fully corrupted state to the learned boundary. The negative sign assigns a positive contribution when restoring the edge reduces stochastic restoration risk. Edge ranking. The BIG scores are computed for all candidate edges and ranked in descending order to obtain the final explanation. For undirected molecular graphs, the two directed message-passing entries corresponding to the same chemical bond share one restoration gate and are mapped back to one bond-level attribution. The resulting scores are used directly for ranking-based metrics, while the Top-k edges are retained for threshold-dependent metrics such as F1, Recall, Precision and Fidelity. Metric Method Mutag Benzene Alkane Fluoride Indole PAINS R-Count R-Max Prec Random 15.58± 0.68 29.90± 0.57 5.17± 0.63 19.23± 0.34 31.46± 0.08 31.74± 0.19 68.52± 0.15 30.96± 1.03 Saliency 38.70± 0.24 44.98± 0.02 0.00± 0.00 37.79± 0.00 51.52± 0.00 52.39± 0.02 63.18± 0.01 41.14± 0.00 GuidedBP 30.74± 0.00 43.35± 0.02 8.86± 0.00 33.73± 0.00 44.85± 0.00 54.74± 0.01 64.43± 0.01 41.67± 0.00 GNNExplainer 24.47± 1.51 19.68± 0.44 24.84± 1.87 23.20± 0.68 43.41± 0.55 42.31± 0.10 85.03± 1.08 42.59± 1.33 PGExplainer 39.74± 0.22 66.20± 0.13 15.53± 0.00 49.96± 0.33 48.76± 0.03 49.00± 0.00 88.02± 0.00 51.15± 0.00 Refine 34.43± 0.75 42.77± 0.47 6.17± 0.00 19.84± 2.11 40.89± 0.08 58.01± 0.05 86.40± 0.08 48.65± 0.00 D4Explainer 23.29± 0.76 47.48± 0.20 15.73± 0.54 21.54± 0.91 39.11± 0.69 43.86± 0.21 92.43± 2.13 44.40± 1.60 ProxyExplainer 30.79± 0.00 48.54± 0.04 8.45± 0.00 29.77± 0.00 40.91± 0.19 38.62± 0.03 89.40± 0.00 48.04± 0.02 ConfExplainer 42.57± 0.00 73.46± 0.01 14.56± 0.00 40.81± 0.06 60.38± 0.00 59.08± 0.01 86.42± 0.00 48.99± 0.00 NICE(Ours) 41.70± 0.19 77.10± 0.05 16.10± 0.07 53.64± 0.04 72.29± 0.00 57.04± 0.00 90.61± 0.00 50.90± 0.00 Table 8: Precision of NICE and the compared baselines. The best result is highlighted in bold, and the second-best result is underlined. Experimental Configuration Target GNNs. We train an independent GIN classifier for each dataset. The target GNN uses a hidden dimension of 3232 and is optimized with Adam using cross-entropy loss. The initial learning rate is 0.010.01, the batch size is 2,0482,048, and the maximum number of training epochs is 1,0001,000. A ReduceLROnPlateau scheduler reduces the learning rate by a factor of 0.50.5 when the validation loss does not improve for 100100 consecutive epochs. The checkpoint with the highest validation accuracy is used as the target model and remains frozen during explanation. NICE configuration. The restoration-gate predictor is optimized using Adam with a learning rate of 0.0010.001. Unless otherwise stated, we use N=16N=16 independent NC samples to estimate the stochastic restoration risk, set the variation coefficient to β=0.1β=0.1, and set the compactness coefficient to λrest=1.0 _rest=1.0. BIG is approximated using T=16T=16 uniformly spaced integration steps. All reported explanation results are averaged over five random seeds. All experiments are finished on a machine with 4 NVIDIA GEFORCE RTX 3090 24GIB GPUs. Figure 8: Fidelity under varying edge-retention ratios on Alkane-Carbonyl and Fluoride-Carbonyl. NICE preserves the target prediction particularly well under compact explanation budgets, while the performance gap gradually narrows as more edges are retained. Higher values indicate better model faithfulness. Appendix F F. Additional Experimental Results Explanation Performance (Precision). Table 8 reports the Precision results. NICE achieves the highest macro-average Precision of 57.42%57.42\%, outperforming the strongest baseline, ConfExplainer, by 4.144.14 percentage points. It ranks first on Benzene, Fluoride, and Indole, and second on Mutag, Alkane, Rings-Count, and Rings-Max, achieving a top-two result on seven of the eight datasets. The improvement is particularly pronounced on Indole, where NICE increases Precision from 60.38%60.38\% to 72.29%72.29\%. Although NICE is slightly behind ConfExplainer and ReFine on PAINS, it remains competitive. Together with the Recall and F1 results in Table 1, these results indicate that the improved coverage of ground-truth explanatory edges does not come at the cost of substantially reduced explanatory selectivity. Figure 9: Distribution of target-class prediction confidence under the original graph, Element-wise Mask (EM), and Noise Corruption (NC) on four representative datasets. For each graph, we instantiate the same ground-truth explanation with EM and NC and record the resulting target-class confidence. Compared with EM, NC generally preserves a confidence distribution that remains closer to the clean computation, while EM more often shifts samples toward low-confidence predictions. Additional fidelity results. Figure 8 extends the fidelity analysis to Alkane-Carbonyl and Fluoride-Carbonyl. On Alkane-Carbonyl, NICE achieves the highest Fidelity under the most compact Top-10%10\% budget and remains among the strongest methods across all retention ratios. The advantage is more pronounced on Fluoride-Carbonyl, where NICE substantially outperforms the baselines at Top-10%10\% and Top-30%30\%. These results indicate that the highest-ranked edges identified by NICE preserve most of the target prediction even when only a small part of the graph is retained. As the retention ratio increases, several baselines gradually catch up because preserving most of the graph reduces the influence of edge-ranking quality. Together with the results in the main text, these curves show that NICE is particularly effective at producing compact and faithful explanations. Appendix G G. Further Analysis of Perturbation Mechanism This experiment further compares the computation induced by Element-wise Masking (EM) and Noise Corruption (NC). Unlike the explanation-performance evaluation, the purpose here is not to determine whether a selected edge configuration is correct. Instead, we hold the edge configuration fixed and examine how the two perturbation primitives affect the graph representation and the original target prediction. Controlled configurations. We evaluate test graphs that are correctly classified by the target GNN, belong to the positive class, and contain a non-empty ground-truth explanation. For each graph, the ground-truth configuration assigns a gate of one to the annotated explanatory edges and zero to the remaining edges. We denote this setting by GT. To distinguish the effect of the perturbation primitive from that of edge selection, we additionally construct sparsity-matched random configurations, denoted by Rand. For each ground-truth configuration, we randomly sample the same number of undirected chemical bonds. The two directed message-passing entries corresponding to the same bond are treated as one edge group. Importantly, the exact same ground-truth or random configuration is instantiated using both EM and NC. EM is deterministic and is evaluated with one forward pass. For NC, we average the results over 5050 independent matched-norm corruption samples for each fixed configuration. We generate 2020 sparsity-matched random configurations for each ground-truth explanation. When multiple ground-truth explanations are available for one graph, their results are first averaged within the graph. The reported mean and standard deviation are then computed across all eligible test graphs. Representation distance. Let (G)h(G) denote the clean graph representation, obtained by applying the target GNN’s readout function to the final-layer node representations. Let ~Ψ(G,,ϵ) h_ (G; ρ, ε) denote the corresponding representation under perturbation primitive Ψ∈EM,NC ∈\EM,NC\. We measure the normalized representation distance by Drepr=‖~Ψ−(G)‖2‖(G)‖2+ε,D_repr= \| h_ -h(G) \|_2 \|h(G) \|_2+ , (49) where ε is a small constant for numerical stability. For NC, Eq. (49) is averaged over the independent corruption samples. A smaller value indicates that the perturbed computation remains closer to the clean graph representation. Target-prediction degradation. Let y∗=argmaxcpc(G)y^*= _cp_c(G) (50) be the original target prediction. We measure the one-sided degradation of its log-probability as Dpred=[logpy∗(G)−logpy∗(,ϵ)]+.D_pred= [ p_y^*(G)- p_y^* ( ρ, ε ) ]_+. (51) The metric is zero when the perturbation preserves or strengthens the target-class probability, and increases only when support for the original prediction decreases. For NC, the reported value is averaged over the independent corruption samples. Lower values are better for both metrics. For each metric D, the relative improvement of NC over EM is computed as Imp.=DEM−DNCDEM×100%.Imp.= D_EM-D_NCD_EM× 100\%. (52) A positive value indicates that NC yields a smaller distance, whereas a negative value indicates that NC produces a larger distance than EM. Drepr↓D_repr Dpred↓D_pred Dataset Method GT Rand GT Rand Mutag EM 0.77± 0.12 0.46± 0.19 0.53± 0.17 0.29± 0.02 NC 0.45± 0.14 0.38± 0.12 0.52± 0.11 0.44± 0.11 Imp. 41.56% 17.39% 1.89% -51.72% Benzene EM 0.03± 0.07 0.11± 0.09 0.77± 0.26 0.38± 0.18 NC 0.03± 0.03 0.06± 0.04 0.74± 0.15 0.43± 0.26 Imp. 00.00% 45.45% 3.90 % -13.16% Alkane EM 0.92± 0.33 0.61± 0.12 0.39± 0.26 0.42± 0.08 NC 0.88± 0.13 0.56± 0.04 0.44± 0.25 0.53± 0.06 Imp. 4.35% 8.20% -12.82% -26.19% Fluoride EM 0.61± 0.17 0.83± 0.21 0.16± 0.16 0.11± 0.12 NC 0.59± 0.11 0.76± 0.24 0.17± 0.15 0.19± 0.16 Imp. 3.28% 8.43% -6.25 % -72.73% Table 9: Controlled comparison of EM and NC under GTExplainer and Random. DreprD_repr and DpredD_pred measure representation distance and target-prediction normalized degradation. Imp. denotes the relative reduction ratio. Results. Table 9 shows a clear difference between the representation- and prediction-level effects of NC. For DreprD_repr, NC yields a lower distance in seven of the eight evaluated configurations and ties EM under the ground-truth configuration on Benzene. The largest reductions occur on Mutag under the ground-truth configuration (41.56%41.56\%) and on Benzene under the random configuration (45.45%45.45\%). Although the gains are smaller on Alkane-Carbonyl and Fluoride-Carbonyl, NC remains consistently closer to the clean representation in both ground-truth and random settings. These results support the intended primitive-level effect of NC: avoiding deterministic scale contraction generally keeps the internal representation closer to the clean computation. The effect on DpredD_pred is less uniform. Under ground-truth configurations, NC slightly reduces the degradation on Mutag and Benzene, but produces moderately larger degradation on Alkane-Carbonyl and Fluoride-Carbonyl. Under random configurations, NC yields larger target-prediction degradation on all four datasets. This result is not inconsistent with the scale-stability property of NC. Preserving the expected squared message norm controls one source of computation shift, but NC still replaces clean message directions with stochastic corrupted directions. The prediction-level effect therefore also depends on the target GNN’s local decision boundary and its sensitivity to the corrupted message information. Together with the results reported in the main text, these findings indicate that the representation-level advantage of NC is substantially more consistent than its unoptimized prediction-level effect. NC should therefore be viewed as defining a scale-controlled corruption and restoration space, rather than as guaranteeing that every fixed corruption configuration preserves the target prediction. This observation further motivates SRB, which explicitly learns a restoration boundary that minimizes target-prediction degradation under NC-induced uncertainty. Prediction Confidence Results. As shown in Figure 9, EM and NC exhibit clearly different confidence profiles. Across all four datasets, the clean computation concentrates a large fraction of samples near high target-class confidence. NC largely preserves this high-confidence regime, although its distribution is slightly broader due to stochastic random-direction corruption. In contrast, EM more frequently shifts samples toward substantially lower confidence, and in Benzene and Rings-Count even produces a pronounced low-confidence mode near zero. This pattern is particularly informative because EM and NC are instantiated on the same ground-truth explanation; hence, the difference cannot be attributed to edge-selection quality. Instead, it reflects the distinct perturbation primitives. Overall, the confidence distributions provide an intuitive behavior-level complement to the distance-based results: NC tends to keep the queried computation closer to the clean prediction regime, whereas EM more readily drives the model into low-confidence responses.