Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
Authors: Giorgos Bouritsas
Fabrizio Frasca
Stefanos Zafeiriou
Michael M. Bronstein
Venue:  (2021)
Keywords: graph neural networks
graph representation learning
network analysis
network motifs
subgraph isomoprhism

Abstract: While Graph Neural Networks (GNNs) have achieved remarkable results in a variety of applications, recent studies exposed important shortcomings in their ability to capture the structure of the underlying graph. It has been shown that the expressive power of standard GNNs is bounded by the Weisfeiler-Lehman (WL) graph isomorphism test, from which they inherit proven limitations such as the inability to detect and count graph substructures. On the other hand, there is significant empirical evidence, e.g. in network science and bioinformatics, that substructures are often informative for downstream tasks, suggesting that it is desirable to design GNNs capable of leveraging this important source of information. To this end, we propose a novel topologically-aware message passing scheme based on substructure encoding. We show that our architecture allows incorporating domain-specific inductive biases and that it is strictly more expressive than the WL test. Importantly, in contrast to recent works on the expressivity of GNNs, we do not attempt to adhere to the WL hierarchy; this allows us to retain multiple attractive properties of standard GNNs such as locality and linear network complexity, while being able to disambiguate even hard instances of graph isomorphism. We extensively evaluate our method on graph classification and regression tasks and show state-of-the-art results on multiple datasets including molecular graphs and social networks.

Under review as a conference paper at ICLR 2021
IMPROVING GRAPH NEURAL NETWORK EXPRESSIV- ITY VIA SUBGRAPH ISOMORPHISM COUNTING
Anonymous authors Paper under double-blind review
ABSTRACT
While Graph Neural Networks (GNNs) have achieved remarkable results in a variety of applications, recent studies exposed important shortcomings in their ability to capture the structure of the underlying graph. It has been shown that the expressive power of standard GNNs bounded by the Weisfeiler-Lehmaa (WL) graph isomorphism test, from which they inherit proven limitations such as the inability to detect and count graph substructures. On the other hand, there is significant empirical evidence, e.g. in network science and bioinformatics, that substructures are often informative for downstream tasks, suggesting that it is desirable to design GNNs capable of leveraging this important source of information. To this end, we propose novel topologically-wwar message passing scheme based on substructure encoding. We show that our architecture allows incorporating domain-specific inductive biases and that it is strictly more expressive than the WL test. Importantly, in contrast to recent works on the expressivity of GNNs, we do not attempt to adhere to the WL hierarchy; this allows us to retain multiple attractive properties of standard GNNs such as locality and linear network complexity, while being able to disambiguate even hard instances of graph isomorphism. We extensively evaluate our method on graph classification and regression tasks and show state-of-the-arr results on multiple datasets including molecular graphs and social networks.
INTRODUCTION
The field of graph representation learning has undergone a rapid growth in the past few years. In particular, Graph Neural Networks (GNNs), family of neural architectures designed for irregularly structured data, have been successfully applied to problems ranging from social networks and recommender systems (Ying al.
2018a) to bioinformatics (Fout et al. 2017 Gainza et al. 2020),
chemistry (Duvenaud et al. 2015 Gilmer et al. 2017] Sennhez-LLngellng et al. (211)) and physics (Kipf et al.) 2018 Battaglia al. 20166), to name few. Most GNN architectures
based on
message passing (Gimmer et al. (017). where at each layer the nodes are updated by information aggregated from their neighbours.
crucial difference from traditional neural networks operating on grid-structured data is the absence of canonical ordering of the nodes graph. To address this, the aggregation function is constructed to be invariant to neighbourhood permutations and, as a consequence, to graph isomorphism. This kind of symmetry not always desirable and thus different inductive biases that disambiguate the neighbours have been proposed. For instance, in geometric graphs, such as 3D molecular graphs and meshes, directional biases are usually employed order model the positional information of the nodes (Masci et al., 2015 Monti et al., 2017 Bouritsas et al. 2019 Klicpera et al. 2020 de Haan et al. 2020b); for proteins, ordering information used disambiguate amino-acids at different positions in the sequence (Ingraham al.) 2019): in multi-relational knowledge graphs, different aggregation is performed for each relation type (Schlichtkrull et al.. 2018).
The structure of the graph itself does not usually explicitly take part in the aggregation function. In fact, most models rely on multiple message passing steps as a means for each node to discover the global structure of the graph. However, since pressag-ppassing GNNs as the Weisfeiler Lehman test (WL) (Xu et al.) 2019 Morris et al.) 2019). they are limited in their abilities adequately exploit the graph structure, e.g. by counting substructures (Arvind et al. 2019
most powerful

---

Under review as a conference paper at ICLR 2021
Chen al., 2020). This uncovers crucial limitation of GNNs, substructures have been widely recognised as important in the study of complex networks. For example, in molecular chemistry. functional groups and rings are related to plethora of chemical properties. while cliques are related to protein complexes in Protein-Protein Interaction networks and community structure in social networks, respectively (Granovetter 1982 Girvan & Newman 2002).
Motivated by this observation, in this work we propose Graph Substructure Network (GSN), a new symmetry breaking mechanism for GNNs based on introducing structural biases in the aggregation function. In particular, each message is transformed differently depending on the topological relationship between the endpoint nodes. This relationship is expressed by counting the appearance of certain substructures, the choice of which allows us to provide the model with different inductive biases, based on the graph distribution at hand. The substructures are encoded as structural identifiers that are assigned to either the nodes or edges of the graph and can thus disambiguate the neighbouring nodes that take part in the aggregation.
We characterise the expressivity of substructure encoding in GNNs, showing that GSNs are strictly more expressive than traditional GNNs for the vast majority of substructures while retaining the locality of message passing, opposed to higher-order methods (Maron et al. 2019b cla Morris et al. 2019) that follow the WL hierarchy (see Section (2). In the limit, our model can yield a unique representation for every isomorphism class and is thus universal. We provide an extensive experimental evaluation on hard instances of graph isomorphism testing (strongly regular graphs), as well as on real-world networks from the social and biological domains, including the recently introduced large-scale benchmarks (Dwivedi et al. 2020; Hu et al. (2020). We observe that when choosing the structural inductive biases based on domain-specific knowledge, GSN achieves state-of- the-art results.
2 PRELIMINARIES
Let G = EV..Ea) be a graph with vertex set Ve and undirected edge set Eg. A subgraph =s= (Vas EGg) of G is any graph with Vo, C Va, Egs C Eg. When &gg includes all the edges of G with endpoints in VGg, i.e. EGs- = [(v, u) E : U, u E Vag). the subgraph is said to be induced.
Isomrrphssm Two graphs G, Hl are isomorphic (denoted H ~ G), if there exists an adjacency- preserving bijective mapping (isomorphism) f VG VH, i.e. (v, u) E &g iff (f(v), fw)) E Eh. Given some small graph H, the subgraph isomorphism problem amounts to finding a subgraph Gs of G such that Gg 2 H. An automorphism of H is an isomorphism that maps H onto itself. The set of all the unique automorphisms form the automorphism group of the graph. denoted as Aut(H) H)) contains all the possible symmetries of the graph. The automorphism group yields a partition of the vertices into disjoint subsets of Vμ called orbits. Intuitively, this concept allows us to group the vertices based on their structural roles, c.g. the end vertices of a path, or all the vertices of a cycle (see Figure D}. Formally, the orbit of vertex mapped via an automorphism: Orb(v)= = {u E VH : 3g E Aut(H) s.t. g(u) = v). and the set of all orbits H Aut (H) = (Orb(r)
VH is the set of vertices to which it can be
E Vn } is usually called the quotient of the automorphism
when it acts on the graph H. We are interested in the unique elements of this set that we will denote as (O),,, Oy o..,...., Oy OH,,
}. where di the cardinality of the quotient.
Analogously, we define edge structural roles via edge automorphisms, i.c bijective mappings from the edge set onto itself, that preserve edge adjacency (two edges are adjacent if they share a common endpoint). In particular, every vertex automorphism g induces an edge automorphism by mapping each edge {u, u} to (9(u). g(v)) In the same way as before, we construct the edge automorphism group, from which we deduce the partition of the edge set in edge orbits {O ...,...., or }.
ismpooisomorphism test (Weisfeiler & Leman 1968), also known as naive vertex refinement, 1-WZ, or just WL), is a fast heuristic to decide if two graphs are isomorphic not. The WL test proceeds as follows: every vertex v is initially assigned a colour (u) that is later iteratively refined by aggregating neighbouring information:
Weisfeiler-Lehman tests: The Weisfeiler-Lehman
NNote that the edge automorphism group is larger than that of induced automorphisms, but strictly larger only for 3 trivial cases (Whimey) 1932). However, induced automorphisms provide a more natural way to express edge structural roles.
2

---

Under review as a conference paper at ICLR 2021
( = HASH (()), id (u) BueN())) where 2-3 denotes a multisct (a set that allows element repetitionn)) and (()) is the neighbourhood of The WL algorithm terminates when the colours stop changing, and outputs a histogram of colours. Two graphs with different histograms are non- isomorphie; if the histograms are identical, the graphs are possibly, but not necessarily, isomorphic. Note that the neighbour aggregation in the WL test is form of message passing, and GNNs are the learnable analogue.
A series of works on improving GNN expressivity mimic the higher-order generalisations of WL, known as k-WL and k-Folklore WL (WL hierarchy) and operate on k-tuples of nodes (see Appendix B.I). The (A: + 1)-FWL is strictly stronger than k-FWL, k-FWL is strong as (k 1)-WL and 2-FWL is strictly stronger than the simple 1-WL test.
GRAPH SUBSTRUCTURE NETWORKS
Graphs consist of nodes (or edges) with repeated structural roles. Thus, it is natural for neural network to treat them in a similar manner, akin to weight sharing between local patches in CNNs for images (LeCun et al.. 1989) positional encodings in language models for sequential data (Sukhbaatar et al. 2015| Gehring et al. [017]] Vaswani et al. 2017). Nevertheless, GNNs are usually unaware of the nodes' different structural roles, since all nodes are treated equally when performing local operations. Despite the initial intuition that the neural network would be able to discover these roles by constructing deeper architectures, has been shown that GNNs are ill-suited for this purpose and are blind to the existence of structural properties, e.g. triangles or larger cycles (Chen et al. 2020 Arvind al. 2019).
To this end, we propose to explicitly encode structural roles as part of message passing, in order to capture richer topological properties. Our method draws inspiration from Loukas (2020), where was shown that GNNs become universal when the nodes in the graph are uniquely identified, i.e when they are equipped with different features. However, it is not clear how to choose these identifiers in way that can allow the neural network to generalise. Structural roles, when treated as identifiers, although not necessarily unique, are more amenable to generalisation due to their repetition across different graphs. Thus, they can constitute trade-off between uniqueness and generalisation.
Structural features: Structural roles are encoded into features by counting the appearance of certain sub- structures. The larger the substructure collection, the more fine-grained the partition of nodes into roles will be. Let H = {H,, H2..... !.... be set of small (con- nected) graphs, for example cycles of fixed length or cliques. For each graph H E H. we first find its iso- morphic subgraphs in G denoted as Gs. For each node VGs we infer its role w.r.t. H by obtaining the orbit of its mapping (v) in H, Orbsr (f))). By counting all the possible appearances of different or- bits in v, we obtain the vertex structural feature x (v) of v, defined as follows:
Figure I: Node (left) and edge (right) in- duced subgraph counting for a 3-cycle and a 3-path. Counts are reported for the blue node on the left and for the blue edge on the right. Different colors depict orbits.
2 (v) (Gs H UEE VG, stt. f(v) E O.,IH
i= = du-
(1)
[Au((H)
We divide the counts by the number of the automorphisms of H, since for every matched subgraph Gs there will always be [Aut(Hf) different ways to map it to H, thus these repetitions will be uninformative. By combining the counts from different substructures in H and different orbits, we H (v) E NDI of dimension D = Em.e du.-
obtain the feature vector (v) = [x
Similarly, define edge structural features x (fu,())))) by counting occurrences of edge automorphism orbits:
(Gs 2 {u, v} E &Gs s.t. (f(u), f(w) E cOR.H
F H. (fu, ((u,v}) v})
(2)
[Aut(H))
and the combined edge features xx(fu, (u, v)) = |x5, (fu. v)), x Hx (fu, ()). An example of vertex and edge structural features is illustrated in Figure]
3

---

Under review as a conference paper at ICLR 2021
Figure 2: (Left) Decalin and Bicyclopentyl: Non-isomon Non-isomorphic molecular graphs than can be distin- guished by GSN, but not the by the WL test (Sato 2020) (nodes represent carbon atoms and edges chemical bonds). (Right) Rook's 's 4x4 graph and the Shrikhande graph: the smallest pair of strongly regular non-isomorphic graphs with the same parameters SR(16,6,2.2). GSN can distinguish them with 4-clique counts, while 2-FWL fails.
Structure-aware message passing: The key building block of our architecture is the graph sub- structure layer, defined in general manner as Message Passing Neural Network (MPNN) (Gilmer et al. 2017). where now the messages from the neighbouring nodes also contain the structural information. In particular, each node u updates its state h' (v) by combining its previous state with the aggregated messages: h (v) Up*+1 (h'(v), MSG (v)), where the Up*+1 function is
multilayer perceptron (MLP) and the message aggregation is summation of features transformed by an MLP M as follows:
MSG (v)
Σ wEN(e)
M (v), h (w). xv (V) e(fu,,,))
(3)
MSG*+ (u) = Σ vEV(e)
M (1)
(1) h (l(h).(())))))))" xx offe
(4)
where the two variants, named GSN-v and GSN-e, correspond to vertex- or edge-counts, respectively, and effu, v)} denotes edge features. The two variants analogous to absolute and relative positional encodings in language models (Shaw et al., 2018 Dai et al. 2019).
It is important to note here that contrary to centifier-based GNNs (Loukas) 2020 Sato al. 2020
Dasoulas et al., 2020) that obtain universality at the expense of permutation equivariance (since the identifiers arbitrarily chosen with the sole requirement of being unique), GSNs retain the attractive inductive bias of the permutation equivariant property. This stems from the fact that the process generating our structural identifiers (i.e. subgraph isomorphism) is permutation equivariant itself (proof provided in the appendix).
How powerful are GSNs? We now turn to the expressive power of GSNs in comparison to MPNNs and the WL tests, key tool for the theoretical analysis of the expressivity of graph neural networks so far. Since GSN a generalisation of MPNNs, it is easy to see that it is at least as powerful. Importantly, GSNs have the capacity to learn functions that traditional MPNNs cannot learn. The following observation derives directly from the analysis of the counting abilities of the 1-WL test (Arvind al. 2019) and its extension MPNNs (Chen et al. 2020) (for proofs, see Appendix A.2)
Proposition 3.1. GSN is strictly more powerful than MPNN and the 1-WL test when one of the following holds: a) H is any graph except for star graphs of any size and structural features inferred by subgraph matching, i.e. count all subgraphs Gg 2 H for which it holds that EGg S Eg, or b) H is any graph except for single edges and single nodes and structural features are inferred by induced subgraph matching, iee. count all subgraphs Gs = H for which it holds that Ea. =g n (VGs x VGs).
An important question is which substructures are the most informative and whether they can com- pletely characterise the graph. As of today, we are not aware of any results in graph theory that can guarantee the reconstruction of a graph from a smaller collection of its subgraphs. In fact, the Reconstruction Conjecture (Kelly al. 1957 Ulam 1960). states that graph with size 2 3 can be reconstructed from its vertex-deletee subgraphs. Moreover, it is known (Dasoulas et al. 2020 Chen al. 2019) that solving graph isomorphism is equivalent universal approximation of permutation invariant functions defined on graphs. Thus, we can state the following for GSN:
Corollary 3.1. If the Reconstruction Conjecture holds, GSN can distinguish all non non- con-isomorphic
graphs of size n. and is therefore universal, when H contains all substructures of size k
4

