Spectral Moment Invariants and the Weisfeiler–Leman Hierarchy:

Separating Power, a Fundamental Limitation, and Three Open

Problems

Murat Ozcek1,*

1 Department of Mathematics, Gaziantep University, Gaziantep, Turkey

Received: July 06, 2025 Revised: October 09, 2025 Accepted: December 08, 2025 ⋆ Corresponding author

ABSTRACT

We study spectral moment invariants Σp(G) = (trAG, . . . , trApG

), built from the adjacency spectrum of a graph G,

as graph isomorphism invariants positioned relative to the Weisfeiler–Leman (WL) hierarchy used to characterize

graph neural network (GNN) expressivity. We give three fully verified case studies. First, C6 vs. 2K3: a 1-

WL-indistinguishable pair separated by Σ3 but not Σ2 or Σ4. Second, K3,3 vs. the triangular prism: a second

1-WL-indistinguishable, cubic pair, also separated at order 3, but where the fourth moment separates as well,

showing separating power is graph-family dependent even at fixed order. Both examples are grounded in a general

fourth-moment identity (Proposition 2.8) and a homomorphism-counting identity (Proposition 2.5) that we prove

from first principles. Third, and in the opposite direction, we prove that spectral moment invariants of every

finite order fail on the classical cospectral, non-isomorphic strongly regular pair srg(16,6,2,2) (the Shrikhande

graph and the 4×4 rook’s graph), verified numerically to fourth order by two independent methods. We situate

both directions within published enumeration data and the Godsil–McKay switching construction, compare the

computational complexity of spectral-moment, WL, and general isomorphism testing, connect the limitation to

Laplacian eigenvector positional encodings in Graph Transformers, and pose three precise open problems.

Keywords: Spectral graph theory Weisfeiler–Leman algorithm Strongly regular graphs Graph neural networks

Graph isomorphism Cospectral graphs

1. INTRODUCTION

The Weisfeiler–Leman (WL) color-refinement procedure [1]

is now the standard yardstick for graph neural network (GNN)

expressivity: message-passing GNNs are no more powerful

than 1-WL [2], and k-WL-equivalent architectures have been

proposed to climb the hierarchy [3, 4]. Graph Transformers

address a related blind spot by injecting Laplacian eigenvectors

as positional encodings [5], implicitly treating the graph

spectrum as a complementary source of structural information.

This raises a natural formal question that, to our knowledge,

has not been posed precisely: how does the family of spectral

moment invariants—scalar isomorphism invariants built

purely from the adjacency eigenvalue multiset — compare

to the WL hierarchy as a separating tool? We answer this

with two fully verified case studies rather than asymptotic

claims, and we show the comparison is genuinely two-sided:

spectral moments beat 1-WL on one canonical instance, and

fail completely, by a rigorous cospectrality argument, on

another. We further situate this two-sidedness within the

broader, decades-old literature on spectral graph characteriza-