Polynormer: Polynomial-Expressive Graph Transformer in Linear Time

1 INTRODUCTION

• Prior linear graph transformers can underperform state-of-the-art GNNs on popular datasets, leaving their practical expressivity in question.Conventional GTs also face quadratic complexity, limiting their use on large graphs.Source: §1 · pp. 1–2
• An L-layer Polynormer can represent a permutation-equivariant polynomial of degree 2L, with coefficients controlled by attention scores.Its local and global attention models incorporate graph topology and node features separately.Source: §1 · p. 2
• Polynormer with ReLU improves accuracy over GNN and GT baselines by up to 4.06% across 11 of 13 node-classification datasets.The datasets include both homophilic and heterophilic graphs.Source: §1 · p. 2
• Even without activation functions, Polynormer surpasses state-of-the-art GNN and GT baselines on multiple datasets.The paper evaluates 22 competitive models on 13 node-classification datasets.Source: §1 · p. 2
• The proposed local-to-global attention avoids dense attention matrices and expensive positional or structural encodings, giving linear complexity and scalability to graphs with millions of nodes.The model integrates graph topology and node features through local and global equivariant attention modules.Source: §1 · p. 2

2 BACKGROUND

• Standard graph-transformer attention uses node features to form query, key, and value matrices, then computes self-attention over nodes.The described setup assumes single-head attention without bias terms.Source: §2 · p. 2
• Positional and structural encodings add graph information to transformers, but their computation can be costly; dense attention also has quadratic complexity in node count.The cited approaches include Laplacian eigenpairs, pairwise distances, and sampled graph substructures.Source: §2 · pp. 2–3
• Polynomial networks represent each output element as a polynomial of input features, with a specified degree and learnable coefficients.The background introduces tensor-vector products to express the polynomial terms.Source: §2 · p. 3
• Polynomial equivariance means permuting input node features permutes the output in the same way.The text distinguishes polynomial networks on node features from spectral graph filters, which use polynomials of graph shift operators.Source: §2 · p. 3
• Earlier polynomial networks capture higher-order feature interactions but can struggle with high-dimensional inputs, and image- and audio-focused methods are not directly applicable to graphs.The background traces these approaches from GMDH through pi-sigma networks to P-nets.Source: §2 · p. 3
• Prior graph-polynomial models either focus on local structures or have high complexity, whereas Polynormer integrates topology into feature-polynomial coefficients for local and global information.The passage describes this integration as enabling application to large-scale graphs with linear complexity.Source: §2 · p. 3

3.1 A POLYNOMIAL-EXPRESSIVE BASE MODEL WITH ATTENTION

• Polynomial expressivity means a model can represent each node's feature multiplied elementwise by any degree-(r-1) monomial formed from input features.Typical message-passing GNNs are at most 1-polynomial-expressive, while GTs and high-order GNNs capture only subsets of monomials at a given degree.Source: §3.1 · p. 4
• An L-layer base model is 2L-polynomial-expressive, with learned attention scores controlling polynomial coefficients.The motivating scalar-feature example represents degree-2 polynomials except the constant term, with W controlling quadratic-monomial coefficients.Source: §3.1 · p. 4
• The base model lacks permutation equivariance and has O(n^2) complexity, motivating linear equivariant attention models.The base model's W and B do not exploit graph inductive bias.Source: §3.1 · p. 4

3.2 EQUIVARIANT ATTENTION MODELS WITH POLYNOMIAL EXPRESSIVITY

• Local attention uses sparse graph attention scores to impose permutation equivariance and restrict nonzero polynomial coefficients to monomials formed from nearby-node features.The method uses GAT attention for efficient implementation and leaves other sparse-attention approaches for future work.Source: §3.2 · p. 5
• Global attention uses permutation-equivariant attention scores to learn degree-2L polynomials containing global, high-order feature interactions, and a kernel trick makes its computation linear.With hidden dimension d ≪ n, local attention costs O(md + nd^2) and global attention costs O(nd^2).Source: §3.2 · p. 5

3.3 THE POLYNORMER ARCHITECTURE

• Polynormer applies local and global attention sequentially, feeding local-module outputs into the global module; ReLU can optionally be added in each layer.The authors report that the local-to-global scheme outperforms simultaneous local-and-global attention and that the architecture can be implemented without enumerating equivariant polynomials.Source: §3.3 · pp. 5–6, Figure 2 · p. 6

4 EXPERIMENTS

• The evaluation covers 13 datasets—7 homophilic and 6 heterophilic—and compares Polynormer with 10 GNNs and 6 graph transformers.For ogbn-products and pokec, the experiments use random-partition mini-batch training because the graphs do not fit in GPU memory for full-batch training.Source: §4 · pp. 6–7, §4.2 · p. 7

4.1 PERFORMANCE ON HOMOPHILIC AND HETEROPHILIC GRAPHS

