Efficient Computation of Higher-Order Subgraph Attribution via Message Passing

Explaining graph neural networks (GNNs) has become more and more important recently. Higherorder interpretation schemes, such as GNNLRP (layer-wise relevance propagation for GNN),
emerged as powerful tools for unraveling how
different features interact thereby contributing to
explaining GNNs. Methods such as GNN-LRP
perform walks between nodes at each layer, and
there are exponentially many such walks. In this
work, we demonstrate that such exponential complexity can be avoided, in particular, we propose
novel linear-time (w.r.t. depth) algorithms that
enable to efficiently perform GNN-LRP for subgraphs. 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 significant acceleration of
the proposed algorithms and demonstrate a high
usefulness and scalability of our novel generalized
subgraph attribution.

• Machine Intelligence