PaperlayerView exact revision on arXiv

Source-linked AI summary

Relevant Walk Search for Explaining Graph Neural Networks

Ping Xiong, Thomas Schnake, Michael Gastegger, Grégoire Montavon, Klaus-Robert Müller, Shinichi Nakajima

arXiv:2605.23673v1cs.LG

TL;DR

GNN-LRP provides higher-order walk explanations, but identifying relevant walks has exponential complexity with network depth. This paper develops polynomial-time max-product-based searches that are exact at the neuron level and approximate at the node level, with experiments showing fast computation and high approximation accuracy.

  • Problem

    GNN-LRP's relevant-walk identification has exponential complexity, limiting the applicability of its higher-order explanations.

  • Method

    The paper uses max-product decomposability to derive an exact neuron-level search and an approximate node-level search for top-K relevant walks.

  • Results

    The proposed algorithms have polynomial computational complexity, while AMP-ave achieves generally good approximation accuracy in experiments across application domains.

  • Takeaways & Limitations

    The method retains GNN-LRP's higher-order feature resolution while avoiding exponential computational costs and provides fast explanations with insignificant approximation error in the reported experiments.

  • Takeaways & Limitations

    The theory and algorithms apply to GNNs only when their relevance propagation rule can be defined in the required form.

Abstract

from arXiv · show

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 \emph{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 \emph{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 \href{https://github.com/xiong-ping/rel_walk_gnnlrp}{github.com/xiong-ping/rel\_walk\_gnnlrp}.

1. Introduction

GNN explainability seeks to expose the features and information flows behind predictions, but GNN-LRP’s higher-order walk explanations require exponentially many evaluations. This paper uses max-product message passing to identify relevant walks with polynomial computational complexity.

  • GNNs are difficult to interpret because their predictive rationale, including jointly contributing node features and graph parts, is not directly exposed.
  • GNN-LRP provides higher-order explanations by measuring the relevance of walks contributing jointly to a prediction.
  • GNN-LRP’s relevant-walk identification requires exponentially many walk evaluations, limiting naive implementations to small network depths and graph sizes.
  • Max-product message passing finds relevant walks through local message passing, reducing complexity with respect to network depth from exponential to linear.
  • The paper proposes exact max-product search for neuron-level walks and approximate max-product search by neuron averaging for node-level walks.
  • Both proposed algorithms have polynomial complexity and retain GNN-LRP’s higher-order feature resolution without exponential computational costs.

2. Background and Related Works

The paper situates walk relevance within message-passing GNNs and prior explanation methods, then connects GNN-LRP’s walk decomposition to probabilistic message passing. Neuron-level and node-level walks capture different aggregation structures.

  • 2.1. Graph Neural Networks: Message-passing GNNs learn node embeddings through repeated aggregate and combine steps based on graph topology.
  • 2.1. Graph Neural Networks: A linear aggregation followed by a one-layer perceptron is a common GCN choice, with a readout producing final predictions from node features.
  • 2.2. Explaining GNNs: Existing GNN explanation methods include masks, gradients, surrogate models, and learned edge-removal predictors, while many focus on node- or edge-level features.
  • 2.3. Relevance of Walks: A walk is an ordered sequence of nodes connected across layers, from an input-layer node through intermediate layers to a final-layer node.
  • 2.3. Relevance of Walks: GNN-LRP propagates relevance through layer-specific matrices, and its propagation rule can be interpreted as summing over neuron trajectories within a node-level walk.
  • 2.3. Relevance of Walks: Neuron-level walks track relevance through neurons, whereas node-level walks aggregate across neurons and may rank paths differently.

3. Message Passing for Relevant Walk Search

The paper applies max-product message passing to search for highly relevant GNN-LRP walks, yielding exact neuron-level search and approximate node-level search. Both approaches have polynomial computational complexity, while AMP-ave relies on a column-similarity assumption for its approximation.

  • Algorithmic framework: Max-product decomposability enables two algorithms for finding the most relevant walks: neuron-level and node-level search.The neuron-level method is exact, whereas the node-level method is approximate.
  • 3.1. Exact Neuron-level Search: The neuron-level max-product messages find the highest-absolute-relevance walk in O(M^2NL) time.The procedure then splits the search space to collect top-K walks rather than only one candidate.
  • 3.1. Exact Neuron-level Search: EMP-neu exactly finds the top-K neuron-level walks in polynomial time under the condition that the selected absolute-relevance candidates contain K positively relevant walks.Its stated computational complexity is O(LM^2N^2 + eKL^2MN).
  • 3.2. Approximate Node-level Search: AMP-ave approximates node-level search by averaging propagation-matrix columns so that max-product message passing becomes applicable.The approximation is motivated by similar-column propagation matrices and uses the same search-space splitting strategy for top-K walks.
  • 3.2. Approximate Node-level Search: AMP-ave's approximation error is controlled by the column-similarity assumption, and its relevance message does not accumulate error when each approximate maximization chooses correctly.The experiments assess approximation accuracy and its dependence on LRP parameters.
  • 3.2. Approximate Node-level Search: AMP-ave has the same computational complexity as EMP-neu, while activation and modified-weight matrices reduce node-level memory to O(L max(M, N)^2).The reduced memory cost makes node-level search feasible for larger-scale problems.

4. Experiments

Experiments evaluate AMP-ave across benchmark and large-scale datasets, measuring approximation accuracy, explanation quality, and scalability. The results show high approximation accuracy and useful higher-order explanations where exhaustive GNN-LRP search is infeasible.

  • Datasets: Experiments use BA-2motif, MUTAG, Mutagenicity, Graph-SST2, and the large-scale Infection dataset.Infection is used to demonstrate scalability when exhaustive evaluation of all walks is infeasible.
  • Approximation Accuracy: AMP-ave generally achieves good approximation accuracy for LRP-γ with γ ≥0.2.The evaluation compares approximate top-K walks with exhaustive-search ground-truth walks using precision and recall.
  • Approximation Accuracy: The average cosine similarity between propagation-matrix columns and their averages exceeds 0.8 across all four benchmark datasets.This similarity is reported as explaining AMP-ave’s good accuracy, although further analysis is needed to guarantee approximation accuracy.
  • Visualization with Top-K Walks: Efficiently found top-K walks capture the most important information obtained by evaluating all walks on Mutagenicity and Graph-SST2.This supports the utility of AMP-ave beyond the large-scale Infection setting.
  • Visualization with Top-K Walks: AMP-ave identifies all three possible infection chains in the illustrated Infection example, with its top-1 walk matching the ground-truth chain.Node-IG and Edge-IG do not identify the corresponding nodes or connected edges as the most relevant, while AMP-ave exposes complete chains.
  • Visualization with Top-K Walks: On Mutagenicity, AMP-ave’s top-10 walks capture relevant mutagenic and non-mutagenic functional groups with polynomial complexity.The visualizations distinguish evidence for mutagenicity from evidence for non-mutagenicity.

Appendix I).

The experiments evaluate relevant-walk detection, computational speed, scalability, and scope limitations across graph datasets. AMP-ave achieves strong detection results and substantially reduces computation, while its approximation lacks a theoretical guarantee and applies only to models with suitable relevance propagation.

  • Quantitative evaluation: 94.22% recall is achieved by AMP-ave's top-5 walks for detecting the ground-truth infection chain on the Infection dataset.The result is close to the oracle detector, while exhaustive evaluation is infeasible for this dataset.
  • Quantitative evaluation: 100% recall is reached faster by AMP-ave than by Edge-IG, GNNExplainer, edge-level GNN-LRP, and gradient-based edge heatmaps on BA-2motif.Positive and negative samples are plotted separately in the motif edge-detection evaluation.
  • Computational efficiency: AMP-ave is orders of magnitude faster than GNN-LRP and remains applicable to the large Infection dataset where all-walk evaluation is infeasible.Figure 9 compares computation time as functions of network depth and graph size, showing a large computational gain.
  • Scope and applications: The framework targets higher-order explanations across chemistry, infection biology, and NLP, with experiments on synthetic and real-world datasets.The conclusion presents EMP-neu as exact at neuron level and AMP-ave as approximate at node level, both using polynomial-time search.
  • Limitations: AMP-ave has no theoretical accuracy guarantee, and the approach applies only when relevance propagation can be defined as in Eq.(5).These limitations may exclude some general GNNs beyond message-passing neural networks.

B.1. EMP-neu-Basic: Derivation of Message Passing Equations (10) and (11)

EMP-neu uses max-product message passing to find highly relevant neuron-level walks and extends this search to top-K solutions through search-space splitting. The resulting procedures have polynomial computational and memory complexity, while AMP-ave provides an approximate node-level counterpart.

  • EMP-neu-Basic: Max-product message passing computes the highest-absolute-relevance neuron-level walk by sequential messages and backtracing maximum step mappings.EMP-neu-Basic propagates messages from layer L to layer 1, then reconstructs the maximizing walk.
  • Complexity: The highest-relevance neuron-level walk requires O(LM^2N^2) time and O(LM^2N^2) memory under the stated complexity expressions.The memory cost includes transition matrices and maximum-step mappings.
  • Top-K search: The top-K neuron-level search repeatedly splits the subset containing the previous solution and selects the most relevant maximizer among the resulting disjoint subsets.This procedure continues until the requested number of solutions is obtained.
  • AMP-ave: AMP-ave approximately searches node-level walks by averaging over neurons, with total complexity O(LM^2N^2 + KL^2MN).The method is implemented through an approximate basic search followed by search-space splitting for top-K walks.
  • Memory reduction: For AMP-ave, memory can be reduced to O(L max(M,N)^2) by using activation and modified weight matrices instead of storing the full transition matrices.The text gives this reduction as a way to make node-level search feasible for larger graphs.
  • Relevance signs: For γ ≥ 0.2, more than half of the top absolute-relevance walks are positive in the reported empirical analysis, although negative objectives can remain frequent on BA-2motif.The sign distribution motivates retrieving more than K absolute-relevance walks when necessary to obtain K positive walks.

D.3. Empirical results from EMP-neu

EMP-neu reproduces the true ranking of top neuron-level walks while requiring dramatically less computation than exhaustive search.

  • Empirical correctness: 3.4 seconds versus over 3 hours: EMP-neu finds the top 100 absolute-relevance walks while exhaustive search evaluates the same ranking far more slowly.The true ranking is in non-decreasing order in the reported comparison, supporting the correctness of EMP-neu.

E. Additional Precision Evaluation on MUTAG and Graph-SST2

Additional precision-recall curves evaluate AMP-ave on MUTAG and Graph-SST2.

  • Additional evaluation: AMP-ave is evaluated with precision-recall curves on the MUTAG and Graph-SST2 datasets.The passage identifies the evaluation but does not report a numerical outcome.

F. Datasets and GNN Models for Experiments

The experiments use graph, molecule, and parse-tree datasets with task-specific GNN architectures and reported test accuracies for Mutagenicity and Graph-SST2.

  • Datasets: The experiments cover BA-2motif graphs, MUTAG and Mutagenicity molecules, and Graph-SST2 parse trees.BA-2motif classifies graphs by attached house or circle motifs; MUTAG and Mutagenicity classify molecules as mutagenic or non-mutagenic, while Graph-SST2 contains text parse trees.
  • GNN models: The BA-2motif model is a 3-layer GIN with ReLU activations, node embeddings progressing from one dimension to 20 and then 2 dimensions, and sum pooling.
  • GNN models: The MUTAG model is a 3-layer GIN with 7-dimensional input features, 128-dimensional intermediate layers, 2-dimensional output, and sum-based readout.
  • Evaluation: 83.16% test accuracy is reported for the Mutagenicity model, trained on 3096 balanced samples with Adam for 25 epochs.
  • Evaluation: 89.40% test accuracy is reported for Graph-SST2, using 768-dimensional pretrained word embeddings and a 3-layer GCN.

G. Oracle Predictors for Infection Dataset

The infection experiments construct oracle predictors from repeated simulations of the SI process and compare walk-detection heuristics based on edge relevance.

  • Oracle predictors: The oracle uses Monte Carlo sampling because the SI model’s predictive probabilities have intractable analytic expressions.It simulates the infection process Q = 1000 times and counts infected nodes and infection chains.
  • Oracle predictors: The oracle infection predictor provides an accuracy upper bound for machine-learning predictors, while the oracle chain predictor bounds possible infection-chain detection accuracy.
  • Walk detectors: The heuristic detectors sort Edge-IG edge scores, retain the top-eK edges, enumerate compatible walks, and assign each walk a relevance score.
  • Walk detectors: Edge-IG sum and Edge-IG prod are used as heuristic baselines with eK = 25, and the heuristics are compatible with edge-level explanation methods.

I.1. Explaining model predictions on Mutagenicity

On Mutagenicity, AMP-ave identifies chemically meaningful mutagenic and non-mutagenic structures in four molecule examples, often more specifically than node- or edge-level baselines.

  • Molecule explanations: The examples contain two mutagenic and two non-mutagenic molecules.
  • Mutagenic molecules: In the first mutagenic molecule, AMP-ave finds the mutagenic NO2 group within the top-10 walks, whereas Node-IG and Edge-IG highlight it only partially.
  • Mutagenic molecules: In the second mutagenic molecule, AMP-ave identifies the OH substituent, while the baselines assign incorrect relevance to the C-O bond or nitrogen atom.
  • Non-mutagenic molecules: For non-mutagenic molecules, AMP-ave identifies C-N bonds or aromatic-ring C substituents associated with chemically stable structures.

I.2. Explaining model predictions on Graph-SST2

On Graph-SST2, AMP-ave highlights sentiment-bearing word groups and higher-order interactions, while competing explanations sometimes focus on incomplete, incorrect, or overly diffuse regions.

  • Sentiment explanations: The examples contain two positive- and two negative-sentiment parse trees.
  • Positive sentiment: For a positive sample, AMP-ave selects “the value and respect” as the most relevant phrase and excludes less relevant words among the top-10 walks.
  • Positive sentiment: In another positive sample, one top-10 walk connects four relevant words, capturing interactions that Node-IG and Edge-IG misidentify.
  • Negative sentiment: For negative samples, AMP-ave identifies “altogether too slight” and “because” with “acts goofy” as sentiment-bearing evidence.
  • Negative sentiment: Visualizing all GNN-LRP walks can make relative relevance harder to judge, whereas AMP-ave narrows attention to selected walks.
Loading 2605.23673v1…