{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T04:15:20Z","timestamp":1768709720036,"version":"3.49.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T00:00:00Z","timestamp":1737676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","award":["101054974"],"award-info":[{"award-number":["101054974"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","award":["820148"],"award-info":[{"award-number":["820148"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2025,1,31]]},"abstract":"\n We prove new upper and lower bounds on the number of iterations the\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -dimensional Weisfeiler-Leman algorithm (\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -WL) requires until stabilization. For\n \n \\(k\\geq 3\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , we show that\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -WL stabilizes after at most\n \n \\(O(kn^{k-1}\\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n iterations (where\n \n \\(n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n denotes the number of vertices of the input structures), obtaining the first improvement over the trivial upper bound of\n \n \\(n^{k}-1\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and extending a previous upper bound of\n \n \\(O(n\\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for\n \n \\(k=2\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>\n \n We complement our upper bounds by constructing\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -ary relational structures on which\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -WL requires at least\n \n \\(n^{\\Omega(k)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n iterations to stabilize. This improves over a previous lower bound of\n \n \\(n^{\\Omega(k\/\\log k)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>\n \n We also investigate tradeoffs between the dimension and the iteration number of WL, and show that\n \n \\(d\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -WL, where\n \n \\(d=\\lceil\\frac{3(k + 1)}{2}\\rceil\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , can simulate the\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -WL algorithm using only\n \n \\(O(k^{2}\\cdot n^{\\lfloor k\/2\\rfloor+1}\\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n many iterations, but still requires at least\n \n \\(n^{\\Omega(k)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n iterations for any\n \n \\(d\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n (that is sufficiently smaller than\n \n \\(n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ).\n <\/jats:p>\n \n The number of iterations required by\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -WL to distinguish two structures corresponds to the quantifier rank of a sentence distinguishing them in the\n \n \\((k + 1)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -variable fragment\n \n \\(\\mathsf{C}_{k + 1}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of first-order logic with counting quantifiers. Hence, our results also imply new upper and lower bounds on the quantifier rank required in the logic\n \n \\(\\mathsf{C}_{k + 1}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , as well as tradeoffs between variable number and quantifier rank.\n <\/jats:p>","DOI":"10.1145\/3708891","type":"journal-article","created":{"date-parts":[[2024,12,20]],"date-time":"2024-12-20T12:14:22Z","timestamp":1734696862000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["The Iteration Number of the Weisfeiler-Leman Algorithm"],"prefix":"10.1145","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0292-9142","authenticated-orcid":false,"given":"Martin","family":"Grohe","sequence":"first","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5437-8074","authenticated-orcid":false,"given":"Moritz","family":"Lichter","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4940-0318","authenticated-orcid":false,"given":"Daniel","family":"Neuen","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"}]}],"member":"320","published-online":{"date-parts":[[2025,1,24]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897542"},{"key":"e_1_3_1_3_2","volume-title":"Linear Algebra Methods in Combinatorics","author":"Babai L\u00e1szl\u00f3","year":"2020","unstructured":"L\u00e1szl\u00f3 Babai and P\u00e9ter Frankl. 2020. Linear Algebra Methods in Combinatorics. University of Chicago."},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3195257"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48224-5_27"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2008.11"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781139028868"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470677"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.134"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00052"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_2"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4478-3_5"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.73"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/20m1314987"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.23638\/LMCS-15(2:19)2019"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2019.8785694"},{"issue":"333","key":"e_1_3_1_18_2","first-page":"1","article-title":"Weisfeiler and Leman go machine learning: The story so far","volume":"24","author":"Morris Christopher","year":"2023","unstructured":"Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. 2023. Weisfeiler and Leman go machine learning: The story so far. J. Mach. Learn. Res. 24, 333 (2023), 1\u201359. Retrieved from http:\/\/jmlr.org\/papers\/v24\/22-0240.html","journal-title":"J. Mach. Learn. Res"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33014602"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1017\/cbo9780511814075"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3651986"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/22m1514076"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781316716878"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2078187"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746617"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS56636.2023.10175818"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70918-3_58"},{"key":"e_1_3_1_29_2","unstructured":"Boris Weisfeiler and Andrei Leman. 1968. The reduction of a graph to canonical form and the algebra which appears therein. NTI. [English translation by Grigory Ryabov] Retrieved from https:\/\/www.iti.zcu.cz\/wl2018\/pdf\/wl_paper_translation.pdf"},{"key":"e_1_3_1_30_2","volume-title":"7th International Conference on Learning Representations (ICLR \u201919)","author":"Xu Keyulu","year":"2019","unstructured":"Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How powerful are graph neural networks?. In 7th International Conference on Learning Representations (ICLR \u201919). OpenReview.net. Retrieved from https:\/\/openreview.net\/forum?id=ryGs6iA5Km"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07968-4"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708891","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3708891","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:54Z","timestamp":1750295874000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708891"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,24]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1,31]]}},"alternative-id":["10.1145\/3708891"],"URL":"https:\/\/doi.org\/10.1145\/3708891","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,24]]},"assertion":[{"value":"2023-08-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-25","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}