A Polynomial Architecture-Attribution Co-Design Framework for Exact Aumann-Shapley Attribution in GNNs

• URL: http://arxiv.org/abs/2607.21094v1
• Date: Thu, 23 Jul 2026 09:26:15 GMT
• Title: A Polynomial Architecture-Attribution Co-Design Framework for Exact Aumann-Shapley Attribution in GNNs
• Abstract summary: We study feature-level and node-level explanations for graph neural networks (GNNs) through the lens of Aumann-Shapley attribution.<n>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.<n>This paper proposes APEX, a model-attribution co-design framework that makes the attribution exactly integral under a GNN architecture.
• Score: 13.870126338533346
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Hierarchical Grading in Large Language Models [0.0]
  We introduce Graded Large Language Models (GLLMs)<n>GLLMs are a framework that equips the representation space of a transformer with a grading.<n>The construction extends the theory of graded neural networks and graded transformers to autoregressive language models.
  arXiv  Detail & Related papers  (2026-07-23T20:14:48Z)
• Neural QAOA$^{2}$: Differentiable Joint Graph Partitioning and Parameter Initialization for Quantum Combinatorial Optimization [3.7086487199744127]
  We propose Neural QAOA$2$, an end-to-end differentiable framework that jointly generates graph partitions and initial parameters.<n>By integrating a generative evaluative network (GEN), our method utilizes a differentiable quantum evaluator as a high-fidelity performance surrogate.<n>Experiments on 183 QUBO, Ising, and MaxCut instances (21 to 1000 variables) demonstrate that our gradient-driven approach broadly outperforms baselines.
  arXiv  Detail & Related papers  (2026-05-13T06:43:10Z)
• Towards Scalable Persistence-Based Topological Optimization [44.16669776030478]
  Persistence-based topological optimization deforms a point cloud $X subset mathbbRd$ by minimizing objectives of the form $L(X) = ell(mathrmDgm(X))$, where $mathrmDgm(X)$ is a persistence diagram.<n>In practice, optimization is limited by two coupled issues: persistent homology is typically computed on subsamples, and the resulting topological gradients are highly sparse, with only a few anchor points receiving nonzero updates.
  arXiv  Detail & Related papers  (2026-05-09T15:47:20Z)
• Pareto-optimal Tradeoffs Between Communication and Computation with Flexible Gradient Tracking [20.36100343422038]
  This paper addresses distributed optimization problems in non-rho convexi.i.d. scenarios.<n>We propose FlexFlexGT, a flexible snapshot tracking method with numbers of local updates in each iteration.<n>We introduce an accelerated gossip-based variant termed Acc-GT, and show that it achieves a tunable-optimal trade-off between communication and computation.
  arXiv  Detail & Related papers  (2025-09-11T21:47:24Z)
• Generalization of Geometric Graph Neural Networks with Lipschitz Loss Functions [84.01980526069075]
  We study the generalization capabilities of geometric graph neural networks (GNNs)<n>We prove a generalization gap between the optimal empirical risk and the optimal statistical risk of this GNN.<n>We verify this theoretical result with experiments on multiple real-world datasets.
  arXiv  Detail & Related papers  (2024-09-08T18:55:57Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
  We study infinite-horizon average-reward Markov decision processes (AMDPs) in the context of general function approximation. We propose a novel algorithmic framework named Local-fitted Optimization with OPtimism (LOOP) We show that LOOP achieves a sublinear $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret, where $d$ and $beta$ correspond to AGEC and log-covering number of the hypothesis class respectively
  arXiv  Detail & Related papers  (2024-04-19T06:24:22Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Calibrate and Boost Logical Expressiveness of GNN Over Multi-Relational and Temporal Graphs [8.095679736030146]
  We investigate $mathcalFOC$NN, a fragment of first-order logic with two variables and counting quantifiers. We propose a simple graph transformation technique, akin to a preprocessing step, which can be executed in linear time. Our results consistently demonstrate that R$2$-GNN with the graph transformation outperforms the baseline methods on both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2023-11-03T00:33:24Z)
• Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
  We show that Adam converges to $epsilon$-stationary points with $O(epsilon-4)$ gradient complexity under far more realistic conditions. We also propose a variance-reduced version of Adam with an accelerated gradient complexity of $O(epsilon-3)$.
  arXiv  Detail & Related papers  (2023-04-27T06:27:37Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• On the approximation capability of GNNs in node classification/regression tasks [4.141514895639094]
  Graph Neural Networks (GNNs) are a broad class of connectionist models for graph processing. We show that GNNs are universal approximators in probability for node classification/regression tasks.
  arXiv  Detail & Related papers  (2021-06-16T17:46:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.