Weisfeiler and Lehman Go Cellular: CW Networks
Authors: Cristian Bodnar
Fabrizio Frasca
Nina Otter
Yu Guang Wang
Pietro Liò
Guido Montufar
Michael M. Bronstein
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph neural networks
graph representation learning
simplicial complexes
cell complexes
cw complexes
simplicial neural networks

Abstract: Graph Neural Networks (GNNs) are limited in their expressive power, struggle with long-range interactions and lack a principled way to model higher-order structures. These problems can be attributed to the strong coupling between the computational graph and the input graph structure. The recently proposed Message Passing Simplicial Networks naturally decouple these elements by performing message passing on the clique complex of the graph. Nevertheless, these models can be severely constrained by the rigid combinatorial structure of Simplicial Complexes (SCs). In this work, we extend recent theoretical results on SCs to regular Cell Complexes, topological objects that flexibly subsume SCs and graphs. We show that this generalisation provides a powerful set of graph "lifting" transformations, each leading to a unique hierarchical message passing procedure. The resulting methods, which we collectively call CW Networks (CWNs), are strictly more powerful than the WL test and not less powerful than the 3-WL test. In particular, we demonstrate the effectiveness of one such scheme, based on rings, when applied to molecular graph problems. The proposed architecture benefits from provably larger expressivity than commonly used GNNs, principled modelling of higher-order signals and from compressing the distances between nodes. We demonstrate that our model achieves state-of-the-art results on a variety of molecular datasets.

Weisfeiler and Lehman Go Cellular: CW Networks
Cristian Bodnar* University of Cambridge cb20150cam ac uk
Fabrizio Frasca" Imperial College London & Twitter f ffrasca@twitter.c .cmm
Nina Otter
Yu Guang Wang MPI-MIS, SJTU UNSW yuguang wang@unsw. edu, au
UCLA
otter@math.ucla.cem edu
Pietro Liò University of Cambridge p12198cam ac.uk
Guido Montúfar
Michael Bronstein Imperial College London & Twitter mbrronstein@twitterr...
MPI-MIS UCLA
montufar0matin ucla. edu
Abstract
Graph Neural Networks (GNNs) limited in their expressive power, struggle with long-range interactions and lack principled way to model higher-order structures. These problems can be attributed the strong coupling between the computational graph and the input graph structure. The recently proposed Message Passing Simplicial Networks naturally decouple these elements by performing message passing on the clique complex of the graph. Nevertheless, these models can be severely constrained by the rigid combinatorial structure Simplicial Complexes (SCs). In this work, we extend recent theoretical results on SCs to regular Cell Complexes, topological objects that flexibly subsume SCs and graphs. We show that this generalisation provides powerful set of graph "lifting" transformations, each leading to a unique hierarchical message passing procedure. The resulting methods, which we collectively call CW Networks (CWNs), are strictly more powerful than the WL test and not less powerful than the 3-WL test. In particular, we demonstrate the effectiveness of one such scheme, based on rings, when applied to molecular graph problems. The proposed architecture benefits from provably larger expressivity than commonly used GNNs, principled modelling of higher- order signals and from compressing the distances between nodes. We demonstrate that our model achieves state-of-the-- results variety of molecular datasets.
Introduction
The operations performed by message passing Graph Neural Networks (GNNs) emulate the structure of the input graph. While this property has clear computational advantages, it brings with it series of fundamental limitations. As observed by Xu et al. [74] and Morris et al. [55] the local neighbourhood aggregations used by GNNs are at most powerful the Weisfeiler- Lehmaan (WL) test 7 in distinguishing non-isomorphic graphs. Therefore, GNNs fail detect certain higer-order meso-scale structures such cliques (induced) cycles 2 15 which are particularly important in applications dealing with social and biological networks or molecular graphs. At the same time, many such layers have be stacked to make mangee interactions in the graph possible. Besides the computational burden this incurs, deep GNNs typically come with additional problems such as over wver-simothing [5]] and over-squashing [1] of the node representations.
Authors contributed equally.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