• Polynormer outperforms all baselines on 3 of 5 homophilic datasets; its accuracy gain over SOTA baselines is 1.65% on Computer.Adding ReLU can further improve Polynormer’s accuracy.Source: §4.1 · p. 7, Table 1 · p. 7
• Polynormer-r surpasses all baselines on 4 of 5 heterophilic datasets and consistently outperforms them across all five, with gains up to 3.55%.The reported minesweeper comparison is 97.46% vs. 93.91%.Source: §4.1 · p. 7, Table 2 · p. 8

4.2 PERFORMANCE ON LARGE GRAPHS

• On large graphs, Polynormer-r outperforms all baselines with accuracy gains up to 4.06%; ogbn-products and pokec use random-partition mini-batch training.Removing ReLU lowers Polynormer’s ogbn-arxiv accuracy by 1.64%.Source: §4.2 · p. 7, Table 3 · p. 8

4.3 ABLATION ANALYSIS ON POLYNORMER ATTENTION SCHEMES

• Local attention is comparable to Polynormer on Computer and Photo but lags on roman-empire and minesweeper; local-to-global attention performs better than parallel local-and-global attention.The authors attribute the latter gap to possible mixing of local and non-local interactions in the parallel variant; on Computer, it performs worse than local attention alone.Source: §4.3 · pp. 8–9, Figure 3 · p. 9

4.4 VISUALIZATION

• Figure 4 compares same-label nodes within five hops, same-label nodes without that distance constraint, and Polynormer’s global attention scores; higher heatmap values indicate greater importance.On 100 sampled minesweeper nodes, the authors report that Polynormer’s attention distinguishes globally important nodes, which can contribute to accurate target-node predictions.Source: §4.4 · p. 9, Figure 4 · p. 9

• Polynormer uses a linear local-to-global attention scheme with high polynomial expressivity and achieves SOTA results on a wide range of graph datasets, even without nonlinear activation functions.Source: §5 · p. 9

• The proof defines coefficient functions over ordered node-index sets and input-feature rows, with L denoting the number of layers.Source: A PROOF FOR THEOREM 3.3 · p. 15
• It proceeds by induction from the base case L = 1 to establish the node representation for an L-layer model.Source: A PROOF FOR THEOREM 3.3 · p. 15
• For a selected degree-(2L−1) monomial, the proof parameterizes weight matrices so the resulting expression yields that monomial multiplied elementwise by node i’s features.Source: A PROOF FOR THEOREM 3.3 · p. 16

B ANALYSIS ON B IN EQUATION 4

• Without B, the base model captures degree-2L monomials but not lower degrees; incorporating B lets it capture all monomial degrees from 1 through 2L, except the constant term.B controls lower-degree monomial coefficients, unlike the cited gating-based GNNs that ignore B in their gating units.Source: B ANALYSIS ON B IN EQUATION 4 · pp. 16–17

C POLYNOMIAL EXPRESSIVITY OF PRIOR GRAPH MODELS

• Prior GTs and high-order GNNs capture only subsets of possible monomials, while tGNN cannot represent monomials with a variable raised to a power of at least 2.The paper concludes that these prior models need nonlinear activations for reasonable accuracy, whereas Polynormer achieves higher accuracy without them.Source: C POLYNOMIAL EXPRESSIVITY OF PRIOR… · p. 17
• Gating-based GNNs primarily model local structures and cannot learn high-order monomials formed from distant-node features.Source: C POLYNOMIAL EXPRESSIVITY OF PRIOR… · p. 17

D.1 HYPERPARAMETER TUNING

• Kernel-based linear GTs require tuning critical hyperparameters, whereas Polynormer’s linear global attention requires none for model tuning.Source: §D.1 · p. 18

D.2 TRAINING STABILITY

• Although cosFormer uses ReLU and handles text sequences up to 16K tokens, the authors observe instability on graphs with millions of nodes.They identify the kernel function as the key distinction between cosFormer and their linear global attention.Source: §D.2 · p. 18
• On ogbn-products and pokec, substituting ReLU into Equation 6 produces a NaN training loss.ReLU zeroes negative key values but preserves positive ones, whose sum across millions of nodes can exceed 32-bit floating-point capacity.Source: §D.2 · p. 18
• Sigmoid maps key values to (0, 1), preventing excessively large sums and the reported NaN loss.The authors use Sigmoid rather than ReLU in their approach.Source: §D.2 · p. 18

E DATASET DETAILS

• Table 4 presents statistics for all 13 experimental datasets, with homophily scores where higher values indicate greater homophily.The homophily score follows the metric proposed by Lim et al. (2021).Source: E DATASET DETAILS · p. 18, Table 4 · p. 18

F HARDWARE INFORMATION

• Experiments ran on a Linux machine with an Intel Xeon Gold 5218 CPU and four RTX A6000 GPUs, while Polynormer training used one GPU.The other GPUs ran baseline experiments in parallel.Source: F HARDWARE INFORMATION · p. 19

G A VARIANT OF POLYNORMER

