{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T18:25:12Z","timestamp":1765045512075,"version":"3.44.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","award":["467516565"],"award-info":[{"award-number":["467516565"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>\n            A graph parameter is a function f on graphs with the property that, for any pair of isomorphic graphs G\n            <jats:sub>1<\/jats:sub>\n            and G\n            <jats:sub>2<\/jats:sub>\n            , f(G\n            <jats:sub>1<\/jats:sub>\n            )=f(G\n            <jats:sub>2<\/jats:sub>\n            ). The Weisfeiler--Leman (WL) dimension of f is the minimum k such that, if G\n            <jats:sub>1<\/jats:sub>\n            and G\n            <jats:sub>2<\/jats:sub>\n            are indistinguishable by the k-dimensional WL-algorithm then f(G\n            <jats:sub>1<\/jats:sub>\n            )=f(G\n            <jats:sub>2<\/jats:sub>\n            ). The WL-dimension of f is \u221e if no such k exists. We study the WL-dimension of graph parameters characterised by the number of answers from a fixed conjunctive query to the graph. Given a conjunctive query \u03c6, we quantify the WL-dimension of the function that maps every graph G to the number of answers of \u03c6 in G.\n          <\/jats:p>\n          <jats:p>The works of Dvorak (J. Graph Theory 2010), Dell, Grohe, and Rattan (ICALP 2018), and Neuen (ArXiv 2023) have answered this question for full conjunctive queries, which are conjunctive queries without existentially quantified variables. For such queries \u03c6, the WL-dimension is equal to the treewidth of the Gaifman graph of \u03c6.<\/jats:p>\n          <jats:p>In this work, we give a characterisation that applies to all conjunctive queries. Given any conjunctive query \u03c6, we prove that its WL-dimension is equal to the semantic extension width sew(\u03c6), a novel width measure that can be thought of as a combination of the treewidth of \u03c6 and its quantified star size, an invariant introduced by Durand and Mengel (ICDT 2013) describing how the existentially quantified variables of \u03c6 are connected with the free variables. Using the recently established equivalence between the WL-algorithm and higher-order Graph Neural Networks (GNNs) due to Morris et al. (AAAI 2019), we obtain as a consequence that the function counting answers to a conjunctive query \u03c6 cannot be computed by GNNs of order smaller than sew(\u03c6).<\/jats:p>\n          <jats:p>The majority of the paper is concerned with establishing a lower bound of the WL-dimension of a query. Given any conjunctive query \u03c6 with semantic extension width k, we consider a graph F of treewidth k obtained from the Gaifman graph of \u03c6 by repeatedly cloning the vertices corresponding to existentially quantified variables. Using a modification due to Furer (ICALP 2001) of the Cai-F\u00fcrer-Immerman construction (Combinatorica 1992), we then obtain a pair of graphs \u03c7(F) and ^\u03c7(F) that are indistinguishable by the (k-1)-dimensional WL-algorithm since F has treewidth k. Finally, in the technical heart of the paper, we show that \u03c6 has a different number of answers in \u03c7(F) and ^\u03c7(F). Thus, \u03c6 can distinguish two graphs that cannot be distinguished by the (k-1)-dimensional WL-algorithm, so the WL-dimension of \u03c6 is at least k.<\/jats:p>","DOI":"10.1145\/3651587","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-17","source":"Crossref","is-referenced-by-count":1,"title":["The Weisfeiler-Leman Dimension of Conjunctive Queries"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5180-7205","authenticated-orcid":false,"given":"Andreas","family":"G\u00f6bel","sequence":"first","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Potsdam, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1879-6089","authenticated-orcid":false,"given":"Leslie A.","family":"Goldberg","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3159-9418","authenticated-orcid":false,"given":"Marc","family":"Roth","sequence":"additional","affiliation":[{"name":"School of Electronic Engineering and Computer Science, Queen Mary University of London, London, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Biomolecular network motif counting and discovery by color coding. Bioinformatics 24, 13 (07","author":"Alon Noga","year":"2008","unstructured":"Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and S. Cenk Sahinalp. 2008. Biomolecular network motif counting and discovery by color coding. Bioinformatics 24, 13 (07 2008), i241--i249."},{"key":"e_1_2_1_2_1","volume-title":"The Weisfeiler-Lehman Procedure. Bull. EATCS 120","author":"Arvind Vikraman","year":"2016","unstructured":"Vikraman Arvind. 2016. The Weisfeiler-Lehman Procedure. Bull. EATCS 120 (2016). http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/442"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2021.104803"},{"key":"e_1_2_1_4_1","volume-title":"Graph Neural Networks with Local Graph Parameters. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021","author":"Barcel\u00f3 Pablo","year":"2021","unstructured":"Pablo Barcel\u00f3, Floris Geerts, Juan L. Reutter, and Maksimilian Ryschkov. 2021. Graph Neural Networks with Local Graph Parameters. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6--14, 2021, virtual, Marc'Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (Eds.). 25280--25293."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1027320705349"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-030--30786--8_26"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2022.3154319"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2021.27"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2015.110"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902279"},{"key":"e_1_2_1_12_1","volume-title":"Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Chen Zhengdao","year":"2020","unstructured":"Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. 2020. Can Graph Neural Networks Count Substructures?. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6--12, 2020, virtual, Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/75877cb75154206c4e65e76b88a12712-Abstract.html"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055502"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470609"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.40"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.113"},{"key":"e_1_2_1_17_1","volume-title":"Counting Answers to Existential Questions. CoRR abs\/1902.04960","author":"Dell Holger","year":"2019","unstructured":"Holger Dell, Marc Roth, and Philip Wellnitz. 2019. Counting Answers to Existential Questions. CoRR abs\/1902.04960 (2019). arXiv:1902.04960 http:\/\/arxiv.org\/abs\/1902.04960"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20461"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/3--540--29953-X"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470677"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/10548.003.0023"},{"key":"e_1_2_1_22_1","volume-title":"Leslie Ann Goldberg, and Marc Roth","author":"G\u00f6bel Andreas","year":"2023","unstructured":"Andreas G\u00f6bel, Leslie Ann Goldberg, and Marc Roth. 2023. The Weisfeiler-Leman Dimension of Conjunctive Queries. arXiv:2310.19006 [cs.DM]"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--1--4612--4478--3_5"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan","author":"Jin Jiashun","year":"2018","unstructured":"Jiashun Jin, Zheng Tracy Ke, and Shengming Luo. 2018. Network Global Testing by Counting Graphlets. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan, Stockholm, Sweden, July 10--15, 2018 (Proceedings of Machine Learning Research, Vol. 80), Jennifer G. Dy and Andreas Krause (Eds.). PMLR, 2338--2346. http:\/\/proceedings.mlr.press\/v80\/jin18b.html"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2309.17053"},{"key":"e_1_2_1_26_1","volume-title":"Colloquium Publications","volume":"60","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"2012","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz. 2012. Large Networks and Graph Limits. Colloquium Publications, Vol. 60. American Mathematical Society."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00067"},{"key":"e_1_2_1_28_1","volume-title":"Network Motifs: Simple Building Blocks of Complex Networks. Science 298, 5594","author":"Milo R.","year":"2002","unstructured":"R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. 2002. Network Motifs: Simple Building Blocks of Complex Networks. Science 298, 5594 (2002), 824--827."},{"key":"e_1_2_1_29_1","volume-title":"Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Morris Christopher","year":"2020","unstructured":"Christopher Morris, Gaurav Rattan, and Petra Mutzel. 2020. Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6--12, 2020, virtual, Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33014602"},{"key":"e_1_2_1_31_1","volume-title":"Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width. arXiv preprint arXiv:2304.07011","author":"Neuen Daniel","year":"2023","unstructured":"Daniel Neuen. 2023. Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width. arXiv preprint arXiv:2304.07011 (2023)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.012"},{"key":"e_1_2_1_33_1","volume-title":"Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree. arXiv preprint arXiv:2206.10321","author":"Roberson David E","year":"2022","unstructured":"David E Roberson. 2022. Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree. arXiv preprint arXiv:2206.10321 (2022)."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2023.79"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2023.82"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02240204"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166--218X(91)90049--3"},{"key":"e_1_2_1_38_1","first-page":"12","article-title":"The reduction of a graph to canonical form and the algebra which appears therein. NTI","volume":"2","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, 9 (1968), 12--16. English translation by G. Ryabov available at https:\/\/www.iti.zcu.cz\/wl2018\/pdf\/wl_paper_translation.pdf.","journal-title":"Series"},{"key":"e_1_2_1_39_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":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651587","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651587","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:39:42Z","timestamp":1755898782000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651587"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651587"],"URL":"https:\/\/doi.org\/10.1145\/3651587","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}