A P OLYNOMIAL A RCHITECTURE –ATTRIBUTION C O -D ESIGN F RAMEWORK FOR E XACT AUMANN –S HAPLEY ATTRIBUTION IN GNN S
Bizu Feng1,2,3 , Zhimu Yang4 , Shuming Wang2,3 , Shaode Yu4 Yuan Cheng1,2 , Xiaojun Qian1 , Zixin Hu1,2,* 1
arXiv:2607.21094v1 [cs.LG] 23 Jul 2026
Institute of Artificial Intelligence Innovation and Industry, Fudan University, Shanghai, China 2 Shanghai Academy of AI for Science, Shanghai, China 3 Human Phenome Institute, Fudan University, Shanghai, China 4 School of Information and Communication Engineering, Communication University of China, Beijing, China [email protected], [email protected] [email protected], [email protected] [email protected], [email protected] *
Correspondence: [email protected]
A BSTRACT 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 finitesample 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 2L − 1. Therefore, Gauss–Legendre quadrature can evaluate the Aumann–Shapley path integral exactly, up to floating-point precision, with 2L−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. Keywords Graph neural networks · Explainability · Aumann–Shapley attribution · Integrated Gradients · Exact attribution
1
Introduction
Graph neural networks (GNNs) have become a standard modeling tool for graph-structured data, with applications in social networks, recommendation systems[1, 2], natural language processing[3], and molecular property prediction [4]. Their success largely comes from iterative message passing[5], which allows node representations to combine local features with multi-hop neighborhood information. However, the same mechanism also makes their predictions difficult to interpret: after several rounds of nonlinear aggregation, it is often unclear which input features, nodes, or substructures are responsible for a model output. This lack of transparency limits the use of GNNs in settings where reliable explanations are needed.
APEX
(a)
(b) Graph at 𝛼 = 1.0
𝜕𝐹 𝜕x "
Graph at 𝛼 = 𝛼!
𝐺𝐼𝑁 𝑃 𝐺 ∈ 𝐴 = 0.9
𝜕𝐹 𝜕x "
Graph at 𝛼 = 0.1
1
0
Attributing the prediction to a specific node
Inevitable Truncation Error
Path Interpolation & Perturbation "# (Compute )
𝛼
𝛼 Discrete sampling 𝑚 steps
"$!
Figure 1: Motivation of APEX. Standard path-integral attribution methods approximate the integral with numerical sampling, which introduces a trade-off between quadrature error and computation. Under the proposed polynomial architecture, the integrand has a known degree bound, allowing Gauss–Legendre quadrature to evaluate the integral exactly with a fixed number of points.
A common way to explain neural predictions is to assign attributions to input variables. Among attribution methods, Shapley-style values are attractive because they are connected to explicit axioms of fair contribution allocation. In differentiable models, continuous contribution allocation can be formulated through path methods related to the Aumann–Shapley construction. Integrated Gradients instantiates such attribution along the straight-line path from a baseline to the input[6, 7, 8]. These methods integrate the gradient of the model along a path from a baseline input to the target input. In principle, this provides a rigorous attribution rule. In practice, however, the integral is rarely available in closed form for standard GNNs, whose nonlinear activations and normalization operations make the integrand analytically difficult to handle. Figure 1 illustrates this limitation and the central motivation of APEX: conventional path attribution relies on a user-specified sampling resolution, whereas APEX uses an architecture-induced degree bound to determine a finite quadrature budget that eliminates truncation error under the stated conditions.Existing implementations therefore rely on numerical approximations such as Riemann sums. With few integration points, the attribution may suffer from non-negligible quadrature error; with many points, the computation becomes expensive because each point requires model evaluation and gradient computation. This paper addresses the above limitation from a model-attribution co-design perspective. Rather than applying a numerical attribution method to an arbitrary nonlinear GNN, we ask whether the GNN architecture can be designed so that the attribution integral becomes exactly computable. Our answer is APEX, a framework built on a polynomial GNN architecture called PolyGIN. PolyGIN replaces non-polynomial components, such as ReLU activations and standard normalization layers, with polynomial or linear operations. As a result, the model output remains a multivariate polynomial in the input node features. This algebraic structure gives a finite degree bound for the derivative along the Aumann–Shapley integration path. Once this degree bound is known, Gauss–Legendre quadrature provides an exact finite-sum evaluation of the path integral. Throughout this paper, APEX refers to the complete co-designed framework consisting of the PolyGIN predictive architecture and its architecture-certified exact attribution procedure, rather than to one aspect alone. The main idea is that if the model output is a polynomial of degree at most 2L in the input features, then the partial derivative involved in the attribution integral has degree at most 2L − 1 along the straight-line path from baseline to input. Since an m-point Gauss–Legendre rule integrates all polynomials of degree at most 2m−1 exactly, setting m = 2L−1 is sufficient to remove quadrature error under the proposed architecture. APEX therefore computes Aumann– Shapley attributions using a fixed, deterministic set of evaluation points rather than heuristic sampling. With respect to the numerical integration resolution, conventional numerical path integration requires Θ(Nstep ) gradient evaluations, whereas APEX uses an architecture-determined budget of exactly 2L−1 deterministic evaluations. Therefore, for a fixed-depth architecture, the attribution budget is independent of the user-specified integration resolution Nstep . 2
APEX
Our contributions are as follows: • We propose PolyGIN, a polynomial variant of the Graph Isomorphism Network that preserves a bounded multivariate polynomial mapping from input node features to model outputs. • We prove a degree bound for PolyGIN and show that the derivative along the Aumann–Shapley path has degree at most 2L − 1, where L is the number of polynomial transformation blocks. • We propose APEX, a GNN-specific architecture–attribution co-design framework that transforms GNN path attribution from a sampling-resolution-dependent numerical approximation problem into a finite exact computation. PolyGIN guarantees that the path integrand has degree at most 2L −1, which yields a sufficient 2L−1 point Gauss–Legendre rule for exact integration. APEX therefore eliminates quadrature truncation error under exact arithmetic, without user-specified integration resolutions or empirical convergence sweeps, whereas conventional numerical path integration requires Θ(Nstep ) gradient evaluations with accuracy dependent on the chosen Nstep . • We extend feature-level attributions to node-level explanations through additive aggregation while preserving completeness, and evaluate the resulting explanations on five graph benchmarks in terms of predictive performance, fidelity, efficiency , and exactness.
2
Related Work
2.1
Graph Neural Network Explanations and Axiomatic Path Attribution
Research on GNN explainability spans multiple paradigms, ranging from the post-hoc identification of influential graph components to the axiomatic attribution of model outputs to input variables[9]. One major line of post-hoc research focuses on identifying graph components that are influential to a trained model’s prediction. GNNExplainer learns instance-specific masks over graph structure and node features to extract a compact explanatory subgraph[10], whereas PGExplainer amortizes this process by learning a parameterized distribution over explanatory edges that can generalize across instances[11]. SubgraphX formulates explanation as a search over candidate subgraphs and uses Monte Carlo tree search together with approximate Shapley-value evaluations to identify predictive structures[12]. FlowX changes the explanatory unit from individual nodes or edges to message flows across GNN layers and estimates their relevance through a sampling- and learning-based procedure[13]. Gradient-based techniques, including saliency and Grad-CAM-style methods adapted to graph models, instead obtain node- or feature-level relevance from local derivatives and intermediate representations[14]. These methods provide useful mechanisms for selecting explanatory structures or ranking graph components, but their scores are defined through method-specific masking objectives, combinatorial search, learned explainers, or local sensitivity measures. However, these methods are generally not designed to satisfy the completeness constraint required by axiomatic path attribution and therefore do not provide a corresponding completeness guarantee. Shapley-style attribution provides a complementary perspective by defining feature contributions through explicit allocation principles. The Shapley value characterizes contribution allocation in finite cooperative games[15], while the Aumann–Shapley construction extends related principles to continuous settings[7]. For differentiable models, path attribution methods distribute the output difference between a reference input and a target input by integrating directional derivatives along a connecting path. Integrated Gradients instantiates this construction using the straightline path from a baseline to the input and satisfies properties including sensitivity and implementation invariance[6]. When the path integral is evaluated exactly, the resulting feature attributions also satisfy completeness: their sum equals the difference between the model scores at the input and the baseline. For standard neural networks, however, the path integrand generally lacks an analytically usable form. Practical implementations therefore replace the integral with a finite numerical rule, commonly using uniformly spaced samples or related composite formulas. The resulting attribution depends not only on the model and baseline but also on the selected integration budget. Increasing this budget reduces numerical error at the cost of additional forward and backward evaluations, whereas an insufficient budget can leave a nonzero completeness gap and alter the numerical values used for feature or node ranking. This issue is distinct from the combinatorial approximation used by Shapley-based graph explainers. For example, SubgraphX approximates coalition-based contributions of subgraphs, and FlowX estimates contributions associated with message flows[12, 13]. APEX instead considers continuous Aumann–Shapley attribution of input features and derives node-level explanations by additive aggregation. Its objective is not to introduce another sampling strategy, but to construct a model class for which the continuous path integral has a known finite exact evaluation budget. 3
APEX
2.2
Architectural Conditions for Exact Path Attribution
Most attribution methods treat the predictive model as fixed and subsequently approximate the explanation required for that model. A smaller line of research has shown that architectural structure can make axiomatic attribution substantially more efficient. Hesse et al. prove that bias-free, nonnegatively homogeneous neural networks admit an axiomatic attribution that can be evaluated with a single forward and backward pass[16]. Their result exploits the scaling identity of positively homogeneous functions and is naturally associated with attribution from the zero reference. It provides an important example of model–attribution compatibility, but the reduction does not directly extend to general baselines or to nonhomogeneous transformations containing additive biases and higher-order interactions. APEX follows the same broad principle that model structure can simplify attribution, but relies on a different algebraic condition. Rather than requiring the path integral to collapse to a single endpoint-gradient computation, APEX constrains the scalar input-to-logit mapping to have bounded polynomial degree. Along an arbitrary straight-line path, the corresponding derivative is then a univariate polynomial whose degree is determined by the architecture. This degree certificate yields a sufficient Gauss–Legendre evaluation budget without selecting a sampling resolution empirically or specifying an error tolerance. The resulting guarantee covers nonhomogeneous polynomial interactions and general reference inputs, while imposing its own explicit restriction: every operation affecting the attributed scalar score must preserve polynomial dependence on the input features. 2.3
Polynomial Architectures for Exact Attribution
Polynomial neural networks have previously been studied as expressive model classes rather than as mechanisms for exact attribution. Kileel et al. characterize the function spaces induced by deep networks with polynomial activations and analyze how architectural choices affect their expressive power[17]. Π-Nets construct high-order input polynomials through structured skip connections and tensorized parameterizations, demonstrating that polynomial architectures can represent nontrivial higher-order interactions rather than reducing to linear models[18]. These results motivate polynomial networks as viable predictive architectures, but they do not use the degree of the input-to-output map to determine an exact path-attribution computation. In APEX, the polynomial restriction is introduced for this specific purpose: the architecture exposes a finite degree bound, and the attribution algorithm uses that bound to select a deterministic quadrature budget. This use of polynomial structure should also be distinguished from polynomial graph filters. Spectral architectures such as Chebyshev graph convolution express the propagation operator as a polynomial in the graph Laplacian[19]. Polynomial dependence on a graph operator does not imply that the complete network is polynomial in its input node features, since subsequent activations, normalization layers, attention mechanisms, or output transformations may remain non-polynomial. APEX instead requires the complete scalar score used for attribution, such as a pre-softmax logit, to be a bounded-degree polynomial of the attributed inputs. PolyGIN realizes this condition while retaining GIN-style neighborhood aggregation[20]. The central distinction from prior polynomial architectures and graph filters is therefore not the use of polynomials itself, but the architecture–attribution co-design that converts a model-level degree bound into an exact and automatically determined Aumann–Shapley evaluation budget.
3
Methodology
This section presents the APEX framework. As summarized in Figure 2, PolyGIN constrains the input-to-logit mapping to a bounded polynomial space, whose degree bound determines a sufficient finite evaluation budget for exact Gauss–Legendre quadrature. The resulting feature-level attributions are then additively aggregated into signed nodelevel explanations while preserving completeness. We first formulate the attribution problem, then define the PolyGIN architecture, establish its degree bound, derive the exact quadrature rule, and present the node-level aggregation. 3.1
Problem Formulation
Let f be a trained graph model and let X ∈ RN ×d be the input node-feature matrix. For simplicity, we write the flattened input features as x1 , . . . , xn , where n = N d. In classification tasks, f denotes the scalar score of the target class, implemented as the pre-softmax logit rather than the post-softmax probability. This distinction is important because a softmax layer would introduce non-polynomial operations and would therefore fall outside the exactness guarantee of APEX. Given a baseline input X ′ , the straight-line attribution path is γ(τ ) = X ′ + τ (X − X ′ ), 4
τ ∈ [0, 1].
(1)
APEX
Input Graph
PolyGIN
Exact Attribution Gradients at 𝑚 Quadrature Points
Aggregation
𝑁, 𝑑$% ×𝑚
Linear 𝑊! Topology 𝐴 ∈ {0,1})×)
∇/𝑓 𝑋& ∇/𝑓 𝑋' ∇/𝑓 𝑋(
PolyScaleNorm
𝜏 = 1 Node Feature 𝑋 ∈ ℝ )×,!" 𝑋# = 𝑋’ + 𝜏# (𝑋 − 𝑋’) 𝜏!
𝑋!
𝜏"
𝑋"
……
……
…… 𝜏(
𝑋(
Poly Activation
×𝐿
𝑧! ⊙ 𝜃
𝑧
× 𝑤'
⨀
⨁
𝑋 − 𝑋’ 2
× 𝑤(
...
× 𝑤)
× 𝑤*
⨁Baseline Difference
𝜙!,! 𝜙!," 𝜙!,' 𝜙",!
Linear 𝑊" ReadOut
𝑁, 𝑑!"#
Φ-
...
'01
Φ# = , 𝜙#,$ $%&
1, 𝑑!"# 1, 1
Linear 𝜏=0
× 𝑤&
∇/𝑓 𝑋)
𝑆𝑢𝑚 (dim = 1) - Φ+ = 𝑓 𝑋 − 𝑓 𝑋 . +∈𝒱
𝑓 𝑋#
Signed Node Attribution
𝑚 = 2$%!
Figure 2: Overview of the APEX computation. PolyGIN constrains the model output to a bounded polynomial space. This gives a degree bound for the derivative along the attribution path, allowing APEX to replace numerical path sampling with exact Gauss–Legendre quadrature. For a target output f (X), the Aumann–Shapley attribution of feature xi is Z 1 ∂f (γ(τ )) ϕi = (xi − x′i ) dτ. ∂xi 0
(2)
This is the straight-line path attribution used by Integrated Gradients [6]. The main computational challenge is evaluating the integral in Eq. (2). Standard IG approximates it with a finite numerical sum. APEX instead designs f so that the integrand is a bounded-degree polynomial in τ , allowing exact quadrature. 3.2
PolyGIN: A Polynomial Graph Architecture
PolyGIN follows the neighborhood aggregation structure of GIN but replaces the nonlinear transformation module with polynomial and linear operations. This ensures that the model output remains a multivariate polynomial in the input node features. Definition 1 (PolyActivation). Given a vector z, the polynomial activation is σpoly (z) = z + θ ⊙ z 2 ,
(3) 2
where θ is a learnable parameter vector, ⊙ denotes element-wise multiplication, and z is applied element-wise. The linear term preserves an identity path, while the quadratic term introduces nonlinear feature interactions. Since the operation is polynomial, it preserves algebraic tractability. Definition 2 (PolyScaleNorm). Given a vector z, PolyScaleNorm is defined as Normpoly (z) = s ⊙ z,
(4)
where s is a learnable dimension-wise scaling vector. A PolyGIN layer first performs the injective sum-aggregation form introduced by GIN [20], unlike normalization layers that divide by data-dependent statistics, PolyScaleNorm is a linear scaling operation and therefore does not destroy the polynomial form. 5
APEX
(l)
Definition 3 (Polynomial GIN Layer). Let hv denote the representation of node v at layer l. A PolyGIN layer first performs GIN-style aggregation, X (l) (l−1) a(l) + h(l−1) , (5) v = (1 + ϵ )hv u u∈N (v)
and then applies a polynomial transformation, (l) (l) (l) h(l) , v = W2 σpoly Normpoly W1 av (l)
(6)
(l)
where W1 and W2 are learnable linear maps. Because aggregation, linear projection, and PolyScaleNorm are linear, and PolyActivation is polynomial, each PolyGIN layer maps polynomial representations to polynomial representations. 3.3
Degree Bound of PolyGIN
The exactness of APEX relies on knowing the degree of the attribution integrand. The following theorem gives the required bound. Theorem 1 (Degree Bound). Consider a PolyGIN network with L polynomial transformation blocks, each containing one PolyActivation. If the network output is denoted by y = f (L) (X), then y is a multivariate polynomial in the input features X with degree at most 2L . Consequently, for any input feature xi , the partial derivative ∂y/∂xi has degree at most 2L − 1. Proof. Let deg(·) denote the maximum polynomial degree with respect to the original input features. At the input layer, h(0) = X, so deg(h(0) ) = 1. Suppose that h(l−1) has degree at most 2l−1 . The aggregation step, linear projections, and PolyScaleNorm are all linear transformations, so they do not increase the degree. PolyActivation maps a representation z to z + θ ⊙ z 2 . Therefore, deg z + θ ⊙ z 2 ≤ max{deg(z), 2 deg(z)} ≤ 2l . (7) By induction, the output after L polynomial transformation blocks has degree at most 2L . Taking a first-order partial derivative reduces the degree of each nonconstant monomial by one, so ∂y/∂xi has degree at most 2L − 1. The bound is stated as an upper bound because degenerate parameter choices may reduce the realized degree. The upper bound is sufficient for choosing an exact quadrature rule. Remark on numerical stability. The degree bound grows exponentially with the number of polynomial transformation blocks, and repeated quadratic transformations may lead to magnitude growth in intermediate representations. PolyGIN inserts PolyScaleNorm between the linear projection and the polynomial activation. Since PolyScaleNorm is a learnable diagonal scaling operation, it provides learnable rescaling of intermediate representations and helps mitigate magnitude growth in practice, without introducing non-polynomial terms or altering the degree bound. This mechanism does not, by itself, guarantee numerical stability for arbitrarily deep polynomial networks. Accordingly, we use a moderate number of polynomial transformation blocks in the experiments considered in this paper. 3.4
Exact Gauss–Legendre Quadrature for Aumann–Shapley Attribution
For a fixed feature xi , define the attribution integrand gi (τ ) =
∂f (γ(τ )) . ∂xi
(8)
Since γ(τ ) is affine in τ and ∂f /∂xi is a polynomial of degree at most 2L −1 in the input features, gi (τ ) is a univariate polynomial in τ of degree at most 2L − 1. Gauss–Legendre quadrature states that an m-point Gauss–Legendre rule integrates every polynomial of degree at most 2m − 1 exactly on [−1, 1] [21, 22]. Therefore, choosing m = 2L−1 6
(9)
APEX
is sufficient for exact integration of gi . Let {tk , wk }m k=1 be the standard Gauss–Legendre nodes and weights on [−1, 1]. After mapping the interval [−1, 1] to [0, 1] by τk = (tk + 1)/2, Eq. (2) becomes 2L−1 ∂f X ′ + tk2+1 (X − X ′ ) xi − x′i X ϕi = wk . (10) 2 ∂xi k=1
Under the PolyGIN degree bound, Eq. (10) evaluates the Aumann–Shapley integral exactly up to floating-point numerical precision. 3.5
Node-level Attribution by Additive Aggregation
APEX first computes feature-level attributions. For graph interpretation, it is often useful to aggregate these feature scores into node-level scores. Let Fv denote the set of feature indices associated with node v. The signed node-level attribution is X Φv = ϕi . (11) i∈Fv
This aggregation preserves the completeness of the feature-level attribution because summation over nodes is equivalent to summation over all input features: X v∈V
Φv =
n X
ϕi = f (X) − f (X ′ ).
(12)
i=1
Importantly, we retain Φv as a signed node-level attribution rather than converting it into a nonnegative magnitude. A positive Φv indicates that node v contributes supporting evidence to the target-class logit relative to the baseline, whereas a negative Φv represents opposing evidence against the target class. Under the PolyGIN degree bound, APEX eliminates quadrature truncation error; consequently, these signed node-level attributions preserve completeness up to floating-point precision and provide a numerically consistent decomposition of the prediction difference into supporting and opposing contributions. Such directional information cannot be represented by nonnegative importance scores alone.
4
Experiments
We evaluate APEX from three perspectives. First, we test whether PolyGIN preserves predictive performance relative to a standard GIN. Second, we evaluate explanation fidelity against representative and state-of-the-art explainability baselines. Third, we measure the completeness error and runtime of the attribution computation. We evaluate APEX on five widely used graph benchmarks covering synthetic, molecular, and textual graphs. Detailed dataset statistics are provided in Appendix A. 4.1
Research Questions
We organize the experiments around the following questions: • RQ1: Predictive performance. Does PolyGIN maintain competitive accuracy compared with a standard GIN? • RQ2: Attribution fidelity. Do APEX attributions identify explanation subsets that are necessary and sufficient for preserving the model prediction, as measured by Fidelity+ and Fidelity− ? • RQ3: Efficiency and exactness. Does APEX reduce the completeness error and the number of required model evaluations compared with numerical integration baselines? 4.2
Predictive Performance of PolyGIN
A meaningful explanation should be computed for a model with adequate predictive performance. To answer RQ1, we compare PolyGIN with a standard GIN under the same hidden dimension and batch size. All models use a hidden dimension of 300 and a batch size of 32. Dataset-specific learning rates and training epochs are reported in Table 1. For every dataset, PolyGIN increases the number of trainable parameters by only approximately 0.12%–0.17% compared with GIN. Therefore, the comparison is conducted under nearly identicalmodel capacity, and the predictive performance of PolyGIN is not obtained through a substantial increase in parameter count. We use the standard 7
APEX
train/validation/test splits for all datasets. GIN and PolyGIN use the same network depth and overall architectural configuration, differing only in the components required by the polynomial design. This matched architectural setting helps isolate the effect of the polynomial constraint on predictive performance. All models are trained using Adam with a weight decay of 5 × 10−6 , and the checkpoint with the best validation performance is selected for evaluation. Results are reported as the mean and standard deviation over ten independent runs with different random seeds. All experiments are conducted on a single NVIDIA GeForce RTX 4090 GPU. Table 1: Training configurations and predictive accuracy of GIN and PolyGIN. Dataset
Model
Learning Rate
Epochs
Params
Accuracy (%)
−4
BA-Shapes
GIN PolyGIN
1 × 10 5 × 10−5
4000 9000
546,304 547,208
97.29 ± 0.77 96.43 ± 0.71
BBBP
GIN PolyGIN
1 × 10−4 1 × 10−4
500 1000
545,402 546,306
89.90 ± 1.09 89.85 ± 0.81
BACE
GIN PolyGIN
5 × 10−5 5 × 10−5
1000 1000
545,402 546,306
83.62 ± 1.19 84.34 ± 1.86
Graph-SST2
GIN PolyGIN
1 × 10−3 1 × 10−3
20 20
773,102 774,006
90.95 ± 0.20 90.23 ± 0.17
Mutagenicity
GIN PolyGIN
1 × 10−4 1 × 10−3
100 800
546,902 547,806
81.78 ± 0.40 80.98 ± 0.61
The results show that PolyGIN achieves accuracy close to the standard GIN on all five datasets. On BACE, PolyGIN obtains a higher accuracy than GIN; on BBBP, Graph-SST2, BA-Shapes, and Mutagenicity, the decrease is below one percentage point. These results suggest that the polynomial constraint does not substantially degrade predictive performance under the evaluated experimental conditions, providing a reasonable basis for the attribution experiments. 4.3
Attribution Fidelity
To answer RQ2, we evaluate whether the selected key factors are necessary and sufficient for the model prediction. We compare APEX with representative and widely used GNN explanation baselines, including GNNExplainer[10], PGExplainer[11], GradCAM[14], FlowX[13], and Integrated Gradients [6]. We evaluate all methods on the same correctly classified test graphs and explain the model-predicted class. APEX attributes the corresponding pre-softmax logit from a zero-feature baseline and ranks nodes in descending order of their signed attribution scores. For the fidelity experiments, IG and its numerical variants use 50 integration points. Edge-based explanations are converted to node masks using the endpoints of the highest-scoring edges. Masked node features are replaced by random withingraph feature permutations while preserving the graph topology, and the resulting prediction probabilities are averaged over ten permutations. We follow the necessity–sufficiency evaluation protocol formalized in GraphFramEx [23] and evaluate all methods at matched sparsity levels. For an input graph G, let c be the class predicted by the original model and let pc (G) be the predicted probability of class c. Given an explanation subset S, let G \ S denote the graph after removing or masking the selected key factors, and let G[S] denote the graph retaining only the selected key factors. We use Fidelity+ = EG [pc (G) − pc (G \ S)] (13) for necessary explanations, where a larger value indicates that the removed components were important to the prediction. We use Fidelity− = EG [pc (G) − pc (G[S])] (14) for sufficient explanations, where a smaller value indicates that the retained components preserve the original prediction more effectively. As with removal-based fidelity metrics generally, these scores may be affected by distribution shift induced by graph perturbation; we therefore use them as comparative model-faithfulness measures under a shared perturbation protocol rather than as direct measures of semantic correctness [24]. Necessary explanations. Figure 3 compares Fidelity+ across datasets and sparsity levels. Under these experimental conditions, APEX obtains higher Fidelity+ than the compared state-of-the-art baselines across the evaluated datasets. This indicates that the key factors selected by APEX have a stronger effect on the model output when removed. These results demonstrate the framework-level effectiveness of the proposed architecture–attribution co-design under the shared evaluation protocol. 8
APEX
BBBP
BACE
Mutagenicity
0.30
0.10
0.20
0.10 0.6
0.7
Sparsity
0.8
0.9
0.30 0.20
0.05
0.10 0.5
0.40
Fidelity+
0.15
0.40
Fidelity+
0.20
BA-shapes 0.60
0.50
Fidelity+
Fidelity+
Fidelity+
Graph-SST2
0.20
0.50
0.30
0.5
0.6
APEX
0.7
Sparsity
0.8
0.9
FlowX
0.40
0.20
0.10 0.5
0.6
0.7
Sparsity
GNNExplainer
0.8
0.9
0.5
0.6
GradCAM
0.7
Sparsity
0.8
0.9
PGExplainer
0.5
0.6
0.7
Sparsity
0.8
0.9
IG
Figure 3: Necessary explanation comparison measured by Fidelity+ . Higher values indicate that the selected key factors are more necessary for preserving the original prediction.
Fidelity-
0.15 0.10
0.20
Fidelity-
0.20
Fidelity-
Graph-SST2
0.10
0.5
0.6
0.7
Sparsity
0.8
0.9
0.04
0.30
0.02
0.20
0.00
0.05 0.00
Mutagenicity
BA-shapes 0.60
Fidelity-
BACE 0.30
Fidelity-
BBBP
0.10
0.40 0.20
0.00 0.5
APEX
0.6
0.7
Sparsity
0.8
FlowX
0.9
0.5
0.6
0.7
Sparsity
GNNExplainer
0.8
0.9
0.5
GradCAM
0.6
0.7
Sparsity
0.8
PGExplainer
0.9
0.5
0.6
0.7
Sparsity
0.8
0.9
IG
Figure 4: Sufficient explanation comparison measured by Fidelity− . Lower values indicate that the retained key factors better preserve the original prediction. Sufficient explanations. Figure 4 reports Fidelity− . APEX achieves lower Fidelity− values than the compared state-of-the-art baselines under the evaluated experimental conditions, meaning that the selected key factors preserve more of the original prediction when kept alone. These results show that, under the evaluated conditions, the complete APEX framework achieves stronger sufficiency fidelity than the compared baselines. 4.4
Efficiency and Completeness Error
To answer RQ3, we evaluate both the computational cost and the attribution completeness error. For path-integral attribution,exact straight-line path attribution satisfies completeness by the fundamental theorem of calculus [6] n X
ϕi = f (X) − f (X ′ ).
(15)
i=1
For an approximate method, we measure the completeness error as ∆comp =
n X
ϕ̂i − f (X) − f (X ′ ) .
(16)
i=1
Exact continuous Aumann–Shapley attribution rigorously satisfies completeness in theory: the sum of all feature attributions equals the change in the model output relative to the baseline, with no error introduced by the attribution allocation itself. Conventional integrated gradients methods numerically approximate the continuous path integral using a finite number of sampling points; consequently, their nonzero completeness error fundamentally arises from the quadrature error induced by path discretization. Appendix C further proves that, for integrated gradients approximated using Riemann sums, the completeness error is exactly equal to the corresponding numerical quadrature error. In contrast, APEX completely eliminates this quadrature error under exact arithmetic, thereby exactly recovering the completeness property of continuous Aumann–Shapley attribution; in practical computation, only rounding errors due to finite-precision floating-point arithmetic remain. Figure 5 compares APEX with numerical integration baselines, including standard IG, trapezoidal IG, and Simpson IG[25]. The numerical baselines reduce completeness error as the number of evaluation points increases, but the error remains visible when the number of evaluations is limited. In contrast, for the 4-block PolyGIN used in our 9
APEX
APEX
IG
NFE
TrapezoidalIG
BA-shapes comp
comp
Mutagenicity 100 10 1 10 2 10 3 10 4 10 5 10 6
2 4 8 16 32 64 12 8 25 6 51 10 2 24
NFE
101 100 10 1 10 2 10 3 10 4 10 5 10 6
NFE
SimpsonIG
100 10 1 10 2 10 3 10 4 10 5 10 6
2 4 8 16 32 64 12 8 25 6 51 10 2 24
Graph-SST2 comp
BACE
2 4 8 16 32 64 12 8 25 6 51 10 2 24
NFE
101 100 10 1 10 2 10 3 10 4 10 5 10 6
2 4 8 16 32 64 12 8 25 6 51 10 2 24
comp
2 4 8 16 32 64 12 8 25 6 51 10 2 24
comp
BBBP 100 10 1 10 2 10 3 10 4 10 5 10 6
NFE
Figure 5: Completeness error with respect to the number of forward evaluations (NFE). Numerical integration baselines reduce the error gradually as more evaluation points are used. APEX reaches numerical precision at the number of points predicted by the PolyGIN degree bound. experiments, Theorem 1 gives an integrand degree bound of 24 − 1 = 15, so 24−1 = 8 Gauss–Legendre points are sufficient. With only eight evaluation points, the completeness error drops directly to the numerical precision limit of FP32, in exact agreement with the theoretical prediction. This result confirms that, under the proposed PolyGIN architecture and logit-based attribution setting, APEX does not merely reduce numerical integration error; rather, it theoretically eliminates the quadrature error induced by finite path sampling. The residual deviations are at the scale expected from finite-precision FP32 computation and are therefore consistent with floating-point roundoff rather than quadrature truncation error, rather than from approximation error in the attribution integral. Consequently, once the model depth is fixed, APEX avoids the sampling-resolution sweep required by numerical IG and achieves constantlevel integration complexity with respect to Nstep .
5
Conclusion
This paper introduced APEX, a framework for exact Aumann–Shapley attribution in polynomial graph neural networks. The central idea is to co-design the model architecture and attribution algorithm: PolyGIN constrains the GNN mapping to a bounded polynomial space, and Gauss–Legendre quadrature uses the resulting degree bound to evaluate the path integral exactly with a fixed number of deterministic points. The feature-level attributions can be aggregated into node-level explanations while preserving completeness. Experiments on five graph benchmarks show that The complete APEX framework achieves higher attribution fidelity than the compared baselines, while its architecture–attribution co-design enables exact path-integral evaluation, up to floating-point precision, with a fixed and deterministic computational budget. The exactness guarantee of APEX is conditional on the polynomial architecture and on computing attributions for scalar polynomial scores, such as logits before non-polynomial output transformations. It does not directly apply to arbitrary GNNs with ReLU activations, softmax probabilities, batch normalization, attention softmax, or other nonpolynomial components. In addition, exact quadrature guarantees mathematical completeness of the path integral under the model, but it does not by itself guarantee agreement with human-interpretable ground truth in every application. Extending comparable guarantees to broader graph architectures and studying the semantic validity of the resulting explanations are important directions for future work.
References [1] Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recommender systems: a survey. ACM Computing Surveys, 55(5):1–37, 2022. [2] Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference, pages 417–426, 2019. [3] Liang Yao, Chengsheng Mao, and Yuan Luo. Graph convolutional networks for text classification. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 7370–7377, 2019. [4] Dejun Jiang, Zhenxing Wu, Chang-Yu Hsieh, Guangyong Chen, Ben Liao, Zhe Wang, Chao Shen, Dongsheng Cao, Jian Wu, and Tingjun Hou. Could graph neural networks learn better molecular representation for drug discovery? a comparison study of descriptor-based and graph-based models. Journal of cheminformatics, 13(1):12, 2021. 10
APEX
[5] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263–1272. Pmlr, 2017. [6] Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In International conference on machine learning, pages 3319–3328. PMLR, 2017. [7] Robert J Aumann and Lloyd S Shapley. Values of non-atomic games. Princeton University Press, 2015. [8] Mukund Sundararajan and Amir Najmi. The many shapley values for model explanation. In International conference on machine learning, pages 9269–9278. PMLR, 2020. [9] Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. IEEE transactions on pattern analysis and machine intelligence, 45(5):5782–5799, 2022. [10] Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019. [11] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances in neural information processing systems, 33:19620–19631, 2020. [12] Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In International conference on machine learning, pages 12241–12252. PMLR, 2021. [13] Shurui Gui, Hao Yuan, Jie Wang, Qicheng Lao, Kang Li, and Shuiwang Ji. Flowx: Towards explainable graph neural networks via message flows. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(7):4567–4578, 2023. [14] Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann. Explainability methods for graph convolutional neural networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10772–10781, 2019. [15] Lloyd S Shapley et al. A value for n-person games. 1953. [16] Robin Hesse, Simone Schaub-Meyer, and Stefan Roth. Fast axiomatic attribution for neural networks. Advances in Neural Information Processing Systems, 34:19513–19524, 2021. [17] Joe Kileel, Matthew Trager, and Joan Bruna. On the expressive power of deep polynomial neural networks. Advances in neural information processing systems, 32, 2019. [18] Grigorios G Chrysos, Stylianos Moschoglou, Giorgos Bouritsas, Yannis Panagakis, Jiankang Deng, and Stefanos Zafeiriou. P-nets: Deep polynomial neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7325–7335, 2020. [19] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016. [20] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. [21] Gene H Golub and John H Welsch. Calculation of gauss quadrature rules. Mathematics of computation, 23(106):221–230, 1969. [22] Sang Hoon Lee, Wei Chen, and Byung Man Kwak. Robust design with arbitrary distributions using gauss-type quadrature formula. Structural and Multidisciplinary Optimization, 39(3):227–243, 2009. [23] Kenza Amara, Rex Ying, Zitao Zhang, Zhihao Han, Yinan Shan, Ulrik Brandes, Sebastian Schemm, and Ce Zhang. Graphframex: Towards systematic evaluation of explainability methods for graph neural networks. arXiv preprint arXiv:2206.09677, 2022. [24] Xu Zheng, Farhad Shirani, Tianchun Wang, Wei Cheng, Zhuomin Chen, Haifeng Chen, Hua Wei, and Dongsheng Luo. Towards robust fidelity for evaluating explainability of graph neural networks. In International Conference on Learning Representations, volume 2024, pages 12250–12275, 2024. [25] Endre Süli and David F Mayers. An introduction to numerical analysis. Cambridge university press, 2003. [26] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9(2):513–530, 2018. [27] Jeroen Kazius, Ross McGuire, and Roberta Bursi. Derivation and validation of toxicophores for mutagenicity prediction. Journal of medicinal chemistry, 48(1):312–320, 2005. 11
APEX
[28] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602–4609, 2019.
12
APEX
A
Dataset Statistics
We use BA-Shapes from GNNExplainer [10]; BBBP and BACE as curated in MoleculeNet [26]; Graph-SST2 from the structured NLP graph-explanation benchmark [9]; and the Mutagenicity dataset derived from the Ames mutagenicity collection of Kazius et al. [27]. We report the statistics of the five evaluated datasets in Table 2. The benchmarks cover synthetic node classification, molecular graph classification, and text graph classification, thereby evaluating APEX across structurally distinct graph domains. Table 2: Statistics of the evaluated datasets. NC and GC denote node and graph classification, respectively.
B
Dataset
Task
# Graphs
Avg. # Nodes
# Classes
BA-Shapes BBBP BACE Graph-SST2 Mutagenicity
NC GC GC GC GC
1 2,039 1,513 70,042 4,337
700 24.1 34.1 10.2 30.3
4 2 2 2 2
How Powerful is PolyGIN?
In this appendix, we analyze the expressive power of PolyGIN under the standard Weisfeiler–Lehman (WL) framework for message-passing graph neural networks. We follow the WL-based expressivity framework developed for messagepassing GNNs and GIN [28, 20]. Our goal is to clarify the representational role of the polynomial constraint introduced in PolyGIN. The analysis follows the same line of reasoning used to characterize the expressive power of Graph Isomorphism Networks (GIN): a message-passing GNN can be as discriminative as the 1-dimensional WL test if its neighborhood aggregation, node update, and graph-level readout functions are injective over the corresponding multisets. We show that PolyGIN has the same upper bound as standard message-passing GNNs: it cannot distinguish graph pairs that 1-WL fails to distinguish. We then show that, under an explicit injectivity condition on the polynomial transformation and graph-level readout, PolyGIN can match the discriminative power of 1-WL. This conditional statement is important: the polynomial degree guarantee used by APEX for exact Aumann–Shapley quadrature does not by itself imply WL-level expressive power. Rather, the exactness guarantee and the WL expressivity guarantee concern two different properties of the architecture. B.1
Preliminaries
Let G = (V, E) be a graph with node features xv for v ∈ V . We consider a message-passing architecture in which each node representation is updated by aggregating the representations of its neighbors. PolyGIN follows the GIN aggregation rule but replaces the usual nonlinear transformation module with polynomial and linear operations. Specifically, the ℓ-th PolyGIN layer computes: X (ℓ) (ℓ−1) a(ℓ) + h(ℓ−1) , (17) v = (1 + ϵ )hv u u∈N (v) (ℓ)
(ℓ)
followed by hv = Pℓ (av ), where: (ℓ) (ℓ) Pℓ (z) = W2 σpoly Normpoly W1 z , σpoly (z) = z + θ(ℓ) ⊙ z 2 , (ℓ)
Normpoly (z) = s(ℓ) ⊙ z.
(18)
(19)
(ℓ)
Here W1 and W2 are learnable linear maps, s(ℓ) is a learnable scaling vector, and θ(ℓ) controls the quadratic polynomial activation. We assume throughout this appendix that the input feature universe is countable and that node degrees are bounded. This is the same setting commonly used in WL-style expressivity analyses of message-passing GNNs[20, 28]. For a finite graph dataset, this assumption is automatically satisfied when node features are categorical, discrete labels, or finite-precision vectors. 13
APEX
We also use A multiset is a set-like object that allows repeated elements. For a node v, the n the notion of a multiset. o (ℓ−1) collection hu : u ∈ N (v) is naturally a multiset, since different neighbors may have identical representations. The 1-dimensional WL test iteratively refines node colors by hashing the pair consisting of a node’s current color and the multiset of its neighbors’ current colors. Thus, at iteration ℓ, WL assigns a new color according to: n o (ℓ−1) c(ℓ) , c(ℓ−1) : u ∈ N (v) , (20) v = HASH cv u where HASH is injective on all distinct pairs. A message-passing GNN can match the WL refinement process only if its update rule preserves the distinctness of these pairs. B.2
PolyGIN is Upper Bounded by 1-WL
We first establish that PolyGIN cannot be more powerful than the 1-WL test. This upper bound is not specific to the polynomial transformation; it follows from the fact that PolyGIN is a permutation-invariant neighborhood aggregation architecture. B.2.1
Proposition 1.
Let G1 and G2 be two graphs with initial node features. If the 1-WL test assigns identical color multisets to G1 and G2 at every iteration, then any PolyGIN with the same initial node features and any fixed parameters assigns identical graph-level representations to G1 and G2 , provided the graph-level readout is permutation invariant. Consequently, PolyGIN is at most as powerful as the 1-WL test in distinguishing non-isomorphic graphs. Proof. We prove by induction on the layer index ℓ that if two nodes have the same WL color after ℓ WL iterations, then PolyGIN assigns them the same representation after ℓ layers. At ℓ=0, the claim follows from the initialization: nodes with the same initial WL color have the same initial feature representation. Assume the claim holds for layer ℓ-1. Consider two nodes v and v ′ whose WL colors at iteration ℓ are the same. By the WL update rule, this means that their previous colors are the same and that their neighbor-color multisets are the same: (ℓ−1) (21) c(ℓ−1) = cv′ v and o n o n (ℓ−1) : u′ ∈ N (v ′ ) . (22) c(ℓ−1) : u ∈ N (v) = cu′ u By the induction hypothesis, nodes with the same WL color at iteration ℓ-1 have the same PolyGIN representation. Therefore, (ℓ−1) (23) h(ℓ−1) = hv′ v and o n o n (ℓ−1) : u′ ∈ N (v ′ ) (24) h(ℓ−1) : u ∈ N (v) = hu′ u as multisets. Since PolyGIN uses a permutation-invariant sum aggregation, the aggregated vectors are equal: X X (ℓ−1) (ℓ−1) (ℓ) (ℓ) (ℓ−1) a(ℓ) + h(ℓ−1) = (1 + ϵ(ℓ) )hv′ + hu′ = av′ . v = (1 + ϵ )hv u
(25)
u′ ∈N (v ′ )
u∈N (v)
Applying the same polynomial transformation Pℓ to both sides gives (ℓ)
(ℓ)
(ℓ) h(ℓ) v = Pℓ (av ) = Pℓ (av ′ ) = hv ′ .
(26)
Thus, the claim holds for layer ℓ. If 1-WL assigns the same color multiset to G1 and G2 at every iteration, then after every PolyGIN layer the two graphs also have the same multiset of node representations. Any permutationinvariant graphlevel readout must therefore produce the same graph representation for both graphs. Hence PolyGIN cannot distinguish any pair of graphs that 1-WL cannot distinguish. This proposition shows that the polynomial design does not move PolyGIN beyond the standard 1-WL expressivity barrier of message-passing GNNs. In particular, PolyGIN cannot distinguish classical 1-WL-indistinguishable graph pairs such as certain regular graph pairs without additional structural information or higher-order mechanisms. 14
APEX
B.3
Injectivity Condition for Matching 1-WL
We now give a sufficient condition under which PolyGIN matches the discriminative power of 1-WL. The central issue is whether the PolyGIN update maps distinct WL refinement pairs to distinct node representations. n o (ℓ) (ℓ−1) (ℓ−1) For each layer ℓ, define the WL refinement pair associated with node v as Pv = hv , hu : u ∈ N (v) . PolyGIN first maps this pair to X + h(ℓ−1) , (27) Sℓ Pv(ℓ) = (1 + ϵ(ℓ) )h(ℓ−1) v u u∈N (v)
and then applies Pℓ . Therefore, the effective update function is Uℓ = Pℓ ◦ Sℓ . We now state the layer-wise injectivity assumption. B.3.1
Assumption 1.
For every layer ℓ, the effective PolyGIN update n o (ℓ−1) h 7→ h(ℓ) , : u ∈ N (v) Uℓ : h(ℓ−1) v u v
(28)
is injective over all node-centered rooted neighborhoods that can occur in the considered graph family. Equivalently, for any two distinct pairs (c, X) ̸= (c′ , X ′ ), where c, c′ are center-node representations and X,X’ are bounded-size multisets of neighbor representations, we require ! ! X X (ℓ) (ℓ) ′ ′ Pℓ (1 + ϵ )c + x ̸= Pℓ (1 + ϵ )c + x . (29) x′ ∈X ′
x∈X
P This assumption separates two possible sources of collision. First, the GIN-style sum (c, X) 7→ (1 + ϵ)c + x∈X x must not collapse distinct center-neighborhood pairs. Second, the polynomial transformation Pℓ must not collapse distinct aggregated vectors that encode different WL refinement pairs. The first part is the same multiset-injectivity issue addressed in the GIN analysis. For countable feature spaces and bounded multisets, the GIN analysis establishes the existence of injective sum-based multiset encodings [20]. The second part is specific to PolyGIN: the polynomial block must preserve the distinctness of the relevant aggregated values. B.3.2
Proposition 2.
Let Aℓ denote the set of aggregated representations that can occur at layer ℓ. Consider the polynomial transformation (ℓ) Pℓ defined in Eqs. (18)–(19). Suppose that W1 is injective on Aℓ , every entry of s(ℓ) is nonzero, and there exists a constant Bℓ > 0 such that every coordinate of (ℓ) a ∈ Aℓ , (30) Normpoly W1 a , lies in [−Bℓ , Bℓ ]. If (ℓ)
θj (ℓ)
for every coordinate j, and W2 injective on Aℓ .
<
1 2Bℓ
(31)
is injective on the representations produced by the polynomial activation, then Pℓ is
(ℓ)
Proof. Since W1 is injective on Aℓ and every entry of s(ℓ) is nonzero, the linear projection and PolyScaleNorm preserve the distinctness of the aggregated representations. For the j-th coordinate, the polynomial activation in Eq. (19) is the scalar function (ℓ) qj (t) = t + θj t2 . (32) For every t ∈ [−Bℓ , Bℓ ], its derivative satisfies (ℓ)
(ℓ)
qj′ (t) = 1 + 2θj t ≥ 1 − 2 θj 15
Bℓ > 0.
(33)
APEX
Therefore, qj is strictly increasing and hence injective on [−Bℓ , Bℓ ]. Since the polynomial activation is applied (ℓ) element-wise, it preserves the distinctness of all representations in the relevant domain. Finally, because W2 is injective on the resulting representations, the complete transformation Pℓ is injective on Aℓ . For a finite graph family or dataset, Aℓ is finite and therefore bounded, so such a constant Bℓ exists. Moreover, the condition permits nonzero values of θ(ℓ) , and thus injectivity does not require removing the quadratic term. Proposition 2 gives explicit sufficient conditions under which the polynomial transformation Pℓ preserves distinct aggregated representations. Therefore, if the GIN-style aggregation is injective and the conditions of Proposition 2 hold, then the effective update Uℓ = Pℓ ◦ Sℓ satisfies the layer-wise injectivity condition in Assumption 1. B.4
PolyGIN Can Match 1-WL Under Injective Updates
Theorem 2. Consider an L-layer PolyGIN. Assume that the input feature universe is countable, neighborhood sizes are bounded, Assumption 1 holds for every layer, and the graph-level readout is injective over multisets of node representations. Then PolyGIN is as powerful as the 1-dimensional Weisfeiler–Lehman test: for any two graphs G1 and G2 , if 1-WL distinguishes G1 and G2 within L iterations, then PolyGIN maps G1 and G2 to different graph-level representations. (ℓ)
(ℓ)
Proof. We prove that, for every layer ℓ, the PolyGIN representation hv uniquely determines the WL color cv , and distinct WL colors are assigned distinct PolyGIN representations. At ℓ = 0, the claim follows from the initialization. Nodes with different initial features have different initial WL colors. Under a one-hot or otherwise injective initial feature encoding, different initial WL colors correspond to different initial PolyGIN representations. Assume the claim holds for layer ℓ − 1. Consider two nodes v and v ′ . If their WL colors at iteration ℓ are different, then by the WL refinement rule, o n n o (ℓ−1) (ℓ−1) : u′ ∈ N (v ′ ) . (34) c(ℓ−1) , c(ℓ−1) : u ∈ N (v) ̸= cv′ , cu′ v u By the induction hypothesis, different WL colors at iteration ℓ − 1 correspond to different PolyGIN representations. Therefore, the two WL refinement pairs induce two distinct PolyGIN representation pairs: n o n o (ℓ−1) (ℓ−1) h(ℓ−1) , h(ℓ−1) : u ∈ N (v) ̸= hv′ , hu′ : u′ ∈ N (v ′ ) . (35) v u By Assumption 1, the effective PolyGIN update Uℓ is injective over such pairs. Hence, o n o n (ℓ) (ℓ−1) (ℓ−1) ′ ′ (ℓ−1) (ℓ−1) h(ℓ) = U : u ∈ N (v ) = hv′ . h , h : u ∈ N (v) = ̸ U , h h ′ ′ ℓ ℓ v v u u v
(36)
Thus, distinct WL colors at iteration ℓ are mapped to distinct PolyGIN representations. This proves the induction step. Now suppose 1-WL distinguishes G1 and G2 within L iterations. Then for some ℓ ≤ L, the multisets of WL colors over the nodes of G1 and G2 differ: n o n o (ℓ) c(ℓ) : v ∈ V (G ) = ̸ c : v ∈ V (G ) . (37) 1 2 v v By the result above, the corresponding multisets of PolyGIN node representations also differ: n o n o (ℓ) h(ℓ) v : v ∈ V (G1 ) ̸= hv : v ∈ V (G2 ) .
(38)
If the graph-level readout is injective over node-representation multisets, then the graph representations of G1 and G2 are different. Therefore, PolyGIN distinguishes every graph pair distinguished by 1-WL within L iterations. Combining Proposition 1 and Theorem 2 yields the following corollary. Corollary 1. Under the injective-update and injective-readout conditions in Theorem 2, PolyGIN has exactly the same graph discriminative power as the 1-WL test. Without these injectivity conditions, PolyGIN remains upper bounded by 1-WL but may be strictly less powerful. 16
APEX
B.5
Discussion: Polynomial Exactness Does Not Imply Injectivity
Theorem 2 should be read as a conditional expressivity result. It does not state that every parameterization of PolyGIN is maximally expressive. Indeed, no such unconditional claim is possible. The polynomial design of PolyGIN was introduced for a different purpose: to ensure that the scalar model output remains a bounded-degree multivariate polynomial in the input features. This property allows the derivative along the Aumann–Shapley path to have a known finite degree, which in turn enables exact Gauss–Legendre quadrature. The degree argument controls the algebraic form of the model output; it does not automatically control whether two different graph neighborhoods are mapped to two different hidden representations. (ℓ)
A simple example illustrates the distinction. If W2 = 0 in some layer, then Pℓ maps every aggregated vector to the zero vector. The layer is polynomial and satisfies the degree bound, but it is clearly non-injective and destroys (ℓ) (ℓ) all neighborhood information. More generally, if W1 , W2 , or the polynomial activation parameters collapse two distinct aggregation values, then the resulting PolyGIN layer cannot simulate the injective hashing step of WL. Therefore, PolyGIN has two logically separate guarantees: • 1. Algebraic exactness for attribution. Because aggregation, linear projection, PolyScaleNorm, and PolyActivation are polynomial or linear operations, the model output has a bounded polynomial degree. This yields an exact finite Gauss–Legendre rule for Aumann–Shapley attribution under the stated assumptions. • 2. WL-level discriminative power under injectivity. If the effective layer-wise update and the graph-level readout are injective over the relevant multisets, then PolyGIN matches the expressive power of 1-WL. These two properties are compatible but not equivalent. The first is guaranteed by the polynomial architecture. The second requires the polynomial transformations to preserve the distinctness of WL refinement pairs.
C
Equivalence Between Completeness Error and Quadrature Error
This section shows that the completeness error in Eq. (16), also referred to as the efficiency gap in some attribution literature, is equivalent to the quadrature error of the numerical path integral for Riemann-sum Integrated Gradients. This equivalence justifies using completeness error as an empirical proxy for the truncation error introduced by numerical path integration. Theorem 3. Let F : Rn → R be continuously differentiable. For an input X ∈ Rn , a baseline X ′ ∈ Rn , and the straight-line path γ(α) = X ′ +α(X −X ′ ), the completeness error of an m-step Riemann approximation to Integrated Gradients equals the absolute quadrature error of the corresponding path integral. Proof. The exact Aumann–Shapley attribution for feature i is Z 1 ∂F (γ(α)) ϕi (X) = (xi − x′i ) dα. ∂xi 0 Summing over all features and applying the chain rule gives Z 1X n n X ∂F (γ(α)) ϕi (X) = (xi − x′i ) dα ∂x i 0 i=1 i=1 Z 1 dF (γ(α)) = dα dα 0 = F (X) − F (X ′ ).
(39)
(40) (41) (42)
An m-step right Riemann approximation gives n X
m
ϕ̂i (X) =
i=1
1 X dF (γ(k/m)) . m dα
(43)
k=1
The quadrature error of this approximation is m
Z 1
k=1
0
1 X dF (γ(k/m)) Rm = − m dα 17
dF (γ(α)) dα. dα
(44)
APEX
Substituting the expressions above yields n X
ϕ̂i (X) − F (X) − F (X ′ ) .
(45)
Taking the absolute value gives exactly the completeness error: n X |Rm | = ϕ̂i (X) − F (X) − F (X ′ ) .
(46)
Rm =
i=1
i=1
Thus the empirical completeness error measures the quadrature error of the numerical path integral.
D
Disentangling Architecture and Attribution Algorithm
A possible confounding factor is that the explanation performance may arise from the PolyGIN architecture alone rather than from the explanation mechanism. To control for this factor, we evaluate multiple explainers on the same trained PolyGIN models. In this setting, all methods receive the same underlying predictive model and differ only in how they construct their explanations.
BBBP
BACE
Mutagenicity
0.10
0.30 0.20
0.5
0.6
0.7
Sparsity
0.8
0.9
0.10
0.10 0.05
0.5
0.6
APEX
0.7
Sparsity
0.8
0.9
FlowX
0.40
Fidelity+
0.15
0.40
Fidelity+
0.20
BA-shapes 0.60
0.50
Fidelity+
Fidelity+
0.30
Fidelity+
Graph-SST2
0.20
0.50
0.30 0.20
0.40 0.20
0.10 0.5
0.6
GNNExplainer
0.7
Sparsity
0.8
0.9
0.5
GradCAM
0.6
0.7
Sparsity
0.8
0.9
PGExplainer
0.5
0.6
IG
0.7
Sparsity
0.8
0.9
Figure 6: Fidelity+ comparison when all explainers are evaluated on the same PolyGIN models.
BBBP
BACE
0.20
Mutagenicity
BA-shapes
0.30
0.80
0.00 0.5
0.6
0.7
Sparsity
0.8
0.9
0.10 0.00
0.02
0.20
Fidelity-
Fidelity-
0.10
0.20
Fidelity-
0.04
Fidelity-
Fidelity-
Graph-SST2
0.30
0.10
0.00 0.5
0.6
0.7
Sparsity
FlowX
0.8
0.9
0.5
0.6
GNNExplainer
0.7
Sparsity
0.8
0.9
GradCAM
0.40 0.20
0.00
APEX
0.60
0.5
0.6
0.7
Sparsity
0.8
PGExplainer
0.9
0.5
IG
0.6
0.7
Sparsity
0.8
0.9
Figure 7: Fidelity− comparison when all explainers are evaluated on the same PolyGIN models. Figures 6 and 7 show that numerical Integrated Gradients achieves fidelity results nearly identical to those of APEX when both are applied to PolyGIN. This agreement is theoretically expected because APEX and numerical IG target the same Aumann–Shapley attribution, although they evaluate the corresponding path integral differently. The close empirical agreement therefore provides a consistency check that APEX recovers the intended continuous path attribution rather than defining a different explanation quantity. In contrast, the other explanation methods do not exhibit substantial improvements when applied to the same PolyGIN models, and several methods even show degraded fidelity performance. This indicates that the polynomial architecture alone does not necessarily improve arbitrary post-hoc explainers. Rather, the proposed contribution is the specific co-design of a polynomial predictive architecture and its compatible exact path-attribution procedure.APEX does not introduce an attribution quantity different from Aumann–Shapley attribution. Instead, it jointly specifies an attribution-compatible predictive architecture and an architecture-certified procedure for evaluating the corresponding continuous attribution exactly within a finite deterministic budget. The same-backbone agreement between APEX and numerical IG validates the target attribution recovered by the framework; it does not imply that the framework-level fidelity can be causally assigned to the architecture alone, nor does it treat the architecture and attribution procedure as interchangeable standalone contributions. Accordingly, the results should be interpreted as evidence for the complete PolyGIN–exact-attribution co-design. 18
APEX
E
Runtime Analysis
We further compare the runtime required to generate one explanation. State-of-the-art learning-based explainers such as GNNExplainer can be costly because they optimize an instance-specific mask for each instance [10]. Numerical IG avoids mask optimization but requires many path samples to reduce quadrature error [6]. APEX requires only the number of Gauss–Legendre points determined by the degree bound. In our 4-block PolyGIN setting, this corresponds to eight forward-backward evaluations. As shown in Figure 8, APEX is substantially faster than dense numerical integration methods while maintaining exact quadrature under the PolyGIN assumptions. GradCAM-like gradient methods may use fewer backward passes, but their fidelity results in Section 4.3 indicate that this lower cost comes with weaker attribution quality under the evaluated settings. Overall, APEX targets a practical trade-off: exact pathintegral attribution for the polynomial model with a small, deterministic evaluation budget. APEX
GNNExplainer
IG
GradCAM
3.0
Time (s)
2.5 2.0 1.5 1.0 0.5 0.0
BBBP
BACE
Graph-SST2
Mutagenicity
BA_shapes
Figure 8: Average runtime for generating one graph explanation.
19
APEX
Node 369
Node 469
Positive (+)
-1
-0.5
Near zero
Target node
0
Signed node attribution
Node 564
Motif node
+0.5
+1
Figure 9: Qualitative visualization of APEX signed node attributions on BA-Shapes. The target node is marked by a red boundary, and motif nodes are marked by black boundaries. Red indicates positive contribution to the target-class logit, blue indicates negative contribution, and white indicates near-zero contribution. Across different target nodes, APEX consistently assigns positive evidence to the complete house motif while leaving most BA-backbone nodes nearly neutral, matching the ground-truth structural rule of the dataset.
F
Additional Qualitative Results
Signed attribution visualization. We provide additional qualitative examples to illustrate how APEX explains graph predictions through signed node-level attributions. Many mask- and subgraph-based explainers used in our comparison produce non-negative selection or importance scores, which typically assign non-negative importance scores to nodes, edges, or subgraphs, APEX directly decomposes the target-class prediction into positive and negative evidence. In our visualization, red nodes have positive attribution and therefore support the displayed target class, while blue nodes have negative attribution and therefore suppress it. White nodes have near-zero contribution. All scores are normalized to [−1, 1] for visualization only. This distinction is crucial: an important node is not necessarily supportive. A token, atom, or structural component may be highly relevant precisely because it argues against the predicted class. APEX’s positive and negative node attributions are grounded in a rigorous Aumann–Shapley axiomatic foundation and constitute a complete signed decomposition of changes in the model output. BA-Shapes. Figure 9 presents explanations on BA-Shapes, a synthetic node-classification benchmark constructed by attaching five-node house motifs to a Barabási–Albert backbone. Node labels encode distinct structural roles within the resulting graph. For each example, we visualize the local ego graph of the target node. The target node, which is itself part of the house motif, is outlined in red, while the remaining nodes of the corresponding ground-truth motif are outlined in black. Across all three examples, APEX clearly separates the class-defining house structure from the surrounding BA backbone. The four non-target nodes of the house motif consistently receive positive attribution, with the strongest positive evidence concentrated on a subset of structurally informative motif nodes. In contrast, the target node itself has a nearzero attribution in these examples. Most nodes in the surrounding BA backbone also receive negligible attribution, although the backbone node at the motif attachment point exhibits a small positive contribution. These explanations closely match the construction of BA-Shapes: the prediction is primarily supported by the target node’s local house structure rather than by the large high-degree neighborhood of the BA backbone. In particular, APEX does not simply select the most densely connected region. It localizes the positive evidence to the groundtruth motif while assigning substantially smaller contributions to structurally irrelevant backbone nodes. The signed visualization therefore reveals both where the model obtains its evidence and the direction in which each node affects the target-class score. 20
APEX
Pred=1 True=1 can
usually
be
traced
back to the
Pred=0 True=0 little
things
painful
Pred=1 True=1 a moving
tragedy
-1
heart
or
-0.5
grey
zone
it progresses in such a low - key manner that it risks monotony
with some buoyant human moments
conservative
the
Pred=0 True=0
Pred=1 True=1 of
as
Pred=0 True=0 of
spirit
a
0
mess
Signed node attribution
from
+0.5
start
to
finish
+1
Figure 10: Token-level signed attribution visualizations of APEX on Graph-SST2. All examples shown are correctly classified, with labels 1 and 0 denoting positive and negative sentiment, respectively. Token colors indicate the direction and relative magnitude of each token’s contribution to the logit of the predicted class: positive values support the prediction, whereas negative values suppress it. Attribution scores are normalized to ([-1, 1]).
Graph-SST2. Figure 10 shows token-level signed attributions on Graph-SST2. Each sentence is represented as a graph, and APEX assigns a signed contribution to each token with respect to the displayed predicted class. Since all shown examples are correctly classified, the explanations can be inspected directly against human sentiment intuition. For positive-sentiment predictions, APEX highlights tokens such as “can”, “moving”, “buoyant”, and “heart” as positive evidence, while words with negative or contrastive semantics, such as “tragedy” and “conservative”, receive negative attribution. Conversely, for negative-sentiment predictions, tokens such as “painful”, “mess”, and “risks” are assigned positive attribution because they support the negative class. Other tokens, including neutral syntactic connectors or semantically opposing words, receive weak or negative contributions. These examples demonstrate a qualitative advantage of signed attribution over ordinary saliency ranking. A nonnegative explanation can identify which words are important, but it cannot distinguish whether an important word supports or contradicts the predicted class. APEX separates these two cases explicitly. This is especially useful for sentiment analysis, where sentences often contain mixed evidence, contrastive phrases, or locally negative words inside globally positive sentences. Molecular graphs. Figure 11 visualizes signed atom-level attributions on molecular property prediction tasks. We consider examples from BBBP, BACE, and Mutagenicity. The label semantics used in the visualization are summarized in Table 3. The examples demonstrate that APEX resolves a molecular prediction into spatially localized and directionally opposing structural evidence, rather than producing a direction-agnostic ranking of important atoms. The BBBP examples show that APEX represents blood–brain barrier permeability as a balance of competing local structural contributions. For the BBB-impermeable molecule in the first column, positive evidence is concentrated on selected atoms of the sulfur-containing fused core and the adjacent carbon framework. By contrast, several carbonyl, hydroxyl, and other oxygen-containing sites contribute negatively to the impermeable-class score. The explanation therefore identifies a specific core region as the dominant source of the model’s impermeability prediction, rather than assigning uniformly positive importance to all polar atoms in the molecule. For the first BBB-permeable molecule, the 21
APEX
-1
pred=0 true=0
pred=1 true=1
pred=1 true=1
pred=0 true=0
pred=1 true=1
pred=1 true=1
pred=0 true=0
pred=1 true=1
pred=1 true=1
-0.5
0
Signed node attribution
+0.5
+1
Figure 11: Signed atom-level attributions on molecular property prediction datasets. Rows correspond to BBBP, BACE, and Mutagenicity examples, respectively. Red atoms support the displayed target class, blue atoms oppose it, and white atoms have near-zero contribution. APEX highlights chemically meaningful evidence, including BBB-relevant polarity and scaffold effects, BACE-related hydrophobic pharmacophore fragments, and mutagenicityassociated structural alerts such as nitro groups. These examples demonstrate that APEX provides direction-aware molecular explanations rather than merely identifying important atoms.
carbonyl-centered linker and its adjacent attachment atom provide the strongest negative evidence, whereas the carbon atoms in the right-hand heterocyclic ring contribute positively to the permeable class. The second permeable example exhibits an equally clear competition: the imide-like NH is the strongest positive contributor, and the terminal alkyl substituent also supports permeability, while the two carbonyl regions and part of the aryl–heterocycle connection oppose the prediction. Taken together, these examples show that APEX does not reduce BBB permeability to a single atom type or global polarity rule. Instead, it distinguishes the contributions of chemically different local environments within the same molecule. The negative contributions of carbonyl-rich regions in the two permeable examples are consistent with the permeability cost commonly associated with exposed polarity and hydrogen-bonding capacity, 22
APEX
Table 3: Label semantics used in the molecular visualization examples. Dataset
Label 1
Label 0
BBBP BACE Mutagenicity
BBB-permeable Active inhibitor Non-mutagenic
BBB-impermeable Inactive molecule Mutagenic
while the strong positive contribution of the NH group in the third molecule illustrates that the learned evidence remains strongly context dependent. The BACE examples reveal class evidence distributed across coordinated scaffold and substituent regions. In the inactive molecule, the terminal chlorine atom provides the strongest positive evidence for the inactive class. Additional positive contributions arise from the amide-containing linker and the terminal fluorinated region, whereas most of the fused nitrogen-containing heteroaromatic scaffold provides negative evidence. The model therefore distinguishes between opposing contributions within the same molecule rather than treating the presence of aromatic rings, heteroatoms, or halogens as uniformly indicative of activity. For the first active molecule, positive evidence extends along the central phenyl–heteroaryl axis and into the terminal alkyne-containing substituent. In contrast, the oxygenated branched region on the left and several atoms in the lower heterocyclic ring oppose the active-class prediction. In the second active molecule, APEX assigns the dominant positive evidence to the central multiring scaffold and its ring-junction region, while several peripheral nitrogen-containing, fluorinated, and heteroaromatic sites contribute negatively. The two active examples thus exhibit a common organization: activity is supported by a coherent central scaffold, while peripheral functional groups modulate the prediction in both directions. This pattern is consistent with the multi-subsite nature of BACE-1 ligand recognition, for which activity depends on the coordinated arrangement of aromatic, hydrophobic, and polar functionalities rather than on the presence of any single fragment. APEX captures this organization as a signed structure–activity decomposition, identifying both the substructures that drive the active prediction and those that weaken it. The Mutagenicity examples illustrate three distinct forms of signed molecular evidence. In the mutagenic nitroaromatic molecule, the dominant positive attribution is sharply localized at the nitro nitrogen. The nitro oxygens, the hydroxyl-containing region, and most peripheral hydrogen atoms contribute negatively to the mutagenic-class score. APEX therefore isolates the nitro center as the principal class-supportive site instead of assigning uniformly positive importance to the entire aromatic molecule. This localization recovers a well-established structural alert for mutagenicity and, at the same time, exposes substantial counter-evidence elsewhere in the molecule. The first non-mutagenic molecule exhibits the opposite organization. A single ether oxygen provides the strongest positive evidence for the non-mutagenic class, with a smaller positive contribution near the hydroxyl-containing terminus, whereas most of the surrounding carbon framework contributes negatively. The final non-mutagenic molecule is particularly informative: nearly all displayed heavy-atom attributions are negative or close to zero, despite the correct class-1 prediction. This result directly reflects the reference-based nature of signed attribution. The molecular structure decreases the target-class score relative to the chosen reference, while the final score nevertheless remains sufficient for the model to predict the non-mutagenic class.These examples demonstrate that APEX can distinguish a localized mutagenicity alert, a localized contribution supporting the non-mutagenic class, and a prediction dominated by negative referencerelative evidence. Such cases cannot be represented faithfully by a non-negative atomic importance map, which would obscure both the direction of the evidence and the qualitatively different roles played by the highlighted atoms. In general, for examples of Mutagenicity, the molecular examples show that APEX produces chemically structured signed explanations: it localizes class-supportive substructures, identifies counter-evidence within the same molecule, and exposes predictions whose interpretation depends critically on the reference output. The observed patterns agree with established structure–property or structure–activity knowledge in several cases, but the attributions describe the evidence used by the trained model rather than experimentally validated molecular mechanisms. Overall, these qualitative results show that APEX yields explanations that are structurally, linguistically, and chemically interpretable across very different graph domains. The examples should not be interpreted as definitive causal mechanisms; rather, they serve as sanity checks that the learned signed decomposition aligns with known dataset rules, human sentiment intuition, and domain-specific molecular knowledge.
23