On a Hierarchy of Spectral Isomorphism Invariants

We consider a hierarchy of graph invariants that naturally extends the spectral invariants defined by F\"urer (Lin. Alg. Appl. 2010) based on angles between the projections of standard basis vectors onto an eigenspace of the adjacency matrix of a graph. We provide a purely combinatorial characterization of this hierarchy in terms of the walk counts. This allows us to give a complete answer to F\"urer's question about the strength of his invariants in distinguishing non-isomorphic graphs in comparison to the 2-dimensional Weisfeiler-Leman algorithm, extending the recent work of Rattan and Seppelt (SODA 2023). As another application of the characterization, we prove that almost all graphs are determined up to isomorphism by their eigenvalues and angles, which is closely related to the long-standing open problem whether almost all graphs are determined by their spectrum. Finally, we describe the exact relationship between the hierarchy and the Weisfeiler-Leman algorithms for small dimensions, as also some other important spectral characteristics of a graph such as the generalized and the main spectra.