Buckets:
Title: On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters
URL Source: https://arxiv.org/html/2309.17053
Markdown Content: Back to arXiv
This is experimental HTML to improve accessibility. We invite you to report rendering errors. Use Alt+Y to toggle on accessible reporting links and Alt+Shift+Y to toggle off. Learn more about this project and help improve conversions.
Why HTML? Report Issue Back to Abstract Download PDF Abstract 1Introduction 2Preliminaries 3Characterizing the WL-dimension of graph motif patterns 4Counting occurrences of graph motif patterns 5Determining the WL-dimension for subgraph counting 6Conclusions and Limitations References
HTML conversions sometimes display errors due to content that did not convert correctly from the source. This paper uses the following packages that are not yet supported by the HTML conversion tool. Feedback on these issues are not necessary; they are known and are being worked on.
failed: MnSymbol failed: tkz-graph
Authors: achieve the best HTML results from your LaTeX submissions by following these best practices.
License: arXiv.org perpetual non-exclusive license arXiv:2309.17053v3 [cs.LG] 28 Mar 2024 On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters Matthias Lanzinger TU Wien & University of Oxford matthias.lanzinger@tuwien.ac.at &Pablo BarcelΓ³ PUC Chile & IMFD & CENIA pbarcelo@uc.cl Abstract
Seminal research in the field of graph neural networks (GNNs) has revealed a direct correspondence between the expressive capabilities of GNNs and the π -dimensional Weisfeiler-Leman ( π WL) test, a widely-recognized method for verifying graph isomorphism. This connection has reignited interest in comprehending the specific graph properties effectively distinguishable by the π WL test. A central focus of research in this field revolves around determining the least dimensionality π , for which π WL can discern graphs with different number of occurrences of a pattern graph π . We refer to such a least π as the WL-dimension of this pattern counting problem. This inquiry traditionally delves into two distinct counting problems related to patterns: subgraph counting and induced subgraph counting. Intriguingly, despite their initial appearance as separate challenges with seemingly divergent approaches, both of these problems are interconnected components of a more comprehensive problem: "graph motif parameters". In this paper, we provide a precise characterization of the WL-dimension of labeled graph motif parameters. As specific instances of this result, we obtain characterizations of the WL-dimension of the subgraph counting and induced subgraph counting problem for every labeled pattern π . Particularly noteworthy is our resolution of a problem left open in previous work concerning induced copies. We additionally demonstrate that in cases where the π WL test distinguishes between graphs with varying occurrences of a pattern π , the exact number of occurrences of π can be computed uniformly using only local information of the last layer of a corresponding GNN. We finally delve into the challenge of recognizing the WL-dimension of various graph parameters. We give a polynomial time algorithm for determining the WL-dimension of the subgraph counting problem for given pattern π , answering an open question from previous work. We additionally show how to utilize deep results from the field of graph motif parameters, together with our characterization, to determine the WL-dimension of induced subgraph counting and counting π -graphlets.
1Introduction Context.
Graph neural networks (GNNs) have gained increasing importance over the last decade due to their ability to process and operate over graph-structured data (Wu et al., 2021; Zhou et al., 2020; Joshi et al., 2020). Tasks in which GNNs excel include node classification (Xiao et al., 2022), graph classification (Errica et al., 2020), link prediction (Teru et al., 2020; Zhu et al., 2021), and query answering over knowledge graphs (Daza & Cochez, 2020; Galkin et al., 2022). Based on these, GNNs have found applications in many fields, including social network analysis (Kipf & Welling, 2018), recommender systems (Ying et al., 2018), chemistry (Gilmer et al., 2017), semantic web (Hogan et al., 2022; Schlichtkrull et al., 2018), natural language processing (Marcheggiani & Titov, 2017), and combinatorial optimization (Dai et al., 2021).
The practical importance of GNNs has spurred the community to study their expressive power. This refers to the ability of GNNs to distinguish pairs of non-isomorphic graphs. As it was early observed in two landmark articles (Morris et al., 2019; Xu et al., 2019), the expressive power of so-called message-passing GNNs (MPGNNs) is precisely that of the Weisfeiler-Leman (WL) test (Weisfeiler & Leman, 1968), one of the most renowned methods for checking graph isomorphism. As recently observed, this correspondence holds even in cases where graphs are node- and edge-labeled, naturally representing the rich structure present in knowledge graphs (BarcelΓ³ et al., 2022). The above has ignited significant interest among experts in exploring which graph properties can be distinguished by the WL test, especially those that are crucial for the applications of MPGNNs (Arvind et al., 2020; Chen et al., 2020; Morris et al., 2020; BarcelΓ³ et al., 2021; Huang et al., 2023; Bouritsas et al., 2023).
A class of graph properties that have received special attention in this context is the number of times a given βpatternβ appears as a subgraph in a graph. The relevance of this class emanates from the fact that subgraph counts are used in several graph-related tasks, such as constructing graph kernels (Shervashidze et al., 2009; Kriege et al., 2018) and computing spectral graph information (Preciado & Jadbabaie, 2010). Subgraph counts also lie at the basis of some methods that measure the similarity between graphs (Alon et al., 2008). Therefore, it is crucial to comprehend the extent to which these methods align with the expressive capabilities of the WL test (or equivalently, MPGNNs).
In its more general version, the WL test is characterized by a parameterized dimension, π β₯ 1 (Cai et al., 1992; Morris et al., 2019). The π -dimensional WL test, or π WL test for short, iteratively colors the π -tuples of nodes in a graph until a fixpoint is reached. Two graphs are said to be distinguishable by π WL, if the multisets of colors of all π -tuples reached at this fixpoint are different. A graph property π can be distinguished by π WL if for any two graphs πΊ , π» where π β’ ( πΊ ) β π β’ ( π» ) only if πΊ and π» are distinguishable by π WL. We are then interested in the least π for which a parameter can be distinguished by π WL. We refer to this π as the WL-dimension of the parameter.
Several important results have been obtained over the last few years regarding the WL-dimension of counting the number of copies of a graph π (the pattern). We summarize some of such results next, by distinguishing the case in which we count copies of π (subgraphs) from the one in which we count induced copies of π (induced subgraphs). For the sake of clarity, we call the former the subgraph WL-dimension of π and the latter the induced subgraph WL-dimension of π .
β’
Counting subgraphs: An important notion in graph theory is the treewidth of a graph, which intuitively measures its degree of acyclicity (Diestel, 2012). The hereditary treewidth of a pattern π is, in broad terms, the largest treewidth of any of the homomorphic images of π . Arvind et al. (2020) initiated the study of the ability of the WL test to count subgraphs in terms of the notion of hereditary treewidth. They established that if the pattern π has hereditary treewidth π , then π has subgraph WL-dimension at most π . Nevertheless, the sole instance in which they were able to demonstrate the validity of the converse was for π
1 , i.e., they showed that π has subgraph WL-dimension one iff π has hereditary treewidth one. In the meantime, some partial results were obtained for the case when π
2 over particular classes of graphs. For instance, by combining results in Arvind et al. (2020) and FΓΌrer (2017), one obtains that the largest cycle (respectively, path) with a subgraph WL-dimension of two is that of length seven. Very recently, however, this gap has been closed. In fact, Neuen (2023) proves the following for each π β₯ 1 : if π is a pattern, then π has subgraph WL-dimension π iff π has hereditary treewidth π . This also provides an alternative explanation for the aforementioned result on cycles (resp., paths), as one can observe that a cycle (resp., path) has hereditary treewidth two iff it is of length at most seven.
β’
Counting induced subgraphs: Most of the existing results on counting induced subgraphs were obtained in Chen et al. (2020). The authors show that all patterns with π + 1 nodes have an induced subgraph WL-dimension bounded by π . Moreover, this is optimal for π
1 ; i.e., no pattern with three or more nodes has induced subgraph WL-dimension one. It is not known if this correspondence continues to hold for π
1 , i.e., whether there are patterns with π + 2 or more nodes with induced subgraph WL-dimension π , for π
1 .
It is noteworthy that the previously mentioned results regarding counting induced subgraphs were achieved in a broader context compared to the results concerning counting subgraphs. Specifically, the former apply even to labeled graphs, where each node and edge is assigned a label, whereas the latter were derived for non-labeled graphs.
Therefore, we have different levels of understanding of the capabilities of the π WL test for counting subgraphs and induced subgraphs. Furthermore, these two issues have been addressed separately and employing distinct techniques, which enhances the perception that there is no inherent structural linkage between the two. However, as evidenced by research in the field of counting complexity, there exists a cohesive approach through which these types of problems can be examined. In fact, the counting of subgraphs and induced subgraphs are fundamentally interconnected, akin to opposite faces of a coin, as they can be represented as linear combinations of one another (LovΓ‘sz, 1967). Thus, we can achieve insight into either of them by exploring the linear combinations of the other.
Expanding upon this idea, Curticapean et al. (2017) introduced a comprehensive framework for graph motif parameters, which are defined as linear combinations of subgraph counts. In this paper, we study the ability of the WL test to count graph motifs, which provides us with a general approach for studying problems related to subgraph counting in this setting. Our main contributions are summarized below. It is worth noting that all such results are derived within the framework established in Chen et al. (2020), which focuses on labeled graphs. This introduces an additional level of intricacy into all the proofs presented in this paper.
β’
By building on tools developed by Neuen (2023) and Seppelt (2023), we establish a precise characterization for the class of labeled graph motifs with WL-dimension π , for π β₯ 1 . Specifically, for subgraph counting, this class precisely corresponds to the patterns of hereditary treewidth π , aligning with the characterization presented by Neuen (2023) for the case of unlabeled graphs. For induced subgraph counting, this class contains precisely the patterns featuring π + 1 nodes, thus resolving the open issue posed by Chen et al. (2020).
β’
The previous result characterizes for which graph motifs Ξ the π WL test is able to distinguish between graphs with different numbers of occurrences of Ξ . A natural question arises: Is it possible to obtain the number of occurrences of a graph motif Ξ in a graph πΊ by computing a function over the multiset of colors of π -tuples of vertices obtained from the π WL test? We answer this question affirmatively. This result can be of interest to researchers working on MPGNN applications, as it suggests that by designing a suitable MPGNN architecture, one might be able to count the number of subgraphs that appear in a given graph.
β’
We finally move into the problem of determining the WL-dimension for the problem of counting the occurrences of a given graph pattern π . Our characterization shows that for counting induced subgraphs this problem is trivial as the WL-dimension is precisely the number of vertices in π minus 1. For subgraph counting, in turn, the problem is nontrivial, as we have to check for each homomorphic image of π whether its treewidth is at most π . Since the number of homomorphic images of π is potentially exponential, this yields a naΓ―ve exponential time algorithm for the problem. We show that, in spite of this, the problem admits a polynomial time algorithm. The existence of such an algorithm was left open in Arvind et al. (2020) even for the case π
2 .
Since many of the proofs in the paper are extensive and complex, we have opted to place technical details in the appendix and offer proof sketches in the main body of the paper to conserve space.
2Preliminaries Labeled graphs.
We work with graphs that contain no self-loops and are node- and edge-labeled. Let Ξ£ and Ξ be finite alphabets containing node and edge labels, respectively. A labelled graph is a tuple πΊ
( π , πΈ , π , π ) , where π is a finite set of nodes, πΈ is a set of undirected edges, i.e., unordered pairs of nodes, π : π β Ξ£ is a function such that π β’ ( π£ ) represents the label of node π£ , for each π£ β π , and π : πΈ β Ξ is a function such that π β’ ( π ) represents the label of edge π , for each π β πΈ .
Given labeled graphs πΊ
( π , πΈ , π , π ) and πΊ β²
( π β² , πΈ β² , π β² , π β² ) , a homomorphism from πΊ to πΊ β² is a function π : π β π β² such that: (1) ( π’ , π£ ) β πΈ β ( π β’ ( π’ ) , π β’ ( π£ ) ) β πΈ β² , for each π’ , π£ β π , (2) π β’ ( π£ )
π β² β’ ( π β’ ( π£ ) ) , for each π£ β π , and (3) for each edge ( π’ , π£ ) β πΈ , it holds that π β’ ( π’ , π£ )
π β² β’ ( π β’ ( π’ ) , π β’ ( π£ ) ) . If, in addition, π is a bijection and the first condition is satisfied by the stronger statement that ( π’ , π£ ) β πΈ β ( π β’ ( π’ ) , π β’ ( π£ ) ) β πΈ β² , for each π’ , π£ β π , then we say that π is an isomorphism. We write π§ππ β’ ( πΊ , πΊ β² ) for the set of all homomorphisms from πΊ to πΊ β² and ππππ β’ ( πΊ , πΊ β² ) for the number of homomorphisms in π§ππ β’ ( πΊ , πΊ β² ) .
For a π -tuple π£ Β―
( π£ 1 , β¦ , π£ π ) β π β’ ( πΊ ) π , we write πΊ β’ [ π£ Β― ] as a shortcut for πΊ β’ [ { π£ 1 , β¦ , π£ π } ] . The atomic type πΊππ β’ ( πΊ , π£ Β― ) of a π -tuple π£ Β― of vertices in a labeled graph πΊ is some function such that, for π£ Β― β π β’ ( πΊ ) π and π€ Β― β π β’ ( π» ) π , it holds that πΊππ β’ ( πΊ , π£ Β― )
πΊππ β’ ( π» , π€ Β― ) if and only if the mapping π£ π β¦ π€ π is an isomorphism from πΊ β’ [ π£ Β― ] into π» β’ [ π€ Β― ] .
Weisfeiler-Leman test.
Let πΊ be a labeled graph. The π WL test, for π > 0 , iteratively colors the elements in π β’ ( πΊ ) π , that is, all tuples of π nodes from π β’ ( πΊ ) . The color of tuple π£ Β― β π β’ ( πΊ ) π after π iterations, for π β₯ 0 , is denoted π π π β’ ( π£ Β― ) . This coloring is defined inductively, and its definition depends on whether π
1 or π
1 .
β’
For π
1 , we have that
π
π
π
β’
(
π£
)
:=
{
πΊππ
β’
(
πΊ
,
π£
)
if
β’
π
0
( π π β 1 π β’ ( π£ ) , { { ( π β’ ( π£ , π€ ) , π π β 1 π β’ ( π€ ) ) β£ ( π£ , π€ ) β π β’ ( πΊ ) } } )
if β’ π β₯ 1
In other words, π π π β’ ( π£ ) consists of the color of vertex π£ in the previous iteration, along with a multiset that includes, for each neighbor π€ of π£ in πΊ , an ordered pair consisting of the color of π€ in the previous iteration and the label of the edge connecting π£ and π€ .
β’
For π
1 , we have that
π
π
π
β’
(
π£
Β―
)
:=
{
πΊππ
β’
(
πΊ
,
π£
Β―
)
if
β’
π
0
( π π β 1 π β’ ( π£ Β― ) , { { πΌπ β’ ( π€ , π β 1 , π£ Β― ) β£ π€ β π β’ ( πΊ ) } } )
if β’ π β₯ 1
Here, πΌπ β’ ( π€ , π , π£ Β― ) denotes the color tuple for π€ β π β’ ( πΊ ) and π£ Β― β π β’ ( πΊ ) π , and is defined as:
πΌπ β’ ( π€ , π , π£ Β― )
( π π π β’ ( π£ Β― β’ [ π€ / 1 ] ) , β¦ , π π π β’ ( π£ Β― β’ [ π€ / π ] ) ) ,
where π£ Β― β’ [ π€ / π ] denotes the tuple that is obtained from π£ Β― by replacing its π th component with the element π€ . In other words, π π π β’ ( π£ Β― ) is formed by the color of π£ Β― in the previous iteration, along with a multiset that includes, for each node π€ in πΊ , a tuple containing the color in the previous iteration for each tuple that can be derived from π£ Β― by substituting one of its components with the element π€ .
The π WL test stabilizes after finitely many steps. That is, for every labeled graph πΊ there exists a π‘ β₯ 0 such that, for each π£ Β― , π€ Β― β π β’ ( πΊ ) π , it holds that
π π‘ π β’ ( π£ Β― )
π π‘ π β’ ( π€ Β― ) βΊ π π‘ + 1 π β’ ( π£ Β― )
π π‘ + 1 π β’ ( π€ Β― ) .
We then define the color of tuple π£ Β― in πΊ as π π β’ ( π£ Β― ) := π π‘ π β’ ( π£ Β― ) .
We say that two labeled graphs πΊ and π» are indistinguishable by π WL (or πΊ β‘ π β’ WL π» ), if the π -WL algorithm yields the same coloring on both graphs, i.e.,
{ { π π ( π£ Β― ) β£ π£ Β― β π ( πΊ ) π ) } }
{ { π π ( π€ Β― ) β£ π€ Β― β π ( π» ) π ) } } .
The version of the WL test used in this paper is also known as the folklore π WL test (as defined, for instance, by Cai et al. (1992)). It is essential to note that an alternative version of this test, known as the oblivious π WL test, has also been explored in the machine learning field (Morris et al., 2019). Notably, it is established that for each π β₯ 1 , the folklore π WL test possesses the same distinguishing capability as the oblivious ( π + 1 ) WL test (Grohe & Otto, 2015).
Graph motif parameters.
A labeled graph parameter is a function that maps labeled graphs into β . A labeled graph motif parameter (Curticapean et al., 2017) is a labeled graph parameter such that, for a labeled graph πΊ , its value in πΊ is equivalent to a (finite) linear combination of homomorphism counts into πΊ . More formally, function Ξ is a labeled graph motif parameter, if there are fixed labeled graphs πΉ 1 , β¦ , πΉ β and constants π 1 , β¦ , π β β β β { 0 } , such that for every labeled graph πΊ :
Ξ β’ ( πΊ )
β π
1 β π π β’ ππππ β’ ( πΉ π , πΊ ) .
(1)
We refer to the set { πΉ 1 , β¦ , πΉ β } as the support π²πππ β’ ( Ξ ) of Ξ .
It is often not easy to see whether a function on graphs is a graph motif parameter. Fortunately, we know that certain model counting problems for large fragments of first-order logic are indeed labeled graph motif parameters. In the following, we view labeled graphs as structures. Logical formulas can then be defined over a signature that contains a unary relation symbol π π , for each label π β Ξ£ , and a binary relation symbol πΈ πΏ , for each label πΏ β Ξ . Let π be a formula with free variables π₯ Β― of the form
β π¦ Β― β’ π β’ ( π¦ Β― , π₯ Β― ) β§ π β β’ ( π₯ Β― ) ,
where π is a formula consisting of positive atoms, conjunction and disjunction, and π β is a conjunction of inequalities and possibly negated atoms. We call such formulas positive formulas with free constraints. We write # β’ π β’ ( πΊ ) for the number of assignments to π₯ Β― for which the formula is satisfied in labeled graph πΊ . It is known that the function # β’ π for such formulas can be expressed as a finite linear combination of homomorphism counts with projection. GΓΆbel et al. (2024) have recently initiated the study of how homomorphism counts with projection relate to the π WL test. In this paper, we are content with a more restricted fragment for which no projection in the homomorphism counts is required.
Proposition 1 (Chen & Mengel (2016),Dell et al. (2019)).
Let π be a quantifier-free positive formula with free constraints. Then the function # β’ π is a labeled graph motif parameter1.
Example 1.
We start by showing that counting subgraphs and counting induced subgraphs are examples of graph motif parameters (for each fixed pattern). Suppose for simplicity that we consider graphs without node labels and with a single edge label, and let πΈ be the corresponding relation symbol. Consider a graph π»
( π , πΈ ) for which we want to count occurrences as a subgraph. We can do this via the following positive formula with free constraints:
π π» := β ( π’ , π£ ) β πΈ πΈ β’ ( π₯ π’ , π₯ π£ ) β§ β π’ β π£ , π’ , π£ β π π₯ π’ β π₯ π£ .
Notice that this formula has a free variable π₯ π£ , for each node π£ β π . If now we want to count the number of occurrences of π» as an induced subgraph, we can simply extend π π» with the following conjunction: β ( π’ , π£ ) β πΈ Β¬ πΈ β’ ( π₯ π’ , π₯ π£ ) . graph motif parameter by πππ½ π» .
Consider the following formula with free variables π₯ 1 , β¦ , π₯ π :
π IS := β 1 β€ π β π β€ π Β¬ πΈ β’ ( π₯ π , π₯ π )
The satisfying assignments to π IS in graph πΊ are precisely its independent sets of size at most π . We see then that counting π -independent sets is a graph motif parameter.
β
Counting graph motifs parameters and the WL test.
Take π
0 . Consider a graph parameter Ξ . We state that the π WL test can distinguish Ξ if, for any pair of labeled graphs πΊ and π» where Ξ β’ ( πΊ ) β Ξ β’ ( π» ) , it follows that πΊ β’ π β’ WL π» . The WL-dimension of a graph parameter Ξ is the minimal π
0 such that the π WL test can distinguish Ξ .
3Characterizing the WL-dimension of graph motif patterns
In this section, we provide a characterization of the WL-dimension of labeled graph motif parameters. To grasp the results presented in this section, it is crucial to first define the concept of the treewidth of a graph πΊ . This concept, well-known in graph theory, aims to quantify the degree of acyclicity in πΊ .
Let πΊ
( π , πΈ , π , π ) be a labeled graph. A tree decomposition of πΊ is a tuple ( π , πΌ ) , where π is a tree and πΌ is a function that maps each node π‘ of the tree π to a subset of the nodes in π , that satisfies the following:
β’
For each ( π’ , π£ ) β πΈ , there exists a node π‘ β π with { π’ , π£ } β πΌ β’ ( π‘ ) .
β’
For each node π£ β π , the set { π‘ β π β£ π£ β πΌ β’ ( π‘ ) } is a subtree of π . In other words, the nodes π‘ of π for which πΌ β’ ( π‘ ) contains π£ are connected in π .
The width of a tree decomposition ( π , πΌ ) of πΊ is defined as max π‘ β π β‘ | πΌ β’ ( π‘ ) | β 1 . The treewidth of πΊ is then defined as the minimum width of any of its tree decompositions. It is easy to see that πΊ has treewidth one if and only if its underlying graph is a tree.
The following is the main result in this section. It characterizes the WL-dimension of a graph motif parameter in terms of the treewidth of its support set.
Theorem 2.
Let Ξ be a labeled graph motif parameter. The WL-dimension of Ξ is the maximum treewidth of any labeled graph in π²πππ β’ ( Ξ ) .
Before providing a proof sketch of this result, we show some examples of how the theorem can be applied to concrete instances of labeled graph motif patterns used in this paper.
Example 2.
Let us consider first the case of counting subgraphs for a labeled graph π» . We denote the corresponding labeled graph motif pattern by π²ππ» π» . We assume that π» does not have self-loops. We call a labeled graph π» β² a homomorphic image of π» , if there exists a surjective homomorphism from π» into π» β² . Notice that the set of homomorphic images of π» contains a finite number of labeled graphs up to isomorphism. Following Curticapean et al. (2017), we denote by πππΊππ β’ ( π» ) the set of all labeled graphs that are obtained from the homomorphic images of π» by removing self-loops. As shown in Curticapean et al. (2017), the support of π²ππ» π» is precisely the set πππΊππ β’ ( π» ) . It follows from Theorem 2 that the π» s for which π WL can distinguish subgraph counting for π²ππ» π» are precisely those for which the maximum treewidth of a labeled graph in πππΊππ β’ ( π» ) is at most π . This result has been established for unlabeled graphs in Neuen (2023). Here, we extend this result to labeled graphs.
Consider now the case of counting induced subgraphs for π» . We write π¨ππ½ π» for the corresponding labeled graph motif pattern It can be shown that, in this case, the support for π¨ππ½ π» is the set of all labeled graphs π» β² that can be obtained from π» by adding edges among its nodes. If π» has π nodes, then the support for π» contains the clique of size π which is known to have treewidth π β 1 . Furthermore, this is the labeled graph with the largest treewidth in the support of π» . It follows from Theorem 2 that the π» s for which π WL can distinguish induced subgraph counting for π¨ππ½ π» are precisely those with at most π + 1 nodes. This solves an open question from Chen et al. (2020). β
We now discuss our proof of Theorem 2. The full argument requires us to extend various existing results in the field to the setting of labeled graphs. We defer those proofs to the appendix. Let β± be a class of labeled graphs. We write πΊ β‘ β± π» if for every πΉ β β± it holds that ππππ β’ ( πΉ , πΊ )
ππππ β’ ( πΉ , π» ) . Following Roberson (2022), we define the labeled homomorphism-distinguishing closure of β± , denoted ππππΌπ πππππΎ β’ ( β± ) , as the set of all labeled graphs πΏ for which the following holds for every labeled graphs πΊ , π» :
πΊ β‘ β± π» βΉ ππππ β’ ( πΏ , πΊ )
ππππ β’ ( πΏ , π» ) .
We say that β± is labeled homomorphism-distinguishing closed, if ππππΌπ πππππΎ β’ ( β± )
β± . A recent paper by Neuen establishes that the class of all (unlabeled) graphs of treewidth at most π is labeled homomorphism-distinguishing closed (Neuen, 2023). As we establish next, this extends to the labeled setting. Here we denote by β β’ π― π the class of all labeled graphs of treewidth at most π .
Lemma 3.
Fix π
0 . The class β β’ π― π is labeled homomorphism-distinguishing closed.
Proof Sketch.
For our proof we show that a recent breakthrough result by Roberson (2022) holds also in the labeled case. The result depends on the notion of weak oddomorphisms which, roughly speaking, are a particular kind of homomorphism that satisfies additional constraints (see Appendix B for details). To simplify the presentation, we actually only show that Robersonβs result holds for edge-labeled graphs, i.e., those labeled graphs where all vertices have the same label. We then show that this is enough and that we can lift the homomorphism-distinguishing closedness from the edge-labeled case to the general labeled case.
Formally, we show the labeled analogue of (Roberson, 2022, Theorem 6.2). Namely, that every class of labeled graphs β± that satisfies the following two closure properties is also labeled homomorphism-distinguishing closed. (1) If πΉ β β± , and πΉ has a weak oddomorphism into πΊ , then πΊ β β± . (2) β± is closed under restriction to connected components and disjoint union. Once we have established that the theorem still holds, we show that both properties are satisfied by β β’ π― π . For the first, in particular, we can build on parts of Neuenβs argument for the unlabeled graph case. The second property is a well known property of treewidth and requires no further insights. β
The second intermediate result that we need is the following lemma, proved recently by Seppelt.
Lemma 4 (Lemma 4 in (Seppelt, 2023)).
Let β± and β be classes of labeled graphs. Suppose β± is finite and its elements are pairwise non-isomorphic. For each πΉ β β± , let π πΏ be a element of β . Then β± β ππππΌπ πππππΎ β’ ( β ) , if for all labeled graphs πΊ , π» we have that:
πΊ β‘ β π» βΉ β πΉ β β± π πΉ β ππππ β’ ( πΉ , πΊ )
β πΉ β β± π πΉ β ππππ β’ ( πΉ , π» ) .
We also need the following result which establishes that two labeled graphs πΊ and π» are indistinguishable by π WL if and only if ππππ β’ ( πΉ , πΊ )
ππππ β’ ( πΉ , π» ) , for every labeled graph πΉ of treewidth π . The unlabeled analogue of this result is due to DvorΓ‘k (2010) (rediscovered by Dell et al. (2018)).
Lemma 5.
For all labeled graphs πΊ , π» we have πΊ β‘ π β’ WL π» if and only if πΊ β‘ β β’ π― π π» .
Proof of Theorem 2.
Let β± be the support of Ξ and π be the maximum treewidth of a labeled graph in β± , for π > 0 . We first show that π WL can distinguish Ξ . Take two labeled graphs πΊ , π» with πΊ β‘ π WL π» . By Lemma 5, we also have that πΊ β‘ β β’ π― π π» . In particular, ππππ β’ ( πΉ , πΊ )
ππππ β’ ( πΉ , π» ) , for every πΉ β β± , and therefore:
Ξ β’ ( πΊ )
β πΉ β β± π πΉ β ππππ β’ ( πΉ , πΊ )
β πΉ β β± π πΉ β ππππ β’ ( πΉ , π» )
Ξ β’ ( π» ) .
Suppose now, for the sake of contradiction, that the β WL test can distinguish Ξ , for β < π . Let πΊ , π» be arbitrary labeled graphs. Notice that we have the following:
πΊ β‘ β β’ π― β π» β πΊ β‘ β β’ WL π» β Ξ β’ ( πΊ )
Ξ β’ ( π» ) β β πΉ β β± π πΉ β ππππ β’ ( πΉ , πΊ )
β πΉ β β± π πΉ β ππππ β’ ( πΉ , π» ) .
The first implication follows from Lemma 5 and the second one since the β WL test can distinguish Ξ . But then Lemma 4 tells us that β± β ππππΌπ πππππΎ β’ ( β β’ π― β ) , and Lemma 3 that ππππΌπ πππππΎ β’ ( β β’ π― β )
β β’ π― β . This is a contradiction since β± contains at least one labeled graph of treewidth π
β . β
4Counting occurrences of graph motif patterns
In this section, we establish that if a graph motif parameter Ξ has WL-dimension π , then one can actually obtain the number of occurrences of Ξ in a graph πΊ by looking independently only at the colors of the individual π -tuples, rather than the full multiset of stable colors for all π -tuples. This is of particular interest when looking at the π WL test from the perspective of MPGNNs. The natural expression of the π WL test in MPGNNs leads to a final layer that assigns a color to each π -tuple of vertices. So, if Ξ is a labeled graph motif parameter, and we want to compute Ξ β’ ( πΊ ) over a labeled graph πΊ , then Theorem 6 shows that it is not necessary to combine the information of the final layer in a global way, but that there is some uniform function that can map each individual color to a rational number, the sum of which will exactly be Ξ β’ ( πΊ ) .
More formally, we show the following result.
Theorem 6.
Let Ξ be a labeled graph motif parameter and suppose that the maximum treewidth of a labeled graph in π²πππ β’ ( Ξ ) is at most π . Also, let π π denote the set of possible colors produced by the π WL test. Then there exists a function π Ξ : π π β β such that Ξ β’ ( πΊ )
β π£ Β― β π β’ ( πΊ ) π π Ξ β’ ( π π β’ ( π£ Β― ) ) , for every labeled graph πΊ .
Theorem 6 is obtained by using the following lemma, whose proof can be found in the appendix.
Lemma 7.
Let πΉ be a labeled graph with treewidth at most π and let π π denote the set of possible colors produced by the π WL test. There exists a function π πΉ : π π β β such that ππππ β’ ( πΉ , πΊ )
β π£ Β― β π β’ ( πΊ ) π π πΉ β’ ( π π β’ ( π£ Β― ) ) , for each labeled graph πΊ .
Theorem 6 is then obtained from Lemma 7 as follows. Let us assume that π²πππ Ξ
{ πΉ 1 , β¦ , πΉ β } and Ξ β’ ( πΊ ) is defined as in Equation (1). We define π Ξ : π π β β as π Ξ β’ ( π )
β π
1 β π π β π πΉ π β’ ( π ) , for each π β π π . We then have that
Ξ β’ ( πΊ )
β π
1 β π π β ππππ β’ ( πΉ π , πΊ ) (Equation (1)
β π
1 β ( β π£ Β― β π β’ ( πΊ ) π π π β π πΉ π β’ ( π π£ Β― π ) ) (Lemma 7)
β π£ Β― β π β’ ( πΊ ) π ( β π
1 β π π β π πΉ π ( π π£ Β― π ) )
β π£ Β― β π β’ ( πΊ ) π π Ξ ( π π£ Β― π ) .
5Determining the WL-dimension for subgraph counting
We finally move on the recognizability problem for WL-dimension. That is, for given graph motif parameter Ξ , we want to know the WL-dimension of Ξ . Arvind et al. (2020) previously raised the question for which labeled graph patterns π» , the graph parameter π²ππ» π» can be expressed by 2 WL. Here, we give a polynomial time algorithm that decides the WL-dimension for all subgraph counting problems, thus also resolving this question as a special case. For the analogous problem π¨ππ½ π» , we have already seen in Example 2 that the recognition problem is, in fact, trivial. In addition, we determine the WL-dimension of counting π -graphlets, i.e., all connected induced subgraphs on π vertices, as illustrative examples of how further such results can be derived from the deep body of work in graph motif parameters.
We will begin with the case of subgraph counting. Recall that a minor of a labeled graph π» is a labeled graph π» β² that can be obtained from π» by removing nodes or edges, or contracting edges (that is, removing an edge and simultaneously merging its endpoints). By Theorem 2, and the following discussion on spasm β’ ( π» ) , recognising the WL-dimension of π²ππ» π» is precisely the problem of recognising the maximum treewidth of the homomorphic images of π» . We can use classic results in the field of graph minors to express this as a property checkable in monadic second-order logic (MSO), for which model checking is tractable in our setting. We give a more detailed sketch of the argument below, full details are provided in the appendix.
Theorem 8.
Fix π
0 . There is a polynomial time algorithm for the following problem: given a labeled graph π» , checking if the WL-dimension of π²ππ» π» is at most π .
Proof Sketch.
The algorithm first checks whether the treewidth of π» is at most π . It is well known that this can be decided in linear time for fixed π Bodlaender (1996). Obviously, π» β πππΊππ β’ ( π» ) , and thus if the treewidth of π» is strictly larger than π , we are done and the algorithm rejects. By the Robertson-Seymour Theorem (Robertson & Seymour, 2004), there is a finite set of graphs β± π , such that there is a πΉ β β± π that is a minor of graph πΊ if and only if the treewidth of π» is at most π . We then show that there is an MSO formula π πΉ such that
π» β§ π πΉ βΊ πΉ is a minor of some homomorphic image of π» .
Clearly then π
β πΉ β β± π π π is an MSO formula such that π» β§ π if and only if the maximum treewidth in the spasm is at most π . By a standard algorithmic metatheorem of Courcelle (Courcelle, 1990), deciding π» β§ π is possible in time π β’ ( β , π ) β’ | π» | , where β is the treewidth of π» . As β β€ π by our initial check, and π depends only on π , the problem is in π β’ ( | π» | ) for fixed π . β
We now move on to study the WL-dimension of counting π -graphlets, a popular problem in graph mining and analysis of social networks Bressan et al. (2017); Jin et al. (2018). Here, no dedicated algorithm is necessary as the WL-dimension will be immediate from observations about the respective support when viewed as graph motif parameters. While the problem of counting π -graphlets is itself popular, its analysis in our context serves as a example of how the recently established theory of graph motif parameters can answer these types of recognizability questions.
The logical view, via positive formulas with free constraints, is not the only natural way to see that a graph parameter is indeed also a graph motif parameter. An alternative notion that is known to correspond to graph motif parameters is the problem of counting all induced subgraphs of size π , that satisfy some arbitrary (computable) property π (Roth & Schmitt, 2020). Thus, with π being the property of the graph being connected, this immediately tells us that counting π -graphlets is a graph motif parameter. In fact, Roth & Schmitt (2020) not only shows that every such property is a graph motif parameter, but they also determine precisely when the π -clique is in the support (i.e., has a coefficient β 0 ). Moreover, in the case of properties that are closed under the removal of edges, there is a strong connection to combinatorial topology that can be leveraged to make this determination.
Proposition 9.
For π
1 , counting the number of π -graphlets has WL-dimension π β 1 .
Proof Sketch.
Let π¨ππ½ π C be graph parameter that counts the number of induced subgraphs on π vertices that are connected, i.e., the number of π -graphlets. For graph property π , let πΈ π π be the set of all edge-subsets of the complete graph on π vertices, such that the corresponding subgraph satisfies property π . Roth & Schmitt (2020) showed that the problem of counting all induced subgraphs on π vertices that satisfy π is a graph motif parameter, and that the π -clique is in the support of the parameter precisely when
β π΄ β πΈ π π ( β 1 ) | π΄ | β 0 .
Furthermore, they show that if π is closed under removal of edges, then πΈ π π β { 0 } forms a so-called simplical graph complex and the reduced Euler characteristic of this simplical complex is also non-zero exactly when the π -clique is in the support of the parameter (see (Jonsson, 2008) for details regarding these notions).
Now, let us use C for the property of being connected and ππ’ for its complement, i.e., disconnectedness. Property ππ’ is closed under removal of edges and its simplical complexes are well understood (cf., (Jonsson, 2008)). In particular, their reduced Euler characteristic is known to be Β± ( π β 1 ) ! , which is non-zero for natural π . Now, it is enough to observe that
β π΄ β πΈ π ππ’ ( β 1 ) | π΄ | + β π΄ β πΈ π π’ ( β 1 ) | π΄ |
0
as the properties are complementary and the sums thus form an alternating sum of binomials. Since the left-hand sum is non-zero, so is the right-hand sum for property π’ . We can therefore conclude that the π -clique is in the support of π¨ππ½ π C 3, demonstrating that the maximal treewidth in the support is at least π β 1 . The argument of Roth & Schmitt (2020) also implicitly shows by construction that the support contains no graphs with more than π vertices, thus also confirming that the treewidth in π²πππ β’ ( π¨ππ½ π C ) is no higher than π β 1 . Applying Theorem 2 completes the argument. β
Moreover, Proposition 1 is constructive and in many cases it is feasible to determine the support from logical formulations of parameters as in Example 1. For example, following the construction of Dell et al. (2019) for the formula π πΌ β’ π reveals that counting π -independent sets also has WL-dimension π β 1 . What is particularly noteworthy in this context, is that we can use the exact same methods that have been used to study the parameterized complexity of these problems. Just as the WL-dimension, the complexity of computing graph motif parameter Ξ depends precisely on the maximum treewidth in π²πππ β’ ( Ξ ) (Curticapean et al., 2017). That is, analysis of the complexity of computing a graph motif parameter and analysis of the WL-dimension of the parameter revolve around the same question of how high the treewidth of the basis can become.
6Conclusions and Limitations
We have shown that recent developments in graph theory and counting complexity can be brought together to provide a precise characterization of the WL-dimension of labeled graph motif parameters. We have also shown that if a graph motif parameter Ξ belongs to such a class, then the number of βappearancesβ of Ξ in a given labeled graph πΊ can be computed uniformly only from local information about the individual π -tuples from the output of the π WL test. Based on known results this suggests that π -dimensional MPGNNs are capable of computing this number, if equipped with the right pooling functions (Morris et al., 2019; Xu et al., 2019). Some work on this direction has already been carried out in Chen et al. (2020) by using local relational polling. Finally, we have used our characterization to show that both the classes of patterns for which the π WL test can distinguish labeled subgraph counting and labeled induced subgraph counting can be recognized in polynomial time.
The main limitation of our work is that it only concerns the worst-case behavior of the algorithms considered. In fact, the counterexamples our proof constructs for cases in which the π WL test is not capable of counting the number of occurrences of a graph motif Ξ are rather complicated and do not necessarily resemble the cases encountered in practice. Therefore, it would be interesting to understand to what extent these results relate to average-case scenarios, or how well they align with practical applications. We leave this for future work.
Acknowledgements
We are very grateful to Marc Roth for many valuable and enjoyable discussions that have influenced this work. Matthias Lanzinger acknowledges support by the Royal Society βRAISON DATAβ project (Reference No. RP\R1\201074) and by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT2201]. Pablo BarcelΓ³ has been funded by the National Center for Artificial Intelligence CENIA FB210017, Basal ANID, and by ANID Millennium Science Initiative Program Code ICN17002.
References Alon et al. (2008) β Noga Alon, Dao P, Hajirasouliha I, Hormozdiari F, and Sahinalp SC.Biomolecular network motif counting and discovery by color coding.Bioinformatics, 13:1β24, 2008. Arvind et al. (2020) β Vikraman Arvind, Frank FuhlbrΓΌck, Johannes KΓΆbler, and Oleg Verbitsky.On weisfeiler-leman invariance: Subgraph counts and related graph properties.J. Comput. Syst. Sci., 113:42β59, 2020. BarcelΓ³ et al. (2021) β Pablo BarcelΓ³, Floris Geerts, Juan L. Reutter, and Maksimilian Ryschkov.Graph neural networks with local graph parameters.In NeurIPS 2021, pp. 25280β25293, 2021. BarcelΓ³ et al. (2022) β Pablo BarcelΓ³, Mikhail Galkin, Christopher Morris, and Miguel A. Romero Orth.Weisfeiler and leman go relational.In LoG, volume 198 of Proceedings of Machine Learning Research, pp. 46. PMLR, 2022. Bodlaender (1996) β Hans L. Bodlaender.A linear-time algorithm for finding tree-decompositions of small treewidth.SIAM J. Comput., 25(6):1305β1317, 1996.doi: 10.1137/S0097539793251219. Bouritsas et al. (2023) β Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein.Improving graph neural network expressivity via subgraph isomorphism counting.IEEE Trans. Pattern Anal. Mach. Intell., 45(1):657β668, 2023. Bressan et al. (2017) β Marco Bressan, Flavio Chierichetti, Ravi Kumar, Stefano Leucci, and Alessandro Panconesi.Counting graphlets: Space vs time.In WSDM, pp. 557β566. ACM, 2017.doi: 10.1145/3018661.3018732. Cai et al. (1992) β Jin-yi Cai, Martin FΓΌrer, and Neil Immerman.An optimal lower bound on the number of variables for graph identification.Comb., 12(4):389β410, 1992. Chen & Mengel (2016) β Hubie Chen and Stefan Mengel.Counting answers to existential positive queries: A complexity classification.In Proc. PODS, pp. 315β326. ACM, 2016.doi: 10.1145/2902251.2902279.URL https://doi.org/10.1145/2902251.2902279. Chen et al. (2020) β Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna.Can graph neural networks count substructures?In NeurIPS, 2020. Courcelle (1990) β Bruno Courcelle.The monadic second-order logic of graphs. i. recognizable sets of finite graphs.Inf. Comput., 85(1):12β75, 1990. Curticapean et al. (2017) β Radu Curticapean, Holger Dell, and DΓ‘niel Marx.Homomorphisms are a good basis for counting small subgraphs.In STOC, pp. 210β223. ACM, 2017. Dai et al. (2021) β Hanjun Dai, Artem Kozachenko, Mark Schmidt, Ioannis Tsochantaridis, and Petar VeliΔkoviΔ.Learning combinatorial optimization algorithms over graphs.In ICML, 2021. Daza & Cochez (2020) β Daniel Daza and Michael Cochez.Message passing for query answering over knowledge graphs.CoRR, abs/2002.02406, 2020.URL https://arxiv.org/abs/2002.02406. Dell et al. (2018) β Holger Dell, Martin Grohe, and Gaurav Rattan.LovΓ‘sz meets weisfeiler and leman.In Proc. ICALP, volume 107 of LIPIcs, pp. 40:1β40:14. Schloss Dagstuhl - Leibniz-Zentrum fΓΌr Informatik, 2018.doi: 10.4230/LIPIcs.ICALP.2018.40. Dell et al. (2019) β Holger Dell, Marc Roth, and Philip Wellnitz.Counting answers to existential questions.In Proc. ICALP 2019, volume 132 of LIPIcs, pp. 113:1β113:15. Schloss Dagstuhl - Leibniz-Zentrum fΓΌr Informatik, 2019. Diestel (2012) β Reinhard Diestel.Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics.Springer, 2012. DvorΓ‘k (2010) β Zdenek DvorΓ‘k.On recognizing graphs by numbers of homomorphisms.J. Graph Theory, 64(4):330β342, 2010.doi: 10.1002/jgt.20461. Errica et al. (2020) β Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli.A fair comparison of graph neural networks for graph classification.In ICLR, 2020. FΓΌrer (2017) β Martin FΓΌrer.On the combinatorial power of the weisfeiler-lehman algorithm.CoRR, abs/1704.01023, 2017.URL http://arxiv.org/abs/1704.01023. Galkin et al. (2022) β Michael Galkin, Zhaocheng Zhu, Hongyu Ren, and Jian Tang.Inductive logical query answering in knowledge graphs.In NeurIPS, 2022. Gilmer et al. (2017) β Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl.Neural message passing for quantum chemistry.In ICML, 2017. GΓΆbel et al. (2024) β Andreas GΓΆbel, Leslie Ann Goldberg, and Marc Roth.The weisfeiler-leman dimension of existential conjunctive queries.2024. Grohe & Otto (2015) β Martin Grohe and Martin Otto.Pebble games and linear equations.J. Symb. Log., 80(3):797β844, 2015. Hogan et al. (2022) β Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia dβAmato, Gerard de Melo, Claudio Gutierrez, Sabrina Kirrane, JosΓ© Emilio Labra Gayo, Roberto Navigli, Sebastian Neumaier, Axel-Cyrille Ngonga Ngomo, Axel Polleres, Sabbir M. Rashid, Anisa Rula, Lukas Schmelzeisen, Juan F. Sequeda, Steffen Staab, and Antoine Zimmermann.Knowledge graphs.ACM Comput. Surv., 54(4):71:1β71:37, 2022. Huang et al. (2023) β Xingyue Huang, Miguel A. Romero Orth, Δ°smail Δ°lkan Ceylan, and Pablo BarcelΓ³.A theory of link prediction via relational weisfeiler-leman.CoRR, abs/2302.02209, 2023. Jin et al. (2018) β Jiashun Jin, Zheng Tracy Ke, and Shengming Luo.Network global testing by counting graphlets.In ICML, volume 80, pp. 2338β2346. PMLR, 2018.URL http://proceedings.mlr.press/v80/jin18b.html. Jonsson (2008) β Jakob Jonsson.Simplicial complexes of graphs, volume 3.Springer, 2008. Joshi et al. (2020) β Chaitanya K. Joshi, Yujia Li, and Bryan Perozzi.A comprehensive survey on graph neural networks.IEEE Communications Surveys & Tutorials, 2020. Kipf & Welling (2018) β Thomas Kipf and Max Welling.Community detection in graphs with graphsage.In ICLR, 2018.URL https://arxiv.org/abs/1706.02216. Kriege et al. (2018) β Nils M. Kriege, Christopher Morris, Anja Rey, and Christian Sohler.A property testing framework for the theoretical expressivity of graph kernels.In IJCAI, pp. 2348β2354. ijcai.org, 2018. LovΓ‘sz (1967) β LΓ‘szlΓ³ LovΓ‘sz.Operations with structures.Acta Mathematica Hungarica, 18(3-4):321β328, 1967. Marcheggiani & Titov (2017) β Diego Marcheggiani and Ivan Titov.Encoding sentences with graph convolutional networks for semantic role labeling.In EMNLP, 2017. Morris et al. (2019) β Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.Weisfeiler and leman go neural: Higher-order graph neural networks.In AAAI, pp. 4602β4609, 2019. Morris et al. (2020) β Christopher Morris, Gaurav Rattan, and Petra Mutzel.Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings.In NeurIPS 2020, 2020. Neuen (2023) β Daniel Neuen.Homomorphism-distinguishing closedness for graphs of bounded tree-width.CoRR, abs/2304.07011, 2023. OEIS Foundation Inc. (2023) β OEIS Foundation Inc.The On-Line Encyclopedia of Integer Sequences, 2023.Published electronically at http://oeis.org. Preciado & Jadbabaie (2010) β Victor M. Preciado and Ali Jadbabaie.From local measurements to network spectral properties: Beyond degree distributions.In CDC, pp. 2686β2691. IEEE, 2010. Roberson (2022) β David E. Roberson.Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree.CoRR, abs/2206.10321, 2022. Robertson & Seymour (2004) β Neil Robertson and Paul D. Seymour.Graph minors. XX. wagnerβs conjecture.J. Comb. Theory, Ser. B, 92(2):325β357, 2004.doi: 10.1016/j.jctb.2004.08.001. Roth (2019) β Marc Roth.Counting problems on quantum graphs: Parameterized and exact complexity classifications, 2019. Roth & Schmitt (2020) β Marc Roth and Johannes Schmitt.Counting induced subgraphs: A topological approach to #w[1]-hardness.Algorithmica, 82(8):2267β2291, 2020. Schlichtkrull et al. (2018) β Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling.Modeling relational data with graph convolutional networks.In ESWC, 2018. Seppelt (2023) β Tim Seppelt.Logical equivalences, homomorphism indistinguishability, and forbidden minors.CoRR, abs/2302.11290, 2023. Shervashidze et al. (2009) β Nino Shervashidze, S. V. N. Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten M. Borgwardt.Efficient graphlet kernels for large graph comparison.In AISTATS, volume 5 of JMLR Proceedings, 2009. Teru et al. (2020) β Komal K. Teru, Etienne G. Denis, and William L. Hamilton.Inductive relation prediction by subgraph reasoning.In ICML, pp. 9448β9457, 2020. Weisfeiler & Leman (1968) β Boris Weisfeiler and A.A. Leman.The reduction of a graph to canonical form and the algebra which appears therein, 1968. Wu et al. (2021) β Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu.A comprehensive survey on graph neural networks.IEEE Transactions on Neural Networks and Learning Systems, 2021. Xiao et al. (2022) β Shunxin Xiao, Shiping Wang, Yuanfei Dai, and Wenzhong Guo.Graph neural networks in node classification: survey and evaluation.Mach. Vis. Appl., 33(1):4, 2022. Xu et al. (2019) β Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.How powerful are graph neural networks?In ICLR, 2019. Ying et al. (2018) β Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec.Graph convolutional neural networks for web-scale recommender systems.In KDD, 2018. Zhou et al. (2020) β Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Maosong Sun, and Jie Tang.Graph neural networks: A review of methods and applications.AI Open, 2020. Zhu et al. (2021) β Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal A. C. Xhonneux, and Jian Tang.Neural bellman-ford networks: A general graph neural network framework for link prediction.In NeurIPS 2021, pp. 29476β29490, 2021. Appendix AProof of Lemma 7
This section focuses on the proof of Lemma 7. While it is well known that the π WL test of a graph πΊ determines the homomorphism counts from every graph π» with π‘ β’ π€ β’ ( π» ) < π , we are interested in a slightly stronger statement. In particular, let π» be a graph and let π Β― be some tuple of π distinct vertices in π» . We show that any two π -tuples of vertices π£ Β― , π€ Β― , possibly from different graphs, that obtain the same stable color by the π WL test, there are the same number of homomorphisms extending π Β― β¦ π£ Β― and π Β― β¦ π€ Β― to the respective graphs of π£ Β― and π€ Β― . As a consequence, we see that it is not necessary to know the full multiset of stable colors to determine the homomorphism count from some pattern πΉ , but rather ππππ β’ ( πΉ , β ) can be computed by computing a partial count for each π -tuple independently and simply summing them up.
This is of particular interest when looking at the π WL test from the perspective of GNNs. The natural expression of the π WL test in MPGNNs leads to a final layer that assigns a color to each π -tuple of vertices. If we want to compute ππππ β’ ( πΉ , β ) with a GNN, Lemma 7 shows that it is not necessary to combine the information of the final layer in some global way, but that there is some uniform function that can map each individual color to a rational number, the sum of which will exactly be ππππ β’ ( πΉ , β ) .
We proceed with some technical definitions. For tree decomposition ( π , π΅ ) and subtree π β² of π we will write π΅ β’ ( π β² ) to mean β π’ β π β’ ( π β² ) π΅ β’ ( π’ ) . It will be convenient to consider nice tree decompositions. A nice TD of labeled graph πΊ is a rooted TD where the bags of all leaves are singletons and all non-root nodes are only of three types:
β’
An introduce node π’ is the only child of parent π , and has π΅ β’ ( π’ )
π΅ β’ ( π ) βͺ { π } for some π β π β’ ( πΊ ) β π΅ β’ ( π ) .
β’
A forget node π’ is the only child of parent π , and has π΅ β’ ( π’ )
π΅ β’ ( π ) β { π } for some π β π΅ β’ ( π ) .
β’
Split nodes π’ , π£ are the only two children of parent π , and have π΅ β’ ( π’ )
π΅ β’ ( π£ )
π΅ β’ ( π ) .
It is well known that if a graph has treewidth π , then it also has a nice TD of width π .
For labeled graphs πΉ , πΊ with π Β― β π β’ ( πΉ ) π , π£ Β― β π β’ ( πΊ ) π we write π§ππ β’ ( πΉ , πΊ ) β’ [ π Β― β¦ π£ Β― ] for the set of all homomorphisms from πΉ into πΊ that extend the mapping π Β― β¦ π£ Β― . For a vertex π£ of labeled graph πΉ we write πΉ β π£ to mean πΉ β’ [ π β’ ( πΉ ) β { π£ } ] .
Proposition 10.
Let ( π , π΅ ) be a tree decomposition of labeled graph πΉ . Let π β² be a subtree of π and let πΌ be a node adjacent to π β² in π . For any π§ β π΅ β’ ( πΌ ) β π΅ β’ ( π β² ) and π¦ β π΅ β’ ( π β² ) it holds that if { π¦ , π§ } β πΈ β’ ( πΉ ) , then π¦ β π΅ β’ ( πΌ ) .
Proof.
Suppose the statement were false. Then there is an edge { π¦ , π§ } with π§ in π΅ β’ ( πΌ ) but not in π΅ β’ ( π β² ) , and π¦ β π΅ β’ ( πΌ ) . Let π β be the subtree of π β π β² that contains πΌ . By connectedness, π§ occurs only in bags of π β , whereas π¦ occurs in none of them. Hence, the edge { π¦ , π§ } cannot be subset of any bag, contradicting that ( π , π΅ ) is a tree decomposition. β
Our plan in the proof of Lemma 7 will be to connect nice tree decompositions to π WL colors. Intuitively, just as the π WL test moves "outward" one vertex at a time at each step, a nice tree decomposition changes only one vertex at a time from parent to child. It is known that π§ππ β’ ( πΉ , β ) is determined by the local homomorphisms from πΉ β’ [ π΅ β’ ( π’ ) ] for each node π’ of a tree decomposition, together with the overlap of bags in neighboring nodes in the tree decomposition. Roughly speaking, we show that a color produced by the π WL test has enough information to determine these two facets.
Our formalization of this idea will require significant technical overhead for bookkeeping. To this end we introduce the following notioons. Let πΉ , πΊ , π» be labeled graphs, let π£ Β― β π β’ ( πΊ ) π , π€ Β― β π β’ ( π» ) π and let π : π β’ ( πΉ ) β π β’ ( πΊ ) , π : π β’ ( πΉ ) β π β’ ( π» ) . For set π β π β’ ( πΉ ) with | π | β€ π we say that π , π are in ( π£ Β― , π€ Β― ) -strict π -agreement if π maps vertices in π only to vertices in π£ Β― and π β’ ( π₯ )
π£ π β π β’ ( π₯ )
π€ π for all π₯ β π . For a tree π with node labels πΏ β’ ( π’ ) β π β’ ( πΉ ) of πΉ we say that two homomorphisms are in colorful strict π leaf agreement if for every leaf β of π there exist π£ Β― β π β’ ( πΊ ) π , π€ Β― β π β’ ( π» ) π such that π , π are in ( π£ Β― , π€ Β― ) -strict πΏ β’ ( β ) -agreement and for some π β₯ 1 either π π π β’ ( π£ Β― )
π π π β’ ( π€ Β― ) if | πΏ β’ ( β ) | β€ π or πΌπ β’ ( π , π , π£ Β― β )
πΌπ β’ ( π , π , π€ Β― β ) where π£ Β―
π£ Β― β β’ π , π€ Β―
π€ Β― β β’ π otherwise.
Lemma 11.
Let πΉ , πΊ and π» be labeled graphs, let π£ Β― β π β’ ( πΊ ) π , π€ Β― β π β’ ( π» ) π with π π π β’ ( π£ Β― )
π π π β’ ( π€ Β― ) for some π β₯ 1 , and let π β π β’ ( πΉ ) with | π | β€ π . Let π β π§ππ β’ ( πΉ , πΊ ) , π β π§ππ β’ ( πΉ , π» ) such that they are in ( π£ Β― , π€ Β― ) -strict π -agreement. Let πΉ β² be a labeled graph with vertex π₯ such that πΉ β² β π₯
πΉ and π₯ is only adjacent to vertices in π . Then there is a bijection π between π§ππ β’ ( πΉ β² , πΊ ) β’ [ π ] and π§ππ β’ ( πΉ β² , π» ) β’ [ π ] such that
1.
for all π β² β π§ππ β’ ( πΉ β² , πΊ ) β’ [ π ] and π β’ ( π β² ) there are π£ Β― β²
π£ Β― β’ π , π€ Β― β² β’ π for π β π β’ ( πΊ ) , π β π β’ ( π» ) , such that π β² , π β’ ( π β² ) are in ( π£ Β― β² , π€ Β― β² ) -strict π βͺ { π₯ } -agreement, and
2.
πΌπ β’ ( π , π β 1 , π£ Β― )
πΌπ β’ ( π , π β 1 , π€ Β― ) .
Proof.
Let π β²
π βͺ { π₯ } . Suppose π β²
π βͺ { π₯ β¦ π } is in π» β’ π β’ π β’ ( πΉ β² , πΊ ) . Since π π π β’ ( π£ Β― )
π π π β’ ( π€ Β― ) there must be some π β π β’ ( π» ) such that πΌπ β’ ( π , π β 1 , π£ Β― )
πΌπ β’ ( π , π β 1 , π€ Β― ) . Let π β²
π βͺ { π₯ β¦ π } . Observe that because of the equal color tuples we have in particular, π β’ π‘ β’ π β’ ( πΊ , π£ Β― β’ π )
π β’ π‘ β’ π β’ ( π» , π€ Β― β’ π ) . As π₯ is only adjacent to vertices in π β² we have that for { π¦ , π₯ } β πΈ β’ ( πΉ β² ) that
{ π β² β’ ( π¦ ) , π β² β’ ( π₯ ) } β πΈ β’ ( πΊ ) β { π£ π , π } β πΈ β’ ( πΊ ) β { π€ π , π } β πΈ β’ ( π» ) β { π β² β’ ( π¦ ) , π β² β’ ( π₯ ) } β πΈ β’ ( π» ) .
The middle equivalence follows from π β’ π‘ β’ π β’ ( πΊ , π£ Β― β’ π )
π β’ π‘ β’ π β’ ( π» , π€ Β― β’ π ) . Similarly, it follows immediately from equivalence of the atomic types, that the vertex labels of π and π must be the same, and that π πΊ β’ ( { π£ π , π } )
π π» β’ ( { π€ π , π } ) . Additionally, we clearly have that π β² , π β² are in ( π£ Β― β’ π , π€ Β― β’ π ) -strict π β² -agreement.
This concludes the argument for the individual homomorphisms. To see that this is indeed always a one-to-one correspondence it is enough to observe that because π π π β’ ( π£ Β― )
π π π β’ ( π€ Β― ) , for every distinct choice of π there must be an appropriate distinct choice of π as above. β
Lemma 12.
Let πΊ and π» be labeled graphs, let πΉ be a labeled graph with a nice TD ( π β , π΅ ) of width π , let π Β― be a tuple made up of π vertices that match a bag of the ( π β , π΅ ) . Let π£ Β― β π β’ ( πΊ ) π , π€ Β― β π β’ ( π» ) π with π π β’ ( π£ Β― )
π π β’ ( π€ Β― ) . Then | π§ππ β’ ( πΉ , πΊ ) β’ [ π Β― β¦ π£ Β― ] |
| π§ππ β’ ( πΉ , π» ) β’ [ π Β― β¦ π€ Β― ] | .
Proof.
Let π be a node in π β with π΅ β’ ( π’ )
{ π π β£ π β [ π ] } and assume, w.l.o.g., that it is the root of π β . We argue inductively on subtrees π of π β that contain the node π that there is a bijection π from π§ππ β’ ( πΉ β’ [ π ] , πΊ ) β’ [ π Β― β¦ π£ Β― ] to π§ππ β’ ( πΉ β’ [ π ] , π» ) β’ [ π Β― β¦ π€ Β― ] such that for every π in the domain of π , it and π β’ ( π ) are in colorful strict π leaf agreement. Recall that colorful strict agreement requires agreement on colors (or color tuples) on some round π β₯ 1 of the π WL algorithm. We will not explicitly argue these indexes in the following but instead note that because π π β’ ( π£ Β― )
π π β’ ( π€ Β― ) , which forms our base case in the following induction, we can start from assuming agreement at an arbitrarily high π . It will be clear from our induction that starting from an π higher than the longest path from π to a leaf will be sufficient.
In the base case π contains only π . Since π π β’ ( π£ Β― )
π π β’ ( π€ Β― ) we have that { π£ π β¦ π€ π } π β [ π ] is an isomorphism from πΊ β’ [ π£ Β― ] to π» β’ [ π€ Β― ] . Thus, π Β― β¦ π£ Β― β π§ππ β’ ( πΉ β’ [ π ] , πΊ ) iff π Β― β¦ π€ Β― β π§ππ β’ ( πΉ β’ [ π ] , π» ) .
For the step, assume the statement holds for a tree π β² . Suppose we extend π β² be a node πΌ that is adjacent in π , giving priority to split nodes (i.e., suppose we always extend first by all adjacent split nodes).
If πΌ split node then the leaf bags remain unchanged. The only change that needs to be discussed is the special case that a new leaf is introduced. In that case, by definition the new leaf has the same bag as an existing leaf and the same witnesses for colorful strict π β² leaf agreement apply to the new bag as well, that is π satisfies the desired property also for π .
If πΌ is not a split node, then let π½ be the leaf of π β² that is adjacent (in π β ) to πΌ . Suppose πΌ is a forget node. By assumption any π β π§ππ β’ ( πΉ β’ [ π β² ] , πΊ ) β’ [ π Β― β¦ π£ Β― ] and π β’ ( π ) are in colorful strict π β² leaf agreement. Since π΅ β’ ( π )
π΅ β’ ( π β² ) , the sets of homomorphisms do not change π β² and π . It is therefore sufficient to check that the colorful strict leaf agreement constraints are also satisfied for leaf π΅ β’ ( πΌ ) . In that case, π satisfies the desired properties also for π . Since π΅ β’ ( πΌ ) β π΅ β’ ( π½ ) , any π , π that are in ( π Β― , π Β― ) -strict π΅ β’ ( π½ ) -agreement, are also in ( π Β― , π Β― ) -strict π΅ β’ ( πΌ ) -agreement. It remains to verify the color constraint on π Β― , π Β― . If | π΅ β’ ( π½ ) | β€ π , then we already have π π π β’ ( π Β― )
π π π β’ ( π Β― ) by assumption and are done. Otherwise, we only know that πΌπ β’ ( π‘ , π , π Β― β )
πΌπ β’ ( π’ , π , π Β― β ) for π Β―
π Β― β β’ π‘ , π Β―
π Β― β β’ π’ . Let π§ be the vertex from π΅ β’ ( π½ ) that is forgotten by πΌ . Let π be the index such that π β’ ( π§ )
π π . We distinguish two cases: first, suppose that there is only one such index and there is at least one other π¦ β π΅ β’ ( πΌ ) such that π β’ ( π¦ )
π π . Then there must be some index π β² such that π π β² is not in π β’ ( π΅ β’ ( πΌ ) ) . By strict agreement the same must hold for π π β² and π β’ ( π΅ β’ ( πΌ ) ) . Hence, π , π are also in ( π Β― β’ [ π‘ / π β² ] , π Β― β’ [ π’ / π β² ] ) -strict π΅ β’ ( πΌ ) -agreement, and we have π π β 1 π β’ ( π Β― β’ [ π‘ / π β² ] )
π π β 1 π β’ ( π Β― β’ [ π’ / π β² ] ) by equality of the color tuples. For the other case, if π§ is the only vertex in π΅ β’ ( πΌ ) that π maps to π π or there is more than one index that equals π β’ ( π§ ) , then simply take π β²
π and proceed as in the other case. This concludes the case where πΌ is a forget node.
Suppose that πΌ is an introduce node that introduces vertex π§ and is adjacent (in π β ) to leaf π½ of π β² . By Proposition 10 we have that all vertices of πΉ β’ [ π ] adjacent (in πΉ ) to π§ are in π΅ β’ ( πΌ ) . By assumption there is a bijection π β² from π§ππ β’ ( πΉ β’ [ π β² ] , πΊ ) β’ [ π Β― β¦ π£ Β― ] to π§ππ β’ ( πΉ β’ [ π β² ] , π» ) β’ [ π Β― β¦ π€ Β― ] that maps every homomorphism to one that is in colorful strict π β² leaf agreement. Thus, in particular all homomorphisms are in ( π Β― , π Β― ) -strict π΅ β’ ( π½ ) -agreement with π π π β’ ( π Β― )
π π π β’ ( π Β― ) (because we assume width π , an introduce node can only follow nodes with at most π vertices in the bag). We can therefore apply Lemma 11 to every pair π , π β’ ( π ) to see that there is a bijection π π β² from π§ππ β’ ( πΉ β’ [ π ] , πΊ ) β’ [ π ] to π§ππ β’ ( πΉ β’ [ π ] , π» ) β’ [ π β’ ( π ) ] such that every π β² β π§ππ β’ ( πΉ β’ [ π ] , πΊ ) β’ [ π ] , is in colorful strict π leaf agreement with π β² β’ ( π β² ) . If | π΅ β’ ( πΌ ) | β€ π we can apply the same reasoning as for forget nodes above to observe that the appropriate constraint on the color follows from the lemma.
Let π β² be the disjoint union of all the individual π π β² for all π β π§ππ β’ ( πΉ β’ [ π β² ] , πΊ ) β’ [ π Β― β¦ π£ Β― ] . To see that the π π β² are in fact disjoint it is enough to observe that the sets π§ππ β’ ( πΉ β’ [ π ] , πΊ ) β’ [ π ] are disjoint for different choices of π as π β’ π β’ π β’ ( π ) β π β’ ( πΉ β’ [ π ] ) . Since all π π β² are injective, so is π β² . To see that π β² is also surjective, suppose a π β π§ππ β’ ( πΉ β’ [ π ] , π» ) β’ [ π Β― β¦ π€ Β― ] not in the image of π β² . This means that π cannot be in any set π§ππ β’ ( πΉ β’ [ π ] , π» ) β’ [ π β’ ( π ) ] for π β π§ππ β’ ( πΉ β’ [ π β² ] , πΊ ) β’ [ π Β― β¦ π£ Β― ] . But π is surjective and therefore this would mean that the projection of π to π β’ ( πΉ β’ [ π β² ] ) is not a homomorphism from πΉ [ π β² ] to π» (extending π Β― β¦ π€ Β― ). But homomorphisms are closed under projection to induced subgraphs, so this is impossible. It follows that π β² is also surjective and therefore is the desired bijection. β
As an alternative proof strategy, the main ideas from above can be used to define an algorithm that computes π§ππ β’ ( πΉ , πΊ ) β’ [ π Β― β¦ π£ Β― ] from π π β’ ( π£ Β― ) . An argument along this direction also demonstrate computability of the functions in Theorem 6 and Lemma 7 in the general case (in the uniform case where π π is finite, it suffices to enumerate graphs until all colors in π π are observed). However, in practice the colors in the π WL test are not maintained in their explicit form as nestings of tuples and multisets but rather by compactly representing the πΌπ tuples via some hash function. In that setting, the viability of such an algorithm would be limited.
Proof of Lemma 7.
Observe that for any two distinct tuples π£ Β― , π€ Β― β π β’ ( πΊ ) π we have that the sets of homomorphisms π§ππ β’ ( πΉ , πΊ ) β’ [ π Β― β¦ π£ Β― ] and π§ππ β’ ( πΉ , πΊ ) β’ [ π Β― β¦ π€ Β― ] are disjoint. It is then straightforward to see that π§ππ β’ ( πΉ , πΊ )
\bigcupdot π£ Β― β π β’ ( πΊ ) π β’ π§ππ β’ ( πΉ , πΊ ) β’ [ π Β― β¦ π£ Β― ] and hence ππππ β’ ( πΉ , πΊ )
β π£ Β― β π β’ ( πΊ ) π | π§ππ β’ ( πΉ , πΊ ) β’ [ π Β― β¦ π£ Β― ] | . By Lemma 12 we have that π§ππ β’ ( πΉ , πΊ ) β’ [ π Β― β¦ π£ Β― ] depends only on π π β’ ( π£ Β― ) . This naturally induces a function π πΉ , π Β― that map the possible colorings of the π WL test π to the respective number of homomorphisms, i.e., such that
β π£ Β― β π β’ ( πΊ ) π π πΉ , π Β― β’ ( π π β’ ( π£ Β― ) )
β π£ Β― β π β’ ( πΊ ) π | π§ππ β’ ( πΉ , πΊ ) β’ [ π Β― β¦ π£ Β― ] |
ππππ β’ ( πΉ , πΊ )
β
Another proof detail of Lemma 12 that we would like to emphasize is that it is not strictly necessary for the stable color of π£ Β― and π€ Β― to be equal. Inspection of the proof reveals that it is sufficient for them to be equal for π π π , where π is greater than the maximal number of introduce nodes on a path from π to a leaf. Building on this observation, Lemma 12 actually also shows that especially for small patterns (the number of introduce nodes is of course no greater than the number of vertices) it is sufficient for the graphs to be equivalent under a limited number of steps of the π WL test, rather than equivalent in the stable color, to deduce that hom β‘ ( πΉ , β ) is the same in both graphs.
Theorem 13.
Let πΉ , πΊ , and π» be labeled graphs and let π
| π β’ ( πΉ ) | . Suppose that πΊ and π» have the same color multiset after π steps of the π WL test. Then ππππ β’ ( πΉ , πΊ )
ππππ β’ ( πΉ , π» ) .
Appendix BTechnical Details for Section 3
The goal of this section is to show that for any labeled graph πΉ that has treewidth greater than π , there are labeled graphs πΊ and π» such that πΊ β‘ π β’ π β’ πΏ π» but ππππ β’ ( πΉ , πΊ ) β ππππ β’ ( πΉ , π» ) . Thus, πΊ and π» are witnesses to the fact that the π WL test cannot express the function ππππ β’ ( πΉ , β ) .
To do so, we show that two important results on the functions ππππ for unlabeled graphs still hold in the labeled setting. To distinguish more clearly between the labeled and unlabeled case we will use the term plain graphs to be those labeled graphs where the vertex- and edge-label alphabets are singletons. For technical reasons we will initially focus on edge-labeled graphs, which are labeled graphs where the vertex-label alphabet is a singleton. For labeled graph πΊ , we write ππ πΊππ β’ ( πΊ ) for the plain graph obtained by making all edge and vertex labels of πΊ the same (without changing the vertices or edges of πΊ ).
The main property of ππππ that we are interested in is equivalence for fixed classes of graphs. Formally, let β± be a class of labeled graphs. We write πΊ β‘ β± π» if for every πΉ β β± it holds that ππππ β’ ( πΉ , πΊ )
ππππ β’ ( πΉ , π» ) . Two families of graph classes will be particularly important in the following. We write π― π for the class of plain graphs with treewidth at most π , let β β’ π― π be the class of labeled graphs of treewidth at most π , and let β° β’ π― π for the class of edge-labeled graphs with treewidth at most π .
The first result that we need is the labeled version of a classic result due to DvorΓ‘k (2010) and later rediscovered by Dell et al. (2018). We recall the lemma as stated in the main body. See 5 We wish warn the reader about an unfortunate confluence of terminology at this point. Some of the literature that we build on also refers to labeled graphs. Unfortunately, our use and the uses in the immediately related literature are pairwise distinct and thus require extra care of the reader. We will add further clarification at points where this becomes directly relevant in this section.
For the second key result we need to recall what it means for a class of plain graphs to be homomorphism-distinguishing closed. A class of plain graphs β± is homomorphism distinguishing closed if for every graph πΉ β β± , there are graphs πΊ , π» such that πΊ β‘ β± π» and ππππ β’ ( πΉ , πΊ ) β ππππ β’ ( πΉ , π» ) . The notion naturally extends to the setting of (edge-)labeled graphs by taking β± , as a class of (edge-)labeled graphs and every mention of πΊ , and π» as (edge-)labeled graphs. To clearly distinguish the property in text going forward we will refer to the case where all involved graphs are labeled as labeled homomorphism-distinguishing closed, and analogously we use edge-labeled homomorphism-distinguishing closed when all graphs are edge-labeled. For plain graphs the following was very recently shown by Neuen Neuen (2023).
Theorem 14 (Neuen (2023)).
The class π― π is homomorphism-distinguishing closed.
Our second key ingredient will be to show the same holds in the labeled setting. That is, that β β’ π― π is labeled homomorphism-distinguishing closed.
For our setting where every edge has exactly one label, we are not aware of any clear way to build directly on Theorem 14 to show the labeled versions. Our plan will therefore be to show that the machinery underlying the proof of Theorem 14 still works in our labeled setting.
The necessary machinery is due to Roberson (2022), who introduced the theory of oddomorphisms and showed their deep connection to homomorphism distinguishability. We recall the definition here for the labeled setting, note however that the definition does not respect labels, except implicitly through the definition of a homomorphism of labeled graphs. The neighborhood π πΊ β’ ( π£ ) of vertex π£ in labeled graph πΊ is the set of adjacent vertices (ignoring any labels). Let πΉ and πΊ be labeled graphs and let π be a homomorphism from πΉ to πΊ . A vertex π of πΉ is odd/even (w.r.t. π ) if | π πΉ β’ ( π ) β© π β 1 β’ ( π£ ) | is odd/even for every π£ β π πΊ β’ ( π β’ ( π ) ) . An oddomorphism from πΉ to πΊ is a homomorphism π such that:
1.
every vertex π of πΉ is either odd or even with respect to π , and
2.
for every π£ β π β’ ( πΊ ) , π β 1 β’ ( π£ ) contains an odd number of odd vertices.
A homomorphism π is a weak oddomorphism if there is a subgraph πΉ β² of πΉ , such that π | π β’ ( πΉ β² ) is an oddomorphism from πΉ β² to πΊ .
For plain graphs, Roberson showed that any class of graphs that is closed under weak oddomorphisms, disjoint unions, and restriction to connected components is homomorphism-distinguishing closed. It is one main goal of this section to show that the same also holds for labeled graphs.
Theorem 15 (Labeled Version of Theorem 6.2 (Roberson, 2022)).
Let β± be a class of labeled graphs such that
1.
if πΉ β β± and there is a weak oddomorphism from πΉ to πΊ , then πΊ β β± , and
2.
β± is closed under disjoint unions and restrictions to connected components.
Then β± is labeled homomorphism-distinguishing closed.
Before we move on to the proof of Theorem 15, we first observe that the class β β’ π― π satisfies the conditions of the theorem. Indeed, Condition 15 is trivially satisfied as the treewidth of a graph is the maximum treewidth over the graphβs connected components (and labels do not influence treewidth). For Condition 1 we can reuse the following key part of the proof of Theorem 14.
Proposition 16 (Neuen (2023)).
Let πΉ be a plain graph in π― π . If there is a weak oddomorphism from πΉ to πΊ , then πΊ β π― π .
Recall that labels serve no explicit role in the definition of an oddomorphism beyond restricting the set of homomorphisms overall. Formalizing this observation we can show the same also for labeled graphs.
Lemma 17.
Let πΉ β β β’ π― π and πΊ be a labeled graph. If there is a weak oddomorphism from πΉ to πΊ , then πΊ β β β’ π― π .
Proof.
First, observe that for labeled graphs πΉ , πΊ , if π is an oddomorphism from πΉ to πΊ , then π is also an oddomorphism from ππ πΊππ β’ ( πΉ ) to ππ πΊππ β’ ( πΊ ) . Now, if there is only a weak oddomorphism π from πΉ to πΊ , there is some subgraph πΉ β² such that π | π β’ ( πΉ β² ) is an oddomorphism from πΉ β² to πΊ . Hence, it is also a oddomorphism from ππ πΊππ β’ ( πΉ β² ) to ππ πΊππ β’ ( πΊ ) , meaning that where is a weak oddomorphism from ππ πΊππ β’ ( πΉ ) to ππ πΊππ β’ ( πΊ ) .
We have that π‘ β’ π€ β’ ( πΉ )
π‘ β’ π€ β’ ( ππ πΊππ β’ ( πΉ ) ) β€ π , and therefore by Proposition 16 ππ πΊππ β’ ( πΊ ) β π― π . And therefore also π‘ β’ π€ β’ ( πΊ )
π‘ β’ π€ β’ ( ππ πΊππ β’ ( πΊ ) ) β€ π , i.e., πΊ β β β’ π― π . β
Assuming Theorem 15, we then immediately obtain the key technical result for homomorphism distinguishing closedness in labeled graphs.
Theorem 18.
β β’ π― π is labeled homomorphism distinguishing closed.
The rest of this section is organized as follows. We first verify that Theorem 15 holds in Section B.1. We then argue Lemma 5 in Section B.2. Finally, in Section B.3 we briefly note why Lemma 4 also holds in the labeled setting.
B.1Proof of Theorem 15
We will closely follow the proof of Theorem 6.2 in (Roberson, 2022). We will see that adapting the initial definitions in the right way will actually leave most of the framework for plain graphs intact. In many situations the effect of the labels is on the argument is very subtle. For the sake of verifiability we therefore repeat the modified arguments for the critical path in the unlabeled setting here. We wish to emphasize that, if not stated otherwise, all proofs are effectively due to Roberson.
We first recall the construction of Roberson for the case of plain graphs, roughly following the presentation of Neuen (2023). Let πΊ be a plain graph and π β π β’ ( πΊ ) . Define πΏ π£ , π as 1 if π£ β π and 0 otherwise. The graph π’π₯π¨ β’ ( πΊ , π ) is the graph with vertices
π β’ ( π’π₯π¨ β’ ( πΊ , π ) )
{ ( π£ , π ) β£ π£ β π β’ ( πΊ ) , π β πΌ β’ ( π£ ) , | π | β‘ πΏ π£ , π β’ mod β’ 2 } .
The graph has edge { ( π£ , π ) , ( π’ , π ) } in πΈ β’ ( π’π₯π¨ β’ ( πΊ , π ) ) if and only if { π£ , π’ } β πΈ β’ ( πΊ ) and π£ , π’ β π β’ Ξ β’ π .
The definition can be naturally adapted to the labeled setting by simply inheriting the labels of the original edges and vertices in πΊ . To this end, let πΊ now be a labeled graph. We will define the labeled graph π’π’π₯π¨ β’ ( πΊ , π ) with π β’ ( π’π’π₯π¨ β’ ( πΊ , π ) )
π β’ ( π’π₯π¨ β’ ( πΊ , π ) ) . For vertex ( π£ , π ) β π β’ ( πΊ , π ) , we set the label π β’ ( π£ ) . For the edge-labeling function π edges we simply say that π β’ ( { ( π£ , π ) , ( π’ , π ) } )
π β’ ( { π£ , π’ } ) . That is, π β’ ( { ( π£ , π ) , ( π’ , π ) } )
π if and only if π β’ ( { π£ , π’ } )
π and π£ , π’ β π β’ Ξ β’ π .
We will show that this definition preserves the key properties of π’π₯π¨ graphs in the labeled setting. This might seem unintuitive as it ignores the labels on the sets π β πΌ β’ ( π£ ) as well as the label of vertices in π . However, the key arguments are relative to homomorphisms on the graphs from which the π’π’π₯π¨ construction is obtained. That is, these homomorphisms already follow the constraints imposed by the labelings. We will say that two vertices π’ , π£ are adjacent via label π if there is an edge { π’ , π£ } with label π .
Lemma 19.
Let πΊ be a connected labeled graph and let π , π β² β π β’ ( πΊ ) . Then π’π’π₯π¨ β’ ( πΊ , π ) β π’π’π₯π¨ β’ ( πΊ , π β² ) if | π | β‘ | π β² | β’ mod β’ 2 .
Proof.
Let π
{ π’ , π£ } β πΈ β’ ( πΊ ) and π β²
π β’ Ξ β’ π . We show that πΊ π β πΊ π β² . Let π : π β’ ( π’π’π₯π¨ β’ ( πΊ , π ) ) β π β’ ( π’π’π₯π¨ β’ ( πΊ , π β² ) ) be
π β’ ( ( π , π ) )
{
(
π
,
π
β’
Ξ
β’
{
π
}
)
π
π’ β’ or β’ π
π£
( π , π )
otherwise
As in the plain graph case, it is straightforward to verify that this is a bijection. Suppose that ( π , π ) and ( π , π ) are adjacent via label π in π’π’π₯π¨ β’ ( πΊ , π ) , i.e., { π , π } β πΈ π β’ ( πΊ ) and { π , π } β π β’ Ξ β’ π . Let π β² , π β² such that π β’ ( ( π , π ) )
( π , π β² ) , π β’ ( ( π , π ) )
( π , π β² ) . If { π , π }
π , then π β²
π β’ Ξ β’ { π } and π β²
π β’ Ξ β’ { π } , hence π β’ Ξ β’ π β²
π β’ Ξ β’ π . Thus, { π , π } is also not in π β² β’ Ξ β’ π β² and π β’ ( ( π , π ) ) is adjacent to π β’ ( ( π , π ) ) . In the other case that { π , π } β π , then π β² and π β² will both, individually, contain { π , π } exactly if π and π , respectively, did. So again { π , π } β π β² β’ Ξ β’ π β² . In both cases, the labels of the edge in π’π’π₯π¨ β’ ( πΊ , π ) and π’π’π₯π¨ β’ ( πΊ , π β² ) is simply inherited from { π , π } . Thus, π preserves labeled adjacency.
If ( π , π ) and ( π , π ) are not adjacent via label π in π’π’π₯π¨ β’ ( πΊ , π ) , then either { π , π } β πΈ π β’ ( πΊ ) or { π , π } β πΈ π β’ ( πΊ ) β© ( π β’ Ξ β’ π ) . In the first case, clearly π β’ ( ( π , π ) ) and π β’ ( ( π , π ) ) cannot be adjacent via label π either. In the latter case, we have shown in our argument above that { π , π } β π β² β’ Ξ β’ π β² if and only if { π , π } β π β’ Ξ β’ π . Since { π , π } β π β’ Ξ β’ π , π β’ ( ( π , π ) ) and π β’ ( ( π , π ) ) will not be adjacent via any label in π’π’π₯π¨ β’ ( πΊ , π β² ) .
We have shown that πΊ π β πΊ π β² for π β²
π β’ Ξ β’ π . This implies the lemma via the same final argument as in (Roberson, 2022, Lemma 3.2). β
As a consequence we can focus our investigation on two specific graphs π’π’π₯π¨ β’ ( πΊ ) := π’π’π₯π¨ β’ ( πΊ , β ) and its twist π’π’π₯π¨ Γ β’ ( πΊ ) := π’π’π₯π¨ β’ ( πΊ , { π£ } ) for some arbitrary π£ β π β’ ( πΊ ) .
As a next step we adapt (Roberson, 2022, Lemma 3.4) to the labeled setting. We first recall a definition from Roberson (2022) that carries over unchanged from the plain graph setting. For any π β π β’ ( πΊ ) , the mapping ( π£ , π ) β¦ π£ is a homomorphism from π’π’π₯π¨ β’ ( πΊ , π ) to πΊ . We will refer to this mapping as π in the following. For a homomorphism π β π§ππ β’ ( πΉ , πΊ ) define
π§ππ π β’ ( πΉ , π’π’π₯π¨ β’ ( πΊ , π ) )
{ π β π§ππ β’ ( πΉ , π’π’π₯π¨ β’ ( πΊ , π ) ) β£ π β π
π }
and observe that the sets π§ππ π ( πΉ , π’π’π₯π¨ ( πΊ , π ) for π β π§ππ β’ ( πΉ , πΊ ) partition π§ππ β’ ( πΉ , π’π’π₯π¨ β’ ( πΊ , π ) ) .
The following statement is subtle in our context. Except for qualifying graphs πΊ and πΉ to be labeled, the statement is verbatim the same as Lemma 3.4 in (Roberson, 2022). That is, the labels are not explicitly considered in the system of equations. Note however that the equations are relative to some homomorphism from πΉ to πΊ , which makes the second set of equations implicitly follow the labeling. The fact that this system of equations does not change is the key to requiring only few changes in the later lemmas, as the argument proceeds mainly algebraically via this system of equations.
Lemma 20 (Labeled version of Lemma 3.4 (Roberson, 2022)).
Let πΊ be a connected labeled graph, let π β π β’ ( πΊ ) , and let πΉ be any labeled graph. For a given π β π§ππ β’ ( πΉ , πΊ ) , define variables π₯ π π for all π β π β’ ( πΉ ) and π β πΌ β’ ( π β’ ( π ) ) . Then the elements of π» β’ π β’ π π β’ ( πΉ , π’π’π₯π¨ β’ ( πΊ , π ) ) are in bijection with solutions of the following equations over β€ 2 :
β π β πΌ β’ ( π β’ ( π ) ) π₯ π π
πΏ π β’ ( π ) , π for all β’ π β π β’ ( πΉ )
(2)
π₯ π π + π₯ π π
0 for all β’ { π , π } β πΈ β’ ( πΉ ) , where β’ π
{ π β’ ( π ) , π β’ ( π ) } β πΈ β’ ( πΊ )
(3) Proof.
Suppose π₯ π π that are a solution of the system of equations in the statement of the lemma. For π β π β’ ( πΉ ) , let π β’ ( π ) β πΈ β’ ( πΊ ) be the edges incident to π β’ ( π ) (regardless of label) for which the variable π₯ π π
1 , i.e., the set { π β πΌ β’ ( πΊ ) β£ π₯ π π
1 } . Let π be the mapping π β¦ ( π β’ ( π ) , π β’ ( π ) ) .
We first show that π β π§ππ π β’ ( πΉ , π’π’π₯π¨ β’ ( πΊ , π ) ) . By Equation 2, π β’ ( π ) is guaranteed to be a vertex of π’π’π₯π¨ β’ ( πΊ , π ) for all π β π β’ ( πΉ ) . To see that π preserves labeled adjacency, suppose { π , π } β πΈ π β’ ( πΉ ) . Then π
{ π β’ ( π ) , π β’ ( π ) } β πΈ π β’ ( πΊ ) since π β π§ππ β’ ( πΉ , πΊ ) . From Equation 3 it follows that π₯ π π
π₯ π π . Then, by construction of π’π’π₯π¨ β’ ( πΊ , π ) , π β’ ( π ) is adjacent via label π to π β’ ( π ) exactly if { π β’ ( π ) , π β’ ( π ) } β π β’ ( π ) β’ Ξ β’ π β’ ( π ) . Meaning that π β’ ( π ) is adjacent via label π to π β’ ( π ) if π is either in both π β’ ( π ) and π β’ ( π ) or in neither, which is true because π₯ π π
π₯ π π . Vertex labels are directly preserved via π .
The arguments for injectivity and surjectivity from the original proof (Roberson, 2022, Lemma 3.4) apply verbatim. β
Since we can use the same system of equations (which does not explicitly consider labels) as used in Roberson (2022), the development from Section 3 of (Roberson, 2022) holds almost unchanged from here. For the sake of completeness we repeat the relevant parts for the proof of Theorem 15 here, including discussion on why the proofs are unaffected by the labels where relevant.
Let πΊ be a connected labeled graph, πΉ a labeled graph, and let π β π§ππ β’ ( πΉ , πΊ ) . Let π be the set of pairs ( π , π ) such that π β π β’ ( πΉ ) and π β πΈ β’ ( π β’ ( π ) ) . We define the matrices π΄ π β β€ 2 π β’ ( πΉ ) Γ π and π΅ π β β€ 2 πΈ β’ ( πΉ ) Γ π as:
π΄ π , ( π , π ) π
{
1
if
β’
π
π
0
otherwise
(4)
π΅ { π , π } , ( π , π ) π
{
1
if
β’
π
β
{
π
,
π
}
β’
and
β’
π
{ π β’ ( π ) , π β’ ( π ) }
0
otherwise
(5)
Let π π be the characteristic vector of π β 1 β’ ( π ) , i.e., the vector where the element corresponding to vertex π β π β’ ( πΉ ) is 1 if π β π β 1 β’ ( π ) and 0 otherwise (i.e., the vector ( πΏ π β’ ( π ) , π ) π β π β’ ( πΉ ) . The system of equations from Lemma 20 can then be expressed as
( π΄ π
π΅ π ) β’ π₯
( π π
0 )
(6) Theorem 21 (Labeled version of Theorem 3.6 (Roberson, 2022)).
Let πΊ be a connected labeled graph, let π β π β’ ( πΊ ) , and let π β π§ππ β’ ( πΉ , πΊ ) for some labeled graph πΉ . Then ππππ π β’ ( πΉ , π’π’π₯π¨ β’ ( πΊ ) )
0 and
ππππ π β’ ( πΉ , π’π’π₯π¨ β’ ( πΊ , π ) )
{ ππππ π β’ ( πΉ , π’π’π₯π¨ β’ ( πΊ ) )
if Equation 6 has a solution
0
if Equation 6 has no solution
Proof Sketch.
The original proof (Roberson, 2022, Theorem 3.6) is a straightforward application of Lemma 20. The equations are exactly the same as in the unlabeled case and the argument works without modification in our setting. β
Theorem 22 (Labeled Version of Theorem 3.13 (Roberson, 2022)).
Let πΊ be a connected labeled graph and πΉ be a labeled graph. Then ππππ β’ ( πΉ , π’π’π₯π¨ β’ ( πΊ ) ) β₯ ππππ β’ ( πΉ , π’π’π₯π¨ Γ β’ ( πΊ ) ) . Furthermore, the inequality is strict if and only if there exists a weak oddomorphism from πΉ to πΊ . If such a weak oddomorphism π exists, there is a connected subgraph πΉ β² of πΉ such that π | π β’ ( πΉ β² ) is an oddomorphism from πΉ β² to πΊ .
Proof Sketch.
The original proof of (Roberson, 2022, Theorem 3.13) works unchanged, although it might not be considered straightforward to observe that this is the case. We therefore repeat the key steps here with emphasis on the points where it needs to be observed that edge labels do not affect the argument. We wish to stress again that this proof is due to Roberson. We repeat it here to allow for a more targeted discussion of why labels have minimal effect on the argument, and to note necessary subtle differences.
If ππππ β’ ( πΉ , π’π’π₯π¨ β’ ( πΊ ) ) β ππππ β’ ( πΉ , π’π’π₯π¨ Γ β’ ( πΊ ) ) , then by Theorem 21 there is a π β π§ππ β’ ( πΉ , πΊ ) such that Equation 6 over β€ 2 does not have a solution. The non-existence of such a solution is equivalent to the existence of solution to the system (the Fredholm Alternative)
( ( π΄ π ) π
( π΅ π ) π
( π π ) π
0 ) β’ ( π§
π¦ )
( 0
1 )
(7)
where π
{ π’ ^ } contains the vertex such that π’π’π₯π¨ Γ β’ ( πΊ ) := π’π’π₯π¨ β’ ( πΊ , { π’ ^ } ) , π¦ is indexed by vertices of πΉ , and π§ is indexed by edges of πΉ .
Since the argument creates a certificate for the non-equivalence of the homomorphism counts, it might be unintuitive that constructing a weak oddomorphism from this certificate still works in the presence of the additional constraints of the edge labels. However, the certificate is still relative to a π β π§ππ β’ ( πΉ , πΊ ) that respects the edge labeling and as we will see, this is sufficient for the argument to still hold.
Observe that a solution ( π¦ , π§ ) π to this system satisfies ( π΄ π ) π β’ π¦
( π΅ π ) π . Let π
{ π β π β’ ( πΉ ) β£ π¦ π
1 } and let πΉ β² be the subgraph of πΉ with all vertices and edges πΈ β’ ( πΉ β² )
{ π β πΈ β’ ( πΉ ) β£ π§ π
1 } . The goal of the argument now is to show that π is an oddomorphism from πΉ β² to πΊ (and thus a weak oddomorphism w.r.t. πΉ ). Since πΉ β² is a subgraph of πΉ , it is clear that π is still a homomorphism from πΉ β² to πΊ , regardless of labels. The arguments for the properties of the oddomorphism themselves are parity arguments on the number of adjacent edges between π β 1 β’ ( π£ ) and π β 1 β’ ( π’ ) for adjacent π£ , π’ β π β’ ( πΊ ) . These arguments also hold unchanged in the labeled setting as the labeled homomorphism π still preserves all adjacencies. Finally, πΉ β² as constructed above may not be connected. As in the unlabeled case we can then replace πΉ β² be a connected component by showing that if there is a weak oddomorphism π | π β’ ( πΉ β² ) for some subgraph πΉ β² , then we can assume w.l.o.g., that πΉ β² is connected (Roberson, 2022, Lemma 3.12). β
Lemma 23.
Let πΉ , πΊ be labeled graphs. Then ππππ β’ ( πΉ , π’π’π₯π¨ β’ ( πΊ ) )
ππππ β’ ( πΉ , π’π’π₯π¨ Γ β’ ( πΊ ) ) .
Proof.
It is known that the identity ππ½ on π β’ ( πΊ ) is an oddomorphism from πΊ to πΊ in the plain graph case (Roberson, 2022, Lemma3.14). The definition of oddomorphism does not take the labels of edges into account (only the neighborhoods of vertices, which are unaffected by labels), and ππ½ is still a homomorphism in the labeled setting. Hence, ππ½ must also be an oddomorphism from πΊ to πΊ in the labeled setting. The statement then follows immediately from Theorem 22. β
The lemma also demonstrates that π’π’π₯π¨ β’ ( πΊ ) β ΜΈ π’π’π₯π¨ Γ β’ ( πΊ ) for any πΊ .
This concludes our replication of the key statements of (Roberson, 2022, Section 3). We will require one additional statement that is not necessary in Robersonβs original argument for the proof of Theorem 15. For technical reasons we will require an labeled graph πΊ such that for some πΉ we can guarantee that ππππ β’ ( πΉ , πΊ )
0 . For plain graphs this is straightforward by taking a large enough clique for πΊ . In the labeled case we need an alternative gadget.
Lemma 24.
Let Ξ£ , Ξ be finite label alphabets and π β₯ 1 . There is a connected labeled graph πΊ such that for every labeled graph πΉ with at vertex/edge-label alphabets Ξ£ , Ξ and π vertices, ππππ β’ ( πΉ , πΊ )
0 .
Proof.
Let π be the set of all (up to isomorphism) labelings of the π vertex clique with labels from Ξ£ and Ξ . Let πΊ β be the disjoint union of all graphs in π . To get the desired graph πΊ , add a fresh vertex with arbitrary label to πΊ β that is adjacent to an arbitrary vertex of each connected component (via an arbitrary edge label). Any π vertex graph πΉ with labels from Ξ£ , Ξ is a subgraph of some element of πΊ β² β π , and hence ππππ β’ ( πΉ , πΊ β² )
0 . Since πΊ β² is a subgraph of πΊ , also ππππ β’ ( πΉ , πΊ )
0 . β
We are now finally ready to prove Theorem 15. Again we can follow the original proof of Theorem 6.2 in (Roberson, 2022) very closely. We give the proof in full as some changes are made due to our streamlined presentation of the preceding statements.
Proof of Theorem 15.
Let πΊ be a graph not in β± . Let πΊ 1 , β¦ , πΊ β be the number of connected components in πΊ and let π½ be the connected graph from Lemma 24 such that ππππ β’ ( πΊ π , π½ )
0 for all π β [ β ] . By Condition (2), there is at least one connected component of πΊ that is not in β± , thus assume w.l.o.g., that πΊ 1 β β± .
Let π» be the disjoint union of π’π’π₯π¨ β’ ( πΊ 1 ) and π½ , and let π» β² be the disjoint union of π’π’π₯π¨ Γ β’ ( πΊ 1 ) and π½ . We will show that π» β‘ β± π» β² and ππππ β’ ( πΊ , π» ) β ππππ β’ ( πΊ , π» β² ) . For the former, suppose πΉ β β± and connected. By Condition (1), there is no weak oddomorphism from πΉ to πΊ , and thus ππππ β’ ( πΉ , π’π’π₯π¨ β’ ( πΊ 1 ) )
ππππ β’ ( πΉ , π’π’π₯π¨ Γ β’ ( πΊ 1 ) ) according to Theorem 22. Because πΉ is connected each homomorphism into π» is either a homomorphism into π½ or into π’π’π₯π¨ β’ ( πΊ 1 ) , i.e., ππππ β’ ( πΉ , π» )
ππππ β’ ( πΉ , π’π’π₯π¨ β’ ( πΊ 1 ) ) + ππππ β’ ( πΉ , π½ ) . The same holds for π» β² , i.e., ππππ β’ ( πΉ , π» β² )
ππππ β’ ( πΉ , π’π’π₯π¨ Γ β’ ( πΊ 1 ) ) + ππππ β’ ( πΉ , π½ ) . Since both terms in both sums are equal we see that ππππ β’ ( πΉ , π» )
ππππ β’ ( πΉ , π» β² ) . Since this holds for all connected πΉ β β± , by Condition (2), it holds for all πΉ β β± .
We move on to show that ππππ β’ ( πΊ , π» ) β ππππ β’ ( πΊ , π» β² ) . Fist, observe that ππππ β’ ( πΊ , π» )
β π
1 β ππππ β’ ( πΊ π , π» ) and similarly for π» β² . our goal will be to show that ππππ β’ ( πΊ π , π» ) β₯ ππππ β’ ( πΊ π , π» β² )
0 for all π β [ β ] , with at least one inequality being strict. For each π β [ β ] we have
ππππ β’ ( πΊ π , π» )
ππππ
β’
(
πΊ
π
,
π’π’π₯π¨
β’
(
πΊ
1
)
)
+
ππππ
β’
(
πΊ
π
,
π½
)
β₯
ππππ
β’
(
πΊ
π
,
π’π’π₯π¨
Γ
β’
(
πΊ
1
)
)
+
ππππ
β’
(
πΊ
π
,
π½
)
ππππ β’ ( πΊ π , π» β² )
0
The equalities are by connectedness, as already argued above. The first inequality follows from Theorem 21. By Lemma 23 first inequality is strict for π
1 and thus ππππ β’ ( πΊ , π» )
ππππ β’ ( πΊ , π» β² ) . β
B.2 Lemma 5
In this section we will discuss why Lemma 5 holds in the labeled setting. From Lemma 7 we directly see that for labeled graphs πΊ , π» , πΊ β‘ π β’ π β’ πΏ π» implies ππππ β’ ( πΉ , πΊ )
ππππ β’ ( πΉ , π» ) for every πΉ β β β’ π― π . We thus focus our attention on showing that πΊ β’ π π» implies the existence of an πΉ β² β β β’ π― π such that ππππ β’ ( πΉ β² , πΊ ) β ππππ β’ ( πΉ β² , π» ) .
As a first step, we consider the logic π π + 1 πΏ of first-order formulas with π + 1 variables and counting quantifiers4 over the signature that contains unary relation symbols π π for each label π in the vertex label alphabet Ξ£ , and binary relation symbols πΈ πΏ for each label πΏ in the edge label alphabet Ξ . We add the superscript πΏ here to distinguish from the usual use of π π + 1 for unlabeled graphs. Cai et al. (1992) famously showed that for graphs πΊ , π» we have πΊ β§ π β π» β§ π for all π β π π + 1 if and only if πΊ β‘ π β’ π β’ πΏ π» . It is folklore that this also holds in the setting of labeled graphs. We in fact only need one direction here, namely if πΊ β’ π β’ π β’ πΏ π» , then there is a π β π π + 1 πΏ such that πΊ β§ π and π» β§ΜΈ π . It is straightforward to verify that the original argument for this direction is unaffected by labels (Cai et al., 1992, Theorem 5.4, case Β¬ 1 β Β¬ 2 ).
In the rest of this section we will show that the existence of such a formula π implies the existence of a labeled graph πΉ for which the homomorphism count into πΊ and π» differs. For this purpose we can adapt an argument by DvorΓ‘k (2010).
We first recall the key definitions from (DvorΓ‘k, 2010). A π -marked5 labeled graph πΊ is a graph with a partial function ππΊππ πΊ : [ π ] β π β’ ( πΊ ) . The set of active markings π πΊ is the subset of [ π ] for which ππΊππ πΊ is defined. Suppose that πΊ , π» are π -marked labeled graphs with π π» β π π» , we define ππππ β’ ( πΊ , π» ) as the number of those homomorphisms π that also preserve markings, i.e., where π β’ ( ππΊππ πΊ β’ ( π ) )
ππΊππ π» β’ ( π ) for each active marking π β π πΊ . A π -marked labeled quantum graph πΊ is a finite linear combination with real coefficients of π -marked labeled quantum graphs. We require all graphs in the linear combination to have the same set of active markings, which we refer to as π πΊ . The function ππππ is extended to the case where the first argument is a π -marked labeled quantum graph πΊ
β π β πΌ π β’ πΊ π as ππππ β’ ( πΊ , π» )
β π β πΌ π β’ ππππ β’ ( πΊ π , π» ) . The treewidth of a quantum graph β π πΌ π β’ πΊ π is max β‘ { π‘ β’ π€ β’ ( πΊ π ) β£ πΌ π β 0 } 6.
A π -marked labeled quantum graph models a formula π for graphs of size π if π πΊ consists of the indices of the free variables of π , and for each labeled graph π» on π vertices with π πΊ β π π» :
β’
if π» β§ π then ππππ β’ ( πΊ , π» )
1 , and
β’
if π» β§ΜΈ π then ππππ β’ ( πΊ , π» )
0 .
From here on we follow the same strategy as DvorΓ‘k, but require some changes to correctly handle labeled graphs.
A product πΊ 1 β’ πΊ 2 of two π -marked labeled graphs πΊ 1 , πΊ 2 is constructed by taking the disjoint union of πΊ 1 and πΊ 2 , identifying the vertices with the same marking, and suppressing parallel edges with the same edge label. That is, we allow the product to have self-loops and to have parallel edges with distinct labels. If there are vertices π£ β π β’ ( πΊ 1 ) , π’ β π β’ ( πΊ 2 ) with the same marking but different vertex labels (we say that πΊ 1 , πΊ 2 are incompatible), the product is a single vertex with a self-loop (and arbitrary labels).
For quantum π -marked labeled quantum graphs πΊ 1
β π πΌ 1 , π β’ πΊ 1 , π and πΊ 2
β π πΌ 2 , π β’ πΊ 2 , π , the product πΊ 1 β’ πΊ 2 is defined as β π , π π½ π , π β’ πΊ 1 , π β’ πΊ 2 , π . The coefficient π½ π , π equals 0 is πΊ 1 , π β’ πΊ 2 , π is the empty graph, contains a loop or parallel edges with distinct labels, otherwise π½ π , π
πΌ β’ 1 , π β’ πΌ 2 , π . The motivation for this distinction in the coefficients π½ π , π is that if π» is a labeled graph, then by definition it has no self-loops and any two vertices are connected only by one edge with one label, hence there can be no homomorphisms into π» from a product πΊ 1 , π β’ πΊ 2 , π that produces such situations. Note that in the situation where πΊ 1 , π , πΊ 2 , π are incompatible at least one of πΊ 1 , π , πΊ 2 , π must have 0 homomorphisms into π» which is why we (ab)use the self-loop as a failure state in this case. In particular, we have ππππ β’ ( πΊ 1 β’ πΊ 2 , π» )
ππππ β’ ( πΊ 1 , π» ) β’ ππππ β’ ( πΊ 2 , π» ) for every labeled graph π» . We write π for a π -marked labeled quantum graph where all coefficients are zero.
Lemma 25 (Labeled version of Lemma 6, (DvorΓ‘k, 2010)).
For each formula in π β π π + 1 πΏ , and for each positive integer π , there exists a labeled quantum graph πΊ of tree-width at most π such that πΊ models π for labeled graphs of size π .
Proof.
We construct πΊ inductively on the structure of π . The base cases significantly differ from those in the proof of (DvorΓ‘k, 2010, Lemma 6). However, once we have established the fact for the base cases, the inductive steps remain the same as they rely only on the property that ππππ β’ ( πΊ 1 β’ πΊ 2 , π» )
ππππ β’ ( πΊ 1 , π» ) β’ ππππ β’ ( πΊ 2 , π» ) , as discussed above, and a technical lemma for quantum graphs (DvorΓ‘k, 2010, Lemma 5) that is not affected by labels.
If π
ππππΎ , let πΊ be the empty graph, if π
πΏπΊπ ππΎ let πΊ
π . If π
π π β’ ( π₯ π ) , let πΊ be the graph with a single vertex π£ with ππΊππ πΊ β’ ( π )
π£ and π β’ ( π£ )
π .
If π
π₯ π
π₯ π , let πΊ
β π β Ξ£ πΊ π (the sum ranges over the elements of the vertex label alphabet) where πΊ π is the π -marked labeled graph with a single vertex π£ , ππΊππ πΊ β’ ( π )
π β’ π β’ π‘ β’ β β’ π β’ π β’ π β’ π β’ π β’ π πΊ β’ ( π )
π£ and π β’ ( π£ )
π . For any specific π -marked π» , the vertex marked as π and π will have only one vertex label. Hence, there will be a homomorphism from exactly one πΊ πΏ (where πΏ matches the label in π» ) and there are 0 homomorphisms for all other germs of πΊ .
If π
πΈ πΏ β’ ( π₯ π , π₯ π ) there are two cases: if π
π , then let πΊ
π as the predicate cannot be satisfied in a self-loop free π» . If π β π , let πΊ
β π , π β² β Ξ£ πΊ π , π β² where πΊ π , π β² is the graph with adjacent vertices π£ and π’ , marked as π , π and labeled with π , π β² , respectively, and π β’ ( { π£ , π’ } )
πΏ . As above, for any given π» , one term of πΊ will have 1 homomorphism into π» , and the others will all have 0 .
That is, for every base case we have shown that the appropriate π -marked labeled quantum graph exists. It is clear that in all the base cases the treewidth is 1 . The rest of the induction proceeds exactly as in (DvorΓ‘k, 2010, Lemma 6). β
Proof of Lemma 5.
As discussed above, we have that for labeled graphs πΊ , π» , πΊ β’ π β’ π β’ πΏ π» implies the existence of a π β π π + 1 πΏ such that πΊ β§ π and π» β§ΜΈ π . By Lemma 25, there is a π -marked labeled quantum graph πΉ with treewidth at most π that models π . Hence, β π πΌ π β’ ππππ β’ ( πΉ π , πΊ )
1 β 0
β π πΌ π β’ ππππ β’ ( πΉ π , π» ) , which means there must be some π such that ππππ β’ ( πΉ π , π» ) β ππππ β’ ( πΉ π , π» ) (recall that the linear combination is always finite). Since πΉ has treewidth at most π , πΉ π β β β’ π― π and therefore πΊ β’ β β’ π― π π» . β
B.3On Lemma 4 for Labeled Graphs
Seppelt (2023) originally showed Lemma 4 for unlabeled graphs. Here we briefly note why the lemma holds unchanged in the labeled case. In particular, the lemma relies on three facts.
1.
First, that ππππ β’ ( πΉ , πΊ 1 Γ πΊ 2 )
ππππ β’ ( πΉ , πΊ 1 ) β’ ππππ β’ ( πΉ , πΊ 2 ) . Where Γ is the direct product as defined in (LovΓ‘sz, 1967).
2.
Second, that the matrix ( ππππ β’ ( πΎ , πΏ ) ) πΎ , πΏ β β π is invertible, where β π is the class of all graphs with at most π vertices.
3.
And finally, that if πΊ β‘ β± π» , then also πΊ Γ πΎ β‘ β± π» Γ πΎ for all graphs πΎ .
The first two points are classic results by LovΓ‘sz (1967), which were originally shown for all relational structures. They thus hold unchanged also for labeled graphs. For the final point, recall that πΊ β‘ β± π» means that for every πΉ β β± we have ππππ β’ ( πΉ , πΊ )
ππππ β’ ( πΉ , π» ) . Then by the first point also ππππ β’ ( πΉ , πΊ Γ πΎ )
ππππ β’ ( πΉ , πΊ ) β’ ππππ β’ ( πΉ , πΎ )
ππππ β’ ( πΉ , π» ) β’ ππππ β’ ( πΉ , πΎ )
ππππ β’ ( πΉ , π» Γ πΎ ) .
Appendix CProof of Theorem 8
This section will make some slight departures from the terminology used in the main body of the paper. For a more focused presentation, we will first discuss the case for unlabeled graphs and afterwards show how to additionally handle labels afterwards. In the main body, the π²ππΊππ of a graph was defined as the set of all homomorphic images, but here it will be simpler to take an alternative (equivalent) perspective. A quotient πΊ / π of a graph πΊ is obtained by taking a partition π of π β’ ( πΊ ) and constructing the graph like πΊ but with all vertices in the same block of π identified. That is, the vertices of πΊ are the blocks of π , and the incidence of a vertex in πΊ / π is the incidence of all vertices in the corresponding block of the partition. It is a standard observation that the set of all quotients of πΊ without self-loops is precisely π²ππΊππ β’ ( πΊ ) (see, e.g., Curticapean et al. (2017)). It will be convenient to also consider the set of all quotients of πΊ , i.e., including those with self-loops, which we will refer to as π²ππΊππ β .
The arguments of this section will revolve around formulas of monadic second-order logic (MSO). That is, formulas of first-order logic that additionally allow for quantification over unary predicates. For formal definition see, e.g., (Courcelle, 1990).
We will decide the treewidth of graphs by deciding whether they contain certain other graphs as minors. To that end we first define the notion of minors formally.
Definition 1.
A minor model from π» into πΊ , is a mapping π : π β’ ( π» ) β 2 π β’ ( πΊ ) such that:
1.
β π’ β π£ β π β’ ( π» ) β’ π β’ ( π’ ) β© π β’ ( π£ )
β ,
2.
β π£ β π β’ ( π» )
πΊ β’ [ π β’ ( π£ ) ] is connected, and
3.
β { π’ , π£ } β πΈ β’ ( π» ) there is an edge (in πΊ ) between some vertex in π β’ ( π’ ) and some vertex in π β’ ( π£ ) .
We say that π» is a minor of πΊ is there a minor model from π» into πΊ .
Checking whether graph π» is a minor of graph πΊ via an MSO formula is a standard construction. Interestingly, to check whether π» is a minor of some quotient of πΊ is simpler, at least in terms of formulating the question in MSO. The key insight here is that the second condition of minor models can effectively be ignored, since there will always be a quotient where all vertices of πΊ β’ [ π β’ ( π£ ) ] are identified. Instead, it is enough to guarantee that the image is non-empty. In concrete terms, to check whether π» is a minor of a graph in π²ππΊππ β β’ ( πΊ ) we will use the following MSO formula.
ππ’ππ‘πππππ
π»
β‘
β
π
1
,
β¦
,
π
π
β
π
(
πΊ
)
(
β
π
|
π
π
|
β₯
1
β§
β
π
β
π
(
π
π
β©
π
π
β ) β§
β { π£ π , π£ π } β πΈ β’ ( π» ) β π₯ β π π β π¦ β π π ( ( π₯ , π¦ ) β πΈ ( πΊ ) ) )
Intuitively, the sets π π correspond to the image of the minor model for vertex π£ π in π» . The minor is of the quotient π where π extends the disjoint sets π 1 , β¦ , π π by the singletons { π£ } for all π£ β π β’ ( πΊ ) but not in any π π for π β [ π ] .
Lemma 26.
Let πΊ and π» be graphs. Then π» is a minor of a quotient πΊ / π β π²ππΊππ β if and only if πΊ β§ ππ’ππ‘πππππ π» .
Proof.
Suppose π» is a minor of πΊ / π and let β be the respective minor map from π» into πΊ / π . Let π be the edge surjective endomorphism (i.e., the homomorphic image) from πΊ into πΊ / π induced by the quotient (i.e., every vertex maps to the block in π that contains the vertex). Let us refer to the vertices of π» as π£ 1 , β¦ , π£ π . The formula is satisfied when for every π β [ π ] , the second-order variable π π is assigned to { π€ β π β’ ( πΊ ) β£ π β’ ( π€ ) β π β’ ( π£ π ) } , that is, all vertices in πΊ that are mapped by π to vertices in π β’ ( π£ π ) . Clearly, the sets π π are disjoint, as the images of π are disjoint. Furthermore, we know by assumption that π is a minor model that for every { π£ π , π£ π } β πΈ β’ ( π» ) , there is at least one edge { π , π } with π β π β’ ( π£ π ) , π β π β’ ( π£ π ) . Since π is edge surjective, there are π β² , π β² β π π such that { π β² , π β² } β πΈ β’ ( πΊ ) and π β’ ( π β² )
π , π β’ ( π β² )
π .
For the other direction now assume that the formula holds. Let π π be the partition of π β’ ( πΊ ) induced by some satisfying choices of π 1 , β¦ , π π (any vertex π£ not in any of these sets corresponds to a singleton { π£ } in the partition). Consider the graph πΊ / π π and let us refer to the vertex corresponding to the block defined by π π as π’ π . We claim that π : π£ π β¦ { π’ π } is a minor model of π» into πΊ / π π . Condition 1 and 2 of a minor model are trivially satisfied. For Condition 3, observe that if there is an edge { π£ π , π£ π } β πΈ β’ ( π» ) but no edge { π’ π , π’ π } β πΈ β’ ( πΊ / π π ) , then there can be no π₯ β π π , π¦ β π π that have an edge between them in πΈ β’ ( πΊ ) , hence contradicting the satisfaction of the final block of conjuncts in ππ’ππ‘πππππ π» . β
We can resolve the possibility of self-loops with a simple observation about minors of quotient graphs. A self-loop occurs in quotient πΊ / π if there is a block π΅ of π that contains adjacent vertices π£ , π’ . W.l.o.g., assume for now that π£ , π’ are the only adjacent vertices in π΅ . If π» is a minor of πΊ / π , it is also a minor of πΊ / π β² where π β² is like π but with π’ as a singleton rather than in π΅ . The vertex for { π’ } in πΊ / π β² will be adjacent to the vertex for block π΅ β²
π΅ β { π’ } . Contracting the vertices for π΅ β² and { π’ } will produce exactly πΊ / π without the self-loop at π΅ . Iterating this idea shows that πΊ / π without self-loops is a minor of some loop-free quotient of πΊ .
Proposition 27.
Let πΊ be a graph and let π» be a loop-free graph. Suppose π» is a minor of some graph in π²ππΊππ β β’ ( πΊ ) . Then π» is a minor of some graph in π²ππΊππ .
Robertson and Seymour famously showed that the graph minor relation is a well-quasi-ordering. Together with the classic observation that any well-quasi-ordering has a finite set of minimal elements this leads to the following standard result.
Theorem 28 (Robertson & Seymour (2004)).
For every minor closed class of graphs π« , there exists a finite set of graphs β± such that πΊ β π« if and only if no πΉ β β± is a minor of πΊ .
Theorem 29.
Deciding max β‘ { π‘ β’ π€ β’ ( πΉ ) β£ πΉ β π²ππΊππ β’ ( πΊ ) } β₯ π is feasible in fixed-parameter linear time when parameterised by π , and in linear time for fixed π .
Proof.
We first check whether π‘ β’ π€ β’ ( πΊ ) β€ π β 1 . It is well known that this can be decided in linear time for fixed π (Bodlaender, 1996). If not, then π‘ β’ π€ β’ ( πΊ ) β₯ π and the algorithm returns true.
The property of having treewidth at most π β 1 is closed under graph minors. By Theorem 28 there exists a finite set β± of forbidden minors for class of graphs with treewidth at most π β 1 . Furthermore, the set β± depends only on the parameter π . Thus, we have that a graph π» has treewidth β₯ π iff it does not have treewidth β€ π β 1 iff it has some graph of β± as a minor. Combining with Proposition 27, we can therefore decide whether the treewidth in the spasm is at least π , by checking for every πΉ β β± whether πΉ is a minor of any quotient of πΊ . According to Lemma 26, this is equivalent to checking whether the formula
π β‘ β πΉ β β± ππ’ππ‘πππππ πΉ
is satisfied by πΊ . By Courcelleβs Theorem (Courcelle, 1990) we can decide πΊ β§ π in time π β’ ( π , π ) β | πΊ | where π is the treewidth of πΊ . Since π depends only on π this is equivalent to π β’ ( π ) β | πΊ | and hence polynomial for fixed π . β
As a final note we wish to point out that this result is primarily of theoretical interest. For most practical pattern sizes, naive enumeration of π²ππΊππ and checking the treewidth individually with state-of-the-art systems for treewidth computation is feasible. The bottleneck in practice is the size of the pattern, as enumerating the contents of π²ππΊππ via naive methods, e.g., enumerating all partitions, becomes challenging above 11 vertices (see Sequence A000110 in the On-Line Encyclopedia of Integer Sequences (OEIS Foundation Inc., 2023)).
Adding Labels
We finally discuss the necessary changes for labeled graphs in the above argument, from which Theorem 8 then follows immediately. By definition, treewidth of labeled graphs is unaffected by the labels. As such we can simply ignore labels in checking for minors. Where the labels make a difference however, is in the set π²ππΊππ itself. Not all loop-free quotients are homomorphic images in the labeled case, but rather we require an additional restriction.
A quotient πΊ / π will not be a homomorphic image in labeled graphs in two cases. First, if a block of π contains two vertices with different vertex labels, and second, if the quotient would create parallel edges with different labels. To lift the previous argument to the labeled case it is therefore enough to enforce these two extra conditions in the ππ’ππ‘πππππ πΉ formulas. To this end, recall that in a satisfying interpretation of the formula, the sets π π correspond precisely to the non-trivial blocks of the quotient for which πΉ is a minor. The two extra restrictions can then be enforced simply by conjunction with the following two formulas formula inside the scope of second order quantification (where Ξ£ , Ξ are the vertex- and edge-label alphabets, respectively).
β π
1 π β π β Ξ£ β π₯ β π π β’ π π β’ ( π₯ )
(8)
Β¬ β π , π β [ π ] 2
π β π β π₯ 1 , π₯ 2 β π π β’ β π¦ 1 , π¦ 2 β π π β’ ( β πΏ , πΏ β² β Ξ
πΏ β πΏ β² ( π₯ 1 , π¦ 1 ) β πΈ πΏ β’ ( πΊ ) β§ ( π₯ 2 , π¦ 2 ) β πΈ πΏ β² β’ ( πΊ ) )
(9)
The term in 8 is easy to interpret, every block π π of the partition must have uniform vertex labels. The term 9 states that there are no two blocks π π , π π such that there are edges with two different edge labels between the blocks, i.e., it is not the case that the quotient will have parallel edges with different labels. Relation πΈ in the original definition of ππ’ππ‘πππππ can trivially be replaced by the disjunction over all edge-label relations. Thus we can easily adapt our argument above to also decide the existence of minor models in π²ππΊππ of a labeled graph.
Report Issue Report Issue for Selection Generated by L A T E xml Instructions for reporting errors
We are continuing to improve HTML versions of papers, and your feedback helps enhance accessibility and mobile support. To report errors in the HTML that will help us improve conversion and rendering, choose any of the methods listed below:
Click the "Report Issue" button. Open a report feedback form via keyboard, use "Ctrl + ?". Make a text selection and click the "Report Issue for Selection" button near your cursor. You can use Alt+Y to toggle on and Alt+Shift+Y to toggle off accessible reporting links at each section.
Our team has already identified the following issues. We appreciate your time reviewing and reporting rendering errors we may not have found yet. Your efforts will help us improve the HTML versions for all readers, because disability should not be a barrier to accessing research. Thank you for your continued support in championing open access for all.
Have a free development cycle? Help support accessibility at arXiv! Our collaborators at LaTeXML maintain a list of packages that need conversion, and welcome developer contributions.
Xet Storage Details
- Size:
- 128 kB
- Xet hash:
- 15762546a7574816e4d4a49c26d1ce7633c262cffc077e24d4fe45fcb0448bcc
Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.