PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2608.16038v2cs.LGcs.AI

TL;DR

Perturb-and-query GNN explanations can confound edge information loss with distribution shift and propagation-scale changes caused by masking. NICE replaces masking with scale-stable Noise Corruption and achieves stronger explanation performance across eight benchmarks, including 8.67% higher Recall and 7.57% higher AUC-ROC than the best baseline.

  • Problem

    Perturb-query GNN explanations lack a reliable perturbation mechanism because element-wise masking couples edge-information corruption with deterministic propagation-scale contraction.

  • Method

    NICE uses matched-norm random-direction Noise Corruption, learns a compact Stochastic Restoration Boundary, and derives edge attributions with Boundary-Integrated Gradient.

  • Results

    Across eight benchmarks, NICE improves average Recall and AUC-ROC over the best baseline by 8.67% and 7.57%, respectively, while achieving higher retention fidelity.

  • Takeaways & Limitations

    Noise Corruption substantially reduces masking-induced Scale Drift, while NICE delivers stronger explanation performance and model faithfulness across the evaluated benchmarks.

Abstract

from arXiv · show

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

The introduction identifies Scale Drift from Element-wise Masking as a confounder in Perturb-Query explanations and proposes Noise Corruption as a scale-stable alternative. It then introduces NICE, which uses stochastic restoration boundary learning to produce compact explanations under NC-induced uncertainty.

  • Motivation: Perturbed graphs can cause distribution shift, making prediction changes ambiguous rather than faithful indicators of the messages affected by perturbation.This motivates reconsidering the perturbation mechanism, not only explanation scores or explainer optimization.
  • Scale Drift: Element-wise Masking introduces Scale Drift by deterministically contracting message scales across message-passing layers.The discrepancy persists even with oracle explanation scores, indicating that score quality alone does not explain the shift.
  • Noise Corruption: Noise Corruption replaces zero-directed masking with matched-norm stochastic corruption that preserves each message’s expected squared norm.NC perturbs message information through a scale-matched corrupted counterpart while avoiding deterministic scale collapse.
  • NICE: NICE builds on Noise Corruption by learning a compact Stochastic Restoration Boundary under stochastic corruption.SRB balances degradation and variation of the original target prediction against restoration compactness.

Preliminaries

The paper formulates graph-classification explanations around edge-induced message passing and perturb-and-query attribution. Conventional element-wise masking couples edge scores to multiplicative message suppression, potentially altering the GNN’s propagation scale.

  • Notation: For graph G = (V, E), the GNN predicts y∗ = arg max_c f_c(G) through layer-wise aggregation of edge-induced messages.The mean squared norm of edge-induced messages serves as a layer-wise proxy for message scale.
  • Perturb-and-Query Explanation: Perturb-and-query explainers assign each edge e an attribution score s_e ∈ [0, 1] by perturbing graph components and querying the fixed target GNN.The stated focus is edge-level explanation for graph-classification tasks.
  • Perturb-and-Query Explanation: A message-passing perturbation uses an intervention variable ρ_e ∈ [0, 1] to control how much the message induced by edge e is perturbed.The perturbation mechanism is represented by Ψ^(l)(ρ_e).
  • Element-wise Masking: Element-wise masking implements the intervention as multiplicative suppression of each induced message, with the mask coefficient directly used as the edge attribution score.This coupling makes attribution operationally tied to message suppression and can systematically alter the target GNN’s propagation scale.

Rethinking the Perturbation Mechanism

This section shows that perturbation-induced distribution shift persists even with oracle explanations and traces it to EM’s deterministic contraction of message scale across propagation layers. The resulting Scale Drift confounds information removal with propagation-scale changes, motivating scale-stable perturbations.

  • Oracle Experiments: Distribution shift persists when perturbations use ground-truth explanations, indicating that unreliable queried responses cannot be attributed solely to explanation quality.Oracle perturbations still produce a clear representation shift relative to the original graph.
  • Scale Drift: Element-wise masking suppresses edge-specific messages while simultaneously reducing propagation scale, making prediction changes ambiguous as measures of edge information.Under deletion-oriented perturbations, EM jointly removes the edge message signal and its contribution to propagation scale.
  • Scale Drift: EM systematically shifts message-scale distributions toward smaller values, and repeated contractions across layers progressively move perturbed computations away from the original propagation regime.This progressive mismatch is termed Scale Drift.
  • Scale Drift: EM introduces deterministic scale contraction whenever a nonzero-scale message is suppressed, with repeated layer-wise contractions amplifying the discrepancy as network depth increases.The theoretical results identify depth-amplified Scale Drift as the accumulation of layer-wise contractions.
  • Implications: Prediction changes under EM may reflect propagation-scale collapse in addition to explanatory-information removal, weakening queried-response reliability and motivating scale-stable perturbations.The proposed direction is to perturb edge-induced message content without deterministically shrinking message scale.

