pith. sign in

arxiv: 2605.22385 · v1 · pith:PGERY4RHnew · submitted 2026-05-21 · 💻 cs.LG

Efficient Higher-order Subgraph Attribution via Message Passing

Ping Xiong , Thomas Schnake , Gr\'egoire Montavon , Klaus-Robert M\"uller , Shinichi Nakajima This is my paper

Pith reviewed 2026-05-22 07:50 UTC · model grok-4.3

classification 💻 cs.LG
keywords Graph Neural NetworksExplainable AILayer-wise Relevance PropagationSubgraph AttributionMessage PassingHigher-order ExplanationsEfficient Algorithms
0
0 comments X

The pith

GNN-LRP subgraph attributions can be computed in linear time using message passing that exploits the distributive property.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper seeks to remove the exponential cost of higher-order subgraph explanations for graph neural networks. Standard GNN-LRP attributes relevance to walks between nodes and then sums those values to obtain subgraph scores, but the number of walks grows exponentially with depth. The authors derive message-passing algorithms that push the distributive property through the relevance rules so that the same total attributions are obtained by propagating aggregated quantities rather than enumerating walks. If correct, this change turns a previously intractable method into a practical tool for explaining GNN decisions on graphs.

Core claim

The authors demonstrate that GNN-LRP subgraph attributions, normally obtained by summing relevance over exponentially many walks, can instead be computed directly via message passing that applies the distributive property of summation and multiplication to the propagation rules. The resulting algorithms run in linear time with respect to network depth. The same technique is adapted to produce a generalized form of subgraph attribution that incorporates features from neighboring nodes.

What carries the argument

Message-passing algorithms derived from the distributive property applied to GNN-LRP relevance propagation rules, which compute aggregated higher-order quantities without enumerating walks.

If this is right

  • Subgraph attributions become feasible for deeper GNN architectures without exponential slowdown.
  • A generalized version that includes neighboring node features can also be computed at linear cost.
  • The method scales to larger graphs and deeper models while preserving exact equivalence to the original GNN-LRP values.
  • Experimental runs confirm substantial runtime reductions and practical usability on graph data.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same message-passing rewrite may apply to other layer-wise relevance schemes that rely on similar product-sum rules.
  • Testing the generalized attributions on molecular or social graphs could surface interaction patterns that standard single-node explanations miss.
  • The linear scaling invites direct comparison against perturbation-based or gradient-based subgraph methods on identical tasks.

Load-bearing premise

The distributive property can be applied to the GNN-LRP relevance rules without changing the final attribution values or requiring architecture-specific corrections.

What would settle it

Compute subgraph attributions for a small GNN both by exhaustive summation over walks and by the proposed message-passing procedure; the two sets of scores must match exactly on every subgraph.

Figures

Figures reproduced from arXiv: 2605.22385 by Gr\'egoire Montavon, Klaus-Robert M\"uller, Ping Xiong, Shinichi Nakajima, Thomas Schnake.

