On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters

Even though it is in scope for GNN-related venues and particularly ICLR, it is not all that clear that ICLR is where this paper would actually find its interested readership.

We believe that our findings hold important implications for both the theoretical underpinnings and practical applications of GNNs, although we acknowledge that we may not have conveyed these implications explicitly enough. Primarily, owing to well-established connections between GNNs and the WL test, our results establish upper bounds on the capacity of GNNs to count subgraphs. Furthermore, as we have mentioned in our response to Reviewer 2nvm, we posit that our results can serve as valuable insights for the development of novel GNN architectures capable of capturing specific graph motif parameters. Presenting our results at ICLR can provide us with a valuable chance to engage in direct conversations about the theoretical and practical implications of our work with the people involved in designing GNN architectures. This primary motivation is the driving force behind our decision to submit our work to this conference.

I am not convinced so much with the novelty of results, especially in light of the recent results such as Neuen (2023). [...]

Please see our reply to Reviewer 2nvm, for a discussion of some of the key technical differences regarding Neuen (2023) specifically.

Comment: Typically in homomorphism literature, a "labeled graph" refers to a graph with certain vertices marked with labels 1,...,k. [...]

Thank you very much for the suggestion. We indeed already make this remark in the appendix since we actually also use the notion described in the comment (although renamed to k-marked to avoid a clash of terms). But we agree that the potential for confusion is high and that this should be clarified already in the main body of the paper.

Thanks for the answer: I have upgraded my rating from Marginally Below (5) to Marginally Above (6).

I hope the authors will address the novelty aspects (differences to existing results) in their introduction more clearly. Considering the lack of experimental work/applications, I suggest that the authors should exactly pinpoint the relevance of their results to the GNN community in a separate paragraph within the introduction.

The novelty of this work isn't clear to me. While the extension to labeled graphs is well-motivated, the results and techniques seem to be obtained by simple / straightforward extensions of recent work for unlabeled graphs. Can you describe what the key roadblocks and innovations are in this setting? This would make it easier to judge the contributions of this work.

On a technical level the extension is not as straightforward as it seems in the high-level view. From Neuen’s proof of the unlabeled case we can reuse only the fact that the property of having treewidth at most k is closed under weak oddomorphisms. However, the underlying series of results by Roberson, from which it follows that this closure implies homomorphism distinguishing closedness needs to be extended to the labeled setting.

This first requires us to adapt the construction of the CCFI graphs for the labeled case, which is non-trivial as there are multiple natural ways to generalize the unlabeled construction. In particular, in the unlabeled construction vertices are of the form (v,S) for all S that are subsets of edges incident to v s.t. S satisfies some technical property. The generalization that we describe is arguably not even the most natural candidate as it ignores the edge labels in the definition of these vertices (the labels are of course used in a later, separate, part of the construction). However, it seems necessary to choose this less natural construction from a technical perspective.

For this modified construction, we then need to reprove the key theorem of this oddomorphism framework. Notably, the main arguments are not combinatorial but instead rely on an algebraic characterization of homomorphisms into the CCFI constructions. The role of labels in this argumentation is thus less straightforward than one might expect and requires careful reproving (and subtle modifications) of a whole series of results. Furthermore, the construction of CCFI (and especially the algebraic characterisation) would be further complicated by the presence of vertex labels. We therefore technically split the argument in showing the case without vertex-labels, and then reducing the general labeled case to this case with only edge labels.

In addition to this technical development which takes up a significant part of the technical appendix, Lemmas 4 and 5 also need to be lifted to their labeled version, which require different techniques (for Lemma 4 this is considered folklore in the context of parameterised counting, but the reasoning is not easily accessible to the intended audience of this paper). The arguments for Lemma 7 do not immediately build on any closely related results.

Finally we believe that the Theorem 8 and Proposition 9 serve as illustrations for why we believe that this work serves as an important foundational contribution to the study of GNN expressiveness. Linking GNNs to recent work in counting complexity via the framework of graph motif parameters allows for relatively simple proofs of a notable open problem in the area (Thm 8), as well as an expressivity question that seemed entirely out of reach with previous methods (Prop 9).

Due to the comment character limit we will adress the question regarding the key technical roadblocks in a separate comment.

What are the implications for GNN design for various tasks, based on the results in your paper? These are only hinted at, but given the audience of this paper, it would be worthwhile to have some discussion about it.

Thank you for the suggestion. We agree that the paper would benefit from some further discussion of this point. We see the implications on two levels. High-level, our results resolve many questions around the theoretical limits of what can be expressed by GNNs. On a more concrete level, we believe that our results serve as a foundation to analyze, unify and shape the increasingly popular area of GNNs that are enriched with structural information about the input graph, such as Graph Substructure Networks (Bouritsas et al., 2022) or GNNs with local graph parameters (Barceló et al., 2021). The motif parameter view can be seen as a list of pieces of information that are necessary to determine a function. It can thus allow us to precisely relate additional structural information that is injected into a GNN to the resulting change in expressivity. We will add respective discussions to the paper.

Is $hom(F_i, G)$ defined somehwere?

Yes, in the last line of the penultimate sentence of page 3. We have defined Hom(F,G) for the set of homomorphisms from F to G and homs(F,G) for the number of such homomorphisms.

In the definition of tree decomposition on page 5, [...]

Thanks! Indeed, there is a typo. It should be $u,v \in \alpha(t)$ or { $u,v$ } $\subseteq \alpha(t)$

Is there any quick intuition for why treewidth is the right determinant of the WL-dimension?

High level, the key idea is that for any graph F with treewidth k, we know that if G and H are equivalent under kWL, homs(F,G) = homs(F,H) (due to Dvořák and Dell, Grohe, Rattan). At the same time the homomorphism distinguishing closedness property of treewidth implies that this is tight, in the sense that for any k’ < k there are graphs G,H that are k’WL equivalent but homs(F,G) \neq homs(F,H).

For the first statement, the intuition is that kWL equivalence means (oversimplified) that the local view of at most (k+1) nodes at a time are the same in G and H. This means that in a tree decomposition for F, the possible local assignments of each bag for G and for H will be isomorphic. Since these local assignments in a decomposition determine the homomorphisms from F, the number will be the same.

For the second statement we are unfortunately not aware of any convincing intuition. The argument is highly technical and relies on the combination of a number of elements that are already individually difficult to grasp intuitively (e.g., oddomorphisms, the algebraic characterisation of homomorphism mentioned above).

Perhaps results from permutation-invariant function representation can be used to give a simpler proof of Theorem 6? It is known that multiset functions can be sum-decomposed in certain situations.. This motivates the common form of "readout" functions in GNNs, i.e. permutation invariant functions mapping from-tuple representations to a single representation for the graph. In fact, from previous work I would already expect to see a result like yours; it is unclear whether your result is useful for practical GNNs, since one would already build a readout function in this form.

This is an interesting idea, but we are not in the position to provide a definite answer regarding its pertinence at the moment. About previous work: The only result we are aware of that relates to the task of counting the number of appearances of a pattern inside a graph is one given by Chen et al in the paper “Can graph neural networks count substructures?”. It is shown in such a paper that a GNN that performs local relational pooling over neighborhoods of the given graph G of radius at most the radius of the pattern p can count the number of occurrences of p in G. Our result is slightly different, as it shows that if the support of p only contains graphs of treewidth k then the number of occurrences of p in a graph G can be obtained from the result of a standard pooling function that counts the number of tuples of each color in the result of the WL test over G.