Methodology

NICE reformulates edge explanation as stochastic restoration: Noise Corruption preserves message scale while restoration gates recover clean-message directions. Stochastic Restoration Boundary learning selects compact, sufficiently reliable restorations, and Boundary-Integrated Gradient converts them into edge attributions.

  • Noise Corruption: Noise Corruption replaces zero-directed message suppression with matched-norm random-direction corruption, avoiding systematic scale shrinkage from Element-wise Masking.Corrupted counterparts are sampled with the same message norm, while their directions are randomized.
  • Noise Corruption: Restoration gates ρ_e continuously move each corrupted message from a fully corrupted counterpart at ρ_e = 0 toward its clean direction at ρ_e = 1.Varying ρ_e defines a scale-stable restoration path within the matched-norm corruption space.
  • Stochastic Restoration Boundary: Stochastic Restoration Boundary learning balances target-prediction restoration risk under NC against compactness to identify a joint restoration configuration.The risk combines expected one-sided target-prediction degradation with β-weighted variation across noise realizations.
  • Boundary-Integrated Gradient: Boundary-Integrated Gradient assigns edge attributions by integrating each edge’s effect on stochastic restoration risk from the fully corrupted state to the learned boundary.The integral is approximated with a Riemann sum over T uniformly spaced restoration-path points.

Experimental Study

Experiments on graph-classification benchmarks evaluate NICE’s explanation quality, scale stability, restoration boundary, and attribution decoding. NICE improves agreement and faithfulness, while NC reduces masking-induced scale drift and SRB/BIG support stable, compact explanations.

  • Faithfulness under Varying Sparsity: Under small explanation budgets, NICE preserves most of the target prediction with a compact subgraph, showing stronger faithfulness as sparsity varies.Figure 4 evaluates Fidelity from Top10% to Top90% sparsity, where higher values better preserve the target model prediction.
  • Depth-amplified Scale Drift under EM: EM contracts message scale from the first layer, with discrepancies persisting or widening across message-passing depth, whereas NC remains closer to clean computation.The pattern appears across representative datasets and both GCN and GIN backbones, and EM’s drift accompanies larger representation and prediction deviations.
  • Why SRB is necessary: Removing SRB’s variation penalty increases mean prediction degradation by 61% and its standard deviation by 217%, while removing compactness regularization raises restoration ratio by 211% and lowers AUC by 6.9%.These ablations support SRB’s dual objectives of restoration quality, stability across NC samples, and compactness.
  • Sensitivity and Efficiency: Increasing β improves stability until excessive values reduce attribution quality, while increasing λrest improves compactness but eventually compromises restoration; more NC samples and BIG steps quickly saturate performance as runtime grows.The reported tradeoffs support the default settings as a favorable balance of performance and efficiency.

Conclusion · A. Notation

The conclusion reframes distribution shift in Perturb-Query GNN explanation as a perturbation-mechanism problem, identifying Scale Drift and introducing Noise Corruption as a scale-stable alternative. It also presents a notation summary for the paper.

  • Conclusion: The work revisits distribution shift in Perturb-Query GNN explanation through the perturbation mechanism.
  • Conclusion: Element-wise Masking couples information corruption with deterministic scale contraction that accumulates across message-passing layers.
  • Conclusion: This accumulated contraction is identified as Scale Drift.
  • Conclusion: Noise Corruption is introduced to avoid the confounding effect of scale contraction.
  • Conclusion: Noise Corruption defines a scale-stable restoration space through matched-norm random-direction corruption.
  • Conclusion: The paper builds NICE on the scale-stable restoration space defined by Noise Corruption.
  • A. Notation: The notation section provides a summary of notation in Part 1.

B. Proofs … Proof of Proposition 3

