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

cs.LGAug 17, 2026

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

Authors: Ziluowen Luo, Jun Yin, Ruochen Liu, Ming Cheng, Shirui Pan, Chengqi Zhang, Senzhang Wang

Organizations: Central South University · Hong Kong Polytechnic University · Griffith University

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.

Figures & tables

Figure 1: Rethinking where the distribution shift enters the Perturb-Query pipeline. Existing efforts focus on ① or ③ (e.g. ProxyExplainer ( Chen et al. 2024 ) ), while this work focuses on ② the perturbation mechanism itself.

Figure 2: Comparison NC with EM in the message passing.

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.

Metric	Method	Mutag	Benzene	Alkane	Fluoride	Indole	PAINS	R-Count	R-Max	Rank
F1	Random	20.06 $\pm$ 0.55	30.80 $\pm$ 0.40	8.90 $\pm$ 1.09	24.52 $\pm$ 0.43	29.49 $\pm$ 0.10	29.00 $\pm$ 0.23	41.23 $\pm$ 0.08	34.95 $\pm$ 0.47	10
	Saliency	49.00 $\pm$ 0.07	47.29 $\pm$ 0.01	0.00 $\pm$ 0.00	48.09 $\pm$ 0.00	50.03 $\pm$ 0.00	49.97 $\pm$ 0.01	37.97 $\pm$ 0.01	46.97 $\pm$ 0.00	6
	GuidedBP	37.50 $\pm$ 0.00	45.31 $\pm$ 0.01	15.17 $\pm$ 0.00	41.68 $\pm$ 0.00	42.67 $\pm$ 0.00	51.66 $\pm$ 0.01	38.77 $\pm$ 0.01	47.03 $\pm$ 0.00	5
	GNNExplainer	31.79 $\pm$ 1.90	25.88 $\pm$ 1.00	32.16 $\pm$ 2.21	30.95 $\pm$ 0.49	42.22 $\pm$ 0.50	38.97 $\pm$ 0.04	51.50 $\pm$ 0.09	45.80 $\pm$ 1.01	8
	PGExplainer	51.67 $\pm$ 0.24	64.96 $\pm$ 0.18	26.39 $\pm$ 0.00	61.79 $\pm$ 0.40	46.65 $\pm$ 0.03	45.98 $\pm$ 0.00	52.65 $\pm$ 0.00	53.17 $\pm$ 0.00	3
	Refine	43.60 $\pm$ 0.82	42.88 $\pm$ 0.31	11.48 $\pm$ 0.00	30.36 $\pm$ 2.42	37.39 $\pm$ 0.06	54.18 $\pm$ 0.07	53.73 $\pm$ 0.00	51.67 $\pm$ 0.00	4

Table 1: Explanation performance of NICE. We retain the Top30% edges and compare them against ground-truth edges. Results are reported as Mean

\pm

Standard Deviation. The best is bold, and the second-best is underlined.

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.

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.

		$D_{\mathrm{repr}}\downarrow$		$D_{\mathrm{pred}}\downarrow$
Dataset	Method	GT	Rand	GT	Rand
R-Count	EM	0.31 $\pm$ 0.09	0.63 $\pm$ 0.22	0.57 $\pm$ 0.15	0.59 $\pm$ 0.12
	NC	0.07 $\pm$ 0.02	0.08 $\pm$ 0.02	0.02 $\pm$ 0.01	0.04 $\pm$ 0.04
	Imp.	77.42%	87.30%	96.49%	93.22%
R-Max	EM	0.45 $\pm$ 0.10	0.61 $\pm$ 0.11	0.36 $\pm$ 0.16	0.48 $\pm$ 0.18
	NC	0.16 $\pm$ 0.03	0.16 $\pm$ 0.04	0.14 $\pm$ 0.05	0.13 $\pm$ 0.06

Table 2: Controlled comparison of EM and NC under GTExplainer and Random.

D_{\mathrm{repr}}

and

D_{\mathrm{pred}}

measure representation distance and target-prediction normalized degradation. Imp. denotes the relative reduction ratio.

Figure 6: Hyperparameter sensitivity of SRB and BIG. We study the effects of the variation coefficient

\beta

, compactness coefficient

\lambda_{\mathrm{rest}}

, NC sample number

N

, and BIG integration steps

T

on performance, stability, compactness, and runtime.

Figure 7: Case study. Gate scores indicate restoration degrees, whereas BIG more clearly highlights edges.

Method	Mean $\downarrow$	Std. $\downarrow$	Rest. $\downarrow$	AUC $\uparrow$
Full SRB	0.23 $\pm$ 0.06	0.06 $\pm$ 0.02	0.27 $\pm$ 0.11	0.87 $\pm$ 0.00
w/o Var.	0.37 $\pm$ 0.08	0.19 $\pm$ 0.07	0.41 $\pm$ 0.13	0.83 $\pm$ 0.06
w/o Comp.	0.25 $\pm$ 0.11	0.09 $\pm$ 0.04	0.84 $\pm$ 0.42	0.81 $\pm$ 0.02