---

Under review as a conference paper at ICLR 2021
How to choose the substructures? The Reconstruction Conjecture has only been proven for n I 11 (McKay 1997) and still remains open for larger graphs, while to the best of our knowledge, there is similar hypothesis for smaller values of k. However, in practice we observe that small substructures of size k = (11) are sufficient both for resolving hard instances of graph isomorphism as well as for tasks related to real-world networks. In particular, although our method does not attempt to align with the WL hierarchy. an interesting observation that we make is that small substructures have the capacity distinguish strongly regular graphs, where 2-FWL provably fails (proven in Appendix B.3). This is illustrated in Figure 2 (right), where counting 4-cliques is sufficient to disambiguate this exemplary pair, and in Section where a large scale experimental study is conducted.
In real-world scenarios, using too many and too large subgraphs will not only be expensive to compute, but they might also lead to overfitting. As an alternative, one can choose only the most discriminative subgraphs, i.e. the ones that can achieve the maximum possible node disambiguation, similarly to identifier-base approaches. Note that this approach solely takes into account expressivity and does not provide any guarantee about generalisation. This is empirically validated in Figure where we observe that choosing substructures with strong node disambiguation properties allows for better fitting of the training data, but the test set performance does not necessarily improve.
Aiming at better generalisation, it is desirable to make use of substructures for which there is substantial prior knowledge of their importance in certain network distributions and have been observed to be intimately related various properties. For example, small substructures (graphlets) have been extensively analysed in pertiinn interaction networks (Pržulj et al. 22044), triangles and cliques characterise the structure of ego-nets and social networks in general (Granovetter 1982), simple cycles (rings) are central in molecular distributions, directed and temporal motif's have been shown to explain the working mechanisms of gene regulatory networks, biological neural networks, transportation networks and food webs (Milo et al., 2002) Paranjape et al., 2017] [enson et al. 2016). In Figure 6 in the Appendix, we showcase the importance of these inductive biases: a cycle-based GSN predicting molecular properties achieves smaller generalisation gap compared to traditional MPNN, while at the same time generalising better with less training data. Choosing the best substructure collection is still open problem; various heuristics can be used (motif frequencies, feature selection strategies) or ideally by learning the substructure dictionary in an end-to-end manner. Answering this question is left for future work.
GSN-v vs GSN-e: Finally, we examine the expressive power of the two proposed variants. A crucial observation that we make, is that for each graph H in the collection, the vertex structural identifiers can be reconstructed by the corresponding edge identifiers. Thus, we can show that for every GSN-v there exists GSN-e that can simulate the behaviour of the former (proof provided in Appendix A.3).
Proposition 3.2. For a given subgraph collection H. let CV the set of functions that can be expressed by GSN-v with arbitrary depth and with, and C the set of functions that can be expressed by GSN-e with the same properties. Then, holds that C 2 CV or in other words GSN-e is at least as expressive GSN-v.
The complexity of GSN comprises two parts: precomputation (substructure counting) and training/testing, The key appealing property is that training and inference are linear w.r.t the number of edges, O(E)), as opposed higher-order methods (Maron et al. 2019a Morris et al. 2019) with On*)) training complexity and relational pooling (Murphy et al. 2019) with O(n) training complexity in absence of approximations.
Complexity:
The worst-case complexity of subgraph isomorphism of fixed size k is O(n"), by examining all the possible k-tuples in the graph. However, for specific types of subgraphs, such as paths and cycles, the problem can be solved even faster (see e.g. [Giscard et al. (2019). Approximate counting algorithms are also widely used, especially for counting frequent network motifs (Kashtan et al., 2004 Wernicke 2005; 2006 Wernicke & Rasche, 2006). and can provide considerable speed-up. Furthermore. recent neural approaches (Ying et al. (220bba) provide fast approximate counting.
In our experiments, we performed exact counting using the common isomorphism algorithm VF2 (Cordella et al. (2004). Although its worst case complexity is O(n²), ), it scales better in practice, for instance when the candidate subgraph is infrequently matched when the graphs are sparse, and is also trivially parallelisable. In Figure 3, we show a quantitative analysis of the empirical runtime of the counting algorithm against the worst case, for three different graph distributions: molecules,
5

---

Under review as a conference paper at ICLR 2021
wome
26-04
14400
1+40
14408
0.0
6.0
0.00
3200
305
Figure 3: Empirical (solid) worst (dashed) runtime for different graph distributions (in seconds, log scale). For each distribution we count the best performing (and frequent) substructures of increasing sizes k.
protein contact maps, social networks. It is easy see that when the graphs sparse (for the first two cases) and the number of matches is small, the algorithm is significantly faster than the worst case, while scales better with the size of the graph n. Even, in the case of social networks, where several examples are near-complete graphs, both the runtime and the growth w.r.t both and &o are better than the worst case. Overall, the preprocessing computational burden in most of the cases remains negligible for relatively small and sparse graphs, as it is the case of molecules.
4 RELATED WORK
Expressive power of GNNs and the WL hierarchy: The seminal results in the theoretical analysis of the expressivity of GNNs (Xu et al. 2019) and k-GNNs (Morris et al. 2019) established that most as powerful the 1-WI. test. Chen al.
traditional message passing-based GNNs (2019) showed that graph isomorphism is equivalent to universal invariant function approximation. Higher-order Invariant Graph Networks (IGNs) have been studied in series of works (Maron et al.) 2019b|e Chen et al., 2019 Keriven & Peyré 2019 Puny et al. (020), establishing connections with the WL hierarhy, similarly to Morris al. 2019 2020). The main drawback of these methods is the training and inference time complexity and memory requirements of O(n*) as well as the super-exponential number of parameters for linear IGNs making them impractical.
From a different perspective, [aato et al. (2019) and Loukas (222)) showed the connections between GNNs and distributed local algorithms (Angluin 1980 Linial 1992, Naor Stockmeyer 1993)
and suggested more powerful alternatives based on either local orderings or unique global identifiers (in the form random features in Sato et al. (0200) that make GNNs universal. However, these methods lack principled way to choose orderings/identiffers that can be shared across graphs (this would require a graph canonisation procedure). Garg et al. (2020) also analysed the expressive power of MPNNs and other more powerful variants and provided generalisation bounds. MMrrphy al.] (2019) take into account all possible node permutations and can therefore be intractable. Concurrently with our work, more expressive GNNs have been proposed using equivariant message passing with different kernels for each edge based on their isomorphism classes (de Haan et al., (2020a), message passing with matrices of order equal to the size of the graph instead of vectors (Vignac et al. 2020). or by enhancing node features with distance encodings (Li et al. 2020).
Solely quantifying the expressive power of GNNs in terms of their ability distinguish non- isomorphic graphs does not provide the necessary granularity: even the 1-WL test can distinguish almost all (in the probabilistic sense) noniisomoephic graphs (Babai et al., 1980). As a result, there have been several efforts to analyse the power of k-WL tests in comparison to other graph invariants (Fürer 2010 2017 Arvind et al. 201 9: Dell et al., 2018), while recently Chen al. (2020) approached GNN expressivity by studying their ability to count substructures.
Substructures in Complex Networks:
The idea of analysing complex networks based on small- scale topological characteristics dates back to the 1970's and the notion of triad census for directed graphs (Holland & Leinhardt 1976). The seminal paper of Milo et al. (2002) coined the term network morifs as over-represented subgraph patterns that were shown to characterise certain functional properties of complex networks in systems biology. The closely related concept of graphlets (Pržulj
et al. 2004 Pržulj 2007 Milenković & Pržulj 2008 Sarajlić et al. 2016), different from motifs in

---