The proofs formalize message-scale behavior under element-wise masking and noise corruption, define the stochastic restoration quantities used by NICE, and establish the resulting scale-drift and norm-preservation properties. They also derive the Boundary-Integrated Gradient and show that cumulative masking drift grows with network depth.

  • Proof of Theorem 1: Theorem 1 isolates element-wise masking’s direct effect by fixing incoming representations and applying coefficients {ρ_a} to the resulting edge-induced messages.The proof recalls the layer-wise message scale and expresses the masked message induced by each edge.
  • Proof of Theorem 1: Noise Corruption replaces each message with matched-norm random-direction corruption, using sampled corruption variables and the resulting GNN prediction under restoration configuration ρ.The proof explicitly characterizes the corruption distribution and its realization-dependent prediction.
  • Stochastic Restoration Boundary Learning: Stochastic Restoration Boundary learning defines target-prediction degradation under NC, stochastic restoration risk, variation and compactness penalties, and the learned boundary.The notation also specifies restoration degree, independently sampled noises, mean degradation, empirical risk, and boundary compactness.
  • Boundary-Integrated Gradient: Boundary-Integrated Gradient derives the corresponding message scale by dividing the relevant expressions and establishes a non-negative scale comparison.The inequality is strict when an edge has positive η_a^(l) and a restoration coefficient below one.
  • Proof of Corollary 2: For a fixed masked edge e with ρ_e ∈(0, 1) and η_e^(l) ≥ η > 0 across layers, Theorem 1 yields a per-layer bound on scale drift.The proof uses 0 < q < 1 and the monotonicity of −log x before summing the bound over layers.
  • Proof of Corollary 2: The cumulative log-scale drift grows at least linearly with the number of message-passing layers.The proof states that the bound’s right-hand side is linear in L with a strictly positive coefficient because q ∈(0, 1).
  • Proof of Proposition 3: NC preserves the squared message norm in expectation for every restoration gate ρ ∈[0, 1].The proof expands the squared norm, samples the corrupted counterpart uniformly from a sphere, uses symmetry around the origin, and takes expectations.

C. Datasets and Target GNNs · Molecular Explanation Benchmarks · B-XAIC Tasks

NICE is evaluated on eight molecular graph-classification benchmarks with chemically annotated edge explanations, using independently trained GIN classifiers as target models. The benchmarks comprise four molecular explanation datasets and four B-XAIC tasks spanning motif detection, diverse alerts, and ring-based reasoning.

  • C. Datasets and Target GNNs: NICE evaluates eight molecular graph-classification benchmarks with ground-truth explanatory structures, representing atoms as nodes and chemical bonds as edges.Annotated bonds corresponding to chemical patterns serve as ground-truth explanatory edges for NICE’s edge-level attributions.
  • C. Datasets and Target GNNs: Each dataset uses an independently trained GIN classifier with hidden dimension 32, Adam optimization, learning rate 0.01, batch size 2,048, and up to 1,000 epochs.Learning-rate reduction occurs after 100 epochs without validation-loss improvement, and the highest-validation-accuracy checkpoint is selected.
  • C. Datasets and Target GNNs: The resulting target GINs attain high predictive accuracy across all eight tasks, supporting evaluation of explanation quality rather than classifier failure.Table 7 also reports positive-label ratios and ground-truth explanation statistics, including mean and standard deviation of the ground-truth edge ratio.
  • Molecular Explanation Benchmarks: The four molecular explanation benchmarks cover mutagenicity, benzene-ring detection, alkane-plus-carbonyl detection, and fluoride-plus-carbonyl detection.Their ground-truth explanations are annotated functional groups, rings, or unions of the relevant atoms and bonds.
  • B-XAIC Tasks: B-XAIC is sampled from ChEMBL 35 after cleaning, yielding 50,000 molecular graphs split into 40,000 training, 5,000 validation, and 5,000 test examples.The source contains approximately 2.5 million drug-like molecules before invalid and duplicate structures, solvents, and counterions are removed.
  • B-XAIC Tasks: B-XAIC tasks test indole detection, PAINS alert recognition, counting molecules with more than four rings, and identifying rings exceeding six atoms.Ground-truth explanations consist of the atoms and bonds forming the detected or qualifying substructures.
  • B-XAIC Tasks: The B-XAIC tasks vary substantially in label balance, with positive-label ratios of approximately 36.94%, 32.88%, 30.06%, and 5.54% across the four tasks.Rings-Max is the most imbalanced task, while Indole requires propagation across multiple atoms to detect its fused bicyclic pattern.

D. Related Work … BIG-Based Explanation Generation

