Moore–Penrose Laplacian Spectral Invariants and Expressivity in Graph Neural Networks

While augmenting vertex-deleted Kelly–Ulam decks with exact integer characteristic polynomials achieves strong structural discrimination across strongly regular and cubic graph censuses, evaluating Faddeev–LeVerrier recurrences over all vertex-deleted components incurs fifth-order polynomial arithmetic complexity in the worst case. Conversely, truncating closed-walk diagonals at fifth order leaves the resulting invariant unable to detect chordless cycles of length six or greater, limiting its discriminative power on long-range skip-link and high-girth regular topologies. Here, we introduce the Moore–Penrose Laplacian Spectral Invariant (Φ⁺ₘₚ), a multi-scale graph invariant with fourth-order polynomial-time complexity. It combines 1-hop fracture shells and canonical 1-WL color refinement with the Moore–Penrose pseudoinverse of the combinatorial Laplacian, evaluated independently across each connected component of the vertex-deleted deck. By incorporating reciprocal algebraic-connectivity information, the diagonal of the Laplacian pseudoinverse, and the Kirchhoff index, the formulation captures connectivity information spanning all path lengths while requiring cubic-time computation per component. Using the All-Minors Matrix-Tree Theorem, we establish that the scaled pseudoinverse entries and pairwise effective resistances admit exact integer representations associated with spanning 2-forests for every connected component. In computational experiments, Φ⁺ₘₚ distinguishes 387 of 390 hard adversarial pairs (99.23%). It achieves 10/10 (100%) on Circular Skip Links CSL(41, r), compared with 1/10 for 1-WL and 5/10 for fifth-order walk diagonals. It also resolves 17/17 (100%) Generalized Petersen graphs up to order 30, separates 500/500 (100%) instances on SRG(35, 18, 9, 9), 492/500 (98.4%) on SRG(36, 15, 6, 6), and 177/180 (98.3%) on SRG(36, 14, 4, 6). Across the reported benchmarks, the method delivers a computational speedup ranging from 129× to 157× over exact Faddeev–LeVerrier evaluation.