Graph Neural Networks with Local Graph  Parameters
Authors: Pablo Barcelo
Floris Geerts
Juan L Reutter
Maksimilian Ryschkov
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph neural network
GNN
finite model theory
homomorphism counts

Abstract: Various recent proposals increase the distinguishing power of Graph Neural Networks (GNNs) by propagating features between k-tuples of vertices. The distinguishing power of these “higher-order” GNNs is known to be bounded by the k-dimensional Weisfeiler-Leman (WL) test, yet their O(n^k) memory requirements limit their applicability. Other proposals infuse GNNs with local higher-order graph structural information from the start, hereby inheriting the desirable O(n) memory requirement from GNNs at the cost of a one-time, possibly non-linear, preprocessing step. We propose local graph parameter enabled GNNs as a framework for studying the latter kind of approaches and precisely characterize their distinguishing power, in terms of a variant of the WL test, and in terms of the graph structural properties that they can take into account. Local graph parameters can be added to any GNN architecture, and are cheap to compute. In terms of expressive power, our proposal lies in the middle of GNNs and their higher-order counterparts. Further, we propose several techniques to aide in choosing the right local graph parameters. Our results connect GNNs with deep results in finite model theory and finite variable logics. Our experimental evaluation shows that adding local graph parameters often has a positive effect for a variety of GNNs, datasets and graph learning tasks. 


