提出可精确计算GNN归因的多项式架构,避免数值近似误差。
A Polynomial Architecture-Attribution Co-Design Framework for Exact Aumann-Shapley Attribution in GNNs

- 设计多层多项式消息传递网络,使归因积分可精确求解。
- 仅需2^(L-1)次评估即可精确计算特征级归因,比传统方法少90%以上。
- 适合需要高精度归因解释的GNN应用,如医疗、金融图分析。
本文研究基于Aumann-Shapley归因的图神经网络(GNN)特征级与节点级解释。现有路径积分方法如Integrated Gradients虽具公理基础,但实际使用中依赖有限样本数值近似,需在积分误差与计算成本间权衡。本文提出APEX框架,通过模型与归因协同设计,使归因积分在多项式GNN架构下可精确计算。核心是PolyGIN,一种类似GIN的图网络,其消息传递、归一化与变换操作保持标量模型输出(如预软最大值对数概率)的有界多元多项式形式。对于含L层多项式变换块的PolyGIN,归因路径导数次数至多为2^L−1。因此,使用高斯-勒让德积分可精确计算Aumann-Shapley路径积分,精度达浮点数极限,仅需2^(L−1)个确定性评估点。归因可在特征级计算后聚合为节点级得分,同时保证完备性。在合成与真实世界图基准上的实验表明,PolyGIN保持竞争力预测性能,而完整APEX框架的归因保真度优于对比基线,路径积分评估次数显著减少。
原文摘要 · Abstract (English)
We study feature-level and node-level explanations for graph neural networks (GNNs) through the lens of Aumann-Shapley attribution. Path-integral methods such as Integrated Gradients provide an axiomatic formulation of attribution, but their practical use in deep GNNs typically relies on finite-sample numerical approximations to the path integral, requiring a trade-off between quadrature error and computational cost. This paper proposes APEX, a model-attribution co-design framework that makes the attribution integral exactly computable under a polynomial GNN architecture. The key component is PolyGIN, a GIN-style graph network whose message-passing, normalization, and transformation operations preserve a bounded multivariate polynomial form for scalar model scores, such as pre-softmax logits. We show that, for a PolyGIN with $L$ polynomial transformation blocks, the derivative along the attribution path has degree at most $2^L-1$. Therefore, Gauss--Legendre quadrature can evaluate the Aumann--Shapley path integral exactly, up to floating-point precision, with $2^{L-1}$ deterministic evaluation points. The resulting attributions can be computed at the feature level and then aggregated into node-level scores while preserving completeness. Experiments on synthetic and real-world graph benchmarks show that PolyGIN maintains competitive predictive performance, while the complete APEX framework achieves higher attribution fidelity than the compared baselines and substantially reduces the number of evaluations required for path integration.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。