$\mathscr{N}$-WL: A New Hierarchy of Expressivity for Graph Neural Networks
Authors: Qing Wang
Dillon Ze Chen
Asiri Wijesinghe
Shouheng Li
Muhammad Farhan
Venue: ICLR 2023 poster (2023)
Keywords: Graph neural network
Weisfeiler-Lehman algorithm
k-WL hierarchy
graph classification

Abstract: The expressive power of Graph Neural Networks (GNNs) is fundamental for understanding their capabilities and  limitations, i.e., what graph properties can or cannot be learnt by a GNN. Since standard GNNs have been characterised to be upper-bounded by the Weisfeiler-Lehman (1-WL) algorithm, recent attempts concentrated on developing more expressive GNNs in terms of the $k$-WL hierarchy, a well-established framework for graph isormorphism tests. In this work we show that, contrary to the widely accepted view, the $k$-WL hierarchy is not well-suited for measuring expressive GNNs. This is due to limitations that are inherent to high-dimensional WL algorithms such as the lack of a natural interpretation and high computational costs, which makes it difficult to draw any firm conclusions about the expressive power of GNNs beyond 1-WL. Thus, we propose a novel hierarchy of graph isomorphism tests, namely Neighbourhood WL ($\mathscr{N}$-WL), and also establish a new theorem on the equivalence of expressivity between induced connected subgraphs and induced subgraphs within this hierarchy. Further, we design a GNN model upon $\mathscr{N}$-WL, Graph Neighbourhood Neural Network (G3N), and empirically verify its expressive power on synthetic and real-world benchmarks.

Published as a conference paper at ICLR 2023
N A NEW HIERARCHY OF EXPRESSIVITY FOR GRAPH NEURAL NETWORKS
Qing Wang, Dillon Chen, Asiri Wijesinghe, Shouheng Li, Muhammad Farhan School of Computing, Australian National University {qing. wang, di dillon. chen2, asiri wrijesinghe ) (anu. edu. au shouheng. 1i, muhammad. farhan (anu. edu. au
ABSTRACT
The expressive power of Graph Neural Networks (GNNs) is fundamental for understanding their capabilities and limitations, i.c., what graph properties can cannot be learnt by GNN. Since standard GNNs have been characterised be upper-bounded by the Weisfeiler-Lehman (1-WL) algorithm, recent attempts concentrated developing more expressive GNNs in terms of the k-WL hierarchy, a well-established framework for graph isormorphism tests. In this work we show well-suited
that, contrary the widely accepted view, the k-WL hierarchy for measuring expressive GNNs. This is due to limitations that are inherent to high- dimensional WL algorithms such as the lack of natural interpretation and high computational costs, which makes it difficult to draw any firm conclusions about the expressive power of GNNs beyond 1- Thus, we propose a novel hierarchy of graph isomorphism tests, namely Neighbourhood WL. (WW-WL), and also establish a new theorem on the equivalence of expressivity between induced connected subgraphs and induced subgraphs within this hierarchy. Further, design a GNN model upon .N -WL, Graph Neighbourhood Neural Network (G3N), and empirically verify its expressive power synthetic and real- worldwrrld benchmarks.
INTRODUCTION
Graph-theoretic algorithms are powerful source of inspiration for Graph Neural Networks (GNNs).
The most known that the expressive power of standard GNNs is bounded by the Weisfeiler-
Lehman (1-WL) algorithm (Weisfeiler & Leman 1968 Xu et al. 2019: Morris et al. 2019). In
pursuit of more expressive GNNs, various attempts have been made to leverage existing results in graph theory such high-dimensional WL algorithms (Azizian & Lelarge 2021 Maron et al. 2019a Morris et al. 2020b), substructure counting (Bouritsas et al. [022] Barceló et al. [2021). and individualisation (Dupty al. 2022). The expressivity of these GNNs is measured in terms of the k-WL hierarchy, a well-established framework for graph isomorphism testing (Grohe 2017).
However, the k-WL hierarchy exhibits several theoretical and practical limitations expressivity for GNNs. Theoretically. is a highly non-trivial problem to tell if and when k- algorithms can distinguish two particular graphs (Kiefer 2020). Deciding which graph properties are important for distinguishing graphs is even much harder, if not impossible. A complete description of all subgraph patterns whose counts and occurrence are k-WL invariant only available for k 1 Arvind et al.) 2020). Even bearing high computational costs, the power of k- WL algorithms in recognising graph properties seems still limited and some negative results are known, e.g., 3- WI. cannot identify any k-cliques with k > 3 (Fürer) 2017). These issues hamper the practical applicability of high-dimensional WI. algorithms for solving real-world tasks on graph-structured data (Chen et al., [2200] Garg al. 2020). A question that arises from this is Whether the k- k-WL hierarchy is a good yardstick for expressivity of GNNs?
measure of
In the search for answer to this question, we observe several disparities between (standard) GNNs and the k-WL hierarchy. First, GNNs encode structural information into nodes as an efficient and practical way for graph learning. This is however against the spirit of the k-WL hierarchy which increases expressive power by going up to higher order objects, i..., k-tuples, rather than just nodes (Cai al. 1992 Grohe 2017). Second, GNNs are built upon natural notion of local

---

Published as a conference paper at ICLR 2023
neighbourhood, i.e., within certain distance node. In contrast, the k-WL hierarchy defines the neighbourhood of k-tuple based on "adjacency". This notion of adjacency involves the enumeration of all nodes of a graph in each dimension, which is not local and raises concerns about computational efficiency (Morris et al. 2020b). Last but not least, GNNs learn node representations by aggregating the information from its neighbouring nodes, assuming "birds of a feather flock together" from real-world perception (Zuu et al. 2020; McPherson et al. (001). The k-WL hierarchy updates the representation of k-tuple by aggregating the information from its adjacent neighbours, which does not have a natural interpretation and thus makes it difficult to understand its real-world implications.
In light of these observations, we explore hierarchy of expressivity that is grounded on new class of graph iso- morphism algorithms, called Neighbourhood WI. -WL) algorithms. This hierarchy overcomes the aforementioned limits of the k-WI. hierarchy. More importantly, it enables a new paradigm for designing expressive GNNs while still re- maining intuitive and computational efficient. We integrate the following novel insights into the algorithmic design of this hierarchy: (1) Instead of imposing a rigid condition that both objects and its neighbours use the same structure (e.g., k-tuple and its variants), why can we not separate them by colouring nodes
312
186
4
20
3
I-WL indistinguishable pairs
2
lower-dimensional space based on information from induced subgraphs in high-dimensional space? (2) Can we build hierarchy of expressivity for GNNs upon a natural choice about neighbourhood, i.e., d- hop neighbourhood? On one hand, this ensures the locality of neighbourhood and thus brings in computational effi- ciency; on the other hand, it allows high-dimensional neigh- bours to capture intricate graph properties into node representations for distinguishing graphs. (3) Unlike the k-WL hicrarchy which increases expressivity only through one dimension k. the hierarchy in our work enables two independent ways of controlling expressive power: the size t of induced subgraphs and the size of neighbourhoods, i.e., enumerating all subgraphs of order within d-hop neighbourhood. This helps strike a balance between computational complexity and expressivity of algorithms, which is often highly sought by real-world applications.
2
3
4
5
6
1
Figure 1: Indistinguishable pairs of simple graphs of eight vertices by 1- WL, which are distinguishable by N- WL under different d and t values.
Figure shows pairs of simple graphs of eight vertices that are indistinguishable by 1-WL but be distinguished by our proposed hierarchy -WL under different and parameters. By the k- hierarehy, we only know that 312 pairs of simple graphs lie between 1-WL and 3-WL as none of them can be distinguished by 1-WL but all of them can be distinguished by 3-WL. Rather than "None" or "All", our -WL hierarchy can distinguish these graphs in a more refined way under varied f and d values, i.e., each point (t, d) in Figurr 1 indicates the number of pairs of simple graphs that remain indistinguishable under these parameters, and all pairs are distinguishable when t 2 3 and d 2 2. Further details and example graphs are provided in Appendix A
With a hierarchy of expressivity, is natural to ask whether the hierarchy is strict. We thus further explore whether the ./' -WI hierarchy is strictly more expressive when considering induced subgraphs or neighbourhoods of larger sizes. To show the strictness, we construct counterexample graphs such that, for any fixed d N and every & E N, there exist non-isomorphic graphs which -L with (t, d) fails to distinguish but can be distinguished by -WL with (t+1, d); on the other hand, for any fixed t N and every d N, there also exist non-isomorphic graphs which -WWL with (t, d) fails to distinguish but can be distinguished by -WL with (t,, d+1). 1). Not surprisingly. constructing such counterexample graphs turns out to be difficult, due to the intricate interaction between / and d as well as the combinatorial nature of graph structure. We present such a construction which can produce families of non- -sommoooopp graph pairs with O(t) or O(d) vertices.
To understand how graph connectivity may affect the expressivity of -WL, we go on to examine the relation between induced subgraphs and their connectivity. Inspired by the Algebra of Sub- graphs (Kocay) 1982), we discover a previously unknown connection between induced subgraphs of size f, for any t N, and induced connected subgraphs whose sizes are less than or equal to t. This surprisingly leads to the finding that these two families of subgraphs have equivalent expressive power for distinguishing graphs. Hence, when graphs are sparse, instead of considering all induced subgraphs, we may consider only induced connected subgraphs, improving efficiency considerably.
2

---

