# From Binary to Continuous: Stochastic Re-Weighting for Robust Graph Explanation

arXiv: https://arxiv.org/abs/2508.01925 · HTML: https://mlsanity.com/paper/2508.01925/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 23 references that are in the map.
- First posted on arXiv 3 Aug 2025.

## Builds on (most cited first, 19 of 19)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [Explainability in Graph Neural Networks: A Taxonomic Survey](https://mlsanity.com/paper/2012.15445/) (2020)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [XGNN: Towards Model-Level Explanations of Graph Neural Networks](https://mlsanity.com/paper/2006.02587/) (2020)
- [PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2010.05788/) (2020)
- [Graph Information Bottleneck for Subgraph Recognition](https://mlsanity.com/paper/2010.05563/) (2020)
- [Knowledge-aware Graph Neural Networks with Label Smoothness Regularization for Recommender Systems](https://mlsanity.com/paper/1905.04413/) (2019)
- [InfoGCL: Information-Aware Graph Contrastive Learning](https://mlsanity.com/paper/2110.15438/) (2021)
- [AutoGCL: Automated Graph Contrastive Learning via Learnable View Generators](https://mlsanity.com/paper/2109.10259/) (2021)
- [GStarX: Explaining Graph Neural Networks with Structure-Aware Cooperative Games](https://mlsanity.com/paper/2201.12380/) (2022)
- [MixupExplainer: Generalizing Explanations for Graph Neural Networks with Data Augmentation](https://mlsanity.com/paper/2307.07832/) (2023)
- [Higher-Order Networks Representation and Learning: A Survey](https://mlsanity.com/paper/2402.19414/) (2024)
- [MAGE: Model-Level Graph Neural Networks Explanations via Motif-based Graph Generation](https://mlsanity.com/paper/2405.12519/) (2024)
- [On Improving the Cohesiveness of Graphs by Merging Nodes: Formulation, Analysis, and Algorithms](https://mlsanity.com/paper/2306.06368/) (2023)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have achieved remarkable performance in a wide range of graph-related learning tasks. However, explaining their predictions remains a challenging problem, especially due to the mismatch between the graphs used during training and those encountered during explanation. Most existing methods optimize soft edge masks on weighted graphs to highlight important substructures, but these graphs differ from the unweighted graphs on which GNNs are trained. This distributional shift leads to unreliable gradients and degraded explanation quality, especially when generating small, sparse subgraphs. To address this issue, we propose a novel iterative explanation framework which improves explanation robustness by aligning the model's training data distribution with the weighted graph distribution appeared during explanation. Our method alternates between two phases: explanation subgraph identification and model adaptation. It begins with a relatively large explanation subgraph where soft mask optimization is reliable. Based on this subgraph, we assign importance-aware edge weights to explanatory and non-explanatory edges, and retrain the GNN on these weighted graphs. This process is repeated with progressively smaller subgraphs, forming an iterative refinement procedure. We evaluate our method on multiple benchmark datasets using different GNN backbones and explanation methods. Experimental results show that our method consistently improves explanation quality and can be flexibly integrated with different architectures.