On the Expressive Power of Geometric Graph Neural Networks
Authors: Chaitanya K. Joshi
Cristian Bodnar
Simon V Mathis
Taco Cohen
Pietro Lio
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph Neural Networks
Geometric Deep Learning
Equivariance
Expressive Power
Graph Isomorphism

Abstract: The expressive power of Graph Neural Networks (GNNs) has been studied extensively through the lens of the Weisfeiler-Leman (WL) graph isomorphism test. Yet, many graphs arising in real-world applications come embedded in Euclidean space with an additional notion of geometric isomorphism, which is not covered by the WL framework. In this work, we propose a geometric version of the WL test (GWL) for discriminating geometric graphs while respecting the underlying physical symmetries: permutation, rotation, reflection, and translation. We use GWL to characterise the expressive power of GNNs that are invariant or equivariant to physical symmetries by studying the classes of geometric graphs that can or cannot be distinguished by these architectures. This allows us to formalise the advantages equivariant GNN layers have over their invariant counterparts in the Geometric Deep Learning blueprint. Finally, we connect our discrimination-based perspective with the universal approximation properties of geometric GNNs and prove they are two sides of the same coin.

Under review as a conference paper at ICLR 2023
ON THE EXPRESSIVE POWER OF GEOMETRIC GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
The expressive power of Graph Neural Networks (GNNs) has been studied ex- tensively through the lens of the Weisfeiler-Lemat (WL) graph isomorphism test. Yet, many graphs in scientific and engineering applications come embedded in Eu- clidean space with an additional notion of geometric isomorphism, which not covered by the WL framework. In this work, we propose geometric version of the WL test (GWL) for discriminating geometric graphs while respecting the un- derlying physical symmetries: permutations, rotation, reflection, and translation. We use GWL to characterise the expressive power of GNNs that are invariant or equivariant to physical symmetries in terms of the classes of geometric graphs they can distinguish. This allows us to formalise the advantages of equivariant GNNs over invariant GNNs: equivariant layers have greater expressive power they en- able propagating geometric information beyond local neighbourhoods, while in- variant layers cannot distinguish graphs that are locally similar, highlighting their inability to compute global geometric quantities. Finally, we prove the equiva- lence between the universal approximation properties of geometric GNNs and our more granular discrimination-base perspective.
INTRODUCTION
Systems in biochemistry Jamasb et al. 2022). material science (Chanussot et al. 2021 , physical simulations "Sanchez-Gonzalez et al. (020)) and multiagent robotics (Li et al. 2020) contain both geometry and relational structure. Such systems can be modelled via geometric graphs embedded Euclidean space. For example, molecules are represented as a set nodes which contain infor- mation about each atom and its 3D spatial coordinates well as other geometric quantities such as velocity or acceleration. Notably, the geometric attributes transform along with Euclidean trans- formations of the system, i.e. they are equivariant to symmetry groups of rotations, reflections, and translation. Standard Graph Neural Networks (GNNs) which do not take spatial symmetries into account are ill-suited for geometric graphs, the geometrie attributes would no longer retain their physical meaning and transformation behaviour (Bogatskiy et al. 2022 Bronstein et al.) 2021
Addressed R1.2, R4.1
GNNs specialised for geometric graphs follow the message passing paradigm (Gilmer et al. 2017) where node features are updated in a permutation equivariant manner by aggregating features from local neighbourhoods. Crucially, in addition to permutations, the geometric attributes of the nodes transform along with Euclidean transformations of the system, i.e. they are equivariant to the Lie group of rotations (SO(d) or rotations and reflections (O(d). We use as a generic symbol for these Lie groups. We consider two classes of GNNs for geometric graphs: (1) G-equivariant mod- els, where the intermediate features and propagated messages are equivariant geometric quantities such as vectors or tensors (Thomas et al. 2018 Anderson et al.) 2019 Jing et al.] 2020 Satorras al., 2021 Brandstetter al., 2022); and (2) G-invariant models, which only propagate local invariant scalar features such distances and angles (Schütt et al., 2018 Xie & Grossman 2018 Gasteiger et al.) 2020). Despite promising empirical results for both classes of architectures, key the- oretical questions remain unanswered: (1) How to characterise the expressive power of geometric GNNs? And (2) what is the tradeoff between eqqiiaaaai and G--invariant GNNs?
Addresses R2.1
The graph isomorphism problem (Read & Corneil 1977) and the Weisfeiler-Leman (WL) WWii- feiler Leman 1968) test for distinguishing non non-isomorphic graphs have become a powerful tool for analysing the expressive power of non-geometric GNNs (Xu et al. 2019) Morris et al.. 2019

---

