Relevant Walk Search for Explaining Graph Neural Networks

Researchers have proposed a polynomial-time method to identify the most important information pathways inside graph neural networks, addressing a computational bottleneck that previously required exponential effort as networks grew deeper [1]. Graph neural networks have become a standard tool for analyzing data structured as graphs, but explaining their decisions is critical for safety, fairness, and robustness [1]. One established technique, layer-wise relevance propagation for GNNs (GNN-LRP), evaluates the relevance of walks — sequences of connected nodes — to reveal how information flows through the model. These higher-order explanations have been shown to be more informative than simpler node- or edge-level explanations [2]. The problem is that exhaustively identifying the most relevant walks with GNN-LRP demands computational resources that grow exponentially with the network’s depth, limiting its use on large-scale problems [1]. The new work, posted to arXiv on 22 May 2026, replaces that exponential complexity with algorithms that run in polynomial time [1]. The approach adapts the max-product algorithm, a standard method for finding maximum-likelihood configurations in probabilistic graphical models [2]. At the neuron level, the algorithm recovers the most relevant walks exactly; at the coarser node level, it produces an approximation [1]. The concept of tracing influential paths through a network echoes older ideas in graph theory. Centrality measures, first developed in social network analysis, assign scores to nodes or edges to quantify their importance in a structure [3]. Applications range from identifying super-spreaders in epidemiology to mapping key infrastructure in urban networks [3]. The new walk-search method extends this lineage into the domain of deep learning on graphs, where the “important” elements are not static nodes but dynamic, multi-step walks that carry a prediction signal. The authors tested their algorithms on benchmarks spanning epidemiology, molecular science, and natural language, demonstrating performance at scale [1]. The code has been released publicly on GitHub [2]. The work arrives as the broader AI field continues to debate the trade-offs between subsymbolic methods — such as neural networks, which surged after 2012 with the availability of large datasets and GPU computing — and symbolic approaches that emphasize human-readable representations and formal reasoning [4]. Explainability research like this aims to make subsymbolic graph models more transparent without sacrificing their predictive power.