The Weisfeiler-Leman dimension of conjunctive queries
A graph parameter is a function 𝑓 on graphs with the property that, for any pair of isomorphic graphs 𝐺1 and 𝐺2, 𝑓 (𝐺1) = 𝑓 (𝐺2). The Weisfeiler–Leman (WL) dimension of 𝑓 is the minimum 𝑘 such that, if 𝐺1 and 𝐺2 are indistinguishable by the 𝑘-dimensional WL-algorithm then 𝑓 (𝐺1) = 𝑓 (𝐺2). The WL-dim...
| Main Authors: | , , |
|---|---|
| Formato: | Conference item |
| Idioma: | English |
| Publicado em: |
Association for Computing Machinery
2024
|
| _version_ | 1826313598437163008 |
|---|---|
| author | Göbel, A Goldberg, LA Roth, M |
| author_facet | Göbel, A Goldberg, LA Roth, M |
| author_sort | Göbel, A |
| collection | OXFORD |
| description | A graph parameter is a function 𝑓 on graphs with the property that, for any pair of isomorphic graphs 𝐺1
and 𝐺2, 𝑓 (𝐺1) = 𝑓 (𝐺2). The Weisfeiler–Leman (WL) dimension of 𝑓 is the minimum 𝑘 such that, if 𝐺1 and 𝐺2
are indistinguishable by the 𝑘-dimensional WL-algorithm then 𝑓 (𝐺1) = 𝑓 (𝐺2). The WL-dimension of 𝑓 is ∞
if no such 𝑘 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 𝜑, we quantify the WL-dimension of
the function that maps every graph 𝐺 to the number of answers of 𝜑 in 𝐺.
The works of Dvorák (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 𝜑, the WL-dimension is equal to the treewidth of the Gaifman graph
of 𝜑.
In this work, we give a characterisation that applies to all conjunctive queries. Given any conjunctive
query 𝜑, we prove that its WL-dimension is equal to the semantic extension width sew(𝜑), a novel width
measure that can be thought of as a combination of the treewidth of 𝜑 and its quantified star size, an invariant
introduced by Durand and Mengel (ICDT 2013) describing how the existentially quantified variables of 𝜑 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 𝜑 cannot be computed by GNNs of order smaller
than sew(𝜑).
The majority of the paper is concerned with establishing a lower bound of the WL-dimension of a query.
Given any conjunctive query 𝜑 with semantic extension width 𝑘, we consider a graph 𝐹 of treewidth 𝑘
obtained from the Gaifman graph of 𝜑 by repeatedly cloning the vertices corresponding to existentially
quantified variables. Using a modification due to Fürer (ICALP 2001) of the Cai-Fürer-Immerman construction
(Combinatorica 1992), we then obtain a pair of graphs 𝜒 (𝐹 ) and 𝜒ˆ(𝐹 ) that are indistinguishable by the (𝑘 − 1)-
dimensional WL-algorithm since 𝐹 has treewidth 𝑘. Finally, in the technical heart of the paper, we show
that 𝜑 has a different number of answers in 𝜒 (𝐹 ) and 𝜒ˆ(𝐹 ). Thus, 𝜑 can distinguish two graphs that cannot be
distinguished by the (𝑘 − 1)-dimensional WL-algorithm, so the WL-dimension of 𝜑 is at least 𝑘. |
| first_indexed | 2024-04-09T03:56:11Z |
| format | Conference item |
| id | oxford-uuid:96d1c05d-de92-4a3b-a304-1c9f5a3afc43 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-09-25T04:17:28Z |
| publishDate | 2024 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:96d1c05d-de92-4a3b-a304-1c9f5a3afc432024-07-20T16:00:20ZThe Weisfeiler-Leman dimension of conjunctive queriesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:96d1c05d-de92-4a3b-a304-1c9f5a3afc43EnglishSymplectic ElementsAssociation for Computing Machinery2024Göbel, AGoldberg, LARoth, MA graph parameter is a function 𝑓 on graphs with the property that, for any pair of isomorphic graphs 𝐺1 and 𝐺2, 𝑓 (𝐺1) = 𝑓 (𝐺2). The Weisfeiler–Leman (WL) dimension of 𝑓 is the minimum 𝑘 such that, if 𝐺1 and 𝐺2 are indistinguishable by the 𝑘-dimensional WL-algorithm then 𝑓 (𝐺1) = 𝑓 (𝐺2). The WL-dimension of 𝑓 is ∞ if no such 𝑘 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 𝜑, we quantify the WL-dimension of the function that maps every graph 𝐺 to the number of answers of 𝜑 in 𝐺. The works of Dvorák (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 𝜑, the WL-dimension is equal to the treewidth of the Gaifman graph of 𝜑. In this work, we give a characterisation that applies to all conjunctive queries. Given any conjunctive query 𝜑, we prove that its WL-dimension is equal to the semantic extension width sew(𝜑), a novel width measure that can be thought of as a combination of the treewidth of 𝜑 and its quantified star size, an invariant introduced by Durand and Mengel (ICDT 2013) describing how the existentially quantified variables of 𝜑 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 𝜑 cannot be computed by GNNs of order smaller than sew(𝜑). The majority of the paper is concerned with establishing a lower bound of the WL-dimension of a query. Given any conjunctive query 𝜑 with semantic extension width 𝑘, we consider a graph 𝐹 of treewidth 𝑘 obtained from the Gaifman graph of 𝜑 by repeatedly cloning the vertices corresponding to existentially quantified variables. Using a modification due to Fürer (ICALP 2001) of the Cai-Fürer-Immerman construction (Combinatorica 1992), we then obtain a pair of graphs 𝜒 (𝐹 ) and 𝜒ˆ(𝐹 ) that are indistinguishable by the (𝑘 − 1)- dimensional WL-algorithm since 𝐹 has treewidth 𝑘. Finally, in the technical heart of the paper, we show that 𝜑 has a different number of answers in 𝜒 (𝐹 ) and 𝜒ˆ(𝐹 ). Thus, 𝜑 can distinguish two graphs that cannot be distinguished by the (𝑘 − 1)-dimensional WL-algorithm, so the WL-dimension of 𝜑 is at least 𝑘. |
| spellingShingle | Göbel, A Goldberg, LA Roth, M The Weisfeiler-Leman dimension of conjunctive queries |
| title | The Weisfeiler-Leman dimension of conjunctive queries |
| title_full | The Weisfeiler-Leman dimension of conjunctive queries |
| title_fullStr | The Weisfeiler-Leman dimension of conjunctive queries |
| title_full_unstemmed | The Weisfeiler-Leman dimension of conjunctive queries |
| title_short | The Weisfeiler-Leman dimension of conjunctive queries |
| title_sort | weisfeiler leman dimension of conjunctive queries |
| work_keys_str_mv | AT gobela theweisfeilerlemandimensionofconjunctivequeries AT goldbergla theweisfeilerlemandimensionofconjunctivequeries AT rothm theweisfeilerlemandimensionofconjunctivequeries AT gobela weisfeilerlemandimensionofconjunctivequeries AT goldbergla weisfeilerlemandimensionofconjunctivequeries AT rothm weisfeilerlemandimensionofconjunctivequeries |