Under review as a conference paper at ICLR 2023
(2)
ll
(2)
f
= * 92
9
(1) Cb(5)
(2) 6
Figure 1: Geometric Weisfeiler-Leman Test. GWL distinguishes non-isomorphic geometric graphs G1 and G2 by injectively assigning colours distinct neighbourhood patterns, up to global symmetries (here 6 = Od)). Each iteration expands the neighbourhood from which geometric information can be gathered (shaded for node i). Example inspired by |Schüttt al, (202T).
The WL framework has been a major driver of progress in graph representation learning (Chen et al., 2019 Maron al. 2019 Dwivedi et al., 2020. Bodnar et al., 2021b a). However, the WL frame- work does not directly apply to geometric graphs as they exhibit stronger notion of isomorphism that also takes spatial symmetries into account.
Contributions. In this work, we study the expressive power of geometric GNNs from the perspec- tive of discriminating non-isomorphic geometric graphs:
In Section 3 we propose geometric version of the Weisfeiler-Leman graph isomorphism test, termed GWL. We use GWL to formally characterise classes of graphs that can and cannot be distinguished by Ø-invariant and G-equivariant GNNs. We show how invariant models have limited expressive power as they cannot distinguish graphs where one-hop local neighbourhoods are similar, while equivariant models distinguish larger class of graphs by propagating geometric vector quantities beyond local neighbourhoods:
In Dection[[ we study the design space of geometric GNNs using GWL, highlighting their theoretical limitations in terms of depth and body order, as well as discussing practical im- plications. We show that (S-invariant models cannot compute global geometric properties such as volume, area, centroid, etc. Synthetic experiments Appendix C supplement our theory and highlight practical challenges in building geometric GNNs.
Addresses R1.4, R2.5, R3.1, R4.1
In Section we follow folnow[Chen et al. (2019) and prove an equivalence between model's 's abil- ity discriminate geometric graphs and its ability to universally approximate @ (--invariant functions. While universality is binary, GWL's discrimination- based perspective provides a more granular and practically insightful lens to study geoemtric GNNs.
2 BACKGROUND
Graph Isomorphism and Weisfeiler-Leman. An attributed graph G = (A, with node set V of size n consists of an n X n adjacency matrix and matrix of scalar features S E Rax Two attributed graphs G, H are isomorphic if there exists an edge-preserving bijection b V(G) V(H) such that s (9) (H)
((3) where the subscripts index rows and columns in the corresponding matrices.
The Weisfeiler-Lemat test (WL) is an algorithm for testing whether two (attributed) graphs are (0)
isomorphic (Weisfeiler & Leman 1968). At iteration zero the algorithm assigns colour c; E C from a countable space of colours C to each node i. Nodes are coloured the same their features are the same, otherwise, they coloured differently. In subsequent iterations t, WL iteratively updates the node colouring by producing a new (0) C::
(t-1) c
Hcc (t-1) l Ije (jEND))
= HASH
(1)
2

---

Under review as a conference paper at ICLR 2023
where HASH is injective map (i.e. a perfect hash map) that assigns unique colour to each input and K-B denotes a multiset a set that allows for repeated elements. The test terminates when the partition of the nodes induced by the colours becomes stable. Given two graphs & and H. if there exists some iteration for which a | E V + Hee | v(H) B. then the graphs are not isomorphic. Otherwise, the WL test is inconclusive, and say it cannot distinguish the two graphs.
Group Theory. We assume basic familiarity with group theory, see Zee (2016) for an overview. We denote the action of the group 6 space X by
If @ acts spaces X and Y. we say function f : X + Y is S-equivariant if f(g x) = g f(x). A function f: X Y is G-invariant if f(g 2) = fxx) The G-orbit of x E X is O (I) {g g E 8) C X. When and x' are part of the same orbit, we write x = x'. We say function f : + Y is G-orbit injective if we have f(x1) f(x2) if and only if Ø ~ 22 for any 21, E X. Necessarily, such function is 0-invariant, since [g x) f(x). We work with the permutation group over n. elements Sn and the Lie groups 6 SO(d) or e = (dd). Invariance to the translation group T(d) is conventionally handled using relative positions, Given one of the standard groups above, for an element g we denote by Mg (or another capital letter) its standard matrix representation.
Addresses R2.1
Geometric graphs. A geometric graph g = (A, S, V, X) with a node set V is an attributed graph that is also decorated with geometric attributes: node coordinates X E Raxd and (op- tionally) vector features V Raxd (e.g. velocity, acceleration). The geometric attributes transform as follows under the action of the relevant groups: (1) S, acts on the graph via P&g == PoS, P. P.X)) (2) Orthogonal transformations Q2 E 8 act on V, X via p XQg; and (3) Translations Ee T(d) act the coordinates X via क + f'for all nodes i. Without loss of generality, we work with a single vector feature per node. Our results generalise to multiple vector features
higher-order tensors, in which case would replace the matrix group representation Q2 with a more generic p(g). Two geometric graphs G and H. are geometrically iso- morphic (denoted G ~ H) if there exists an attributed graph isomorphism b such that the geometric attributes are equivalent, up to global group actions QB G and i'E T(d):
Addresses R2.2
(0)))
(H)
b(8)*
(H)
(H) 21(3 b(s) +0)) for all E V(G).
(2)
Geometric graph isomorphism and distinguishing (sub-)graph geometries has important practical implications for representation learning. For e.g., molecular systems, an ideal architecture should map distinct local structural environments around atoms to distinct embeddings in representation space (Bartók et al. 2013
Pozdnyakov et al. 2220)).
Geometric Graph Neural Networks. We consider two broad classes of geometric GNN archi- tectures. B-equivariant GNN layers update sealar and vector features from iteration to t + via learablee aggregate and update functions, AGG and UPD, respectively:
8 (I+1) (1+1) = UPD ((s!) (()), AGG (I((s))) .8 J.
(t)
(3)
where ã. E.- ã. denote relative position vectors. Alternatively, &- 6-invariant GNN layers do not update vector features and only aggregate scalar quantities from local neighbourhoods:
Addresses
R4.2
(1+1) UPD (c)
AGG [[((s]) { U. Ty k.g)) lj e.
(4)
For both models, the scalar features at the final iteration are mapped to graph-level predictions via permutation-invariant readout f T TRJ'. See Appendix for concrete examples of geometric GNNs covered by our framework.
Addresses R2.2, R4.3
THE GEOMETRIC WEISFEILER -EEAN TEST
Assumptions. Analogous to the WL test, the geometric and scalar features the nodes are equipped with come from countable subsets C' C Rd and C" C IR, respectively. As a result, when we require functions to be injective, we require them to be injective over the countable set of G-orbits that are obtained by acting with G on the dataset.
Intuition. For intuition of how generalise WL geometric graphs, note that WL uses a local, node-centric, procedure to update the colour of each node using the colours of its the 1- hop neighhourhond Nú. In the geometric setting, N₁ is an attributed point cloud around the central
3

---

Under review as a conference paper at ICLR 2023
node i. As result, each neighbourhood carries two types of information: (1) neighbourhood type (invariant to B) and (2) neighbourhood geometric orientation (equivariant to 6). From an axiomatic point of view, our generalisation of the WL aggregation procedure must meet two properties:
Property 1: Orbit injectivity of colours. If two neighbourhoods are the same up to an action of 6 (e.g. rotation), then the colours of the corresponding central nodes should be the same. Thus, the colouring must be 6--oritt injective - which also makes (6-invariant- over the countable set of all orbits of neighbourhoods in our dataset.
Preservation of local geometry. A key property of WL is that the aggregation is injective. A G-iinvrriant colouring procedure that purely satisfies Property 1 is not sufficient because, by definition, it loses spatial properties of cach neighbourhood such as the relative pose or orientation (Hinton al. 2011). Thus, we must additionally update auxiliary geometric information variables in way that is --equivariant and injective.
Property 2:
Geometric Weisfeiler-LLeman (GWL). These intuitions motivate the following definition of the GWL test. At initialisation, we assign to each node i E V scalar node colour E C' and an auxiliary object gi containing the geometric information associated to
(s)H(s:), g
c
(5)
where HASH denotes an injective map over the scalar attributes s; of node To define the inductive step, assume we have the colours of the nodes and the associated geometric objects at iteration t - 1. Then, we can aggregate the geometric information around node into new object as follows:
g (t) ((c ((c"-") gg. "-
(((e)-)) 9 (-11) Z.y)) Ii
Importantly, the group @ can act on the geometric objects above inductively by acting on the geo- metric information inside it. This amounts to rotating (or reflecting) the entire t-hop neighbourhood contained inside:
g g.g. = (c) (0) Oz
(-g.":-(' ((oe-))) g.g. 9," A(e)) .9.9) "0-"
Qg Rgtty 1 E N:))
Clearly, the aggregation building gi for any time-step is injective and @ G-equivariant. Finally, we compute the node colours iteration for all E V by aggregating the geometric information in the neighbourhood around node i:
== (1HASH
g (1)
by using G-orbit injective and 6-invariant function that we denote by I-HASIL. That is for any geometric objects g.g', I-HASH(g) I-HASH(g') if and only if there exists g E @ such that g.g'. Note that I-HASH is an idcalised 6-orbit injective function, similar to the HASH function used in WI., which is not necessarily continuous.
Addresses R4.4
Overview. With each iteration, 9 aggregates geometric information in progressively larger /-hop
subgraph neighbourhoods AA(0)) around the node i. The node colours summarise the structure of these t-hops via the -n-invariant aggregation performed by I-HASH. The procedure terminates when the partitions of the nodes induced by the colours do not change from the previous iteration. Finally, given two geometric graphs G and H. there exists some iteration for which (( i V(G) * (e(") i V(H) then GWL deems the two graphs being geometrically non-isomorphic. Otherwise, we say the test cannot distinguish the two graphs.
Invariant GWL Since we are interested in understanding the role of C-equivariance, also consider a more restrictive Invariant GWL (IGWL) that only updates node colours using the G-orbit injective I-HASH function and does not propagate geometric information:
I-HASH
(c(--1) 6.). ((c)) (((5t--), , Z.y)) 11 e.B.
IGWL with k-body scalars. In order to further analyse the construction of the node colouring function I-HASH, we consider IGWL(R) based on the maximum number of nodes involved in the computation of G-invariant scalars (also known as the 'body order' (Batatia et al.) (002a))):
: (-HASH(()) ((e"=").8 3.). ..)) A(c
Ty Zgy) 1 (iENN.))
(9)
4

---

Under review as a conference paper at ICLR 2023
1
(I)
ll
(3)
cf
G1
91 g2
92
(1) ((())
(2)
Ci(t)
66
Figure 2: Invariant GWL. Test. IGWL cannot distinguish 91 and G2 they are 1-hop identical: The 65-rrit of the 1-hop neighbourhood around each node is the same, and IGWL cannot propagate geometric orientation information beyond 1-hop (here 6 O())..
and I-HASH is defined as:
(t-1) Tbe dsj.)B) I E (Ni) HASH (QI-HASH (c) (c( B.), ((())))) ... $c
where j = -- are all possible k-tuples formed of elements of NG. Therefore, IGWL is now constrained to extract information only from all the possible k-sized tuples of nodes (including the central node) in neighbourhood. For instance. (-HASH(2) can identify neighbourhoods only up to pairwise distances among the central node and any of its neighbours (i.e. a 2-body scalar), while (-HASH(3) up to distances and angles formed by any two edges (i.e. 3-body scalar). No- tably, distances and angles alone are incomplete descriptors of local geometry (Bartók et al. 2013 Pozdnyakov et al. 2020). Therefore, I-HASH(()) with lower h makes the colouring weaker.
Addresses R4.4
3.1 WHAT GEOMETRIC GRAPHS CAN GWL AND IGWL DISTINGUISH?
In order to formalise the expressive power of GWL and IGWL, let us consider what geometric graphs can and cannot be distinguished by the tests. As a simple first observation, we note that when all coordinates and vectors set equal to zero GWL coincides with the standard WL. In this edge case, GWL has the same expressive power as WL.
Next, let us consider consider the simplified setting of two geometric graphs Gi (Ai, Si, Vi X1))) and G2 (A2, S2, V2, X2) such that the underlying attributed graphs Si) and (Aq, S2) are isomorphic. This case frequently occurs chemistry, where molecules occur in different conforma- tions, but with the same graph topology given by the covalent bonding structure. Recall that each iteration of GWL aggregates geometric information g; (k) from progressively larger neighbourhoods N around the node i, and distinguishes (sub-)graphs via comparing @-orbit injective colouring of 9, (k) We say 91 and G2 are k-hop distinct if for all graph isomorphisms there is some node i b(i) V22 such that the corresponding k-hop subgraphs ~V(()) and Ar(k) distinct. Other- b(s)
wise, we say 9i and G2 are k-hop identical if all An(h) and (((A) are identical up to group actions. b(()
Addresses R2.3
We can now formalise what geometric graphs can and cannot be distinguished by GWL. Proofs are available in Appendix D
Proposition 1. GWL can distinguish any k-hop distinct geometric graphs G1 and G2 where the underlying attributed graphs are isomorphic, and k iterations are sufficient.
Proposition Up iterations, GWL cannot distinguish any k-hop identical geometric graphs 91 and G2 where the underlying attributed graphs are isomorphic.
Additionally, we can state the following results about the more constrained IGWL. Proposition 3. IGWL can distinguish any 1-hop distinct geometric graphs 9n and G2 where the underlying atributed graphs isomorphic, and I iteration is sufficient.
5

---

Under review as a conference paper at ICLR 2023
Proposition 4. Any number of iterations of IGWL cannot distinguish any 1-hop identical geometric graphs $1 and G2 where the underlying attributed graphs are isomorphic.
An example illustrating Propositions 1 and iis shown in Figures [ respectively.
We can now consider the more general case where the underlying attributed graphs for 91 (A1, St, Vi, x1) and 92 = (A2, 22, V22 X2) are non-isomorphic and constructed from point clouds using radial cutoffs, as conventional for biochemistry and material science applications.
Proposition 5. Assuming geometric graphs are constructed from point clouds using radial cutoff', GWL can distinguish any geometric graphs 91 and G2 where the underlying attributed graphs are non-isomorphic, At most KMax iterations are sufficient, where kMax is the maximum graph diameter among 91 and G2.
These results enable us to compare the expressive powers of GWL and IGWL. Theorem 6. GWL strictly more powerful than IGWL.
This statement formalises the advantage of G-equivariant intermediate layers for graphs and ge- ometric data, as prescribed in the Geometric Deep Learning blueprint (Bronstein et al., 2021] in addition echoing similar intuitions in the computer vision community. As remarked by Hinton et al. (2011), translation invariant models do not understand the relationship between the various parts of image (colloquially called the "Picasso problem"). Similarly, our results point to IGWL failing to understand how the various I-hops of graph are stitched together. Finally, we identify setting where this distinction between the two approaches disappears.
Proposition 7. IGWL has the same expressive power for fully connected geometric graphs.
3.2 CHARACTERISING THE EXPRESSIVE POWER OF GEOMETRIC GNNS
We would like to characterise the maximum expressive power of geometric GNNs based on the GWL test. Firstly, we show that any message passing (-equivariant GNN can be at most as powerful as GWL in distinguishing non-isomorphic geometric graphs. Proofs are available in Appendix E
Theorem 8. Any pair of geometric graphs distinguishable by (--qquivariant GNN is also distin- guishable by GWL.
With a sufficient number of iterations, the output of G-equivariant GNNs can be equivalent to GWL if certain conditions are met regarding the aggregate, update and readout functions.
Proposition 9. 6-eqqivariant GNNs have the same expressive power as GWL if the following condi- tions hold: (1) The aggregation AGG is an injective, 6 G-eqqivariant multiset funcisetfunction. (2) The scalar part of the update UPD, is a 6-orbit injective, G-invariant multiset function. (3) The vector part of the update UPD,, is an injective, G-equivariant multiset function, (4) The graph-level readout f is an injective multiset function.
Similar statements can be made for C (8-invariant GNNs and IGWL. Thus, directly transfer our results about GWL and IGWL to the class of GNNs bounded by the respective tests. This has several interesting practical implications, discussed subsequently.
Addresses R1.3
4 UNDERSTANDING THE DESIGN SPACE OF GEOMETRIC GNNS VIA GWL
Overview. We now use the GWL framework better understand key design choices for building geometric GNNs (Batatia et al., 2022a): (1) Depth or number of layers; and (2) Body order of in- variant scalars. In doing so, we formalise theoretical limitations of current architectures and provide practical implications. Proofs are available in Appendix F
4.1 ROLE OF DEPTH: PROPAGATING GEOMETRIC INFORMATION
Each iteration of GWL expands the neighbourhood from which geoemtric information can be gath- ered. We leveraged this construction in Section 3.1 to formalise the number of GWL iterations required to distinguish classes of geometric graphs.

---

Under review as a conference paper at ICLR 2023
0000 foe GWL
noalar mag.
IOWL
geometiic mag
Stertion
1; g
Hi vi
9
F/a Y
j
Bi. Vg
A=
B V
BBg V
x
X
X
Xmm
X
V.
9g. V
V
V
8/s
V
1-2
Figure 3: Geometric Computation Trees for GWL and IGWL. Unlike GWL, geometric orienta- tion information cannot flow from the leaves to the root in IGWL, restricting its expressive power. IGWL cannot distinguish O1 and G2 as all 1-hop neighbourhoods are computationally identical.
Consequently, stacking multiple 6-equivariant GNN layers enables the computation of composi- tional geometric features. This can be understood via geometric version of computation trees T represents the maximum information contained in GWL/IGWL colours or GNN features at iteration f by an 'unrolling' of the message passing proce- dure. Geometric computation trees are constructed recursively: T.(0) (si, B.) for all V. For t >> 0, we start with a root node (s,, (x) and add child subtree T, for all j E Mr along with the relative position Eiy along the edge, as shown in Figure To obtain the root node's embedding or colour, both scalar and geometrie information propagated from the leaves up the root. Thus, two nodes have identical geometric computation trees, they will be mapped to the same node embed- ding or colour. Critically, geometric orientation information cannot flow from one level another in the computation trees for IGWL and 6- f--invariant GNNs, as they only update scalar information. In the recursive construction procedure, we must insert a connector node (s), d,) before adding the child subtree T (t- !) for all j N₁ and prevent geometric information propagation between them.
(aagg et al. 2020). computation
Addresses R2.3
As a result, even the most powerful 6-iivariant GNNs are restricted in their ability to compute global and non-local geometric properties.
Proposition 10. IGWL and G-invariant GNNs cannot decide several geometric graph properties: (1) perimeter. surface area, and volume of the bounding box/sphere enclosing the geometric graph; (2) distance from the centroid or centre of mass; and (3) dihedral angles.
Practical Implications. Proposition 10 together with Propositions 1 and highlight critical theoretical limitations of 6-invariant GNNs. Our results suggest that E equuiiarian GNNs should be preferred when working with large geometric graphs such macromolecules with thousands of nodes, where message passing is restricted to local radial neighbourhoods around each node.
Motivated by these limitations, two straightforward approaches to improving & ---ivvrriant GNNs may be: (1) pre-computing non-local geometric properties as input features, e.g. models such as GemNet (Gsteiger et al. 2021) and GearNet (Zhang al.) 2022) already use two-hop dihedral angles. And (2) working with fully connected geometric graphs, as Proposition
that -eequivariant and G-invariant GNNs can be made equally powerful when performing all-to-all message passing. This is supported by the empirical success of recent (6-invariant 'Graph Transformers' (Joshi) 2020; Shi
al. 2022) for small molecules with tens of nodes, where working with full graphs is tractable.
4.2
ROLE OF BODY ORDER: DISTINGUISHING 6-ORBITS
At each iteration GWL and IGWL, the I-HASH function assigns a G-iivariaat colouring to dis-
tinct geometric neighbourhood patterns. I-HASII is an idealised G-orbit injective function which is not necessarily continous. In geometric GNNs, this corresponds to scalarising local geometric infor- mation when updating the scalar features; examples are shown in equation II and equation 12 We can analyse the construction of the I-HASH function and the scalarisation step in geometric GNNs via the k-body variations IGWL.(R)-
7

---

Under review as a conference paper at ICLR 2023
Firstly, we formalise the relationship between the injectivity of (-HASH(a) and the maximum cardi- nality of local neighbourhoods in a given dataset.
Proposition 11.
(-H is 8-orbit injective for m - max (Wa)) | i E V}), the maximum
cardinality of all local neighbourhoods N₂ in given dataset.
Practical Implications. While building provably injective (-HASH(() functions may require in- tractably high k, the hierarchy of (GWL- tests enable us to study the expressive power of practical G-invariant aggregators used in current geometric GNN layers, e.g. SchNet (Schütt et al.) 2018).
Addresses
E-GNN (Satorras et al. 202I), and TFN (Thomas et al. 2018) use distances; DimeNet (Gasteiger
R2.7
et al.
2020) uses distances and angles. Notably, MACE (Batatia et al. 2022b) constructs a com-
plete basis of scalars up to arbitrary body order & via Atomic Cluster Expansion (Dusson et al.;
2019). which can be 6-orbit injective if the conditions in Proposition 11 are met. We can state the following about the (G) hierarchy and the corresponding GNNs.
Addresses R4.4
Proposition 12. IGWL(a) is at least as powerful as (GWL For l S 5, (GWL(R) is strictly more powerful than (GWL(K-13-
Finally, we show that IGWI.((2) is equivalent to WI. when all the pairwise distances between the nodes are the same. A similar observation was recently made by Pozddnyakov & Ceriotti (2022).
Proposition 13. Let 91 = ,A,, S,, X and G2 = (A2, S2, X2) be two geometric graphs with the property that all edges have equal length. Then, IGWL(2) distinguishes the two graphs if and only if WL can distinguish the attributed gruphs Si) and Si).
This equivalence points to limitations of bastance-based @ -i-ivarraant models like SchNet (Schitt) et al. 2018). These models suffer from all well- failure cases of WL, e.g. they cannot distin- guish two equilateral triangles from the regular hexagon (Gasteiger et al. 2020).
Synthetic Experiments. results and highlighting practical challenges in building powerful geometric GNNs, s.a. oversmooth- ing and oversquashing with increased depth, as well as designing efficient higher order aggregators.
contaiin additional synthetic experiments supplementing our
Addresses R1.4, R2.5,
R3.1, R4.1
5 DISCRIMINATION AND UNIVERSALITY
Overview. Following Chen al. 2019), we study the equivalence between the universal approx- imation capabilities of geometric GNN models (Dym & Maron 2020) and perspective of discrimi- nating geometric graphs introduced by GWL, generalising their results to any isomorphism induced by a compact Lie group B. We further study the number of invariant aggregators that are required in continuous setting to distinguish any two neighbourhoods. Proofs are available Appendix G
In the interest of generality, we use a general space X acted upon by a compact group & and we are interested in the capacity of G-invariant functions over X to separate points in Y. The restriction to a smaller subset Y is useful because we would like to separately consider the case when Y is countable due to the use of countable features. Therefore, in general, the action of 6 on Y might not be strictly defined since it might yield elements outside Y. For our setting, the reader could take X = (I2d x R y to be the space of n X n geometric graphs and Y = X where X C R2 X
Addresses R2.4
Definition 14. Let & be a compact group and C collection of G-invariant functions from a set X to R. For subset Y C X, we say the C is pairwise Y discriminating for any y1, y22 E Y such that y1 & y2, there exists a function h E C such that h(y)) + h(y22).
We note here that h is not necessarily injective, i.e. there might be v/, y/2 for which h(y)) = h(1/)- Therefore, pairwise discrimination is weaker notion of discrimination than the one GWL uses.
Addresses R2.4
Definition 15. Let & be compact group and C a collection of @ d-invariant functions from X to R. For Y S X, we say the C is universally approximating over Y if all 6 invariaat functions f from X to IR for all e >> 0, there exists h E C such that || -he, llv == supyer If(y) - h(y)] <
Countable Features. We first focus on the countable feature setting, which is also the setting where the GWL test operates. Therefore, we will assume that is countable subset of X. Theorem 16. IfC C is universally approximating over Y, then C is also pairwise Ye discriminating.
8

---

Under review as a conference paper at ICLR 2023
This result further motivates the interest in discriminating geometric graphs, since model that not distinguish two non- con-isommoppic geometric graphs is not universal. By further assuming that Y is finite, obtain a result in the opposite direction. Given collection of functions C, we define like in Chen et al. (2019) the class with J; C and finite k; where the MLP has I. layers with ReLU hidden activations.
given by all the functions of the form (x), (((()).)...((()))]
Theorem 17. C is pairwise Yo discriminating, then C+2 universally approximating over Y.
Continous Features. The symmetries characterising geometric graphs are naturally continuous (e.g. rotations). Therefore, it is natural to ask how the results above translate to continuous B- invariant functions over continuous subspace Y. Therefore, for the rest of this section, we assume that (X, d) is a metric space, Y is a compact subset of X and @ acts continuously on X.
Addresses R2.4
Theorem 18. IfC can universally approximate any continuous G-invariant functions on Y, then C is also pairwise Ys discrininating.
With the additional assumption that = we can also prove the converse.
Theorem 19. C, a class of functions over Y, is pairwise Ye discriminating, then C+2 can also universally approximate any continuous function over Y.
We now produce an estimate for the number of aggregators needed to learn continous orbit-space
injective functions on manifold X based on results from differential geometry (Lee) 2013). A
Addresses R2.6
group 6 acts freely on X if gz = x implies g = ES, where E is the identity element B.
Theorem 20. Let X be a smooth r-dim manifold and & an m-dim compact Lie group acting con- tinuously on X. Suppose there exists a smooth submanifold of X of the same dimension such that & acts freely on it. Then, any G-orbit injective function f X + Rd requires that d 2 n m.
We now x this theorem to the local aggregation operation performed by geometric GNNs. Let X =mma and = Sn x (dd) or S, x (d)... Let P3 and g be the permutation matrix and the orthogonal matrix associated with the group element g B. Then g acts on matrices X X continuously via Pg PgQ Then, B orbit-space injective functions on X are functions on point different point clouds.
clouds of size n that
distinguish any
Theorem 21. For n 2 d - > or n = d = 1, any continuous Sn x SO(d) orbit-space injective function f Raxd + R2 requires that q 2 nd - -d(d= 1)/2.
We can also generalise this O(d), with the slightly stronger assumption that n 2 d. Theorem 22. For n 2 > O, any continuous Sn, x (d) orbit-space injective fnjnctive f R Rd requires that q 2 nd d(d= 1)/2.
Overall, these results show that when working with point clouds in IR3 is common in molecular or physical applications, at least q 3(n - 1) aggregators are required. This result argues why bigger representational width can help distinguish neighbourhoods. Finally, in the particular case of the zero-dimensional subgroup S, x (esora) = Sn we obtain statement holding for all n and generalising a result from PNA Corso et al. (2020) regarding the aggregators for non-geometric GNNs. The original PNA result considers the case d = I and here extend it to arbitrary d. Proposition 23, Any Sn -nviniaaiatt injective function f Raad R2 requires q 2 nd.
DISCUSSION
This work proposes a geometric version of the Weisfeiler-Leman graph isomorphism test (GWL) for discriminating geometric graphs while respecting the underlying spatial symmetries. We use GWL to characterise the expressive power of geometric GNNs and connect the universal approximation properties of these models to discriminating geometric graphs.
GWL provides an abstraction to study the limits of geometric GNNs. In practice it is challenging to build maximally powerful GNNs that satisfy the conditions of Proposition 9 as GWL relies on perfect colouring and aggregation functions to identify distinct neighbourhoods and propogate their geometric orientiation information, respectively. Based on the intuitions gained from GWL, future work will explore building provably powerful, practical geometric GNNs for applications in bio- chemistry, material science, and multiagent robotics, and better characterise the trade-offs related to practical implementation choices.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In ICLR, 2021.
Brandon Anderson, Truong Son Hy, and Risi Kondor. networks. NeurlPS, 2019.
Cormorant: Covariant molecular neural
Albert P Bartók, Risi Kondor, and Gábor Csányi On representing chemical environments. Physical Review B, 2013.
llyes Batatia, Simon Batzner, Dávid Péter Kováes, Albert Musaelian, Gregor NC Simm, Ralf Drautz, Christoph Ortner, Boris Kozinsky, and Gábor Csányi. The design space of (3)-evvivar atom- centered interatomic potentials. arXiv preprint, 2022a.
Ilyes Batatia, Dávid Péter Kovács, Gregor NC Simm, Christoph Ortner, and Gábor Csányi Mace: Higher order equivariant message passing neural networks for fast and accurate force fields. arXiv preprint, 2022b.
Simon Batzner, Albert Musaelian, Lixin Sun, Mario Geiger, Jonathan P Mailoa, Mordechai Ko- rnbluth, Nicola Molinari, Tess E Smidt, and Boris Kozinsky. E (3)-equivariant graph neural networks for data-efficient and accurate interatomic potentials. Nature communications, 2022.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. NeurIPS, 2021a.
Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pietro Lio, and Michael Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. In ICML, 2021b.
Alexander Bogatskiy, Sanmay Ganguly, Thomas Kipf, Risi Kondor, David W Miller, Daniel Mur- nane, Jan Offermann, Mariel Pettee, Phiala Shanahan, Chase Shimmin, et al. Symmetry group equivariant architectures for physics. arXiv preprint, 2022.
Johannes Brandstetter, Rob Hesselink, Elise van der Pol, Erik Bekkers, and Max Welling. Geo- metric and physical quantities improve e(3) equivariant message passing. In ICLR, 2022.
Glen E Bredon. Introduction compact transformation groups. Academic press, 1972.
Glen E Bredon. Topology and geometry, volume 139. Springer Science & Business Media, 2013.
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint, 2021.
Lowik Chanussot, Abhishek Das, Siddharth Goyal, Thibaut Lavril, Muhammed Shuaibi, Morgane Riviere, Kevin Tran, Javier Heras-Domingo, Caleb Ho, Weihua Hu, Aini Palizhati, Anuroop Sri- ram, Brandon Wood, Junwoong Yoon, Devi Parikh, C. Lawrence Zitnick, and Zachary Ulissi. Open catalyst 2020 (oc20) dataset and community challenges. ACS Catalysis, 2021.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. NeurIPS, 2019.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. NeurIPS, 00513260-13277 2020.
Justas Dauparas, Ivan Anishchenko, Nathaniel Bennett, Hua Bai, Robert J Ragotte, Lukas Milles, Basile IM Wicky, Alexis Courbet, Rob J de Haas, Neville Bethel, et al. Robust deep learning based protein sequence design using proteinmpan. bioRxiv, 2022.
Ralf Drautz, Atomic cluster expansion for accurate and transferable interatomic potentials. Physical Review B, 2019.
Genevieve Dusson, Markus Bachmayr, Gabor Csanyi, Ralf Drautz, Simon Etter, Cas van der Oord, and Christoph Ortner. Atomic cluster expansion: Completeness, efficiency and stability. arXiv preprint, 2019.
10

---

Under review as a conference paper at ICLR 2023
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint, 2020.
Nadav Dym and Haggai Maron. On the universality of rotation equivariant point cloud networks. In ICLR, 2020.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric, In ICLR Workshop, 2019.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. ICML, 2020.
Johannes Gasteiger, Janek GroB, and Stephan Günnemann. Directional message passing for molec- ular graphs. In ICLR, 2020.
Johannes Gasteiger, Florian Becker, and Stephan Günneeannn. Gemnet: Universal directional graph neural networks for molecules. In NeurIPS, 2021.
Mario Geiger and Tess Smidt. e3nn: Euclidean neural networks. arXiv preprint, 2022.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
Geoffrey Hinton, Alex Krizhevsky, and Sida D Wang. Transforming auto-encoders. In ICANN, 2011.
Arian Rokkum Jamasb, Ramon Viñas Torné, Eric Ma, Yuanqi Du, Charles Harris, Kexin Huang, Dominic Hall, Pietro Lio, and Tom Leon Blundell. Graphein a python library for geometric deep learning and network analysis biomolecular structures and interaction networks. In NeurlPS, 2022.
Bowen Jing, Stephan Eismann, Patricia Suriana, Raphael John Lamarre Townshend, and Ron Dror. Learning from protein structure with geometric vector perceptrons. ICLR, 2020.
Chaitanya Joshi. Transformers are graph neural networks. The Gradient, 2020.
John M Lee. Smooth manifolds. Introduction to smooth manifolds, pp. 540-555. Springer, 2013.
Dov Levine and Paul Joseph Steinhardt. Quasicrystals: new class of ordered structures. Physical review letters, 1984.
Qingbiao Li, Fernando Gama, Alejandro Ribeiro, and Amanda Prorok. Graph neural networks for decentralized rulti-robot path planning. In IROS, 2020.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. NeurlPS. 2019.
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.
Hoang Nt and Takanori Maehara. Revisiting graph neural networks: All have is low-pass filters. arXiv preprint, 2019.
Sergey N Pozdnyakov and Michele Ceriotti. Incompleteness of graph convolutional neural networks for points clouds in three dimensions. arXiv preprint, 2022.
Sergey N Pozdnyakov, Michael J Willatt, Albert P Bartók. Christoph Ortner, Gábor Csányi, and Michele Ceriotti. Incompleteness of atomic structure representations. Physical Review Letters, 2020.
Ronald C Read and Derek Coreeil. The graph isomorphism disease. Journal of graph theory, 1977.
11

---

Under review as a conference paper at ICLR 2023
Alvaro Sanchez-Gonzalei! Jonathan Godwin, Tobias Pfaff, Rex Ying, Jure Leskovee, and Peter Battaglia. Learning to simulate complex physics with graph networks. In JCML, 2020.
Victor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E (n) equivariant graph neural net- works. In ICML, 2021.
Kristof Schütt, Oliver Unke, and Michael Gastegger. Equivariant message passing for the prediction of tensorial properties and molecular spectra. In ICML, 2021.
Kristof T Schüitt, Huziel E Sauceda, P-J Kindermans, Alexandre Tkatchenko, and K-R Müller. Schnet-a deep learning architecture for molecules and materials. The Journal of Chemical Physics, 148(24):241722, 2018.
Alexander V Shapeev. Moment tensor potentials: A class of systematically improvable interatomic potentials. Multiscale Modeling & Simulation, 2016.
Yu Shi, Shuxin Zheng, Guolin Ke, Yifei Shen, Jiacheng You, Jiyan He, Shengjie Luo. Chang Liu, Di He, and Tie- Yan Liu. Benchmarking graphormer on large-scale molecular modeling datasets. arXiv preprint, 2022.
Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang. Li Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rotation-and translation-equiiariant neural networks for 3d point clouds. arXiv preprint, 2018.
Jake Topping. Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squahhing and bottlenecks on graphs via curvature. In ICLR, 2022.
Soledad Villar, David W Hogg, Kate Storey-Fisher, Weichi Yao, and Ben Blum-Smith. Scalars universal: Equivariant machine learning, structured like classical physics. NeurIPS, 2021.
Maurice Weiler, Mario Geiger, Max Welling, Wouter Boomsma, and Taco S Cohen. 3d steerable cnns: Learning rotationally equivariant features in volumetric data. NeurIPS, 31, 2018.
Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. NTI, Series, 1968.
Tian Xie and Jeffrey C. Grossman. Crystal graph convolutional neural networks for an accurate and interpretable prediction of material properties. Phys. Rev. Lett., 2018.
Keyulu Xu. Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? In ICLR, 2019.
Anthony Zee. Group theory nutshell for physicists. Princeton University Press, 2016.
Zuobai Zhang, Minghao Xu, Arian Jamasb, Vijil Chenthamarakshan, Aurelie Lozano, Payel Das, and Jian Tang. Protein representation learning by geometric structure pretraining. arXiv preprint, 2022.
A RELATED WORK
Literature on the completeness of atom-centred interatomic potentials has focused on distinguishing 1-hop local neighbourhoods (point clouds) around atoms by building spanning sets for continu- ous, G-equivariant multiset functions (Shapeev) [016 Drautz 2019 Dusson et al.) 2019 Pozd- nyakov et al. 2020). Recent theoretical work on geometric GNNs and their universality has shown that architectures such as TFN, GemNet and GVP-GNN (Dym & Maron 2020 Villar et al., [021 Gasteiger et al.] [021] Jing et al.) (020) can be universal approximators of continuous, G-equivariant or G-invariant multiset functions over point clouds, i.e. fully connected graphs. In contrast, the GWL framework studies the expressive power of geometric GNNs operating sparse graphs from the perspective of discriminating geometric graphs and the graph isomorphism problem. The dis- crimination lens is potentially more granular and practically insightful than universality. A model may either be universal or not. On the other hand, there could be multiple degrees of discrimination depending on the classes of geometric graphs that and cannot be distinguished, which our work aims to formalise.
Addresses R2.4
12

---

Under review as a conference paper at ICLR 2023
B ADDITIONAL BACKGROUND ON GEOMETRIC GNNS
The GWL framework can be used to characterise the expressive power and theoretical limitations of two broad classes of geometric GNNs.
G-invariant GNNs. (-invariant GNN layers aggregate scalar quantities from local neighbourhoods via scalarising the geometric information. Scalar features are update from iteration to / 1 via learnable aggregate and update functions, AGG and UPD, respectively:
(++)) = UPD
s AGG [[(ss
U. Jj Tny) Ii
(10)
For egg., SchNet Schütt et al. 2018) uses relative distances || to scalarise local geometric in- formation, while DimeNet (Gasteiger al. 2020) uses both distances as well as angles z.j. Li among triplets, as follows:
Addresses R4.3
(++1)
8,
Σ JEM,
Ji
(SchNet)
(11)
(+1) 8;
Σ f JEN,
Σ fa ( ( | Baj E.H. )
(DimeNet)
(12)
KEMAG
G-equivariant GNNs. G-equivariant GNN layers update both sealar and vector features by prop-
agating scalar as well as vector messages, m (t) and m respectively:
(1) mi m (t) 8,
AGG (() (1) (e) (e Egg
(Aggregate)
(13)
(1+1) s((+1) = UPD
(0
(m m )))
(Update)
(14)
For e.g., PaiNN (Shhttt et al. 2021) interaction layers aggregate scalar and vector features via learnt filters conditioned on the relative distance:
Σ f
|
(15)
JEN
m
1
f2
|
S3 {
|
Zaj
(16)
JEN.
JEN;
E-GNN Satorras et al. step applies gated non linearity (Weiler et al. (018)) on the vector features, which learns to scale their magnitude using their norm concatenated with the scalar features:
2021) and GVP-GNN JJig et al. 2020) use similar operations. The update
(++1) m + f (m llm.1))))
(++1) = :mm? + fs m
[m (11)
m (t)
(17)
The updated scalar features are both (6-invariant and ((d)--ivvriiat as the only geometric informa- tion used the relative distances, while the updated vector features are G-equivariant and T(d)- invariant as they aggregate G-equivariant, T ((dd)invariant vector quantities from the neighbours.
Addresses R4.3
Another example of -eequivariant GNNs the e3nn framework (Geiger Smidt 2022), which can be used to instantiate Tensor Field Network (Thomas et al. 2018). Cormorant (Anderson al. 2019). SEGNN (Brandstetter et al. 2022). and MACE (Batatia et al., 2022b). These models use higher order spherical tensors hi I 2l+1x as node feature, starting from order = up to arbitrary / = L. The first two orders correspond to scalar and vector features, respectively. The higher order tensors h; are updated via tensor products of neighbourhood features h, for all j N, with the higher order spherical harmonic representations Y of the relative displacement
Addresses R2.2
Ky F
wey:
h ((((t)))
(()
Σ Y (wa)) &w n
(18)
JEN,
where the weights w of the tensor product are computed via a learnt radial basis function of the relative distance, i.e. w (Ilă,,1)- To obtain the entry ma { {-la,..., +lg} for the order-la part
13

---

Under review as a conference paper at ICLR 2023
of the updated higher order tensors h (++1), we can expand the tensor product in equation 18 as:
lyma
h (1+1)
h (0)
Com dama
Σ JEN,
Ststats (1 YT."! (#iz) h (0) jdamm?
(19)
1y J2mp
where Clama dgm are the Clebsch-Gordan coefficients ensuring that the updated features are equiv- ariant. Notably, when restricting the tensor product to only scalars (1 = 0) and vectors (7 = 1), we
obtain updates of the form similar to equation [3] equation [6 and equation 17
Applications. Systems in biochemistry, material science, physical simulations, and multiagent robotics can modelled using geometric GNNs. Invariant GNNs have shown strong performance for protein design (Zhang et al., 2022, Dauparas et al. (022) and electrocatalysis (Gasteiger et al.) 2021 Shi et al. 2022), while equivariant GNNs are being used within learnt interatomic potentials for molecular dynamics (Schittt et al. 2021 Batzner et al. 2022 Batatia et al. 2022b).
Addressed
R4.1
C SYNTHETIC EXPERIMENTS FOR GEOMETRIC GNN DESIGN SPACE
Addresses R1.4, R2.5, R3.1, R4.1
We perform three simple synthetic experiments to highlight the practical challenges of building maximally powerful geometric GNNs. We hope that our synthetic experiments and associated code can be a pedagogical tool for exploring the geometric GNN design space in future work.
Setup and Hyperparameters. We experiment with the following models: (1) SchNet (Schütt) jet al. (018)) and DimeNet (Gasteiger et al.] 22200) as representative -iiinariaant GNNs; (2) E-GNN (Satorras et al. 2021) and GVP-GNN (Jing et al. 2020) representative G-equivariant GNNs which
use scalars and vectors in RR:; and (3) TFN (Thomas et al. 2018) and MACE (Batatia et al. 2022b) to study higher order G-equivariant GNNs using spherical tensors. For SchNet and Dime we use the implementation from PyTorch Geometric (Fey & Lenssen 2019). For E-GNN, GVP-GNN, and MACE, we adapt implementations from the respective authors. Our TFN implementation is based on e3nn (Geiger & Smidi 2022), and we also re-implement MACE by incorporating the Equivariant wetaariaan.rrduuttaet ProductRasiss
from its authors into our TFN layer. We set scalar feature channels to 128 for SchNet, DimeNet, and EGNN. We set scalar/vector/ensor feature channels to 64 for GVP, TFN, MACE. TFN and MACE use order L = 2 tensors by default. MACE uses local body order 4 by default. We train all models for 100 epochs using the Adam optimiser, with an initial learning rate le- - 4, which we reduce by a factor of 0.9 and a patience of 25 epochs when the performance plateaus. All results are averaged across 10 random seeds.
Identifying neighbourhood fingerprints: counterexamples from Pozdnyakov et al. (2020). GWL uses node colouring function I-HASH for distinguishing G-orbits of neighbourhoods, i.e. a neighbourhood fingerprint. In geometric GNNs, this corresponds to a scalarisation step where lo- cal geometric information from subsets of neighbours is aggregated to compute G-invariant scalars (termed the body order).
Addresses R2.3, R4.4
To demonstrate the practical implications of scalarisation body order, we evaluate current geomet- ric GNN layers on their ability to discriminate countcrexamples from Pozdnyakov et al. (2020). Each counterexample consists of a pair of local neighbourhoods that are indistinguishable when comparing their set of k-body scalars, i.e. I- I-HASH(()) and geometric GNN layers with body order k cannot distinguish the neighbourhoods. The 3-body counterexample corresponds to Fig. (b) in (Pozdnyakov et al.) 2020), 4-body chiral to Fig.2(e), and 4-body non-chiral to Fig.2(()); the 2-body counterexample is based on the two local neighbourhoods in our running example.
In Table I we train single layer geometric GNNs to distinguish the counterexamples using updated scalar features. Unsurprisingly, we find that most layers computiong 2 or 3 body scalarisations fail the task. Notably, training higher body order MACE layers to distinguish the chiral and non-chiral 4-body counterexamples should be theoretically possible, but proved challenging in practice. This highlights the difficulty of designing as well as optimising continuous, high body order neighbour- hood fingerprints.
Identifying neighbourhood orientation: rotationally symmetric structures. GWL is able to perfectly aggregate -e-quivariant geometric information without losing neighbourhood orientation by making use of an auxiliary nested geometric object gi- On the other hand, G-equivariant GNNs
14

---

Under review as a conference paper at ICLR 2023
Counterexample from Pozdnyakov et
(2020)
2-body
3-body (Fig.1(b)
4body non-chiral
4body chiral
GNN Layer
(Fig.2(f))
(Fig.2(c))
Sch
50.0 + 0.0
50.0 0.0
50.0 = 0.0
50.0 + 0.0
DimeNett.body
100.0 0.0
5.0
50.0 0.0
5.0
E-GNNN2-buut body
50.0 0.0
0.0
50.0
50.0
80(3)-Eq, 033--qqivv.
GVP-GNNs-boof
100.0 0.0
5.00
5..0
50.0
2.ody
50.0
5.00
5.0
5.0
MACE3-body
100.0 0.0
0.0
50.0
50.0
MACE4-body
100.0 0.0
100.0
50.0
5..0
MACEs body
100.0 0.0
100.0 0.0
50.0
50.0
TFN 2-body
50.0
5.0
50.0
50.0
MACE3-body
100.0 0.0
50.0 0.0
5.00
5.,0
MACE E.4-boyy
100.0 0.0
100.0 + 0.0
50.0
50.0
MACEs-body
100.0 = 0.0
100.0 + 0.0
50.0
50.0
Table 1: Counterexamples from Pozdnyakov et al. (2020). We train single layer geometric GNNs to distinguish each counterexample pair of local neighbourhoods that are indistinguishable using k-body scalarisation. Most current geometric GNN layers are restricted to body order or and fail the tasks. Distinguishing the 4-body counterexamples should be theoretically possible with higher body order MACE layers, but proved challenging in practice. This highlights the difficulty of designing as well optimising high body order neighbourhood fingerprints beyond simple distances and angles. Anomolous results are marked in red and expected results in green
Rotational
symmetry 5 fold
GNN Layer
2 fold
3 fold
10 fold
Spherical Cart.
E-GNN
50.0 + 0.0
50.0 + 0.0
50.0 0.0
50.0
GVP-GNNL=1
50.0 0.0
50.0 = 0.0
50.0 0.0
50.0
TFN/MACE
+000
50.0
50.0 0.0
5.0
TEN/MACE
100.0
50.0
50.0
5..0
TFN/MACEL
100.0 - 0.0
100.0 =
50.0
5.0
TFN/MACE,
100.0 + 0.0
100.0 + 0.0
100.0 + 0.0
50.0 + 0.0
TFN/MACE:=10
100.0 + 0.0
100.0 0.0
100.0 0.0
100.0 + 0.0
Table 2: Rotationally symmettric structures. We train single layer --equivariant GNNs to distinguish two distinct rotated versions of each L-fold symmetric structure. We find that layers using order I, tensors are unable to identify the orientation of structures with rotation symmetry higher than I-fold. This issue particularly prevalent for E-GNN and GVP-GNN (tensor order 1).
aggregate geometric information via summing neighbourhood features in fixed dimensional spaces using either cartesian vectors or higher order spherical tensors, which come with tradeoff' between tractability and empirical performance.
In Table 2 we study how rotational symmetries interact with tensor order in (-equivariant GNNs. We evaluate current (E-equivariant layers on their ability to distinguish the orientation of structures with rotational symmetry. An L-fold symmetric structure does not change when rotated by an angle 2x around a point (in 2D) or axis (3D). We consider two distinct rotated versions of each L-fold symmetric structure and train single layer (-equivariant GNNs to classify the two orientations ing the updated geometric features. We find that layers using order L tensors are unable to identify the orientation of structures with rotation symmetry higher than I-fold. This observation can be
L
15

---

Under review as a conference paper at ICLR 2023
k nodes
9 * Ga
i nodes
4-chains)
Number of layers
GNN Layer
1 + 2
| +3
1 +
IGWL
50%
50%
50%
50%
50%
Inv.
SchNet
50.0 = 0.00
50.0 0.00
50.0 = 0.00
50.0 0.00
50,0 0.00
DimeNet
50.0 = 0.00
50.0 + 0.00
50.0 + 0.00
50.0 + 0.00
50.0 + 0.00
GWL
50%
100% %
100%
100%
100 %
Equiv.
E-GNN
50.0 =.0
50.0 + 0.0
50.0
50.0 0.0
100.0 = 0.0
GVP-GNN
50.0 0.0
100.0 = 0.0
100.0 0.0
100.0 + 0.0
100.0 = 0.0
TFN
50.0 0.0
50.0 + 0.0
50.0 0.0
80.0 24.5
85.0 22.9
MACE
50.0 0.0
90.0 # 20.0
90.0 + 20.0
95.0 = 15.0
95.0 + 15.0
Table 3: k-chain geometric graphs. k-chains are (1 + 1)-hop distinguishable and (L$) 1) GWL iterations are theoretically sufficient to distinguish them. We train geometric GNNs with an increasing number of layers distinguish k: = 4-chains. 6-equivariant GNNs may require more iterations that prescribed by GWL, pointing to preliminary evidence of oversmoothing and oversquashing when geometric information is propogated across multiple layers using fixed dimensional feature spaces. IGWL and (6-invariant GNNs are unable to distinguish k-chains for any h: 2 and G O3)).
attributed to the spherical harmonics which exhibits rotational symmetry themselves and used as the underlying basis. Layers such as E-GNN and GVP-GNN using cartesian vectors (correspond- ing to tensor order 1) popular as working with higher order tensors be computationally intractable for many applications. However, E-GNN and GVP-GNN are particularly poor at discim- inating orientation of rotationally symmetric structures. This may have implications for modelling of periodic materials which naturally exhibit such symmetries (Levine & Steinhardt 1984).
Propogating geometric information: k-chains. In addition to perfect aggregation, GWL also assumes perfect propogation of -e-quivariantt geometric information, which implies that the test can be run for any number of iterations without loss of information. In geometric GNNs, (-equivariant information is propogated via summing features from multiple layers in fixed dimensional spaces, which may lead to distortion or loss of information from distant nodes.
Addresses R1.4
To study the practical implications of depth in propagating geometric information beyond local neighbourhoods, we consider k--hain geometric graphs which generalise the examples from [Schtt et al. (2021). Each pair of k-chains consists of k + 2 nodes with & nodes arranged in a line and differentiated by the orientation of the 2 end points. Thus, k-chain graphs are (1 1)-hop distin-
GWL iterations are theoretically sufficient to distinguish them. In Table 3 train --equivariant and G-invariant GNNs with an increasing number of layers to distinguish k-chains. Despite the supposed simplicity of the task, especially for small chain lengths, we find that popular (6-equivariant GNNs such as E-GNN and TFN may require more iterations that pre- scribed by GWL. Notably, as the length of the chain gets larger than k 4, all G-equívariant GNNs tended to lose performance and required more than (L + iterations solve the task. IGWI. and G-invariant GNNs are unable distinguish k-chains.
guishable, and [ +
Table 3 together with Table 2 points to preliminary evidence of the oversmoothing and oversquash- ing phenomenon Nt & Machara 2019 Alon & Yahav! 2021 Topping et al. 2022) for geometric GNNs. These issues are most evident for E-GNN, which uses a single vector feature to aggregate and propogate geometric information. This may have implications in modelling macromolecules where longerange interactions often play important roles. Studying both these issues are exciting avenues for future work towards building provably powerful, practical geometric GNNs.
Addresses R1.4
16

---

Under review as a conference paper at ICLR 2023
D PROOFS FOR WHAT GWL AND IGWL CAN DISTINGUISH
The following results are a consequence of the construction of GWL as well as the definitions of k-hop distinct and k-hop identical geometric graphs. Note that k-hop distinct geometric graphs are also (k: + 1)-hop distinct. Similarly, k-hop identical geometric graphs are also (k- 1)-hop identical, but not necessarily (k 1)- distinct.
Given two distinet neighbourhoods Ni and .22, the B-orbits of the corresponding geometric multi- sets g1 and g2 are mutually exclusive, L.e. Os (oogg) (g2) = 0. By the properties of I-HASH this implies C1 F C2- Conversely, if Nı and N2 were identical up to group actions, their 6-orbits would overlap, i.e. 91 = 92 for some E & and Os = Os (g2) = c1 C2.
Proposition 1. GWL can distinguish any k-hop distinct geometric graphs I1 and G2 where the underlying attributed graphs are isomorphic, and k iterations are sufficient.
Proof of Proposition The k-th iteration of GWL identifies the 6-orbit of the k-hop subgraph
Ng(h)) at each node via the geometric multiset g (k) G1 and G2 being k-hop distinct implies that
there exists some bijection b and some node i V1, b()) E V/2 such that the corresponding k-hop
subgraphs (7(e)) and Ar(k) are distinct. Thus, the 6-orbits of the corresponding geometric multisets b(x)
(A) and 9bt)) are mutually exclusive, i.e. Og (k) n O Os (g 0
(k)
(k) + b())
(k) Thus, k
9,
iterations of GWL are sufficient distinguish 91 and G2.
Proposition 2. Up k iterations, GWL cannot distinguish any k-hop identical geometric graphs 91 and G2 where the underlying attributed graphs are isomorphic.
Proof of Proposition The k-thh iteration of GWL. identifies the G-orbit of the k-hop subgraph A7(5) at each node i via the geometric multiset g 91 and G2 being k-hop identical implies that for all bijections and all nodes E V1, b(i) E V2, the corresponding k-hop subgraphs An( and b(a)
are
identical up to group actions. Thus, the G-orbits of the corresponding geometric multisets g, and (k)
(k)
(k) (k) Thus, up to iterations of GWL cannot Pb(3) overlap, i.e. Oo (g: (*)) = Os (g)))) + c, b(a)' distinguish 91 and G2.
Proposition 3. IGWL can distinguish any 1-hop distinct geometric graphs 91 and G2 where the underlying attributed graphs are isomorphic, and 1 iteration sufficient.
Proof of Proposition Each iteration of IGWL identifies the 6-orbit of the 1-hop local neighbour- hood V (k=1) at each node i. G1 and G2 being 1-hop distinct implies that there exists some bijection b and some node i b1,b(() E V2 such that the corresponding 1-hop local neighbourhoods, .v(1)
and (t11) are distinct. Thus, the G-orbits of the corresponding geometric multisets g;" and Ib(
(1)
b(5) mutually exclusive, i.e. Oe (g )) n O (9))
c + C())
(1) (1) Thus, iteration of IGWL
sufficient distinguish G1 and G2-
Proposition 4. Any number of iterations of IGWL cannot distinguish any 1-hop identical geometric graphs G1 and G2 where the underlying attributed graphs are isomorphic.
Proof of Proposition Each iteration of IGWL identifies the 6-orbit of the 1-hop local neighbour- hood (, each node but cannot identify G-orbits beyond 1-hop by the construction of IGWL as no geometric information is propagated. Gi and G2 being 1-hop identical implies that for all bi- V2, E V2, the corresponding 1 1-hop local neighbourhoods (x())) and b(G) are identical up to group actions. Thus, the G-orbits of the corresponding geometric multisets (1) (1) and go()) overlap, i.e. (g. ()) Oo (9))))
jections b and all nodes i
((k)
(k) (k)
g
c
-00 Thus, any number of IGWL
iterations cannot distinguish Gi and G2-
17

---

Under review as a conference paper at ICLR 2023
Proposition 5. Assuming geometric graphs are constructed from point clouds using radial cutoffs, GWL can distinguish any geometric graphs 91 and G2 where the underlying attributed graphs are non-isomorphic, At most kuax iterations sufficient, where kMar is the maximum graph diameter among 91 and G2.
Proof of Proposition 5 We assume that a geometric graph 9 S,, X) is constructed from point cloud (S, V. x) using a predetermined radial cutoff r. Thus, the adjacency matrix is defined as dij 1 if a7, Tggl2 S or 0 otherwise, for all dij E A. Such construction procedures are conventional for geometric graphs biochemistry and material science.
Given geometric graphs G1 and 92 where the underlying attributed graphs are non-isomorphic, identify kMxx the maximum of the graph diameters G and G2, and chose any arbitrary nodes i EE V1,J E V2. We can define the kMx-hop subgraphs. .V (Naaa) and (( at and j. respectively. Thus, N1 (K(a))) Vi for all E V1, and .V. N V/2 for all j E V2- Due to the assumed construc- tion procedure of geometric graphs, N (((haa)) and ! must be distinct. Otherwise, if NV and A (Asssa)) were identical up to group actions, the sets (S1, Vi, X1) and (S2, Vg, X2) would have yielded isomorphic graphs.
The kMax-th iteration of GWL identifies the G-orbit of the kMax-hop subgraph N ((( at each node i via the geometric multiset g (AMML), As A Af(lsse) and Ar (haa are distinct for any arbitrary nodes
(hsm) are mutually exclusive, i.e. O (g. (Hrra)) > n O (g (haaa) = =0 7 (krem) # c (free)) Thus, Max iterations of GWL are sufficient to distinguish Gi and G2.
Vi.J E V22 the G-orbits of the corresponding geometric multisets g, (AMu) and g,
Theorem 6. GWL is strictly more powerful than IGWL.
Firstly, we can show that the GWL. class contains IGWI. if GWL. can learn the identity when updating 9i for all i V, i.e. g) - g. (t-1) (0) (8,, B.). Thus, GWL least as powerful as IGWL, which does not update gt.
Proof of Theorem 0
g
Secondly, show that GWL is strictly more powerful than IGWL, it suffices to show that there exist pair of geometric graphs that can be distinguished by GWL but not by IGWL. We may consider any k-hop distinet geometric graphs for k > 1, where the underlying attributed graphs are isomorphic. Proposition [ states that GWL can distinguish any such graphs, while Proposition 4 states that IGWL cannot distinguish them. An example is the pair of graphs in Figures [
[
Proposition 7. IGWL has the same expressive power as GWL. fully connected geometric graphs.
We will prove by contradiction. Assume that there exist a pair of fully connected geometric graphs 9i and G2 which GWI. can distinguish, but IGWI. cannot.
Proof of Proposition 7
If the underlying attributed graphs of 91 and G2 are isomorphic, by Proposition | and Proposition Gi and G2 are 1-hop identical but k-hop distinct for some h > 1. For all bijections b and all nodes E V1,b(i) V2, the local neighbourhoods AA(1) and (V(() are identical up to group actions,
and (g (1) = (0(0) (1)
= c = b(()) Additionally, there exists some bijection b and
(1)
some nodes i E b(i) E 1/2 such that the k-hop subgraphs AA(A) and NNb()) are distinct, and (a))
(g ) a Oe (g)()) = 0 = (²a) # 6(1) However, as 91 and G2 are fully connected, for any k.
(k)
(0 = ((()) and N = Nola are identical up to group actions. Thus, (g(g) - Os (g.
On (1) Oe (ga)) c c cmn) "gay This is contradiction.
(b)
(1) (k) (k) (k)
I and G2 are non-isomorphic and fully connected, for any arbitrary E Vi,j E V22 and any k-hop neighbourhood, we know that N, = (A) and N₁ = N Thus, a single iteration of GWL and IGWL identify the same G-orbits and assign the same node colours, i.e. (=(g,") = O (g. (k)) +
(1) (R) and O (1) Os Os ) of =g
(k) This is contradiction.
18

---

Under review as a conference paper at ICLR 2023
E PROOFS FOR EQUIVALENCE BETWEEN GWL AND GEOMETRIC GNNS
Our proofs adapt the techniques used in (Xu et al. 2019 Morris et al. 2019) for connecting WL with GNNs. Note that we omit including the relative position vectors zi in GWL and geometric GNN updates for brevity, as relative positions vectors can be merged into the vector features.
Theorem 8. Any pair of geometric graphs distinguishable by @--eqivariant GNN is also distin- guishable by GWL.
Proof of Theorem g Consider two geometric graphs & and H. The theorem implies that if the GNN graph-level readout outputs f()) & f(H), then the GWL test will always determine G and H to be non-isomorphic, i.e. 9 + H.
We will prove by contradiction. Suppose after T iterations, a GNN graph-level readout outputs (() * (HH), but the GWL test cannot decide G and H are non-isomorphic, iee. 9 and H always have the same collection of node colours for iterations O to T. Thus, for iteration t and t + for any T 1, 9 and H. have the same collection of node colours {c,") well as the same collection of neighbourhood geometric multisets { {(c(') (g.") ()) ((c,,)) - | E NV } up to group actions. Otherwise, the GWL test would have produced different node colours at iteration ++ for G and H as different geometric multisets get unique new colours.
We will show that on the same graph for nodes and k. if (c. 9 (2) = (c2 9 9 we always
have GNN features (s!") b(!)) (s(") Q,5(%) for any iteration This holds for t = 0 because
GWL and the GNN start with the same initialisation. Suppose this holds for iteration t. At iteration
++ 1, if for any i and k; (c(4t)) . ((+1)) (ck g 9t ( then:
(++1),
(cf ( 96 ), (1e 9 ( IJEENB
{
(o .9 gh ) (C : I
(0)
(20)
By our assumption on iteration t,
(5) (1) o( {(s)0) (f 1 Ij (s )00( ((sf)...0f) 1s NaB] (21)
As the same aggregate and update operations are applied each node within the GNN, the same inputs, i.e. neighbourhood features, are mapped to the same output. Thus, (s (1+1) 0
(((+1)
() By induction, if (c.") g g (c 9 (() we always have GNN node features (8)
(e) 2o)( for any iteration L. This creates valid mappings ds do such that s(4)
(c()) and 5!!) (c(c) (1)) for any i E V.
Thus, if G and H have the same collection of node colours and geometric multisets, then G and H. also have the same collection of GNN neighbourhood features
(1 o(d), H( (0) 1 NBB = (<<=(c(") 0. g.. ()))), ((0,(c))) (c 9 ())) li E
Thus, the GNN will output the same collection of node scalar features {s} {s(T)
for 9 and H. and the permutation- iomuuaationinvariaant invariant graph-level readout will output (() f(H). This is a contradiction.
(T)
Similarly, G-invariant GNNs of the form in Equation 4 can be at most as powerful as IGWL.
Theorem 24. Any pair of geometric graphs distinguishable by a G-invariant GNN is also distin- guishable by IGWL
Proof. The proof follows similarly to the proof for Theorem g
Proposition 9. @-equivariant GNNs have the same expressive power as GWL if the following condi- tions hold: (1) The aggregation AGG is an injective, 6-equivariant multiset function. function, (2) The scalar part of the update UPD, is G-orbit injective, G-invariant multiset function. (3) The vector part of the update UPD, is an injective, (-equivariant multiset function. (4) The graph-level readout f is an injective multiset function.
19

---

Under review as a conference paper at ICLR 2023
Proof of Theorem 9 Consider GNN where the conditions hold. We will show that, with a suffi- cient number of iterations t, the output of this GNN is equivalent to GWL, i.e. s(t) = c(")
Let G and H. be any geometric graphs which the GWL test decides non-isomorphic iteration T. Because the graph-level readout function is injective, i.e. maps distinct multiset of node scalar features into unique embeddings, it suffices to show that the GNN's neighbourhood aggregation process, with sufficient iterations, embeds & and H into different multisets node features.
For this proof, we replace G-orbit injective functions with injective functions over the equivalence class generated by the actions of 6. Thus, all elements belonging to the same 6-orbit will first be mapped to the same representative of the equivalence class, denoted by the square brackets [...]. followed by an injective map. The result is 6-orbit injective.
Let us assume the GNN updates node scalar and vector features as:
(1) UPD, ([(s) [(s
(t-1), , ,.(--)),, AGG (H(ss) .S] (t-1)) of(-1) ) I 1 e.)))
(22)
(0) UPD (o (1-1) o. )((- AGG (1(0) 88 (1-1) (((-1) oft
of .oj I1
(23)
with the aggregation function AGG being G-equivariant and injective, the scalar update function UPD, being G-invariant and injective, and the vector update function UPD, being G-equivariant and injective.
The GWL test updates the node colour (c) and geometric multiset 9 as:
o = h. ([(ot-)) . -.ggt- g((-)),, H(cH"") :g) " (ie
(24)
g. h2 ((()t g. () ((())
(1-1) ,9 " I5
(25)
where It, is a 0-invariant and injective map, and hy is a G-equivariant and injective operation (e.g.
in equation 6 expanding the geometric multiset by copying).
We will show by induction that at any iteration I, there always exist injective functions yPs and you
such that (t) (c(c)) and 5!!) (o(c, (t) (0)). This holds for 0 because the initial node
(0))) for i E V(G), V(H). features are the same for GWI. and GNN, & = s and (0) (s (1) with pa(c.)). and ot") with
Suppose this holds for iteration t. At iteration t + 1, substituting s
(p((()) (1) .9
( gives us
o (++1) = UPD (((eodd") Po ()) AGG (H((.(c))) Polc)) pold" .g. (o(")
( NiB)
((+)) = UPD (c)) ( AGG (H(p.(c.)) p.("") .f P.(C (.())),,)))))) 1j N,
The composition of multiple injective functions is injective. Therefore, there exist some injective functions and go such that:
8 (1+1)
10 , ) NiBl). go (l(e() Ii ()))) Hic
(26)
(++) Jr (c))) :g. (1) [(c))) gg.
(0)
( (jeNN)) NiB).
(27)
We can then consider:
s (++1)
go o hTt ho ([(.)) g. (1) ((e)) ) 11 bil (
(28)
of ((+) go o hい² hw (c (0 ((c,0 9 ( (
(1)
(29)
Then, we can denote p.. = g. ohh and p = oh, as injective functions because the composition of injective functions is injective. Hence, for any iteration + 1, there exist injective functions y
and P such that 8 (t+1) Pa (c (()+)) and )((+1) pv (c (++) (+)1)g((( ((+11)
At the T-th iteration, the GWL test decides that G and H. are non-isomorphic, which means the multisets of node colours (c)T)) are different for g and H. The GNN's node scalar features (of (T) = (c(()) } must also be different for 9 and H because of the injectivity of ps.
20

---

Under review as a conference paper at ICLR 2023
A weaker set of conditions is sufficient for 6 (6-invariant GNN be least expressive as IGWL.
Proposition 25. Ø-invariant GNNs have the same expressive power as IGWL if the following condi- tions hold: (1) The aggregation &o and update ó are G-orbit injective. B 8-invariant multiset functions.. (2) The graph-level readout f is an injective multiset function.
Proof. The proof follows similarly the proof for Theorem
F GEOMETRIC GNN DESIGN SPACE PROOFS
Proposition 10. IGWL and G-invariant GNNs cannot decide several geometric graph properties: (1) perimeter, surface area, and volume of the bounding box/sphere enclosing the geometric graph; (2) distance from the centroid or centre of mass; and (3) dihedral angles.
Following Garg al. 2020), we say that class of models decides a geo- metric graph property if there exists a model belonging to this class such that for any two geometric graphs that differ in the property, the model is able to distinguish the two geometric graphs.
Proof of Proposition 10
In Figure 4 we provide an example of two geometric graphs that demonstrate the proposition. Gi and G2 differ in the following geometric graph properties:
Perimeter, surface and volume of the bounding box enclosing the geometric grapt (32 units, 40 units?, 16 units vs. (28 units, 24 units?, units²).
Multiset of distances from the centroid or centre of mass: {0.00, 1 1.00, 1.00, 2.45, 2.45] vs. {0.40, 1. 1.08, 1.08, 2.32, 2.32).
Dihedral angles: <(ljkm)
(E x ( x [ X.mmkl are clearly different for the two graphs.
However, according to Proposition and Theorem 24 both IGWL and (-iivariaatt GNNs cannot distinguish these two geometric graphs, and therefore, cannot decide all these properties.
1-2,11,11
1( 2--111-11
(0,,0,0)
k (1,0,0)
Q
(0, 0.0.4.1 0)
m (2, 1,
j 1(-1,0,0)
3 ((-1,0,0 (0,0,00 ke (1,0,0)
G1
m (2, -1,1)
G2
Figure 4: Two geometric graphs for which IGWL and (--invariant GNNs cannot distinguish their perimeter, surface area, volume of the bounding box/sphere, distance from the centroid, and dihedral angles. The centroid is denoted by red point and distances from it are denoted by dotted red lines. The bounding box enclosing the geometric graph denoted by the dotted green lines.
We can also show this by constructing geometric computation trees for any number of IGWL or (--invariant GNN iterations, as illustrated Figure 3 We observe that the geometric computation trees of any pair of isomorphic nodes identical, as all 1hhop neighbourhoods are computationally identical. Therefore, the set of node colours or node scalar features will also be identical, which implies that Gi and G2 cannot be distinguished.
Proposition 11. I-HASUl;m) is @-orbit injective for m max( ([W) i V}), the maximum cardinality of all local neighbourhoods N₂ given dataset.
The same result applies for the bounding sphere, shown in the figure.
21

---

Under review as a conference paper at ICLR 2023
Proof of Proposition 17 As is the maximum cardinality of all local neighbourhoods Ms under consideration, any distinct neighbourhoods M1 and N₂ must have distinct multisets of m mn-body scalars. As (mH computes scalars involving up to nodes, it will be able to distinguish any such N1 and N2. Thus, (m)) is 6-orbit injective.
Proposition 12. (GWLo)) is at least as powerful as IGWL(k-I)- For k S 5, (GWL(K) is strictly more powerful than (GWL-k-1)-
Proof of Proposition 12 By construction, (-HASIl(s) computes G-invariant scalars from all possi- ble tuples of up to k nodes formed by the elements of a neighbourhood and the central node, Thus, the (A) class contains I-HASH(R-1)) and (R) is least as powerful as I- (-HASH(e-1)> Thus, the corresponding test IGWL(a)) is at least as powerful as IGWL(a-1)
Secondly, to show that IGWL(a) strictly more powerful than IGWL(;-1) for k S suffices to show that there exist pair of geometric neighbourhoods that can be distinguished by IGWL.(R) but not by (k-)-
For 1s and 6 (3) or SO(3), for the local neighbourhood from Figure 1 in Schütt et al. (2021, two configurations with different angles between the neighbouring nodes can be distinguished by IGWL(s) but not by (2)
For k = 4 and @ O(3) SO(3), the pair of local neighbourhoods from Figure 1 in Pozdnyakov et al. (2020) can be distinguished by IGWL(4) but not by IGWL(s).
For k = 5 and @- (3)), the pair of local neighbourhoods from Figure 2(e) in Pozdnyakov et al. 2020) can be distinguished by IGWL(s) but not by IGWL(4).
For k 5 and @ S3(3), the pair of local neighbourhoods from Figure 2(f) in Pozd nyakov et al. 2020) can be distinguished by IGWL(s) but not by IGWL(4)-
Xi) and G2 = (A2, S2, X2) be two geometric graphs with the property that all edges have equal length. Then, IGWL(2) distinguishes the two graphs if and only if WL. can distinguish the attributed graphs (A,,Sı) and St).
Proposition 13. Let 9i (Ai,
Proof of Proposition 13 Let e and k the colours produced by IGWL(2) and WL, respectively, and let i and j be two nodes belonging to any two graphs like in the statement of the result. We prove the statement inductively.
Clearly, (0) k!!)) for all nodes and c( (0)
c; if and only if ( (0) Now, assume that the
statement holds for iteration That is c, C, if and only if (4) k holds for all i. Note that
(1) (1)
o((+1) of ( if and only if c(" c/ and (cc))) | I N.B ((())) |[ 1p N₁ B.
1)
since the norm of the relative vectors is the only injective invariant that IGWL(2) can compute (up to
a scaling). Since all the norms are equal, by the induction hypothesis, this equivalent to k.") 150
and ( (0) p P ((:00 E N, Therefore, this is equivalent to k (1+1) = k (1+1)
G UNIVERSALITY AND DISCRIMINATION PROOFS
G.1 EQUIVALENCE BETWEEN UNIVERSALITY AND DISCRIMINATION
The results in this subsection use the proofs from Chen al. (2019) with minor adaptations. Theorem 16. CfC is universally approximating over Y, then C is also pairwise Ye discriminating.
Proof. Given any y Y, otherwise. Therefore, 8, can be approximated with some < 0.5 over Y by some function h E C. Hence, h(y) h(yy) for any y, v E Y and C is pairwise Yo discriminating.
construct the G-invariant function
X, 5,(x) = 0 y ~ z and
22

---

Under review as a conference paper at ICLR 2023
The following two Lemmas follow from Chen et al. (2019) with minor adaptations. Lemma 26. IfC is pairwise Yo discriminating, then for all E Y, there exists a function by E C+1 such that for all y', 8y(yy) 0 if and only if y 1/.
Proof. For any y1, 1/2 E Y such that yn & y2, let 6n be the function that distinguishes y1, 12- That is 1n1. wy (w1) + 8 wa (V2). Then, we can define function dy,y/ E C:
0 if σ =
6 y (x) 18 (x) Sy (v)
> 0 if x = y
(30)
0 otherwise
This function is already similar to the dy function whose existence we want to prove. To obtain function that strictly positive over all the x E Y with of y, we can construct bg as a sum over all the 8 y.y'
if x =
5y(z)= =
Σ
if 7 y and E (Y) 2 otherwise
(31)
V'EY.y''y
Given the finite set of functions fo J, notice that
8 yg (x) (8 (n.r(()) (e (v) 5g (z)).
Then 8y is obtained by summing all these functions over y' Y with y' # so by E CC+1
Lemma 27. Let C is a class of G-invariant functionn from - IR such that for any y. V E C X, where Y finite, there is öy with the property 8y(y') 0 if and only if y y'. Then C+1 is universally approximating over Y.
Proof. For y E Y, define ry = =
y minggey.y 6y')). Define the hump function with radius r > O,
b, E + R as (s) ( where
(==) ReLU((= + ReLU(L -) 2ReLU(=).
Define ky = Y Yo (v) -1 Since is finite and the intersection with the orbit contains y. ky is finite and well-defined. We can define the G-invariant function h from X to IK as:
M(x)
kyf (., DEY
(32)
Notice that h/y = fly and h e C+1, Therefore, C+1 is universally approximating. Theorem 17. If is pairwise Yo discriminating, then C+2 universally approximating over Y.
Proof. Result follows directly from the two Lemmas above.
Lemma 28. Let X, Y be topological spaces and h X Y + IR continuous functiion Then, if Y compact, fx) infyer h(z,)) 3) continuous.
Proof. The open sets (-oo,a) a) and (b, 00) form basis for the topology of R. Thus, we show that their preimage under of is open. First, notice x E f-1((-o,, a)) and only if (x, y) e h ((=o(_)))) for some y E Y. Therefore, f- a)) px(h- (x- a))))) where Px X x + X is the function projecting in the first argument. Since px is continuous and open, it follows px (h- (ai-iii-aaaaae (((-oo,)) a))) is open.
When x E (-b,, oo)). it implies that for all y E Y, h1 8) > b. This means that for all r e ((b, oo)) and y Y, have (x, y) h-b((,, oo)). Since h(b, oo) is open, then there exists an open box Un.y x Va., S ((b, 00) containing (x, y). Then, the union Uyer (Un.y x Va.y) covers (x) Y. Since Y is compact, there exists finite subcover UK= (Ur. x Vz.9a) of size Kg. Then notice that the open set A, = n K= Un is neighbourhood around æ and A. x Y C h h- oo)). Therefore, A, S f ((b, oo)) and since E f ((b, oo)) was chosen arbitrarily, f ((b, oc)) is open.
23

---

Under review as a conference paper at ICLR 2023
Theorem 18. C can universally approximate any continuous G-invariant functions Y, then C also pairwise Ye discriminating.
Proof. Consider v.y/ E Y such that y 3 y/- Then, the function 6z(2) = inf ge d gæ) = mingee d(y, ga)gg=)))=)))) O, where the second equality follows from the compactness of G. This function is G-invariant. To show that it is continuous, notice that the function fa g) = d(y. gx) is given by the composition dy o a, where a x 6 + X the continuous group action and dy given by (z) d(y,v), 22), which is also continuous. Since composition of continuous functions is continuous and (z) = gn h(z, 6), follows from Lemma that 6, is a continuous function.
- IR is
Given universally approximating class of functions C, we can find function f approximating 8, with precision c 5,(y22 and, therefore, f(v) # f(y').
2-
Definition 29. Let C be class of functions X - The and Y S X. We say that C can locate every orbit over Y for any y E Y and any & > there exists by such that:
1. For all s/ e EY,6,(0)2 20
2. For all vf E EYY
y', then 8, (1/) = O.
3. There exists ry > 0 such that ( < Vy for any yf E Y, then there is g E B such that d(y', 9. y) <.
Notice that since by E C, it is 6 -5-invariant and then for any y E Oo 6y(1/) 6y(")) and there exists g E 6 such that d(y". 0 y) < E. Therefore, intuitively one should see by as some sort of "distance function" measuring how far all y" Ou (v') are from the orbit of y. In other words, when 6, (v²) is low, it means that the entire orbit of y" is close to the orbit of y-
Lemma 30. If is a collection of continuous G-invariant functions from X - IR that is pairwise Yø di-discriminating. then C+1 is able to locate every orbit over Y.
Proof. Select an arbitrary y Y. For 3 * y, let 6y.y' be the function in C separating y and y'. Consider the radius ry.y'" : 2 3/0y. (1) ( > and define the set
Ay 5 oy. (Sy.r (v') Ty Eyeer (v') ryy)
Since Sy.r is continuous, Ay is open. yf = y, then we define Ay = By, E), the open ball in X centred at y with radius e. Clearly, Uver Ay forms a cover for Y. Since Y is compact, then there exists finite subcover given by finite subset Yo Y such that Uper Age
We construct the function (1/) over X as (v') E max( | Tv.y'" y (y") oy. (g")),0) 0). Since ,y.v' is continuous and @ invaaraiant, so is 8y. Finally, it can be shown that 8, can indeed locate the orbit of y over Y.
(v²), where δ (v*) =
1. Clearly, 8, (x) 2 0 for any E X.
2. For any 3¹ E Y, if y", then because 6 is G-invariant, we have sy (v²) dy (v)) so (y() ( = 0.
3. First, consider y" E Y such that vg E B, d(g . y" 2 e. Then, y² E Y UV Ag'. Then, there must be a y' Yo Oolv), such that y² Ay' There- fore, (1") (x') < Taw < f. Then, we have fT 16 (v.r(1/) $T -T -Taa Tryar > 0 (yar(y") > Tn Therefore, we can set ry 3 miin/'Xo)00()))) Tyay 0. ( < rry it folloow that for all o' E Yo Ov()") 6 6..r (x*) T.a'' which implies "" Ugees Blg v,)). Finally, this proves there is g E G such that d(y", .g g.9) <.
-
Since the absolute value function can realised using ReLU activations, it is easy to see that 5, C+1
24

---

Under review as a conference paper at ICLR 2023
Lemma 31. C,, class of functions over compact set Y. can locate every isomorphism class, then C+2 is universal approximating over Y.
Proof. Consider any continuous and 6-invariant function on X. Since Y C X is compact, then is uniformly continuous when restricted to Y. In other words, for all E >> 0, there exists r > 0, such that for all y1, 1/2 E Y, if d(y), 92) < r, then (f()) f(z2)l < E.
Let E Y and define Be (y, == Uy B(y'rr) to be the union of all the open balls of radius r on the orbit of Using the function 6y from Definition 29 there exists Ty such that by ([0,rr)) S (y. for any y E Y. Since by is continuous, 6y ([,, ry)) is open. Therefore, {6y ([O, heY is an open cover for Y. Since Y is compact, we can find a finite subcover (67 ((0, ry))) (ry))JeBs where Yo is finite subset of Y.
We can now use the functions by to construct a set of continuous 6-invariant functions that forms partition of unity for this finite cover. For yo E Yo we construct the function &yo (v/) max(r yo yo0(v (w'),)) 0) and the function o(y/) = Eyeero Oy- (w'), ), both which are continuous. Noticing that (u = yo ((O, )) and that Φy (B') > for any y' E Y, the set of functions vo (3') = ovg (v')) form partition of unity with Emer, 1mm (v') 1 for all y' EY oly")
Notice that write any (6-invariant function f as:
f(y') = f(y')
Σ JoEY
Dan (3')
Σ
f( (o
(33)
Yo Wo ((0.rvo))
The intuition is that because f is continuous, we can approximate f(y') in the expression above by the value of (yo) since y/ is in the neighbourhood of some you Thus, the function that approximates I is h(v') Lo ((o)) (v/). We now show that h can approximate with arbitrary accuracy.
If v/ (10, ryo)) )). then there exists @ such that d(y', 0 yo) < Using the fact that is continous, this implies [f(y') ll yo)l < Because is invariant, (wo) f(g yo). which
implies [f(y/) - (wo)) < &. Then we have:
[ - Σ 1100) -
Σ
f(yo) (v')
(34)
BoEYo v e' (00.r.)))
1f(')) f(vo) viDo (v/) <
(35)
Yo : y E'E ((0.r..))
Finally, to see that h is in C + 2, we can use an MLP with one hidden layer to approximate the followed by one final layer to compute the linear combination of the 1hyo-
Theorem 19. If C, a class of functions over Y, is pairwise Ye discriminating, then C+2 can also universally approximate any continuous function over Y.
Proof. The proof follows from the two Lemmas above.
G.2 NUMBER OF AGGREGATORS CONTINOUS SETTING
Theorem 20. Let X be a smooth n-dim manifold and & m-dim compact Lie group acting con- tinuously on X. Suppose there exists a smooth submanifold of X of the same dimension such that @ acts freely it. Then, any G-orbit injective function f X + Rd requires that d >
Proof. Suppose for the sake of contradiction that there exists an orbit-space injective and continuous function f X + Rm, with m < d. Since Y is submanifold of the same dimension X, then must also be injective over Y. By the Quotient Manifold Theorem (Lee) 2013). Y/8 is topological manifold of dimension d dim X dim G. The map f induces injective function g Y/6 + RT This map is also continuous because for an open set V E 1 (V) = Ty (V)). Because f is continuous and zy is open map, this set is open.
Addresses R2.6
25

---

Under review as a conference paper at ICLR 2023
Y
Rd
Y/G
R
Because Y/S is manifold, there exist an open set U S Y/6 and a homeomorphism vb U + Rdd Then the composition - 9 o 2 is a continuous and injective map from (ú)) I to R.. By the Invariance of Domain Theorem (Bredon] 2013 Corollary 19.9), h is open and it is homeomorphism onto its image ((()(U)) _ I By the Invariance of Dimension Theorem (Bredon
2013 Corollary 19.10), d
Theorem 21. For 2 d 1 or = d = 1, any continuous S, x SO(d) orbit-space injective function f : Raxd + R requires that q 2 nd d(d 1)/2.
Proof. We now consider the case when @ = Sn x SO(d). First, notice that the proof above also holds for this group since is a subgroup of S, (d). However, we can obtain a stronger result and show the result holds for n 2 d 1. In what follows, we reuse the notation from the proof above.
We define the set
z'= (X E X E .... <id-1 S n n.t S. Fii.-..,Z,..1 are linearly independent }: containing d - 1 row-vectors that are linearly independent. Define Mx to be the set of all (d 1) (d 1) minors of the matrix X. Then, we can construct continuous function h(X) m |m| and notice that Z' coincides with the open set h h-'((O, oo)). Then, the set V = Yn Z' also open and non-empty. Therefore, V is submanifold of X of the same dimension and the action of ( is well-defined and continuous on W. We can show again this action is free.
As in the proof above, we have that P3 In. so it remains to inspect the case = XQ2. Any non-trivial rotation Qg must rotate at least a two-dimensional subspace of Rdd. Since the rows of the matrix X span a (d didienssia subspace of R. then Qg cannot leave X invariant unless Qg = Ia. Applying Theorem 20 again yields the result.
For = d = 1, I1-11 : Rixd + IR is. as before, & orbit-space injective.
Theorem 22. For n 2 > any continuous S, x (dd orbit-space injective f Ruxd RS requires that q 2 nd d(d= 1)/2.
Proof. First, suppose that n 2 d > 1. Consider the subspace Y == x || * ||
j), where the norm is just the standard Euclidean norm. Consider the function 9 X IR given by g( = min:ej ||| | ||ا Ill- By standard analysis, this function is continuous and notice that
= g (10, ))) which means that Y is open in X. We also define the set
= = (X E X 3 i1 <... < ia < n.
0).
containing row-vectors that span Rdd As above, this set is the preimage the absolute determinant over (0, oo), which makes Z open in X. Then, the W Y n is also open and non-empty. Therefore, W is submanifold of X of the same dimension and the action of é is well-defined and continuous on W. We can show this action is free.
We investigate the solutions of the equation P₂ = P&X XQ, for X E W. Since orthogonal transformations preserve norms and the rows of X have different norms, it follows that P. = T, + X = XQ We know that subset of the rows of X span the whole of Rd Define the sub-matrix of X containing these rows by X E Iddd Then, we have X g X = Q₂
(X+)-IX' X* Ia. This proves that the action is free and applying Theorem 20 yields the result.
For the trivial case when n = 1, notice that ||-1| : R xd + R is & orbit-space injective.
Proposition 23, Any Sn -ivvariatt injective function f Rdd R requires 2 nd.
Proof. Reusing the notation from above, notice that for all 1, Sn acts freely the sub-mun manifold as shown above. Seeing S, as a zero-dimensional Lie group and applying Theorem 20 yields the result.
26

---

Under review as a conference paper at ICLR 2023
H ALTERNATIVE GWL FORMULATION FOR SO(2)
The version of GWL presented in the main text makes use of a geometric neighbourhood object that keeps increasing size at each iteration. A natural question to ask whether more compact encoding of the orientation of neighbourhood can be achieved. In this section, we show this possible for SO(2), which has some particularly convenient properties: it is commutative and its (discrete) subgroups are particularly simple. First, we point out why when working with the standard representation of (O(d) acting on vectors R&d, the orientation of a neighbourhood cannot be (injectively) encoded into another vector obtained from permutation invariant aggregation.
Definition 32 (Representation). A representation of a group & on a vector space V over is group honomorphism from G to GV), the general linear group on V. That is, a representation is a map p: G + GL(V), such that p(g g2) =
Denote by p the usual representation of O(d) on Rd. Let X' C IRd be a countable feature space, X == {x11....; En) X' multi-set of features and associated representations Pl:-... Pr 6 SO(d). Furthermore assume that 6 acts on Raxd via g. := [o find a multi-set function f d + Rd that is (dd)-qquivariat and injective over the orbit of X, denoted by (xx A first observation is that if O(d) acts (faithfully) via p on R then there is no such function due to the presence of discrete rotational symmetries in certain sets of input vectors (i.e. snowflake like structures).
We want to
Proposition 33 (The Discrete Symmetry Problem). Let X E Rnx2 be a point cloud with n points having (discrete) rotational symmetry, iee. there exists a E Sn and g + id (()) s.I. a gX. Then, any permutation invarian and -quivvarua function f functiooo that f(X) = fgg 0 for all g.
R + I22 has the property
Proof. xX g.X
f(TX)= = f(xX) = = f(x)=
f(X)= =0
This result easily extends to any dimension d by finding such a set of vectors that span two dimen- sional plane and performing a rotation that plane. The proposition above shows that we need to find an alternative representation We show that this is possible for @ SO(2) and for the rest of this section assume d = 2.
Theorem 34. There exists representation p C + SO(R?) and multi-set function HASH,
sending X to R.2 (0) that is unique for each multi-set X C X of bounded size and HASH, (gX) HASH, (X). Furthermore, for any two X1. X1 C X we have that ||HASH, (X1]l =
(X2) iff there is g E B such that 9x11= X2-
Proof. Let (X) be an orbit of X generated by the action of the group @ = SO(() acting on Raxd Sn (i.e. the space of multi-sets of 2D vectors) as the statement of Theorem 34 Then, (2()) acts transitively on (x( by construction.
Ox(X) dx (0())
SO(R2)
S c CR
S0(2)
Denoting by ((X) its isotropy/stabilizer group of X, the function øx O(X) - S0(2)/8(X)
given by Φx (Y) (gX) = ((X) with g E SO(2) is well-defined and, moreover, it is an equivariant homeomorphism of 8-spaces (e.g. see Proposition 4.1 in Bredon (1922).
Notice that because SO(2) is abelian, B(X) is a normal subgroup and SO(2) ((X) (X) is not only manifold, but also a (Lic) group. We will show that we can find a faithful orthogonal representation of this quotient group. Because we working with finite neighbourhoods, the group ( is finite cyclic subgroup (standard result) if X + O. Otherwise, ((X) = 50))).
Therefore, let denote by a(g((X)) the smallest angle of rotation in the equivalence class (X). If 6(X) is a finite cyclic subgroup generated by rotations of an angle 6, then ((80(2)/(())) [0,0). If ((X) S0(2), then a(S0(2)/6(X)) 0. Thus, we can
27

---

Under review as a conference paper at ICLR 2023
construct the orthogonal representation (0(2))((() SO(RR) given by n((((())
(80 (xx))//())27 ((X) finite and 7 I, otherwise. can be checked that in either case, 17 is injective group homomorphism and, therefore, faithful representation of the group.
Given [1,0] 0J E R², can define map W., (O((R)) 5 given by w. (Ra) R. u.
which another homeomorphism. Thus, the composition is sb = wa o o Φx (x)) + R² (X) (
an injective function. Moreover, because the quotient map क S0(2) + (0(2) (20))/(22
is
group homomorphism, we can compose with 7 to lift the representation of (0(2) (xX) ) to
representation = 7 o π of SO(2). Therefore, follows that is also equivariant with respect to this representation of SO(2).
Finally, we can extend v to a function that is injective for any multi-set by constructing (x) for each orbit Og (X), where X is representative of the orbit, using map wo& (X) where [I- [I-HASH(X), 0] (i.e. the norm encodes the orbit).
Alternative S0(2) Geometric Weisfeiler-Leman Test. Given geometric graph (g, X, H),, the (0)))-GWL algorithm consists of three steps:
1. For each node and M(o), initialise:
HASH, F...)
m = HASH Aw (H, xx,Il)
HASII (2C, 27
HASH (m mo m m
2. For each node e E G. update m = HASH, (m .m
3. Go back to step 2 until the partition induced by Hf ||lm!!|| : E GB becomes stable.
4. Return colours of the nodes [[ || GB last iteration L.
28


Reviews:
[{"review_id": "yhblJLOZXHP", "reviewer": "Reviewer_Kinq", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this work, the authors propose a hierarchy (analogous to the WL hierarchy for graphs) $-$ for graphs with geometric features (Typically node features with coordinate information, velocity, etc) which can then be used to characterize the expressive power of equivariant and invariant geometric graph neural network layers to distinguish geometric graphs. The authors then subsequently provide theoretical statements - which link the discriminative power of models on geometric graphs to its universality. ", "summary_of_the_review": "In current state, the weaknesses associated with the paper out-weigh the strengths. However, I would be happy to increase the scores if the authors provide appropriate clarifications.\n\n\n**Updates:**\n\n27th Nov:\n\nThank you very much for the detailed clarifications to reviewers questions as well as the extensive updates to the paper based on reviewer suggestions. I will increase my score to an 6 and would like to see the paper accepted.\n\n\nAfter reading through the other reviews, I have one follow up question regarding the motivation - and would be happy to increase my score further.\n\nConsider the case where geometric graphs are not rigid - for example molecules typically tend to have multiple conformations - where the relative positions of atoms in the molecule change -- and potentially a different contact graph (say based on 3nm distances) is obtained . In such a case, combining 1WL with equivariant/ invariant layers could be too restrictive -- i.e. different conformers of the same molecule would end up with different representations (while ideally we want them in the same equivalence class). Given, the above scenario, why do we need to study the expressive power of 1WL with Lie group equivariant/ invariant layers?\n\n\n11th Dec:\nAfter discussions with other reviewers, reducing score to 5 (From 6)", "strength_and_weaknesses": "**Strengths**:\n1. The idea to extrapolate the WL hierarchy to geometric graphs is important given the recent advances and interesting\n2. The background work and the connections to recent works on geometric graphs is very well presented.\n\n**Weakness, corresponding questions and suggestions:**\n1. In my opinion, based on the statements on preserving the relative positions and using appropriate group actions $-$ the paper appears to incorrectly convey that all Lie groups preserve isometry - which is not the case. Also paper in current state cannot directly handle something like quadrapole-quadrapole interactions (e.g. Anderson, et al. 2019 - Comormant: Covariant molecular neural networks). Would suggest the authors rather use group representations rather than presenting them just as group actions (this would avoid any confusion to readers who may assume all lie groups are matrix lie groups for instance)\n2. To me, it appears like the expressive power of IGWL appears to be misrepresented - am I misunderstanding something? For example, in Figure 2, the authors claim IGWL cannot distinguish the two geometric graphs - however the multiset (Eq 9) does include information about vectors - and a powerful and expressive multiset function, can allow for interactions between the vectors in the multiset from different neighbors - which can help distinguishing the graphs.This raises concern about the statements in section 4 - for example - Proposition 4, Theorem 6.\n3. There appears to be a lack of a connection from moving from the statements in Section 4 to the statements in Section 5. For instance, until Section 5, the authors assume countable number of orbits -- which could be violated in Section 5 e.g. Theorem 21 (unless in cases for example where you explicitly show that the function is a proper map or via alternative mechanisms - currently I am unfortunately unable to locate a statement which conveys the same) and hence can't directly see its extension to the geometric graph application\n4. Lack of experiments (please add at least on synthetic geometric graphs) which show the authors claims that equivariant layers are more powerful than invariant layers - all else remaining constant. \n5. Some of the lemmas and theorem statements in the main paper and appendix related to section 5 - are well known results available in most differential geometry books (e.g. John Lee's Smooth Manifolds) - Would suggest the authors clearly indicate this)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "UMAwDr56gCC", "reviewer": "Reviewer_Vdrv", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work conducts an analysis of expressive power of geometric graph neural networks. Analogous to WL test for generic GNNs, this work proposes Geometric WL (GWL) test and its constraint version IGWL for geometric graphs. It characterizes an expressive-power gap between GWL and IGWL, which is then accordingly extended to a gap between equivariant and invariant GNNs.", "summary_of_the_review": "I would like to recommend rejection. I am willing to raise my score if the above concerns are resolved.\n\n\n---\n\nThe score is raised from 3 to 5.", "strength_and_weaknesses": "Strengths:\n1. Learning on geometric graphs becomes more and more significant these days, and theoretical analysis of geometric GNNs is somehow limited. This work picks a good field.\n2. The presentation is clear and easy to follow. The examples provided in Figures 1, 2 are good to show the gap between equivariant and invariant networks.\n3. The results about numbers of aggregators in Theorem 21-23 are good, as an extension of previous results in PNA.\n\nConcerns:\n1. The major concern is a relative lack of novelty and contribution. Since geometric graphs are generic graphs equipped with additional node coordinates, the definitions of GWL and IGWL are very straightforward (which is not negative). But results in Section 4.1 on characterizing the gap between GWL and IGWL are too easy to obtain, including Prop 2, 3, 4, 7 and Theorem 6. Also, the results in Section 4.2 on the correspondence between GNNs and (I)GWL are too straightforward.\n2. Theorem 21-23 build results on lower bounds of numbers of aggregators for injective functions. It would be great if it discusses whether or not such numbers are linked with the number of layers. In my mind, oversquashing [1]  might be interesting if its discussion can be generalized to geometric graphs. From a broader view, since this work is to generalize theoretical discussion on generic graphs to geometric ones, it would be better to develop a bigger story including richer contents, such as oversmoothing and oversquashing, rather than expressive power only.\n\nReference:\n[1] Understanding over-squashing and bottlenecks on graphs via curvature.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Ik90y4C_e0", "reviewer": "Reviewer_J5ce", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces equivariant and invariant geometric graph neural networks. The authors provide a theoretical analysis of these architectures by introducing a geometric version of the Weisfeiler-Leman (WL) test. In addition to the graph structure, nodes have now geometric attributes (like position, velocity...) in geometric graphs. Geometric graphs will be said to be geometrically isomorphic, if their underlying graphs are isomorphic and their geometric attributes can be obtained through rotations (or reflections). In this setting, a natural extension of WL is proposed and connected to the expressive power of geometric GNN.", "summary_of_the_review": "This paper is not ready for publication and need some major revisions.", "strength_and_weaknesses": "The theoretical analysis extends known results connecting WL to the expressive power of GNN.\n\nI would have liked to get a better motivation for this paper. It is not clear at all to me that this extension to geometric GNN will be of any use. What would be a learning task where these GNNs will produce better results than standard GNNs? It is fine to present theoretical results but I think that a clear connection to machine learning is missing here.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "C3MBcktZmA6", "reviewer": "Reviewer_XpRF", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper considers the problem of isomorphism, in the spirit of the WL test, but for geometric graphs. Such graphs have become prominent in recent times e.g. in applications in chemistry, and have seen notable empirical success. In addition to the usual combinatorial (graph) structure, the geometric nature of such graphs implies that GNNs designed to work on them must respect additional physical symmetries (rotation, reflection, translation). The usual WL test is not sufficient to cover such graphs, and a similar, but more general, geometric analog is needed. This paper fills the gap by proposing such a \"geometric WL test\", which can start to answer questions about the expressive power of geometric GNNs. The proposed procedure is quite straightforward, and the attendant theorems characterize some classes of geometric graphs that can be distinguished by the proposed test. Further, it also manages to quantify questions such as the tradeoffs between G-equivariant GNNs and G-invariant ones. Lastly, the paper also provides an equivalence between a model's ability to discriminate geometric graphs and their universality properties (vis-a-vis to approximate G-invariant functions). \n\n ", "summary_of_the_review": "See above. ", "strength_and_weaknesses": "- The paper has a very clear motivation, and attacks a problem of interest, given the recent successes of geometric GNNs in various key applications in the physical sciences. \n- The formulation of the geometric WL is straightforward and clean, and also interleaves nicely with existing work using the WL test. \n- The procedure proposed seems to indicate some directions for building provably powerful geometric GNNs, which are also practical. The current formulation is not exactly practical, and is kind of abstract.\n- The connections between universality and expressivity discussed are also quite interesting. \n- Lastly, the paper is quite well written and is a pleasure to read. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject