PaperlayerView exact revision on arXiv

Source-linked AI summary

Higher-Order Explanations of Graph Neural Networks via Relevant Walks

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

arXiv:2006.03589v3cs.LGcs.AIstat.ML

TL;DR

GNNs are hard to explain because graph structure is tightly integrated into their computation, making ordinary input-feature attribution inadequate. The paper introduces GNN-LRP, which uses nested higher-order attribution to score relevant walks and demonstrates it across multiple applications. The method produces detailed explanations, broadly applies across architectures and graph types, and outperforms other explanation methods in a quantitative benchmark, while some evaluation procedures can underestimate higher-order methods.

  • Problem

    GNNs remain difficult to interpret because their graph inputs are deeply entangled with the model, limiting conventional explainable-AI approaches.

  • Method

    GNN-LRP uses higher-order Taylor expansions implemented as nested first-order attribution steps, producing relevance scores for walks in the input graph.

  • Results

    GNN-LRP produces detailed explanations, applies across diverse GNN architectures and graph types, and significantly outperforms other explanation methods in a quantitative benchmark.

  • Takeaways & Limitations

    Across sentiment analysis, quantum chemistry, and image classification, GNN-LRP reveals model strategies, including undesired Clever Hans strategies, and yields problem-relevant quantum-chemical insights.

  • Takeaways & Limitations

    Gradient-based GNN-GI explanations can lose attribution in deep models because gradient shattering makes the gradients noisy and less reliable.

Abstract

from arXiv · show

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.

1 INTRODUCTION

GNNs are difficult to explain because their input graphs are entangled with the model, limiting conventional feature-attribution approaches. The paper introduces GNN-LRP, a higher-order, walk-based explanation method demonstrated across diverse graph applications.

  • Motivation: GNNs remain black boxes because their graph inputs are deeply entangled with the neural-network structure.This limits both extracting insight from learned models and verifying that they use graph structure as intended.
  • Higher-Order Explanations: Higher-order Taylor expansions attribute predictions to groups of edges, such as walks, rather than individual nodes or edges.The approach targets joint edge contributions that existing GNN explanation techniques do not identify.
  • Method: GNN-LRP nests first-order expansions from the top layer toward the input and can apply LRP at each step to uncover relevant walks.The procedure starts with node attribution and recursively expands nodes into walks through lower layers.
  • Applications: GNN-LRP applies to diverse GNN models and graph inputs, including parse trees, molecular graphs, and pixel lattices.The paper demonstrates it on sentiment prediction, quantum-chemical property prediction, and image classification.

2 TOWARDS EXPLAINING GNNS

The paper explains why first-order attribution to initial node states is insufficient for GNNs and develops higher-order attribution over the true graph input. Under stated architectural conditions, the expansion decomposes predictions into joint edge effects.

  • GNN Structure: GNNs place graph connectivity across multiple interaction layers, so the input graph is part of the network structure rather than only its first layer.Interaction blocks aggregate neighboring information and then apply combine functions to node representations.
  • First-Order Explanation: Attributing the prediction to initial node states may miss higher-layer importance and whether nodes matter independently or through graph structures.These limitations arise because the decomposition uses H0 instead of the true graph input Λ.
  • Higher-Order Expansion: First-order analysis of the graph input cannot identify multiplicative interactions across layers, whereas higher-order Taylor expansion can.The expansion assigns joint effects to bags of edges and therefore captures interactions among multiple edges.
  • Higher-Order Expansion: A suitable reference point is difficult to specify, but GNN properties yield a simpler full decomposition on bags of T edges.For piecewise-linear, positively homogeneous combine and readout functions, choosing eΛ = sΛ and taking s → 0 eliminates terms outside network depth T.

3 EXPLAINING GNNS IN PRACTICE

The section develops walk-based explanations for GNNs by decomposing higher-order graph attributions into nested, layer-wise computations. GNN-LRP uses LRP within this procedure to produce detailed explanations across diverse GNN architectures.

  • Higher-order derivatives are difficult to extract systematically and do not scale to complex neural-network models.
  • Walk-based explanations: A walk is an ordered sequence of edges connecting nodes in consecutive GNN layers, preserving layer-specific structure beyond a bag-of-edges.
  • GNN-GI baseline: GNN-GI decomposes higher-order terms into walks using nested Gradient × Input attributions computed through successive first-order derivatives.
  • GNN-GI baseline: GNN-GI can lose prediction relevance when nonzero biases break conservation, while gradient shattering makes explanations noisy and less reliable in deep models.
  • GNN-LRP: GNN-LRP replaces the GNN-GI attribution steps with LRP, which propagates relevance from top-layer outputs toward input connections and handles neuron-level connections.
  • GNN-LRP: The nested LRP procedure starts with top-layer node attribution, recursively grows nodes into walks, and can use standard first-order explanation rules at each step.
  • Applicability: GNN-LRP applies to architectures including GNN, GCN, GraphSAGE, Neural FP, GIN, spectral filters, SchNet, and VGG-16.

4 TESTING AND VALIDATING GNN-LRP

GNN-LRP is evaluated qualitatively and quantitatively across synthetic graph, sentiment, molecular, and image tasks. It produces detailed, robust explanations and systematically outperforms competing methods in the reported benchmark.

  • Synthetic data: On the synthetic task, GNN-LRP explains GIN predictions by identifying walks through high-degree nodes as principal contributors.Leaf nodes and sequences of low-degree nodes are irrelevant or slightly contradict the prediction.
  • Qualitative comparison: GNN-LRP produces more detailed explanations than Pope et al. and GNNExplainer, while offering greater robustness than GNN-GI.The benchmark identifies GNN-LRP as the only method combining the desired robustness with a high level of detail.
  • Qualitative comparison: GNN-LRP provides finer-grained explanations than node-based methods by distinguishing individual-node contributions from interactions among connected nodes.Its walk-based relevance can also be reassigned to nodes, edges, leaves, trees, or cycles for different explanation granularities.
  • Quantitative comparison: GNN-LRP is systematically best on the synthetic benchmark for both activation and pruning tasks.The nearest competitors are Pope et al. with LRP, GNN-GI, and GNNExplainer.
  • Quantitative comparison: On sentiment analysis, GNN-LRP and GNNExplainer perform best on both activation and pruning, consistent with explanations that capture word interactions such as negation.They are followed by GNN-GI and Pope et al.'s node-attribution methods.
  • Quantitative comparison: GNN-LRP performs above competitors on SchNet and best on both tasks for VGG-16 image recognition.For VGG-16, the paper relates LRP's advantage over GI to handling neuron biases and gradient shattering in deep models.

5 NEW INSIGHTS WITH GNN-LRP

GNN-LRP reveals meaningful, higher-order structures behind predictions across sentiment analysis, quantum chemistry, and image classification. These explanations expose model strategies, biases, and chemically plausible regularities.

  • 5.1 Sentiment Analysis: GNN-LRP shows sentiment predictions based on meaningful combinations of words rather than isolated words.It correctly identifies combinations such as “the best movies” and “boring pictures” as positive and negative contributors.
  • 5.1 Sentiment Analysis: Compared with Bag-of-Words, GNN-LRP shows that the GNN captures and disambiguates sentiment in consecutive words.For example, the BoW model marks “like” as positive despite the preceding “didn’t”.
  • 5.1 Sentiment Analysis: GNN-LRP uncovers model flaws and biases, including localized walks that miss sarcasm and neutral entities receiving positive relevance.The method can identify such effects from individual examples or by systematically averaging explanations over a corpus.
  • 5.2 Quantum Chemistry: In SchNet, one-edge walks indicate electrostatic poles, self-walks reflect atom-type properties, and longer walks capture more complex spatial contributions.The resulting relevant walks agree with chemical characteristics and indicate chemically plausible learned regularities.
  • 5.3 Revisiting Image Classification: GNN-LRP reveals hierarchical image concepts: VGG-16 composes local edges into teapot parts and then into the whole object.For dumbbell images, it separately detects the arm and dumbbell before composing a “dumbbell-arm” concept near the wrist.
  • 5.3 Revisiting Image Classification: These explanations inspect image-classification structure beyond pixel-wise heatmaps and expose ‘Clever Hans’ strategies.The method provides insight into detailed classification behavior that standard pixel-wise explanations cannot provide.

6 CONCLUSION

The paper presents GNN-LRP as a theoretically principled explanation method for complex GNN–graph interactions. It reports stronger quantitative performance than other explanation methods, broad architectural applicability, and insights across several application domains.

  • GNN-LRP uses higher-order Taylor expansions to explain the nested interaction between a GNN and its input graph.The paper also introduces GNN-GI as a simple baseline and GNN-LRP as the more robust method for highly nonlinear models.
  • GNN-LRP significantly outperforms other explanation methods in the paper’s quantitative benchmark.
  • GNN-LRP applies across GCN, GIN, and spectral-filtering architectures and supports parse trees, spatial graphs, and pixel lattices.
  • Applications in sentiment analysis, quantum chemistry, and image classification reveal model strategies, undesired ‘Clever Hans’ behavior, and problem-relevant insights.

1 Higher-Order Explanations of Graph Neural

The supplied passage contains the paper title fragment “Networks via Relevant Walks.”

  • The title fragment ends with “Networks via Relevant Walks”.
  • The supplied title fragment refers to networks and relevant walks.
  • No further section content is supplied beyond the title fragment.

(SUPPLEMENTARY MATERIAL)

The supplementary material provides proofs, a justification of GNN-LRP for GCNs, and additional experimental details.

  • The supplied supplementary passage identifies the authors as Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof Schütt, Klaus-Robert Müller, and Grégoire Montavon.
  • The supplementary material includes proofs for Propositions 1 and 2 underlying the method.
  • It gives a detailed justification of the GNN-LRP procedure for the GCN.
  • It provides additional details about the synthetic dataset and graph neural networks used in the experiments.

APPENDIX A PROOF OF PROPOSITION 1

Under piecewise-linear, positively homogeneous GNN components, the network output becomes piecewise a homogeneous polynomial of order T. Taylor expansion at a scaled reference point retains only order-T terms as the scale approaches zero.

  • Taylor expansion at eΛ = sΛ eliminates all terms whose order differs from the network depth T as s → 0.The proof separates higher- and lower-order terms and shows both vanish in the limit.
  • The output f(Λ) is piecewise a homogeneous polynomial of order T under the stated architecture and activation assumptions.Repeated linear aggregation and piecewise-linear, positively homogeneous combine and readout functions establish this structure.
  • The analysis can be restricted to the polynomial piece containing the entire positive scaling line sΛ, including both the input and reference point.Positive homogeneity ensures that this piece can be chosen to contain (sΛ)s>0.
  • The surviving order-T decomposition is organized over bags of edges of length T, with multiplicities counted by the multi-index αB.The multi-index records repeated edges and its factorial accounts for duplicate-edge permutations.

APPENDIX B PROOF OF PROPOSITION 2

The proof converts the surviving higher-order derivatives into products along graph walks. Distinct interaction layers and nonzero connectivity restrict the decomposition from edge bags to ordered walks.

  • Higher-order terms can be computed as sequential differentiations and multiplications by connectivity terms forming each walk W.This is the central equivalence established by Proposition 2.
  • Only derivatives involving distinct interaction layers remain nonzero, reducing the expansion to ordered edge sequences.Repeated differentiation with respect to the same connectivity block vanishes because the function is piecewise linear in each block.
  • An edge sequence contributes only when all of its connectivity entries are nonzero, which is exactly the condition that it forms a graph walk.The proof then rewrites walks as node sequences for subsequent equations.
  • The bag relevance equals the sum of relevance values over walks contained in that bag: RB = ∑W∈B RW.The final identity follows after node notation, derivative reordering, and implicit layer notation.
  • Reordering derivatives and scalar multiplications is valid because parameters from different layers are distinct and can be permuted.This produces the implicit layer notation used in the final walk expression.

APPENDIX C DERIVING AND JUSTIFYING THE GNN-LRP PROCEDURE

GNN-LRP is justified by an inductive relevance-propagation construction demonstrated for GCNs and extended similarly to GIN and spectral networks. Its walk computation can be accelerated on graphs with disjoint receptive fields.

  • The inductive procedure assumes each layer’s relevance has a locally constant coefficient multiplying the activation of the propagated neuron.The coefficient is treated as locally approximately constant with respect to lower-layer activations.
  • For GCNs, graph connectivity is broken down to neuron-level inputs, enabling an LRP-γ propagation rule through a Linear-ReLU layer.LRP-γ is selected for added robustness and includes LRP-0 as the γ = 0 special case.
  • Pooling in GNN-LRP is restricted to neurons belonging to the traversed node K because the corresponding connections reach only K.This differs from standard LRP, which pools over a broader higher-layer neuron set.
  • The resulting LRP quantity recovers the product structure assumed by the induction, justifying propagation from the GNN output back to the first layer to compute relevant walks.The three verification steps establish the inductive principle for the GCN.
  • The product approximation is rule-dependent: an alternate direct connectivity mapping prevents the same product structure and stops further propagation within this framework.Thus, the procedure’s continuation depends on the chosen decomposition and propagation rule.
  • The inductive justification also applies similarly to the GIN and spectral network models considered in the paper.The appendix states that GNN-LRP can consequently be justified for these models as well.
  • For locally connected graphs with disjoint receptive fields, multiple walk relevances can be computed in parallel using one backward pass.The implementation uses node masks and interprets lower-layer attributions as relevance for walks entering the selected node.

APPENDIX E DETAILS ON THE SYNTHETIC DATASET

The synthetic dataset contains 20-node graphs from two classes with different attachment processes. Its arbitrary scalable generation supports training without overfitting from limited data.

  • The dataset consists of 20-node graphs generated from two graph classes.One class uses Barabási-Albert graphs with growth parameter 1.
  • In the second class, the 5th, 10th, 15th, and 20th added nodes connect to two existing nodes instead of one.This defines the class’s higher-growth attachment process.
  • The second class distributes connections more evenly between nodes than the Barabási-Albert class, corresponding to an inverse preferential attachment model.The passage contrasts the two classes’ connection distributions.
  • Because the dataset is synthetically generated, arbitrarily large datasets can be produced for model training without overfitting from dataset size.The passage explicitly links scalable generation to avoiding overfitting.
  • The paper trains and analyzes GNNs on the synthetic data alongside models for sentiment analysis, quantum chemistry, and image classification.The appendix identifies these model and task settings as part of the paper’s experimental preparation.

F.1 GNNs trained on Synthetic Data

The paper evaluates graph neural networks across synthetic graphs, dependency-tree sentiment analysis, molecular property prediction, and image classification. The described models use graph interactions followed by pooling or task-specific readouts, with reported test performance for sentiment and quantum chemistry models.

  • Synthetic graph models: The synthetic-data experiments compare GCN, GIN, and ChebNet architectures with two interaction layers and global average pooling.The GCN uses 128 neurons per layer, while the GIN and ChebNet use 32; ChebNet receives an adjacency power expansion.
  • Synthetic graph models: Synthetic graph nodes are initialized with a constant value, so the first layer extracts node degrees and the second aggregates neighboring degrees.Non-positive bias constraints are imposed through a scaled softmin reparameterization.
  • Text sentiment model: The sentiment model is trained on a binarized Stanford Sentiment Treebank using dependency trees generated by spaCy.Its word-level initialization combines pretrained, random, part-of-speech, and stemmed-word embeddings before graph propagation.
  • Text sentiment model: The text model applies repeated GCN interaction units, feed-forward transformations, global average pooling, and a softmax readout.The reported configuration uses hidden dimension dh = 10 and T = 3 interaction layers.
  • Molecular property model: The SchNet experiment uses molecular graphs whose nodes represent atoms and whose edges encode interatomic distances to predict atomization energy and dipole moment.The model is trained on 110,000 QM9 data points with three interaction blocks and a 2.5 Å cutoff, achieving a mean absolute error of 0.015 eV for the reported prediction setting.
Loading 2006.03589v3…