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

Jialiang Yin, Zheng Zhao, Linsey Pang, Bo Dong, Bin Shi, Jiaxing ZhangarXiv 2026 · arXiv

TL;DR

Post-hoc Graph Neural Network (GNN) explainers often rely on soft masks that leak label-irrelevant noise, causing severe out-of-distribution (OOD) issues during evaluation. HPME solves this by combining a generalized Graph Information Bottleneck with hard structural perturbations (graph pooling) and a novel structural mixup strategy. This approach cleanly isolates discrete explanatory subgraphs and generates realistic, in-distribution graphs, significantly improving explanation fidelity across both classification and regression tasks.

What Problem Does This Paper Address?

As Graph Neural Networks (GNNs) are increasingly deployed in high-stakes domains like healthcare, fraud detection, and drug discovery, understanding why they make specific predictions is crucial. Instance-level post-hoc explainers attempt to solve this by identifying the most influential subgraphs driving a GNN's decision.

However, most dominant methods rely on soft masks—continuous edge weights optimized via gradient descent. The problem? Soft masks rarely push weights completely to zero, allowing residual, label-irrelevant noise to leak into the explanation. When these noisy or highly sparse subgraphs are evaluated by the GNN, they create a massive Out-of-Distribution (OOD) distribution shift because the GNN was trained on full, well-connected graphs.

While recent methods use "mixup" strategies (blending the explanatory subgraph with a random background graph) to combat this OOD issue, the continuous nature of soft masks allows noise to corrupt the mixup process. Furthermore, standard mixup techniques often wire subgraphs together randomly, creating uninterpretable, synthetic edges that distort the true data distribution.

Figure 1: Intuitive illustration of the OOD problem and mixup strategies. The left part shows two original graphs 𝐺 and 𝐺′ with their corresponding explanatory subgraphs 𝐺∗

Methods

The authors introduce HPME (Hard-Perturbation Mixup Explainer), a framework grounded in a generalized Graph Information Bottleneck (GIB) objective. It features two primary innovations:

  1. Hard Perturbations via Graph Pooling: Instead of learning continuous soft masks, HPME integrates discrete graph pooling layers directly into the optimization process. By dropping label-irrelevant nodes and edges entirely, it enforces a strict information-capacity bound. This mathematically forces the explainer to compress the graph into a clean, discrete explanatory subgraph ($G^*_{pool}$).
  2. Structural Mixup via Replacement: To resolve the OOD dilemma without generating unrealistic graph structures, HPME introduces a structure-level replacement strategy. Given a target graph $G$ and a randomly sampled graph $G'$, HPME extracts their pooled subgraphs and physically swaps them at identical node positions. This preserves natural connectivity and local semantics rather than relying on random edge wiring or soft mathematical blending.

The entire pipeline is optimized using a Binary Cross-Entropy (BCE) alignment loss that forces the learnable explainer network to match the discrete structural reference generated by the hard pooling operator.

Overview of the HPME framework, illustrating the graph pooling, structural mixup, and loss optimization steps.

Datasets

The authors evaluated HPME across 13 diverse datasets spanning graph classification, graph regression, node classification, and link prediction:

  • Synthetic Classification: BA-2Motifs, BA-HouseGrid, BA-HouseAndGrid, SPMotif.
  • Real-World Molecular Classification: Alkane-Carbonyl, Fluoride-Carbonyl, Benzene.
  • Synthetic Regression: BA-Motif-Volume, House-Grid-Volume, BA-Motif-Counting, Triangles, House-OrGrid-Volume.
  • Real-World Molecular Regression: Crippen.

Key Insights and Ideas

  • Hard Beats Soft for Compression: While continuous soft masks are optimization-friendly, they act like a leaky sieve for information bottleneck objectives. Hard discrete choices (via pooling) provide a theoretically grounded way to enforce a true information capacity limit, completely filtering out background noise.
  • Mixup Needs Structural Integrity: Traditional graph mixup methods interpolate feature matrices or randomly connect components, creating uninterpretable "graph monsters." Swapping structurally intact subgraphs at aligned node positions maintains the underlying data distribution.
  • Information Bottleneck Equivalence: The authors theoretically prove that minimizing conditional entropy on their structurally mixed, in-distribution graph is mathematically equivalent to optimizing the true conditional entropy of the isolated explanatory subgraph, successfully bypassing the OOD trap.

Key Results

  • State-of-the-Art Accuracy: HPME consistently outperformed 8 major baselines (including GNNExplainer, PGExplainer, and MixupExplainer). On graph classification tasks, it achieved an average AUC-ROC improvement of 11.39% over the best baseline. On regression tasks, it achieved up to a 30.16% relative improvement in AUC.
  • Distribution Shift Mitigation: Quantitative evaluation using cosine similarity and Euclidean distance of latent representations confirmed that HPME's mixed graphs remain highly faithful to the original graph distribution, far outperforming soft-mask alternatives.

Limitations and Future Work

The primary limitation acknowledged by the authors is that HPME is currently designed and optimized for homogeneous graphs. Extending this generalized GIB framework with hard perturbations to heterogeneous graphs or more complex, multi-relational graph structures represents a vital and promising direction for future research.

Summary updated

Abstract

Graph Neural Networks (GNNs) have demonstrated remarkable performance across a range of applications involving graph-structured data, particularly in high-stakes domains. However, the opaque nature of their decision-making processes limits their trustworthiness and broader adoption. Existing post-hoc explanation methods aim to improve explainability by identifying subgraphs that influence GNN predictions and adopt mixup strategies to alleviate the out-of-distribution (OOD) issue caused by using subgraphs for prediction. Yet, these approaches typically rely on soft masks, which are inherently unable to fully eliminate label-irrelevant information, allowing redundant structures to leak into the mixup process and hindering the resolution of the OOD problem, thereby degrading explanation fidelity. In this work, we propose HPME, a Hard-Perturbation Mixup Explanation framework grounded in a generalized Graph Information Bottleneck, which leverages graph pooling to extract discrete explanatory subgraphs and to yield an information-capacity bound to thoroughly compress label-irrelevant components. Furthermore, we introduce a novel mixup strategy built upon structure-level replacement, generating in-distribution explanations to effectively mitigate the distribution shift. Extensive experiments on diverse tasks demonstrate that HPME achieves state-of-the-art performance in generating robust and interpretable explanations across both synthetic and real-world datasets.
BibTeX
@misc{yin2026beyond,
  author = {Jialiang Yin and Zheng Zhao and Linsey Pang and Bo Dong and Bin Shi and Jiaxing Zhang},
  title = {{Beyond Soft Masks: Hard-Perturbation Mixup Explainer for Robust GNN Explainability}},
  year = {2026},
  eprint = {2606.05756},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.05756},
}

Loading related content...

Figure