# Relevant Walk Search for Explaining Graph Neural Networks

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 40 references that are in the map.
- First posted on arXiv 22 May 2026.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Axiomatic Attribution for Deep Networks](https://mlsanity.com/paper/1703.01365/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [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)
- [Explainability Techniques for Graph Convolutional Networks](https://mlsanity.com/paper/1905.13686/) (2019)
- [Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking](https://mlsanity.com/paper/2010.00577/) (2020)
- [Higher-Order Explanations of Graph Neural Networks via Relevant Walks](https://mlsanity.com/paper/2006.03589/) (2020)
- [Building and Interpreting Deep Similarity Models](https://mlsanity.com/paper/2003.05431/) (2020)
- [GNNInterpreter: A Probabilistic Generative Model-Level Explanation for Graph Neural Networks](https://mlsanity.com/paper/2209.07924/) (2022)
- [Task-Agnostic Graph Explanations](https://mlsanity.com/paper/2202.08335/) (2022)
- [Temporal Graph Kernels for Classifying Dissemination Processes](https://mlsanity.com/paper/1911.05496/) (2019)
- [L2XGNN: Learning to Explain Graph Neural Networks](https://mlsanity.com/paper/2209.14402/) (2022)

## Built on by (most cited first, 1 of 1)

- [Normalized Relevance Measure as a Unifying Framework to Explain Neural Network Latent Structures](https://mlsanity.com/paper/2606.00557/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have become important machine learning tools for graph analysis, and its explainability is crucial for safety, fairness, and robustness. Layer-wise relevance propagation for GNNs (GNN-LRP) evaluates the relevance of walks to reveal important information flows in the network, and provides higher-order explanations, which have been shown to be superior to the lower-order, i.e., node-/edge-level, explanations. However, identifying relevant walks by GNN-LRP requires em exponential computational complexity with respect to the network depth, which we will remedy in this paper. Specifically, we propose em polynomial-time algorithms for finding top-K relevant walks, which drastically reduces the computation and thus increases the applicability of GNN-LRP to large-scale problems. Our proposed algorithms are based on the max-product algorithm -- a common tool for finding the maximum likelihood configurations in probabilistic graphical models -- and can find the most relevant walks exactly at the neuron level and approximately at the node level. Our experiments demonstrate the performance of our algorithms at scale and their utility across application domains, i.e., on epidemiology, molecular, and natural language benchmarks. We provide our codes under hrefhttps://github.com/xiong-ping/relwalkgnnlrpgithub.com/xiong-ping/relwalkgnnlrp.