{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:32:29Z","timestamp":1753885949481,"version":"3.41.2"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"abstract":"<jats:p>\n            The\n            <jats:italic>k<\/jats:italic>\n            -dimensional Weisfeiler-Leman (\n            <jats:italic>k<\/jats:italic>\n            -WL) algorithm is a simple combinatorial algorithm that was originally designed as a graph isomorphism heuristic. It naturally finds applications in Babai\u2019s quasipolynomial-time isomorphism algorithm, practical isomorphism solvers, and algebraic graph theory. However, it also has surprising connections to other areas such as logic, proof complexity, combinatorial optimization, and machine learning.\n          <\/jats:p>\n          <jats:p>\n            The algorithm iteratively computes a coloring of the\n            <jats:italic>k<\/jats:italic>\n            -tuples of vertices of a graph. Since F\u00fcrer\u2019s linear lower bound [ICALP 2001], it has been an open question whether there is a super-linear lower bound for the iteration number for\n            <jats:italic>k<\/jats:italic>\n            -WL on graphs. We answer this question affirmatively, establishing an\n            <jats:italic>\u03a9<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n              \/2\n            <\/jats:sup>\n            )-lower bound for all\n            <jats:italic>k<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3727978","type":"journal-article","created":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T10:53:36Z","timestamp":1743850416000},"update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements"],"prefix":"10.1145","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"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-3585-8213","authenticated-orcid":false,"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[{"name":"Mathematics, TU Darmstadt, Darmstadt, Germany"}]}],"member":"320","published-online":{"date-parts":[[2025,4,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1338435"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/120867834"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897542"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_13"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","unstructured":"Christoph Berkholz Moritz Lichter and Harry Vinall-Smeeth. 2024. Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism. CoRR abs\/2407.17947(2024). doi: 10.48550\/arXiv.2407.17947 arXiv:2407.17947","DOI":"10.48550\/arXiv.2407.17947"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3195257"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_10"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","unstructured":"Susanna\u00a0F. de Rezende Noah Fleming Duri\u00a0Andrea Janett Jakob Nordstr\u00f6m and Shuo Pang. 2024. Truly Supercritical Trade-offs for Resolution Cutting Planes Monotone Circuits and Weisfeiler-Leman. CoRR abs\/2411.14267(2024). doi: 10.48550\/arXiv.2411.14267 arXiv:2411.14267","DOI":"10.48550\/arXiv.2411.14267"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20461"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48224-5_27"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2018.33"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_42"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3708891"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2015.28"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0070"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4478-3_5"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3436980.3436982"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.73"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.23638\/LMCS-15(2:19)2019"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3572918"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2019.8785694"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2014.01.004"},{"key":"e_1_2_1_24_1","unstructured":"Christopher Morris Yaron Lipman Haggai Maron Bastian Rieck Nils\u00a0M. Kriege Martin Grohe Matthias Fey and Karsten\u00a0M. Borgwardt. 2021. Weisfeiler and Leman go Machine Learning: The Story so far. CoRR abs\/2112.09992(2021). arXiv:2112.09992 https:\/\/arxiv.org\/abs\/2112.09992"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33014602"},{"issue":"1919","key":"e_1_2_1_26_1","first-page":"181","article-title":"A proof of Bertrand\u2019s postulate [J","volume":"11","author":"Ramanujan Srinivasa","year":"2000","unstructured":"Srinivasa Ramanujan. 2000. A proof of Bertrand\u2019s postulate [J. Indian Math. Soc. 11 (1919), 181\u2013182]. In Collected papers of Srinivasa Ramanujan. AMS Chelsea Publ., Providence, RI, 208\u2013209.","journal-title":"Indian Math. Soc."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858790"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","unstructured":"David\u00a0E. Roberson. 2022. Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree. CoRR abs\/2206.10321(2022). doi: 10.48550\/arXiv.2206.10321 arXiv:2206.10321","DOI":"10.48550\/arXiv.2206.10321"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.12.023"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1027"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2078187"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.2009.11920980"},{"key":"e_1_2_1_33_1","series-title":"Series 2","volume-title":"The reduction of a graph to canonical form and the algebra which appears therein. NTI","author":"Weisfeiler Boris","year":"1968","unstructured":"Boris Weisfeiler and Andrei Leman. 1968. The reduction of a graph to canonical form and the algebra which appears therein. NTI, Series 2 (1968). English translation by Grigory Ryabov available at https:\/\/www.iti.zcu.cz\/wl2018\/pdf\/wl_paper_translation.pdf."},{"key":"e_1_2_1_34_1","volume-title":"7th International Conference on Learning Representations, ICLR 2019","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 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net. https:\/\/openreview.net\/forum?id=ryGs6iA5Km"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3727978","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T10:54:23Z","timestamp":1743850463000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3727978"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,5]]},"references-count":34,"alternative-id":["10.1145\/3727978"],"URL":"https:\/\/doi.org\/10.1145\/3727978","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2025,4,5]]},"assertion":[{"value":"2024-01-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-23","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"3727978"}}