Graph Neural Networks with Local Graph Parameters
Pablo Barceló' Floris Geerts Juan Reutter!:2 Makkimiliann Ryschkov
Department of Computer Science, PUC, Chile
2 Millennium Institute for Foundational Research on Data, Chile
Department of Computer Science, University of Antwerp, Belgium
[pbarcelo.jreutter]] ding.puc.c. [floris. geerts, paksimiiian ian. ryschkovl duantwerpen. be
Abstract
Various recent proposals increase the distinguishing power of Graph Neural Net- works (GNNs) by propagating features between k-tuples of vertices. The distin- guishing power of these "higher-order" GNNs is known to be bounded by the k-dimensional Weisfeiler-Leman (WL) test, yet their (n*) memory requirements limit their applicability. Other proposals infuse GNNs with local higher-order graph structural information from the start, hereby inheriting the desirable (n) memory requirement from GNNs at the cost of a one-time, possibly non-linear, preprocess- ing step. We propose local graph parameter enabled GŇNs as a framework for studying the latter kind of approaches. We precisely characterize their distinguish- ing power, terms of variant of the WL test, and in terms of the graph structural properties that they take into account. Local graph parameters can be added to any GNN architecture, and are cheap to compute. In terms expressive power, our proposal lies in the middle of GNNs and their higher-order counterparts. Further, we propose several techniques to aid in choosing the right local graph parameters. Our results connect GNNs with deep results in finite model theory and finite vari- able logics. Our experimental evaluation shows that adding local graph parameters often has positive effect variety of GNNs, datasets and graph learning tasks.
Introduction
Context. Graph neural networks (GNNs) [Merkwirth and Lengauer, 2005, Scarselli al., 2009], and its important class of Message Passing Neural Networks (MPNNs) [Gilmer et al., 2017], are one of the most popular methods for graph learning tasks. Such MPNNs use an iterative message passing scheme, based on the adjacency structure of the underlying graph, to compute vertex (and graph) embeddings in some real Euclidean space.
The expressive (or distinguishing) power of MPNNs is, however, rather limited [Morris et al., 2019, Xu al., 2019]. Indeed, MPNNs will always identically embed vertices (graphs) when these vertices (graphs) cannot be distinguished by the one- me-dimensioonll Weisfeiler-Lemaa (WL) algorithm. Two graphs G1 and H₃ and vertices v and that cannot be distinguished by WL (and thus any MPNN) are shown in Fig. 1. The expressive power of WL is well-understood [Cai et al., 1992, Dell et al., 2018, Arvind et al., 2020] and basically can only use tree-based structural information in the graphs to distinguish vertices. Hence, no MPNN can detect that vertex in Fig. is part of 3-clique, whereas w is not. Similarly, MPNNs cannot detect that i is part of a 4-cycle, whereas not. Further limitations of WL in terms of graph properties can be found, e.g., in Arvind et al. [2020], Chen et al. [2020] and Tahmasebi and Jegelka [2020].
To remedy the weak expressive power of MPNNs, so-called higher-order MPNNs were proposed [Maron al., 2019a, Morris al., 2019, 2020], whose expressive power well-understood and
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

measured in terms of the k-dimensional WL procedures (k-WL) [Maron et al., 2019a, Chen et al., 2019a, Geerts, 2020, Sato, 2020. Azizian and Lelarge, 2021]. In a nutshell, k-WL operates on k-tuples of vertices and allows to distinguish vertices (graphs) based on structural information related to graphs of treewidth l [Dvorak, 2010, Dell et al., 2018]. By definition, WL = 1-WL. As an example, 2-WL can detect that vertex u in Fig. belongs to 3-clique or 4-cycle since both have treewidth two. While more expressive than WL, the GNNs based on k-WL require O(n²) operations in each iteration, where is the number of vertices, hereby hampering their applicability.
A more practical approach is extend the expressive power of MPNNs whilst pre- serving their (n) cost in each iteration. Various such extensions [Kipf and Welling,
w
(2)
(2)
2017, Chen et al., 2019a, Li et al., 2019, Ishiguro et al., 2020, Bouritsas et al., 2020, Geerts et al., 2021] achieve this by infusing MPNNs with local graph structural infor- mation from the start. That is, the iterative message passing scheme of MPNNs is run on vertex labels that contain quantitative in- formation about local graph structures.
(2)
G1
H1
Figure 1: Two graphs that are indistinguishable by the WL-test. The numbers between round brackets indicate how many homomorphic images of the 3-clique each vertex is involved in.
It is easy to see that such architectures can go beyond the WL test: for example. adding triangle counts to MPNNs suffices to distinguish the vertices and w and graphs G1 and H1 in Fig. 1. Moreover, the cost a single preprocessing step to count local graph parameters, thus maintaining the (n) cost in the iterations of the MPNN. While there are some partial results showing that local graph parameters increase expressive power [Bouritsas et al., 2020, Li et al., 2019], their precise expressive power and relationship to higher-order MPNNs was unknown, and there is little guidance in terms of which local parameters do help MPNNs and which ones do not. The main contribution of this paper is a precise characterization of the expressive power of MPNNs with local graph parameters and its relationship to the hierarchy of higher-order MPNNs.
Our contributions. In order to nicely formalize local graph parameters, we propose to extend vertex labels with homomorphism counts of small graph patterns." More precisely, given graphs P and G. and vertices r in P and v in G, we propose to augment the initial features of v with the number of homomorphisms from P to G that map r to v, denoted by hom( P"", G as a way to capture local structural information. More generally, homomorphism counts for a collection of graphs are considered. Indeed, we propose J-MPNNN where F = {Pi.... ...., PF) which extend MPNNs by (i) first allowing preprocessing step that labels each vertex of graph G with the vector (hom (PT, GD), G"),..., hom( PT, G))), and (ii) then run an MPNN on this labelling. Our main contributions are the following:
a set of (graph) patterns,
1. We precisely characterize the expressive power of F-MPNNs by means of an extension of WL. denoted by F-WL. This characterization gracefully extends the characterization for standard MPNNs. mentioned earlier, by setting 0, and provides insights in the expressive power of existing MPNN extensions, most notably the Graph Substructure Networks of Bouritsas et al. [2020].
2. We compare F-MPNNs to higher-order MPNNs, which are characterized in terms of the k-WL- test. On the one hand, while J-MPNNs strictly increase the expressive power of the WL-test, for any finite set J of patterns, 2-WL can distinguish graphs which J-MPNNs cannot. On the other hand, for each k 2 1 there are patterns P such that [PMMMPNNs can distinguish graphs which k-WL cannot.
3. We deal with the challenging problem of pattern selection and comparing J-MPNNs based on the patterns included in F.. We prove two partial results: one establishing when a pattern P in F is redundant, and another result indicating when P does add expressive power, based on the treewidth of P compared to the treewidth of other patterns in F..
4. Our theoretical results are complemented by experimental study in which we show that for various GNN architectures, datasets and graph learning tasks, all part of the recent benchmark by Dwivedi et al. [2020], the augmentation of initial features with homomorphism counts of graph patterns has often a positive effect, and the cost for computing these counts incurs little to no overhead.
We recall that homomorphisms adge-preserving mappings between the vertex sets.

---

As such, we believe that F-MPNNS not only provide an elegant theoretical framework for understanding local graph parameter enabled MPNNs. they are also a valuable alternative to higher-order MPNNs as a way to increase the expressive power of MPNNs. In addition, and as will be explained in Section 2, JFMMNNS provide a unifying framework for understanding the expressive power of several other existing extensions of MPNNs. Proofs of our results and further details on the relationship to existing approaches and experiments can be found in the supplementary material.
Related Work. Works related to the distinguishing power of the WL-test, MPNNs and their higher- order variants are cited throughout the paper. Beyond distinguishability GNNs are analyzed in terms of universality and generalization properties [Maron et al., 2019b, Keriven and Peyré, 2019, Chen et al., 2019b, Garg et al., 2020, Azizian and Lelarge, 2021]. local distributed algorithms [Sato et al., 2019, Loukas, 2020], randomness in features [Sato et al., 2021, Abboud et al., 2021] and using local context matrix features [Vignac et al., 2020J. Other extensions of GNNs are surveyed, e.g., in Wu et al. [2021]. Zhou et al. [2018] and Chami et al. [2021]. Related are also the Graph Homomorphism Convolutions by NT and Maehara [2020] which apply SVMs directly on a homomorphism count representation of vertices. Finally, our approach is reminiscent of graph representations by means of graphlet kernels [Shervashidze et al., 2009], but then on the level of vertices.
Limitations of our approach. One of the limitations of F-MPNNs is that their expressive power depends on the set F of patterns. Our work offers tools and guidelines to help in this search, but the best set of patterns must still be found by trial-and-error. However, as we show in Section 6, MPNNs almost always benefit from any set of additional features, assuming that the resulting model goes beyond the WL test. Cliques and cycles are two types of simple patterns that guaranteed to extend the WL test, and indeed we show that striking gains can be obtained by simply adding these features to existing benchmarks. For simplicity of exposition we focus on vertex- undirected graphs but all our results can be extended to edge-labelled directed graphs.
2 Local Graph Parameter Enabled MPNNs
We here introduce our MPNNs with local graph parameters. We first recall some graph concepts.
Graphs. We consider undirected vertex-labelled graphs G= (V, x). with V the set of vertices, E the set of edges and X a mapping assigning a label to each vertex in V. The set of neighbors of a vertex is denoted by (N( = {u E V {u, v} E E}. A rooted graph is a graph in which one of its vertices is declared as its root. We denote a rooted graph by G where E V is the root and depict them as graphs in which the root is blackened vertex, such as e.g., A Given graphs G = (Va, Ea)Xa) and H = (VHr, EH, XH), an homomorphism h is mapping h : Va + Vir such that (i) (h(w), h())) E Eu for every {u, F E Eg. and (ii) Xa = X (n(())) for every u E Va. For rooted graphs G" and H an homomorphism must additionally map v to w. We denote by hom( G, H) the number of homomorphisms from G to H; similarly for rooted graphs.
XG)
P() be set of rooted graphs, which we refer to as patterns. As a uniform formalization of local graph structural information, we propose the use of homomorphism counts of patterns in F to enhance the initial feature of vertices. To illustrate the idea, consider the graphs in Fig. 1. As mentioned, these graphs cannot be distinguished by the WL-test, and therefore cannot be distinguished by the broad class of MPNNs. If we allow a preprocessing stage, however, in which the initial labelling of every vertex e is extended with the number of (homomorphic images of) 3-cliques in which v participates (indicated by numbers between brackets in Fig. 1), then clearly vertices v and w (and the graphs G1 and H1) can be distinguished based on this extra structural information. In fact, the initial labelling already suffices for this purpose. In our setting, this will correspond to selecting the rooted 3-clique A. and attach to each vertex hom( (A. G³). Information about 4-cycles requires adding hom G*) as well.
MPNNs with local graph parameters. FP
We therefore propose F-enabled MPNNs, or just J-MPNNs, defined in the same way as MPNNs [Gilmer et al., 2017] with the crucial difference that the initial feature vector of a vertex v (a one-hot encoding of its label (c))) is augmented with all the homomorphism counts from patterns in F.
Formally, in each round d an J-MPNN M labels each vertex v in graph G with a feature vector (d) M.F.G. which is inductively defined as follows:
3

---

(0) M.v.G.,v = (xa(v), hom(Pp. .").........
"om X M.F.G..u COMB (4) ((x()_2)) E Nc())B) for 0.
x M.F.G,v. == UPD( (d-1)
where COMB (4) and UPD(4) are an aggregating and update function, respectively, as in standard MPNNs, and where { denotes a multi-set. We note that standard MPNNs are F-MPNNs with F 0. As for MPNNs, we can equip F-MPNNs with a READOUT function that aggregates all final feature vectors into single feature vector in order to classify distinguish graphs.
We remark that any MPNN architecture can be turned into am J-MPNN by a simple homomorphism counting preprocessing step. As such, we propose a generic plug-in in for large class of GNN architectures. Better still, hom(P", G") can be computed in time ([VVal (w((()))) [Díaz et al., 2002], where tw()r) denotes the treewidth of pattern p" The treewidth of patterns used in F- MPNNs is typically small. And indeed, homomorphism counts of small graph patterns can be efficiently computed in practice, even on large datasets [Zhang et al., 2020]. We also remark that the use of rooted patterns is important because different vertices in a pattern may embed differently around target vertex in a graph. For example, hom A G*) can be different from hom & G"). The choice of root in graph P can be avoided by including different rooted versions of P in F. In fact, it suffices to include one rooted version P for each vertex r in a distinct orbit in P. We note that for symmetric graphs, such cliques and cycles, all vertices lie in the same orbit and single, arbitrary, choice of root vertex suffices. Alternatively, one could define hom G*) == Erev, hom(P", G²) which ignores how the pattern is locally mapped into graph. We speculate, however, that this results in a model that is less powerful than F-MPNNs.
Despite their simplicity, we will show that F-MPNNs can substantially increase the power of MPNNs by varying F, only paying a one-time preprocessing cost.
F-MPNNs as unifying framework. An important aspect of F-MPNNs is that they allow a prin- cipled analysis of the power of existing extensions of MPNNs. For example, taking F = { suffices to capture degree-aware MPNNs [Geerts et al., 2021], such as the Graph Convolution Networks (GCNs) [Kipf and Welling, 2017], which use the degree of vertices; taking F = {Li, L2, .... Le} for rooted paths L; of length suffices to model the walk counts used in Chen et al. [2019a]; and taking& F as the set of labeled trees of depth one precisely corresponds to the use of the WL-kabelling obtained after one round by Ishiguro et al. [2020]. Furthermore, {Co) JMMPNN, where Cg denotes the cycle of length L, correspond to the extension proposed in Section 4 in Li et al. [2019].
In addition, FMMNNNs are close in spirit to the Graph Substructure Networks (GSNs) by Bouritsas et al. [2020], which use subgraph isomorphism counts of graph patterns. We recall that an isomor- phism from G H is a bijective homomorphism h from G to H which additionally satisfies (i) (u) hw)) E Eg for every {u, r} E Eн, and (ii) (a(h-((u)
(m() for every u E Vnr- When G and H are rooted graphs, isomorphisms should preserve the roots as well. Now, in a GSN, the feature vector of each vertex is augmented with the subgraph isomorphism counts, sub( Pr G for rooted patterns pr a set of P of patterns, and this is followed by the execution of an MPNN, just for our F-MPNNs. Importantly, J-MPNNs can be used to bound the expressive power of GSNs, as we will show later. We note that computing sub(P", G") is, in general, more costly than computing hom(P" OP G") [Curticapean et al., 2017]. This partially motivates our choice of using homomorphism counts instead of subgraph isomrrphism counts. Moreover, homomorphism counts of tree patterns underly existing characterizations of the expressive power of MPNNs [Dell et al., 2018, Grohe, 2020a]. As we will see shortly, these characterizations gracefully extend to J-MPNNs.
3 The Expressive Power of F-MPNNS
We next provide exact characterizations of the expressive power of F-MPNNs. Our results extend those for standard MPNNs [Xu et al., 2019, Morris et al., 2019, Dell et al., 2018].
Characterization in terms of F-WL. We bound the expressive power of J-MPNNs in terms of what we call the J-WL-test. This test extends the WL-test [Weisfeiler and Lehman, 1968, Grohe, 2017] in the same way J-MPNNs extend standard MPNNs: by including homomorphism counts

---

of patterns in F in the initial labelling. The F-WL-test, for F= (Pr...... ,P),, is a vertex labelling algorithm that iteratively computes a label GF, for each vertex v a graph G, as follows:
(d)
(0) GF = (xo(o),hom({) ())............... hom(PT, G"))
GF HASH (d-1) FFF (FF.G.u u E No())D), for d d> 0.
(d)
The F-WL-test stops in round d when no new pair of vertices are distinguished, that is, XF.G,en (d-1)
(d-1)
(d) XF.G.az implies XF.G.v, Xx,G,,y for any vertices i and 02 in G. The standard WL-test corre- sponds to (0)-WL. We can use the F-WL-test to compare vertices of the same graphs, or different graphs. We say that the F-WL-test cannol distinguish verlices if their final labels are the same, and that the F-WL-test cannot distinguissh graphs G and H if the multiset containing each label computed for G is the same as that of H. Similarly as for MPNNs and the WL-test [Xu et al., 2019, Morris et al., 2019], the F-WL-test provides an upper bound for the expressiveness of F-MPNNs.
(d)
Proposition 1. If two vertices of graph cannot be distinguished by the F-WL-test, then they cannot be distinguished by any F-MPNN either. Moreover. if two graphs cannot be distinguished by the F-WL-test, then they cannot be distinguished by any J-MPNN either.
Furthermore, simply adding local parameters from a set F of patterns to the GIN architecture of Xu et al. [2019) results in J-MPNNS that match the expressive power of the F-WL-test.
Characterization in terms of F-pattern trees. At the core of several results about the WL-test lies a characterization linking the test with homomorphism counts of (rooted) trees [Dell et al., 2018, Grohe, 2020a]. In view of the connection to MPNNs, it tells that MPNNs only quantitarive tree-based structural information from the underlying graphs. We next extend this characterization to F-WL by using homomorphism counts of so-called F F-pattern trees. Proposition 1 then reveals that J-MPNNs can use quantitative information of richer graph structures than the trees used by MPNNs.
To define F-pattem trees we need the graph join operator Given two rooted graphs GO and H the join graph (G * H)" is obtained by taking the disjoint union of G" and H", followed by
identifying w with v. The root of the join graph is v. For example, the join of do and 88 is g Furthermore, if G is a graph and pr a rooted graph, then joining vertex in G with P" results in the disjoint union of G and P", where r is identified with Let F = .Pr..... ..... }.). An F-pattemn tree I" is obtained from a standard rooted tree 5 = (V, F,,), x). called the hackhone of T", followed by joining every vertex & E V with any number of copies of patterns from F. Examples of F-pattern trees, for F = (AA) are shown in Fig. 2, where grey colored vertices are part of the backbones of the F-pattern trees. We define the depth of an F-pattern tree as the depth of its backbone. Standard trees are F-pattern trees in which no patterns are joined with backbone vertices. We next use F-pattern trees to characterize the expressive power of F-WL and thus, by Proposition of F-MPNNs.
Figure 2: Examples of F-pattern trees.
Theorem 1. For any finite collection F of patterns, vertices v and w in a graph G are indis- tinguishable by the F-WL-test if and only if hom(T", = hom(T", G") for every rooted F F-patler tree T Similarly, G and H are indistinguishuble by the J-WL-lest if and only if hom G) = hom(T, H) for every (unrvoted) F-pattern tree T.
The proof of this Theorem requires generalization of the techniques from Dell et al. [2018] and Grohe [2020a,b], used to characterize the expressiveness of WL in terms of homomorphism counts of trees. In fact, we can use our proof to recover said results simply by setting J. = Ø. We note that F-MPNNs are more expressive than MPNNs (recall the graphs G2 and H2 and JF == ))
We can even make the above theorem more precise. When F-WL is run for d rounds, then only F-patterns trees of depth d are required. This tells that increasing the number of rounds of F-WL results in that more complicated structural information is taken into account. As an illustration, consider the graphs G2 and H2 and vertices v and w shown in Fig. 3 and let us consider F-WL with F = }. J. We argue that e and w cannot be distinguished by F-WL based on the initial labelling only, but they can be distinguished after one round.
5

---

Indeed, by definition, F-WL cannot distinguish v from w based on the initial labelling since these vertices have the same triangle count (zero). Hence, no J-MPNN can distinguish these vertices either. run for one round, Theorem implies that F-WL cannot distinguish v from w if and only if hom(T", .G) = hom(T", H for any F-pattern tree of depth at most 1. is readily verified that hom 8. (..5)
hom 8:: H and thus F-WL distinguishes v from w after one round. Also, G2 and H2 can be distinguished by F-WL after one round. Moreover, G2 and H2 are indistinguishable by WL showing again that J-MPNNs are more expressive than MPNNs. The example shows that more rounds allow F-MPNNs to detect more complex patterns based on F-pattern trees. This is in contrast to, e.g.. the Graph Homomorphism Convolutions by NT and Maehara [2020] in which only homomorphism counts of patterns in F, and not the counts of the derived F-patterns trees, are taken into account.
+
22
H2
Figure 3: (60) JMMPNNs quire one round to distinguish from w.
Implications for other MPNN extensions. Importantly, Theorem I discloses the boundaries of F. MPNNs. To illustrate this for some specific instances of F-MPNNs mentioned earlier, the expressive power of degree-based MPNNs [Kipf and Welling. 2017, Geerts et al., 2021] is captured by (L1): pattern trees, and walk count MPNNs [Chen et al., 2019a] are captured by (Ir..... L3 J-pattern trees. These pattern trees are just trees, since joining paths to trees only results in bigger trees. Thus, Theorem 1 tells that all these extensions are still bounded by WL (albeit needing fewer rounds). In contrast, beyond WL, {C2] Jpattetter trees capture cycle count MPNNs [Li et al., 2019]. Our results also shed light on the expressive power of GSNs [Bouritsas et al., 2020] which, as already mentioned, use subgraph isomorphism counts of patterns P E P. More precisely, P-GSN augments vertex features by including sub(P", G") for rooted versions pr of P E: P, where ranges over representative vertices of the different orbits in P. Let us denote by P+ this set of rooted patterns.
Fact 1 (Curticapean al. [2017]). For any set P of rooted patterns, there exists pattern set s(P) such that for each P" E P. sub(P", ,G") can be computed based on {hom(Q", G*) Q" E s(P).
In other words, subgraph isomorphism counts can be computed in terms of homomorphism counts, albeit by using different pattern sets. For example, if P = (88), then s(P) = 18-- d. 8, ) which contains all different homomorphic images of 8.8 As a consequence, we obtain:
Proposition 2. P-GSNs cannot distinguish more vertices than thans(Pt)-MPNNI MMPNNs can.
So. we can bound the expressive power of GSNs in terms of J-MPNNs. In the supplementary material we also show that F-MPNNs are bounded by GSNs that use some special set of patterns derived from F. We conclude by observing that the proof technique underlying Theorem 1 can be directly applied to GSNs. The key insight is to redefine the notion of homomorphism from pattern trees to graphs. Indeed, consider a P-GSN and a corresponding P+-pattent tree T", We define shom(T", G") as the number of mappings h VT + VG such that (i) lu(r) = U; (ii) h is homomorphism when restricted to the backbone of T" and (iii) for each pr joined with backbone vertex, (P")) is isomorphic to pr, We then have the following counterpart of Theorem for GSNs:
Theorem 2. For any finite collection P of patterns, vertices u and w a graph G are indistinguish- able by PPPPPP if and only if shom (T", , G") = (TT .G") ) for every rooted P -pattern tree T". Similarly, G and H are indistinguishable by P-GSNs if and only if shom(T, G) shom (T, H) for every (unrooted) pt -pattern free T.
4 A Comparison with the k-WLttest
Compared to the computationally intensive higher-order MPNNs based on the k-WL-tests [Maron et al., 2019a, Morris et al., 2019, 2020], F-MPNNs are an alternative and efficient way to extend the expressive power of MPNNs (and thus the WL-test). In this section we situate F-WL in the k-WL hierarchy. The definition of the L-tst can be found, e.g., in Morris et al. [2020]. and is provided in the supplementary material as well. We also use the standard notion of treewidth of a graph (see e.g., Bodlaender [1993]). Intuitively, treewidth measures the tree-likeness of graph. For example, trees have treewidth one, cycles have treewidth two, and the k-clique Kg has treewidth k - 1. Furthermore, the treewidth of a pattern p" is the treewidth of its unrooted version P.

---

We have seen that F-WL can distinguish graphs that WL cannot: just consider {K3} I-L for the 3-clique K3. To generalize this observation we need some notation. Let F and G be two sets of patterns and consider an J-MPNN M and G-MPNN N. We say that M is upper bounded in expressive power by N if for any graph G, if N cannot distinguish vertices v and w, then neither can M. A similar notion is in place for pairs of graphs: if N cannot distinguish graphs G and H, then neither can M. More generally, let M be a class of F-MPNNs and N be a class of G-MPNNs. We say that the class M is upper bounded in expressive power by N if every M E .M is upper bounded in expressive power by an N E (which may depend on M). When M is upper bounded by V and vice versa, then M and N are said to have the same expressive power. A class NN is more expressive than a class M when M is upper bounded in expressive power by N, but there exist graphs that can be distinguished by MPNNs in V but not by any MPNN in M.
Our first result is a consequence of the characterization of k-WL in terms of homomorphism counts of graphs of treewidth & [Dvorak, 2010, Dell et al., 2018].
Proposition 3. For each siite set F of patterns, the expressive power of F-WL is bounded by k-WL, where k is the largest treewidth of a pattern in F.
For example, since the treewidth of Kg is 2, we have that { {K3]-WL is bounded by 2-WL. Similarly, (K++1) 1 J-WL is bounded in expressive power by k-WL.
Our second result tells how to increase the expressive power of F-WL beyond k-WL. A pattern Pr is a core if any homomorphism from P to itself is injective. For example, any clique K₁ and cycle of odd length is a core.
Theorem 3. Let F be a finite set of patterns. If F contains a pattern P which is a core and has treewidth k, then there exist graphs that can be distinguished by F-WL but not by (k= -1)-L.
In other words, for such F, F-WL is not bounded by (k- 1)- For example, since K3 is a core, J-5-WLL is not bounded in expressive power by WL = 1-WL. More generally, [K&]-W is not bounded by (k- 1)-WL. The proof of Theorem 3 is based on extending deep techniques developed in finite model theory, and that have been used to understand the expressive power of finite variable logics [Atserias et al., 2007, Bova and Chen, 2019]. This result is stronger than the one underlying the strictness of the k-WL hierarchy [Otto, 2017], which states that k-WL is strictly more expressive than (k- - 1)- Indeed, Otto [2017] (] only shows the existence of pattern pr of treewidth & such that (k= - 1)-WL is not bounded by (-W) In Theorem 3 we provide an explicit recipe for finding such a pattern p", that is, pr can be taken a core of treewidth kt
In summary, we have shown that there is a set F of patterns such that (i) F-WL can distinguish graphs which cannot be distinguished by (k: - 1)-WL, yet (ii) F-WL cannot distinguish more graphs than k-WL. This begs the question whether there is finite set F such that F-WL is equivalent in expressive power to k-WL. We answer this negatively.
Proposition 4. For any k > 1, there does not exist finite set F of patterns such that F-WL is equivalent in expressive power to k-W
In the proof of Proposition 4 we show stronger claim. Indeed, construct two graphs that can be distinguished by 2-WL but cannot be distinguished by any F-WL. Since any two graphs that can be distinguished by 2-WL can also be distinguished by k-WL, for any > 2, the proposition follows. In view of the connection between J-MPNNs and GSNs mentioned earlier, we thus show that no GSN can match the power of k-WL, which was question left open in Bouritsas et al. [2020]. We remark that if we allow F to consist of all (infmitely many) patterns of treewidth k. then F-WL is equivalent in expressive power to k-WL [Dvorak, 2010, Dell al., 2018].
5 When Do Patterns Extend Expressiveness?
Graph patterns are not learned, but must be passed as an input to MPNNs together with the graph structure. Thus, knowing which patterns work well, and which do not, is of key importance for the power of the resulting F-MPNNs. This is difficult question to answer since determining which patterns work well clearly applicationddpenneenn From a theoretical point of view, however, we can still look into interesting questions related to the problem of which patterns to choose. One such
2 As for the F--tettst, J-MPNNs cannot distinguish vertices if they are assigned the same feature vector.
7

---

a question, and the one studied in this section, is when a pattern adds expressive power over the ones that we have already selected. More formally, we study the following problem: Given a finite set F of patterns, when does adding a new pattern P to F extends the expressive power of the F-WL-tes!?
To positively answer this question, we need to find two graphs G and H, show that they indistinguishable by the F-WL-test, but show that they can be distinguished by the FU FU(PT-WW test. As an example we show that longer cycles always add expressive power.
Proposition 5. For any l > 3. (C.,...,
--W is more expressive than (Ca,-- ..... CL-1)-WL
Here. C₁ denotes cycle of length l. We also observe that, by Proposition 3, (C ,.g,..,, C,),.,,,,JWWLi is bounded by 2-WL for any 2 3 because cycles have treewidth two.
In general, it is quite challenging find two graphs and to prove that they are indistinguishable by F-WL but can be distinguished by the F F {P*) [-r-----tesst --WLttest. Instead, in this section we provide two techniques that can be used to partially answer the question posed above by only looking at properties of the sets of patterns. Our first result is for establishing when a pattern does not add expressive power given set F of patterns, and the second one when it does.
Detecting when patterns are superfluous. Our first result states that instead of choosing complex patterns that are the joins of smaller patterns, one should opt for the smaller patterns.
Proposition Let P = PT P5 be a pattern that is the join of two smaller patterns. Then for any set F of patterns, we have that FU ( [P")-WL is upper bounded by F FU
Stated differently, this means that adding to any pattern which is the join of two patterns already in F does not add expressive power. For example, instead of the pattern one should simply use the
3-clique oo. This in line with other advantages of smaller patterns: their homomorphism counts are easier to compute, and, since they are less specific, they should tend to produce less over-fitting.
Detecting when patterns add expressiveness. Joining patterns into new patterns does not give extra expressive power, but what about patterns which are not joins? We next provide useful recipe for detecting when a pattern does add expressive power. We recall that the core of a graph P is its unique (up isomorphism) induced subgraph which is both homomorphic image of P and core.
Theorem 4. Let F be finite set of patterns and let Q' be a pattern whose core has treewidth k. Then, FU J-WL is more expressive than F-WL if every pattern P E F satisfies one of the following conditions: (i) Pr has treewidth < k; or (ii) pr does not map homomorphically to Q".
As an example, [Ks....,K, J-L is more expressive than [Kg.... Ke- 1-WL for any È 3 because of the first condition. Similarly, {K3...., Ke, C. J-L is more expressive than [Ks,... ... KeL-WL for odd cycles Cm. Indeed, such cycles are cores and no clique K₂ with & > 2 maps homomorphically to C..
Experiments
We next showcase that GNN architectures benefit when homomorphism counts of patterns are added as additional vertex features. For patterns where homomorphism and subgraph isomorphism counts differ (e.g.. cycles) we compare with GSNs [Bouritsas et al., 2020]. We use the benchmark for GNNs by Dwivedi et al. [2020], as it offers a broad choice of models, datasets and graph classification tasks.
Selected GNNs. We select the best architectures from Dwivedi et al. [2020]: Graph Attention Networks (GAT) [Velickovic et al., 2018], Graph Convolutional Networks (GCN) [Kipf and Welling, 2017]. GraphSage [Hamilton et al., 2017], Gaussian Mixture Models (MoNet) [Monti et al., 2017] and GatedGCN [Bresson and Laurent, 2017]. We leave out various linear architectures such as GIN [Xu et al., 2019] as they were shown to perform poorly on the benchmark.
Learning tasks and datasets. As in Dwivedi et al. [2020] we consider (i) graph regression and the ZINC dataset [Irwin et al., 2012, Dwivedi et al., 2020]: (ii) vertex classification and the PATTERN and CLUSTER datasets [Dwivedi et al., 2020]; and (iii) link prediction and the COLLAB dataset [Hu al., 2020]. We omit graph classification: for this task, the graph datasets from Dwivedi et al. [2020] originate from image data and hence vertex neighborhoods carry little information.
8

---

Table 1: Results for the ZINC dataset.
(a) Results for the ZINC. dataset show that homomorphism (hom)
(b) The effect of different cycles for the GAT model over the ZINC dataset, using mean absolute error.
counts of eycles improve every model. We compare the mean absolute error (MAE) of each model without any homomorphism count (baseline), against the model augmented with the hom count, and with subgraph isomorphism (iso) counts of C3-Cio.
SET (F)
MAE
MODEL
MAE (BASE)
MAE (HOM)
MAE (ISO)
NONE
0.47
[Ca]
0.45
GAT 0.47=0002
0.22:10.01
0.24
{Ca]
0.34#0.02
GCN
0.35=
0.20=10.01
0.22#0.01
{C&}
0.31
GraphSage
0.44#0.01
0.24=0.01
0.24#0.01
Co}
0.28#0.01
MoNet 0.25=00001
0.19+0.01
0.16
[Ca,... Co}
0.23+0.01
GatedGCN
0.34#0.05
0.1353=0.01
0.1357+0.01
[Ca,..., C.0
0.22+0.01
Patterns. We extend the initial features of vertices with homomorphism counts of cycles C2 of length < 10, when molecular data (ZINC) is concerned, and with homomorphism counts of k-cliques KR for l 5, when social or collaboration data (PATTERN, CLUSTER, COLLAB) is concerned. We use the z-score of the logarithms of homomorphism counts to make them standard- normally distributed and comparable other features. Section tells us that all these patterns will increase expressive power (Theorem 4 and Proposition 5) and are "minimal" in the sense that they are not the join of smaller patterns (Proposition 6). Similar pattern choices were used in Bouritsas et al. [2020]. We use DISC [Zhang et al., 2020]', tool specifically built to get homomorphism counts for large graph datasets. Each model trained and tested independently using combinations of patterns.
Higher-order GNNs. We do not compare to higher-order GNNs since this was already done by Dwivedi et al. [2020]. They included ring-GNNs (which outperform 2WL-GNNs) and 3WL-GNNs in their experiments, and these were outperformed by our selected "linear" architectures. Although the increased expressive power of higher-order GNNs may be beneficial for learning, scalability and learning issues (e.g.. loss divergence) hamper their applicability [Dwivedi al., 2020]. Our approach thus certainly outperforms higher-order GNNs with respect to the benchmark.
Methodology. Graphs were divided between training/test as instructed by Dwivedi et al. [2020], and all numbers reported correspond to the test set. The reported performance is the average over four runs with different random seeds for the respective combinations of patterns in F, model and dataset. Training times were comparable the baseline of training models without any augmented features.' 4 All models for ZINC, PATTERN and COLLAB were trained on a GeForce GTX 1080 Ti GPU, for CLUSTER a Tesla V100-SXM3-32222 GPU was used.
Next we summarize our results for each learning task separately. Here we report results using 16 message-passing layers for ZINC, PATTERN, and CLUSTER, and 3 message-passing layers for COLLAB, as in Dwivedi et al. [2020]. In the supplementary material we report comparable results using only 4 layers for ZINC and PATTERN.
Graph regression. The first task of the benchmark is the prediction of the solubility of molecules in the ZINC dataset [Irwin et al., 2012, Dwivedi et al., 2020], a dataset of about 12 000 graphs of small size, each of them consisting of one particular molecule. The results in Table 1a show that each of our models indeed improves by adding homomorphism counts of cycles and the best result is obtained by considering all cycles. GSNs were applied to the ZINC dataset as well [Bouritsas al., 2020]. In Table la also report results by using subgraph isomorphism counts (as in GSNs): using homomorphism counts provides comparable results with using subgraph isomorphism counts although homomorphism counts are typically more efficient to compute. By looking at the full results, we see that some cycles are much more important than others. Table 1b shows which cycles have the greatest impact for the worft-performing baseline, GAT. Remarkably, adding homomorphism counts makes the GAT model competitive with the best performers of the benchmark.
We thank the authors for providing us with an exccutable.
*Code reproduce experiments is available at https: http://hhhhh...ooooooccccoeoe.ee

---

Table 2: Results for the PATTERN dataset show that homomorphism counts improve all models except GatedGCN. We compare weighted accuracy of each model without any homomorphism count (base- line) against the model augmented with the counts of the set J that showed best performance (best F).
MODEL BEST
ACCURACY BASELINE
ACCURACY BEST
GAT [Ka, K4, Kτ}
78.83 0.60
85.50 0.23
GCN K4, Ks}
71.42 = 1,38
82.49 = 0,48
GraphSage { (Ka, Ka, Ks}
70.78 = 0,19
85,85 = 0.15
MoNet (K3, Ks}
85.90 + 0,03
86.63 = 0.03
GatedGCN (0)
86.15 + 0.08
86.15 0.08
Table 3: All models improve the Hits@50 metric over the COLLAB dataset. We compare each model without any homomorphism count (baseline) against the model augmented with the counts of the set of patterns that showed best performance (best F).
MODEL + BEST F
HITS @50 BASELINE
HITS @ 50 BEST
GAT [Ka)
50.32.10.55
52.87110.87
GCN (Ks, K4, Ks}
$1.35.1.30
54.6011.001
GraphSage {Ko}
50.33=0.68
11.39
MoNet { {Ka)
49.81
51.76+1.38
GatedGCN {Ks}
51.00=2.554
51.57=#0.68
The next task the benchmark corresponds to vertex classification. Here analyze two datasets, PATTERN and CLUSTER [Dwivedi et al., 2020], both containing over 12 000 artificially generated graphs resembling social networks or communities. The task to predict whether vertex belongs to particular cluster pattern, and all results are measured using the accuracy of the classifier. Also here, our results show that homomorphism counts, this time of cliques, tend to improve the accuracy of models. Indeed, for the PATTERN dataset we in all models but GatedGCN (Table 2), and three models are improved the CLUSTER dataset (reported in the supplementary material). Once again, the best performer in this task is model that uses our extended features. Note that we do not need to compare against subgraph isomorphism counts (GSNs), because for cliques, homomorphism counts coincide with subgraph isomorphism counts (up to a constant factor).
Vertex classification.
improvement
Link prediction In our final task we consider single graph, COLLAB [Hu et al., 2020], with over 235 000 vertices, containing information about the collaborators in an academic network, and the task at hand to predict future collaboration. The metric used in the benchmark the Hits @its@sa 50 evaluator [Hu et al., 2020]. Here, positive collaborations are ranked among randomly sampled negative collaborations, and the metric the ratio of positive edges that are ranked at place 50 or above. Once again, homomorphism counts of cliques improve the performance of all models, see Table 3. An interesting observation is that the best set of features (cliques) does depend on the model, although the best model uses all cliques again. We do not compare against subgraph isomorphism counts (GSNs) for the same reason as mentioned above.
Remarks. The best performers in each task use homomorphism counts, in accordance with theoretical results, showing that such counts do extend the power of MPNNs. Homomorphism counts also cheap compute. For COLLAB, the largest graph in our experiments, the homomorphism counts of all patterns we used, for all vertices, could be computed by DISC [Zhang et al., 2020) in less than minutes. One important remark is that selecting the best set of features is still challenging endeavor. Our theoretical results help us streamline this search, but for now it is still an exploratory task. In our experiments we first looked adding each pattern individually, and then tried with combinations of those that showed the best improvements. This feature selection strategy incurs considerable cost and needs further investigation.
7 Conclusion
We propose J-MPNNs efficient way increase the expressive power of MPNNs and showed that enriching features with homomorphism counts of small patterns is a promising add-on to any GNN architecture. Graph parameter selection and complete characterization of when adding new pattern to F adds expressive power to the F-WL-test deserves further study.
10

---

Acknowledgments and Disclosure of Funding
The computational resources and services used in this work were provided by the HPC core facility CalcUA of the University of Antwerp, VSC (Flemish Supercomputer Center) and Imec IDLAB, funded by the Research Foundation Flanders (FWO) and the Flemish Government, This work is also partially funded by ANID -Milennnium Science Initiative Program Code ICN17_002, Chile.
References
Ralph Abboud, ismail Īlkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of the 30th International Joint Conference on Artificial Intelligence, pages 2112-2118, 2021. URL https:
//doi.org/ 10. 24963/ 11963/1jee ijcaiiicaiiiii/ Ajcai.2021/29..
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On Weisfeiler-Leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sciences, 1 113:42 59, 2020. URL https: / //wo///oi./// org/oo../.........o... org/1..1016/ 1016/j j jess. 2020. 2020.04.000 003.
Albert Atserias, Andrei A. Bulatov, and Victor Dalmau. On the power of k-consistency. In Proceedings of the 34th International Colloquium on Automata, Languages and Program- ming, volume 4596 of Lecture Notes in Computer Science, pages 279-2900 2007. URL https://don http:::///oo..o//////////
Waiss Azizian and Mare Lelarge. Expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations, 2021. URL https: /ttp:////peeeeieee//eeeee http/forummid111iggy//aaaoo
Hans L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. In
Proceedings of the 25th Anmual ACM Symposium on Theory of Computing, page 226-234 1993.
URL https: /oi. owwoooo/// 10. 1145/167088. 167161.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. In Graph Representation Learning and Beyond (GRL+) Workshop at the 37th International Conference on Machine Learning, 2020.
URL https:tpp/. arxiv org/ abs/2006....////////////022 09222020.00002.....2.2
Simone Bova and Hubie Chen. How many variables needed to express existential positive query? Theory Comput. Syst., 63(7):1573-1594, 2019. URL https://doi. http://dd..ogg/1.11101011 1007/ s00224-00 00044-018-9988 9884-2.
Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv, 2017. URL https:
//arxiv. //aaxiiv.rrg////e/ev......o...lr abs 11111777555
Jin- Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identifications. Combinutorica, 12(4):389-410, 1992. URL https://doot arg/10. 1007 FB00/B2033
Ines Chami, Sami Abu-El-Haija, Bryan Perozzi, Christopher Ré, and Kevin Murphy. Machine learning graphs: A model and comprehensive taxonomy. arXiv, 2021. URL https:
org/abs/2005. 03675.
Ting Chen, Song Bian, and Yizhou Sun. Are powerful graph neural nets necessary? dissection on graph classification. arXiv, 2019a. URL httph: org//bs//t// /905 04579.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with GNNs. In Advances Neural Information Processing Systems, volume 32, pages 158894115002, 2019b. URL httpt:://///tttt httttp:://proceeding.. cc/
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural net- works count substructures? In Advances in Neural Information Processing Syy- tems, volume 33, 2020. URI. https: /ttp://pepo......e//ee////e/./ee wwwpooceeeinnnnnuuieieeeeeeeeeee wwwripp..c/ppppeeeeee cc/papprr2000/f11
775777or711150044465/88888821112 Pater/...-aap..... pdf.

---

Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In Proceedings of the 49th Symposium on Theory of Computing, pages 210-223. 2017. URL httpthttpheee //dx..//xxx .og. org/10..//.. 1tt/111.115550 1145/3055399 .001555999005502... 3055502.
Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász meets Weisfeiler and Leman. In Proceedings of the 45th International Colloquium on Automata, Languages, and Progrumming, volume 107, pages 40:1-40:14, 2018. URL htwph:ttpps/e... /dtp:::////i../ org/10. 10. 4230/LIPIcs ICALP 2018.40.
Zdenek Dvorak. On recognizing graphs by numbers of homomorphisms. Journal of Graph Theory, 64(4):330-342, 2010. URL https: / /tt.i/oiiioooo org.oogg///.o 10. 1002/jgt. 20446......
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv, 2020. URL https://aarat /ttp///avvvvv..//av//ee////aa.l/ wwwriii.o///.....o.ooooo www.ooggg///ooooooooo/..ot....o/ abs/2003. 00982.
Josep Díaz, Maria Serna, and Dimitrios M. Thilikos. Counting H-colorings of partial k-trees. Theoretical Computer Science, 281(1):291-099, 2002. URL htttps///ooi. http://ooo..rg/////// / org/10..16/1 $0304 00077-8
Vikas K. Garg, Stefanie Jegelka, and Tommi S. Jaakkola. Generalization and representational limits of graph neural networks. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pages 3419-3430, 2020. URL BtLLhttp://ppoooooo http///pooeeeenn.e//ee////e mlr, wtt.eaaww.......e.eeeeee gaagg//200. garg20c. html.
Floris Geerts. The expressive power of kth-order invariant graph networks. arXiv, 2020, URL https://arxiv org/ abo/2007. 12035.
Floris Geerts, Filip Mazowiecki, and Guillermo A. Pérez. Let's agree to degree: Comparing graph convolutional networks in the message-passing framework. In Proceedings of the 38th International Conference on Machine Learning, 2021. URL httph:tt//aaaaee //avvvv org/ abs/ abs/2004 02593.
Justin Gilmer, Samuel Schoenholz, Patrick F, Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 1263-1272, 2017. URL http: / http:////cccee/ess.eeeoo mlr.
pttsss//7//gimmrr111 hatee///////////////// pdf.
Martin Grohe. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, Lecture Notes in Logic. Cambridge University Press, 2017. URL https:://oi..... org/ /0.
9781139028868.
Martin Grohe word2vec, node2vee, graph2vec. x2vec: Towards a theory of vector embeddings of structured data. In Proceedings of the 39th Symposium Principles of Database Systems, pages 1-16, 2020a. URL /nattps://oi..ooo /trgg/10. 10. 1..0..145//500 1145/3375395 010.///33953337411....
Martin Grohe. Counting bounded tree depth homomorphisms. In Proceedings of the 35th Symposium on Logic in Computer Science, pages 507-520, 2020b. URL https: //doi. http///i.oor///////////o./ooo.et org/ 10. 1145/
$373718.3394733 3394739.
William I.. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in Neural Information Processing Systems, volume 30, pages 1024-1034, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Information Processing Systems, volume 33, 2020. URL https: / or abs/ 2005. 00687.
John J. Irwin, Teague Sterling, Michael M. Mysinger, Erin S. Bolstad, and Ryan G. Coleman. Zine: A free tool to discover chemistry for biology. Journal of Chemical Information and Modeling, 52 (7):1757-1768, 2012. URL https:////// //doi. org/ 10. c13001273
Katsuhiko Ishiguro, Kenta Oono, and Kohei Hayashi. Weisfeiler-Lehman embedding for molecular graph neural networks. arXiv, 2020. URL https: / arxiv. org.orgg//oo. http:aas/200...0ee
12

---

Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neu- ral networks. In Advances in Neural Information Processing Systems, volume 32. pages 7092-7101, 2019. URL https: https://prooeedings..oo newrips a892666865611138866665522-
pdf.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks.
In International Conference on Learning Representations, 2017. URL
Michael Lingzhi Li, Meng Dong, Jiawei Zhou, and Alexander M. Rush. A hierarchy of graph neural networks based on learnable local features. arXiv, 2019. URL http::://axxii..oot org.abs wttp:/...rrgaa//11111... 1911. 05256.
Andreas Loukas. What graph neural networks cannot leamn: depth vs width. International Conference on Learning Representations, 2020. URL btttp:://openreveie net/ fott/foree forum?id= B112bp4YwS.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Sys- tems, volume 32, pages 2153-2164, 2019a. URL attp://papers.nip wwtpssccppppccccppppreeeepee
-aa---grrhp---eorrs...-e - 8488-provably-pont wttplly--ooorulu-eeee
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97, html.
pages 4363-4371, 2019b. URL http:://poccedeiii
mlr wttpss//v///mmaoonn
Christian Merkwirth and Thomas Lengauer. Automatic generation of complementary descriptors with molecular graph networks. J. Chem. Inf. Model., 15(5):1159-1168, 2005. URL https:
//pubs. acs org/ ht///dii//dff//// /t0f//ffff/0/// 1021/ c204//c004963b..
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning graphs and manifolds using mixture model CNNs. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5115-5124, 2017. URL https: httpss://ppeaaccess thecvf.e... com/ content_cvpr_201111111 201pp_p01//pppers Ceatti_Geomerric.c Lew.eeeeeeeaninnnccc..... 20t___aprp7ppppppppppppp
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gauray Rattan, and Martin Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pages 4602-4609, 2019, URL https://doi. http://o...ooo////// 10. 1609/ aaai. v33i01 33014602.
Christopher Morris, Gauray Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. In Advances in Neural Information Processing Systems, volume 33, 2020. URL https: : arxiv. (trgg/abs/1900 01543.
Hoang NT and Takanori Machara. Graph homomorphism convolution. In Proceedings of the 37th International Conference on Machine Learning, pages 7306-7316, 2020. URL http: //proceedings.u mlr. http://.........ee/1/1////////// gtress/v119/nguyen2200 html.
Martin Otto. Bounded Variable Logics and Counting: A Study in Finite Models, volume 9 of Lecture Notes Logic. Cambridge University Press, 2017. URL https:///ooi 1011
9781316716878.
Ryoma Sato. A survey the expressive power of graph neural networks. arXiv, 2020. URL https://arxiv. wrgg/bss//0000 04078.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural net- works for combinatorial problems. In Advances in Neural Information Processing Systems, volume 32, pages 4083-4092, 2019. URL https: http://pppppsp.ss.peee www.rrs.iis.ccc..oo httpppsccc/aape/21///il.. -apeer .df.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. Proceedings of the 2021 SIAM International Conference on Data Mining, pages 333-341, 2021. URL https: /doi. org/ 11111111111 1178
13

---

Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Trans. Neural Networks, 20 20(1):61-80, 2009, URL https://doi.... org/10. 1119/TTTNNNN 2008 2005605.
Nino Shervashidze, S.V.N. Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In Proceedings of the 12th International Conference Artificial Intelligence and Statistics, volume 5, pages 488 495, 2009. URL http://prroeeddings mlr. oata html.
Behrooz Tahmasebi and Stefanie Jegelka. Counting substructures with higher-order graph neural networks: Possibility and impossibility results. arXiv, 2020. URL https://arxiv.rt org/aba/
2012. 03174.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. URL
net/ ftd
Clément Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-passing, Advances in Neural Information Processing Systems, volume 33, 2020, URL https: https://proont //tpoceeeeoc..eeeeee/eeeeec wew.iinnnnnnnnis.eeeeee..rr neurips cc/ cc/pappr////aa// /2000 22/h//2222/hh////// / Abstract a2207eeaaa1992111191881188388833 - html.
Boris Weisfeiler and Andrei A. Lehman. reduction of a graph to canonical form and an algebra arising during this reduction. Nauchno--Techmicheskay Informatsiya, 2(9):12-16, 1968. itu..cu..........ii............. https: /www:/wwww/// itiiiiii zcu. cz http//1211//pppp httpp//////ppppppppppa.aaaaaaaaa translation. pdf.
Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-24, 2021. URL https://doi..
org/ 10. 1109 10//TNNLS...... 2020 2978386.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https:// openreview wwwnrreieewnee/Eooeee
Hao Zhang, Jeffrey Xu Yu, Yikai Zhang, Kangfei Zhao, and Hong Cheng. Distributed subgraph counting: A general approach. Proc. VLDB Endow., 13(11):2493-2555 2020. URL http:
vldb. //www. //www.vldb... orggpvllb/volll htoool11//22222hheee
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph neural networks: A review of methods and applications. ArXiv, 2018. URL http: /tarpiv///xxi...// org/abs/ 1812. 08434.
14


Reviews:
[{"review_id": "qSX4jGaJXy_", "reviewer": "Reviewer_vuNp", "summary": "- This paper proposes F-MPNN, which extends the expressive power of MPNN whilst preserving their O(n) cost in each iteration.\n- This paper provides some theoretical guarantees for F-MPNNs. \n-- It shows that F-MPNN can be at most as expressive as F-WL-test\n-- It compares the expressive power between F-WL-test and k-WL-test.\n- Certain improvements are shown in experiments.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pro:\n- It is a smart idea to utilize the design of the F-WL-test to design the F-MPNN, so that this type of GNN can enjoy the theoretical guarantee of distinguishing power as what the F-WL-test has.\n- This method is less expensive than some higher-order MPNN in terms of the complexity in each iteration.\n\nCons:\n- The proofs heavily depend on existing works but are not suitably mentioned in the main text. I think it is totally fine to make a statement in the main text because a novel combination of existing proof techniques is also valuable.\n- As already mentioned by the authors, in practice it is hard to pre-select a suitable set of patterns since they cannot be learned by gradients. The theoretical results in Sec 4 do provide certain information but they are not enough to serve as practical guidance since the search space is just way too large.\n- Experiments can be conducted more rigorously (see below).\n\nDetailed questions for experiments:\n- By adding the patterns, the dimension of the augmented node features will become larger and the model will contain more parameters. When making the comparison, have all models used the same feature dimension and the same number of parameters? This should be controlled to exclude the effect of using a larger model. (e.g., the results in Table 1 (b))\n- The key baseline in this paper is the ISO in Table 1 (a). Why results of ISO are missing in Table 2 and Table 3? If one also searches the best performing pattern for ISO using the same computing cost as the search for F-MPNN, what will be the best performing accuracy for ISO on PATTERN and COLLAB?\n- Except for ISO, there are several other works that also augment the initial feature with precomputed node features. Some simple ones include random feature [1], port numbering / weak-coloring feature [2], local matrix feature [3]. I noticed that these three are also cited in related work. It will be better to see a comparison to these simple augmented approaches.\n- Minor question: The hyperparameters of the GNNs are not described. What's the hidden size? Number of hops? Will different choices of these hyperparameters affect the improvement from augmenting the features?\n\nOther question:\n- Although it is a one-time preprocessing stage, how is the complexity?\n\nSummary:\n- This paper provides theoretical guarantees for the proposed F-MPNN in its distinguishing power, which is valuable. However, since the theory is insufficient to provide practical guidance for choosing a suitable set of F patterns, I think the empirical experiments become important to support the claims in this paper. Therefore, my main concern is that the experiments are not convincing enough (see details above).\n\n[1] Sato,  R.,  Yamada,  M.,  and  Kashima,  H. Random features strengthen graph neural networks.arXiv preprintarXiv:2002.03155, 2020.\n\n[2] Sato, R., Yamada, M., and Kashima, H. Approximation ratios of graph neural networks for combinatorial problems.In Advances in Neural Information Processing Systems, pp. 4081–4090, 2019.\n\n[3] Vignac, Clément, Andreas Loukas, and Pascal Frossard. \"Building powerful and equivariant graph neural networks with structural message-passing.\" NeurIPS. 2020.\n\n\n\n**After reading the response**\n\nThank the authors for the detailed response! I appreciate the theoretical contribution of this paper, but I still have concerns about its practical usage, without the experimental comparison to other augmented GNN models. The authors claimed that this method can extend any existing GNNs, including those augmented GNNs. However, although the paper has theoretically shown the improvement in expressiveness compared to MPNN, the improvement to existing *augmented* MPNNs [1,2,3] are unclear, which will require additional experiments to verify. Moreover, these augmented GNNs [1,2,3] and some other alternatives that use distance-based features are less expensive (pre-processing) and do not require choosing the patterns (that means fewer tuning parameters). How useful is the proposed method compared to these **simpler** methods (which also have theoretical guarantees) is unclear. This is the major reason why I choose to retain my initial score. I personally believe this will be a very nice paper if additional experiments with convincing results are provided.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "O7kk84cNpCi", "reviewer": "Reviewer_pwMn", "summary": "This paper proposes a novel GNN framework, F-MPNN, to efficiently increase the expressive power of MPNNs. The proposed framework uses local higher-order graph parameters which are the homomorphism counts of small patterns (graph sets). The adoption of different patterns will result in different MPNNs. \n\nFrom a theoretical perspective, the expressive power of F-MPNN is characterized based on the WL algorithm, and is compared to higher-order MPNNs. Since the performance of F-MPNN depends on the selection of patterns, how different patterns affect the expressive power is also investigated.\n\nThe theoretical findings are further validated via extensive experiments with various GNNs, datasets, and graph-related tasks. The results demonstrate the promising improvements achieved by using the proposed efficient local graph parameters. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed framework successfully unifies several existing extensions of MPNNs with solid theoretical analysis. The connections and comparisons between the proposed F-MPNNs and higher-order MPNNs characterize the expressive power of related models with more insights and details. Besides, the effects of different selection of patterns on the expressive power are also investigated, which helps to better understand the power of the proposed model. \n\nThe experiments are done with broad coverage of models, datasets, and tasks to evaluate the performance of the proposed method. The results are discussed in detail and the promising performance of the proposed methods is validated clearly.\n\nThe paper is overall well organized. However, the authors should double-check the grammar if accepted:\n\nLine 14: aide --> aid\n\nLine 17: effect for --> effect on\n\nLine 161: the the --> the\n\nLine 221: in that more --> in more\n\nLine 222: be distinguish --> be distinguished\n\nLine 230: less rounds --> fewer rounds\n\nLine 368: have greatest impact for --> have the greatest impact on\n\nLine 401: deserves --> deserve\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitations of their work in Introduction.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "K2fsBXjbyxr", "reviewer": "Reviewer_t8ms", "summary": "This paper proposes local graph parameter enabled GNNs as a framework for studying the local higher-order graph structural information. Local graph parameters can be added to any GNN architecture, and are cheap to compute. In terms of expressive power, their proposal lies in the middle of GNNs and their higher-order counterparts. Further, they propose several techniques to aide in choosing the right local graph parameters. The experimental evaluation shows that adding local graph parameters often has a positive effect for a variety of GNNs, datasets and grpah learning tasks. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "For the main part, as a resubmission from ICML, this work fixed the issues as they mentioned in the last submission. The overall quality of the current version is solid and it can deliver  the main idea of F-MPNN method. And this work can inherit the merits from arbitrary GNNs which makes the value of this method more general\n\nFor the minor part, this work still has typos and need further proof-read. For example, P2 line 51. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, this work mentions the limitations in the main paragraph", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Bq49a6zwY1", "reviewer": "Reviewer_wpY3", "summary": "This paper provides a theoretical framework attempting to unify a variety of recent methods in the Graph Neural Network literature, which all follow a similar conceptual approach: they introduce extra structural features in the input of the Neural Network that cannot be computed by traditional message passing. The main formalism underlying the framework is that of homomorphism, which is an adjacency-preserving mapping between two graphs. Differently from subgraph isomorphism, homomorphisms are not necessarily bijective (think of walks vs paths).  The authors define $\\mathcal{F}$-MPNNs as a message passing framework where node features are enhanced with the homomorphism counts of every pattern in a collection $\\mathcal{F}$. The authors derive a deep characterization of the expressive power of $\\mathcal{F}$-MPNNs, both in comparison to the k-WL hierarchy and between different instantiations thereof,  show how it can incorporate other approaches, and answer numerous research questions that have been left open by the most related paper, that of Bouritsas et al., arxiv’20. The method is also validated experimentally, by enhancing GNNs with homomorphism counts of cycles and cliques, on node, edge and graph level tasks, showing consistent improvement against various conventional MPNN counterparts.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Although injecting structural features in the input of GNNs is common in the GNN community, usually, the theoretical justifications are limited in showing improvements over the 1-WL, while sometimes the structural features are chosen in an ad-hoc way. However, this paper goes much deeper in the theoretical justifications showing that homomorphisms allow a more accurate characterisation of expressivity, while most importantly, using the observation that different types of subgraph counting (motifs, graphlets, homomorphisms…) can be derived from one another via linear combinations (e.g., see  Borgs et al., “Counting Graph Homomorphisms” Topics in Discrete Mathematics, 2006), they motivate why homomorphisms can be an elegant and unifying framework.\n\nI must admit that it is a bit hard to follow for non-experts due to the utilisation of many specialised notions in graph theory, so there is room for improvement in that respect. Specific comments follow:\n\n**Strengths**:\n\n- I found this paper quite useful to the community, bringing important ideas from graph theory to graph neural networks, and shedding light on many open questions in the expressive power of this class of GNNs. I also appreciate the fact that the authors are honest w.r.t. the main limitation of the work, i.e. the pattern selection.\n- The paper addresses a number of open research questions described in GSNs (although not directly applicable to GSNs, the corresponding results on $\\mathcal{F}$-MPNNs provide important insights to the reader):  \n     - How do substructure-enabled MPNNs relate to k-WL (Proposition 2 and 3)?\n     - What type of patterns grant F-MPNNs the ability to distinguish graphs that k-WL cannot (cores of treewidth k – Theorem 2; this is in agreement with the 4-clique counterexample used in the GSN paper)? \n     - In which cases can we be sure that expressivity increases when adding patterns to the collection (Propositions 4,5 and Theorem 3)? Moreover, Proposition 5 implies a compositionality property of certain patterns, i.e., when two patterns $P_1$, $P_2$ are added to the collection, expressivity increases more than by simply adding their composition $P_{1,2}$. I am still not sure though if this implies that a $\\\\{P_1, P_2\\\\}$-MPNN can count $P_{1,2}$ homomorphisms.\n-\tThe experimental results are diverse, spanning all types of graph-related problems, showing consistent improvement against the conventional MPNN baselines.\n\n\n**Weaknesses**:\n-\tIn my opinion, the paper is a bit hard to follow. Although this is expected when discussing more involved concepts, I think it would be beneficial for the exposition of the manuscript and in order to reach a larger audience, to try to make it more didactic. Some suggestions: \n    -\tA visualization showing a counting of homomorphisms vs subgraph isomorphism counting.\n    - It might be a good idea to include a formal or intuitive definition of the treewidth since it is central to all the proofs in the paper.\n    - The authors define rooted patterns (in a similar way to the orbit counting in GSN), but do not elaborate on why it is important for the patterns to be rooted, neither how they choose the roots. A brief discussion is expected, or if non-rooted patterns are sufficient, it might be better for the sake of exposition to discuss this case only in the supplementary material.\n-\tThe authors do not adequately discuss the computational complexity of counting homomorphisms. They make brief statements (e.g., L 145 “Better still, homomorphism counts of small graph patterns can be efficiently computed even on large datasets”), but I think it will be beneficial for the paper to explicitly add the upper bounds of counting and potentially elaborate on empirical runtimes.\n-\tComparison with GSN: The authors mention in section 2 that F-MPNNs are a unifying framework that includes GSNs. In my perspective, given that GSN is a quite similar framework to this work, this is an important claim that should be more formally stated. In particular, as shown by Curticapean et al., 2017, in order to obtain isomorphism counts of a pattern P, one needs not only to compute P-homomorphisms, but also those of the graphs that arise when doing “non-edge contractions” (the spasm of P). Hence a spasm(P)-MPNN would require one extra layer to simulate a P-GSN. I think formally stating this will give the interested reader intuition on the expressive power of GSNs, albeit not an exact characterisation (we can only say that P-GSN is at most as powerful as a spasm(P)-MPNN but we cannot exactly characterise it; is that correct?)\n-\tAlso, since the concept of homomorphisms is not entirely new in graph ML, a more elaborate comparison with the paper by NT and Maehara, “Graph Homomorphism Convolution”, ICML’20 would be beneficial. This paper can be perceived as the kernel analogue to F-MPNNs. Moreover, in this paper, a universality result is provided, which might turn out to be beneficial for the authors as well.\n\n\n\n**Additional comments**:\n- I think that something is missing from Proposition 3. In particular, if I understood correctly the proof is based on the fact that we can always construct a counterexample such that F-MPNNs will not be equally strong to 2-WL (which by the way is a stronger claim). However, if the graphs are of bounded size, a counterexample is not guaranteed to exist (this would imply that the reconstruction conjecture is false). Maybe it would help to mention in Proposition 3 that graphs are of unbounded size?  \n-\tMoreover, there is a detail in the proof of Proposition 3 that I am not sure that it’s that obvious. I understand why the subgraph counts of $C_{m+1}$ are unequal between the two compared graphs, but I am not sure why this is also true for homomorphism counts.\n-\tTheorem 3: The definition of the core of a graph is unclear to me (e.g., what if P contains cliques of multiple sizes?)\n-\tIn the appendix, the authors mention they used 16 layers for their dataset. That is an unusually large number of layers for GNNs. Could the authors comment on this choice?\n-\tIn the same context as above, the experiments on the ZINC benchmark are usually performed with either ~100K or 500K parameters. Although I doubt that changing the number of parameters will lead to a dramatic change in performance, I suggest that the authors repeat their experiments, simply for consistency with the baselines.\n-\tThe method of Bouritsas et al., arxiv’20 is called “Graph Substructure Networks” (instead of “Structure”). I encourage the authors to correct this.\n\n-------\n-------\n### After rebuttal\n\nThe authors have adequately addressed all my concerns. Enhancing MPNNs with structural features is a family of well-performing techniques that have recently gained traction. This paper introduces a unifying framework, in the context of which many open theoretical questions can be answered, hence significantly improving our understanding. Therefore, I will keep my initial recommendation and vote for acceptance. Please see my comment below for my final suggestions which, along with some improvements on the presentation, I hope will increase the impact of the paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "*Limitations*: The limitations are clearly stated in section 1, by mainly referring to the fact that the patterns need to be selected by hand. I would also add a discussion on the computational complexity of homomorphism counting.\n\n*Negative societal impact*: A satisfactory discussion is included in the end of the experimental section.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper unifies several classes of recently proposed graph neural network architectures via the notion of graph homomorphisms. The reviewers agree that presented theoretical framework is novel. Even more importantly, it can be successfully applied to propose new GNN architectures. The paper is well written and provides rigorous mathematical analysis of several GNN methods that were previously analyzed only empirically.
Decision: Accept (Poster)