ChebyGNN: Linear-Time Spectral 2-WL Expressivity via Relational Chebyshev Fingerprints

Isotropic message-passing Graph Neural Networks (MPNNs) are fundamentally bounded by the 1-Weisfeiler-Leman (1-WL) graph isomorphism test, rendering them blind to spatial symmetries and co-spectral regular topologies. While higher-order (k-WL) and equivariant subgraph architectures break this barrier, they inherit prohibitive polynomial O(N^(k+1)) time or combinatorial memory overheads, severely restricting their scalability to large-scale relational structures. In this work, we introduce ChebyGNN, a scalable and provably expressive framework driven by Relational Chebyshev Spectral Fingerprints (χ-SF). By extending spectral approximation theory from node-level local loop-counting to joint pairwise relational tracking, we extract multi-scale spectral diffusion traces without executing explicit matrix diagonalizations or dense tensor expansions. We theoretically prove that by restricting polynomial matrix evaluations strictly to adjacent vertex pairs, χ-SF captures macro-topological cycle configurations and achieves an expressivity equivalent to the 2-WL test, while preserving a strict linear-time complexity O(|E| * K) and a sparse memory footprint. Furthermore, we bridge this algebraic formulation with natural intelligence, mapping our three-term recurrence directly onto biological cortical loop dynamics with delayed feedback inhibition. Empirically, ChebyGNN achieves a complete separation score of 100% (212/212 distinguished graph pairs) on the BREC expressivity benchmark, bypassing the Out-of-Memory (OOM) crashes typical of higher-order baselines. Furthermore, experiments on molecular (ZINC-12k Test MAE 0.1057 ± 0.0029 with 182k parameters) and web-scale graphs (ogbn-arxiv Test Accuracy 71.80% ± 0.14% at 1.8 GB VRAM) confirm that ChebyGNN establishes a new Pareto-efficiency frontier, combining higher-order 2-WL expressivity with web-scale computational efficiency.