做GNN可解释性研究的团队终于有了高效工具——多项式时间算法让GNN-LRP从理论走向大规模应用，做图分析或模型调试的开发者可以直接用开源代码试试。
图神经网络（GNN）的可解释性对安全、公平和鲁棒性至关重要。GNN-LRP方法通过评估路径相关性提供高阶解释，优于节点/边级解释，但计算复杂度随网络深度指数增长。本文提出基于最大积算法的多项式时间算法，能在神经元级别精确、节点级别近似地找到最相关的K条路径，大幅降低计算成本。实验在流行病学、分子和自然语言基准上验证了算法的可扩展性和实用性。代码已开源。
Relevant Walk Search for Explaining Graph Neural Networks
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}.