The paper situates NICE among post-hoc GNN explainers and distribution-shift remedies, then details SRB optimization and BIG-based edge attribution under noise corruption. The implementation fixes the target GNN, learns stochastic restoration boundaries, and integrates restoration-risk gradients to rank explanatory edges.

  • D. Related Work: Post-hoc GNN explainers identify prediction-relevant nodes, edges, or subgraphs using gradient-, search-, and decomposition-based approaches.
  • D. Related Work: Distribution-shift methods improve explanations, representations, proxy graphs, or queried-prediction reliability at different stages of the Perturb-Query pipeline.
  • D. Related Work: NICE instead addresses multiplicative masking, which suppresses edge-specific messages and contracts propagation scale, through a scale-controlled restoration intervention rather than smoother edge deletion.
  • E. Implement Details: The implementation section specifies the SRB optimization procedure, BIG explanation generation, and experimental configurations.
  • SRB Training Stage: The target GNN remains frozen while an MLP maps each edge representation to a sigmoid restoration gate shared across message-passing layers.
  • SRB Training Stage: SRB estimates stochastic restoration risk from independent matched-norm corruption samples, resampled at every optimization step, and balances target-prediction restoration against edge-normalized compactness.
  • BIG-Based Explanation Generation: BIG follows a linear restoration-gate path from fully direction-corrupted messages to the learned boundary and numerically integrates restoration-risk gradients along it.
  • BIG-Based Explanation Generation: BIG scores represent each edge’s displacement from full corruption to the learned boundary, with positive contribution assigned when restoration reduces risk; scores are ranked for final explanations.

Experimental Configuration

Experiments train independent GIN classifiers with fixed optimization and checkpoint-selection settings, while NICE uses specified stochastic restoration, compactness, and BIG integration configurations.

  • Target GNNs: Target GNNs are independent GIN classifiers with hidden dimension 32, Adam optimization, 0.01 initial learning rate, batch size 2,048, and up to 1,000 epochs.A ReduceLROnPlateau scheduler halves the learning rate after 100 consecutive epochs without validation-loss improvement, and the highest-validation-accuracy checkpoint is selected.
  • NICE configuration: NICE uses Adam at learning rate 0.001, N = 16 NC samples, β = 0.1, λrest = 1.0, and T = 16 BIG integration steps.Explanation results are averaged over five random seeds.

F. Additional Experimental Results

NICE achieves the strongest reported explanation precision, ranking in the top two on seven of eight datasets. It also delivers leading fidelity on additional Alkane-Carbonyl and Fluoride-Carbonyl evaluations, especially under compact edge budgets.

  • Explanation Performance (Precision): 57.42% macroaverage Precision makes NICE the top method, exceeding ConfExplainer by 4.14 percentage points.NICE ranks first on Benzene, Fluoride, and Indole, and second on Mutag, Alkane, Rings-Count, and Rings-Max.
  • Explanation Performance (Precision): NICE improves Indole Precision from 60.38% to 72.29%.This is identified as a particularly pronounced improvement in the reported results.
  • Additional fidelity results: NICE achieves the highest Fidelity on Alkane-Carbonyl at the most compact Top-10% budget and substantially outperforms baselines on Fluoride-Carbonyl at Top-10% and Top30%.It remains among the strongest methods across all retention ratios on Alkane-Carbonyl.

G. Further Analysis of Perturbation Mechanism

The controlled analysis shows that Noise Corruption (NC) more consistently preserves clean graph representations than Element-wise Masking (EM), while its effects on target-prediction degradation are mixed. Confidence profiles likewise indicate that NC better maintains high target-class confidence, motivating restoration-boundary learning rather than assuming every corruption preserves predictions.

  • Representation distance: NC yields lower representation distance than EM in seven of eight configurations, tying EM under Benzene ground truth.The largest reductions are 41.56% on Mutag under ground truth and 45.45% on Benzene under random configurations.
  • Representation distance: NC remains closer to clean representations across both ground-truth and random settings, supporting its intended reduction of deterministic scale contraction.The gains are smaller on Alkane-Carbonyl and Fluoride-Carbonyl but remain consistent.
  • Target-prediction degradation: NC’s target-prediction degradation is less uniform: it slightly improves ground-truth results on Mutag and Benzene but worsens them on the other datasets and under every random configuration.This does not contradict scale stability because norm preservation controls only one source of computation shift while corruption still replaces clean messages.
  • Interpretation and motivation: NC should be interpreted as defining a scale-controlled corruption and restoration space, not as guaranteeing target-prediction preservation for every fixed configuration.This motivates SRB, which explicitly learns a restoration boundary.
  • Prediction confidence: Across all four datasets, NC largely preserves the clean computation’s high-confidence regime, whereas EM more often shifts samples toward substantially lower target-class confidence.NC’s confidence distribution is slightly broader because of stochastic random-direction corruption; EM’s low-confidence shifts are especially noted for Benzene and Rings-Count.
Loading 2608.16038v2…