Breaking the 1-WL Barrier: Turbo Fiedler Deck as a Spectral Positional Encoding for Industrial-Scale GNNs

Abstract The 1-Weisfeiler-Lehman (1-WL) test has stood as the theoretical ceiling of Graph Neural Networks (GNNs) for too long, blinding state-of-the-art models to struc- tural symmetries critical in drug discovery and materials science. We shatter this barrier not with heavier compute, but with sharper geometry. We introduce the Turbo Fiedler Deck, a spectral-topological engine that unifies combinatorial vertex criticality with Fiedler eigenvalue perturbation. Unlike O(n!) exact algorithms that collapse under symmetry, our method computes a permutation-invariant signature in polynomial time (O(n 3 )). The distinction is absolute: on the SRG(96) bench- mark—a notorious ”graveyard” where standard VF2 times out and 1-WL fails com- pletely—our method stands alone, achieving 100% discrimination in ∼320ms. While others guess or wait, the Fiedler Deck solves. Scaled to 31,364 USPTO molecules, it delivers 99.979% accuracy at 228 structures/second. This is the new deterministic standard for expressivity-unbounded GNNs. The method also successfully discriminates Cai-F¨urer-Immerman (CFI) graphs—the canonical proof construction for 1-WL limitations—with 100