To address these problems, we propose a novel message passing procedure based on (regular) cell complexes, also known as CW complexes topological objects that form the building block of algebraic topology [8 When paired with theoreticalll-justifi
"lifting" transformation augmenting the graph with higher-dimensional constructs called "cells", our method results in a multi-dimensional and hierarchical message passing procedure over the input graph. Our approach generalises and subsumes the recently proposed Message Passing Simplicial Networks (MPSNs) [S]. which operate on simplicial complexes (SCs), topological generalisations of graphs. However, SCs have a rigid combinatorial structure that significantly limits the range of lifting transformations one could use to meaningfully modulate the message passing procedure. In contrast, show that cell complexes, which in turn generalise simplicial complexes and come with additional flexibility, allow one to construct new and better ways of decoupling the input and computational graphs.
Main Contributions To summarise, we propose message passing scheme operating on regular cell complexes. We call this family of models CW Networks (CWNs) and study their expressive power using a cellular version of the WL. test. We show that for an entire class of "lifting" transformations CWNs are at least as powerful as the WL test. Furthermore, we prove that for some of the maps in this class, CWNs can be strictly more powerful than WL, Simplicial WL (SWL) and also not less powerful than 3-WL. We also express the fundamental symmetries of these models and show how they can be seen as generalised convolutional operators on cell complexes. Experimentally. we focus our attention on particular "lifting" map based on induced cycles. When applied to molecular graphs, it leads to an intuitive hierarchical message passing procedure involving the atoms, the bonds between them and the chemical rings of the molecules. We demonstrate that this provably powerful approach obtains state-of-the results on popular large-scale molecular graph datasets and other related tasks. To the best of our knowledge, this is the first work proposing cell complex representation for molecules. Our code is available at htttpss/ /bttps://github wtt/wwwtteetttteeeeeeeecccocccet ceceeereeeaacchhheeeeeeee
Background
Definition 1 (Hansen and Ghrist 36).. A regular cell complex (Figure ! is topological space X together with a partition (X, Jop of subspaces X₂ of X called cells, and such that
1. For each x E X there exists an open neighbordhood of x that intersects finitely many cells. For all a, T we have that X, n Xx + 0 iff X, Xa. where X the closure of cell.
3. Every cell is homeomorphic to R.. for some (Regularity) For every a E Px there is a homeomorphism & of closed ball in Th to X such that the restriction of the interior of the ball is homeomorphism onto Xo.
We note that by condition (2) the indexing set Px has a poset structure
<> X, C Xx. while condition (4) guarantees that this poset structure encodes all the topological information about X. Thus, we can identify regular cell complex X with
Q3
this poset, called face poset of X. We also use 7 < a for the strict version of this partial order.
Φ2
Intuitively, one constructs a cell complex through a hierarchical gluing procedure. One starts with set of vertices (O-cells). Then edges (I-cells) are attached to these by gluing the end- points of closed line segments them. We have now only described a (multi) graph. However, one can generalise this even further by taking two-dimensional closed disk and glue its boundary (i.e. a circle) to any simple cycle in the (multi) graph previously built in Figure While we generally not concerned with dimensions above two, this can be further generalised by gluing the boundary of n-dimennional balls to certain (n 1) ce-s in the complex.
Figure 1: A cell complex X and the corresponding homeomorphisms to the closed balls for three cells of dif- ferent dimensions in the complex.
Consider the examples in Figure 3 The shown sphere is a cell complex obtained from two O-cells (i.e. vertices), to which two 1-cells (i.e. edges), which form the equator, were attached. The boundary
We use these terms interchangeably, For the latter, the C stands for "closure- -lossre-finite", and the W for "weak" topology. The term was coined by Whitehead 72).

---

and there is no cell 5 such that Figure 2:
Closed wwo-dimensional disks are glued to the bound- ary of the rings present in the graph (left). The result 2D regular cell complex (right).
Figure 3: A sphere and an empty tetrahedron. The latter also a simplicial complex.
of two 2-dimensional disks (i.e. the two hemispheres) were glued to the equator to form a sphere. The second example is tetrahedron with empty interior. is particular type of cell complex called simplicial complex (SC). The only 2-cells it allows are triangle-shaped. More generally, the n n-dimensional cells of SCs are n-simplices, which makes them slightly more rigid structures.
Definition 2. The k-skeleton of a cell complex X, denoted X ((k,, is the subcomplex of X consisting of cells of dimension at most k.
This definition is useful for referring for certain parts of the complex. For instance, x0) contains the vertices in the complex, while ( contains the vertices and the edges (i.e. the underlying graph).
The combinatorial structure the complex can be more compactly described by an incidence relation we call the boundary relation, whose reflexive and transitive closure gives the partial order defined above. The boundary relation describes what cells are on the boundary other cells. For instance, the edges of the sphere in Figure B are on the boundary of the 2-cells forming the two hemispheres.
Definition 3. We have the boundary relation a iff 0<Ō<T
We can use this to define the four types of (local) adjacencies present in cell complexes. These adjacencies will be the fundamental building block of our message passing procedure. To explain these in more familiar terms, for each adjacency, we exemplify how it shows up in graphs.
Definition (Cell complex adjacencies). For a cell complex X and a cell a Pxx we define:
1. The boundary adjacent cells B(a)= {r T d). These are the lower-dimensional cells on the boundary of a. For instance, the boundary cells of an edge are vertices.
2. The co-boundary adjacent cell C(r) = {T < T) These are the higher-dimensional cells with a on their boundary. For instance, the co- ro-boundary cells of a vertex are the edges is part of.
3. The lower adjacent cells (o) { 38 such that 5 < and 8 < T). These are the cells of the same dimension as a that share a lower dimensional cell on their boundary. The line graph classic example of this.
adjacencies between the edges
4. The upper adjacent cells Nç(a) = {T 36 such that a - and r < 5}. These are the cells of the same dimension as a that are on the boundary of the same higher-dimensie cell a. The typical graph adjacencies between vertices are the canonical example here.
Cellular Weisfeiler Lehman
The results in this section show how one can transform graphs into dimees--imenii cell complexes in such a way that performing colour refinement on the resulting cell complexes makes it easier test their isomorphism. The message passing model from Section will take advantage of these theoretical results. All proofs can be found in Appendix A
Overview
Definition 5. Let be colouring of the cells in complex X with Cor denoting the colour assigned to cell a E Px. Define B(g,T) == B(a) ((G)) and C(a, = C(T) We define the following multi-sets of colours:
The colours of the boundary cells a: cb(o) (fc, T B(o)}.
2. The colours of the co-boundary cells of a: ce(a) ((c- C(a)))
The lower adjacent colours of a: cy(a) (((,,, T and 8 B(a,T)B
4. The upper adjacent colours of c7(o) (((c,,c)) Ny(o) and C(
3

---

HASH
Old colour
2D calls the edge
Edges part of 2D & shared asll
Edges sharing a shardd vertee
Boundary
vertioes
Figure 4: The CWL colouring procedure for the yellow edge of the cell complex. All cells have been assigned unique colours to aid the visualisation of the adjacencies. Note that the yellow edge aggregates long-range information from the light green edge.
Note that unlike in graphs and simplicial complexes, the sets ( and C(o, r) have more than one element. For instance, two (closed) 2-cells might intersect in more than one edge (e.g. the two hemispheres in Figure D and conversely, two edges might be on the boundary of the same two 2-cells. This illustrates the more flexible combinatorial structure of cell complexes.
Cellular WL (CWL) We consider CWL, colour refinement scheme for cell complexes that generalises the Simplicial WL [ and WL [ZT] tests. We use oy to refer to the colour assigned by CWL to cell at iteration of the algorithm. When the input is a simplicial complex, this recovers the SWL algorithm. A step of the algorithm is graphically depicted in Figure 4 for a single cell.
1. Given a regular cell complex X, all the cells a are initialised with the same colour.
Given the colour of of cell a at iteration we compute the colour of cell at the next iteration d+11 by injectively mapping the multi-sets of colours belonging to the adjacent cells of a using perfect HASH function: ct HASH c (o) co( of (o), ) (o)).
The algorithm stops when a stable colouring reached. Two cell complexes are considered non-isomorphic if their colour histograms are different. Otherwise, the test is inconclusive.
First, state the following theorem from Bodnar et al. [ involving SWL and simplicial complexes. This theorem shows that on simplicial complexes, certain adjacencies can be pruned without affecting the non-isomorphic SCs that can be distinguished. This has important computational implications. Theorem 6. SWI. without coboundary and lower-adjacencies has the same expressive power in distinguishing non-isomorphic simplicial complexes SWL with the complete set of adjacencies.
It is not immediately clear whether equivalent theorem would also hold for cell complexes. This is because cells, unlike simplices, can have widely different shapes and, as described above, the adjacencies between them take more complicated forms. Nevertheless, show that positive result can be obtained.
Theorem 7. CWL without coboundary and lower-adjacencies has the same expressive power in distinguishing non-isomorphic cell complexes as CWL with the complete set of udjacencies.
We note this does not mean that the removed adjacencies are completely redundant in practice. Even if they are not needed from (theoretical) colour refinment perspective, they might still include important inductive biases that make them suitable for certain tasks.
We are now interested in examining various procedures for mapping, or "lifting", graphs into the space of regular cell complexes. Such a procedure can used to test the isomorphism of two graphs by performing colour refinement the cell complexes they are mapped to. The hope is that CWL applied to these cell complexes is more powerful than WL applied to the initial graphs. We will later show that for wide range of transformations, this is indeed the case. We start by rigorously defining what we mean by a "lifting".
Definition 8. A cellular lifting map is a function f G + X from the space of graphs G to the space of regular cell complexes X with the property that two graphs G1, G2 are isomorphic iff the cell complexes f(Gr), f(Gz) are isomorphic.
This property ensures that testing the isomorphism of the two cell complexes is equivalent to testing the isomorphism in the input graphs. This would not be the case two non-isomoprhic graphs were mapped to the same cell complex.

---

Example 9. It can be verified that the function mapping each graph to its clique complex fi.e. every (k++ + cl-cqique in the graph becomes a k-simplex) is cellular lifting map.
The clique complex lifting map from Example 2 has been used by Bodnar et al. S to show that SWL
is strictly more powerful than WL. We restate this result:
Theorem 10. SWL with clique complex lifting is strictly more powerful than WL.
natural question what other lifting transformations make CWL. strictly more powerful than WL? We first describe space of lifting transformations that make CWL at least as powerful as WI. Definition 11. A lifting map skeleton if for any graph G, the 1-skeleton of f(G) and G are isomorphic as (multi) graphs.
Intuitively, skeleton- preettoiinne liftings ensure that the additional structure added by the lifting map comes from attaching cells of dimension at least two to the graph. These mappings keep the 0-cells and 1-cells intact and are, therefore, restricted from making modifications to the input graph structure. An important remark is that for simplicial complexes, attaching simplices based on cliques present in the graph is the only possible skeleton preserving transformation. Once again, this illustrates the limitations of simplicial complexes for adding useful nigher-dimensiona structures to the graph.
Example 12. The function from Example y is also deeleton-preserving because the I-skeleton of the clique complex of a graph is trivially isomorphic to the graph. A lifting function mapping each graph to multi- graph where each edge is doubled by parallel edge is not skeleton skeleton- preserving ( (Figure) 5
We now show that all the maps in the skeleton-preserving class have the following desirable property:
Theorem 13. Let f be Sheletton-preservee lifting map. Then CWL(f) (i.e. CWL using lifting f) is least as powerful as WL in distinguishing non-isomorphic graphs.
Figure 5: A graph, its clique com- plex and the graph with duplicated edges. The first map is skeleton- preserving. while the second not.
To prove that some of these make CWL strictly more powerful than WI., is sufficient to find a pair of graphs that cannot be distinguished by WI., but can be distinguished by CWL. The following result gives examples of such maps.
Definition 14. Let k-CL, k-IC, k-C be the lifting maps attaching cells to all the cliques, induced cycles and simple cycles, respectively, of size at most Corollary 15. For all l 2 3. CWL(k-CL), CWL(k-IC) and CWL(k-C) are strictly more powerful than WL.
We note that this not a complete list. For instance, the result can also be extended to combinations of the above or other transformations. We can also relate CWL to the higher-order 3-WL test.
Theorem 16. There exists pair of graphs indistinguishable by 3- WL but distinguishable by CWL(k- CL) with k 2 4. CWL(k-IC) with 2 and CWL(K-C) with k 2 8.
Finally, we conclude this section by showing how CWL can achieve a superior expressive power compared to SWL. This result is proven by Corollary 31 in the Appendix.
Theorem 17. Let k-CL U k-1C and k-CL U k-C denote combined liftings attaching cells to the union of the specified substructures. CWL(kg-CI, U Ic) and CWL(ks-CLL J l2--C) are strictly more powerful than SWL(ks-CCL -CL) all 22 2 5.
Molecular Message Passing with CW Networks
We now describe CW Networks with an applied focus on molecular graphs to ground the discussion. Therefore, from now on we assume the use of the skeleton skeleton-preesrrving preserving lifting transformation that attaches 2-cells to all the induced cycles (i.e. chordless cycles) in the graph as in Figure 2 This leads to a message passing procedure involving atoms (vertices O-cells), the bonds between atoms (edges/ / 1-cells) and chemical rings (induced cycles / 2-cells). Additionally, in virtue of Theorem we consider only the boundary and upper adjacencies between these cells without sacrificing the expressive power. The equations for the other adjacencies, which we do not use, can be found in Appendix A We note however, that the theoretical results in this section are general and not particular to these specific choices of adjacencies and lifting transformation.
5

---

Molecular Message Passing
The cells in our CW Network receive two types of messages;
+++ g (a) = EB))) (Mx (K/ (t))
m +++ (a) AGGG,EN((o),,cioonn My (Mi My (G.))) n&)).
The first specifies messages from atoms to bonds and from bonds to rings. The second type of message, specifies messages between atoms connected by bond and messages between bonds that are part of the same ring (Figure 6). Note that for the second type of adjacency, when two atoms communicate, we include the features of the bond between them. Similarly, when two bonds communicate, we include the features of the ring they communicate through. The update operation takes into account these two types of incoming messages and updates the features of the cells:
hith = U (N's migo) m (o)).
To obtain a global embedding for a cell complex X from a model with L layers, the readout function takes as input the separate multi-sets of features corresponding to the atoms, bonds and the rings:
hx READOUTU (hh d0 (h B ddm(())= Thy dx)
Expressivity Naturally, the ability of CWNs to distinguish non -on-isomorphic regular cell complexes is bounded by CWL. Similarly to GNNs and WL, CWNs can also be shown to be as powerful as CWL as long as they are equipped with sufficient number of layers and the parametric local aggre- gators they use can learn to be injective. Multiple such multi-set aggregators are known to exist and can be directly employed in our model.
20 1
Theorem 18. CW Networks are at most as powerful CWL. Additionally, when using injective neighbourhood aggregators and a sufficient number of layers, CWNs are as powerful as CWL.
Corollary 15 states that CWL is strictly more powerful than the standard WL when the lifting procedure attaches 2-cells to induced cycles of size k 2 3. As a consequence of Theorem 18 this result also holds for molecular message passing CWNs equipped with injective aggregators. In practice, k is to be considered as a standard hyperparameter, and its choice can either be driven by validation set performance, or by domain knowledge (if available).
T
Figure 6: Hierarchi- cal depiction of the message passing pro- cedure. Orange ar- rows indicate bound- ary messages received by cells o and while blue ones show upper messages received by cells r and 8.
Symmetries Given graph G with adjacency matrix A and feature ma- trix X, function ff is (node) permutation equivariant if Pf(A, X) = (PAAP PX), for any permutation matrix P. GNN layers respect this equation, which ensures they compute the same functions up to permutation (i.e. relabeling) of the nodes. Similarly, it can be shown that CW Networks are equivariant with respect to permutations of the cells and corresponding permutations of the boundary relations o < T between cells. We define this notion of cquivariance more formally in Appendix C
Theorem 19. CW Network layers are cell permutatiio equivariant.
Rang-Range Interactions Several graph-related tasks require the ability to capture long-range interactions between nodes. For instance, certain molecular properties depend on atoms placed on the opposite sides of ring 31 60 As a consequence of the coupling between the input and computa- tional graphs, L message passing operations are necessary in GNNs let a node receive information from an L-hops distant node. In contrast, our hierarchical message passing scheme requires at most L layers since 2-cells create shortcuts. For example, a constant number of CWN layers (3) is enough to capture dependencies between atoms on the opposite sides of ring, independently of the ring size. In Section 5. we verify this a controlled scenario. Additional experiments on real world graphs in Section
5.2 5.2mm confirm that it can achieve state-of-the-art performance with a limited number of layers.
Due to the lack of a canonical ordering between neighbours, many common GNNs use symmetric convolutional kernels, resulting in isotropic filters treating neighbours equally. Recent works have proposed to address this limitation by employing additional structural informa- CWNs also implicitly achieve this form of anisotropy by integrating information from
Anisotropic Filters
tion 6 [0].

---

(944)
1.0
10-
10
220 SUmERR
10-
0.4
12
10
0.5
20
seios a)))
spcre A.A
GALREL 2-14
Ring size
tt sy
(a) Transferrrer Results, Accuracy is over hal- anced classes. A score of 0.2 is equivalent to a random guess. Error bars show the min and max. Our model obtains high-scores in average even for large rings despite using only three layers.
Family
(b) Failure rates the SR isomorphism task, the smaller the better (mean and std-error over 5 runs). In parantheses, for each model, the maximum size ls of rings lifted to 2-cells.
Figure Results on the Ring Transfer and SR synthetic benchmarks.
the higher-order cells and their associated substructures into the message passing procedure. For instance, bond features can learn to encode their membership to ring and also communicate directly with other bonds present in the ring. Consequently, the messages between atoms connected through these bonds are modulated by the presence of the ring as well by the presence of other nodes and bonds part of that ring.
CWNs as Generalised Convolutions Our message passing scheme can be seen a (non-linear)
generalisation of linear diffusion operators cell complexes. Recent works [R] 25 have introduced convolutional operators on SCs by employing the Hodge Laplacian [63] a generalisation of the graph Laplacian. By leveraging to cell complexes to define cellular convolutional operators. In Appendix D we discuss this approach and show that our cellular message passing scheme subsumes it. This represents a promising avenue for studying CWNs from a spectral perspective, an endeavour we leave for future work.
the cellular Sheaf Laplacian 36). similar construction can be extended
Computational Complexity When considering cells of a constant maximum dimension and bound- ary size, the computational complexity of the message passing scheme is linear in the size of the input complex. For the molecular applications we are interested in, the average number of rings per molecule is upper bounded by small constant (e.g. three for MOLHIV), so the size of the complex is approximately the same as the size of the graph. Therefore, in this setting, the computational complexity of the model is similar to that of message passing GNNs. Separately of this, the one one-time preprocessing step of computing the lifting of the graphs should also be considered. The C' induced cycles in a graph can be listed in O E + |V[C') polylog [V]) time (26. Again, given that C' is upper bounded by a small constant for the molecular datasets of interest in this work, the complexity of the lifting procedure also almost linear in the size of the graph. A more detailed analysis backed
up by wall-clock time experiments is given in Appendix B
5 Experiments
In this section we validate the theoretical and empirical properties of our proposed message passing scheme in controlled scenarios as well as in real-world graph classification problems, with a focus on large scale molecular benchmarks. For simplicity. in all experiments we employ model which stacks CWN layers with local aggregators as GIN 744
We name our architecture "Cell Isomorphism Network" (CIN). O-cells are always endowed with the original node features; higher-dimensional cells are populated in a benchmark specific manner. See Appendix I for details on feature initialisation, message passing and readout operations, hyperparameters, implementation and benchmark statistics.
7

---

5.1
Synthetic Benchmarks
CSL
Circular Skip Link dataset was first introduced in [77 and has been recently adopted as a reference benchmark to test the expressivity of GNNs 124 It consists of 150 4-regular graphs from 10 different isomorphism classes, which we need to predict. Unsolvable by the WL test and message passing approaches
[4 57
we use it to validate the expressive power of CWNs.
Table I: Classification accuracy on CSL.
We follow the same evaluation setting as Dwivedi et al. 22]: 5-fold cross validation procedure and 20 different random weight initialisations. For our model, we set
Method
Mean
Min
Max
the maximum ring size k- = 8. In Table I we follow the common practice on this dataset and report the mean, minimum and maximum test accuracy obtained by CIN over the 100 runs, along with the results by the baselines MP-GNNs, that is classic message passing GNNs (GAT (69]. MoNet [54]. GIN [74], etc.), and RingGNN [[4] perform as random guessers. In contrast, our model is able identify the isomorphism class of each test graph in every run while featuring only fraction of the computational complexity of 3WLGNN, the best performing reference baseline 24 53
MP-GNNs 10.000=00.000
10.000
10.000
RingGNNN 10.00=00.000
10.000
10.000
3WLGNN 97.800+10.916
30.000
100.000
CIN (Ours)
100.000+0.000
100.000
100,000
presented in Dwivedì et al. 24
SR Similarly to Bodnar et al. g and [10, we consider Strongly Regular graphs within the same family as hard examples of non-isomorphic graphs we seek to distinguish. Any pair of graphs within the same family cannot provably be distinguished by 3-WL test 8 IT]. We reproduce the same experimental setting of Bodnar et al. [8]. In particular, we consider 9 distinct SR familie<sandd and run our model untrained on the cell complex lifting of each graph, with & 4, 5, 6. O-cells (nodes) are initialised with a constant unitary signal, while 1- and 2-cells are initialised with the sum of the contained O-cells. We additionally run an MLP baseline with sum readout to appreciate the contribution of message passing, We report the percentage of non non-distinguished pairs Figure 7b Contrary to 3-WL, both CIN and the MLP baseline are able to distinguish many pairs across all families, with better performance attained for larger For k = 6, we observed CIN disambiguate all pairs in all families (0.0% failure rate). Despite the strong results achieved by the baseline, we found CIN always distinguish a larger number of -oniooomo pairs for the same values of kt this confirming the importance of cellular message passing.
Ring TingTransfer In order to empirically validate the ability of CIN to capture long-range node dependencies, we additionally design third synthetic benchmark dubbed as 'RingTraasfer'. Graphs in this dataset are chordless cycles (rings) of size k. In each graph we mark two special nodes as target and source, always placed at distance 1 J. The task is for target to output the one-hot encoded label assigned to source. All other nodes the ring are assigned unitary constant feature vector. A model has to learn to transfer the information contained in source to the opposite side of the ring, where target resides. We initialise 1- and 2-dimensional cells with null signal. In Figure 7a we show the performance of a 3-layer CIN as a function of the ring size k. along with that of GIN ! baselines equipped with ] stacked layers. We observe that our model learns to solve the task with only 3 computational steps, independent of k. As for GIN, we observed degradation in the performance for & > 24, up to complete failure. We hypothesise this to be due to the difficulties of training such a deep GNN (2 12 layers). We further verify the (theoretically expected) failure of GIN (not included) when endowed with less than layers.
5.2 Real-World Graph Benchmarks
TUD We test our model on 8 TUDataset benchmarks [66] with small and medium sizes from biology (PROTEINS y (2)). chemistry (i.e. molecules MUTAG A5 [1]. PTC. NCI and NC1109 70)) social networks (LMDB-B, IMDB-M, RDT-B). We consider induced cycle of size up to k = 6 for our graph lifting procedure. We initialise node (and (-cell) features as described and higher dimensional cells by averaging or summing the features of the included O-cells. The training setting and evaluation procedure follow those in Xu et al. [74]. We report the results in Table CIN compares more than favourably with the baselines. displaying strong empirical performance on all benchmarks. The mean accuracy of CIN ranks top on four out of eight datasets.
in Xu et al.
è Data available at: http::/users... cecs. anu, edu, au/"bdm/data. http///dtaaaggppppaaee graphs.htm html
8

---

Table TUDatasets. The first section of the table includes the accuracy graph kemnel methods, while the second includes GNNs. The top three are highlighted by First, Second, Third.
Datasel
MUTAG
PTC
PROTHINS
NCI1
NC1109
IMDB-B
IMDB-M
RITEB
RWK
20
79.2+22.1
55.9
59.6:0.11
>3 days
N/A
N/A
N/A
N/A
(A
81.411.7
55.7=0.5
71.44031
62.5=0.3
62.440.3
N/A
N/A
58
76.0+22.7
59.5+2,4
73.7+10.7
82.5=0.5
N/A
NIA
N/A
N/A
WL kemeel
65
90.4++5.7
$9.9+4.3
75.0++3.1
86.0=1.8
N/A
73,8+3.9
50.9+3.8
81.0+311
DCNN 8
N/A
N/A
61.3:t1.6
56.6=100
N/A
49.1+14
33.5::14
N/
DGCNN 16
85.8
58.622.55
75,5+0099
74,4=0.5
N/A
70.0=0.9
47.810099
N/A
IGN 52
83,9+13.0
58.5+6.9
76.6+
74.3=2.7
72.8+1.5
72.0+55.5
48.74:3.4
N/A
GIN 72
89.4::5566
64.6=7.0
76.2+42.8
82.7=1.7
N/A
75.1+:5.1
52.342.88
92,44.5
PPGNs 633
90.622..7
66.2-6.6
77.2414.7
83.2=111
82.21:14
73.0=5.8
50.513.6
N/A
Natural GN
21
89,4:11.6
66.8=1.77
71.7:t1.0
824=1.3
NIA
73.5+20
51.31155
N/A
GSN 10
92.2 + 7.5
68.2 7.2
76.6 +: 5.0
83.5
N/A
77.8 3.3
3.3
N/A
SIN 8
NIA
N/A
76.4 3.3
82.7 2.1
NIA
75.6
5..4
92.2 1.0
CIN (Ours)
92.7 + 6.1
68.2 5.6
77.0
83.6
84.0 1.6
7..6
52.7
92.
Table 3: ZINC (MAE), ZINC-FULL (MAE) and Mol-HIV (ROC-AUC).
ZINC +
ZINC-FULL
MOLHIV
Method
No Edge Feat.
With Edge Feat.
All methods
All methods
GCN 47
0,469=0.002
N/A
N/A
76.06=
GAT 69
0,463+00002
N/A
N/A
N/A
GatedGCN
0.422-0.000
0.363+0.009
N/A
N/A
GIN 14
0.408=0.000
0.252-10.01 0014
0.088:10.002
77.07:11.49
PNA 20
0.320=0.032
0.188 004
N/A
79.05
DGN
5
0.219=0.010
0.168=0.003
N/A
79.70=0099
HIMP 2r
N/A
0.151
0.036:10.002 N/A
08.80
GSN
10
0.139=0.007
0.10810.018
77.99
CIN-small (Ours)
0.139
0.09410.004
0.044
$0.55+1.04
CIN (Ours)
0.005
0.079-10.06
0.022:10.002
80,94-10.57
On the remaining datasets, CIN achieves the second place. We observe that the best results are on datasets from the biological and chemical domains, where rings play relevant role.
ZINC
We study the effectiveness of cellular message passing on larger scale molecular benchmarks from the ZINC database [o ZINC (12k graphs) and ZINC-FULL (250k graphs) ?
B3
43
75
are two graph regression task datasets for drug constrained solubility prediction. In these experiments, consider rings up size k 18. We follow the training and evaluation procedures in 24 Our experiments encompass different scenarios, examine the impact of ablating edge features and of constraining the parameter budget of the architecture to 100k. All results are illustrated in Table 3 where we also include the results for ZINC-FULL obtained by the same exact architectures. Our model exhibits particularly strong performance on these benchmarks: it attains state-of-the-ang results on both the two dataset variants, outperforming other models by significant margin. CIN attains strong results even when constrained by the parameter budget. still achieves oate-of-the-an performance on ZINC and is on-par with the best unconstrained baseline under edge-feature ablation.
We additionally our model on the molecular ogbg-molhiy dataset from the Open Graph Benchmark A0 (41k graphs). The task is to predict the capacity of compounds to inhibit HIV replication. Rings of size up reference and replicate the same hyperparameter setting in our model, including the use of only 2 message passing layers. We report the mean test ROC-AUC metrics the epoch of best validation performance for 10 random weight initialisations. Similarly to ZINC, we experiment with "small" model whose number parameters constrained in the order of 100k. Table displays the results. CIN significantly outperforms other strong GNN baselines, even when constrained by the parameter budget. Consistently with 277, we observe that only two layers are sufficient when performing hierarchical message passing across meso-scale structures such as rings.
Mol-HIV
are considered as 2-cells. We take the architecture in 127 as

---

Related Work, Discussion and Conclusion
Recent works have proposed the generalisation of GNNs to simplicial All these simplicial methods are subsumed by the model in Bodnar et al. M which CWNs in turn subsume. To the best of our knowledge, Hajij et al. [4 is the only other example of message passing on cell complexes, but this work does not study the expressive power of the proposed scheme, neither it experimentally validates its performance. In contrast, our work comprehensively characterises the expressiveness of cellular message passing, and introduces a theoretically grounded and empirically effective framework to apply it on graph structured data in way to address several limitations of standard Graph Neural Networks.
Cell complex models
complexes B
25
32 351
Molecular substructures A few other works have extended GNNs to account for molecular substructures. Junction Trees (JT), which conveniently represent singletons, bonds and rings as supernodes in tree, have been used in molecular graph generation 45 14
JTs are also used in the recent work of Fey et al. 27 who employs them design hierarchical message passing scheme based on the tree structure. However, this hierarchy has a different configuration than the one cell complexes provide. Information about eycles also used in GSNs [00] to augment the node features, but the model retains the usual message passing procedure of GNNs. These last two models are of particular relevance to the present work, since they utilise information about chemical rings. is important to remark that CWNs compare favourably with both of them in all our benchmarks.
Higher-order GNNs A related line of work has studied lifting graphs into k-dimensional tensor representations that can be processed by provably expressive k-GNNs 4 522 [3] With higher values of k, these models achieve higher-expressivity but due the computational complexity this incurs, values of k 2 3 are of little use in practice. Therefore, unlike CWNs, these models cannot explicitly represent in practice chemical rings of common sizes (e.g. five or six). Furthermore, by being upper- bounded by 3- 3-WL, the 2-GNN models cannot count the number of induced cycles of size greater than four (see Appendix A for details). In contrast, CWNs can easily count these important chemical substructures through the readout operation it performs on the 2-cells.
Limitations The main limitations of the model are of computational nature. While the compu- tational complexity of the message passing procedure and its preprocessing step is suitable for molecular and geometric graphs, the number of rings (and more generally simple cycles) in general graphs can be exponential in the number of nodes. In that case, one has to resort to smaller 2-cells like triangles, which can be found efficiently in general graphs. Moreover, one has to typically use weights specific for each dimension of the cell complex, increasing the number of parameters compared to GNNs. However, we have shown that our model can compensate this increase with reduced number of layers and still achieve state-of satie--f-th-aaa results on some of the molecular benchmarks.
From theoretical point of view, this work is concerned only with regular cell complexes. Adopting this restriction is useful from multiple perspectives: regular cell complexes are easier to analyse, their combinatorial structure completely describes their topology and convolutions can be defined them through the Sheaf Laplacian (see Appendix
D). Nonetheless, some of our theoretical results could be extended to non-regular complexes, which could be obtained by lifting transformations not studied in this work, such as attaching 2-cells to paths in the graph. We leave addressing non-regular complexes and their trade-offs to future developments of this work.
Societal Impacts Most of our paper is theoretical in nature and we do not see immediate direct negative societal impacts. Within the scope of social network applications, sufficient evidence of performance improvement on related benchmarks to justify obvious adoption in such domain. In contrast, the empirical performance molecular benchmarks suggests it may have a positive impact on applications of immediate interest in pharmaceutics, such as drug discovery B0)
do not yet have
Conclusion We have proposed a provably powerful message passing procedure on cell complexes motivated by a novel colour refinement algorithm to test their isomorphism. This allows us to consider flexible lifting operations graphs to implement more expressive architectures which benefit from decoupling the computational and input graphs. Our methods show excellent performance on diverse synthetic and real-world molecular benchmarks.
10

---

Funding and Acknowledgements
YW and GM acknowledge support from the ERC under the EU's Horizon 2020 programme (grant agreement n' 757983). MB is supported in part by ERC Consolidator grant n" 724228 (LEMAN). The authors declare no competing interests. We are also grateful Ben Day, Gabriele Corso and Nikola Simidjievski for their helpful feedback. We would also like to thank Vijay P. Dwivedi and Chaitanya K. Joshi for clarifying certain aspects their Benchmarking GNNs [ work, and to Muhammet Balcilar for signalling a numerical precision issue in early SR graphs experiments.
References
[1] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. ICLR, 2021.
[2] V. Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On weisfeiler- leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sciences, 11::42-59, 2020. ISSN 0022-0000.
[3] James Atwood and Don Towsley. Diffusion-coonvlutiinal neural networks. In NIPS, pages 1993-2001, 2016.
[4] Waiss Azizian and Mare Lelarge. Expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations, 2021. URL https: /oopenreview aegpenreieee.ntttftuurraaaaaaaee wet.://rormmtaaxxxlgggya.aaa..aa
[5] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization. arXiv preprint arXiv: 160.044607.0 2016.
[6] Dominique Beaini, Saro Passaro, Vincent Létourneau, William L Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. ICML, 2021.
[7] Etienne E. Birmelé, Rui Ferreira, Roberto Grossi, Andrea Marino, Nadia Pisanti, Romeo Rizzi, and Gustavo Sacomoto. Optimal Listing of Cycles and st-Paths in Undirected Graphs. In 24th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, United States, January 2013.
[8] Cristian Bodnar, Fabrizio Frasca, Yu Guang Wang, Nina Otter, Guido Montúfar, Pietro Lio, and Michael Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. ICML, 2021.
[9] Karsten M. Borgwardt, Cheng Soon Ong, Stefan Schönauer, S. V. N. Vishwanathan, Alex J. Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 2005.
[10] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. arXiv:2006.09252. 2020.
[11] Xavier Bresson and Thomas Laurent. arX1v:171100753,, 2017.
Residual gated graph convnets. arXiv preprint
[12] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34 (4):18-42, 2017. 2017.
[13] Eric Bunch, Qian You, Glenn Fung, and Vikas Singh. Simplicial 2-complex convolutional neural networks. In NewrIPS Workshop on Topological Data Analysis and Beyond, 2020.
[14] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In NeurlPS, volume 32, 2019.
[15] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? In NeurlPS, 2020.

---

[16] N. Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM J. Comput., 14:210-223, 1985.
[17] Fan Chung. Spectral graph theory. American Mathematical Society, 1997.
[18] Djork-Amé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (ELUss. In ICLR, 2016.
[19] Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26( (1)): 2004.
[20] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. In NeurlPS, volume 33, pages 13260-13271, 2020.
[21] Pim de Haan, Taco Cohen, and Max Welling. Natural graph networks. In NewrIPS, 2020.
[22] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, 2016.
[23] Paul Dobson and Andrew J Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of Molecular Biology, 330(4):771-783, 2003.
[24] Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982 2020.
[25] Stefania Ebli, Michaël Defferrard, and Gard Spreemann. Simplicial neural networks. In NeurIPS Workshop on Topological Data Analysis and Beyond, 2020.
[26] Rui Ferreira, Roberto Grossi, Romeo Rizzi, Gustavo Sacomoto, and Marie-France Sagot. Amortized Õ(IVI) Delay Algorithm for Listing Chordless Cycles in Undirected Graphs. In 22th Annual European Symposium Algorithms, volume 8737 of Algorithms ESA 2014, Lecture Notes in Computer Science, pages 4 418-429, Wroclaw, Poland, September 2014.
[27] M. Fey, J. G. Yuen, and F. Weichert. Hierarchical inter-message passing for learning on molecular graphs. In ICML Graph Representation Learning and Beyond (GRL+) Workhop, 2020.
[28] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with Py Geometric. In ICLR Workshop on Representation Learning Gruphs and Manifolds, 2019.
[29] Thomas Gärtner, Peter Flach, and Stefan Wrobel. On graph kernels: Hardness results and efficient alternatives. In Learning theory and kernel machines, pages 149. Springer, 2003.
[30] Thomas Gaudelet, Ben Day, Arian R Jamasb, Jyothish Soman, Cristian Regep, Gertrude Liu, Jeremy B R Hayter, Richard Vickers, Charles Roberts, Jian Tang, David Roblin, Tom I. Blundell, Michael M Bronstein, and Jake P Tayg.r-King. Utilizing graph machine learning within drug discovery and development. Briefings in Bioinformatics, 05 2021. ISSN 1477-4054.
[31] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In ICMI., 2017.
[32] Nicholas Glaze, T. Mitchell Roddenberry, and Santiago Segarra. Principled simplicial neural networks for trajectory prediction. In ICML, 2021.
[33] Rafael Gómez-Bombarell Jennifer N Wei, David Duvenaud, José Miguel Hernández-Lobato. Benjamín Sánchez-Lengelingg Dennis Sheberla, Jorge Aguilera- paallera-lparrguirree, Timothy D Hirzel, Ryan Adams, and Alán Aspuru- Guzik. Automatic chemical design using a data-driven continuous representation of molecules. ACS Central Science, 4(2):268-22) 2768, 2018.
[34] Mustafa Hajij, Kyle Istvan, and Ghada Zamzmi. Cell complex neural networks. In NeurlPS Workshop on Topological Data Analysis and Beyond, 2020.
[35] Mustafa Hajij, Ghada Zamzmi, and Xuanting Cai. Simplicial complex representation learning. arXiv preprint arXiv:2103.0 040460 2021.
12

---

[36] J. Hansen and R. Ghrist. Toward spectral theory of cellular sheaves. Journal of Applied and Computational Topology, 3:315-358, 2019.
[37] Jakob Hansen and Thomas Gebhart. Sheaf neural networks. In NeurIPS 2020 Workshop on Topological Data Analysis and Beyond, 2020.
[38] Allen Hatcher. Algebraic topology. Cambridge Univ. Press, Cambridge, 2000.
[39] Christoph Helma, Ross D. King, Stefan Kramer, and Ashwin Srinivasan. The predictive toxicology challenge 2000-2001. Bioinformatics, 17(1):107-108, 2001.
[40] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In NeurlPS, 2020.
[41] Weihua Hu* Bowen Liu", Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-tree tre-training graph neural networks. In International Conference on Leurning Representations, 2020.
[42] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. ICML, 2015.
[43] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In ICML, pages 2323 2323-2332, 2018.
[44] Wengong Jin, Kevin Yang, Regina Barzilay, and Tommi Jaakkola. Learning multimodal graph-to-graph translation for molecular optimization. In ICLR, 2019.
[45] Jeroen Kazius, Ross McGuire, and Roberta Bursi. Derivation and validation of toxicophores for mutagenicity prediction. Journal of Medicinal Chemistry, 48(1):312-33) 2005.
[46] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ICLR, 2015.
[47] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ICLR, 2017.
[48] Nils Kriege and Petra Mutzel. Subgraph matching kernels for attributed graphs. arXiv preprint arXiv:1206.6465 2012.
[49] Casimir Kuratowski. Sur le probleme des courbes gauches en topologie. Fundamenta mathe- maticae, 15(1):27--283, 1930.
[50] Greg Landrum. RDKit: Open-source cheminformatics software. 2016.
[51] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. AAAI, volume 32, 2018.
[52] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In ICLR, 2018.
[53] Haggai Maron, Heli Ham-H Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In NeurlPS, 2019.
[54] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model CNNs. In CVPR, pages 5425-5434, 2017.
[55] 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, 2019.
[56] Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataset: A collection of benchmark datasets for learning with graphs ICML. Graph Representation Learning and Beyond (GRL+) Workhop, 2020.
13

---

[57] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. ICML, volume 97, pages 4663 4673, 2019.
[58] Marion Neumann, Roman Garnett, Christian Bauckhage, and Kristian Kersting. Propagation kernels: efficient graph kernels from propagated information. Machine Learning, 102(2): 209- 019-2455220 2016.
[59] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury. Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, high-performance deep learning library. In NeurlPS, pages 8024-8035. 2019.
[60] Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific Data, 1(1):1-7, 2014.
[61] Kaspar Riesen and Horst Bunke. Iam graph database repository for graph based pattern recognition and machine learning. In Joint IAPR International Workshops on Statistical Techniques in Pattem Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), pages 287-297. Springer, 2008
[62] Ryoma Sato. A survey on the expressive power of graph neural networks. arXiv preprint arXiv:2003.0444 040078 2020.
[63] Michael T Schaub, Austin Benson, Paul Horn, Gabor Lippner, and Ali Jadbabaie. Random walks on simplicial complexes and the normalized Hodge 1 I-Laplacian. SIAM Review, 62(2): 353-391, 2020.
[64] Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In AISTAT, pages 488-495, 2009.
[65] Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. JMLR, 12(Sep):2539-2561 2011.
[66] Howard E. Simmons and John E. Maggio. Synthesis of the first topologically non-planar molecule. Tetrahedron Letters, 22(4):287-25) 1981. ISSN 0040-4039.
[67] Amit Singer and Hau-Tieng Wu. Vector diffusion maps and the connection laplacian. Commu- nications in Pure and Applied Mathematics, 68(8), 2012.
[68] Teague Sterling and John J. Irwin. ZINC 15 ligand discovery for everyone. Journall of Chemical Information and Modeling, 55(11))2324-2333 11 2015, doi: 10. 10010221accscccmm500555599 URL https://doi. http///o..or/////// 1021 acs jcim.5b00599
[69] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
[70] Nikil Wale, Ian A Watson, and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14(3):3473775, 2008.
[71] Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. NTI Series, 12-):12-16, 1968.
[72] J. H. C. Whitehead. Combinatorial homotopy. I. Bulletin of the American Mathematical Society, 55(3.P1):213 245, 1949. doi: bams/1 183513543.
[73] Keyulu Xu. Chengtao Li, Yonglong Tian, Tomohiro Sonobe. Ken ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, 2018
[74] Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
14

---

[75] Jiaxuan You. Bowen Liu, Rex Ying, Vijay Pande, and Jure Leskovec. Graph convolutional policy network for coal-directed molecular graph generation. NeurIPS, 2018.
[76] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAI, 2018.
15

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section i
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We provided
link to our code in the paper.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Details are provided Section 5 and Appendix E
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section and Appendix
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] We used multiple existing datasets described and referenced in Section S
(b) Did you mention the license of the assets? [Yes] See Appendix
(c) Did you include any assets either in the supplemental material URL? [Yes] We included a link to our code.
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [N/A] We are only using publicly available datasets.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A] None of the datasets we are using contain personally identifiable information or offensive content.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
16


Reviews:
[{"review_id": "fzT6BGmqIk3", "reviewer": "Reviewer_23iC", "summary": "The paper focuses on generalizing graph neural networks to model higher-order structures. It proposes a new message passing scheme operating on regular cell complexes. The induced models, called CW Networks, generalize and subsume the message passing simplicial networks (MPSNs) which operate on simplicial complexes, and are proved more powerful than the WL test and in some cases not less powerful than the 3-WL test. \n\n\n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written. It makes a comprehensive theoretic analysis of the proposed model as well as a thorough empirical study. The concept of using cell complexes seems to be a natural but novel extension of simplicial complexes and has some intuitive advantages on molecular datasets (with a lot of rings). The experimental results are also quite good compared to other recent models. I think it is already in good shape and ready for publication. \n\nAs to the negative points, the authors actually already indicated the limitation of the method in the paper, i.e. the high computational complexity on more general large graphs, which would impede the applicability of the model. \n\nAnother minor problem may be the experiments of long-range interaction. The synthetic data only contains chordless rings and it seems all nodes are in the same rings. That may be not a general case, or we can say it just covers one case of long-range interactions. To make the experiments more convincing, maybe in addition to the central rings there should also be some associated branches? \n\nI have also another question for the authors: if we pre-process the graphs to decompose them into nodes, edges, rings, and use these elements as nodes to form one heterogenous graph, would a GNN on that graph be equal to the cellular message passing to some extent?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No major negative social impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "MEOVmyIemz", "reviewer": "Reviewer_rLZj", "summary": "This paper presents an extension of the message passing simplicial network based introduced in [4] on cell complex. The authors first introduce background on regular cell complex. They present an extension of the Weisfeiler Lehman test that generalises the simplicial WL from [4] to Cellular WL and give theoretical results about the power of this new test. Then they introduce CW Networks which is a natural extension of message passing GNN to message passing on cells and show that their architecture is permutation equivariant. Finally, they show on synthetic benchmarks and real-world graphs that their architecture achieves better performances.", "questions": "", "limitations": "", "rating": 4, "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": "1- The idea of lifting graphs to higher order representation is interesting but not new and the authors should clarify it: [34] already showed that the expressive power is increased when dealing with high-order tensor representations of the graphs with linear layers. \n\n2- Since Cellular WL add a lot of information, Theorem 13 is not really surprising. Indeed, the analysis made in Section 3 is rather misleading. The interest of the various WL tests is to show the trade-off between the complexity of the algorithm and its expressive power. 1-WL is less complex than 3-WL and so on but you gain in term of expressiveness.  This is the main motivation for comparing the expressive power of a GNN with the k-WL test. See [34], or Waiss Azizian, Marc Lelarge. Expressive Power of Invariant and Equivariant Graph Neural Networks, ICLR 2021, for a general overview about GNN and WL tests. In Section 3, the authors completely ignore the complexity part. For example, if I understand correctly, the clique complex lifting will include the information about all cliques in the graph which might be very costly to compute, hence Corollary 14 is just telling that if you have access to this information you can do better than a very simple algorithm. It is clearly true but not very interesting.\n\n3- The authors mention the complexity of their GNN on page 6 and write that under some conditions the complexity is \"linear in the size of the input complex\". But how big can this size of the input complex be in term of the size of the graph?\n\n4- In their Theorem 17, the authors show that CW Network layers are cell permutation invariant. Does it imply that the GNN is graph permutation invariant?\n\n5- It seems that the authors only look at graph embedding with their CWN. Is it possible to obtain node embedding by modifying the READOUT function?\n\n6- In the experiment section, it would have been nice to compare CIN with other algorithms having access to the same information as CIN. Since, the authors compute all the rings in the graph for their CIN, how is the perfomance of a standard GNN improved if we add the statistics of the rings in addition to the embedding computed by the GNN? Such result would allow to demonstrate whether the improvement seen in the paper is due to the new architecture or to the new features added. Similarly, you can probably increase the performance of the WL kernel by adding this new feature to get very good results.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "OK", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "BKSOJ5Q83L4", "reviewer": "Reviewer_hkAr", "summary": "Recently, there have been several attempts to put higher-order structures on graphs and perform message passing over these structures. One example is the Message Passing Simplicial Networks proposed in e.g, ref[4]. The present paper extends the higher-order structures from simplicial complexes (SCs) to regular cell complexes (also known as CW complexes), or more precisely, generalizes the Simplicial WL of ref[4] to a Cellular WL (CWL). Both theoretical understanding, and experimental studies of CWL are presented. Specific contributions include: \n\n(1) To obtain a CW complex from a graph, the paper introduces a ``cellular lifting map\", and shows a skeleton-preserving lifting map gives rise to a CWL that is at least as powerful as standard WL (Weisfeiler-Lehman) in graph isomorphism testing. It also gives examples of specific natural lifting maps (which includes the previous SWL in [4] as a special case) that is at least as powerful as the so-called 3-WL. \n\n(2) It describes and implements a CW network using a lifting map that attaches 2-cells to all induced cycles in the input graphs. This architecture (CWN) makes sense especially for molecular graphs applications (in capturing both the covalent bonds and chemical rings). \n\n(3) It presents various experimental results on synthetic and real datasets, which show that a specific instantiation of CWN, called CIN, can both differentiate certain hard cases for graph isomorphism testing (e.g, 4-regular graphs), comparable or better performance on TUDatasets, and better performance in molecular benchmark datasets. \n", "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": "I want to thank the authors for their responses to my questions in the review and during the discussion period. Please add a discussion/clarification of Theorem 15 as discussed. I maintain my score of the paper. \n\nSee the above for the summary of the paper and its contribution. \n\n** strength of the paper: \n(1) Graph neural networks (especially message passing graph networks) have received great attention in recent years. Recently there has been much interest in message passing over higher order structures, mostly to increase the expressiveness power of graph networks. Using CW complexes as in this paper is more flexible (e.g, filling induced cycles by 2-cells) than using simplicial complexes. The use of CWL is both natural and useful in practical applications. \n\n(2) The authors present several theoretical results on CWL and CWN. The formulation of lifting map is interesting. \n\n(3) Good empirical studies are presented, with both synthetic datasets to show the expressiveness and real benchmark datasets to see performance improvements. \n\n\n** weakness of the paper: \n(a) The development of CWL is a generalization of the simplicial version (SWL, ref[4]). Most of the theoretical results feel incremental compared to the work of ref[4]. (The notion of cellular lifting map is new but perhaps not surprising. I have read the supplement briefly as well, and understand that there are complications / technicality that need to be addressed due to the use of cells instead of simplices. The concept of cellular message passing also exists in ref[24].) If there are significant new ideas, it would be great if they can be articulated. \nFurthermore, just being more expressive than WL is not a very strong theoretical result, especially since CWL is using high-dimensional cells. \n\n(b) (A minor one:) I like the discussions and theoretical results on expressive power in distinguishing non-isomorphic graphs. There are other ways to increase expressive power, for example, by using more powerful initial node features (say sth. that captures cycle information) or by using node coloring (e.g, the following reference): \n      [Ref]: \"Coloring Graph Neural Networks for Node Disambiguation\",\n      George Dasoulas, Ludovic Dos Santos, Kevin Scaman, Aladin Virmaux, \n      IJCAI 2020. \nIt could be good to include a comparison with the approach in the above Ref. \n\n** overall evaluation: \nOverall, I think this is a solid paper that presented nice studies over a natural object with reasonably convincing experimental results (especially over molecular graphs). The originality is somewhat limited (e.g., when compared to work of Ref[4]). Nevertheless, it is well-written and I enjoyed reading it. \n\n** other comments:\n-- Maybe I missed it in the submission and supplement: how is the ring size $k$ chosen in experiments (especially for real datasets)? Different values of $k$ seem to be used for different applications. Is there a consistent strategy to choose it? \nThere is a range of hyperparameters listed in Table 8 in supplement. Why not having $k$ as another hyperparameter? Also, how does the number of hyperparameters compare to other standard approaches, say GIN? \n-- In Definition 1, is \"regularity\" important for the CW network? Is it needed for any of the results later? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequate", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "1dT9V8eOT3a", "reviewer": "Reviewer_1iwy", "summary": "In this work, the authors propose a new member of graph neural networks, called CWN, that considers the higher-order structure of graphs. The proposed model leverages the topological properties of cell complexes and establishes a novel hierarchical message passing procedure. The authors demonstrate that the proposed CWN is more powerful than the WL test and can be comparable to the 3-WL test. The proposed model achieves encouraging performance on graphs with complicated structures, e.g., molecules, while it requires a preprocessing step with the tolerable time cost.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I like this work because of its solid theoretical analysis, sufficient and convincing experimental results, and detailed supplementary materials. Additionally, in Section 4, the authors connect the proposed method with existing works and highlight its advantages, which further clarifies the contribution of this work to the community.\n\nI only have four suggestions:\n\n1. Line 121: \t“Simplicial WL” -> “Simplicial WL (SWL)”, such that SWL will be understandable.\n\n2. The GWL coloring procedure (the preprocessing step) shown in Figure 3 provides a hierarchical way to extract features from graphs. If my understanding is correct, we can define a graph kernel based on the features and provide a kind of high-order WL kernel accordingly. Could the authors take this potential kernel method as a baseline in the experiment?\n\n3. The introduction of CWN in Section 4 is too brief. It would be nice if the authors can illustrate the molecular message-passing model by a figure — after doing the coloring procedure, how to apply message passing to the coloring result? Maybe the authors can consider using a simple molecule as the graph in Figure 3 and adding a subfigure to it.\n\n4. Reading this paper is challenging for the readers without topological background. Section 2 is not a good starting point for such readers. Before showing Figure 1, it would be necessary to add a Figure to illustrate topological space X, its partitions, and cells, with sufficient symbols and notations, such that it will be much easier to understand the concepts in definition 1.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I did not find any obvious or potential negative societal impact of the proposed work.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new graph neural network framework allowing message passing for high-order structures. The paper provides clear theoretical foundation and also delivers convincing empirical evidence. Although it was mentioned that the contribution is a bit incremental over existing work [4,24], overall the paper was positively/passionately accepted. One reviewer did raise strong concern about the presentation of the paper. But based on the paper and all other reviewers' opinions, the presentation concern does not seem general. Therefore, the AC recommends the paper to be accepted.   
Decision: Accept (Poster)