# Higher-Order Explanations of Graph Neural Networks via Relevant Walks

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

## Key facts

- Cited by 138 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2020.

## Built on by (most cited first, 30 of 138)

- [From Attribution Maps to Human-Understandable Explanations through Concept Relevance Propagation](https://mlsanity.com/paper/2206.03208/) (2022)
- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [XAI for Transformers: Better Explanations through Conservative Propagation](https://mlsanity.com/paper/2202.07304/) (2022)
- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [DIG: A Turnkey Library for Diving into Graph Deep Learning Research](https://mlsanity.com/paper/2103.12608/) (2021)
- [GraphFramEx: Towards Systematic Evaluation of Explainability Methods for Graph Neural Networks](https://mlsanity.com/paper/2206.09677/) (2022)
- [Towards Self-Interpretable Graph-Level Anomaly Detection](https://mlsanity.com/paper/2310.16520/) (2023)
- [Probing GNN Explainers: A Rigorous Theoretical and Empirical Analysis of GNN Explanation Methods](https://mlsanity.com/paper/2106.09078/) (2021)
- [Zorro: Valid, Sparse, and Stable Explanations in Graph Neural Networks](https://mlsanity.com/paper/2105.08621/) (2021)
- [GCExplainer: Human-in-the-Loop Concept-based Explanations for Graph Neural Networks](https://mlsanity.com/paper/2107.11889/) (2021)
- [Explaining the Explainers in Graph Neural Networks: a Comparative Study](https://mlsanity.com/paper/2210.15304/) (2022)
- [Reinforced Causal Explainer for Graph Neural Networks](https://mlsanity.com/paper/2204.11028/) (2022)
- [MambaLRP: Explaining Selective State Space Sequence Models](https://mlsanity.com/paper/2406.07592/) (2024)
- [Toward Explainable AI for Regression Models](https://mlsanity.com/paper/2112.11407/) (2021)
- [A Survey on Explainability of Graph Neural Networks](https://mlsanity.com/paper/2306.01958/) (2023)
- [DAG Matters! GFlowNets Enhanced Explainer For Graph Neural Networks](https://mlsanity.com/paper/2303.02448/) (2023)
- [TempME: Towards the Explainability of Temporal Graph Neural Networks via Motif Discovery](https://mlsanity.com/paper/2310.19324/) (2023)
- [Higher-order Clustering and Pooling for Graph Neural Networks](https://mlsanity.com/paper/2209.03473/) (2022)
- [Disentangled Explanations of Neural Network Predictions by Finding Relevant Subspaces](https://mlsanity.com/paper/2212.14855/) (2022)
- [The Clever Hans Effect in Unsupervised Learning](https://mlsanity.com/paper/2408.08041/) (2024)
- [FlowX: Towards Explainable Graph Neural Networks via Message Flows](https://mlsanity.com/paper/2206.12987/) (2022)
- [DEGREE: Decomposition Based Explanation For Graph Neural Networks](https://mlsanity.com/paper/2305.12895/) (2023)
- [PredDiff: Explanations and Interactions from Conditional Expectations](https://mlsanity.com/paper/2102.13519/) (2021)
- [xMIL: Insightful Explanations for Multiple Instance Learning in Histopathology](https://mlsanity.com/paper/2406.04280/) (2024)
- [ES-GNN: Generalizing Graph Neural Networks Beyond Homophily with Edge Splitting](https://mlsanity.com/paper/2205.13700/) (2022)
- [Towards Faithful and Consistent Explanations for Graph Neural Networks](https://mlsanity.com/paper/2205.13733/) (2022)
- [Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks](https://mlsanity.com/paper/2501.16944/) (2025)
- [RelP: Faithful and Efficient Circuit Discovery in Language Models via Relevance Patching](https://mlsanity.com/paper/2508.21258/) (2025)
- [Algorithmic Concept-based Explainable Reasoning](https://mlsanity.com/paper/2107.07493/) (2021)
- [Explaining machine-learned particle-flow reconstruction](https://mlsanity.com/paper/2111.12840/) (2021)

## Abstract (arXiv)

Graph Neural Networks (GNNs) are a popular approach for predicting graph structured data. As GNNs tightly entangle the input graph into the neural network structure, common explainable AI approaches are not applicable. To a large extent, GNNs have remained black-boxes for the user so far. In this paper, we show that GNNs can in fact be naturally explained using higher-order expansions, i.e. by identifying groups of edges that jointly contribute to the prediction. Practically, we find that such explanations can be extracted using a nested attribution scheme, where existing techniques such as layer-wise relevance propagation (LRP) can be applied at each step. The output is a collection of walks into the input graph that are relevant for the prediction. Our novel explanation method, which we denote by GNN-LRP, is applicable to a broad range of graph neural networks and lets us extract practically relevant insights on sentiment analysis of text data, structure-property relationships in quantum chemistry, and image classification.