Reproduce “Higher-Order Explanations of Graph Neural Networks via Relevant Walks” on OpenResearch

About this paper

Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T. Schütt, Klaus-Robert Müller, Grégoire Montavon

Researchers from the Berlin Institute of Technology present GNN-LRP, a method to explain Graph Neural Network predictions by identifying 'relevant walks' (sequences of edges) that contribute to the model's output. The approach provides detailed and robust explanations, consistently outperforming gradient-based baselines and existing methods in quantitative activation and pruning tasks across diverse GNN architectures and applications, including molecular property prediction and sentiment analysis.

Key insights

• GNN predictions, particularly for models with piecewise linear and positively homogeneous activation functions, can be decomposed into relevance scores attributable to 'bags' of edges, which correspond to 'walks' through the network layers.
• Nested application of LRP, justified by Deep Taylor Decomposition, provides a robust mechanism to propagate relevance backward along these walks, addressing limitations of simpler gradient-based approaches like noise and relevance non-conservation.
• Identifying relevant walks offers a higher-order, fine-grained understanding of GNN decision strategies, revealing complex structural patterns and multi-step interactions that influence predictions, which are often missed by single-element attribution methods.

Summary by alphaXiv.