Polynormer is a polynomial-expressive graph transformer with linear complexity, designed to balance expressivity and scalability in graph neural networks (GNNs). Unlike traditional graph transformers (GTs), which often have quadratic complexity, Polynormer achieves linear complexity by learning high-degree polynomials through a novel base model that incorporates graph topology and node features. This model is permutation equivariant, meaning it preserves the structure of node permutations, and uses a local-to-global attention scheme to learn high-degree equivariant polynomials. Polynormer outperforms state-of-the-art GNN and GT baselines on 13 graph datasets, including large graphs with millions of nodes, even without nonlinear activation functions. It achieves significant accuracy improvements, up to 4.06%, on 11 out of 13 datasets. Polynormer's linear complexity allows it to scale to large graphs efficiently, avoiding the quadratic complexity of traditional attention mechanisms. The model's polynomial expressivity is motivated by the Weierstrass theorem, which guarantees that any smooth function can be approximated by a polynomial. Polynormer's architecture combines local and global attention mechanisms to capture both local and global structural information, making it effective for both homophilic and heterophilic graphs. The model's performance is validated through extensive experiments on various graph datasets, demonstrating its effectiveness in capturing critical global structures and improving node classification accuracy.Polynormer is a polynomial-expressive graph transformer with linear complexity, designed to balance expressivity and scalability in graph neural networks (GNNs). Unlike traditional graph transformers (GTs), which often have quadratic complexity, Polynormer achieves linear complexity by learning high-degree polynomials through a novel base model that incorporates graph topology and node features. This model is permutation equivariant, meaning it preserves the structure of node permutations, and uses a local-to-global attention scheme to learn high-degree equivariant polynomials. Polynormer outperforms state-of-the-art GNN and GT baselines on 13 graph datasets, including large graphs with millions of nodes, even without nonlinear activation functions. It achieves significant accuracy improvements, up to 4.06%, on 11 out of 13 datasets. Polynormer's linear complexity allows it to scale to large graphs efficiently, avoiding the quadratic complexity of traditional attention mechanisms. The model's polynomial expressivity is motivated by the Weierstrass theorem, which guarantees that any smooth function can be approximated by a polynomial. Polynormer's architecture combines local and global attention mechanisms to capture both local and global structural information, making it effective for both homophilic and heterophilic graphs. The model's performance is validated through extensive experiments on various graph datasets, demonstrating its effectiveness in capturing critical global structures and improving node classification accuracy.