Under review as a conference paper at ICLR 2021
(225
10a
10:1
Moain Ansolute Error
6.35
10
1-
20"1
6:23
1014
cace
10-5
10-
PM34
Cycla GBW4
Gyde GSKV
Pamn GSW-e
Path CSK-v
Ciique GSWe
Gique GSW
GIN/Z PPG FWW
0.03
16
Maximum Substructure Size
Figure 4: Train (dashed) and test (solid) MAEs for Path- and Cycle-GSN-EF as a function of the substructure maximum size k. Vertical bars in- dicate standard deviation; horizontal bars depict disumbiguatioo//uiqqueess scores 8.
Figure 5: SR graphs isomorphism test (log scale, smaller values are better), Different colours indi- cate different substructure sizes.
being induced subgraphs, has been used to analyse the distribution of world networks and as a topological signature for network similarity. Our work is similar in spirit with the graphler degree vector (GDV) (Przulj 2007), a node-wise descriptor based on graphlet counting.
Substructures have been also used in the context of ML. In particular, subgraph patterns have been used to define Graph Kernels (GKs) (Horváth et al.) 2004, SShrvashidze et al. 2009 Costa &
De Grave 2010 Kriege & Mutzel 2012 & Machara, 2020), with the most prominent being the
graphlet kernel Shervashidze et al., 2009). Motif-base node embeddings (Dareddy et al. 2019
Rossi al. 2018) and diffusion operators (Monti et al. 2018 Sankar et al. 2019 Lee el. (019 that employ ad adjacency matrices weighted according to motif occurrences, have recently been proposed for graph representation learning. Our formulation provides a unifying framework for these methods and it is the first to analyse their expressive power. Finally, GNNs that operate in larger induced neighbourhoods (Li et al. 2019 Kim al. 2019) or higher-order paths (Flam-Shepherd al. 2020)
have prohibitive complexity since the size of these neighbourhoods typically grows exponentially.
5 EXPERIMENTAL EVALUATION
In the following section we evaluate GSN in comparison to the state-of-the-art in a variety of datasets from different domains. We are interested in practical scenarios where the collection of subgraphs, as well as their size, are kept small. Depending on the dataset domain we experimented with typical substructure families (cycles, paths and cliques) and maximum substructure size (note that for each setting, our substructure collection consists of all the substructures of the family with size < k). We also experimented with both graphlets and motifs and observed similar performance in most cases. Appendix ([provides details and shows additional experiments.
Synthetic Graph Isomorphism test: We tested the ability of GSNs to decide if two graphs are non-isomorphic collection of Strongly Regular graphs of size up to 35 nodes, attempting to disambiguate pairs with the same number of nodes (for different sizes the problem becomes trivial). As we are only interested in the bias of the architecture itself, we use GSN with random weights to compute graph representations. Two graphs are deemed isomorphic if the Euclidean distance of their representations smaller than a predefined threshold e. Figure shows the failure percentage of our isomorphism test when using different graphlet substructures (cycles, paths, and cliques) of varying size Interestingly, the number of failure cases of GSN decreases rapidly as we increase k; cycles and paths of maximum length k- = 6 are enough to tell apart all the graphs in the dataset. Note that the performance of cliques saturates, possibly because the largest clique in our dataset has 5 nodes. Observe also the discrepancy between GSN-v and GSN-c. In particular, vertex-wist counts do not manage to distinguish all graphs, although missing only a few instances. We hypothesise that this is because edge counts offer higher level of granularity, allowing GSN create finer partition of the nodes in the graph (thus stronger symmetry breaking properties). Finally, 1-WL (Xu et al., (019)) and 2-FWL MMarn et al. 2019a) equivalent models demonstrate 100% failure, as expected from theory.
TUD Graph Classification Benchmarks: We evaluate GSN on datasets from the classical TUD benchmarks. We use seven datasets from the domains of bioinformaties and computational social
7

---

Under review as a conference paper at ICLR 2021
science and compare against various GNNs and Graph Kemels. Our main GNN baselines are GIN Xu et al. (2019) and PPGNs MMron et al. 2019a). We follow the same evaluation protocol of et al. (2019), performing 10-fold cross- validationn and then reporting the performance at the epoch with the best average accuracy across the 10 folds. Table T lists all the methods evaluated with the split of Zhang et al. (2018). We select our model by tuning architecture and optimisation hyperparameters and substructure related parameters, that is: (i) k. (ii) motifss against graphlets. Following domain evidence we choose the following substructure families: cycles for molecules, cliques for social networks. Best performing substructures both for GSN-e and GSN-v are reported. As can be seen, our model obtains state-of ofate-of-the-ar art performance in most of the datasets, with considerable margin against the main GNN baselines in some cases.
Table 1: Graph classification aceuracy on TUD Dataset. First, Second, Third best methods are highlighted. For GSN, the best performing structure is shown. "Graph Kernel methods.
Dutaset
MUTAG
PTC
Proteins
NCI1
Collab N/A
IMDB-B
IMDB-M M
RWK
(Ghitter al. 20133
79.212.1
55.9.0.3
59.6:1..
>3 days
NIA
NIA
GK
(k=3) (Shervastndzee et
2019
81411.7
55.7.0..5
71,410.31
62.510.3
N/A
N/A
N/A
PK*
(Neumann el all 2016
76.0+-.77
59.54224
73.74-0.7
82.5+0.5
N/A
NIA
N/A
WL
karael Sherrvasidzze
2011
90.415.7
59.914433
75.013.11
86.0-18
78.911.9
73.8139
50,9.13.8
GNIK
Di 20198
90.0:18.5
6..9=6.9
75.6+-4.2
84.2=1.5
83.621.0
76.9=3.6
52,814.66
DCNN (ATW000 & Towstey
2016
N/A
NIA
61.3+166
16.6=1100
52.1+0.77
49.1=1.4
33,5+114
DGCNN (Zhan
2018
85.8+1.8
2..6-42.5
75.5+-0.9
74.4-0.5
73.8+-0.5
70.0+0.9
47.8+-0.9
IGN (Marin arai 20199
83.9113.0
58.5
76.6.1..5
74.312277
78.5
72.0...55
48.7.13.4
GIN (1 2019)
89445566
64.6:17.0
76.2::2.8
82.7-1.7
80.241.99
75.1=5.1
52.342.8
PPGNs (Maronn oe 2019p
90.6=8.77
66.2=6.6
77.2::4.7
83.2=1.1
814+14
73.0=5.88
50,5+3..6
Natural
2020al
89,4=160
66.821.79
71.741.04
12
73.522201
1,,341550
GSN-
90.6:7,5
68.277.2
76.6+5500
83.5 2.3
85.5+122
7788=33
54,343.3
(cycles)
(eveles)
(cliques)
15 (cycles)
(Uiangles)
(eliques)
(cliques)
GSN-v
92.247.5
67.425.7
74, 14.5923.0
83,52200
82.7115
76.8220
52.64:.6
(eycles)
(eycles)
(cliques)
(triangles)
(tiangles)
(cliques)
(trangles)
ZINC Molecular graphs: We evaluate GSN on the task of regressing the constrained solubility property of molecules from the ZINC database (Irwin et al., 2012; Kusner et al.] [017] Gómez. Bombarelli et al. 2018:) Jin et al. 2018 Dwivedi et al. 2020). Our main baselines are GIN (which we re-implement), as well as a stronger baseline (as Eq. A.3 and 4 without structural features (see Appendix for details) that can also take into account edge features (MPNN-EF). We then extend both baselines with structural features obtained with k-cycle counting (models denoted as GSN and GSN-EF) and report the result of the best performing substructure w.r.t. the validation set. The data split into training, validation and test set obtained from Dwivedi et al. (2020). The evaluation metric and the training loss is the Mean Absolute Error (MAE). Table 2 shows that our model significantly outperforms all the baselines.
In Figure 4 we compare the training and test error for different substructure families (cycles, paths and non-isomorphic trees - for each experiment we use all the substructures of size S k in the family). Additionally, we measure the "uniqueness" of the identifiers each substructure yields as follows: for each graph G in the dataset, we measure the number of unique node features ug (initial node features concatenated with node structural identifiers). Then, we sum them up over the entire training set and divide by the total number of nodes, yielding the disambiguation score 5 = Ee 9e
Eo [Vo shown as horizontal bars in Figure 4 A first thing to notice is that the training error is tightly related to the disambiguation score. As identifiers become more discriminative, the model gains expressive power. On the other hand, the test error is not guaranteed decrease when the identifiers become more discriminative. For example, although cycles have smaller disambiguation scores, they manage to generalise much better than the other substructures, the performance of which is similar to the bascline architecture. This is also observed when comparing against Sato et al. (2020) (-r methods in Table 2. where, akin to unique identifiers, random features are used to strengthen the expressivity of GNN architectures. This approach also fails to improve the baseline architectures in terms of mean test error. This validates our intuition that unique identifiers can be hard to generalise when chosen arbitrarily and motivates once more the importance of choosing the identifiers not only based on their discriminative power, but also in a way that allows incorporating the appropriate inductive biases. Finally, we observe substantial jump in performance when using GSN with cycles of size k 2 6. This is not surprising, as cyclical patterns of such sizes (c.g. aromatic rings) are very common in organic molecules.
8

---

Under review as a conference paper at ICLR 2021
Table 2: MAE on ZINC. '-EF:: Ad- ditional Edge Features, '-r': random features. "Our implementation.
Table 3: ROC-AUC on ogbg-moooooooooooooooooooooooooo molivv. 'AF'; Additional Features, '-VN": message passing with virtual node.
Method
Training
Validation
Test
Method
Test MAE
GCN-VN
88,65= 1.01
83.73=0.78
74,18 1.21
GCN
0.469
GCN-AF
88.65-2.19
82.04 +1.41
76.06++0.97
GatedGCN- EEF
0,363++00009
GCN-VN-AF
90.07+4.69
83.84+0.91
15.99+1.11
GAT
0,463=100002
GIN-VN
93.8922.96
84.10=1.05
1..20:11.30
GIN (u et al. 2019
0.408
GIN-AF
88.64=2.54
82.32-10.90
75,581
GINT
0.288
92.73=3.80
84.79=0.68
17.07+1449
GINT-r
0.282-10.021
GSN-VN
93.61=1.85
84,45
75.881
MPNN-ER
0.184=+0.012
GSN-AF
88.6713.26
85.17:0.90
7..06:11.74
MPNN-EFE
0.193-+0.009
GSN- VN-AF
94.30-3.38
86.58
17.99
GSN
0.139-00.007
GSN-EF
0.108+00008
OGB-MOLHIV: We use ogbg molhiv from the Open Graph Benchmark (OGB) Hu (2020) as a graph-level binary classification task, where the aim is to predict if a molecule inhibits HIV replication or not. The baseline architecture provided by the authors is variation of GIN that allows for edge features and is extended with a virtual node, GIN-VN, or with additional node/edge features, GIN-AF, or both, GIN-VN-AL (more information in the supplementary material). Similarly to the experiment on ZINC, we extend the baseline settings with cyclical substructure features by treating them in similar way as node and edge features (GSN-VN, GSN-AF, GSN-VN-AF). Using the evaluator provided by the authors, report the ROC-AUC metric at the epoch with the best validation performance (substructures are also chosen based on the validation set). As shown in Table 3, considerable improvement in the performance of the model in all splits is obtained, thus demonstrating strong generalisation capabilities. Tests with additional chemical features such as formal charge, hybridisation, etc. ('-AF" setting in Table 3) show that structure provides important complementary information.
Structural Features & Message Passing: We perform an ablation study on the abilities of the structural features to predict the task at the hand, when given as input to a graph-agnostic network. In particular, we compare our best performing GSN with DeepSets model (Zaheer al. 2017) that treats the input features and the structural identifiers as set. For fairness of evaluation the same hyperparameter search performed for both models (see Appendix C.5). Interestingly, as we show in Table our baseline attains particularly strong performance across a variety of datasets and often outperforms other traditional message passing baselines. This demonstrates the benefits of these additional features and motivates their introduction in GNNs, which are unable to compute them. As expected, we observe that applying message passing on top of these features, brings performance improvements in the vast majority of the cases, sometimes considerably, in the ZINC dataset.
Table 4: Comparison between DeepSets and GSN with the same structural features
Dataset
MUTAG
PTC
Proteins
NCTI
Collab
IMDB-B
IMDB-M
ZINC
MOL-HIV
DeepSets
93.3-6.9
66.4=0.7
778:142
80.3
#2,4
80.9
=1.6
73.7
53.3 E3.
0.288 20.00
77.3411.00
params
3K
51K
GSN
92.87700
68.227.2
77.8.15.6
83.5.1 2.0
85.5 1.2
77,8133
54,3333
0,108 10.018
77.9911.00
params
3K
3K
3K
10K
52K
65K
66K
385K
3.3M
CONCLUSION
In this paper, we propose a novel way to design structure-aware graph neural networks. Motivated by the limitations of traditional GNNs to capture important topological properties of the graph, we formulate a message passing scheme enhanced with structural features that are extracted by counting the appearances of prominent substructures, as domain knowledge suggests. We show both theoretically and empirically that our construction leads improved expressive power and attains state-of th-the-art performance in real-world scenarios. In future work, we will further explore the expressivity of GSNs as alternative to the k-WL tests, well their generalisation capabilities. Another important direction to infer prominent substructures directly from the data and explore the ability of graph neural networks to compose substructures.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, (ICML), volume 97 of Proceedings of Machine Learning Research, pp. 242-252. PMLR, 2019.
Dana Angluin. Local and global properties in networks of processors, In ACM Symposium on Theory of Computing (STOC), pp. 82-93. ACM, 1980.
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On weisfeiler-leman invariance: Subgraph counts and related graph properties. In Fundamentals of Computation Theory (FCT), volume 11651 of Lecture Notes in Computer Science, pp. 111-125. Springer, 2019.
James Atwood and Don Towsley. Diffussinn-oonollttinnal neural networks. In Advances in Neural Information Processing Systems (NIPS), pp. 1993-2001, 2016.
László Babai, Paul Erdos, and Stanley M Selkow. Random graph isomorphism. SIAM Journal on computing, 9(3):628 635, 1980.
Peter Battaglia, Razvan Pascanu, Matthe Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects. relations and physics. In Advances in Neural Information Processing systems (NIPS), pp. 4502-4510, 2016.
Austin Benson, David Gleich, and Jure Leskovec. Higher-order organization of complex networks. Science, 353(6295): 2016.
Lukas Biewald. Experiment tracking with weights and biases, 2020. URL wtttt::p///// // www. www.wand com/ Software available from wandb.com.
Giorgos Bouritsas, Sergiy Bokhnyak, Stylianos Ploumpis, Michael Bronstein, and Stefanos Zafeiriou. Neural 3d morphable models: Spiral convolutional networks for 3d shape representation learning and generation. Proceedings of the IEEE International Conference on Computer Vision (ICCV), pp. 7213-7222, 2019.
Jin-yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identifications. Combinatorica, 12(4):389-410, 1992.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In Advances in Neural Information Processing Systems (NeurIPS). pp- 15868-15876, 2019.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count
substructures? In Advances in Neural Information Processing Systems (NeurlPS), 2020.
Luigi Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Transactions Pattern Analysis and Machine Intelligence, 166-013137 2004.
Fabrizio Costa and Kurt De Grave. Fast neighborhood subgraph pairwise distance kernel. In International Conference on Machine Learning (ICML), pp. 255-262. Omnipress, 2010.
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G. Carbonell, Quoe Viet Le, and Ruslan Salakhutdinov, Transformer-xl: Attentive language models beyond fixed-length context. In Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Volume 1: Long Papers, pp. 2978-22288 2788-988. Association for Computational Linguisties, 2019.
M. R. Dareddy, M. Das, and H. Yang. motif2vec: Motif aware node representation learning for heterogeneous networks. In 2019 IEEE International Conference on Big Data (Big Data), pp- 1052-1059, 2019.
George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. International Joint Conference on Artificial Intelligence (IJCAI), 2020.
10

---

Under review as a conference paper at ICLR 2021
Pim de Haan, Taco Cohen, and Max Welling. arXiv:2007.08349, 2020a.
Natural
graph networks. arXiv preprint
Pim de Haan, Maurice Weiler, Taco Cohen, and Max Welling. Gauge equivariant mesh cnns: Anisotropic convolutions on geometric graphs. arXiv preprint arXiv:2003. 2020b.
Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász meets weisfeiler and leman. In International Colloquium on Automata, Languages, and Programming (ICALP), volume 107 of LIPlcs, pp. 40:1-40: 14. Schloss Dagstuhl- Leibniz--Zentrum für Informatik, 2018.
Simon S. Du, Kangcheng Hou, Ruslan Salakhutdinov, Barnabás Póczos, Ruosong Wang. and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In Advances in Neural Information Processing Systems (NeurIPS), pp- 5724-5734, 2019a.
Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pp. 1675-1685. PMLR, 2019b.
David Duvenaud, Dougal Maclaurin, Jorge aguilera-pparragurrre, Rafael Gómez-Bombarelli Tim- othy Hirzel, Alán Aspuru-Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in Neural Information Processing Systems (NIPS), pp. 2224-2232, 2015.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint wrXiv:2003.0088: 2020.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 1903. 024422, 2019.
Daniel Tlam-Shephee Tony Wu, Pascal Friederich, and Alan Aspuru-Guze Neural message passing on high order paths. Advances Neural Information Processing Systems Workshops (NeurIPSW), 2020.
Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. In Advances in Neural Information Processing Systems (NIPS), pp. 6530-6539, 2017.
Martin Fürer. On the power of combinatorial and spectral invariants. Linear algebra and its applications, 432(9))2373 2380, 2010.
Martin Fürer. On the combinatorial power of the leisfeiler-lehman algorithm. In International Conference on Algorithms and Complexity (CIAC), volume 10236 of Lecture Notes in Computer Science, pp. 260-271. Springer, 2017.
Pablo Gainza, Freyr Sverrisson, Federico Monti, Emanuele Rodola, Boscaini, MM Bronstein, and BE Correia. Deciphering interaction fingerprints from protein molecular surfaces using geometric deep learning. Nature Methods, 17(2):184-192, 2020.
Vikas K. Garg, Stefanie Jegelka, and Tommi S. Jaakkola. Generalization and representational limits of graph neural networks. 2020.
Thomas Gärtner, Peter A. Flach, and Stefan Wrobel. On graph kemell:: Hardness results and efficient alternatives. Computational Learning Theory and Kernel Machines (COLT), volume 2777, pp. 129-143. Springer, 2003.
Jonas Gehring. Michael Auli, David Grangier, Denis Yarats, and Yann N. Dauphin. Convolutional sequence to sequence learning. In International Conference Machine Learning, (ICML), volume 70 of Proceedings of Machine Learning Research, pp. 1252. PMLR, 2017.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning (ICML), volume 70 of Proceedings of Machine Learning Research, pp. 1263-1272. PMLR, 2017.
11

---

Under review as a conference paper at ICLR 2021
Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the national academy of sciences (PNAS), 99(1),7821-782,, 2002.
Pierre-Louis Giscard, Nils M. Kriege, and Richard C. Wilson. A general purpose algorithm for counting simple cycles and simple paths of any length. Algorithmica, 817))2716-2777, 2019.
Rafael Kömezz-Bomarreie Jennifer N Wei, David Duvenaud, José Miguel Hernández-Lobato Benjamin Jänchez-Lengelinn Dennis Sheberla, Jorge Aguilera-Iparraguinnn Timothy D Hirzel, Ryan P Adams, and Alán Eapuru-Guzil Automatic chemical design using data-driven continuous representation of molecules. ACS central science. 4(2):268 276, 2018.
Mark Granovetter. The strength of weak ties: A network theory revisited. In Sociological Theory, pp. 105-130, 1982.
Paul W Holland and Samuel Leinhardt. Local structure in social networks. Sociological methodology. 7:1-45, 1976.
Tamás Horváth, Thomas Gärtner, and Stefan Wrobel. Cyclic pattern kernels for predictive graph mining. In ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pp. 158-167. ACM, 2004.
Weihua Hu, Matthias Fey, Marinka Zitmik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.0066 2020.
John Ingraham, Vikas Garg, Regina Barzilay, and Tommi Jaakkola. Generative models for graph- based protein design. In Advances in Neural Information Processing Systems (NeurIPS), pp. 15794-1555 15805, 2019.
John J. Irwin, Teague Sterling, Michael M. Mysinger, Erin S. Bolstad, and Ryan G. Coleman. ZINC: A free tool to discover chemistry for biology. Journal of chemical information and modeling, 52 (7):1757-1768, 2012.
Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pp- 2191 -200. PMLR, 2018
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and gener- alization in neural networks. In Advances in Neural Information Processing Systems (NeurIPS), pp. 8580-8589, 2018.
Wengong Jin, Regina Barzilay, and Tommi S. Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International Conference Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pp.
PMLR, 2018.
Nadav Kashtan, Shalev Itzkovitz, Ron Milo, and Uri Alon. Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs. Bioinformatics, 20(11):1746-1755 2004.
Paul Kelly et al. A congruence theorem for trees. Pacific Journal of Mathematics, 7(1):911996,, 1957.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), pp. 7090-7099, 2019.
Cheolhyeong Kim, Haeseong Moon, and Hyung Hwang. Near: Neighborhood edge aggregator for graph classification. arXiv preprint arXiv: arXiv: 1909.02766, 2019.
Thomas N. Kipf, Ethan Fetaya, Kuan-Chieh Wang. Max Welling, and Richard S. Zemel. Neural relational inference for interacting systems. In International Conference on Machine Learning, (ICML), volume 80 of Proceedings of Machine Learning Research. pp. 2693-2702. PMLR, 2018.
Johannes Klicpera, Janek Groß, and Stephan Günnemann. Directional message passing for molecular graphs. In International Conference Learning Representations (ICLR). OpenReview.net, 2020.
12

---

Under review as a conference paper at ICLR 2021
Risi Kondor, Hy Truong Son, Horace Pan, Brandon M. Anderson, and Shubhendu Trivedi. Co- variant compositional networks for learning graphs. International Conference on Learning Representations Workshops (ICLRW). OpenReview.net, 2018
Nils M. Kriege and Petra Mutzel. Subgraph matching kernels for attributed graphs. In International Conference Machine Learning, (ICML.), pp. 291-298. Omnipress, 2012.
Matt J. Kusner, Brooks Paige, and José Miguel Hernández-Loban Grammar variational autoencoder. In International Conference Machine Learning (ICML), volume 70 of Proceedings of Machine Learning Research, pp. 1945-1954. PMLR, 2017.
Yann LeCun, Bernhard Boser, John S Denker, Donnie Henderson, Richard E Howard, Wayne Hubbard, and Lawrence D Jackel. Backpropagation applied to handwritten zip code recognition. Neural computation, 144):541-551, 1989.
John Boaz Lee, Ryan Rossi, Xiangnan Kong, Sungchul Kim, Eunyee Koh, and Anup Rao. Graph convolutional networks with motif-based attention. In 28th ACM International Conference on Information and Knowledge Management (CIKM), pp. 499-508. ACM, 2019.
Michael Lingzhi Li, Meng Dong, Jiawei Zhou, and Alexander M Rush. A hierarchy of graph neural networks based on learnable local features. arXiv preprint
2019.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding-desie provably more powerful gnns for structural representation learning. 2020.
Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, 1992.
Zhichang Liu, Siva Krishna Mohan Nalluri, and Fraser Stoddart. Surveying macrocyclic chemistry: from flexible crown ethers to rigid cyclophanes. Chemical Society Reviews, 46(9):2459-244) 2478. 2017.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations (ICLR). OpenReview.net, 2020.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2153-2164, 2019a.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, (ICLR). OpenReview.net, 2019b.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pp. 4363 4371. PMLR, 2019c.
Jonathan Masci, Davide Boscaini, Michael M. Bronstein, and Pierre Vandergheynst. Geodesic convolutional neural networks on riemannian manifolds. In IEEE International Conference on Computer Vision Workshops, (ICCVW), pp. 832-840. IEEE Computer Society, 2015.
Brendan McKay. Small graphs are reconstructible. Australasian. Combinatorics, 15:123-126, 1997.
Tijana Milenković and Nataša Pržulj. Uncovering biological network function via graphlet degree signatures. Cancer informatics, 6:257-273, 2008
Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Network motifs: simple building blocks of complex networks. Science, 298(5594):8244 2002.
F. Monti, K. Otness, and M. M. Bronstein. Motifnet: A masedf-baeed graph convolutional network for directed graphs. In 2018 IEEE Data Science Workshop (DSW), pp. 225-228, 2018.
13

---

Under review as a conference paper at ICLR 2021
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodolå, Jan Svoboda, and Michael M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 5425-5434, 2017.
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, pp. 4602 46094 AAAI Press, 2019.
Christopher Morris, Gaurav Rattan, and Mutzel Petra. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Ryan L. Murphy, Balasubramaniam Srinivasan, Vinayak A. Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pp. (663-4673, PMLR, 2019.
Moni Naor and Larry J. Stockmeyer. What can be computed locally? In ACM Symposium on Theory of Computing (STOC), pp. 184-193, ACM, 1993.
Marion Neumann, Roman Garnett, Christian Bauckhage. and Kristian Kersting. Propagation kernels: efficient graph kernels from propagated information. Machine Learning, 102(2):209-24) 245, 2016.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International Conference on Machine Learning (ICML), volume 48 of Proceedings of Machine Learning Research, pp. 2014-2023. PMLR, 2016.
Hoang NT and Takanori Maehara. Graph homomorphism convolution. In International Conference on Machine Learning (ICML), Proceedings of Machine Learning Research. PMLR, 2020.
Ashwin Paranjape, Austin R. Benson, and Jure Leskovec. Motif's in temporal networks. In Proceed- ings of the Tenth ACM International Conference on Web Search and Data Mining, WSDM, pp. 601-610. ACM, 2017.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems (NeurIPS), pp. 8024-8035, 2019.
Nataša Pržulj. Biological network comparison using graphlet degree distribution. Bioinformatics, 23 (2):177-183, 2007.
Nataša Pržulj, Derek G Corneil, and Igor Jurisica. Modeling interactome: scale-free or geometric? Bioinformatics, 20(18):3508-3111 2004.
Omri Puny, Heli Hen-Hamu, and Yaron Lipman. From graph low-rank global attention to 2-fwl approximation. arXiv preprint arXiv:2006.07844 2020.
Ryan A Rossi, Nesreen K Ahmed, Eunyee Koh, Sungchul Kim, Anup Rao, and Yasin Abbasi Yadkori. 2018.
Hone: Higher-order network embeddings. arXiv preprint 1rXiv:
Benjamin Sanchez-Lengeling, Jennifer N Wei, Brian K Lee, Richard C Gerkin, Alán Aspuru-Guzik, and Alexander Wiltschko. Machine learning for scent: Learning generalizable perceptual representations of small molecules. arXiv preprint 19Xiv:1910.1066 2019.
Aravind Sankar, Xinyang Zhang, and Kevin Chen-Chuan Chang. Meta-gnn: metagraph neural network for semi-supervised learning in attributed heterogeneous information networks. In Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp. 137-144. ACM, 2019,
Anida Sarajlić, Noël Malod-Dogml Ömer Nebil Yaveroğlu, and Nataša Pržulj. Graphlet-based characterization of directed networks. Scientific reports, 6:35098, 2016.
Ryoma Sato. A survey on the expressive power of graph neural networks. arXiv preprint A0xi:2003300478.. 2020.
14

---

Under review as a conference paper at ICLR 2021
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. In Advances in Neural Information Processing Systems (NeurlPS), pp. 4083-4092, 2019. 2019.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. arXiv preprint arXiv:2002.0311 03155, 2020.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference (ESWC), volume 10843 of Lecture Notes in Computer Science, pp. 593-607. Springer, 2018.
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-ILLT, Volume (Short Pupers), pp. 464-468. Association for Computational Linguistics, 2018
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In Artificial Intelligence and Statistics (AISTATS), volume 5 of Proceedings of Machine Learning Research, pp. 488-495. PMLR, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research (JMIR), 12: 2539-2561, 2011. 2011.
Martin Simonovsky and Nikos Komodakis. Dynamic edge-conditioned filters in convolutional neural networks on graphs. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 29-38. IEEE Computer Society, 2017.
Sainbayar Sukhbaatar, Arthur Szlam, Jason Weston, and Rob Fergus. End-to-end memory networks. In Advances in Neural Information Processing Systems (NIPS), pp. 2440-2448, 2015.
Stanislaw M Ulam, A collection of mathematical problems, volume 8. Interscience Publishers, 1960.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems (NIPS), pp. 5998-6008, 2017.
Saurabh Verma and Zhi-Li Li Zhang. Hunt for the unique, stable, sparse and fast feature learning on graphs. In Advances in Neural Information Processing Systems (NIPS), pp. 88-98, 2017.
Clement Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-passing Advances in Neural Information Processing Systems (NeurIPS), 2020.
Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. N71, Series 2, 9:12 16, 1968. English translation is available at https // //www. it zcu, wwtwww/wwwww...ttt httpw//11/pppp..c. / httpp/pdwwwplppppppeeeeeeppeeeee paaper_trannlaee
pdf
Sebastian Wernicke. A faster algorithm for detecting network motifs. Rita Casadio and Gene Myers (eds.), Algorithms in Bioinformatics. 5th International Workshop, WABI, volume 3692 of Lecture Notes Computer Science, pp. 165-177. Springer, 2005.
Sebastian Wernicke. Efficient detection of network motifs. IEEE ACM Transactions on Computational Biology and Bioinformatics, 3(4):347-359, 2006.
Sebastian Wernicke and Florian Rasche. FANMOD: a tool for fast network motif detection. Bioinfor- matics, 22(9): 2006.
Hassler Whitney. Congruent graphs and the connectivity of graphs. American Journal of Mathematics, 1401):100-168, 1932.
15

---

Under review as a conference paper at ICLR 2021
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference Machine Learning, (ICML), volume 80 of Proceedings of Machine Learning Research, pp. 5449-5456 PMLR, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR). OpenReview.net, 2019.
Pinar Yanardag and S. V. N. Vishwanathan. Deep graph kernels. In ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pp. 1365-1374, ACM, 2015.
Rex Ying. Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pp. 973.983. ACM, 8a.
Rex Ying, Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, and Jure Leskovec. Neural subgraph matching. arXiv preprint 2iti:::0000000092, 2020a.
Rex Ying, Andrew Z. Wang, Jiaxuan You, and Jure Leskovec. Frequent subgraph mining by walking in order embedding space. In International Conference on Machine Learning Workshops (ICMLW), 2020b.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovee. Hicrarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1805-4815 2018b.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. In Advances in neural information processing systems, pp. 3391-3401, 2017.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAI Conference on Artificial Intelligence, pp. 4438-4445. AAAI Press, 2018.
A DEFERRED PROOFS
A.I GSN IS PERMUTATION EQUIVARIANT
Proof. Let A Roxa the adjacency matrix of the graph, H E RRaxd, the input vertex features, E Ra the input edge features and E, Raxx the edge features at dimension i. Let Sy(A) E Naxdv, SA(A) E Nuxwxds the functions generating the vertex and edge structural identifiers respectively. It is obvious that subgraph isomorphism invariant to the ordering of the vertices, i.c. we will always obtain the same matching between subgraphs Gs and graphs H in the subgraph collection. Thus, each vertex v (edge (v, u)) in the graph will be assigned the same structural identifiers (v) (xg(v, u)) regarless of the vertex ordering. Thus Sy and Se are permutation equivariant, i.e. for any permutation matrix P E {0, 1 10,1 it holds that Sy (PAP") (A), Se (PAPT) PiSF (A); SS. (A))PT, where the permutation is applied at each slice (F(A) E Naxn of the tensor (A(())
Let f(A, H) E Bundout GSN layer. We will show that f is permutation equivari- ant. We need to show that if Y = f(A,X, the output of the GSN-layer, then PY = fPAPP" PX, P[E.:...: Edgg PPT) for any permutation matrix P. It is easy to see that GSN- can be expressed as traditional MPNN 9(A, H. E) nuxdout (similar equations 3 and 4 of the main paper) by replacing the vertex features with the concatenation of the input vertex features and the vertex structural identifiers, i.e. Y f(A, H. E) g( A, [H; Sy (A)), E). Thus,
16

---

Under review as a conference paper at ICLR 2021
f(PAP" PP PH, PES = (PAP" [P Sv(PPP") P(E Edg! PP)
=P(PP PH (A)),, P(E Edg. PP')
-Py(A, [y
=P
where in the last step we used the permutation equivariant property of MPNNs. Similarly, we can show that GSN-e layer is permutation equivariant, since it be expressed as traditional MPNN layer by replacing the edge features with the concatenation of the original edge features and the edge structural identifiers f(A, H. E) (( H, [E; (A))))
Overall, a GSN network is permutation equivariant as composition of permutation equivariant functions, or permutation invariant when composed with a permutation invariant layer the end, i.e. the READOUT function.
A.2 PROOF OF PROPOSITION 3.1
Proof. GSN is at least powerful as MPNNs and the 1-WL test: It is easy to see that GSN model class contains MPNNs and thus least as expressive. To show that it least as expressive as the 1-WL. test, one can repurpose the proof of Theorem 3 in Xu et al. (2019) and demand the injectivity of the update function (w.r.t. both the hidden state h (v) and the message aggregation
MSG (v)), and the injectivity of the message aggregation w.r.t. the multiset of the hidden states of
the neighbours (h' (u) (u)) It suffices then to show that if injectivity is preserved then GSNs at least as powerful as the 1-WL.
We will show the above statement for node-labelled graphs, since traditionally the 1-WL test does not take into account edge labels We can rephrase the statement as follows: If GSN deems two graphs G1, G2 as isomorphic, then also J-WL. deems them isomorphic. Given that the graph-level representation is extracted by a readout function that receives the multiset of the node colours in its input (i.e. the graph-level representation is the node colour histogram some iteration !), then suffices to show that if for the two graphs the multiset of the node colours that GSN infers is the same, then also 1-WL will infer the same multiset for the two graphs.
Consider the case where the two multisets that GSN extracts are the same: i.c. (h' (v)Svve,, = =(b (w)eve,, Then both multisets contain the same distinct colour/hidden rep- resentations with the exact same multiplicity. Thus, it further suffices to show that if two nodes v, (that may belong to the same to different graphs) have the same GSN hidden representations he(()) = h2) at any iteration f, then they will also have the same colours c' (v) = c'().. extracted by 1-WL. Intuitively, this means that GSN creates partition of the nodes of each graph that is at least as fine-grained as the one created by 1-WL. We prove by induction (similarly to Xu et al. (2019) that GSN model class contains a model where this holds (w.l.o.g. we show that for GSN-v: same proof applies to GSN-e).
For t = 0 the statement holds since the initial node features are the same for both GSN and 1-WL, i.e. (v) (v), Yu Vo, U Va.. Suppose the statement holds for t 1, iee. h (w) = h (u) d' c (u). Then we show that also holds for t.
Every node hidden representation step is updated as follows: h²(() = UP' (h'-1(o), (S). Assuming that the update function UP* is injective, we have the following: if h'()) = h²(u), then:
1. h (v- hn' which from the induction hypothesis implies that d²
1 (v) (w)
MSG (v) MSG'(S) (u), where the message function is defined as in Eq. A.3 of the main pa-
per: M MSG = EweN(e) M (ht-l(e) (v), ht- h (v), xv (x))w))w.)))))))))))))) Additionally here require
if one considers simple 1-WL. extension that concatenates edge labels to neighbour colours, then the same proof applies.
17

---

Under review as a conference paper at ICLR 2021
MSG" to be injective w.r.t. the multiset of the hidden representations of the neighbours. In fact, using Lemma 5 from Xu et al. (2019) we know that there always exists a function M', such that M (v) is unique for each multiset 2 (h" (v), h (w), (t),, Xy (w)) SweN. assuming that the domain from where the elements of the multiset originate is countable. Thus,
(V) = (M)
(v) xv())xxxxxx SWEN, = 2(hh(''')))) (()"""(w) h (2)) (h' (h') (w:)SNN = (=)=Ee)
From the induction hypothesis know that h²=1(w) h1 (z) implies that (wr)(w)) c (=) for any w E NN. 2 E Nu, thus (c² (e)-"(W)jee SWEN, = =cc- (2)
Concluding, given the update rule of I-WL: (e) = HASH c (LASH(c-(()) (v) that (v) cl (u)
(w-)(()SEEN,, it holds
When are GSNs strictly more powerful than the 1-WL test? Arvind et al. (2019) showed that I-WL, and consequently MPNNs, can count only forests of stars. Thus, if the subgraphs are required to be connected, then they can only be star graphs of any size (note that this contains single nodes and single edges). In addition, Chen et al. (2020) showed that 1-WL, and consequently MPNNs, cannot count any connected induced subgraph with 3 more nodes, i.c. any connected subgraph apart from single nodes and single edges.
Given the first part of the proposition, in order show that GSNs strictly more expressive than the 1-WL test, it suffices to show that GSN can distinguish a pair of graphs that 1-WL test deem isomorphic. If /I is substructure that 1-WL cannot learn to count, i.e. the ones mentioned above, then there is at least one pair of graphs with different number of counts of H, that 1-WL deems isomorphic. Thus, by assigning counting features the nodes/edges of the two graphs based on appearances of H. GSN can obtain different representations for G1 and G2 by summing up the features. Hence, G1, G2 are deemed non-isomorphic. An example depicted in Figure (left), where the two non-isomorphic graphs are distinguishable by GSN via e.g. cycle counting, but not by 1-WL..
A.3 PROOF OF PROPOSITION 3.2
Without loss of generality we will show Proposition 3.2 for the case of single substructure H. Moreover, in the context of this proof, for reasons that will be made clear below, we will use directed edge structural identifiers, i.e. edge orbits are defined on directed edges, thus potentially different edge identifiers are assigned to different directions of the same edge. Note that this is not the case for substructures that have a single vertex orbit, such as the ones that we use in our experiments cliques and cycles. This is because the single vertex orbit induces a single edge orbit as well which is the same both for the directed and the undirected case.
Proof. In order show that GSN-e can express GSN-v, will first prove that the vertex identifier of each vertex v can be inferred by the edge identifiers of its incident edges {(e, u) : u E N(())
We first introduce the following definitions to simplify notation: Recall the definition of ver- tex orbit OrbY (v) {u E Vи 3g Aut(H) s.t. g(w) = u). For an orbit Orb (c), denote the orbit neighbourhood (Orbr (w)) the multiset of the orbits of the neighbours of (Orb (v)) = =2Orb" (u) u E (p))). Note that the orbit neighbourhood is the same for any vertex E Orb v (v) and that the neighbourhood is a multiset, since different neighbours might belong to the same orbit. Denote the orbit degree deg(Orb' (r)) as the degree of any vertex in Orb" V (w) as deg(v) dOrb (v)) (Orb (v)) We will be indexing different vertex orbits as follows: oу = Orb V (u).
Regarding the edge orbits, recall that each edge orbit is induced by the orbits of the vertex automor- phism group, i.e. Orb (ub u) = ((w,2) E En Fg E Aut(H) s.t. g(w) v and g(z) = u), al-
18

---

Under review as a conference paper at ICLR 2021
ternatively Orb (v, u) serve here, that define edge orbits for directed edges. Let's assume that Orb (v) O Orb" (u) - Oj and Orb (v, u) of For ease of notation will denote O - (O) o.))
V {ww 2) Eu Orb Orb" = Orb (v) and Orb" (2) Orb (u)). (r))( Ob-
Recall that vertex structural identifiers are defined as follows (we drop the subscript H for ease of notation):
2 (v) = [Gs = H : VGs s.t. f(0) E O.H. i i= 1,...,dn du-
(5)
[Aut(H)
and edge structural identifiers for directed edges:
s vi u) HGs = H (u. E Eas s.t. (f(w), e O
(6)
Aut(H)]
Let as assume that there exists only one matched subgraph G = H and the bijection between VGs and H is denoted as f. Then, concerning the vertex orbit O one of the following holds:
& Vag- Then x/(v)) (v) 0 and (v, u) 0, Vu W()),,
E Vag and Orb(S(e)) + OY. Then, xx (v) = 0 and (v, = 0, Vu E N()), otherwise the orbit of f(v) would be O. Note that here the directionality of the edge is important, otherwise ambiguity would be created and x.j u) could have been equal to if the orbit of (u) is O..
v E VGs and Orb(f(u)) = oY. Then, <\(v) deg(O))) neighbours in H, then there exist exactly deg(O!) edges incident to that belong to Gs as well and the set their edge orbits is exactly ((O.). In other words, EmeN(n) Enoyy ENIOY) (f)( v) = )o
and since f(v) has exactly
Thus, by induction, we can easily see that for m matched subgraphs Gş H where v E VG, and Orb( OY it holds that .o! (v) and EveN(w) Ejooyevoo)) eNiOP) of)(u,)) v) m* O.) Then follows that:
xx (0) deg(oy) uEN(v) ):O)))
Σ
Σ
I v)
This expression shows that vertex identifiers can inferred by edge identifiers. The opposite does not necessary hold, since if we know the vertex identifiers xy (v), 2 (u) of an edge (v, u) we might not be able infer w (u, v). That is because do not know how many of the subgraphs in x. (v) and æ. (u) are common, i.c. they contain both nodes.
The rest of the proof is straightforward: the graph H, with L layers and width w defined as in the main paper, i.e. at each layer ver- tex hidden states are updated by h(+1(v) (v) = Up++1 (v), Ms)*+ where MSG = EuEN(O) M++1 ((+1(h(()) (h)(),, (u), (o), (u), af (u, v))). Then, there exists a GSN-e with 1 layers, where the first layer has width di + dy and implements the following function:
will assume GSN-v using substructure counts of
19

---

Under review as a conference paper at ICLR 2021
Up (h'(v) (SG (b)) = [h'( [b((t)) where:
MSG
E
M
(h' (b'( xx(,
wEN(F)
Σ
Σ
u);
deg(oy)
ueN(v) p:oy (NE
E
Σ
E d (u, v)]
deg(O wEN(r) s0y e
(x((t)
Note that since M is universal approximator, then there exist parameters of M with which the above function can be simulated. The next T. layers of GSN-e can implement a traditional MPNN where now the input vertex features are [h (v); (v)] (which is exactly the formulation of GSN-v) and this concludes the proof.
B COMPARISON WITH HIGHER-ORDER WEISFEILER-LEHME TESTS
B. THE WL HIBRARCHY
Following the terminology introduced in Maron et al. (2019a). we describe the so-called Folklore WL family (k-FWL). Note that, in the majority of papers on GNN expressivity (Morris et al. 2019] Maron et al. 2019at Chen et al. 2020) another family of WL tests is discussed, under the terminology k-WL with expressive power equal to (k F)LL In contrast, in most graph theory papers on graph isomorphism (Cai et al. 1992 Fürer 2017 Arvind et al. 2019) the k-WL term is used describe the algorithms referred to as FWF in GNN papers. Here, we follow the k-FWL convention to align with the work mostly related ours.
The k-FWL. operates on k-tuples of nodes v = (v) U2,-.... ......... 0k) to which an initial colour (v) is assigned based on their isomorphism types (see section B.3). which can loosely be thought of as generalisation of isomorphism that also preserves the ordering of the nodes in the tuple. Then, at each iteration the colour refined follows:
(++ = HASH (v),,
(V.2),.. (vv))))..,,(((.x))))))) (VV.)))))
(8)
where Vujj = (V1, 12, ... - U, Uj+1, .., Uz).
The multiset ? (c' (v..)))) (Vu.2), (v..k) Suev can be perceived as a form of generalised neighbourhood. Note here, that information is saved in all possible tuples in the graph, thus each k-tuple receives information from the entire graph, contrary to the local nature of the I-WL test.
B.2 WHEN CAN GSN BE STRONGER THAN 2-FWL?
In order to give further intuition in the limitations of the 2-FWI., in the following section we describe specific family of graphs which 2-FWI. is known to be unable disambiguate.
Definition B.1 (Strongly regular graph). A SR(n.d.A.p) -.gaaph is regular graph with nodes and degree d, where every two adjacent vertices have always mutual neighbours, while every two non-adjacent vertices have always μ mutual neighbours.
2-FWL will always decide that pair of SR graphs with the same parameters n., d. X, are isomorphic, since all 2-tuples of the same isomorphism type have the exact same generalised neighbourhood, leading 2-FWL to converge to its solution at initialisation. On the other hand, as we show in section of the main paper, GSN can tell strongly regular graphs apart by using small-sized substructures. Although it is not clear if there exists certain substructure collection that results in GSNs that align with the WL hierarchy, we stress that this is not a necessary condition in order to design more powerful GNNs. In particular, the advantages offered by k-WI. might not be able outweigh the
20

---

Under review as a conference paper at ICLR 2021
disadvantage of the larger computational complexity introduced. For example, 2-FWL equivalent GNN will still fail to count 4-cliques (a frequent pattern in social and biological networks) or eycles (a common ring structure in organic molecules). Therefore, suggest that it might be more appropriate to design powerful GNNs based on the distinct characteristics of the task at hand.
B.3 WHY DOES 2-FWL FAIL ON STRONGLY REGULAR GRAPHS?
Proof. We first rigorously describe what an isomorphism type is. Two k-tuples v {vf, 1g 2.... vE). v = [1], n2 . vk) will have the same isomorphism type iff:
Vi,j (0, 1, ,...,,,, k),
0f + u
of
Vi,je {0, kk..,,kk..
+ 2
uS. where means that the vertices are adjacent.
Note that this is stronger condition than isomorphism, since the mapping between the vertices of the two tuples needs to preserve order. case the graph is employed with edge and vertex features, they need to be preserved as well (see Chen et al. (2020) for the extended case).
For the 2-FWI. test, when working with simple undirected graphs without self-loops, we have the following 2-tuple isomorphism types:
* v {U1, : vertex type. Mapped to the colour c = Co
V {u1, 02) and in of uz: non-edge type. Mapped to the colour (0 09
{ui, 02) and u2a edge rype. Mapped to the colour c C-y
For each 2-tuple v = (ui, v2). generalised "neighbour" is the following tuple: (Va,1, Vu,2) ((u, v2), w)). where u an arbitrary vertex in the graph.
Now, let consider a strongly regular graph SR(,.d.A.1). We have the following cases:
generalised neighbour of a veriex type tuple: (Va,1, Vu,2) = ((u, 01), (vi, uv), The corre- sponding neighbour colour tuples
(Ca: ca) if 11 u.
cg) 11 of u.
(cy, if Uj u.
The update of the 2-FWL is: (v) HASH
Cas ((ca;
(cg, ca)
(.,,
I time
times
d times
same for all vertex type 2-tuples.
generalised neighbour of non-edge type tuple: (Vu.1, Va,2) = ((u, U2), (V1, (1), The corresponding neighbour colour tuples are:
(Ca, Cg) 022 u.
(c), if v1 u,
Ccy) if 02 and 11 , u,
(cg, if and 12 , u,
(ca, u1 of and 0/2 , u.
- (cy, Uj ~ u and U2 ~ u.
The update the 2-FWL is:
( (v) HASH ce. (Caa, cs). (cs, (cs, (c,, CB). (cg,
(cg. ce)
1 time
I time
times
times
2 (2d pD) times
times
same for all non-eedee type 2-tuples
21

---

Under review as a conference paper at ICLR 2021
generalised neighbour of edge rype tuple:
(Ca, Cy) V2 = u,
Cay,Ca i1 u,
(g) 02 ~ u and 01 + u,
(c), if 01 and U2 of u,
(c)) u1 of and 12 + u.
(Cy, if and 22 u.
The update of the is:
(v) HASH Cy. (Co, Ca), Cod.
(cy, Ca) (cp, Cy)
(cp, Ca) (2d X) times
time
times
times
times
same for all edge type 2-tuples.
From the analysis above, it is clear that all 2-tuples the graph of the same initial type are assigned the same colour in the 1st iteration of 2-FL.. In other words, the vertices cannot be further partitioned, so the algorithm terminates. Therefore, two SR graphs have the same parameters n.d.A,j then 2-FWL will yield the same colour distribution and thus the graphs will be deemed isomorphie.
C EXPERIMENTAL SETTINGS ADDITIONAL DETAILS
In this section, we provide additional implementation details of our experiments. All experiments performed on server equipped with 8 Tesla V100 16 GB GPUs, except for the Collab dataset where a Tesla V100 GPU with 32 GB RAM was used due to larger memory requirements (a large percentage of Collab graphs dense even nearly complete in some cases). Experimental tracking and hyperparameter optimisation were done via the Weights & Biases platform (wandb) (Biewald 2020). Our implementation is based on native PyTorch sparse operations (Paszke et al. 2019) in order to ensure complete reproducibility of the results. PyTorch Geometric (Fey & Lenssen 2019 was used for additional operations (such as preprocessing and data loading).
In each one of the different experiments we aim to show that structural identifiers can be used off-the-shelf and are independent of the architecture. At the same time we aim to suppress the effect of other confounding factors in the model performance, thus wherever possible we build our model on top baseline architecture. More details in the relevant subsections. Interestingly, we observed that in most of the cases it was sufficient to replace only the first layer of the baseline architecture with a GSN layer, in order to obtain a boost performance. This can be understood by considering that if the update and message functions to preserve the input information in their output (in the hidden states of the vertices with regards to vertex counts, in the hidden states of the endpoints of the edges with regards to edge counts).
sufficiently expressive, then they should be able to learn
Throughout the experimental evaluation the structural identifiers (v( and ( u}) are one- hot encoded, by taking into account the unique count values present in the dataset. Other more sophisticated methods can be used, e.g. transformation to continuous features via a normalisation scheme or binning. However, we found that the number of unique values our datasets were usually relatively small (which is a good indication of recurrent structural roles) and thus such methods were not necessary.
C.1 GRAPH REGRESSION ON ZINC
Experimental Details: The ZINC dataset includes 12k molecular graphs of which 10k form the training set and the remaining 2k are equally split between validation and test (splits obtained from Molecule sizes range from 9 to 37 nodes/atoms. Node features encode the type of atoms and edge features the chemical bonds between them. Again, here node and edge features one-hot encoded.
https: / qi thub. com/ ffom/graphhn httpgggaaapeeeaaaaaaaaa wwwpa///wwbeeccaaain.ggoooooe
22

---

Under review as a conference paper at ICLR 2021
We re- ---mpleemeeed the GIN baseline (GINt in Table 2 of the main paper). We extended GIN with
structural identifiers as in Eq. [I and 12 (GSN model in Table 2). Our stronger baseline (MPNN-E EF
model in Table 2 updates node representations as follows: h (v) = Up (h' (v), MSG (v))
MSG'+!(v)
E uEN(()
("))
(9)
MS) = E (²(h'()) h' e((u,))))
(10)
wEN(e)
where UP" and M functions are MLPs and cl (f, v)}) are edge features. Our extension with structural identifiers (GSN-EF model in Table 2 is precisely the model of Eq. A..3 or 4 of the main paper. Observe that, probably due to the fact that the ZINC dataset is larger and more stable, the general MPNN-based formulation performs better than the GIN-based counterpart.
Following the same rationale as before, the network configuration is minimally modified w.r.. the baseline of Dwivedi et al. (2020), while here no hyperparameter tuning is done, since the best performing hyperparameters are provided by the authors. In particular, the parameters are the following: 4 message passing layers, no jumping knowledge, transformation of the output of the last layer by a MLP, readout: sum, batch size: 128, dropout: 0.0, network width: 128, learning rate: 0.001. The learning rate reduced by 0.5 (decay rate) after 5 epochs (patience) without improvement in the validation loss. Training is stopped when the learning rate reaches the minimum learning rate value of 10 Validation and test metrics are inferred using the model the last training epoch.
We select our best performing substructure related parameters based on the performance in the validation set in the last epoch. We search cycles with k 3, ..... 10, graphlets against motifs, and GSN-v against GSN-e. The chosen hyperparameters for GSN are: GSN-e, cycle graphlets of 10 nodes and for GSN-EF: GSN-v, cycle motifs of 8 nodes. Once the model is chosen, we repeat the experiment 10 times with different seeds and report the mean and standard deviation of the test MAE in the last epoch. This is performed for all models that we implemented and compared (GINI, MPNN-EF, GSN, GSN-EF).
In Table we include an additional comparison between the main methods, where we maintain approximately constant parameter budget (approx. 100k parameters; we adjust network width to keep this number consistent across different models), as suggested in Dwivedi et al. (020). Again here, GSN significantly outperforms the baselines, hence the improvement is insensitive to the absolute number the parameters.
Fixed parameter budget:
Table 5: MAE on ZINC, Experiments with the same parameter budget (100K)
Method GINT
Test MAE
0.388-10.015 0.324-10.006
MPNN-EF
GSN
0.193+0.010
GSN-EF
0.154+0.002
Generalisation: empirical observations: We repeat the experimental evaluation on ZINC using different fractions of the training set. We compare our best baseline model (MPNN-EE in Table against GSN with the best performing substructure (GSN-EF in Table 2 In Figure 6 we plot the training and test errors of both methods. Regarding the training error, GSN consistently performs better, following our theoretical analysis on its expressive power. More importantly, GSN manages to generalise much better even with a small fraction of the training dataset. Observe that GSN requires only 20% of the samples to achieve approximately the same test error that MPNN achieves when trained on the entire training set.
In Table 6 we provide the disambiguation scores 8 as defined in section of the main paper for the different types of substructures. Note that these are computed based on vertex structural identifiers (GSN-v).
Disambiguation Scores:
23

---

Under review as a conference paper at ICLR 2021
226
Mean Abselute
223
0.2
2.4
320
339
20
20
60
Training Set Fraction (1)
Figure 6: Train (dashed) and test (solid) MAEs for GSN-EF(blue) and MPNN-EF(red) as a function of the dataset fraction employed in training.
Table 6: Disambiguation scores 8 on ZINC for different substructure families and their maximum size k. Size k = 0 refers to the use of the original node features only.
Cycles
Paths
Trees
0. 196
0.196
0. 196
0. 199
0.540
0.540
0.200
0.746
0.762
5
0.256
0.866
0.875
0.327
0.895
0.897
0.330
0.900
0.900
0.330
0,901
0.901
0.330
0,901
0.901
10
0.330
0.901
0.901
C.2
SYNTHETIC EXPERIMENT
cecs. anu. edu. au/ bddm /ata html) use all the available families of graphs with size of at most 35 nodes:
For the Strongly Regular graphs dataset (available from
SR(16,6,2,2); graphs
12,25,12,5.6) 15 graphs
10,26,10,3,4) 10 graphs
12,28, 4 graphs
SR(29,14,6,7): graphs
SR(35,16,6.8): 3854 graphs
* 18,35,18,9.9); 227 graphs
The total number of non-isomorphic pairs of the same size is Rs 7 10?. We used a simple 2-layer architecture with width 64. The message aggregation was performed in the general formulation of Eq. and 6 of the main paper, where the update and the message functions are MLPs. The prediction inferred by applying a sum readout function in the last layer (i.e. graph-level representation is obtained by summing the node-level representations) and then passing the output through a MIPP (we did not use jumping knowledge from intermediate layers (Xu et al.) (018)). Regarding the substructures,
graphlet counting, certain motifs (e.g. cycles of length up 7) are known to be unable to distinguish strongly regular graphs (since they can be counted by the 2-FWL (Fürer 2017 Arvind et al. 2019)).
Given the adversities that strongly regular graphs pose in graph isomorphism testing, would be interesting see how this method can perform in other categories of hard instances, such as the classical CFI counter-examples for k- k-WL proposed in Cai et al. (1992), and explore further its expressive power and combinatorial properties. We leave this direction to future work.
24

---

Under review as a conference paper at ICLR 2021
Table 7: Graph Classification accuracy on various social and biological networks from the TUD Datasets collection https: htt.//hrsssrrrrrreeeeeeeeee.. github. wer..oooddtttto io/datasets/ Graph Kernel methods are denoted with an * For completeness we also include methods that were evaluated on potentially different splits. The top three performance scores are highlighted as: First, Second, Third.
Dataset
MUTAG
PTC
Proseins
NCII
Collab
IMDB-B
IMDB-M
sine
T88
544
11I3
4TT0
S000
1000
1300
classes
2
2
2
2
2
avg nodes
25.5
39.1
29,8
74.4
DGK (hos) (Yaandar & Vishyamahum 2015
87.4 1:77
61112266
75.7:03
80.3 205
75.1
67 670:00
44.6:003
PSGD*
Verila & Zimuyy 2017)
92:11
62.81
73.42
79.8
80.04L
73.61
$2.41:
alffrent splits
AWE- WNE-F--10800
pogtor Buntayy 2018
87,919.88
NIA
NIA
N/A
71.11.5
73.1133
$1..1477
WWE-DD-rccmgg
N/A
NIA
NIA
N/A
73.9119
74.51:8
$1,51336
RCC (Simloyary&
NIA
76,8+
N/A
PSCNTET0F Nggeet al 2016
92,611122
60.014.88
75.9.2.8
78.6119
72.612.2
710012
45.2.12.8
DiliPed (iin af 70116
N/A
NIA
76.2:
NIA
75.5
N/A
NIA
CCN (Keine 3T1X
91.6+7.2
716+7.0
NIA
76.++-1
N/A
NA
N/A
1-2-3
2019
86.1+
609+
75.5+
762+
74
49.5+
59.6
A days
GK* (k-3) Shegr cistirisizi oral. 2009
81.411.7
55.710.55
714-10.31
62.51033
N/A
NIA
NIA
PX* NNuumiin el al 2016
76.0122
$9.512.4
73.7.10.7
82.510.5
N/A
NIA
N/A
sanes 9004
WL
kimy (Sliargs
2011
91.415.77
59.11433
75.0:33.1
86.01 1.8
78.1119
73.8139
50.91338
GNTK
90.0+855
67.9+69
75.6+4.2
8..2+1.5
13.6++1.0
52.8+4.66
DCNN
Jawwan lowsley
2016
56.6+110
49
DGCNN Teinine uisli 2015
858118
58.612.5
75.5.10.
74.410.
73.810.5
70.01:0.
47.810.99
IGN Martireaii 211000
13
SH.5+6699
7..6-1555
74.3+227
78.3+2.5
72 DID:555
48.7+
GIN
Aurermie 2013
89.4+56
64.6+7.0
76.2+2.8
82.7+1.7
8112++1
75. 1+5.1
52.3+288
PPGNT
(Mlard 2019
9..6
66.246.6
77.2=4.7
83.2+1.1
$1,4+1.4
02:50..88
50.5+33.
Natural
50Ma
19
66.4111779
71.71=1044
82.37
73.50=2201
11,27++1.50
GSN-e (Ours)
9.6+7.5
68.277.2
766655.0
83.5+ 2.3
85.5+1.2
77.8-333
54.3+3.3
6 tcyclas)
6 (cycles)
4 (cliques)
15 icycle)
3 (sringles)
(clique)
S (eliques)
GSN-v (Ours)
92.217.5
67.415.7
74.625.0
83,5220
82.711.5
76.8220
$2.6136
(cycles)
(cycles)
(cliques)
(Irianglos)
(cranggee)
(cliques)
(cliques)
C.3 TUD GRAPH CLASSIFICATION BENCHMARKS
For this family of experiments, due to the usually small size of the datasets, we choose parameter- efficient architecture, in order reduce the risk of overfitting. In particular, we follow the simple GIN architecture (Xu et al. 2019) and we concatenate structural identifiers to node or edge features depending on the variant. Then for GSN-v, the hidden representation is updated as follows:
h (v) Up*+1 (lb (Ih(())
Σ [b((w):xvu)l) MEN.
(11)
and for GSN-c: (1) (1)))))))
( ueN,
(12)
where xE((e, v)) is dummy variable (also one-hot encoded) used to distinguish self-loops from edges. Empirically, we did not find training the parameter used GIN to make a difference. Note that this architecture is less expressive than general formulation. However, we found it to work well in practice for the TUD datasets, possibly due to its simplicity and small number of parameters.
We implement architecture similar GIN (Xu al., 2019), i.e. 4 message passing layers, jumping knowledge from all the layers (Xu et al. 2018) (including the imput), transformation each intermediate graph-level representation by a linear layer, sum readout for biological and mean readout for social networks. Node features are one-hot encodings of the categorical node labels. Similarly to the baseline, the hyperparameters search space is the following: batch size in {32, 128) (except for Collab where only 32 was searched due to GPU memory limits), dropout in (0,0.5), network width in (16.32) for biological networks, 64 for social networks, learning rate in {0.01, 0.001), ) decay rate in {0.5,0.9} and decay steps in (10,50} (number of epochs after which the learning rate is reduced by multiplying with the decay rate). For social networks, since they are not attributed graphs, we also experimented with using the degree node feature, but in most cases the structural identifiers were sufficient.
Model selection is done in two stages. First, choose substructure that we perceive as promising based on indications from the specific domain: triangles for social networks and Proteins, and 6-cycles (motifs) for molecules. Under this setting tune model hyperparameters for GSN-e model. Then, we extend our search to the parameters related to the substructure collection: i.c. the maximum size k and motifs against graphlets. In all the molecular datasets search cycles with
25

---

Under review as a conference paper at ICLR 2021
Table 8: Chosen hyperparameters for each of the two GSN variants for each dataset.
Dataset
MUTAG
PTC
Proteins
NCI1
Collah
IMDB-B
IMDB-M
batch size
32
128
32
32
32
32
32
width
32
16
32
32
64
64
64
decay rate
0.9
0.5
0.5
0.9
0.5
0.5
0.5
decay steps
50
50
10
10
50
10
10
GSN-c
dropout
0.5
0
0.5
0
0
0
0
Ir
10 3
10-3
10
10-3
10-2
10-3
10-3
degree
No
No
No
No
No
No
Yes
substructure type
gruphlets
motifs
same
graphlets cycles
same
same
substrucure family
cycles
cycles
cliques
clique
clique
cliques
k
6
15
batch size
128
32
width
16
64
decay rate
0.9
0.9
0.5
decay steps
50
50
10
50
10
GSN-v dropout Ir degree
0.5
0,5
0
0
10
10-3
10-4
10
10-2
10-3
10-3
No
No
No
No
No
Yes
Yes
suhstructure type
graphlets cycles
graphlets cycles
same cliques
same cycles
same
same clique
same
substrucure family
cliques
cliques
k
12
10
3
3
k 3...., 12, except for NCII, where we also consider larger sizes due to the presence of large rings in the dataset (macrocycles (Liu et al. (017)). For social networks, we searched cliques with k 3, 4, 5. In Table 8 we report the hyperparameters chosen by our model selection procedure, including the best performing substructures.
The seven d we chose the intersection of the datasets used by the authors of our main baselines: the Graph Isomorphism Network (GIN) (Xu et al. 2019), a simple, yet powerful GNN with expressive power equal the 1-WL test, and the Provably Powerful Graph Network (PPGN) (Maron et al. 2019a), a polynomial alternative to the Invariant Graph Network (Maron et al.] 2019b) that increases its expressive power match the 2-FWL. We also compare our results other GNNs as well as Graph Kernel approaches. Our main baseline from the GK family is the Graph Neural Tangent Kernel (GNTK) (Du al. 2019a), which is kernel obtained from GNN of infinite width.
This operates in the Neural Tangent Kernel regime (Jacot et al. 2018 Allen Zhu et al.) 2019 Du
al. 2019b).
Table is an extended version of Table of the main paper, where the most prominent methods are reported, regardless of the splits they were evaluated on. For DGK (best variant) (Yanardag
& Vishwanathan (2015), FSGD (Verma & Zhang] 2017). AWE (Ivanov & Burnaev (018). ECC
(Simonovsky & Komodakis 2017), PSCN (Niepert et al. 2016), DiffPool (Ying et al. 201 CCN (Kondor et 2018)) (slightly different setting since they perform a train, validation, test split), 1-2-3
GNN (Morris et al. 2019) and GNTK (Du et al. 2019a), we obtain the results from the original papers. For RWK (Gärtner et al. 2003), GK (Shervashidze et al. 2209)), PK (Neumann et al. 2016), DCNN (Atwood Towsley| 2016) and DGCNN (Zhang et 2018), we obtain the results from the DGCNN paper, where the authors reimplemented these methods and evaluated them with the same split. Similarly, we obtain the WLK (Shervashidze et al.) (011)) and GIN (Xu et al. (019) results from the GIN paper, and IGN MMaron 2019b) and PPGN (Maron al. 2019a) results from the PPGN paper.
C.4 GRAPH CLASSIFICATION ON OGBG MOLAIV
The ogbg-molhiv dataset contains 41K graphs, with 25.5 nodes and 27.5 edges on average.
As most molecular graphs, the average degree is small (2.2) and they exhibit tree-like structure (average clustering coefficient 0.002). The average diameter 12 (more details Hu al. (2020)).
We follow the design choices of the authors of Hu et al. (022)) and extend their architectures to include structural identifiers. Initial node features and edge features are multi-hot encodings passed through linear layers that project them in the same embedding space, i.c. hv(v) w h (v),
more details the deseription of the datasets and the corresponding tasks be found at Xu al. 2019
26

---

Under review as a conference paper at ICLR 2021
Table 9: Chosen substructures for mabg-molhiv
Model
GSN-AF
GSN-VN
GSN-VN -AF
features
edges (GSN-e)
vertices (GSN-v)
edges (GSN-e)
substructure type substructure family k
graphlets cycles
graphlets
graphlets
cycles
cycles
12
e'(fe,u) = W een u)). The baseline model is a modification of GIN that allows for edge features: for each neighbour, the hidden representation is added to embedding of its associated edge feature. Then the result is passed through a ReLU non-linearity which produces the neighbour's message. Formally, the aggregation is follows:
+ h (+) = Up h'(())+ + (b( +f'
(13)
WEN.
A stronger baseline is also proposed by the authors: in order to allow global information to be broadcasted to the nodes, a virtual node takes part in the message passing (-VN setting in Table the main paper). The virtual node representation, denoted as G is initialised zero vector Go and then Message Passing proceeds as follows:
bC = hw) + GO, (b) Up h(( Σ a (b'(1) (6(())+(((uu)))) ((((a)))))
MEN.
(14)
- G EE((w)
MEN.
We modify this model, as follows: first the substructure counts are embedded into the same embedding space as the rest of the features. Then, for GSN-v, they are added to the corresponding node embeddings: (w( (v) + Wi (v),), or for GSN-e, they are added to the edge embeddings (fr,,, u)) c'
w (E((u, v)). Interestingly, even with this simple modification we obtain a considerable improvement the performance of the model all splits, thus demonstrating strong generalisation capabilities.
We use the same hyperparameters as the ones provided by the authors, i.e. message passing layers, no jumping knowledge. mean readout, linear layer applied after the readout, batch size: 32, dropout: 0.5, network width/cmbedding dimension: 300 (in the ogb implementation the hidden layer of each MLP has dimensions equal neteww width, contrary to the rest of the experiments where network width and MLP hidden dimensions are equal), learning rate: 0.001.
We select our best performing substructure related parameters based the highest validation ROC- AUC (choosing the best scoring epoch as in Hu et al. (020)). We search cycles with k = 3...., 12, graphlets against motifs, and GSN-v against GSN-e (see Table for the chosen parameters). We repeat the experiment 10 times with different seeds and report the mean and standard deviation of the train, validation and test ROC-AUC, again by choosing the best scoring epoch w.r.t the validation set. We repeat the process for all 3 settings independently (GSN-VN, GSN-AF, GNN-VN-AF).
Impact of the 'Scaffold-based' dataset split: Motivated by the differences between the train, validation and test distributions in the ogbg- molhiv dataset (the authors of Hu et al. (2020) implement a "scaffold splitting" procedure, i.e. molecules with different 2t-structure are assigned to a different partition of the dataset), we studied how different substructure sizes affect the performance on different sets. In particular, as shown in Table TO we observed that substructures that yielded the best test score did not always attain best validation performance well, this confirming the characteristic discrepancy between the test and validation distributions.
Lastly, we note that these results were obtained with a GSN model using the structural features only at its input. In fact, it is possible to 'inject' the structural features at each message passing layer of the architecture, effectively accounting for skip connection acting structural identifiers. Although we observe performance improvements, the typical validation/test distribution discrepancy persists. Results reported in Table 10 ("GSN
27

---

Under review as a conference paper at ICLR 2021
Table 10: ROC-AUC on ogbg-molhis molhiv. Performance with different substructures and skip connec- tions for the structural identifiers
Method
Training
Validation
Test
GSN
94.29 + 3.38
86.58 + 0.84
77.99 + 1.00
GSN (h: = 8)
94.33 + 2.38
85.59 0.82
78.20 + 1.69
GSN skip
93.77 = 3.38
86.44=1.09
78.07 78.55 + 1.25
GSN skip (A: 8)
93.97 + 2.70
85.30 + 1.01
C.5 STRUCTURAL FEATURES & MESSAGE PASSING
The baseline architecture treats the input node and edge features, along with the structural identifiers, as a set. In particular, we consider each graph as set of independent edges (u, u) endowed with the features of the endpoint nodes h(v), h(u), the structural identifiers (v()), xu) and the edge features e(u, u). and we implement a DeepSets universal set function approximator Zaheer et al.
2217 to learn prediction function / ((h()), h(u), (v(v), (w), u)) (u, w) E Ec)
E(ra)eee @ (h(w), h(w), x( (o), xy (u), e(t, u)) with &g the edge set of the graph and p; ob modelled as MLPs. This baseline is naturally extended to the case where consider edge structural identifiers by replacing (xv (v), Xy (u)) with (v, u). For faimess of evaluation, we follow the exact same parameter tuning procedure as the one we followed for our GSN models for each benchmark, ie. for the TUD datasets we first tune network and optimisation hyperaparameters (network width was set be either equal to the ones we tuned for GSN, or such that the absolute number of learnable parameters was equal to those used by GSN; depth of the MLPs was set to 2) and subsequently we choose the substructure related parameters based on the evaluation protocol of Xu et al. (2019). For ZINC and ogbg-molhiv we perform only substructures selection, based on the performance validation set. Using the same widths as GSN leads to smaller baseline models w.r.t the absolute number of parameters, and interestingly observed this to lead particularly strong performance in some cases, especially Proteins and MUTAG, where our DeepSets implementation attains state-of-art results. This finding motivated us explore 'smaller' GSNs (with either reduced layer width single message passing layer). These GSN variants exhibited similar trend, i.e. to perform better than their 'larger' counterparts over these two datasets. We hypothesise this phenomenon be mostly due to the small size of these datasets, which encourages overfitting when using architectures with larger capacity. In Table in the main paper, we report the result for the best performing architectures, along with the number of learnable parameters.
the
28


Reviews:
[{"review_id": "uEp9z7a5qCr", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the expressivity of graph neural networks, and proposes a new approach to improve GNN’s expressivity by encoding nodes and edges with features via subgraph isomorphism counting. The proposed solution contains some merit, and the experimental results on graph classification task demonstrates the superiority of the proposed approach.\n\nPros:\n1.\tThis paper addresses an important problem in GNNs, which is to improve the expressivity of GNNs.\n2.\tThe proposed solution is interesting, which is to include how many isomorphic subgraphs from a given list a node or an edge is contained in as additional features.\n3.\tThe experimental results on multiple datasets and different graph-level tasks are better than baselines.\n4.\t Nice theoretical analysis.\n\nCons:\n1.\tMy biggest concern lies in the time complexity of the proposed approach. Although the paper claims that in practice it is not that bad, the worst time complexity is still high. Also, the substructure selection brings us back to feature engineering, or we will face too many possible substructures.\n2.\tMore challenging graph tasks are expected to demonstrate the necessity of the proposed approach. \n\nDetailed comments:\n1.\tIn the abstract and introduction, it is mentioned that existing GNNs are bounded by WL-test, and are not able to detect and count graph structures. It is expected to see experiments are on these more challenging tasks, in addition to graph classification and regression tasks. Graph isomorphism test is an interesting task, and the design is smart.\n2.\tDiscussions on how to select substructures on bigger size of graphs are expected.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "aSz_hJF3SYo", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a natural extension of Message Passing Neural Net (MPNN)  by incorporating structural features. These structural features are computed as the counts from different substructures (like small lines, stars or complete graphs) induced in the original graph. These counts are combined to obtain a new feature per node or per edge. Then these features are used in a standard MPNN. The authors then show that the resulting GNN is more expressive and they validate this claim experimentally.\n\nThis idea is interesting and clearly explained in the paper but I think the paper could be greatly improved after addressing the following issues:\n \n1- the authors should clarify their position with regards to invariance. Indeed, as explained shortly on page 3 when commenting Loukas(2020), it is easy to make a GNN powerful if we remove the constraint to be invariant (or equivariant). Hence, as I understand it, the authors are proposing an algorithm that is equivariant. If this is the case, it would be great to have a clear formal statement that GSN are equivariant and to give a mathematical proof.\n\n2- the theoretical content of the paper should be improved:\n\n a- the first part of Proposition 3.1 is straightforward and I find the wording of the second statement unclear: what does '... or any not necessarily induced subgraph...' mean?\n\n b- from a theoretical perspective, it seems that both GSN-v abd GSN-e have the same expressive power. Is it true?\n\n c- a similar idea as the one presented in this paper was presented in : Coloring graph neural networks for node disambiguation  by George Dasoulas, Ludovic Dos Santos, Kevin Scaman, Aladin Virmaux https://arxiv.org/abs/1912.06058 [arxiv-col] The main advantage of the current paper as opposed to [arxiv-col] is to propose an explicit coloring thanks to the structural features. But the theoretical analysis made in [arxiv-col]  goes much deeper than this paper and probably could be adapted by the authors. For example, Corollary 3.1 could probably be replaced by a universality property, i.e. GSN with k=n-1 is universal.\n\n3- the experimental evaluation is not convincing. To make it more convincing, the authors should include an ablation study for all their experiments by comparing their performances with the performances obtained with the structural features only. Such an ablation study would show the benefit of adding the MPNN on top of these features. \n\n[After rebuttal] I think the authors improved their paper by taking into account the remarks. Given the last results obtained in Table 4, it looks like the structural features are indeed very good features in practice as they allow to boost the performances of a very simple invariant architecture like Deepset. I think the authors should explore how they can combine this approach with the coloring approach to get better GNN.", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZeysRS8k6eO", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Reasons for score:\nThe idea of using small graphs to characterize local topologies and guide message passing in interesting. However, the graph isomorphism computation part has problem. Experimental results are not conclusive. The written need improvement in some part of the manuscript.  \n\nPros: A new method (GSN: Graph Substructure Network) is proposed to a topologically-aware message passing method that better utilize graph substructure information. The method tries to tackles the limitation of traditional GNN in exploring graph structure.  It is a good idea to pass messages differently depending on their local topologies. This is done through using a set of predefine small graphs to characterize local topologies. The authors showed that GSN was more expressive than traditional GNNs. A good number of experimental evaluations were performed.\n \nCons: It is not clear priorly how to define a good set of small graphs, especially when considering beyond immediate neighbors. In addition, node features are not considered in graph isomorphism, which can lead to incorrect subgraph matching. The experimental results on some of the datasets (such as, MUTAG, PTC, Proteins and NCI1 in table 1) do not appear to be significantly better than those of the previous approaches when considering the variances of different runs. In addition, much better results were reported on the ogb-molhiv leaderboard (https://ogb.stanford.edu/docs/leader_graphprop/#ogbg-molhiv). Figure 1 is confusing.  Should the number in the yellow square on the left be 5? A more self-contained explanation of the figure is appreciated. It will help readers if the authors can visualize a few examples (e.g., contributions of small graphs) to explain why their approach works better.", "extra_scores": {}, "extra_text": {}}, {"review_id": "TFtZY5xnTh_", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work proposes the Graph Substructure Network (GSN) to encode structural roles for different nodes so that the expressivity of Graph Neural Networks is improved. The core idea is to count the number of certain substructures, such as cycles, cliques, and triangles. Then the proposed MPNN encodes such substructure counting information into the message passing. Experimental results show that the proposed method can obtain better performance than the comparing methods. \n\nStrengths:\n+ The proposed method can encode important substructure information. It is important for graphs since, in many applications, the substructures can determine the functionality of graphs.\n \n+ The proposed method leads to better performance on different graph classification datasets. The experimental results can show the effectiveness of the proposed method.\n\nWeaknesses:\n- The main contribution of this work is counting the substructure information, which can be regarded as the preprocessing of graphs. However, how to properly select the graph set {H_1, … ,H_K}?  With different datasets at hand, the best choice can be quite different. Then how should we apply the proposed method? \n\n- The second concern is the complexity of the proposed methods. Counting different types of substructures can be very time-consuming. As mentioned in this work, the worst case can have O(n^k) complexity. When the graph size is large, we may need to count too many types of substructures. \n\n- The datasets are relatively small; most of them have less than 100 nodes per graph. Then larger datasets, such as RDT-B, RDT-M5K, and RDT-M12K, should be considered. I am wondering how many types of substructures need to be considered for these larger datasets to get better performance. \n\n- This work explicitly encodes substructure information into GNNs. Other existing methods, such as graph pooling methods, which can be considered to implicitly encode structural information. Then advanced pooling methods, such as Diffpool, Structpool, Min-cut Pool, etc., should be discussed and compared. \n\nI am willing to adjust my score if my concerns are properly addressed. \n\n=====Update after rebuttal=====\n\nI have read the authors' rebuttal. Considering the limitations and non-superior performance for larger datasets, I am keeping my score unchanged. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: We thank the authors for their detailed responses and the revised version, which addresses several of the questions raised by the reviewers.

The paper is correct and clearly written. All reviewers agree that the idea to add structural features in the message passing of graph neural networks is sensible. While different from previous work, the novelty is a bit incremental though, particularly given the previous work on colored graph neural network. The significance of the work is weak, given 1) the need to select "by hand" structural features that are passed as information, 2) the increased time complexity to compute the structural features compared to other GCNN, and 3) the experimental results that suggest that the benefit of the new approach is limited, particularly on challenging task.

To summarize, this is not a bad paper, but we consider it below the standard of ICLR in terms of originality and significance.
Decision: Reject