• The variant updates node features using local and global attention layers in parallel, but the ablation reports worse performance than Polynormer’s local-to-global attention.Its Q, K, V, and H matrices come from linear projections of the previous layer’s node features.Source: G A VARIANT OF POLYNORMER · p. 19

H.1 BASELINE MODELS

• Baseline comparisons draw on reported results for homophilic, heterophilic, and large-scale datasets, with hyperparameter tuning for models lacking public results.The appendix lists tuning configurations for GCNII, GGCN, OrderedGNN, tGCN, and G2-GNN.Source: §H.1 · p. 19

H.2 POLYNORMER

• Polynormer uses a local-module warm-up, eight attention heads, and mini-batch training for ogbn-products and pokec, while other datasets use full batches.The local attention module is replaced by GCN on ogbn-arxiv and pokec, where the authors report better performance and lower memory usage.Source: Table 5 · p. 20, §H.2 · p. 21
• The implementation applies LayerNorm to H ⊙ AV and scales it by 1 − σ(1βT) to improve training stability and typically improve accuracy.The local module is given explicitly, while the global module follows a similar approach.Source: §H.2 · p. 21

I MODEL IMPLEMENTATION

• The implementation pseudocode applies local attention before global attention, with each module multiplying its convolution output by a projected feature term plus a trainable sigmoid-weighted parameter.The global attention pseudocode maps queries and keys through Sigmoid, computes normalized attention using numerator and denominator terms, and applies LayerNorm.Source: I MODEL IMPLEMENTATION · pp. 21–22

J.1 PROFILING RESULTS ON SYNTHETIC GRAPHS

• Memory grows linearly, GPU training time remains nearly constant, and CPU time grows linearly as synthetic graph size increases.The synthetic Erdos-Renyi graphs ranged from 1,000 to 200,000 nodes, with average degree around 5 and node feature dimension 100; the GPU-time pattern is attributed to parallel computation on an RTX A6000.Source: Figure 5 · p. 22, §J.1 · pp. 22–23

J.2 PROFILING RESULTS ON LARGE REALISTIC GRAPHS

• On large realistic graphs, Polynormer ranks among the three fastest models and has relatively low memory usage.The comparison reports training time per epoch and memory usage; the authors attribute efficiency partly to common, optimized graph-framework APIs.Source: §J.2 · p. 23, Table 6 · p. 23

K WL EXPRESSIVITY OF POLYNORMER

• With B = 1β^T and identical node features, Equation 18 reduces to 1-WL message passing when W is designed appropriately.The passage gives the adjacency matrix with self-loops as an example for W.Source: K WL EXPRESSIVITY OF POLYNORMER · p. 23
• Encoding the first non-trivial Laplacian eigenvector v2 in polynomial coefficients lets Polynormer-v2 distinguish some non-isomorphic graphs that 1-WL cannot.Figure 6 illustrates two such graph pairs.Source: K WL EXPRESSIVITY OF POLYNORMER · p. 24, Figure 6 · p. 24
• On realistic node-classification datasets, Polynormer-v2 does not clearly outperform Polynormer-v1, so the authors use v1 in practice.They suggest that unique node features may reduce the value of additional positional information; using v1 also avoids computing a Laplacian eigenvector.Source: K WL EXPRESSIVITY OF POLYNORMER · p. 24

L CASE STUDY: AI MODEL RUNTIME PREDICTION ON TPU

• TpuGraphs evaluates runtime prediction on tensor-computation graphs; its Layout collection contains 31 million graph-configuration pairs averaging over 7,700 nodes per graph.The dataset includes graphs from varied ML programs and compiler configurations.Source: L CASE STUDY: AI MODEL RUNTIME… · p. 25

L.1 RESULTS ON TPUGRAPHS-LAYOUT COLLECTIONS.

• On XLA-Random, Polynormer improves accuracy by 10.3% over GraphSAGE and 6.3% over Polynormer-local.XLA-Random is described as the most challenging collection because it combines diverse graph structures with varied compiler configurations.Source: §L.1 · p. 25

L.2 RESULTS ON TPUGRAPHS (LAYOUT + TILE).

• On TpuGraphs Layout plus Tile, Polynormer improves accuracy over the baseline by 31.8%, compared with 19.6% for its local module alone.The table reports averaged runtime-prediction accuracy; Polynormer-Local denotes the local attention module.Source: §L.2 · pp. 25–26, Table 9 · p. 26

M DISCUSSION ON THE DEFINITION OF POLYNOMIAL EXPRESSIVITY

• The authors motivate higher polynomial expressivity by noting that polynomials can approximate any smooth function under the Weierstrass theorem.They therefore relate higher polynomial expressivity to greater capacity for learning complex functions.Source: M DISCUSSION ON THE DEFINITION OF… · p. 26
• Graph topology affects which monomial terms appear, while treating structural information as polynomial coefficients simplifies analysis and enables decoupling it from node features.The authors describe this simplification as supporting development of a scalable model with high polynomial expressivity.Source: M DISCUSSION ON THE DEFINITION OF… · p. 26