Table 3: Analysis of SRB. Results are averaged over Benzene.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Description
Graph and target GNN
$G=(\mathcal{V},\mathcal{E})$	Input graph with node set $\mathcal{V}$ and edge set $\mathcal{E}$ .
$\mathcal{V}=\{v_{1},\ldots,v_{n}\}$	Set of nodes in graph $G$ .
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$	Set of edges in graph $G$ .
$v_{i}$	The $i$ -th node in graph $G$ .
$e_{ij}=(v_{i},v_{j})$	Edge between nodes $v_{i}$ and $v_{j}$ .

Appendix

Table 4: Summary of notation (Part 1).

Symbol	Description
Noise Corruption
$\boldsymbol{\epsilon}_{e}^{(l)}$	Matched-norm random corruption of $\mathbf{m}_{e}^{(l)}$ .
$\mathcal{P}_{e}^{(l)}$	Distribution of the corrupted message $\boldsymbol{\epsilon}_{e}^{(l)}$ .
$\boldsymbol{\epsilon}$	Collection of corruption variables sampled.
$\mathcal{P}_{\mathrm{NC}}$	Joint distribution of corruption variables.
$f(G;\boldsymbol{\rho},\boldsymbol{\epsilon})$	GNN prediction under restoration configuration $\boldsymbol{\rho}$ and NC realization $\boldsymbol{\epsilon}$ .

Appendix

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

Appendix

Table 6: The statistics of the evaluated datasets and the split.

Dataset	Target Acc. (%)	Positive Ratio (%)	Ground-Truth Explanation	GT Edge Ratio (%) Mean $\pm$ Std.
Mutagencity	100.00	36.20	${}\mathrm{NO}{\vphantom{\mathrm{X}}}_{\smash[t]{\mathrm{2}}}$ and ${}\mathrm{NH}{\vphantom{\mathrm{X}}}_{\smash[t]{\mathrm{2}}}$ groups	$3.78\pm 6.85$
Benzene	93.17	50.00	Benzene ring	$13.17\pm 13.60$
Alkane	100.00	33.33	Alkane chain and ${}{}\mathrm{C}\hbox to0.0pt{\raisebox{0.86108pt}{{$ - $}}\hss}\raisebox{-0.86108pt}{{$ - $}}\mathrm{O}$ group	$1.46\pm 2.10$
Fluoride	96.31	17.61	Fluorine atom and ${}{}\mathrm{C}\hbox to0.0pt{\raisebox{0.86108pt}{{$ - $}}\hss}\raisebox{-0.86108pt}{{$ - $}}\mathrm{O}$ group	$2.69\pm 6.04$
Indole	98.68	36.70	Fused benzene–pyrrole structure	$11.54\pm 16.85$
PAINS	91.84	32.94	Detected PAINS alert substructure	$10.34\pm 17.01$

Appendix

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.

\mathbf{s}^{\mathrm{BIG}}=-\boldsymbol{\rho}^{\star}\odot\frac{1}{T}\sum_{k=1}^{T}\nabla_{\boldsymbol{\rho}}\widehat{\mathcal{R}}_{y^{*}}(\boldsymbol{\rho}^{(k)})

Appendix

Algorithm 1 BIG-Based Explanation Generation

Metric	Method	Mutag	Benzene	Alkane	Fluoride	Indole	PAINS	R-Count	R-Max
Prec	Random	15.58 $\pm$ 0.68	29.90 $\pm$ 0.57	5.17 $\pm$ 0.63	19.23 $\pm$ 0.34	31.46 $\pm$ 0.08	31.74 $\pm$ 0.19	68.52 $\pm$ 0.15	30.96 $\pm$ 1.03
	Saliency	38.70 $\pm$ 0.24	44.98 $\pm$ 0.02	0.00 $\pm$ 0.00	37.79 $\pm$ 0.00	51.52 $\pm$ 0.00	52.39 $\pm$ 0.02	63.18 $\pm$ 0.01	41.14 $\pm$ 0.00
	GuidedBP	30.74 $\pm$ 0.00	43.35 $\pm$ 0.02	8.86 $\pm$ 0.00	33.73 $\pm$ 0.00	44.85 $\pm$ 0.00	54.74 $\pm$ 0.01	64.43 $\pm$ 0.01	41.67 $\pm$ 0.00
	GNNExplainer	24.47 $\pm$ 1.51	19.68 $\pm$ 0.44	24.84 $\pm$ 1.87	23.20 $\pm$ 0.68	43.41 $\pm$ 0.55	42.31 $\pm$ 0.10	85.03 $\pm$ 1.08	42.59 $\pm$ 1.33
	PGExplainer	39.74 $\pm$ 0.22	66.20 $\pm$ 0.13	15.53 $\pm$ 0.00	49.96 $\pm$ 0.33	48.76 $\pm$ 0.03	49.00 $\pm$ 0.00	88.02 $\pm$ 0.00	51.15 $\pm$ 0.00
	Refine	34.43 $\pm$ 0.75	42.77 $\pm$ 0.47	6.17 $\pm$ 0.00	19.84 $\pm$ 2.11	40.89 $\pm$ 0.08	58.01 $\pm$ 0.05	86.40 $\pm$ 0.08	48.65 $\pm$ 0.00