Published as a conference paper at ICLR 2023
Table 1: Comparison of k-WL and their variants 6-k-LWL Morris al. 2020b), (k, SLLWL (Morris
et al. 2022), and (k, <)(=-SSTTW (Zhao et al.) 2022a) with our algorithms N (t., d)-WL and (t, (t,d))WW W)WWL, where #Coloured objects and #Neighbour objects refer to the number of coloured objects in graph and the number of neighbour objects for each coloured object, respectively: AColoured objects and &Neighbour objects refer to the type of coloured objects and the type of neighbour objects, respectively; ri is the number of nodes and is the average node degree in a graph; at is the average number of nodes in the d-hop neighbourhood of node. Note that a < n for
graphs whose diameters are considerably greater than d.
W-WL
8-4-LWL
(k, s)-LWL
((t,d)-WL (k, SETTLL
(t,
objects
#Coloured
n*
n²
subset(n"
subset
n
n
#Neighbour
objects
n x
a
a x
n X
subset(E
A AColoured
k-tuless
k-tuples
t-tuples
S k-sets
nodes
nodes
objects
Neighbour
k-tples
k-tuples
A-tuples
S--sets
1-sets
S Lt-sets
objects
Spursity
x
aawrreness
Contributions.
The main contributions of this work are summarised below:
We introduce a new class of graph isomorphism algorithms, Neighbourhood WL -WL,, which exhibit natural and strict hierarchy of expressivity for measuring GNNs in their ability to distinguish graphs (hheorem 3.1 Theorem 3.2, and 3.3).
We establish a new theorem on the equivalence of expressivity between induced connected subgraphs and induced subgraphs in general within the hierarchy of . which enables us to further leverage graph sparsity for improving efficiency (Theorem 3.7).
We explore how the hierarchy of -WL relates the k &- hierarchy and establish their connections (Theorem 3.8).
We propose new GNN model architecture, Graph Neighbourhood Neural Network (G3N), which instantiates the ideas of the -WL algorithms for graph learning (Theorem 4.1).
2 RELATED WORK
Since the advent of Graph Neural Networks (GNNs), a central theme is to understand the expressivity of GNNs. It has been revealed that standard GNNs most expressive as the Weisfeiler-Leman (WL) algorithm (Weisteiler & Leman 1968 Xu et al. 2019 Morris et al. 2019). Ever since, the WL algorithm has played a crucial role in the theoretical studies on GNNs.
The WL hierarchy generalises the WL algorithm (1-WL) to classify k-tuples of vertices (Grohe 2017 Babai & Kucera 1979). It is known that k- is strictly more powerful than (k- for
any k 2 3. The Cai-Fürer- Immerman (CFI) construction can produce a family of non-isomorphic graph pairs as counterexamples which are indistinguishable by (k-1)-WL but can be distinguished
by k-WL (Cai et al.) 1992). Since k-WL is computationally expensive for & > 3, k-WL is mostly used as theoretical tool graph isomorphism testing and not practically useful.
Various attempts have been made in recent years to develop more expressive GNNs see survey by [Sato] (2020). Until now, the expressivity of GNNs typically measured in terms of 1-WL. However, the expressivity gap between A: = and & 3 for k- is often too large for applications in practice. On one hand, 1-WL not expressive enough since it cannot count some simple structures such eycles triangles; on the other hand, many applications may not require strong 3-WL power. There is a lack of measure for expressivity of models that lies in between 1-WL and 3- WL, as well as beyond higher-dimenssioal WL- in a more refined and natural way.
In this work, we depart from the k- WL hierarchy by proposing a new hierarchy that builds on high-order subgraphs within a neighbourhood aggregation scheme to characterise the expressivity of GNNs. Table shsows a comparison between WL and their variants and our hierarchy. A detailed discussion this comparison and other related works are provided in Appendix B
3

---

Published as a conference paper at ICLR 2023
G
G2
d=1 d=2
d=3 d
m 2
Figure 2: Two graphs distinguishable by --- (2, (2,1)-WL and N 22, but not (2,333)-
3 NEIGHBOURHOOD WL ALGORITTMM
Let G = (V, E)) be simple graph with set V of nodes and a set E of edges and | = Given node u E V, its d-hop neighbourhood is defined by Na(u) {u E V p(u, v) S d] where p(-) denotes the shortest-pathe distance between two nodes and E Na(u). The order of (sub)graph the number of its nodes. We use G1 S G2 to denote that G1 is a subgraph of G2, and G1 G2 that G1 and G2 are isomorphic, i.e., there exists bijection between their nodes which induces correspondence between their edges. Each equivalence class under = is called an isomorphism type. All the proof' for lemmas and theorems in this section are provided in Appendix C
3.1 A HIERARCHY OF EXPRESSIVITY
We begin with a simple yet weak hierarchy. This hierarchy shows that expressivity increases with the order of induced subgraphs in a neighbourhood; but counterintuitively, expressivity does not necessarily increase with the size of a neighbourhood.
Weak hierarchy. A node colouring in G is a function ç: V -> N which is refined in iterations, i.e. ('(x) for / 0, .,. m. Initially, each node u assigned with some colour (t) Then, the colour (l+1(u) is iteratively refined based on the its own colour s (u) and the colours of induced subgraphs in its neighbourhood at the /-th iteration. The colours of induced subgraphs are also defined iteratively, according to the colours of their nodes in the same iteration and connectivity of the nodes. Let Sç denote the of all induced subgraphs G and fseo : SG - N be a permutation invariant function that encodes the isomorphism types of induced subgraphs. A subgraph colouring in G at the 1-th iteration is a function ç SG N such that (S() * (S2) iff fiso(Si) # (Ss)
Given the set S(u,t.d) of all induced subgraphs of order within the d-hop neighbourhood of node u, ((u.)) (S) S ((m,.d) and fi (S)= and 4, (S)o Sw,,t we have (4+ nAsu(s (w), (e.))))e).
Here, HASH(-) is an injective hash function.
We use _V- (t, d) to denote the above algorithm with two parameters: t for the order of induced subgraphs and for the hop neighbourhood. The following thcorem can be proven.
Theorem 3.1. For any fixed d N. A (t+1, -L is strictly more expressive than N (t, -L in distinguishing non-isoo non-isomorphic graphs, where 2 1.
However, (1,d+1)-WT is not necessarily more expressive than (1,,, WLL in distinguishing non-isomorphic graphs. Figure iillustrates the problem. We observe that the source of the problem is that subgraphs are treated multisets in which their colours can be distinguished only by their isomorphism types. Thus, aggregating subgraphs from larger neighhourhood may lose information about subgraphs in the previous smaller neighbourhood.
Strong hierarchy. To alleviate the above problem, propose consider not only isomorphism types but also positional types of subgraphs. This enables us to capture relative importance of structures, even of the same isomorphism type, in neighbourhood as receptive field increases.
We define a permutation invariant function Spos Sg - N that encodes the positional types of induced subgraphs in G to satisfy the following condition for any t and any e N:
VSS S a (S(u,1,+1)) S(u.r.a)) (Spas (S.) * Spos (S,))-
2
4

---

Published as a conference paper at ICLR 2023
We also reformulate the subgraph colouring function as 5¹ Sc + N such that ('())) (52
iff (S1) = {1so(S2) (S2) and fpoz = Spos (S2). Let S(u,i,) = (S)s E ((u,td)) frso (5)=i,
and Spos (S) } and Ja = poos (S) E Stu,r,a) ). Then the node colouring in Equation is
redefined to integrate the positional types of induced subgraphs as
(1) = HASuU("(()) (u), ((ann)ieeee)))
We denote this algorithm with node colouring defined in Equation 3 as N (1, d)-WL, to distinguish it from (1,,, (4, when considering higher-order -oderr subgraphs or larger neighbourhoods.
dL- The following theorem states that the expressivity of ((,, d)- increases
Theorem 3.2. For any fixed d E N. A (t+1,, WL is strictly more expressive than .N (N,t, d)- W-- in distinguishing non-isomorphic graphs, where 2
Theorem 3.3. For any fixed e N, (t, (f.)+11-- WL is strictly more expressive than N (t, d).dd)-W in 1---1)-Wir distinguishing non-isomorphic graphs, where d 2 1.
Strictness of hierarchies. To prove the strictness of the hierarchies in Theorem 3.1 and Theorem 3.2 we need to construct a family of non-isomorphic graph pairs such that, for any fixed d E N. there exist at least two non-isomorphic graphs that are distinguishable by the colours of their nodes that are iteratively refined through counting all (+1-order induced subgraphs of different isomorphism and positional types in d-hop neighbourhoods of their nodes, but indistinguishable if considering all t-order induced subgraphs instead. Conversely, Theorem 3.3 requires to construct a family of non-isomorphic graph pairs such that, for any fixed & N. there exist at least two non-isomorphic graphs which can be distinguished by the colours of their nodes through counting all t-order induced subgraphs of different isomorphism and positional types in d--phhop neighbourhoods of their nodes, but cannot be distinguished if considering d-hop neighbourhoods of their nodes instead. We present these constructions in Appendix with illustrations in Figure 6 Figure 7 and Figure 8
Upper bound expressivity. With increasing / and values, the upper bound expressivity of (1,, d)-
WL is reached when both t and d equal to the diameter of graph. such cases, whether ./V (t, (t.d) d)-
WL can distinguish two non- non-isormorphic graphs is reduced to the classical graph isomorphism (GI) problem (Grohe & Schweitzer (020). This is because, given a graph G. each d-hop neighbourhood subgraph is the same as the graph G when d 2 dia(G', induced subgraphs of t vertices are also the same as the graph G when t 2 dia(G), where Gia refers to the diameter of G.
Note that as shown by Cai, Fürer, and Immerman in their seminal paper (Cai et al. 1992). the k-WL algorithm is incomplete in the sense that, for any k E N, there exists a pair of non-isomorphic graphs that cannot be distinguished by the k- algorithm. Similarly, in our work, the construction presented in in|Appendix C Cssows that, for any t e N and d e N, there exists a pair of non-isomorphic graphs that cannot be distinguished by M (t, dL-
3.2
HEREDTTAR SUBGRAPHS
The locality of neighbourhood restricts M d)-WI. WL. to considering only induced subgraphs that are "close" to node. This nice property helps reduce the computational complexity, compared with k- WL. Nonethelles, enumerating all induced subgraphs in a neighbourhood can still be inefficient if their order is high. Real-world applications often focus analysing connectivity of nodes in graph. For example, highly interacting proteins are more likely to form function modules (Alokshiyal et alal,,2010 2019). Thus, natural thought further reduce complexity is to consider only connected subgraphs. Following this direction, we identify connected connected-hereditary subgraphs. Surprisingly, turns out that all connected induced subgraphs with orders greater than can capture no less information than all induced subgraphs of order f. This finding leads us to improving the -WL algorithm by taking graph connectivity into consideration.
Let If C Ie be the set of isomorphism types in I, for connected subgraphs. Instead of considering all subgraphs in the neighbourhood as in [Equatio 3) we now restrict node colouring to connected subgraphs but allow the orders of connected subgraphs to range over [1,
= HASH(s((u). U (Kunnn)ersseee.)
(4)
kE[L.]
5

---

Published as a conference paper at ICLR 2023
For this algorithm with node colouring based only connected subgraphs, we denote it (t, d)- WL. Although Equation 4 might look rather restricted, we show that if two graphs G1 and G2 are distinguishable by N d)-WL, they are also distinguishable by "t, dL-WL. This is due to property of subgraphs occurring in (t,,, dI, which we elaborate below.
Let S and S be the set of all subgraphs in the d-hop neighbour- hood of a node u being considered by (t, d)-WL and (t,, (t,,),WL, respectively, and S-* the of all subgraphs of order é in S.
Definition 3.4. Let S C Sc. Then said to be comnected-hereditayy every S S is a connected induced subgraph and S E S implies that every connected induced subgraph of S is also in S.
S contains all connected induced subgraphs of k vertices with 1 < t the d-hop neighbourhood a node. We have the following lemma.
(a) Neighbourhoods Rook's 's graphs and the Shrikhande graph.
Lemma 3.5. S is connected hereedtarrrdi.rry.
Let S1 o S2 denote the union of two node-disjoint subgraphs, i.e., V(Si) ((2)) 0, and μuS) the number of connected components in S. The lemma below states that any non-connected subgraph in (S=t-S is union of number of smaller connected subgraphs in S whose nodes are disjoint to each other.
Lemma 3.6. For each induced subgraph S satisfying S E S but & Set, there exists a set (Si, S C See such that S S1 S2 o... o Sq. where p(5) q.
G2
(b) An 8-cycle and pair of disconnected 4-yycls.
The intuition is that smaller connected induced subgraphs can actually be used pieces reconstruct all the disconnected order-t induced subgraphs, without losing expressivity. Hence, based on these lemmas, can prove the following theorem that the (t, (ftt,d))W) dL algorithm is as powerful as the M ((t, dL-WL algorithm. In fact, both algorithms have the same expressivity.
Figure 3: Pairs of non- isomorphic (sub)graphs.
Theorem 3.7. For any t E N and d E N, (t, d)- and N (t, d)-WL have the same expressivity in distinguishing non-isomorphic graphs.
is worth noting that, by further restricting connected subgraphs to specific isomorphism types, we may obtain different subclasses of algorithms. For example, if limiting I, to cycles, cliques, and paths, M dL is reduced to the neighbourhood WL algorithms N eeycle (t, d)-WL. N yalique (t, d)- WL, and path (t, dd- dL, respectively, which encode structures of specific kinds from the node neighbourhoods into node colours.
3.3 CONNECTIONS TO k- WL HIERARCHY
One may arise a question with regard to how -V relates the k-WL hierarchy. Since 1-WL corresponds to node labelling based on multiset of the colours of its neighbours within a 1-hop neighbourhood, is straightforward to establish the following connection.
Theorem 3.8. . (1, 1)-WL is equivalent to 1-WL in distinguishing non-isomorphic graphs.
By Theorems 3.2 and 3.3 we know that the expressivity of Af (t, d) increases when increasing either
the order of subgraphs or the hop of a neighbourhood. This leads to the proposition below. Proposition 3.9. Both . (2, 1)-WL and (1, are strictly more powerful than 1-WL in distinguishing non-isomorphic graphs.
However, in general, the WLL hierarchy is incomparable with k-W as we notice in the nontrivial case that (3, 1) is incomparable to 3-WL. A canonical example of two non-isomorphic, strongly regular graphs which 3-WL cannot distinguish are Rook's 's graph and the Shrikhande graph. Despite being strongly regular, (3, 1)WL can distinguish them by distinguishing 3-order subgraphs in 1 h-hop node neighbourhoods in Figure 3aa). Nevertheless, (3, 1) WL fails to detect 4-cycles its receptive field is too small in contrast to 3-WL. This is seen where the former is unable to distinguish an 8-cycle from two disconnected 4-cycles in Figure 3((b) whereas 3-WL is able to distinguish them.

---

Published as a conference paper at ICLR 2023
Figure 4: An overview of a G3N layer: (a) t-order subgraphs are extracted from node's d-hop neighbourhood. (b) The subgraphs are grouped by their positional and isomorphic types. (c) The subgraphs are embedded by pooling function PoOL. (d) The subgraph embeddings are aggregated in their own topologiaal groups by AGG". (e) The resulting embedding vectors are further aggregated and combined with AGG and COMBINE: form updated node emhedding.
GRAPH NEIGHBOURHOOD NEURAL NETWORK
Motivated by the -WL algorithm, design Graph Neighhourhood Neural Network (G3N) which is able to leverage and learn structural information from neighbourhoods.
Model design. Given graph G (V, E), each node E V is associated with an f-dimensional feature vector F, E / and ()) = xu.- Let S! (i.j) denote the set of all f-order subgraphs within the d-hop neighbourhood of node with the isomorphism type and positional type j at the 1-th layer. Then at the (1+1)-thh layer the node embedding h ((+1) of a node u is defined by
1 11+1)
COMBINE (n.)) Aad (IJ))lxxJa
(Aca" ses (t.)) (i.))
(Pool((3))):
POOL(-) extracts node representations within a subgraph S as subgraph embedding which can be defined by any graph pooling method. Aggregation proceeds in two steps: AGG (-) combines subgraph embeddings of the same isomorphism and positional types and AGG combines the resulting embeddings from subgraphs the neighbourhood. COMBINE(.) combines the node embedding of node u at the previous layer with the aggregated embedding of subgraphs. Further details of the G3N model architecture are described in Appendix D
One compare Equation 5|o the node colouring of -WL described in Equation 3 where subgraph pooling corresponds to subgraph colouring, and the aggregation corresponds to the hashing of sets of multisets. We refer to G3N with given t and d by G3N-(t, d).
Expressivity analysis. G3N-(t, d) is at most as expressive as (t dL-WL. To match the expres- siveness of H (t, dL, one may insert Multi-Layer Perceptrons (MLPs) approximate injective functions as employed by Xu et al. (019). However, this comes at higher parameter complexity which may increase expressiveness but could decrease generalisability. The following theorem phrases this formally with the proof available in Appendix C
Theorem 4.1. G3N-(t, d) with injective COMBINE and AGG functions, an injective AGG" function w.r.t. multisets of subgraphs with the same isomorphism and positional types, an injective graph readout function, and sufficiently many layers is as powerful as NN .N dl-WL.
Complexity analysis. Usually, expressivity comes a cost of computational complexity and this is no exception for G3N. Let denote the average node degree of graph. Then ignoring node features embedding dimensions, standard GNNs have the complexity O(n a) while G3N has O(n (?")) per layer. Here, is a very small value, usually less than 6. Note that d < n is an average size of local d-hop neighbourhood, different from &- which considers all vertices in graph, i.e., O(n)).
7

---

Published as a conference paper at ICLR 2023
Table Graph isomorphism tasks on EXP, SR25, graph8c and CSL are evaluated by counting the pairs of graphs which are indistinguishable. Substructure counting tasks are performed on the RandomGraph dataset and evaluated by MSE.
Graph isomorphism
Substructure counting
Model
EXP
SR25
graph8c
CSL
Triangle
Tailed Tri.
Star
4-Cycle
MLP
600
105
293K
45
3.13E-1
2.22E-1
1.04
1.73E-1
GCN
600
105
4775
45
2.43E-1
1,42E-1
1.0E-4
1.14E-1
GAT
600
105
1828
45
2.47E-1
1,44E-1
1.0E-
1.12E-1
GIN
600
105
386
45
2.06E-1
1,18E-1
1.0E-
1.21E-1
PPGN
0
105
1
1.00E-4
2.61E-4
1.0E-4
3.30E-4
G3N-(2,1)
600
105
36
1.81-4
3,58E-4
6,46E-4
1,03-1
G3N-(3.1)
600
0
36
4.31E-4
4.30E-4
3,41E-4
1,14B-
G3N-(2,2)
0
105
15
6.77E-4
7.06E-4
8.63E-4
1.61E-2
G3N-(3,2)
0
10
1,55E-3
1.69E-3
4.42E-3
7,38E-3
Table 3: TU datasets evaluated by classification accuracy (%). The first 3 rows are kernel methods and the remaining are GNN models. The first and second best results are highlighted and underlined.
Model
MUTAG
PTC_MR
PROTEINS
NCT1
IMDB-B
IMDB-M
RWK
79.242.1
55.920.3
59.620.1
>3 days
WL-kernel
90.4
59.924.3
75.043.1
86.0118
73,8239
50.943.8
P-WL
90.521.3
64.020.8
75.9
85.620.3
PATCHY-SAN
92,6*4.2
60.0+4.8
75.9+28
78.6+1.9
71 71.0#22
45.2+2.8
DCNN
11.3#
$6.6+1.0
11.1
33.5
DGCNN
85, 85.8
58.6#0.0
75.5+0.9
74.4+0.5
70.020.9
47.8+0.9
GIN
89.425.6
64.627.0
76,242.8
82.7+1.7
75.1
52.34288
PPGN
90.628.7
66.2#6.6
77.224.7
83.241.1
73.0#5.8
50.5+3.6
G3N-(1,1)
99.9
63 3
73.61:5.3
82.3+5.2
73.6
51.5+2.9
G3N-(2,2)
92.0+:422
65.5#6.3
74.6#4.1
83.2
74.3+3.7
52.4+3.4
Further, we may consider only connected subgraphs when graphs are sparse. Subgraph aggregations can be conducted in parallel across all subgraphs according to their isomorphism and positional types. Computationally, is much more efficient than expressive GNNs based on k-WL.
5 EXPERIMENTS
run experiments on synthetic and real-world datasets to empirically validate the theoretical properties of G3N. For synthetic datasets, we focus on two main tasks: the graph isomorphism problem and substructure counting. As for real-world datasets, we focus on graph classification and regression molecular datasets and social networks. Details about datasets, basclines, and experimental setups, as well as additional experimental results, are available AAppeddix E
5.1 SYNTHETIC DATASETS
Serup. EXP (Abboud al. 2021) consists of 600 pairs of nonisomorphic graphs (G,, H2) each encoding a propositional formula which is either satisfiable not. The graphs are designed to be indistinguishable by 1-WL. $ (Balcilar et al. 2021) contains strongly regular graphs, each with 25 nodes and indistinguishable by 3-WL. graph8c (Balcilar et al. 2021) contains all 11,117 connected non -somioooooppic 8-node graphs, which 312 pairs are indistinguishable by 1-WL and all distinguishable by 3-WL. CSL was first introduced by Murphy al. (2019) and commonly used to test graph expressiveness (Dwivedi et al. 2020). consists of 10 isomorphism classes of node 4-regular graphs which are almost all distinguishable by 3-WL. For counting graph substructures, consider RandomGraph (Chen et al. 2020). We follow the setup described by Balcilar et al. (2021).
available http:://uers.cee anu http:///www......oooooa..aa/aaaa
8

---

Published as a conference paper at ICLR 2023
Table 4: Experiments on ZINC and MolHIV, where the performance of the methods marked by * (i.e., DEEP LRP, GSN, and CIN) is based on pre-selected subgraph patterns.
(a) ZINC evaluated by MAE
(b) MolHIV evaluated by ROC-AUC.
ZINC (no edge features)
ZINC
MolHIV (test)
MolHIV
Model
Model
(edge features)
(validation)
GCN
0.459=+0.006
0.321=0.009
GCN
0.7606+00.0977
0.8204#0.0141
PPGN
0.407=+0.028
GIN
0.7558=t0.0144
0.8232+000000
GIN
0.387=000155
0.103400004
GraphSNN
0.785 10000170
0.835920.0099
PNA
0.320=#00052
0.1884+0004
PNA
0.7905=0.0132
DGN
0.219#0.010
0. 0..08+0.003
DGN
0.7970=2.0097
DEEP LRP"
0.223#0.008
DEEP LRP*
0.7687=00.0188
0.813 +0000
GSN#
0.140:000006
0.1 15#0.0112
GSN#
0.7799=0.0100
0.8658200.084
CIN#
0.115#0.003
0.079:0.006
CIN#
0.809420.0057
(2,3
0.165=0.018
0.128*00015
G3N- (2,3)
0.790020.0134
0.835920.0011
we can see that G3N with & and d alone is already more expressive than 1-WL bounded GNNs, being able to distinguish most graph8c graphs and some CSL graphs. By increasing to we are able to distinguish PPGN is unable to. Other configurations of d and also support that -WLL is incomparable with k-WL. Looking at substructure counting tasks, G3N with t = 2 are able to trivially detect triangles but not 4-cycles. Setting
Observations. From Table
SR25 graphs which the 3-WL bounded
and d 2 allows us detect 4-cycles. Note that G3N with 2 and = 2 is unable to learn 4-cycles but is able to memorise some configurations, leading to the slightly lower error. We finally observe that for higher d and i, convergence of G3N takes longer due to its higher expressivity and low parameter budget in this setting, resulting in slighty poorer predictions.
5.2 REAL-WORLD DATASETS
Setup. ZINC (Irwin et al. 2012 contains 250K molecules of which 12K are selected for the task of regressing constrained solubility. We follow the experimental setup described in (Dwivedi et al.) 2020). MolHIV was introduced by Wu et al. (2018) as part of the MoleculeNet benchmark and has been proposed in (Hu al. 2020) be graph classification tasks. We follow the train, validation and test split from Hu et al. (2020) and evaluate on the test score corresponding to the best validation score. We further consider the bioinformatics and social network datasets from the TUDataset collection (Morris et al. 2020a). We follow the setup described in (Xu et al. 2019).
Observations. From the results collated Tables 3 and 4 G3N performs well compared with the other baselines. On ZINC. G3N performs better on learning topological features over PPGN. There exist stronger performing models on molecular datasets such as CIN (Bodnar et al. 2021a) and GSN (Bouritsas et al., 2022);; however, these methods explicitly compute cycle information which is known to be correlated with molecular classes and attributes. For example, cycle counts are used in the calculation of the regressed constrained solubility attribute of ZINC datasets (Irwin et al. (012).. Among the basclines that learn topological features without pre-selecting opplicatoo-dependee subgraph patterns, G3N performs best ZINC both with edge features and without edge features.
CONCLUSIONS
We proposed new class of graph isomorphism algorithms known as -V-WL algorithms. This class of graph isomorphism algorithms exhibits a more refined hierarchy of expressivity for distinguishing non-isomorphic graphs by focusing on approximating graph neighbourhood structures as best as possible. We further explored how to narrow our focus down to only connected subgraphs to improve efficiency while still preserving expressiveness. Motivated by -WL, proposed the G3N architecture which is provably more expressive than vanilla cressage-passingg neural networks and is able to leverage graph structure more effectively for prediction tasks.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We are thankful to Professor Brendan Mckay for helpful discussions and feedback. We gratefully acknowledge the support of the Australian Research Council under Discovery Project DP210102273. We also would like to thank anonymous reviewers for their comments and suggestions which helped improve the quality of the paper.
REPRODUCIBILITY STATEMENT
To ensure reproducibility of the theoretical and empirical results included in this work, we have made the following efforts: (1) For theoretical results, the complete proofs for lemmas and theorems are
provided in Appendix G (2) Details the model architecture and the implementation are included in Appendix D (3) Experimental details, including datasets, baseline methods, hyperparameter selection, and additional experimental results, are provided in Appendix E] (4) The code is available at htttt:::///// http::://ggtttuuu..o wtt.://..ooo/aaaa1/13133333 133/GNN
REFERENCES
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In International Joint Conference on Artificial Intelligence (IJCAI), 2021.
Sami Abu-EI-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional ar- chitectures via sparsified neighborhood mixing. In International Conference on Machine Learning (ICML), pp. 21-29, 2019.
Mohammed Alokshiya, Saeed Salem, and Fidaa Abed. A linear delay algorithm for enumerating all connected induced subgraphs. BMC bioinformatics, 20(12):1-11, 2019.
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On weisfeiler--emme invariance: Subgraph counts and related graph properties. Journal of Computer and System Sciences, 113:42-59, 2020.
James Atwood and Don Towsley. Diffussin--oonvoluttinnal neural networks. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1993-2001, 2016.
Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations (ICLR), 2021.
László Babai and Ludik Kucera. Canonical labelling of graphs in linear average time. In Annual Symposium on Foundations of Computer Science (SFCS), pp. 39-46, 1979.
Muhammet Balcilar, Pierre Héroux, Benoit Gaüzère, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In International Conference on Machine Learning (ICML), volume 139, pp. 599-608, 2021. 2021.
Pablo Barceló, Floris Geerts, Juan Reutter, and Maksimilian Ryschkov. Graph neural networks with local graph parameters. Neural Information Processing Systems (NeurIPS), 34, 2021.
Dominique Beaini, Saro Passaro, Vincent Létourneau, William L. Hamilton, Gabriele Corso, and Pietro Lió. Directional graph networks. In International Conference on Machine Learning, volume 139, pp. 748-758, 2021.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. International Conference on Learning Representations, 2022.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances in Neural Information Processing Systemx, 34:2625-2644 2021a.
10

---

Published as a conference paper at ICLR 2023
Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pietro Lio, and Michael Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. In International Conference on Machine Learning (ICML), pp. 1026-1037, 2021b.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Robert Brijder, Floris Geerts, Jan Van Den Bussche, and Timmy Weerwag. On the expressive power of query languages for matrices. ACM Transactions Database Systems (TODS), 1434),1-31, 2019.
Rémy Brossard, Oriel Frigo, and David Dehaene. Graph convolutions that can finally model local structure. arXiv preprint (rxXi:2011..5000 2020.
Jin-Yi Yi Cai, Martin Fürer, and Neil Immerman. optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-41) 1992.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in Neural Information Processing Systems (NeurIPS), 2020.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Velickovic. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems (NeurIPS), 33, 2020.
Mohammed Haroon Dupty, Yanfei Dong, and Wee Sun Lee. Pf-gnn: Differentiable particle filtering based approximation of universal graph representations. International Conference on Learning Representations, 2022.
Vijay Prakash Dwivedi, Chaitanya Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint vrXiv:2003.00982. 2020.
Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang. How powerful are k-hop message passing graph neural networks. Advances Neural Information Processing Systems, 2022.
Fabrizio Frasca, Beatrice Bevilacqua, Michael M Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. arXiv preprint arXiv:2206. /440, 2022.
Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko, and Oleg Verbitsky. The weisfeiler-leman algorithm and recognition of graph properties. Theoretical Computer Science, 895:96-114, 2021.
Martin Fürer. On the combinatorial power of the weisneil algorithm. International Conference Algorithms and Complexity, pp. 260-271. 2prnee...pringerr, 2017.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning (ICML), pp. 3419-3430, 2020.
Thomas Gärtner, Peter Flach, and Stefan Wrobel. On graph kernels: Hardness results and efficient alternatives. In Learning theory and kernel machines, pp. 129-143. 2003.
Floris Geerts and Juan L Reutter. Expressiveness and approximation properties of graph neural networks. In International Conference on Learning Representations (ICLR), 2022.
Martin Grohe. Descriptive complexity, canonisation, and definable graph structure theory, volume 47,
Cambridge University Press, 2017.
Martin Grohe and Pascal Schweitzer. The graph isomorphism problem. Communications of the ACM, (0(11))122-133: 2020.
Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borgwardt. Topological graph neural networks. International Conference on Learning Representations (ICLR), 2021.
11

---

Published as a conference paper at ICLR 2023
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. Neural Information Processing Systems (NeurlPS), 2020.
John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zine: free tool to discover chemistry for biology. Journal of chemical information and modeling, 52(7): 1757-1768, 2012.
Sandra Kiefer. Power and limits of the Weisfeiler-Leman algorithm. PhD thesis, Dissertation, RWTH Aachen University, 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks.
In International Conference on Learning Representations (ICLR), 2017.
William L Kocay. Some new methods in reconstruction theory. In Combinatorial Mathematics IX, pp. 89-114. Springer, 1982.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations (ICLR), 2020.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph
networks. In International Conference on Learning Representations (ICLR), 2018.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019a.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International Conference on Machine Learning (ICML), pp. 4363-4371, 2019b.
Brendan D McKay, Practical graph isomorphism. Congressus Numeranitum, 30:45-87, 1981.
Brendan D Mckay and Adolfo Piperno. Practical graph isomorphism, ii. Journal of Symbolic
Computation, 60:94-112, 2014.
Miller McPherson, Lynn Lovin,Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415-44) 2001.
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 Conference on Artificial Intelligence, volume 33, pp. 4602-4609, 2019.
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. ICML Graph Representation Learning and Beyond (GRL+) Workhop, 2020a.
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Neural Information Processing Systems (NeurIPS), 33, 2020b.
Christopher Morris, Matthias Fey, and Nils M Kriege. The power of the weisfeiler-leman algorithm for machine learning with graphs. International Joint Conference Artificial Intelligence (IJCAI), 2021.
Christopher Morris, Gaurav Rattan, Sandra Kiefer, and Siamak Ravanbakhsh. Speqnets: Sparsity- aware permutation-eqquiariaa graph networks. In ICML, 2022.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning (ICLR), pp. 4663-4673, 2019.
Hoang Nguyen and Takanori Machara. Graph homomorphism convolution. In International Confer- ence on Machine Learning, pp. 7306-7316. PMLR, 2020.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International Conference Machine Learning (ICMI.). pp. 2014-2023, 2016.
12

---

Published as a conference paper at ICLR 2023
Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. k-hop graph neural networks. Neural Networks, 130:195 205, 2020.
Bastian Rieck, Christian Bock, and Karsten Borgwardt. A persistent weisfeiler-lemman procedure for graph classification. In International Conference Machine Learning (ICML), pp. 5448-5458, 2019.
Ryoma Sato. A survey on the expressive power of graph neural networks. arXiv preprint arXiv:2003.0400 040778 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 333-341, 2021.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mchlhorn, and Karsten M Borgwardt. Weisfeiler-lemman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Erik Thiede, Wenda Zhou, and Risi Kondor. Autobahn: Automorphism-based graph neural nets. Advances in Neural Information Processing Systems, 34, 2021.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations (ICLR), 2017.
Clément Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-passing. In Neural Information Processing Systems (NeurIPS), 2020.
Guangtao Wang, Rex Ying. Jing Huang, and Jure Leskovec. Multi-hop attention graph neural network. arXiv preprint arXiv:2009. 14332, 2020.
Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. N77, Series, 2(9):12-16, 1968.
Asiri Wijesinghe and Qing Wang. A new perspective on" how graph neural networks go beyond weisfeiler-lehmann" In International Conference on Learning Representations, 2022.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learning. Chemical science, 9(2):513-530, 2018
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations (ICLR), 2019.
Jiaxuan You, Jonathan Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. In Conference on Artificial Intelligence (AAAI), 2021.
Muhan Zhang and Pan Li. Nested graph neural networks. Advances in Neural Information Processing Systems (NeurIPS), 34, 2021.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAI Conference Artificial Intelligence, 2018.
Lingxiao Zhao, Louis Härtel, Neil Shah, and Leman Akoglu. A practical, progressively-expessive gnn. Advances in Neural Information Processing Systems, 2022a.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any gnn with local structure awareness. International Conference on Learning Representations (ICLR), 2022b.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 13:7793-78044 2020.
13

---

Published as a conference paper at ICLR 2023
CONTENTS (APPENDIX)
A Indistinguishable Pairs kLWL vs WWWL
14
B Related Work
15
I Expressive GNNs Beyond 1-WL Test
15
B.2 Connections to WL and its Variants
17
Proofs of Theorems
18
C.1
Proots for Weak Hierarchy (Theorem 3.1)
18
C.2 Proofs for Strong Hierarchy (Theorem 3.2 and Theorem 3.3)
................................
C.3 Proofs for Connected-Hereditary Subgraphs Theorem 3.7)
23
C.4 Proofs for Connections k-WL Hierarchy (Theorem 3.8]
C.5
Proofs for Graph Neighbourhood Neural Network (Theorem 4.
31
D
G3N Model Architecture
32
E
Experimental Details and Results
33
Datasets
33
E,2
Baseline Methods
................................
34
Parameter Selection
34
E,4
Ablation Study
35
E.5
Runtime and Memory Analysis for t and d
35
E.6
Runtime Analysis for Connected Variants
E.7
Complexity Analysis k-WI. -WL
37
Limitations and Future Work
39
A INDISTINGUISHABLE PAIRS k-WL vs -WWL
Figure presents two pairs non- non-isomorppic simple graphs of eight vertices from the 312 pairs of non-isomorphic simple graphs reported in Figure
In terms of the J-WL hierarchy, both pairs of these non-isomorphic simple graphs cannot be distin- guished by 1-WL but can be distinguished by 3-WL. Beyond these, there is no further information about why these pairs of non-isomorphic graphs can or cannot be distinguished and what graph properties are important distinguishing them.
Nonetheless, if looking into these pairs of non-isomorphic graphs in terms of the WWWL hierarchy, we have the following observations:
Although both pairs of graphs are among the 312 pairs of non-isomorphic simple graphs of eight vertices that cannot be distinguished by 1-WL, they look very different, exhibiting different properties.
(2)
The reason why G and G in Figure 5)a) cannot be distinguished by 1-WL due to the fact that these two graphs have the same number of vertices in their 1-hop neighbourhoods. Indeed, they also have the same number edges in their 1-hop neighbourhoods. However, they do have different numbers of triangles in their 1-hop neighbourhoods, which explains why they can only be distinguished by N (1. dI- if 3.
(3) The reason why G and G2 in Figure 5)b) cannot be distinguished by 1-WL is different from the case why G2 and GH2 in Figure 5(a) cannot distinguished by I-WL. If 1, then no matter how t is increased, is always insufficient to distinguish these two graphs. On the other hand, even t = 1, these two graphs can be distinguished as long as we consider their 2-hop neighbourhoods rather than 1-hop neighbourhoods, i.e., d d22
Table 5 presents that, among all simple graphs of eight vertices, . dL with varying t and d values have different expressive powers in distinguishing pairs of these simple graphs. For example (1, W)- fails to distinguish 312 pairs of simple graphs from all pairs of simple graphs of eight
14

---

Published as a conference paper at ICLR 2023
Gi
(a)
G (b)
G2
Figure 5: Two pairs of non-isomorphic simple graphs of eight vertices: (a) G1 and G22 cannot be
distinguished by N (t, dL-WL unless & 2 3, regardless how large d is; (b) G and G2 cannot be
distinguished by- N (t, dd- unless d 2 2, regardless how large t is.
vertices and (11, d.-WL with d = 2,3,,4,3 3,5, 6 fails to distinguish 186 pairs of simple graphs. On the other hand, (t, 1)-WL with t = 3,4,5, 6 fails to distinguish 5 pairs of simple graphs
In summary, for all simple graphs of eight vertices, A (1, with 2 3 and d 2 2 sufficient distinguish any pair of them.
Table 5: Indistinguishable pairs by N d on all simple graphs of eight vertices.
d 1
d = 2
d = 3
d =
4
d
=
5
d
t =
312
186
186
186
186
1 186
t =
20
6
6
t 3
5
0
0
0
[ = 4
5
0
0
0
0
[ 5
5
0
0
0
0
t = 6
5
0
0
0
0
B RELATED WORK
B. EXPRESSIVE GNNS BEYOND 1-WL TEST
Below, we summarise the main directions research for designing expressive GNNs that go beyond 1-WL test.
High-order GNNs. Following h- WL, a natural way of increasing the power GNNs is to go higher
dimensions (Azizian & Lelarge 2021 Morris et al. [202I) Morris al. 2019) introduced k-GNN
based on a set variant of WL, which learns features over subgraphs on A nodes and is strictly
weaker than k-WL. Maron al. 2018
expressive as k-WL and showed that reduced 2-order GNN is as powerful as 3- WL. Morris et al. (2020b 2022) and Zhao al. (2022a) proposed high-order GNNs by only considering a subset of kttuples, i.c.. k-tuples that are local or correspond to inducing subgraphs with certain connected components. These GNN models are all provably stronger than 1-WL; however, they still suffer from the shortcomings of k-WL intniintuitive design and high computational costs and are thus impractical for real-world tasks, particularly when graphs are large.
2019b a) developed k-order GNNs that
Unlike these works, our GNN architecture is not built upon the classical k-WL algorithms. At its core, the -WW algorithm proposed in this work node (I-dimensional) refinement algorithm based high-order induced subgraphs in its d-hop neighbourhood, i.e., incorporating subgraph colouring into node colouring instead of propagating k-tuple colouring based on k-tuple colouring of the same dimension. Further, the _ algorithm has the same locality as in standard GNNs, i.e., considering local structures in the neighbourhood within d-hop away from each node.
Injecting structures. Substructure counting has been leveraged by several GNNs inject structural information into node or edge features of a graph (Bouritsas et al., 2022 Barceló et al.) (02T). Typically, isormorphism counts (Bouritsas al. 2022) homomorphism counts (Barceló al.
15

---

Published as a conference paper at ICLR 2023
2021) of small subgraph patterns (e.g., cycles and cliques) are precomputed as application-specific inductive biases. In a similar spirit, Thiede et al. (2021) applied convolutions on automorphism groups of subgraph patterns; Nguyen & Machara (2020) used homomorphism counts of subgraph pattens as graph invariants. A recent work (Wijesinghe & Wang 2022) introduced a way of injecting structural coefficients from local structures into neighbour aggregation. Despite being more expressive than 1-WL, all these models require preprocessing to extract structural information from subgraphs.
Although considering subgraphs, our work has some important distinctions from the above works. We consider subgraphs from a combinatorial perspective which does not require hand-choosing subgraph patterns, while the above GNN models consider specific subgraphs that are pre-defined. As noted by Barceló et al. (202T), knowing which subgraph patterns work well and which do not is critical for the power of the GNN models that reply on specific pre-defined subgraph patterns. However, this question is not easy to answer because determining which subgraph patterns work well is often ipplication-dependeet
Subgraph-based GNNs. Several recent studies proposed to apply base GNN on subgraphs of graph rather than on the whole graph directly (Zhao et al. 2022b; Zhang Li, 2021; Bevilacqua er al. 2022, Frasca et al. 2022). The way of representing graph in terms of subgraphs may vary in models. Beeviacquu et al. (2022) represents each graph as a multiset of subgraphs chosen according to predefined policy, e.g., removing one edge one node. ZZhoo et al. (2022b) and Zhang & Li (2021) represent a graph with a multiset of induced subgraphs, each rooted at one node in the graph, which generalises rooted subtrees used in the traditional setting. It has been shown that, by applying a base GNN that is expressive as I-WL such as GIN (Xu et al. 2019) on subgraphs, the expressive power of these models goes beyond I-WL.
Our work is different from these subgraph-bases GNNs because we do not apply a GNN on subgraphs. Instead, our GNN architecture aims to incorporate structural information (i.e., isomorphism types) and positional information (i.e., positional types) of subgraphs in the neighbourhood of each node into the node's 's embedding. To this end, our GNN architecture similar to standard GNNs except that the neighbourhood information for aggregation may include the information from high-order subgraphs a neighbourhood rather than merely neighbouring nodes.
K-hop message-passing GNNs. Recently, some attempts have been made to extend GNNs from 1-hop message passing aggregation to K-hop message passing aggregation (Abu-El- Hl-Ha et al. 2019 Nikolentzos et al.) 2020; Brossard et al., 2020 Wang et al. 2020 Feng et al. 2022). The key idea is to aggregate information from not only direct neighbours (I (I-hop neighbours) of node but also neighbours within K hops of a node. Feng et al. (2022) showed that standard K K-hop poessag-passsngg GNNs are strictly more powerful than 1-WL test when K > 1, but their expressive power is bounded by 3-WL test whose proof is based on the work in (Frasca et al.) 2022). To further improve the expressive power, Feng et al. (2022) proposed a new GNN model, called KP-GNN, which leverages the information of peripheral subgraphs into K- K-hop message-passing GNNs.
Our work provides comprehensive theoretical framework for characterising the expressive power of different K- K-hop message-passing GNNs. For example, standard K K-hop message-passen passing GNNs with the shortest path distance kernel (Feng et al. (022)) can be characterised as corresponding to our Mf,, d)-WL with d = K, where each node has shortest-path distance to the target node as a positional type. Further, depending on the isomorphism types of peripheral subgraphs, KP-GNN can be characterised as an instance of .f d)-WL in our work with d = K and t referring to the size of peripheral subgraphs, where isomrphism types are restricted to pre-selected isormorphism types by KP-GNN.
Node identity and individualisation. Several works augmented node identifiers (Loukas 2020
You et al. 202T) and random features (Vignac et al., 2020) (Sato et al., 202T, Abboud et al. 202T) or applied individualisation and refinement (Dupty et al. 2022) to improve the expressive power of GNNs. Specifically, You et al. (202T) proposed ID-GNNs which add identity information for each rooted node during message passing. Vignac et al. (2020) manipulated node identifiers in cermutationninvarial way to learn local context around each node. MMrpphy et al. (019) introduced RP-GNN which runs permutation-sensitvv GNN by adding node identifiers and then sums over all permutations of node identifiers to obtain cotmuutationiiivrriaa representations. Dupty et al. (2022) individualised nodes using individualisation and refinement for canonical colouring. These GNNs are permutation invariant in expectation.
16

---

Published as a conference paper at ICLR 2023
In our work, we do not assign identifiers and random features to nodes, nor individualise and refine the colours of nodes. Our GNN architecture can preserve permutation invariance.
Tensor languages. Several works have studied the expressive power of GNNs from the perspective of matrix query languages. Balcilar et al. (202T) obtained the upper bounds of the expressive power of GNNs in terms of 1-WL and 2- 2-WL based the MATLANG matrix query language (Brijder et al. 2019). Geeets & Reutter (2022) explored a tensor language specifically designed for specifying GNNs and discovered the connections between guarded fragment of the MATLANG matrix query language and k-WL. The key idea is to first reduce the expressivity problem of GNNs to the problem of specifying GNNs in a tensor language and then analyse their expressive powers in terms of the number of indices and the summation depth used in tensor language expressions.
In addition to the above, Bodnar al. (2021a b) proposed message passing scheme operating on topological objects such as simplicial complexes or cell complexes, |Horn et al. (2021) proposed a topological layer for GNNs that can leverage topological information of graph using persistent homology- technique for calculating topological features such as connected components and cycles of graph. These works also lead to more expressive GNNs than I-WL.
B.2 CONNECTIONS TO &- AND ITS VARIANTS
Recently, several heuristic algorithms for the graph isomorphism problem have been developed based on the classical k- WL algorithms, which take into account the sparsity of graphs (Morris et al. 2020bb 2022 Zhao et al. 2022a These works were motivated by addressing the issue of high computational cost associated with the classical k-WL. algorithms.
In the following, we conduct comparison of the k-WL and its variants, and our A -WL algo- rithms. To obtain a better understanding of the underlying differences between these two families of algorithms (k-WL. vs -WL), we separate the comparison of these algorithms into two aspects:
Objects be coloured in a graph (i.e.. #Coloured objects referring to the number of coloured objects and AColoured objects referring to the type of coloured objects);
(2) Neighbour objects when colouring each object (i.e., #Neighbour objects referring to the number of neighbour objects and ANeighbour objects referring to the type of neighbour objects).
Let denote the number of nodes in graph, be the average number of nodes adjacent node in a graph (i.c., average node degree), a be the average number of nodes in the d-hop neighbourhood of node, and dia(G) G) be the diameter of graph. We denote sets with exactly i nodes as k-sets and sets with at most & nodes as < k-sets. Usually, ad < n when d << dia(G). Further, subset(n*, s) refers to the number of k-tuples in a subset of all n² k-tuples whose induced subgraphs have at most s connected components, while subsen() (?), c) refers to the number of < k-sets in a subset of all Σ (?) sets whose induced subgraphs have most e connected components.
Table compares k- WLW, .A -WL, and their variants in terms of #Coloured objects, #Neighbour objects, AColoured objects, ANeighhour objects, and sparsity-awarenest We have the following observations:
k-WL and its variants focus on colouring k-tuples, subsets of k-tuples or their corresponding set forms such as k-sets and < k-sets by aggregating information from their neighbours of the same types. -L aims to colour nodes by aggregating information from neighbouring subgraphs. Here, subgraphs may be considered as corresponding to (-sets or S I-sets. In regard to their connections to GNN architectures, both k- and .W-WL can be casily implemented for graph- learning tasks. However, for node-level lcarning tasks, as discussed in MMoris et al. (2022), k-WL and its variants need an additional pooling operation combine features of k-tuples, kssett, < k-sets that contain a node for computing representation of the node. In contrast, -WLL serves as a natural paradigm that computes node representations as first-class citizens.
k-LL has a more global nature than .V-WL in the sense that its coloured objects are grounded on all possible k-tuples of an entire graph. The variants of k-WL. impose some
17

---

Published as a conference paper at ICLR 2023
Table 6: Comparison k-WL and their variants 6-k-LWL (Morris 2020b), (k, s)-LWL (Morris) et al. 2022), and (k, - (Zhao et al. 2022a) with our M (t. W and (t. d]- W-WL. where #Coloured objects and #Neighbour objects refer to the number of coloured objects in graph and the number of neighbour objects for each coloured object, respectively; AColoured objects and ANeighbour objects refer to the type of coloured objects and the type of neighbour objects, respectively; is the number of nodes and is the average node degree in graph; a is the average number of nodes in the d-hop neighbourhood of a node. Note that a < n for graphs whose diameters considerably greater than d.
W-
8-L-LWL ()LW))
(H,O(S)-EEWL
((t,
(t,
#Coloured
objects
n*
n
subset(n""s)
n
#Neighbour
objects
n x
a axk
a axk
n xx
subset E
AColoured
k-tuples
k-tuples
A-tuples
< k-sets
nodes
nodes
objects
A Neighbour
objects
k-tuples
k-tuples
A-tuples
S k-sets
t-sets
S ftssets
Sparsity
X
/
x
-awareness
additional conditions on all k-tuples with an aim to reduce all k-tuples to subset of all k-tuples or k-uules.. Two commonly used conditions by the variants of k- 4-WL are:
reducing k-tuples or < k-tuples to set form such as k-sets and k-sets, and restricting coloured objects neighbour objects satisfying a certain connectivity conditions, e.g., containing no more than a specified number of connected components.
In contrast, -L is designed to be local. This difference can be observed from Table 6
Specifically, for coloured objects, k-WL and its variants deal with the number n² of all k-tuples, subset of all k-tuules, or $ k-sets from entire graph, while -W only deals with the number n of all nodes a graph. For neighbour objects, k- k-WL considers the number x k of neighbour objects for each coloured object; 5-k-LWI (Morris et al.) (220b)) and (ki, s)-LWI. (Morris et al. 2022) consider the number a x k of neighbour objects, where a refers to the average node degree, since only local neighbours
k-tuple are taken into consideration; and (k, <)(<-STTWL (Zhao et al. 2022a) considers the number n x q of neighbour objects for each coloured object, where q E [b.. For N d), it considers the number (e") of subgraphs of order from the d-hop neighbourhood of a node while "t, dL considers only connected subgraphs with < t nodes. When a < -WWL performs much more efficient than k- and its variants.
As depicted in Table 6 the variants 8-L-LWL, (k, s)-LWL, (k, (S)))SWL) and our "t, dL are sparsity-aware (i.c., adapt to the sparsity of a graph), while the classical Nonetheless, different from
k-WL and our A (t,, dL algorithms these k-WL variants which trade off expressivity for computational efficiency, our (t, d)- WL is provably as powerful / (t, dL without compromising expressive power while improving efficiency on sparse graphs (see Theorem 3.7).
not sparsity-
Remark B.I. It is worthy to note that, when learning node representation, our -WL algorithms consider all or connected subgraphs bounded within the d-hop neighbourhood of node, but these subgraphs may not necessarily be incident to the node. This is different from rooted subgraphs considered by the local variants of G-W as well as subgraph-base based GNNs in the literature.
C PROOFS OF THEOREMS
C. PROOFS FOR WEAK HIERARCHY THEORREM 3.1)
To prove Theorem 3.1 begin with the following lemma.
18

---

Published as a conference paper at ICLR 2023
Lemma 1. For any fixed d E N, (t+11 11-1,, is at least as expressive N - (t,d)-WL in distinguishing non-isomorphic graphs, where 1.
Proof. We prove this lemma by contradiction. Assume that there exist two non-isomorphic graciphhhiggghhhsshpe G and G2 which can be distinguished by -t, d)-WL, but cannot be distinguished by N (t+1, d)- WL iterations. This implies that, for any (-th iteration where / - 0,1,..., k- N d)) WL must have the same multiset of node colours for G1 and G2-
Now suffices show that, for any iteration I, if the colours of any two nodes in G1 and G2 are the same by (t+1, prove this by induction.
then their node colours by .N" (t, dD-WL must also be the same. We
When = 0, the initial node colours are the same for -++1,, (-1,d) d--WL and Mf d)-WL; hence, the above statement holds. When > we assume that this statement holds for 1-1. Then, the colours of any two nodes in G and G2 are the same at the 1-th iteration by - (1+1,,,,11 d)- i.e., (((1)) = (w2), by Equation we have:
(5 (s))
= (u2), s)
Since i and u2 have the same colour in the 1-1-th iteration, this gives the following equation which must hold
( (4 =
By the definition of the -WL algorithm, (e hit represents the set of multisets of colours for subgraphs of 1+11 order from the d-hop neighbourhood of a node u at the 1-1-th iteration of This corresponds to (.*1) induced subgraphs of order [+1 where m refers to the number of vertices in the d-hop neighbourhood of node and w.l.o.g. we assume t+1 S m.
applying
We show that (5(u.)) hien.,, determines (Su.,))ier, Here, (f(w.)) hier, corresponds to (7)) induced subgraphs of order the d-hop neighbourhood of node u at the I-th iteration of (t, d)- WL. Since each 5(w..) encodes the count of induced subgraphs with respect to an isomorphism type i, we just need to show that the isomorphism counts of induced subgraphs of order are determined by the isomorphism counts of induced subgraphs of order 1+
Let S be an induced subgraph of order 1+11. We denote the deck of S as deck(S) which is the set of induced subgraphs of order t that are obtained by deleting one vertex in every possible way from S. That is, deck(S) SS v V(S), V(S) V(S) S²) C S}.
By the results in (Kocay 1982), we know that counting induced subgraphs and counting all subgraphs have the same power. Note that each subgraph of vertices lies in m- subgraphs of (++1 vertices. So there is a total number (m-t) of subgraphs of (+11 vertices, for which each subgraph S" vertices sits in their decks. Thus, to determine the number of times subgraph S' of vertices occurs in graph, we can first count the occurrence of S" in all of subgraphs of t+11 vertices, and then divide the count by (m-t). Therefore, the counts of subgraphs of vertices t. In doing so, we are able to infer the isomorphism counts of induced subgraphs of order t from the isomorphism counts induced subgraphs of order t+1.
vertices f+1 1 implies the counts of subgraphs
Thus, we have the following equation:
( (s = (6tm),))
Accordingly, the following must hold:
(ur), ( her.) = (uz=)(uz) her.)
Hence, by Eqquaion again, we know that the node colours of u, and ut by N- (t, dd- WL must also be the same the 1-th iteration.
19

---

Published as a conference paper at ICLR 2023
This implies that there exists an injective function between colours of the nodes by . (t+11, d)- -WL and by .V" (t, dt, at any I-th iteration. Since for any 1-th iteration where 0, 1.... k-1 N (++1, d'-WL has the same multiset of node colours for G1 and G2. G2 (t, d.. must also have the same multiset of node colours for G1 and G2. This means that (t, d) cannot distinguish G1 and G2 after k iterations, which contradicts with the assumption. The proof is done.
Theorem 3.1. For any fixed N, M dt- strictly more expressive than (t, dt, in distinguishing non-isomorphic graphs, where 2 1.
is
Proof. By Lemma 1 we know that (t+11 d)-WL is as expressive as N (t, d.-WL. Thus, we just need to show that, for any fixed but arbitrary E N, there exists at least a pair non- isomorphic graphs (G1, G2) that cannot be distinguished by N d)-WL but can be distinguished by N d
Let V(G) and E(G) denote the set of nodes and the set edges G. respectively. In general, there are three cases when constructing such a pair of non-isomorphic graphs (G1, G2):
When & = 1, we construct G₁ to be two cycles length 2d + and G2 to be one cycle of length 4d 2.
When 2, we first construct a pair (G1, G2) of graphs where Gı consists of two cycles of length and G₂ consists of one cycle of length 8, Let G denote the complement of graph Then, we construct G, = G, to the complement of G, for r 1,2.
When / 2 3, we first construct a pair (G1, G2) of graphs where G₁ consists two cycles of length E and G2 consists of one cycle of length 26, where is defined follows:
13/-11/2 or (3t + 1)/2 if odd: 31/2
i
(6)
/ is even.
Then, for each of G1 and G2, add single vertex that connects all vertices graph. More precisely, given two new vertices U1 VG,) and v2 & V(G2). we define G1 and G2 as V(C.) V(G,) {r,} and E(G,) = E(G,) U ((v,, u)lu e V(G,)) for = 1,2.
Figure 8
(a) demonstrates the aforementioned pairs of non-isomorphic graphs for the case of t = 1. Figure shows the pair of non-isomorppic graphs for the case of 2. Figure 7 (a)-(c) shows the pairs of non -somoooocppicc graphs for the cases of = 3 and t 4.
The proof is done.
G
G2
G
4-cycles
8-cycle
G =
G - T2
Figure 6: (Left) Two graphs G1 and G2 where G1 consists of two 4-cycles and G2 is one 8-cycle; (Right) Two graphs G2 and G₂ that can be distinguished by - 1, dL but cannot be distinguished by - dL-WL for and 2 1, where G, and G₂ are the complements of G₁ and G2 respectively.
20

---

Published as a conference paper at ICLR 2023
G
G2
c=
(a)
G
G2
V
5=
V/2
(b)
G
G₂
V
6
1/2
(c)
Figure Three pairs of non-isomorphic graphs (G1, G2) that can be distinguished by A 1, WL but cannot be distinguished by N (t.d)-WL: (a) = 3 and f = 4, (b) t 3 and 5, and (c) t and where d 2
C.2 PROOFS FOR STRONG HIERARCHY (HEOREM 3.2 AND THEOREM 3.3
Lemma 2. For any fixed d E N, ((t+1,d)WWL. at least as expressive as M d)- in distinguishing non-isomorphic graphs, where 2
Proof. The proof can be carried out in the same way as in the proof for Lemma Specifically. to prove this lemma, it suffices show that, for any two non-isomorphic graphs G2 and G2. if they can be distinguished by (t, dL-WL at the (-th iteration, they can also be distinguished by N (t+1, dL the 1-th iteration. By the definition of the - algroithm, the of multisets of colours for subgraphs of t+11 order from the d-hop neighbourhood of node u at the 1-th iteration of applying H (t+11 d WL is represented
{E) (E(w.t.) he This still corresponds to (.7)) induced subgraphs of order t+1, where m refers to the number of vertices in the d-hop neighbourhood of node and w.l.o.g. assume f+1 &
Now, we need to show that (E/u.s.)) lieden determines (4/u.,.) ben.je.. (E( heeneee corresponds ("*) induced subgraphs of order in the d-hop neighbourhood of node u at the 1-th iteration of N (1, dLL Different from &(u..) that encodes the count of induced subgraphs with respect only isomorphism type i, Elu.i,) encodes the count of induced subgraphs with respect to both isomorphism type and positional type j. Accordingly, need show that the counts
21

---

Published as a conference paper at ICLR 2023
of induced subgraphs of order t with respect to both isomorphism types and positional types determined by the counts of induced subgraphs of order t++1 with respect to both isomorphism types and positional types.
The fact that each subgraph of t vertices lies in m-t subgraphs of t++1 vertices remains. To take both isomorphism types and positional types into account, when determining the number of times subgraph S' of vertices occurs in a graph, we can first count the occurrence of S' in all subgraphs of t+1 vertices with respect both the isomorphism and positional types, and then divide the count by (m-t). Thus, the counts of induced subgraphs of vertices [+] +-1 imply the counts of induced subgraphs of vertices respect to both isomorphism types and positional types.
Theorem 3.2. For any fixed d E N, M (1+1, (i-1,,d)Wi dL-WL is strictly more expressive than N d)-WLL in distinguishing non-isomorphic graphs, where 2
Proof. By Lemma 2 we know that (t+11, WL is at least expressive N d)) in distinguishing non-isomorphic graphs. For the strictness of expressivity between A M (t+11,d)- and (L,, d)-WL, we can see that the pairs of non-isomorphic graphs (G1, G2) that cannot be distin- guished by (t, d)- WL but can be distinguished by .A - (t+1, d WL in the proof of Theorem 3.1 still hold when taking positional types of induced subgraphs into account. Thus. we can prove this strictness in a similar way as for the case that N ( d.- is strictly more expressive than - (t, dL- i.e. based on the same pairs of non-isomorphic graphs (G1, G2) described in the proof of Theorem 3.1
Before proving Theorem 3.3 we first prove the following lemma.
Lemma 3. For any fixed t E N, (t,,d+1)--W is at least as expressive as V dd. in distinguishing non-isomorphic graphs, where 2 1.
Proof. We can proceed with the proof as follows, in a way similar to Lemma]] 1 Assume that there exist two non-isomorphic graphs G1 and G2 which can be distinguished by . d)-WL, but cannot be distinguished by .V (t, d+1)-WL after k iterations. This implies that, for any 1-th iteration where 1, N (t, d+I)--W. must have the same multiset of node colours for G1 and G2. k-
1 1=
Then we show that, for any iteration 1, if the colours of any two nodes in G1 and G2 are the same by N (tt, d+1))WL, then their node colours by NV (t, d)-WL must also be the same. Again, we prove this by induction.
When = 0, the initial node colours are the same for (t, d+1)- and (t,, d)- d'- Hence, the above statement holds. When 7 >> O, we assume that this statement holds for the 1-1hth iteration. Then, the colours of any two nodes in G1 and G2 are the same at the (-th iteration by M (t, d+1)- WL, ('(u)) 5 (uz), by Equation 3 we have:
(sn=)(u1); (S( bew.knneeeeeeann = (12))
Since in and un have the same colour in the 1-1-th iteration, this gives the following equation which must hold
By the definition of the permutation invariant function fpoe Sc N that encodes the posi- tional types of induced subgraphs and satisfies the condition: VS, E Sju, E (Spa,,,d4)) ((u,,a)) (S.) # (S)), we know that Ja S Ja+ı holds for induced subgraphs in neighbourhoods and any fixed but arbitrary N, where Ja (S)]S S(u,,4)) and Jat1 (Spo((S) (u..d+))) Accordingly, we have the following for any node in G1 and Gz:
[el-1 henseet S 1El-1 hienssen
22

---

Published as a conference paper at ICLR 2023
Since Ç¹ Sg N such that (1())) (S22 iff fis0(S1) and ((w.i.5) (S){S ((,,t,d) (S)oi and (5)= by Equation 3 aggai and the fact that HASH(.) in Equation iss an injective function, we further have
and ( (S1) fpos (S2)
( Ayn = 1e
We know (u1) =5-=1(m (uz) by the assumption for the | 1-th iteration. Thus, the following must hold:
(s' (w)),,n), (o) = -s- (u²)) (
According to Equation 3 know that the node colours of and u2 by N (1, d)-WL. must also be the same at the 1-th iteration.
This implies that there exists injective function between the colours of nodes by N d+1)- WL and NY (t. dL- at any 1-th iteration. Since for any /-th iteration where 1 = 0, I...., k- (t, d+1)-WL has the same multiset of node colours for Gi and G2, M (t, d)-WL must also have the same multiset of node colours for G1 and Gz. This means that (t, d)-WL cannot distinguish G1 and G2 after & iterations, which contradicts with the assumption. Hence, N (t, df1)-+--WW. WL is at least expressive as . (t, dl-WL in distinguishing -sommooooppicc graphs.
k-1
Theorem 3.3. For any fixed t N. N d+-)d---WL.... WLL is strictly more expressive than N (t,, dd-WL in distinguishing non-isomorphic graphs, where 2 1.
Proof. Firstly, we show that, for a fixed but arbitrary t E N, there exists at least one pair of non- isomorphic graphs (G1, G2) that cannot be distinguished by A (t, d but can be distinguished by M(t, (t, d+1) d-W. Generally speaking, there are also three cases to consider when constructing such a pair non non-isomorphic graphs (G1, G2):
When t 1, we construct G₁ be two cycles of length 2d + and G2 be one cycle of length 4d 2.
When t = 2, we construct G to be two cycles of length 2d + and G2 to be one cycle of length 4d + 6.
When / 2 3, we construct G to be two cycles of length 2d + and G2 to be one cycle of length 4d + 4.
Figure 8 (a)-(c) depicts the pairs of non-isomorphic graphs being constructed for the cases of any and t = 2, and = 3, respectively.
Then, by Lemma 3 we also know that M ,f,t, (++1)-WL is expressive M dL- Based on the above two aspects, it can thus be concluded that (t,, (++1)-WL. is strictly more expressive than N (t, dL-WL in distinguishing non-isomorphic graphs.
C.3 PROOFS FOR CONNECTED- HERREDTARY SUBGRAPHS
THEOREM 3.7
Lemma 3.5. Sht connected-hereditary
Proof. By the definition of S.St every S S is a connected induced subgraph, Further, if SE S.S, then every connected induced subgraph of S is also in S By Theorem 3.4 S is thus connected-hereditaryy
Lemma 3.6. For each induced subgraph satisfying E S but S & S.t. there exists a set (S,, S2,.,,, } S5t such that S S₁ S2 Sq: where ((S) = q.
23

---

Published as a conference paper at ICLR 2023
G
G2
(2d+ 1)-cylles
(4d 2)-cycle
(a)
G
G₂
(2d+ 3) -yccclss
(4d + 6) -cycle
(b)
G
G2
(2d+ 2)-cycles
(4d + 4)-cycle
Figure 8: Three families of pairs of graphs that can be distinguished by N- + 1)-WL but cannot be distinguished by. N- (1,, dJ-WL: (a) / = and d 2 (b) = 2 and d 2 1, and (c) / 2 3 and d I.
Proof. Since S E S but S & S such an induced subgraph S must have more than one connected component. Then, for each connected component in S. it corresponds to one connected induced subgraph in S. Thus, is straightforward to show that S = S₁ S2 o...... S.S. where [S1, S2..... ......... } corresponds to the set of components of S and {S1, S, Sy} C S is such set of connected induced subgraphs.
The proof of o Theorem 3.7 depends on two lemmas Lemma and Lemma In the following, prove these two lemmas first.
Lemma For any E and N, A"t d) is least as expressive (t, ((t,d)-WL. dL in distinguishing non-isomorphic graphs.
Proof. For clarity, we use (u) and ('()) to refer to the colour of a node u by (t d), and (t, dL-WL, respectively, in the following of this proof.
We prove this lemma by contradiction. Assume that there exist two non- -soooohoo graphs G1 and G2 which can be distinguished by (t, dLL but cannot be distinguished by "t, d)-WL after k iterations. This implies that, for any I-th iteration where = 0, 1, 1-1, A=l1, d)-WL must have the same multiset of node colours for G1 and G2, i.e., (s: (.vE()))) ((5((2)) B.VEGG.)
Below, we need to prove the following statement:
(A1). For any iteration 1, if the colours of any two nodes in G1 and G2 are the same by A d)- WL. i.c., <((u,) = (u))), then their node colours by (t, d)JWL must also be the same, i.e., s'(11) 5 (u2).
24

---

Published as a conference paper at ICLR 2023
We prove Statement Al by induction.
For 0, Statement A1 holds since the initial node colours are the same for (t, d) -II and N (t, d)
Assume that Statement Al holds for 1-1. Then if su((2) = (2(22), by Equation 4 and the fact that (ASH(-) is injective, we have:
- -
- (u1). U Her ke(1).]
U kE[L,1]
This leads to the following equation:
U [E[1,A]
U ( (e ke(L
Now, need to show that, with respect both isomorphism types and positional types, the counts of connected subgraphs of vertices k for S. k S determine the counts of all subgraphs of f vertices.
We first ignore positional types and focus on proving that the counts of connected subgraphs of vertices for S le S t determine the counts all subgraphs of vertices with respect to isomorphism types. The main theorem upon which our proof will be based is the Vertex Theorem of Kocay (1982).
Let G = (V, E)) be graph, G[V'] for V S V be an induced subgraph of G whose vertex set 7 and whose edge set consists of all of the edges in E that have both endpoints V and c(S, G) l[ C (G) G[V' = S}} denote the number of induced subgraphs of G which are isomorphic to S, i.e., isomorphism counts the symbol G in e(S, G¹) unless the graph G needs to be specified.
G. the following, we omit
We start with introducing Kocay's Vertex Theorem.
Vertex Theorem. Let .n)) be a list of all isomorphism types of graphs, and S and S2 be any two graphs. Then
((S))((22) = Σ ame(im))
where the coefficient am the number of decompositions of (1m) into V11 U V22 such that im [V]] ~ S1 and im [V2] S2, and V1 and V/2 may be overlapping.
Below, we show how to use Kocay's 's Vertex Theorem to prove that, given the counts of connected subgraphs of k vertices with 1 k & & with respect their isomorphism types, the counts of subgraphs of t vertices with respect to all isomorphism types can be determined.
If an isomorphism type corresponds to connected subgraphs, i.e., E If, then it is trivial prove because the count of connected subgraphs with respect to such isomorphism type is already available. Thus, we only need to discuss the case for E (Tz - Iς) in the following. We prove this by induction:
For le 1. there only one isomorphism type inde that IE. Thus, the count of nodes with respect to inode is already available.
For l: = 2, there are two isomorphism types one in IS (i.e., ledge) and the other in (T& IE) (i.e., inondge). By the Vertex Theorem, we can determine the count of subgraphs for inoedge easily through the following equation by applying the Vertex Theorem:
-
ciioode) (inoode) )o(bnode) = aie((foodgee azc(Eedge) -ggc(inode)-
25

---

Published as a conference paper at ICLR 2023
Here, d1, 0g. and ag are the coefficients. Following the Vertex Theorem, each am where m = 1,2, 3 represents the number of decompositions of V(im). where im inaodges Bedges undde respectively, into Ví U V22 such that im [V]] &node and im [V2] ~ bnode- Note that, it is possible that V1 n V/2 A 0. Based on this, we have 01 = 2, 02 2, and 0g 1. That is,
((Inode)) = 20(2n (nnodee)) + 2c(Eedge) + c(inode))
(9)
Since indd I and ledge E Lig the values of c(inode) and c(iedge) are already available. Hence, we can calculate the value of c(Inoedge) according to the above equation.
Assume that this holds for 1- we now prove the case For each isomor- phism type i E (4, If), we apply [quattion 7 of the Vertex Theorem as follows:
* The LHS of Equation 7 corresponds to two subgraphs S and S2 of i which satisfy the condition: V(Si) / 0, V(S2) o 0, and Si o S2 = i, i.e., i is the union of two node-disjoint subgraphs S₁ and S.y;
* The RHS of Equation 7 corresponds to the set of all isomorphism types in Uigkge Ia including the isomorphism type i.
Note that the order of considering isomorphism types in (Te I5) is non-trivial. Specifically, given two isomorphism types i and i' from 4, with (ii) = V('). we say that i subsume i', denoted as i = ,, if and only if there exists at least one decomposition of V(i) into Vi...., V/ such that Ulaos V/ = V(i) and (i(V)).-.. [[V]] = (Ss St 5r where S2, S) is the set of all con- nected components of i'. For any two isomorphism types from (I, - I5), one iso- morphism type should be calculated before the other isomorphism type if the former subsumes the latter. Since all isomorphism types in L have the same number of vertices (i.e., vertices) and are distinct from each other, we have the following properties:
Pl. (4,2) is a poset, i.e., 3 is a partial order on isomorphism types in 4t- P2. Coefficients for isomorphism types in I - {i} are zero if they are subsumed by i.
According these two properties, we know that, given any isomorphism type (T-- - If), the values of c(t') for isomorphism types i' E (7₂ 1f) that satisfy /' J i are already known, while the values of c(i" for isomorphism types i" E (T: 72)) that satisfy i i" are unknown but also not needed since their corresponding coefficients are zeros. Moreover, by the assumption that the case = t-1 holds, the values of c(i" !M, for isomorphism types i" E I where 1 < k $ t are known, including c(S1) and C(S2). Hence, the value of c(i) can be determined by applying Equation of the Vertex Theorem as described above.
Since positional types provide additional information to distinguish subgraphs, we may view them as one additional feature for subgraphs and handle it as an extension to isomorphism types to prove that the counts of connected subgraphs of vertices k for 1 < k S t determine the counts of all subgraphs of vertices with respect to both isomorphism types and positional types. This thus leads to the following:
Since we assume that Statement A1 holds for the (1-1)-th iteration, i.e., if ((-( = - (wz), then siens"- (m1) = (1-(( we further have the following:
(m))) ((( i, (anr,,))))saaa )ien.eeu.) = (sz)) (((( (,n, (eMeesee
Hence, from the above equation and by the definition of node colouring in Equation 3 we know that s'(un) ) = s((22). Statement A1 thus holds for the 1-th iteration.
26

---

Published as a conference paper at ICLR 2023
Ii
4-1
X
7 J Z
7 C
V.
t= 4
L
1=3 3
1=2
t=1
Figure 9: Isomorphism types for graphs of / vertices, where 1 < / < 4, I refers to a set of isomorphism types for connected subgraphs of order less than or equal and I - I refers to set of isomorphism types for disconnected subgraphs (i.e., containing at least two connected components) of order less than or equal to t.
According Statement AI, there must exist an injective function such that ('()) f(c:(u)) for any vertex in G1 and G2. Then, since for any 1-th iteration where = 0, 0, k-1 (t, has the same multiset node colours for G₁ and G2, i.e., (5((w))Buseiic)) = (12( Bf (e)V((2)) (t, d)- must also have the same multiset of node colours for G1 and G2, i... (u)) B EVv (z))) ( ( This means that Ntt, (tt,d)-WL cannot distinguish G2 and G2 after i iterations, which contradicts with the assumption.
Example 1. Figure 9 depicts all isomorphism types for graphs with up to 4 vertices. Below, we illustrate how to calculate c(. .) on graphs by applying the Vertex Theorem, where is an isomorphism type in (T, If') for 4.
Step 1: We calculate d. using the following equation, where el ) and c(.-) are known because both and .. are isomorphism types in U1 1::
el )c( = 2c(. + 2c(._) + c(
(10)
Step 2: We calculate c(. by decomposing, into two subgraphs S1 = and S2 Since the coefficients that correspond to the following isomorphism types are zeros, we omit these isomorphism types in the equation:
Then, we have the equation below:
+ azo 4 + azc(
aic( Z + a5c( + age( (
c((-))(. .) =aje
a70
+ agell )) agel
annc(. .)+
+ +120( (
a
(11)
anzhl/ / .)+ ancclee)
Following the Vertex Theorem, we have the following coefficients for Equation 11
01
02
03
0.4
05
06
07
0g
0g
010
01
012
013
014
0
2
2
2
2
0
27

---

Published as a conference paper at ICLR 2023
In the RHS of Equatiin 11 the isomorphism types in the first, third and fifth lines belong to 1 for 1 = 4, 3, 2, respectively. Hence, the counts subgraphs with respect to these isomorphism types are already available. The isomorphism types in the second line belong to 4: - g for = 4, By the property P1, we know that the counts of subgraphs with respect to these isomorphism types 7. and have been calculated before calculating the count with respect to The isomorphism types in the fourth line belong to 1. - 1 for k = 3, and by the induction, the count of subgraphs with respect to the isomorphism type
is available. Therefore, only the value of c(. is unknown in the RHS of Equation 11 On the other hand, the values for c(.o) and c(. are both known because and
belong to 1g. for k = 2. Putting things together, we can determine the value of cl. .) using Equation 11
In the following, we illustrate how to apply Equation 10 and Equation 11 in the above steps to calculate cl. for two graphs:
and X
(1) Calculating c(. .) for
We hereby detail how cl can be derived for the graph
We know e( . = 5 and c(. .) = 6 for the graph 7 By applying Equation 10 in Step 1, we have
Equation
5 x 5 = 20( .)
(12)
Hence, we obtain c(. 4.
Now apply Step 2. Because 7. .. and . all subsume. we have caleulated cf (7))
c(. .) = 0 and c(. = 2. Further, know the counts of isomorphism types that belong to 1 1, al (L)) = 2 and
for l: 4,3, 2, i.e. we have < = cl (11 0, o, =(A
of <(L.) = c(.,) = 6. By the induction, we have also calculated cl/ .) = 3t at h: = 3.
By applying EEquation 11 thus have
x +
0+0+0+06 3+
0+2x66 6+
2
0
By solving it we have c(. .) = 0 for the graph
(2) Calculating c(. .) for K We show another example of calculating c(. for the graph
We know c( .) 5 and c(. = 4 for the graph K By applying Equation 10 in Step 1, we have
5 x 20( .) + 2 x 4
(13)
Hence, we know c(. .) = 6.
Now we apply Step 2. Because V.. and all subsume we have calculated of (7.)
c(. .) = 0 and c(l = 1. Further, we know the counts of isomorphism types that belong to Ig
for A: = =, 2, i.e. we have aL = = = - = 0, cl c///) = 1, ol ( 2 and
(L)) c(.oo) 4. By the induction, have also calculated el d 4 at = 3.
28

---

Published as a conference paper at ICLR 2023
By applying Equation 11
thus have
4 x + 111x2x 2+
0+2x1+0+d,
0+2x 4+
2 4+
0
By solving it we have c(. 3 for the graph
Remark C.1. It is worthy to notice that, when calculating cii) ( an isomorphism type i E (1z 16--1. 18).
the ways of applying Equation
2 of the Vertex Theorem may not be unique.
Taking the isomorphism type c(. for example,
calculate it in two different ways:
(1) As illustrated in Example 1 and then calculate c(. via treating S1 - and S
we may first calculate c(. .) via treating S1 = and S2
(2) Alternatively, we may first calculate c([)) .) via treating S1 = and S2 and then calculate c( via treating S1 -/- and S2
Lemma 5. For any i E N and d E N d)- is at least as expressive as N d)- in distinguishing non-isomorphic graphs.
Proof. The proof follows similar structure used in the previous lemmas. Specifically, we assume that there exist two non-isomore non-isomorphic graphs G2 and G2 which can be distinguished by st d)-WL, but cannot be distinguished by N (t, (t, dL after l iterations. This implies that, for any 1-th iteration where = 0, 1,..... k N (t,, dL-WL must have the same multiset of node colours for G and G2. ie..
= [[s -
(GV)(
We need to prove the following statement:
(A2). For any iteration I, if the colours of any two nodes in G1 and G2 are the same by (t,, d)- WL, i.e., s((u)) =<((u)) then their node colours by (t, d)-WL must also be the same, i.e., ((( (u2).
We prove Statement A2 by induction:
For 0, Statement A2 holds since the initial node colours are the same for V dL and (tt, WW.L
Assume that Statement A2 holds for 1-1, Then if c'(()) 5((u)), by Equation we have
(wn),, (.leense.))) (12), (
This gives us the following
(s = (s1-1 (6
Then, we need to further prove that, with respect to both isomorphism types and positional types, the counts of all subgraphs of vertices can determine the counts connected subgraphs of vertices for < As The proof may follow similar counting argument from Lemma by noticing that each subgraph of vertices uniquely determines the set of all subgraphs of & vertices contained within it for 1 < < t.. Thus, to determine the
29

---

Published as a conference paper at ICLR 2023
number of times subgraph S of & vertices occurs in graph where 1 S S t, we check all subgraphs of vertices which contain it and then divide the count by (2-x), ie., the number subgraphs of vertices which contain where m = |Na(u)] is the size the neighbourhood of node Thus, have
(i U kE[11]]
U kE[1.1]
Similar to the previous direction, by assumption Statement A2 holds for the (1-1)-th iteration, i.e., if cf (un) = (uz), then (1n) - - We obtain the following:
(d U ( kE(1.]]
1 (wi), U her kE[L.]]
By the definition of node colouring in Equation 4 ffor .. WLL, we conclude ((())) = (u2). Hence, Statement A2 also holds for the (-th iteration.
According to Statement A2, there must exist an injective function f such that <<(u) (((( for any vertex in G1 and G2. Then, since for any 1-th iteration where / = 0, 0,1...., has the same multiset of node colours for G₁ and G2, i.e., ((n(w) (ur))).eevia eV(C,) ( (12) (usVia)))) Noll, d)-WL must also have the same multiset of node colours for G1 and Gg.
k-....,,k11 k-1 (t, WL.
( (u))) =
This means that (I, dL- cannot distinguish Gi and G2 after l iterations, which contradicts with the assumption. The proof is done.
Theorem 3.7. For any t N and d N. N, dL and M dL have the same expresivity distinguishing non-isomorphic graphs.
Proof. Lemma 4 and Lemma Jogetteerr prove this theorem.
C.4 PROOFS FOR CONNECTIONS TO W- HIERARCHY (THEOREM 3.8)
Theorem 3.8. (1, is equivalent 1-WI. in distinguishing non-isomorphic graphs.
Proof. (1, (WLL has f = and d = 1. Accordingly, the node colouring function in Equation for M (1, 1)- can be expressed as
(+) = HASH (d(2), (I)(w)) (d(()) Ni(w)
We may remove ( since occurs twice the input of the above hash function and does not add addition! information. This leads to the following simplified expression:
( HASH(s'(u), (v)( E N())).
which is exactly the same the node colouring function of 1-WI..
30

---

Published as a conference paper at ICLR 2023
C.5 PROOFS FOR GRAPH NEIGHBOURHOOD NEURAL NETWORK HEOREM 4.
Theorem 4.1. G3N-(1, d) with injective COMBINE and AGG functions, an injective AGG function w.r.t multisets of subgraphs with the same isomorphism and positional types, an injective graph readout function, and sufficiently many layers is as powerful as ./ (tt,, (t, d)-WL.
Proof. The proof can proceed similarly to the proof that GIN is expressive 1-WL (Xu et al. 2019). Let G1 and G2 be any two non-isomorphic graphs which can be distinguished by M (t, (t,d)-WL. the k-th iteration. It suffices show that G3N's neighbourhood aggregation scheme described in Equation 5] with the above assumptions is able to map G1 and G2 into different multisets of node features. The G3N's neighbourhood aggregation scheme is restated as
h/ COMBINE (H(-1), AAG (i.))xx (AGO" (est-"(()) (POOL(S))))
According Equation dt, applies an injective hash function HASH(-) update the node colours at the 1-th iteration:
('()) HASH((""²(u), (L) ((rahs)
where ((u,i.) = (S)- E S(u,id) freo (S)= and (S)
Below, we need to show that there always exists an injective function f such that to = f(s((()) for any iteration 1. We prove this by induction.
When / 0, both 1 and (u) are the input node feature node a. Thus, 1 = (u) holds for any node in G1 and G2.
Assume that ha (t-1) (u)) holds, need to show that ha f(s'(u) holds. Firstly, we have:
( COMBINE (f(s' AGG (1.)exxJa (AGo" -es (POOL(S)))
Since assume that both COMBINE(.) and AGG injective functions and the composition of injective functions is injective, there exists some injective function such that
12 (s(
{ AcO" sEs (PoOL(S)) SEI..EJaa
(i, denotes the of l-order subgraphs within the d-hop neighbourhood of a node u with the isomorphism type and the positional type j at the (1-1)-th layer, we have (/u.1.,) (
Because S ((,
(( B- By the definition of subgraph colouring, i.e., ç² Sc - N such that ('())) (3()) iff (is) (ie)(S2) and fpos (Si) (S2). and the assumption that AGG (-) is injective function with respect to multisets of subgraphs with the same isomorphism and positional types, we further have the following:
M = of (s² (U)) bEL.Ee))
where g' is also an injective function. Thus, we have ha (1-1) = g' o (<()) and f = g' -1 Since g' and HASH are injective, and the composition of injective functions is injective, f is injective.
31

---

Published as a conference paper at ICLR 2023
At the k-th iteration, if (t, d) dL distinguishes G1 and G2 to be non-isomorphic, this implies that G1 and G2 differ in (u))u E V(G1) and (u)(u) E V( Then, G1 and G2 must also have different G3N's node embeddings at the k-th iteration due the injectivity of f. The proof is done.
D G3N MODEL ARCHITECTURE
Here we describe the specific G3N layer in more detail. An instance of Equation 5 we employ is as follows:
h ((+1) =0 h(0 =
Σ
(ba)
!
Σ
h w Σ WE
(3,5)
(14)
(K,)
SEs (K,s)
where ha E gd and (1+1)) Rd are learned node embeddings each layer, and excluding sub- and superscript notations, W E Rd are learnable linear transformations and a are learnable scalars corresponding to different isomorphism and positional types of subgraphs. Furthermore, any nonlinear activation function such as sigmoid or ReLU.
Matching the notation described earlier EEuation 5] the pooling function for subgraphs can be defined by any permutation invariant pooling function. Here, given subgraph S E s(() (), we have
Enow (1,)
POOL(S) =
(15)
WES
In practice, we may also consider component-wise product over node embeddings in a subgraph: POOL(S) Oves a (1g (W(!)) (i.)) In this case, has to be bounded activation function such as
sigmoid in order to ensure numerical stability. The inner aggregation step AGG simply sums up all the subgraph emheddings of the same isomorphism and positional types, while the aggregation step A applies weighted sum with learnable weights the aggregated groups of subgraph embeddings the same isomorphism and positional types. To match expressivity of -WL, one may replace the outer activation function a with an MI.P and replace W(O) with e()), where e!!) learnable scalar parameter, seen in GIN Xu et al. 2019).
However, we found that using different learnable linear transformations for all possible isomorphism and positional types leads to much slower training. For example, if we had number [Jal of positional types and a number [/] of isomorphism types, this would lead to [1] x |Jzl possible combinations of linear transformations, resulting in longer training and higher generalisation gap due to the large number of parameters. To remedy this problem, we instead only use different weight matrices for positional types only, and inject the isomorphism type information additional features to node emheddings. For example, we change Equaii/Euuation 14 to Equation 16 below
((+1)
h
Σ
an
Σ
(16)
(a
SES! (6.1)
where e; denotes a vector with entries all zero except one at the i-th component. Thus, we have a different pool function for subgraph embeddings but keep all other components the same:
(h k.)w)
PooL(S) =
(17)
WES
32

---

Published as a conference paper at ICLR 2023
In the implementation. apply pre-processing step compute all indices of induced neighbour- hood subgraphs with respect to their isomorphism and positional types and store all these indices, which are used by G3N layers described in Equation 5 This pre- pre-processing step is only required to perform once on each dataset.
For isomorphism types, nauty algorithm (McKay] 1981 Mckay & Piperno] 2014). When S 3, for efficiency, we consider a simple way determine isomorphism types which count edges and nodes of subgraphs. In order to preserve structural information, initial colours of nodes are treated as being the same in the computation of isomorphism types.
compute them generally for any t-order subgraphs using the McKay's
For positional types, we implement fpos as follows. Let S be an induced subgraph in the d-hop neighbourhood of node u. Then fpos(S is the set of shortest-pali distances of the nodes in $ to the node u, i.e., fpos (S) = {p(u, 2) V(S)). where refers to the shortest- paartest-pathh distance between nodes u and v. For example, p(u, 02) = 1 and p(u, vz) 2. then the positional type of S is fpos (S) -1, 2 in this case.
has three nodes V(S) = {vi, U2 23) with p(u, u1
Remark D.I. In our work, the definition of positional types for induced subgraphs (via the function fooe) is intended to characterise two general conditions that are required at the minimum to establish the proposed strong hierarchy: (1) permutation invariant; (2) the condition specified Equation Thus, in general, there are many different ways to instantiate the function f for positional types implementation, as long as spos permutation invariant and satisfies the condition specified in Equation 2
There model variants in G3N implementation: is aggregate all connected-herediin hereditary subgraphs of order up to I, corresponding to the node colouring function defined by Equation 4]as discussed in Section 3.2 and the other aggregate all (-order subgraphs regardless of connectivity, corresponding to the node colouring function defined by [Equation In our experiments, we consider the former one the default model, unless otherwise stated.
E EXPERIMENTAL DETAILS AND RESULTS
In the following, provide the further information about the datasets, baseline methods, and parameter selection considered in our experiments as well as additional experimental results.
E. DATASETS
Table 7 summarises the dataset tasks and the statistics of the datasets used in our experiments.
Table 7: Dataset statistics.
Datasct
Task type
#Classes
#Graphs
Avg. #nodes
Avg. #odges
Avg. diameter
graphSc
Isomorphism
11117
11117
28.8
2.7
EXP (iso ver.)
Isomorphism
1200
1200
44.4
110.2
7.1
SR25 (iso ver.)
Isomorphism
15
15
25
300
2
CSL (iso ver.)
Isomorphism
41
164
6
RandomGraph
Regression
5000
18.8
62.6
4.2
MUTAG
Classification Classification
2
188
17.9
19.8
8.2
PTC-MR
2
344
14.3
14.7
7.5
PROTEINS
Classification
2
1113
39.0
72.8
11.3
NCTI
Classification
4110
29.9
32.3
11.5
IMDB-B
Classification
2
1000
19.8
96.5
1.9
IMDB-M
Classification
3
1500
13.0
65.9
1.5
7INC
Regression Classification Classification
12000
23.1
49.8
12.5
MolHIV
41127
25.5
27.5
12.0
MoITOX21
2
7831
18.6
19.3
9.6
33

---

Published as a conference paper at ICLR 2023
E.2 BASELINE METHODS
In our experiments on synthetic datasets, we compared the performance of G3N against the following baseline methods: MLP, GCN (Kipf & Welling 2017), GAT |Velickovic et al. 2017). GIN (Xu al. 2019), and PPGN (Maron et al. (019a).
In our experiments for real-world datasets, we considered the following baseline methods:
For the TU datasets, compared G3N against (1) three kernel methods RWK Gärtner
et al. 2003), WL-kernel (Shervashidze et al. (0011, 1, and P-WL (Rieck et al. 2019) (2) five
GNN models PATCHY-SAN (Niepert al. 2016)), DCNN (Atwood & Towsley 2016).
DGCNN (Zhang et al. 2018), GIN (Xu et al.
2019). and PPGN (Maron et al. 2019aa)
For the ZINC and MolHIV datasets, we compared G3N against GCN (Kipf Welling
2017), PPGN (Maron et al. 2019a), GIN (Xu al. 2019), PNA (Corso et al. (2020), DGN
Beaini et al., 2021). DEEP LPR (Chen et al. 2020). GSN (Bouritsas et al. 2022) and CIN
Bodnar al. 2021a
E.3 PARAMETER SELECTION
Synthetic datasets. We follow the experimental setup described by Balcilar et al. (2021)
For the EXP, SR25, graph8c, and CSL datasets, we run 100 randomly initialised weights on the models and record pairs of graphs to be similar if the L1 distance of the length 10 graph representations is less than 0.001 on any of the runs. All models are constrained to a 30K parameter budget, consisting of 4 convolutional layers, sum readout, and one final linear layer.
For the RandomGraph dataset, all models are also restricted to a 30K parameter budget, consisting of 4 convolutional layers, readout, and further fully connected layers trained for up to 200 iterations with a fixed learning rate of 0.001. Learning terminates when error goes below 10-4
TU datasets. Following the setup from Xu et al. (019). model evaluation and selection are done by collecting the accuracy from the single epoch with the best volss-valiationn accuracy averaged over the 10 folds. We fix t 2, d 2, hidden units of 128 and learning rate of 0.001 which is halved every 50 steps. Table 8 summarises the hyperparameters used in our experiments for these datasets.
ZINC. We follow the setup deseribed in Dwivedi et al. (2020) with batch size 128 and 1000 epochs with initial learning rate of 10-3 which halved when validation does not improve over after 20 steps and training is halted when the learning rate goes under 10-5, We fix 2, d 3 and by adhering to the 100k parameter budget, we use 4 message passing layers with hidden size 80, followed by final MLP readout.
MolHIV. We follow the train, validation and test split from Hu et al. 2020 and evaluate on the test and set the batch size be 128,
score corresponding to the best validation score. We fix 2, hidden dimension 128, number of message passing layers 3, 100 epochs with a fixed learning rate 10-3 and dropout ratio 0.5.
MoITOX21. We follow the train, validation and test split from Hu et al. (020) and evaluate on the test score corresponding to the best validation score. We set the batch size be 64, hidden dimension 300, number of message passing layers 4, 100 epochs with a fixed learning rate 10-3 and dropout
ratio 0.5.
Table 8: Hyperparameters for TU datasets.
Dataset
MUTAG
MR
PROTEINS
NCT1
IMDB-B
IMDB-M
#Layers
2
4
2
5
2
Drop ratio
0.1
0.5
0.75
0.1
0.5
0.5
batch size
64
32
64
32
64
64
#Epochs
200
300
200
200
200
200
34

---

Published as a conference paper at ICLR 2023
E.4 ABLATION STUDY
Setup. We analyse the effect of 1. and d on the expressivity and generalisability of G3N. We run all different configurations of {1,2,3},d datasets ZINC and MolTOX21. An initial learning rate is set to 10 and is halved when validation does not improve over 20 patience steps and training halted when the learning rate goes under 10-5 The results are reported in [Table and Table 10
21, and number of layers [3, 4,53 on the
Table 9: Test MAE (average test score) and generalisation gap (test score train score) on ZINC for different configurations of and d. The results show that d' is more important for performance on ZINC.
Test MAE
Generalisation Gap
#I Laaerr
3
5
0.353
0.32420.017
0.29225.019
0.131#+0.26
0, 0.13920.027
0.147
t= 1
d = 2
0.305#0.020
0,258#0.012
0.240
0.161#00013
0.142+0.018
0.140=00007
d == 3
0.187#00004
0.191=t0.007
0.194#0.006
0.083++00014
0.101
0.094+00016
d -=] 1
0.328#0.022
0.361#0.000
0.377=0.000
0.102++0.22
0.09440.010
0.129#0.013
1= 2
d = 2
0.337=0.008
0.282:t00199
0.258=20021
0.132+#0.24
0. 1..
0.133#00014
3
0.182+0.003
0.176::0000
0.185##.008
0.076#0.003
0.088#0.006
0.090=a0014
1
0.370#0.005
0.362
0.357=0.023
0.127
0. 106+0.0100
0.131
t=3 3
2
0.341#00011
0.328
0,312
0.133:t0.019
0.1 130#0.017
0.119=00010
d = 3
0.176=20007
0.175:200007
0.182=t.010
0.072+t.011
0.074
0.077#00009
Table 10:
Test ROC-AUC (average test score) and generalisation gap (test score train score) on MoITOX21 for different configurations of and d. The results show that is more important for performance on MolTOX21.
Test ROC-AUC (%)
Generalisation Gap
#1 .ayers
5
3
t
0.7363220.06
0..433*+0.00
0.7398=00000
0,1476=#0.03
0.1303+0001
06133:320:11
d d=1
t == 2
0.7402220.03
0.7565#0.006
0.7482#0.006
0.13399#0.002
0.1 1462#0001
0. 11135000000
t 3
0.7487=20000
0.764920.107
0.7531
0.1171#0.001
0.0734+0.009
0.093440.003
t t=] 1
0.736520.013
0.7400s60009
0.7553
0.1364200.02
0.0
1.6000
d=2
t= 2
0.7426*20.009
0.75144#0.000
0.7603=2.009
0.1352+#0.04
0.0994#0.003
0.0965#0.002
{ --3 3
0.749620.019
0.7636200009
0.7657=1.006
0.1296220006
0.0773+0.016
0.090020:016
t= 1
0.7443+t0.07
0.751 1 +000007
0.7494220000
0.1364220.003
0.126440..03
0.1390#0.004
d=3
t=
2
0.753 +0.005
0.7593#5.001
0.7577=0.008
0.1203=au.00
0.093440.009
0.0996#0.007
3
0.758620.006
0.7695=2.007
0.7608
0.1006=00.055
0.0656:0.013
0.0831
Observations. We observe that inereasing the size of subgraphs t the size of the receptive field generally increase expressive power and reduces generalisation gap. This supports the theoretical results with the higher expressive power of -WI. for higher or higher d. One reason the generalisation gap is lower is because graph structure becomes more important for learning than node features with G3N which prevents overfitting. Further, according to the Table 9] a higher number of layers is required for expressivity for lower values of d and vice versa. This is because the total receptive field of each node with L layers of G3N is d L, thereby requiring a balance of d and L to receive enough information from far away nodes in graph. Moreover, according to Table 10 can obtain higher expressive power by increasing the size / of subgraphs since this can lead to capturing more local structural information into node embeddings.
E.5 RUNTIME AND MEMORY ANALYSIS FOR / AND d
Setup. Here we present empirical analysis of the runtime and memory usage of G3N as the neighbourhood size d and the order of subgraphs increase. We measure resource usage by varying and while fixing all other hyperparameters. All model configurations include 4 message passing
35

---

Published as a conference paper at ICLR 2023
Table 11: Runtime measured by seconds per epoch on ZINC (molecular dataset) and IMDB-B (social network dataset) with parameter budget of approximately 30k. A message passing neural network (MPNN) is modelled by G3N with meaning that d 2, 3 use the same resources. OOM represents out of memory.
The IMDB-B graphs have maximum diameter
ZINC
IMDB-B
runtime (s/epoch)
#parameters
runtime (s/epoch) #parameters
MPNN
0.4
32607
0.1
33758
GNNML3
4.3
33309
0.4
34537
PPGN
3.7
32417
0.6
32009
G3N-(2,1)
0.6
31631
0.2
32938
G3N-(2,2)
1.1
31759
0.4
33018
G3N-(2,3)
1.6
31051
G3N-(3.1)
0.5
32911
1.6
33578
G3N-(3,2)
1.6
31601
OOM
OOM
G3N-(3.3)
2.5
32079
Table 12: Runtime and number of parameters for G3N on ZINC (molecular dataset) and IMDB-B (social network dataset) with 4 number of layers and hidden dimension of 64. The IMDB-B graphs have maximum diameter 2, meaning that d = 2, 3 use the same resources. OOM represents out of memory.
ZINC
IMDB-B
runtime (s/epoch)
#parameters
runtime (s/epoch) #parameters
MPNN
0.4
23619
0.1
53198
GNNML3
4.4
120077
0.4
122601
PPGN
3.9
91329
0.8
138753
G3N-(2,1)
0.7
32581
0.2
71122
G3N-(2,2)
1.2
50505
0.5
106970
G3N-(2,3)
1.7
68429
G3N-(3,1)
0.6
23875
1.7
72146
G3N-(3,2)
1.7
60747
OOM
OOM
G3N-(3.3)
2.5
97619
layers and hidden dimension adhering to 30k parameter budget for runtime analysis, and hidden dimension of 64 for memory analysis. Furthermore, we run experiments on two different datasets ZINC and IMDB-B which have different settings and graph densities: ZINC consists of molecular graphs with average graph density 0. 0.195 and diameter 12.47 which are sparser than the IMDB-B social networks with average graph density 0.520 and diameter 1.86, and max diameter We further compare against GNN models with 3WL expressivity: GNNML3 (Balcilar et al. 2021 and PPGN
(Maron et al. 2019a). The implementations are taken from Balcilar (202 The experiments for this section were run on an RTX 3090 GPU.
Observations. Viewing the results in Table II we notice that for sparse graphs the order of magnitude for runtime stays the same even when d and are increased up to 3. On the other extreme when graphs are small and dense, runtime increases number of connected components in neighbourhood grows large can be seen with d = 2 on the IMDB-B dataset which results global aggregation. For t 3, this results memory issues from computing all 3-order subgraph indices. Note that the runtime for (4 (2, 1) is greater than for (t. d) (3, 1). This because all 3-order subgraphs in 1 hhhpp neighbourhoods have the same positional type, whereas there
greater rate as and increase, given that the
positional types of 2-order subgraphs in the given datasets. We further note that runtime performance comparable with the higher order GNN methods with the exception on the IMDB-B dataset where model performs aggregation whole graphs.
36

---

Published as a conference paper at ICLR 2023
On the other hand in Table 12 we note that the parameter usage increases more moderately regardless of dataset structure, as the parameters are bounded by up to 5 times the parameters used in the message passing version of G3N. This is because the number of parameters scales with the number of isomorphism types, which are modest for connected components and small and t.
We further note from both tables that the main computation effort arises from varying d and and not the number of parameters of the model as expected.
E.6 RUNTIME ANALYSIS FOR CONNECTED VARIANTS
Table 13: Runtime measured by seconds per epoch and MAE on ZINC with a parameter budget of approximately 100k G3N with aggregation variants: connected t-subgraphs only, connected- hereditary subgraphs, and all t-subgraph.
connected
connected-hereditary
all
runtime(s/epoch) MAE
2.5
4.2 0. 0.174+0.002
5.5
0.16540.006
0.226+0.009
Setup. We further present empirical analysis of the runtime and performance of G3N on the ZINC dataset with various aggregation variants depending on which subgraph types it aggregates. Specifically, consider the original G3N which aggregates only connected (-order subgraphs, G3N which aggregates connected-hereditaee
subgraphs discussed in Section 3.2, and G3N which aggregates all t-order subgraphs regardless of connectivity. The message G3N layer equations given in Equation 14] and Equation 16 remain unchanged for all connectivity variants with the except of the definition of S (i, which consists of the set of all induced subgraphs from the neighbourhood of a node u being restricted to connectivity variants discussed above.
The parameter setup for all three variants consists of the same setup with the ZINC experiments above. Specifically, we have a batch size 128 and an initial learning rate of 10-3 which is halved when validation does not improve over after 25 steps and training is halted when the learning rate goes under 10 10-5, We fix t = 3, d = 3 with 2 message passing layers and fix the number of hidden units such that we adhere to 100k parameter budget. We use an MLP readout. The experiments for this section were run on RTX 3090 GPU.
Observations. From Table 13 we observe that the runtime of all the G3N variants have the same order of magnitude. By considering connected-herediing there are fewer isomorphism types to consider for the given dataset. Note however, that this does not hold in general and that there exist graphs where considering connected-hereditary subgraphs is less efficient, such as with cliques. We further note that the connected conmected-hereditarry variant provides better performance which may be attributed to the fact that by considering all possible isomorphism types regardless of connectivity, we may lose information in the training process as to which structures are actually helpful for prediction. This is given by the intuition that connected components should have a greater contribution for predictions. Finally, we note that considering connected f-order subgraphs only as opposed to
subgraphs, we achieve lower runtime as
subgraphs (all k-order subgraphs for < k S t) obviously provides faster runtime but more significantly provides similar performance. This may be attributed the fact that larger t-order subgraphs in the given dataset generally subsume smaller subgraphs in providing structural information for prediction.
E.7 COMPLEXITY ANALYSIS A-WL vs WWL
Serup. We conduct an experiment to empirically analyse the time complexity of our -WL algo- rithms, in comparison with the classical k-WL algorithms. In the experiment, four datasets ZINC, MolHIV, NCII, and IMDB-B are selected, which have varying graph structural information, such as the sparsity of a graph, the diameter of graph, etc. For each dataset, we randomly select 10 graphs.
We compute the average complexity of k- and - -WI as follows: (1) for k-WL, we compute n' (t rz) where = k. This is because k-WL considers the number n² of k-tuples in a graph G with |V (G)l = n and there are further (k n) neighbouring k-tuples considered for colouring each of such k-tuples. (2) for -WL, we compute x (s") where refers to the number of nodes to be
37

---

Published as a conference paper at ICLR 2023
d
1
2
d 3
10
10t3
10ah
Complexity
k-WL
10
1000
107
10
10a
10a
4
2
5
6
t
Figure 10: ZINC
d
d 3
.f-WL
10tB
10t3
Complexity
10a2
k-WL
1010
10
10a
107
107
10a
10
2
4
6
7
8
2
3
5
7
8
3
4
6
8
Figure 11: MolHIV
d
= 2
d
=
10
>-WL
1017
10
Complexity
k-WL
10a2
1013
10th
10a
10a
10a
10a
10a
105
6
Figure 12: NCI1
d = 1
d = 2
d = 3
.W-WL k-WL
10
10a3
10
Complexity
10
10
10
107
10a
10a
10a
Figure 13: IMDB-B
38

---

Published as a conference paper at ICLR 2023
coloured in graph and (e") approximates the number of neighbouring subgraphs of order within the local d-hop neighbourhood of a node. The results are reported in Figures 10
11
12 and 13
Observations. From these figures, we observe the following:
When d = 1, for graphs with relatively large diameters such ZINC, MolHIV, and NCII, as shown in Figures 10 11 and 12 our Y algorithm is several orders of magnitude faster than the k-WL algorithm. We can see that the performance gap between k-WL and -LL becomes more and more significant when / increases and becomes stable after 4. This is because the number of I-hop neighbours a' is much smaller than the total number of nodes n in a graph (i.e., a' < n)) For graphs with very small diameters such as IMDB-B, all the nodes are almost within 2-hop of a node; therefore, the number of 1-hop neighbours a² is relatively closer to the number of nodes n in such graphs. In this case, as depicted in Figure 13 the performance gap between k- WL and - becomes small.
When d = 2, for graphs with relatively large diameters such as ZINC, MolHIV, and NCII, as shown in Figures 10 11 and 12 N -WL still shows significant performance improvement over k- WL and the performance gap starts to increase after t 4. The increase in the complexity of -WL for t [1, 2, 3] is due to the effect of including 2-hop neighbours along with 1-hop neighbours; after = 4, the size 2-hop neighbours |a²| and parameter t start to approach each other which results in an increased performance gap. For IMDB-B dataset with a very small diameter, as shown in |Figure 13) almost all the nodes in the graphs are within 2- 2-hop (i.c., a n) and the time complexity of our algorithm increases for initial values of t and then start to stabilizes or decreases as compared to k-WI..
When d = 3, the value of ad gradually approaches the total number of nodes in a graph. In such cases, ./' -WL remains significantly faster on graphs with relatively large diameters, as shown in Figures TO. 11 and [22 and also shows to outperform well for graphs with small diameters with k-WL. shown in Figure 13 The performance gap still becomes larger with the increased values of parameter l.
Overall, due to the local nature of the -WL algorithm in contrast to the global nature of the k-WL algorithm, the -WL algorithm is much more efficient than the k-WL algorithm when performing on graphs with reasonably large diameters, particularly if diameters are greater than values. The performance gap between the -WL algorithm and the k- algorithm is reduced when increasing d or graphs have very small diameters, e.g., IMDB-B has an average diameter 1.9.
Remark F.1. The complexity of -WL can be reduced when the gap between and al gets smaller.
This is because the number of induced subgraphs (ee) may decrease in this case. For instance, we can see from Figure 10 that when d = 1 and t = 4. the complexity is lower than the one at d = 1 and t t= 3: then it stabilises when d = 1 and t > 5. Similar cases can be observed from Figure 17 and
Figure 12
F LIMITATIONS AND FUTURE WORK
In this work, the design of G3N still has some limitations. Firstly, as with most expressive GNN models going beyond 1-WL, G3N suffers from inevitably increased runtime per training step and parameter complexity. Although seen to be feasible for sparse molecular graphs, this may still pose an issue with much larger datasets. To solve this issue, one may have to consider sampling methods. Another issue is with an unclear explanation on the gap between expressivity and generalisability. Finally, although G3N able to detect graph substructures contrary methods which precompute and inject them as additional features for learning, the parameters d and / are still domain dependent and will have to be hand chosen to balance computational resources and performance. Due to these limitations, one interesting future research direction is to explore the underlying design princi- ples of expressive GNN models for a better understanding of the interaction between expressivity, generalisability, explanability, and training efficiency of GNN models.
From the algorithmic perspective, for both k-WL and .'- -WL, a possible future research direction is to analyse their connections to node-level, link-level, or more generally subgraph-level properties and accordingly build connections between subgraph properties and expressivity of GNN models. In the literature of the k- algorithms, despite their fruitful connections to logic and descriptive
39

---

Published as a conference paper at ICLR 2023
complexity theory, there is no clear understanding for characterisations of subgraph patterns whose counts and occurrence are higher-order k-WL invariant (Kiefer 2020). fact, traditionally, the k-WL algorithm is mainly used as combinatorial tool in graph isomorphism tests and little work has been done to study the applicability of 4-WI. to recognition of graph properties rather than to testing isomorphism (Fuhlbrück et al. (02T). Further, study the formal properties of the -WWW algorithms by exploring the connections between the -WL hierarchy and logic is needed.
40


Reviews:
[{"review_id": "bZcBekJNBL1", "reviewer": "Reviewer_YCJN", "summary": "", "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": "", "summary_of_the_paper": "This paper studies the expressive power of graph neural networks from a different angle than the classical $k$-WL hierarchy. Authors argue that $k$-WL is not very well-suited for developing new graph neural network architectures since (i) these algorithms are already computationally demanding with $k\\geq 2$, (ii) this hierarchy is not ``granular enough'' to capture graphs that lie between $1$-WL and $3$-WL, and most importantly (iii) $k$-WL algorithms rely on computations over $k$-tuples (and associated neighbourhoods), which are not local, and this does not align with the initial motivation of graph neural networks which aggregate information locally. Based on these (and similar) observations, authors propose a new hierarchy of graph isomorphism tests, coined as Neighbourhood-WL ($N$-WL)\nalgorithms. They prove that this is a proper hierarchy and introduce Graph Neighbourhood Neural Network (G3N) based on\nthe $N$-WL algorithms, and report empirical findings.", "summary_of_the_review": "I agree with many points of the paper, but I am not convinced that this class of algorithms is the way forward. It is also unclear to me whether, or to what extent, this study improves our understanding of the field.", "strength_and_weaknesses": "Strengths:\n\n- The study of expressive power of GNNs is important, and there is a value in looking beyond the WL hierarchy in designing novel models.\n- Looking at multi-hop neighbourhoods in aggregation is at the core of this work, which is well-understood concept with potential benefits/\n\nWeaknesses:\n\n- The paper is hard to follow: For example, it is not immediately clear what the parameter $t$ exactly stands for in $N(d,t)$ and why it is important. It is stated relatively early that this is the size of the induced subgraphs, but there is no justification as to why this parameter needs to be controlled. In my understanding, this is due to computational inefficiency: the proposed class of algorithms enumerate all subgraphs of order $t$ within a $d$-hop neighbourhood, and this should be clearly stated. \n\n- The paper is not very well-placed in the literature. Authors have an extensive related work (a bulk of it is in the appendix, which is not a great practice in my opinion), but there are no concrete connections to other well-known concepts: To elaborate on this:\n\n   -  $N(d,t)$ algorithms operate over $d$-hop neighbourhoods, which are defined using shortest path distances. Authors hint to the fact that that the class of $N(d,t)$ algorithms may not be a natural choice, since increasing $d$, while fixing $t$ does not necessarily yield more expressive power. They propose to use the positional information in the respective hops, which leads to a more intuitive class of algorithms: In my opinion, this is the right way of using the shortest path kernel within the algorithm. This paper builds on this idea to use positional info in the induced subgraphs, but the connections are not explored/explained. \n\n   -  It is not very clear whether one gains more by using the induced subgraphs, as compared to just using multi-hop aggregation (which also has strictly more expressive power than 1-WL and generally incomparable to the hierarchy). The presented ablation study confirms the role of $d$, but the same cannot be easily claimed for $t$.\n\n   -  Authors are understandably critical about the $k$-WL hierarchy, but this is not always well-calibrated. I suggest authors tone these statements differently. There are many well-known connections between $k$-WL hierarchy and logics, which precisely inform us about the formal properties of these algorithms.\n\n   -  There are many local variants of $k$-WL algorithms which are proposed with similar intuition: instead of aggregating over all $k$-tuple neighbourhoods, these algorithms only look at $k$-tuples within a local neighbourhood, which is not far away from the intuitions presented in this paper. The connections need to be discussed in depth, clarifying whether the proposed model has advantages over local WL algorithms.\n\n\n- In the actual model, authors inject isomorphism types into node features (which is different than operating over isomorphism types), quoting the authors: ``However, we found that using different learnable linear transformations for all possible isomorphism\nand positional types leads to much slower training. ... To remedy this problem, we instead only use different weight matrices for\npositional types only, and inject the isomorphism type information as additional features to node embeddings.\"\n\n- The given review time is not sufficient to check the proofs in detail. The theorem statements are not very specific: It should be stated what is fixed, and how the other parameter ranges. It is also unclear whether the statements are over the class of all graphs, or just over graph pairs. The WL hierarchy is an infinite hierarchy: Is the same true here? \n\n- WL algorithms can be used to analyse node-level, or link-level properties, and the same applies here, but it is unclear to me, e.g., under which conditions $(G_1,u)$ can be distinguished from $(G_2,v)$. I understand if this is left as future work, but it is important to highlight.\n\n- The runtime of these class of algorithms is also prohibitive, and using a small $t$ seems the only way around the issue. I am not convinced that this new class of algorithms suggests a promising direction. \n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ay1pt6rzmj", "reviewer": "Reviewer_rk5R", "summary": "", "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": "", "summary_of_the_paper": "The paper introduces a new family of isomorphism testing algorithms based on the WL tests hierarchy called Neighborhood-WL ($\\mathcal{N}-$WL). Similarly to the WL test, the proposed algorithms iteratively refine a node coloring to determine whether two graphs are isomorphic. The difference from the WL test is that the node coloring is updated by aggregating the colors of subgraphs of size $t$ in the node’s $d$-hop neighborhood. The authors show that the parameters $(t,d)$ induce a strict hierarchy of isomorphism testing algorithms and further suggest and prove equivalence to a more computationally efficient variant aggregating a connected heredity neighborhood. Inspired by the $\\mathcal{N}$-WL hierarchy, the authors propose a corresponding GNN design that can match the expressive power of $\\mathcal{N}$-WL tests.\n\n", "summary_of_the_review": "The paper provides a well-defined new hierarchy of isomorphism testing hierarchy. I find this construction elegant, and the generality of the suggested framework is appealing. My main concern regarding this work is the lack of discussion of the relation to K-hop GNNs that share many ideas with this work. Furthermore, [1] somewhat overlaps with this work, and an elaborate discussion on that is also required. \n\nI rate this paper as marginally below the acceptance threshold but would reconsider it upon clarifying and addressing my concerns. ", "strength_and_weaknesses": "### 1. Strengths\n\n- The paper proposes a new isomorphism testing hierarchy. \n- The authors provide a thorough theoretical characterization of the suggested hierarchy - expressivity, connection to WL tests, and complexity. \n- The paper introduces a flexible and general GNN architecture design based on the $\\mathcal{N}$-WL hierarchy.\n- An extensive experimental evaluation and ablation study is performed.\n\n### 2. Weaknesses\n\n#### \t1. **Relation to K-hop GNNs** - \n[1] analyses the expressive power of K-hop GNNs which basically, similar to this work, aggregate information from the k-hop neighborhood of each node and use this information to update the node's color at each iteration. In [1] they show that K-hop GNNs' expressive power is bounded by the 3-WL test. They further suggest a variant of K-hop GNNs to increase the expressive power, called KP-GNNs. I find the idea in KP-GNNs very similar to the addition of the positional types in the current work. \n\n#### \t2. **Experimental Results** - \nThe experimental results, as in many GNN papers, justify the theoretical statements but do not exhibit any significant improvement in real-life datasets. Furthermore, I find the comparison on the ZINC dataset rather lacking (see Table 5 in [1]).\n\n#### \t3. **Name of the paper** - \nThe name of the paper is quite general and does not reflect the properties of the proposed hierarchy. I would suggest changing it to something of the flavor \"Neighborhood WL hierarchy of expressivity for graph neural networks\"\n\n[1] Feng et. al. [How Powerful are K-hop Message Passing Graph Neural Networks](https://arxiv.org/abs/2205.13328 ) (NeurIPS 2022) \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "VkPD7EPXXI", "reviewer": "Reviewer_e9AE", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This work tries to propose a new class of graph isomorphism testing algorithm, called Neighbourhood WL ($\\mathscr{N}$-WL), which stores complex information in low dimension, instead of using high-order tuples in $k$-WL. It develops two Neighbourhood WL algorithms with parameters ($t$,$d$) and theoretically discusses whether the algorithms gain expressivity with parameters increased. Then, to reduce complexity, it further develops a connected-subgraph version of $\\mathscr{N}$-WL and its GNN implementation. The proposed GNN model is evaluated on a number of synthetic and real-world experiments.", "summary_of_the_review": "For now, I would like to recommend ''below acceptance threshold'' due to the mentioned concerns. I am willing to raise my score if the concerns are addressed.\n\n=== Acknowledgement ===\n\nDue to time limit, I only read the main text and the proof of Theorem 3.1. Other parts in Appendix were not thoroughly checked.", "strength_and_weaknesses": "Pros:\n1. The discussion of related works in Section 2 and Appendix B is comprehensive.\n2. The theoretical arguments of weak-hierarchy-related $\\mathscr{N}^-$-WL and strong-hierarchy-related $\\mathscr{N}$-WL seem to be nice, with sufficient proof and counter-examples for general settings of parameters ($t$,$d$).\n3. The development from $\\mathscr{N}$-WL to its connected-subgraph version $\\mathscr{N}^c$-WL is great, accompanied with clear reasoning in Section 3.2.\n\nConcerns:\n1. I am a little confused by the definition of $f_{pos}$ under ''Strong Hierarchy''. Here are a series of questions:\n    * there is a parameter $d$ in $\\mathscr{N}$-WL. But there is again $\\forall~ d\\ge 1$ as the condition of ''... $f_{pos}(S_i)\\neq f_{pos}(S_j)$''. Is the second $d$ not related to the first $d$? \n    * Is $f_{pos}$ unique or universal for any target node $u$? If unique, it seems very complicated to parameterize the representation of $J_d$ in Eq(4). If $f_{pos}$ is universal: moreover, if the answer to the above question is ''not related'', then it seems $f_{pos}$ is coloring everything distinctly because the target node can be arbitrary.\n    * again, how is $J_d$ obtained in the model in Eq(4)?\n2. The compared baselines in the ZINC experiment are not enough, because it only includes PPGN as the GNN beyond 1-WL. For instance, GSN is missing, which is cited and discussed by the authors for many times. It would be great to see the comparison with more expressive GNNs to show the sufficiency and efficiency of the proposed model.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ERsoFx_AAP", "reviewer": "Reviewer_QGtL", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper proposes a new hierarchy of expressive isomorphism test algorithm and GNN model, with combining k-WL tuple idea and rooted subgraph idea from subgraph GNNs. More specifically, the author still work on subgraph GNNs with each node representing the encoding of d-hop rooted subgraph around the node. Unliking 1-WL encoding of the d-hop rooted subgraph, the author proposes to apply t-set extraction for the d-hop rooted subgraph which should be much more powerful than 1-WL encoding. The author proved strictly increased expressivity with respect to increasing t and d, under the help of positional information of every t-set. Furthermore, the author claim that one only need to consider (≤)t-set whose induced subgraph are connected, and it does not lose any expressivity. The corresponding GNN model is also designed, and the author conducts extensive experiments over several widely used benchmark datasets for evaluating expressivity. ", "summary_of_the_review": "The author proposes an interesting design of color updating isomorphism test algorithm, and study it theoretically. It would be further improved if its upper bound is studied or the connection to k-WL is much more clear. ", "strength_and_weaknesses": "**Strength**: \n1. Going beyong k-WL hierarchy is an important direction, as k-WL is not practical with k > 3.\n2. The designed hierarchy combines recently hot subgraph GNNs and k-WL, which is novel and an interesting angle.\n3. The author proved strictly increasing expressivity with respect to increasing d hop and t size, which is a great contribution in theory. \n4. I personally find that theorem 3.7 is the most interesting one, however I'm not fully convinced that the theorem is correct, as I cannot fully  follow their proofs. (This theorem can reduce a lot t-sets, which can greatly improve runtime. It's hard to believe that this won't lose expressivity. )\n\n**Weaknesses**:\n1. Although the proposed hierarchy has increased expressivity with d and t. It is not clear the upper bound expressivity of the method. And the connect to k-WL is not clear also. It's possible that its maximum expressivity is limited.  \n2. The proof of theorem 3.7 is questionable. \n3. The runtime analysis shows that the method is faster over sparse graph, but for denser graph this can be very slow.\n4. When d is large, the computational cost can be closer to k-WL (its set version) for extracting all t-tuples. The main difference to k-WL will be that the intermediate representation is size n instead of size n^t. \n5. The experimental result over real-world datasets is not very good, this may suggests the expressivity upper bound of this method is limited. \n\n**Missing Reference**:\nStudying an improved expressivity hierarchy has been explored. The paper [Zhao et al. NeurIPS 2022] improved k-WL by using ≤k sets and studied its expressivity theoretically. The theorem 8 in [Zhao et al. NeurIPS 2022] is similar to the paper's Lemma 3.6 and has connection to Theorem 3.7. They also used connected components. I suggest the author to have a check. \n\n**Additional Suggestion**:\nAs mentioned above, the proposed hierarchy is under the rooted subgraph WL presented in [Zhao et al, ICLR 2022]. The difference would be improving encoding of rooted subgraph with higher-order sets. The original paper uses 1-WL to encode rooted subgraph, which has overall expressivity upper bounded by 3-WL [Frasca et al. NeurIPS 2022]. It would be interesting to know that assuming we have the most expressive rooted subgraph encoder, what is the expressivity upper bound of the rooted subgraph WL? This upper bound would also be the upper bound of the proposed hierarchy. The author needs to study the upper bound of the proposed hierarchy to see whether it can achieve universality. \n\n[Zhao et al. NeurIPS 2022] A Practical, Progressively-Expressive GNN, https://arxiv.org/pdf/2210.09521.pdf.   \n[Zhao et al. ICLR 2022] From stars to subgraphs: Uplifting any GNN with local structure awareness.   \n[Frasca et al. NeurIPS 2022] Understanding and extending subgraph gnns by rethinking their symmetries.   ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster