{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:05:44Z","timestamp":1764781544312,"version":"3.46.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T00:00:00Z","timestamp":1761696000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T00:00:00Z","timestamp":1761696000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We consider a hierarchy of graph invariants that naturally extends the spectral invariants defined by F\u00fcrer (Lin. Alg. Appl. 2010) based on the angles formed by the set of standard basis vectors and their projections onto eigenspaces of the adjacency matrix. 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\u00fcrer's question about the strength of his invariants in distinguishing non-isomorphic graphs in comparison with 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 in terms of the spectrum and the angles, which is of interest in view of the long-standing open problem whether almost all graphs are determined by their eigenvalues alone. 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.<\/jats:p>","DOI":"10.1007\/s00037-025-00270-x","type":"journal-article","created":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T17:27:18Z","timestamp":1761758838000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On a Hierarchy of Spectral Isomorphism Invariants"],"prefix":"10.1007","volume":"34","author":[{"given":"V.","family":"Arvind","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Fuhlbr\u00fcck","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"K\u00f6bler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oleg","family":"Verbitsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,10,29]]},"reference":[{"key":"270_CR1","unstructured":"V. Arvind, F. Fuhlbr\u00fcck, J. K\u00f6bler, and O. Verbitsky. On\na hierarchy of spectral invariants for graphs. In 41st International\nSymposium on Theoretical Aspects of Computer\nScience, (STACS\u201924), volume 289 of LIPIcs, pages 6:1\u20136:18.\nSchloss Dagstuhl \u2013 Leibniz-Zentrum f\u00a8ur Informatik, 2024.\ndoi:10.4230\/LIPICS.STACS.2024.6."},{"key":"270_CR2","doi-asserted-by":"crossref","unstructured":"L. Babai. Graph isomorphism in quasipolynomial time.\nIn Proceedings of the 48th Annual ACM Symposium on\nTheory of Computing (STOC\u201916), pages 684\u2013697, 2016. doi:10.1145\/2897518.2897542.","DOI":"10.1145\/2897518.2897542"},{"key":"270_CR3","doi-asserted-by":"crossref","unstructured":"L. Babai, P. Erd\u0151s, and S. M. Selkow. Random graph isomorphism.\nSIAM Journal on Computing, 9(3):628\u2013635, 1980.\ndoi:10.1137\/0209047.","DOI":"10.1137\/0209047"},{"key":"270_CR4","doi-asserted-by":"crossref","unstructured":"A. R. Barghi and I. Ponomarenko. Non-isomorphic graphs\nwith cospectral symmetric powers. Electron. J. Comb., 16(1),\n2009. doi:10.37236\/209.","DOI":"10.37236\/209"},{"key":"270_CR5","unstructured":"A. E. Brouwer. Paulus-Rozenfeld graphs. URL: https:\/\/www.win.tue.nl\/~aeb\/drg\/graphs\/Paulus.html."},{"key":"270_CR6","doi-asserted-by":"crossref","unstructured":"J. Cai, M. F\u00fcrer, and N. Immerman. An optimal lower bound\non the number of variables for graph identifications. Combinatorica,\n12(4):389\u2013410, 1992. doi:10.1007\/BF01305232.","DOI":"10.1007\/BF01305232"},{"key":"270_CR7","unstructured":"G. Chen and I. Ponomarenko. Coherent configurations.\nWuhan: Central China Normal University Press, 2019."},{"key":"270_CR8","unstructured":"D. Cvetkovi\u0107. The main part of the spectrum, divisors and\nswitching of graphs. Publ. Inst. Math., Nouv. S\u00e9r., 23:31\u201338,\n1978. URL: http:\/\/elib.mi.sanu.ac.rs\/files\/journals\/publ\/43\/6.pdf."},{"key":"270_CR9","unstructured":"D. Cvetkovi\u0107 and M. Lepovi\u0107. Cospectral graphs with the\nsame angles and with a minimal number of vertices. Publ.\nElektroteh. Fak., Univ. Beogr., Ser. Mat., 8:88\u2013102, 1997.\nURL: http:\/\/www.jstor.org\/stable\/43666387."},{"key":"270_CR10","doi-asserted-by":"crossref","unstructured":"D. Cvetkovi\u0107, P. Rowlinson, and S. Simi\u0107. An introduction\nto the theory of graph spectra, volume 75 of Lond. Math. Soc.\nStud. Texts. Cambridge: Cambridge University Press, 2010.\ndoi:10.1017\/CBO9780511801518.","DOI":"10.1017\/CBO9780511801518"},{"key":"270_CR11","doi-asserted-by":"crossref","unstructured":"D. Cvetkovi\u0107, P. Rowlinson, and S. Simic. Eigenspaces\nof Graphs. Encyclopedia of Mathematics and its\nApplications. Cambridge University Press, 1997.\ndoi:10.1017\/CBO9781139086547.","DOI":"10.1017\/CBO9781139086547"},{"key":"270_CR12","doi-asserted-by":"crossref","unstructured":"D. Cvetkovi\u0107, P. Rowlinson, and S. Simi\u0107. A study of\neigenspaces of graphs. Linear Algebra and its Applications,\n182:45\u201366, 1993. doi:10.1016\/0024-3795(93)90491-6.","DOI":"10.1016\/0024-3795(93)90491-6"},{"key":"270_CR13","doi-asserted-by":"crossref","unstructured":"Z. Dvo\u0159\u00e1k. On recognizing graphs by numbers of homomorphisms.\nJournal of Graph Theory, 64(4):330\u2013342, 2010.\ndoi:10.1002\/jgt.20461.","DOI":"10.1002\/jgt.20461"},{"key":"270_CR14","unstructured":"F. Fuhlbr\u00fcck. TCSLibLua. GitLab repository, 2023.\nURL: https:\/\/gitlab.com\/tcslib\/tcsliblua\/-\/tree\/7e429da7fcf9bf8d93dfc50b54e823a47364cb4b."},{"key":"270_CR15","doi-asserted-by":"crossref","unstructured":"M. F\u00fcrer. On the power of combinatorial and spectral invariants.\nLinear Algebra and its Applications, 432(9):2373\u20132380,\n2010. doi:10.1016\/j.laa.2009.07.019.","DOI":"10.1016\/j.laa.2009.07.019"},{"key":"270_CR16","doi-asserted-by":"crossref","unstructured":"D. Garijo, A. J. Goodall, and J. Nesetril. Distinguishing\ngraphs by their left and right homomorphism\nprofiles. Eur. J. Comb., 32(7):1025\u20131053, 2011.\ndoi:10.1016\/j.ejc.2011.03.012.","DOI":"10.1016\/j.ejc.2011.03.012"},{"key":"270_CR17","doi-asserted-by":"crossref","unstructured":"F. Geerts. On the expressive power of linear algebra\non graphs. Theory Comput. Syst., 65(1):179\u2013239, 2021.\ndoi:10.1007\/S00224-020-09990-9.","DOI":"10.1007\/s00224-020-09990-9"},{"key":"270_CR18","doi-asserted-by":"crossref","unstructured":"W. H. Haemers and E. Spence. Enumeration of cospectral\ngraphs. European Journal of Combinatorics, 25(2):199\u2013211,\n2004. doi:10.1016\/S0195-6698(03)00100-8.","DOI":"10.1016\/S0195-6698(03)00100-8"},{"key":"270_CR19","unstructured":"D. A. Holton and D. Lou. Matching extensions of strongly\nregular graphs. Australas. J. Comb., 6:187\u2013208, 1992."},{"key":"270_CR20","doi-asserted-by":"crossref","unstructured":"S. Hoory, N. Linial, and A. Widgerson. Expander graphs and\ntheir applications. Bull. Am. Math. Soc., New Ser., 43(4):439\u2013\n561, 2006. doi:10.1090\/S0273-0979-06-01126-8.","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"270_CR21","doi-asserted-by":"crossref","unstructured":"C. R. Johnson and M. Newman. A note on cospectral graphs.\nJournal of Combinatorial Theory, Series B, 28(1):96\u2013103,\n1980. doi:10.1016\/0095-8956(80)90058-1.","DOI":"10.1016\/0095-8956(80)90058-1"},{"key":"270_CR22","doi-asserted-by":"crossref","unstructured":"F. Liu and J. Siemons. Unlocking the walk matrix\nof a graph. J. Algebr. Comb., 55(3):663\u2013690, 2022.\ndoi:10.1007\/s10801-021-01065-3.","DOI":"10.1007\/s10801-021-01065-3"},{"key":"270_CR23","unstructured":"B. D. McKay. Graphs. URL: https:\/\/users.cecs.anu.edu.au\/~bdm\/data\/graphs.html."},{"key":"270_CR24","doi-asserted-by":"crossref","unstructured":"B. Mohar and S. Poljak. Eigenvalues in combinatorial optimization.\nIn Combinatorial and graph-theoretical problems\nin linear algebra, pages 107\u2013151. New York: Springer-Verlag,\n1993. doi:10.1007\/978-1-4613-8354-3.","DOI":"10.1007\/978-1-4613-8354-3_5"},{"key":"270_CR25","doi-asserted-by":"crossref","unstructured":"S. O\u2019Rourke and B. Touri. On a conjecture of Godsil concerning\ncontrollable random graphs. SIAM J. Control. Optim.,\n54(6):3347\u20133378, 2016. doi:10.1137\/15M1049622.","DOI":"10.1137\/15M1049622"},{"key":"270_CR26","unstructured":"A. J. L. Paulus. Conference matrices and graphs of order\n26. Technical report, Eindhoven University of Technology,\n1973. URL: https:\/\/research.tue.nl\/files\/4424819\/252855.pdf."},{"key":"270_CR27","doi-asserted-by":"crossref","unstructured":"D. L. Powers and M. M. Sulaiman. The walk partition and\ncolorations of a graph. Linear Algebra Appl., 48:145\u2013159, 1982.\ndoi:10.1016\/0024-3795(82)90104-5.","DOI":"10.1016\/0024-3795(82)90104-5"},{"key":"270_CR28","doi-asserted-by":"crossref","unstructured":"G. Rattan and T. Seppelt. Weisfeiler-Leman and graph\nspectra. In Proceedings of the 2023 ACM-SIAM Symposium\non Discrete Algorithms (SODA\u201923), pages 2268\u20132285. SIAM,\n2023. doi:10.1137\/1.9781611977554.ch87.","DOI":"10.1137\/1.9781611977554.ch87"},{"key":"270_CR29","unstructured":"M. Z. Rozenfeld. The construction and properties of certain\nclasses of strongly regular graphs. Uspehi Mat. Nauk, 28:197\u2013\n198, 1973."},{"key":"270_CR30","unstructured":"Sirolf. Characterization of k-walk-equivalent graphs, 2018.\nURL: https:\/\/mathoverflow.net\/questions\/304106\/characterization-of-k-walk-equivalent-graphs."},{"key":"270_CR31","unstructured":"E. Spence. Strongly regular graphs on at most 64 vertices.\nURL: http:\/\/www.maths.gla.ac.uk\/~es\/srgraphs.html."},{"key":"270_CR32","doi-asserted-by":"crossref","unstructured":"E. van Dam, W. Haemers, and J. Koolen. Cospectral\ngraphs and the generalized adjacency matrix. Linear\nAlgebra and its Applications, 423(1):33\u201341, 2007.\ndoi:10.1016\/j.laa.2006.07.017.","DOI":"10.1016\/j.laa.2006.07.017"},{"key":"270_CR33","doi-asserted-by":"crossref","unstructured":"E. R. van Dam and W. H. Haemers. Which graphs are determined\nby their spectrum? Linear Algebra and its Applications,\n373:241\u2013272, 2003. doi:10.1016\/S0024-3795(03)00483-X.","DOI":"10.1016\/S0024-3795(03)00483-X"},{"key":"270_CR34","unstructured":"O. Verbitsky and M. Zhukovskii. Canonization of a random\ngraph by two matrix-vector multiplications. In 31st Annual European Symposium on Algorithms (ESA 2023),\nvolume 274 of Leibniz International Proceedings in Informatics\n(LIPIcs), pages 100:1\u2013100:13, Dagstuhl, Germany,\n2023. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00a8ur Informatik.\ndoi:10.4230\/LIPIcs.ESA.2023.100."},{"key":"270_CR35","unstructured":"B. Weisfeiler and A. Leman. The reduction of a graph\nto canonical form and the algebra which appears therein.\nNTI, Ser. 2, 9:12\u201316, 1968. English translation is available\nat https:\/\/www.iti.zcu.cz\/wl2018\/pdf\/wl_paper_translation.pdf."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00270-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-025-00270-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00270-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:00:21Z","timestamp":1764781221000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-025-00270-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,29]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["270"],"URL":"https:\/\/doi.org\/10.1007\/s00037-025-00270-x","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2025,10,29]]},"assertion":[{"value":"9 August 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"19"}}