Figure 1
Figure 1. Figure 1: Visualisation for the joint contribution of atom sub [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Computation of the subgraph relevance (left). A naive implementation of GNN-LRP computes the sum of the [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: LRP as message passing. (a) An example graph consisting of 3 nodes (with self-connections). (b) Unfolded [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Computation time on BA-2motif dataset. Note the [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Accuracy and AUROC of node ordering task on [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: AUAC (top row, higher is better) and AUPC (bottom row, lower is better) on MUTAG and Graph-SST2 datasets of [PITH_FULL_IMAGE:figures/full_fig_p009_6.png] view at source ↗
read the original abstract

Explaining graph neural networks (GNNs) has become more and more important recently. Higher-order interpretation schemes, such as GNN-LRP (layer-wise relevance propagation for GNN), emerged as powerful tools for unraveling how different features interact thereby contributing to explaining GNNs. GNN-LRP gives a relevance attribution of walks between nodes at each layer, and the subgraph attribution is expressed as a sum over exponentially many such walks. In this work, we demonstrate that such exponential complexity can be avoided. In particular, we propose novel algorithms that enable to attribute subgraphs with GNN-LRP in linear-time (w.r.t. the network depth). Our algorithms are derived via message passing techniques that make use of the distributive property, thereby directly computing quantities for higher-order explanations. We further adapt our efficient algorithms to compute a generalization of subgraph attributions that also takes into account the neighboring graph features. Experimental results show the significant acceleration of the proposed algorithms and demonstrate the high usefulness and scalability of our novel generalized subgraph attribution method.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper proposes novel algorithms for higher-order subgraph attribution using GNN-LRP. It claims that message-passing techniques combined with the distributive property allow direct computation of subgraph attributions in linear time with respect to network depth, avoiding explicit summation over exponentially many walks. The work further adapts the approach to a generalized form of subgraph attribution that incorporates neighboring graph features, with experiments demonstrating computational acceleration and practical usefulness.

Significance. If the algorithms preserve exact equivalence to standard GNN-LRP while achieving the claimed linear-time scaling, the result would be significant for scalable explainability of GNNs. Higher-order attributions have been limited by exponential complexity; an exact message-passing reformulation would make them feasible for deeper networks and larger graphs. The generalization to neighboring features is a natural extension that could improve explanatory power. The algebraic use of distributivity to rearrange relevance propagation is a strength if rigorously verified.

major comments (1)
  1. [§3] §3 (Message Passing for GNN-LRP): the central claim that distributivity yields exact higher-order attributions in linear time requires explicit verification for non-linear activations (e.g., ReLU) and per-node/layer normalization terms. The relevance rule typically multiplies incoming relevance by (activation * weight / normalization); when these are computed locally, rearranging the sum-over-walks across layers is not automatically exact. The manuscript must show either a formal proof that no correction terms arise or numerical equivalence checks against brute-force walk summation on the architectures tested.
minor comments (2)
  1. The abstract and introduction would benefit from a brief statement of the precise GNN architectures and activation functions for which exactness is claimed.
  2. Figure 2 (or equivalent runtime plot): axis labels and legend should explicitly state whether the baseline is the original exponential GNN-LRP or a different approximation.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their constructive comments and for recognizing the potential significance of our message-passing reformulation of GNN-LRP. We address the single major comment below and will revise the manuscript to incorporate the requested verification.

read point-by-point responses

  1. Referee: [§3] §3 (Message Passing for GNN-LRP): the central claim that distributivity yields exact higher-order attributions in linear time requires explicit verification for non-linear activations (e.g., ReLU) and per-node/layer normalization terms. The relevance rule typically multiplies incoming relevance by (activation * weight / normalization); when these are computed locally, rearranging the sum-over-walks across layers is not automatically exact. The manuscript must show either a formal proof that no correction terms arise or numerical equivalence checks against brute-force walk summation on the architectures tested.

    Authors: We agree that explicit verification strengthens the central claim. In our derivation, the forward-pass activations (including ReLU outputs) and per-node/layer normalization factors are fixed constants computed once before relevance propagation. Consequently, each edge carries a fixed multiplier of the form (activation × weight / normalization) that is independent of any particular walk. The higher-order attribution is therefore exactly the sum over walks of the product of these per-edge multipliers. Because multiplication is distributive over addition, the sum-over-walks can be rearranged into a message-passing recursion without introducing correction terms. We will add (i) a concise formal proof of this equivalence in the revised §3 and (ii) numerical equivalence checks that compare the message-passing results against brute-force enumeration of walks on the GNN architectures used in our experiments. revision: yes

Circularity Check

0 steps flagged

Derivation applies standard distributivity to existing GNN-LRP rules without reducing to fitted inputs or self-citations

full rationale

The paper derives linear-time subgraph attribution by rearranging GNN-LRP relevance sums via the distributive property of multiplication over addition in a message-passing formulation. This is a direct algebraic identity applied to the pre-existing layer-wise relevance propagation scheme; no parameters are fitted to the target attributions, no uniqueness theorem is imported from the authors' prior work to force the form, and the central claim does not rename or redefine quantities in terms of themselves. The abstract and derivation description present the efficiency gain as a consequence of this rearrangement, which remains independent of the specific numerical values being attributed. No load-bearing step reduces by construction to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The approach rests on the algebraic distributivity of summation over multiplication when applied to relevance scores; no free parameters, invented entities, or domain-specific axioms beyond standard graph neural network forward-pass assumptions are mentioned in the abstract.

axioms (1)
  • domain assumption Relevance scores in GNN-LRP can be aggregated using the distributive law of summation and multiplication without loss of exactness.
    Invoked to justify replacing exponential walk enumeration with direct message passing.

pith-pipeline@v0.9.0 · 5719 in / 1264 out tokens · 29339 ms · 2026-05-22T07:50:46.483135+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages

  1. [1]

    Yu , title =

    Zonghan Wu and Shirui Pan and Fengwen Chen and Guodong Long and Chengqi Zhang and Philip S. Yu , title =

    work page

  2. [2]

    PloS one , volume=

    On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation , author=. PloS one , volume=. 2015 , publisher=

    work page 2015

  3. [3]

    Neuroimage , volume=

    Complex network measures of brain connectivity: uses and interpretations , author=. Neuroimage , volume=. 2010 , publisher=

    work page 2010

  4. [4]

    and Chmiela, Stefan and Gastegger, Michael and Schütt, Kristof T

    Unke, Oliver T. and Chmiela, Stefan and Gastegger, Michael and Schütt, Kristof T. and Sauceda, Huziel E. and Müller, Klaus-Robert , doi =. SpookyNet: Learning force fields with electronic degrees of freedom and nonlocal effects , ty =. Nature Communications , number =

    work page

  5. [5]

    Nature neuroscience , volume=

    Human cognition involves the dynamic integration of neural activity and neuromodulatory systems , author=. Nature neuroscience , volume=. 2019 , publisher=

    work page 2019

  6. [6]

    Digital Signal Processing , volume=

    Methods for interpreting and understanding deep neural networks , author=. Digital Signal Processing , volume=. 2018 , publisher=

    work page 2018

  7. [7]

    Explaining Deep Neural Networks and Beyond:

    Wojciech Samek and Gr. Explaining Deep Neural Networks and Beyond:. Proc

    work page

  8. [8]

    , title =

    Bishop, Christopher M. , title =. 2006 , isbn =

    work page 2006

  9. [9]

    CoRR , volume =

    Hao Yuan and Haiyang Yu and Shurui Gui and Shuiwang Ji , title =. CoRR , volume =. 2020 , url =

    work page 2020

  10. [10]

    GNNExplainer: Generating Explanations for Graph Neural Networks , booktitle =

    Zhitao Ying and Dylan Bourgeois and Jiaxuan You and Marinka Zitnik and Jure Leskovec , editor =. GNNExplainer: Generating Explanations for Graph Neural Networks , booktitle =

    work page

  11. [11]

    Parameterized Explainer for Graph Neural Network , booktitle =

    Dongsheng Luo and Wei Cheng and Dongkuan Xu and Wenchao Yu and Bo Zong and Haifeng Chen and Xiang Zhang , editor =. Parameterized Explainer for Graph Neural Network , booktitle =

    work page

  12. [12]

    On Explainability of Graph Neural Networks via Subgraph Explorations , booktitle =

    Hao Yuan and Haiyang Yu and Jie Wang and Kang Li and Shuiwang Ji , editor =. On Explainability of Graph Neural Networks via Subgraph Explorations , booktitle =

    work page

  13. [13]

    Vu and My T

    Minh N. Vu and My T. Thai , editor =. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual , year =

    work page 2020

  14. [14]

    7th International Conference on Learning Representations,

    Keyulu Xu and Weihua Hu and Jure Leskovec and Stefanie Jegelka , title =. 7th International Conference on Learning Representations,

    work page

  15. [15]

    IEEE Transactions on Pattern Analysis and Machine Intelligence , title=

    Schnake, Thomas and Eberle, Oliver and Lederer, Jonas and Nakajima, Shinichi and Sch. IEEE Transactions on Pattern Analysis and Machine Intelligence , title=. 2021 , volume=

    work page 2021

  16. [16]

    Link Prediction Based on Graph Neural Networks , booktitle =

    Muhan Zhang and Yixin Chen , editor =. Link Prediction Based on Graph Neural Networks , booktitle =

    work page

  17. [17]

    Genome Medicine , volume=

    Explaining decisions of graph convolutional neural networks: patient-specific molecular subnetworks responsible for metastasis prediction in breast cancer , author=. Genome Medicine , volume=. 2021 , publisher=

    work page 2021

  18. [18]

    6th International Conference on Learning Representations,

    Jie Chen and Tengfei Ma and Cao Xiao , title =. 6th International Conference on Learning Representations,

    work page

  19. [19]

    Evolution of Graph Classifiers , year=

    Domingue, Miguel and Dhamdhere, Rohan and Harish Kanamarlapudi, Naga Durga and Raghupathi, Sunand and Ptucha, Raymond , booktitle=. Evolution of Graph Classifiers , year=

    work page

  20. [20]

    Hamilton and Zhitao Ying and Jure Leskovec , editor =

    William L. Hamilton and Zhitao Ying and Jure Leskovec , editor =. Inductive Representation Learning on Large Graphs , booktitle =

    work page

  21. [21]

    The Journal of Chemical Physics , volume=

    Schnet--a deep learning architecture for molecules and materials , author=. The Journal of Chemical Physics , volume=. 2018 , publisher=

    work page 2018

  22. [22]

    Franco Scarselli and Marco Gori and Ah Chung Tsoi and Markus Hagenbuchner and Gabriele Monfardini , title =

    work page

  23. [23]

    Kipf and Max Welling , title =

    Thomas N. Kipf and Max Welling , title =. 5th International Conference on Learning Representations,

    work page

  24. [24]

    Distill , year =

    Olah, Chris and Mordvintsev, Alexander and Schubert, Ludwig , title =. Distill , year =

    work page

  25. [25]

    Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps , booktitle =

    Karen Simonyan and Andrea Vedaldi and Andrew Zisserman , editor =. Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps , booktitle =

    work page

  26. [26]

    Real Time Image Saliency for Black Box Classifiers , booktitle =

    Piotr Dabkowski and Yarin Gal , editor =. Real Time Image Saliency for Black Box Classifiers , booktitle =

    work page

  27. [27]

    Wainwright and Michael I

    Jianbo Chen and Le Song and Martin J. Wainwright and Michael I. Jordan , editor =. Learning to Explain: An Information-Theoretic Perspective on Model Interpretation , booktitle =

    work page

  28. [28]

    Hao Yuan and Jiliang Tang and Xia Hu and Shuiwang Ji , editor =

    work page

  29. [29]

    CoRR , volume =

    Federico Baldassarre and Hossein Azizpour , title =. CoRR , volume =. 2019 , url =

    work page 2019

  30. [30]

    Pope and Soheil Kolouri and Mohammad Rostami and Charles E

    Phillip E. Pope and Soheil Kolouri and Mohammad Rostami and Charles E. Martin and Heiko Hoffmann , title =

    work page

  31. [31]

    Yue Zhang and David DeFazio and Arti Ramesh , editor =. RelEx:

    work page

  32. [32]

    CoRR , volume =

    Qiang Huang and Makoto Yamada and Yuan Tian and Dinesh Singh and Dawei Yin and Yi Chang , title =. CoRR , volume =. 2020 , url =

    work page 2020

  33. [33]

    Spectral Networks and Locally Connected Networks on Graphs , booktitle =

    Joan Bruna and Wojciech Zaremba and Arthur Szlam and Yann LeCun , editor =. Spectral Networks and Locally Connected Networks on Graphs , booktitle =

    work page

  34. [34]

    Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering , booktitle =

    Micha. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering , booktitle =

    work page

  35. [35]

    Reverend

    Judea Pearl , editor =. Reverend. Proceedings of the National Conference on Artificial Intelligence, Pittsburgh, PA, USA, August 18-20, 1982 , pages =

    work page 1982

  36. [36]

    and Debnath, Gargi and Shusterman, Alan J

    Debnath, Asim Kumar and Lopez de Compadre, Rosa L. and Debnath, Gargi and Shusterman, Alan J. and Hansch, Corwin , title =. Journal of Medicinal Chemistry , volume =. 1991 , doi =

    work page 1991

  37. [37]

    Journal of Medicinal Chemistry , volume =

    Kazius, Jeroen and McGuire, Ross and Bursi, Roberta , title =. Journal of Medicinal Chemistry , volume =. 2005 , doi =

    work page 2005

  38. [38]

    Manning and Andrew Y

    Richard Socher and Alex Perelygin and Jean Wu and Jason Chuang and Christopher D. Manning and Andrew Y. Ng and Christopher Potts , title =. Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing,

    work page 2013

  39. [39]

    Pinar Yanardag and S. V. N. Vishwanathan , editor =. Deep Graph Kernels , booktitle =. 2015 , doi =

    work page 2015

  40. [40]

    arXiv preprint arXiv:2005.00687 , year=

    Open Graph Benchmark: Datasets for Machine Learning on Graphs , author=. arXiv preprint arXiv:2005.00687 , year=

    work page arXiv 2005

  41. [41]

    A Unified Approach to Interpreting Model Predictions , volume =

    Lundberg, Scott M and Lee, Su-In , booktitle =. A Unified Approach to Interpreting Model Predictions , volume =

    work page

  42. [42]

    and Riley, Patrick F

    Gilmer, Justin and Schoenholz, Samuel S. and Riley, Patrick F. and Vinyals, Oriol and Dahl, George E. , title =. Proceedings of the 34th International Conference on Machine Learning - Volume 70 , pages =. 2017 , publisher =

    work page 2017

  43. [43]

    Journal of Medicinal Chemistry , volume =

    Kazius, Jeroen and McGuire, Ross and Bursi, Roberta , title =. Journal of Medicinal Chemistry , volume =

    work page

  44. [44]

    Yuyang Gao and Tong Sun and Rishab Bhatt and Dazhou Yu and Sungsoo Hong and Liang Zhao , editor =

    work page