Appendix

Table 8: Precision of NICE and the compared baselines. The best result is highlighted in bold, and the second-best result is underlined.

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.

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.

		$D_{\mathrm{repr}}\downarrow$		$D_{\mathrm{pred}}\downarrow$
Dataset	Method	GT	Rand	GT	Rand
Mutag	EM	0.77 $\pm$ 0.12	0.46 $\pm$ 0.19	0.53 $\pm$ 0.17	0.29 $\pm$ 0.02
	NC	0.45 $\pm$ 0.14	0.38 $\pm$ 0.12	0.52 $\pm$ 0.11	0.44 $\pm$ 0.11
	Imp.	41.56%	17.39%	1.89%	-51.72%
Benzene	EM	0.03 $\pm$ 0.07	0.11 $\pm$ 0.09	0.77 $\pm$ 0.26	0.38 $\pm$ 0.18
	NC	0.03 $\pm$ 0.03	0.06 $\pm$ 0.04	0.74 $\pm$ 0.15	0.43 $\pm$ 0.26

Appendix

Table 9: Controlled comparison of EM and NC under GTExplainer and Random.

D_{\mathrm{repr}}

and

D_{\mathrm{pred}}

measure representation distance and target-prediction normalized degradation. Imp. denotes the relative reduction ratio.

GNN Explainability

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

See all 82 papers

Towards Faithful Graph Explanations with Synergistic Edge Effects via Granular Balls
Jul 23, 2026Jiancu Chen, Shuyin Xia, Guan Wang +2Graph Neural Networks GNN Explainability
Chongqing Key Laboratory of Computational Intelligence, Key Laboratory of Big Data Intelligent Computing, Key Laboratory of Cyberspace Big Data Intelligent Security, Ministry of Education, School of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing, China · School of Computer Science and Engineering, Chongqing Three Gorges University, Chongqing, China
Why Self-Inconsistency Arises in GNN Explanations and How to Exploit It
May 8, 2026Wenxin Tai, Yaqian Liu, Ting Zhong +1Explanation Stability GNN Explainability
University of Electronic Science and Technology of China
Beyond Soft Masks: Hard-Perturbation Mixup Explainer for Robust GNN Explainability
Jun 4, 2026Jialiang Yin, Zheng Zhao, Linsey Pang +3OOD Generalization GNN Explainability
Xi’an Jiaotong University · Xi’an, China · PayPal +2

Jul 23, 2026J/K move · Enter open · S save

Towards Faithful Graph Explanations with Synergistic Edge Effects via Granular Balls

Jiancu Chen, Shuyin Xia, Guan Wang, Degang Chen+1

Chongqing Key Laboratory of Computational Intelligence, Key Laboratory of Big Data Intelligent Computing, Key Laboratory of Cyberspace Big Data Intelligent Security, Ministry of Education, School of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing, China · School of Computer Science and Engineering, Chongqing Three Gorges University, Chongqing, China

Graph Neural Networks GNN Explainability

Open paper AskPDF arXiv

Instance-level explanations aim to reveal the rationale behind a model's decisions for a specific graph. Previous methods explain graph neural networks (GNNs) by selecting important edges to induce subgraphs, where edge importance is assessed by perturbing each edge and observing changes in the model predictions. However, they often neglect the synergistic effects among edges, which are crucial for accurately characterizing edge importance. To address this issue, we propose SeeExplainer, a parameter-free explainer to interpret GNNs. Specifically, we first introduce a granular-ball graph refinement mechanism that decomposes a graph into several disjoint granular-balls with no fixed size, and utilize them as nodes to construct a structural graph. This process can better capture the synergistic effects among edges. Then, we perturb nodes and edges in the structural graph to generate explanatory subgraphs based on their respective contributions. Experiments on several graph classification datasets of different networks show that SeeExplainer outperforms state-of-the-art baselines.

Abstract

GNN Explainability

Explore similar work

Towards Faithful Graph Explanations with Synergistic Edge Effects via Granular Balls

Why Self-Inconsistency Arises in GNN Explanations and How to Exploit It

Beyond Soft Masks: Hard-Perturbation Mixup Explainer for Robust GNN Explainability