On the Expressive Power of Geometric Graph Neural Networks
The expressive power of Graph Neural Networks (GNNs) has been studied
extensively through the Weisfeiler-Leman (WL) graph isomorphism test. However,
standard GNNs and the WL framework are inapplicable for geometric graphs
embedded in Euclidean space, such as biomolecules, materials, and other
physical systems. In this work, we propose a geometric version of the WL test
(GWL) for discriminating geometric graphs while respecting the underlying
physical symmetries: permutations, rotation, reflection, and translation. We
use GWL to characterise the expressive power of geometric GNNs that are
invariant or equivariant to physical symmetries in terms of distinguishing
geometric graphs. GWL unpacks how key design choices influence geometric GNN
expressivity: (1) Invariant layers have limited expressivity as they cannot
distinguish one-hop identical geometric graphs; (2) Equivariant layers
distinguish a larger class of graphs by propagating geometric information
beyond local neighbourhoods; (3) Higher order tensors and scalarisation enable
maximally powerful geometric GNNs; and (4) GWL's discrimination-based
perspective is equivalent to universal approximation. Synthetic experiments
supplementing our results are available at
\url{https://github.com/chaitjo/geometric-gnn-dojo}
Chaitanya K. Joshi, Cristian Bodnar, Simon V. Mathis, Taco Cohen, Pietro Liò
# On the Expressive Power of Geometric Graph Neural Networks

###### Abstract

The expressive power of Graph Neural Networks (GNNs) has been studied extensively through the Weisfeiler-Leman (WL) graph isomorphism test. However, standard GNNs and the WL framework are inapplicable for _geometric graphs_ embedded in Euclidean space, such as biomolecules, materials, and other physical systems. In this work, we propose a geometric version of the WL test (GWL) for discriminating geometric graphs while respecting the underlying physical symmetries: permutations, rotation, reflection, and translation. We use GWL to characterise the expressive power of geometric GNNs that are _invariant_ or _equivariant_ to physical symmetries in terms of distinguishing geometric graphs. GWL unpacks how key design choices influence geometric GNN expressivity: (1) Invariant layers have limited expressivity as they cannot distinguish one-hop identical geometric graphs; (2) Equivariant layers distinguish a larger class of graphs by propagating geometric information beyond local neighbourhoods; (3) Higher order tensors and scalarisation enable maximally powerful geometric GNNs; and (4) GWL's discrimination-based perspective is equivalent to universal approximation. Synthetic experiments supplementing our results are available at [https://github.com/chaitio/geometric-gnn-dojo](https://github.com/chaitio/geometric-gnn-dojo)

Figure 1: **Axes of geometric GNN expressivity: (1)**_Scalarisation body order_: increasing body order of scalarisation builds expressive local neighbourhood descriptors; (2) _Tensor order_: higher order spherical tensors determine the relative orientation of neighbourhoods; and (3) _Depth_: deep equivariant layers propagate geometric information beyond local neighbourhoods.
## 1 Introduction

Systems in biochemistry [1], material science [2], physical simulations [3], and multiagent robotics [4] contain both geometry and relational structure. Such systems can be modelled via _geometric graphs_ embedded in Euclidean space. For example, molecules are represented as a set of nodes which contain information about each atom and its 3D spatial coordinates as well as other geometric quantities such as velocity or acceleration. Notably, the geometric attributes transform along with Euclidean transformations 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, as the geometric attributes would no longer retain their physical meaning and transformation behaviour [5; 6].

GNNs specialised for geometric graphs follow the message passing paradigm [7] where node features are updated in a permutation equivariant manner by aggregating features from local neighbourhoods. Crucially, in addition to permutations, the updated geometric features of the nodes retain the transformation behaviour of the initial attributes, _i.e._ they are also equivariant to the Lie group of rotations (\(SO(d)\)) or rotations and reflections (\(O(d)\)). We use \(\mathfrak{G}\) as a generic symbol for these Lie groups. We consider two classes of geometric GNNs: (1) \(\mathfrak{G}\)**-equivariant models**, where the intermediate features and propagated messages are equivariant geometric quantities such as vectors [8; 9; 10] or tensors [11; 12; 13]; and (2) \(\mathfrak{G}\)**-invariant models**, which only propagate local invariant scalar features such as distances and angles [14; 15; 16].

Both classes of architectures have shown promising empirical results for applications ranging from protein design [17; 18], molecular dynamics [19; 20], and electrocatalysis [21; 22]. At the same time, key theoretical questions remain unanswered: (1) How to characterise the _expressive power_ of geometric GNNs? and (2) What is the tradeoff between \(\mathfrak{G}\)-equivariant and \(\mathfrak{G}\)-invariant GNNs?

The graph isomorphism problem [23] and the Weisfeiler-Leman (WL) [24] test for distinguishing non-isomorphic graphs have become a powerful tool for analysing the expressive power of non-geometric GNNs [25; 26]. The WL framework has been a major driver of progress in graph representation learning [27; 28; 29; 30; 31]. However, WL does not directly apply to geometric graphs as they exhibit a stronger notion of geometric isomorphism that accounts for spatial symmetries.

**Contributions.** In this work, we study the expressive power of geometric GNNs from the perspective of discriminating non-isomorphic geometric graphs.

* In Section 3, we propose a geometric version of the Weisfeiler-Leman graph isomorphism test, termed GWL, which is a theoretical upper bound on the expressive power of geometric GNNs.
* In Section 4, we use the GWL framework to formalise how key design choices influence geometric GNN expressivity, summarised in Figure 1. Notably, invariant GNNs cannot distinguish graphs where one-hop neighbourhoods are the same and fail to compute non-local geometric properties such as volume, centroid, etc. Equivariant GNNs distinguish a larger class of graphs as stacking equivariant layers propagates geometric information beyond local neighbourhoods.
* Synthetic experiments in Section 5 demonstrate practical implications for building maximally powerful geometric GNNs, _s.a._ oversquashing with increased depth, and counterexamples that highlight the utility of higher order order spherical tensors.
* Finally, in Section 6, we prove an equivalence between a model's ability to discriminate geometric graphs and its universal approximation capabilities. While universality is binary, GWL's discrimination-based perspective provides a more granular and practically insightful lens into geometric GNN expressivity.

## 2 Background

**Graph Isomorphism.** An attributed graph \(\mathcal{G}=(\mathbf{A},\mathbf{S})\) is a set \(\mathcal{V}\) of \(n\) nodes connected by edges. \(\mathbf{A}\) denotes an \(n\times n\) adjacency matrix where each entry \(a_{ij}\in\{0,1\}\) indicates the presence or absence of an edge connecting nodes \(i\) and \(j\). The matrix of _scalar_ features \(\mathbf{S}\in\mathbb{R}^{n\times f}\) stores attributes \(\mathbf{s}_{i}\in\mathbb{R}^{f}\) associated with each node \(i\), where the subscripts index rows and columns in the corresponding matrices. The graph isomorphism problem asks whether two graphs are the same, but drawn differently [23]. Two attributed graphs \(\mathcal{G}\), \(\mathcal{H}\) are _isomorphic_ (denoted \(\mathcal{G}\simeq\mathcal{H}\)) if there exists an edge-preserving bijection \(b:\mathcal{V}(\mathcal{G})\to\mathcal{V}(\mathcal{H})\) such that \(\mathbf{s}_{i}^{(\mathcal{G})}=\mathbf{s}_{b(i)}^{(\mathcal{H})}\).
Weisfeiler-Leman Test (WL).WL tests whether two (attributed) graphs are isomorphic [24]. At iteration zero, WL assigns a _colour_\(c_{i}^{(0)}\in C\) from a countable space of colours \(C\) to each node \(i\). Nodes are coloured the same if their features are the same, otherwise, they are coloured differently. In subsequent iterations \(t\), WL iteratively updates the node colouring by producing a new \(\mathbf{c}_{i}^{(t)}\in C\):

\[\mathbf{c}_{i}^{(t)}:=\textsc{Hash}\left(\mathbf{c}_{i}^{(t-1)},\{\!\!\{\mathbf{c}_{j}^{(t -1)}\mid j\in\mathcal{N}_{i}\}\!\!\}\right), \tag{1}\]

where Hash is an injective map (_i.e._ a perfect hash map) that assigns a unique colour to each input. The test terminates when the partition of the nodes induced by the colours becomes stable. Given two graphs \(\mathcal{G}\) and \(\mathcal{H}\), if there exists some iteration \(t\) for which \(\{\!\!\{c_{i}^{(t)}\mid i\in\mathcal{V}(\mathcal{G})\}\!\!\}\neq\{\!\!\{c_{i}^ {(t)}\mid i\in\mathcal{V}(\mathcal{H})\}\!\!\}\), then the graphs are not isomorphic. Otherwise, the WL test is inconclusive, and we say it cannot distinguish the two graphs.

Group Theory.We assume basic familiarity with group theory, see Zee [32] for an overview. We denote the action of a group \(\mathfrak{G}\) on a space \(X\) by \(\mathfrak{g}\cdot x\). If \(\mathfrak{G}\) acts on spaces \(X\) and \(Y\), we say: (1) A function \(f:X\to Y\) is _\(\mathfrak{G}\)-invariant_ if \(f(\mathfrak{g}\cdot x)=f(x)\), _i.e._ the output remains unchanged under transformations of the input; and (2) A function \(f:X\to Y\) is _\(\mathfrak{G}\)-equivariant_ if \(f(\mathfrak{g}\cdot x)=\mathfrak{g}\cdot f(x)\), _i.e._ a transformation of the input must result in the output transforming equivalently. We also consider _\(\mathfrak{G}\)-orbit injective_ functions: The _\(\mathfrak{G}\)-orbit_ of \(x\in X\) is \(\mathcal{O}_{\mathfrak{G}}(x)=\{\mathfrak{g}\cdot x\mid\mathfrak{g}\in \mathfrak{G}\}\subseteq X\). When \(x\) and \(x^{\prime}\) are part of the same orbit, we write \(x\simeq x^{\prime}\). We say a function \(f:X\to Y\) is _\(\mathfrak{G}\)-orbit injective_ if we have \(f(x_{1})=f(x_{2})\) if and only if \(x_{1}\simeq x_{2}\) for any \(x_{1},x_{2}\in X\). Necessarily, such a function is \(\mathfrak{G}\)-invariant, since \(f(\mathfrak{g}\cdot x)=f(x)\).

We work with the permutation group over \(n\) elements \(S_{n}\) and the Lie groups \(\mathfrak{G}=SO(d)\) or \(\mathfrak{G}=O(d)\). Invariance to the translation group \(T(d)\) is conventionally handled using relative positions or by subtracting the centre of mass from all nodes positions. Given one of the standard groups above, for an element \(\mathfrak{g}\) we denote by \(\mathbf{M}_{\mathfrak{g}}\) (or another capital letter) its standard matrix representation.

Geometric Graphs.A geometric graph \(\mathcal{G}=(\mathbf{A},\mathbf{S},\mathbf{\tilde{V}},\mathbf{\tilde{X}})\) is an attributed graph that is also decorated with geometric attributes: node coordinates \(\mathbf{\tilde{X}}\in\mathbb{R}^{n\times d}\) and (optionally) vector features \(\mathbf{\tilde{V}}\in\mathbb{R}^{n\times d}\) (_e.g._ velocity, acceleration). Without loss of generality, we work with a single vector feature per node. Our setup generalises to multiple vector features or higher-order tensors. The geometric attributes transform as follows under the action of the relevant groups: (1) \(S_{n}\) acts on the graph via \(\mathbf{P}_{\sigma}\mathcal{G}:=(\mathbf{P}_{\sigma}\mathbf{AP}_{\sigma}^{\top},\mathbf{P}_{ \sigma}\mathbf{S},\mathbf{P}_{\sigma}\mathbf{\tilde{V}},\mathbf{P}_{\sigma}\mathbf{\tilde{X}})\); (2) Orthogonal transformations \(\mathbf{Q}_{\mathfrak{g}}\in\mathfrak{G}\) act on \(\mathbf{\tilde{V}},\mathbf{\tilde{X}}\) via \(\mathbf{\tilde{V}}\mathbf{Q}_{\mathfrak{g}},\mathbf{\tilde{X}}\mathbf{Q}_{\mathfrak{g}}\); and (3) Translations \(\mathbf{\tilde{t}}\in T(d)\) act on the coordinates \(\mathbf{\tilde{X}}\) via \(\mathbf{\tilde{x}}_{i}+\mathbf{\tilde{t}}\) for all nodes \(i\). Two geometric graphs \(\mathcal{G}\) and \(\mathcal{H}\) are _geometrically isomorphic_ if there exists an attributed graph isomorphism \(b\) such that the geometric attributes are equivalent, up to global group actions \(\mathbf{Q}_{\mathfrak{g}}\in\mathfrak{G}\) and \(\mathbf{\tilde{t}}\in T(d)\):

\[\left(\mathbf{s}_{i}^{(\mathcal{G})},\mathbf{\tilde{v}}_{i}^{(\mathcal{G})},\mathbf{\tilde {x}}_{i}^{(\mathcal{G})}\right)\ =\ \left(\mathbf{s}_{b(i)}^{(\mathcal{H})},\ \mathbf{Q}_{\mathfrak{g}}\mathbf{\tilde{v}}_{b(i)}^{( \mathcal{H})},\ \mathbf{Q}_{\mathfrak{g}}(\mathbf{\tilde{x}}_{b(i)}^{(\mathcal{H})}+\mathbf{\tilde{t}}) \right)\quad\text{for all }i\in\mathcal{V}(\mathcal{G}). \tag{2}\]

Geometric graph isomorphism and distinguishing (sub-)graph geometries has important practical implications for representation learning. For _e.g._, for molecular systems, an ideal architecture should map distinct local structural environments around atoms to distinct embeddings in representation space [33; 34], which can then be used for downstream predictive task.

Geometric Graph Neural Networks.We consider two broad classes of geometric GNN architectures. (1) _\(\mathfrak{G}\)-equivariant GNN layers_[10; 11] propagate scalar as well as geometric vector features from iteration \(t\) to \(t+1\) via learnable aggregate and update functions, Agg and Upd, respectively:

\[\mathbf{m}_{i}^{(t)},\mathbf{\tilde{m}}_{i}^{(t)} :=\textsc{Agg}\left(\{\!\{(\mathbf{s}_{i}^{(t)},\mathbf{s}_{j}^{(t)},\mathbf{ \tilde{v}}_{i}^{(t)},\mathbf{\tilde{v}}_{j}^{(t)},\mathbf{\tilde{x}}_{ij})\mid j\in \mathcal{N}_{i}\}\!\!\}\right)\] (Aggregate) (3) \[\mathbf{s}_{i}^{(t+1)},\mathbf{\tilde{v}}_{i}^{(t+1)} :=\textsc{Upd}\left((\mathbf{s}_{i}^{(t)},\mathbf{\tilde{v}}_{i}^{(t)}) \,\ (\mathbf{m}_{i}^{(t)},\mathbf{\tilde{m}}_{i}^{(t)})\right)\] (Update) (4)

where \(\mathbf{\tilde{x}}_{ij}=\mathbf{\tilde{x}}_{i}-\mathbf{\tilde{x}}_{j}\) denote relative position vectors. Alternatively, (2) _\(\mathfrak{G}\)-invariant GNN layers_[14; 16] do not update vector features and only propagate invariant scalar quantities computed using geometric information within local neighbourhoods:

\[\mathbf{s}_{i}^{(t+1)}:=\textsc{Upd}\left(\mathbf{s}_{i}^{(t)}\,\ \textsc{Agg}\left(\{\!\{(\mathbf{s}_{i}^{(t)},\mathbf{s}_{j}^{(t)},\mathbf{ \tilde{v}}_{i},\ \mathbf{\tilde{v}}_{j},\ \mathbf{\tilde{x}}_{ij})\mid j\in\mathcal{N}_{i}\}\!\!\}\right)\right). \tag{5}\]

For both models, the scalar features at the final iteration are mapped to graph-level predictions via a permutation-invariant readout \(f:\mathbb{R}^{n\times f}\to\mathbb{R}^{f^{\prime}}\). **In Appendix B, we provide unified equations and examples of geometric GNNs covered by our framework.**
## 3 The Geometric Weisfeiler-Leman Test

**Assumptions.** Analogous to the WL test, we assume for the rest of this section that all geometric graphs we want to distinguish are finite in size and come from a countable dataset. In other words, the geometric and scalar features the nodes are equipped with come from countable subsets \(C\subset\mathbb{R}^{d}\) and \(C^{\prime}\subset\mathbb{R}\), respectively. As a result, when we require functions to be injective, we require them to be injective over the countable set of \(\mathfrak{G}\)-orbits that are obtained by acting with \(\mathfrak{G}\) on the dataset.

**Intuition.** For an intuition of how to generalise WL to geometric graphs, we note that WL uses a local, node-centric, procedure to update the colour of each node \(i\) using the colours of its the 1-hop _neighbourhood_\(\mathcal{N}_{i}\). In the geometric setting, \(\mathcal{N}_{i}\) is an attributed point cloud around the central node \(i\). As a result, each neighbourhood carries two types of information: (1) neighbourhood type (invariant to \(\mathfrak{G}\)) and (2) neighbourhood geometric orientation (equivariant to \(\mathfrak{G}\)). This leads to constraints on the generalisation of the neighbourhood aggregation procedure of Equation 1. 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 \(\mathfrak{G}\) (_e.g._ rotation), then the colours of the corresponding central nodes should be the same. Thus, the colouring must be \(\mathfrak{G}\)-orbit injective - which also makes it \(\mathfrak{G}\)-invariant - over the countable set of all orbits of neighbourhoods in our dataset.

**Property 2: Preservation of local geometry.** A key property of WL is that the aggregation is injective. A \(\mathfrak{G}\)-invariant colouring procedure that purely satisfies Property 1 is not sufficient because, by definition, it loses spatial properties of each neighbourhood such as the relative pose or orientation [35]. Thus, we must additionally update auxiliary _geometric information_ variables in a way that is \(\mathfrak{G}\)-equivariant and injective.

**Geometric Weisfeiler-Leman (GWL).** These intuitions motivate the following definition of the GWL test. At initialisation, we assign to each node \(i\in\mathcal{V}\) a scalar node colour \(c_{i}\in C^{\prime}\) and an auxiliary object \(\boldsymbol{g}_{i}\) containing the geometric information associated to it:

\[c_{i}^{(0)}:=\text{Hash}(\boldsymbol{s}_{i}),\quad\boldsymbol{g}_{i}^{(0)}:= \left(c_{i}^{(0)},\vec{\boldsymbol{v}}_{i}\right), \tag{6}\]

where Hash denotes an injective map over the scalar attributes \(\boldsymbol{s}_{i}\) of node \(i\), _e.g._ the Hash of standard WL. 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 \(i\) into a new object as follows:

\[\boldsymbol{g}_{i}^{(t)}:=\left((c_{i}^{(t-1)},\boldsymbol{g}_{i}^{(t-1)})\;,\;\{\!\!\{(c_{j}^{(t-1)},\boldsymbol{g}_{j}^{(t-1)},\vec{\boldsymbol{x}}_{ ij})\mid j\in\mathcal{N}_{i}\}\!\!\}\right), \tag{7}\]

Here \(\{\!\!\{\!\{\!\{\!\{\!\{\!\{\!\{\!\}\}\}\}\}\!\!\}\!\!\}\!\!\}\) denotes a multiset - a set in which elements may occur more than once. Importantly, the group \(\mathfrak{G}\) can act on the geometric objects above inductively by acting on the geometric information

Figure 2: **Geometric Weisfeiler-Leman Test.** GWL distinguishes non-isomorphic geometric graphs \(\mathcal{G}_{1}\) and \(\mathcal{G}_{2}\) by injectively assigning colours to distinct neighbourhood patterns, up to global symmetries (here \(\mathfrak{G}=O(d)\)). Each iteration expands the neighbourhood from which geometric information can be gathered (shaded for node \(i\)). Example inspired by Schütt et al. [9].
inside it. This amounts to rotating (or reflecting) the entire \(t\)-hop neighbourhood contained inside:

\[\mathfrak{g}\cdot\mathbf{g}_{i}^{(0)} :=\left(c_{i}^{(0)},\ \mathbf{Q}_{\mathbf{g}}\mathbf{\bar{v}}_{i}\right),\] (8) \[\mathfrak{g}\cdot\mathbf{g}_{i}^{(t)} :=\left((c_{i}^{(t-1)},\mathfrak{g}\cdot\mathbf{g}_{i}^{(t-1)}),\ \tfrac{t}{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!
where \(\mathbf{j}=[j_{1},\ldots,j_{k}]\) are all possible \(k\)-tuples formed of elements of \(\mathcal{N}_{i}\). Therefore, \(\text{IGWL}_{(k)}\) is now constrained to extract information only from all the possible \(k\)-sized tuples of nodes (including the central node) in a neighbourhood. For instance, \(\text{I-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 \(\text{I-Hash}_{(3)}\) up to distances and angles formed by any two edges (_i.e._ a \(3\)-body scalar). Notably, distances and angles alone are incomplete descriptors of local geometry as there exist several counterexamples that require higher body-order invariants to be distinguished [33, 34]. Therefore, \(\text{I-Hash}_{(k)}\) with lower \(k\) makes the colouring weaker.

### Characterising the expressive power of geometric GNNs

Following Xu et al. [25], Morris et al. [26], we would like to upper bound the expressive power of geometric GNNs by the GWL test. We show that any \(\mathfrak{G}\)-equivariant GNN can be at most as powerful as GWL in distinguishing non-isomorphic geometric graphs. Proofs are available in Appendix E.

**Theorem 1**.: _Any pair of geometric graphs distinguishable by a \(\mathfrak{G}\)-equivariant GNN is also distinguishable by GWL._

With a sufficient number of iterations, the output of \(\mathfrak{G}\)-equivariant GNNs can be equivalent to GWL _if_ certain conditions are met regarding the aggregate, update and readout functions.

**Proposition 2**.: \(\mathfrak{G}\)_-equivariant GNNs have the same expressive power as GWL if the following conditions hold: (1) The aggregation Agg is an injective, \(\mathfrak{G}\)-equivariant multiset function. (2) The scalar part of the update \(\textsc{Upd}_{\text{\tiny$\mathcal{D}$}_{i}}\) is a \(\mathfrak{G}\)-orbit injective, \(\mathfrak{G}\)-invariant multiset function. (3) The vector part of the update \(\textsc{Upd}_{\text{\tiny$\mathcal{D}$}_{v}}\) is an injective, \(\mathfrak{G}\)-equivariant multiset function. (4) The graph-level readout \(f\) is an injective multiset function._

Similar statements can be made for \(\mathfrak{G}\)-invariant GNNs and IGWL. Thus, we can directly transfer theoretical results between GWL/IGWL, which are abstract mathematical tools, and the class of geometric GNNs upper bounded by the respective tests. This connection has several interesting practical implications, discussed subsequently.

## 4 Understanding the Design Space of Geometric GNNs via GWL

**Overview.** We demonstrate the utility of the GWL framework for understanding how geometric GNN design choices [36] influence expressivity: (1) Depth or number of layers; (2) Invariant vs. equivariant message passing; and (3) Body order of invariant scalarisation. In doing so, we formalise theoretical limitations of current architectures and provide practical implications for designing maximally powerful geometric GNNs. Proofs are available in Appendix D.

### Role of depth: propagating geometric information

Let us consider the simplified setting of two geometric graphs \(\mathcal{G}_{1}=(\mathbf{A}_{1},\mathbf{S}_{1},\mathbf{\tilde{V}}_{1},\mathbf{\tilde{X}}_{1})\) and \(\mathcal{G}_{2}=(\mathbf{A}_{2},\mathbf{S}_{2},\mathbf{\tilde{V}}_{2},\mathbf{\tilde{X}}_{2})\) such that the underlying attributed graphs \((\mathbf{A}_{1},\mathbf{S}_{1})\) and \((\mathbf{A}_{2},\mathbf{S}_{2})\) are isomorphic. This case frequently occurs in chemistry, where molecules occur in different conformations, but with the same graph topology given by the covalent bonding structure.

Each iteration of GWL aggregates geometric information \(\mathbf{g}_{i}^{(k)}\) from progressively larger neighbourhoods \(\mathcal{N}_{i}^{(k)}\) around the node \(i\), and distinguishes (sub-)graphs via comparing \(\mathfrak{G}\)-orbit injective colouring of \(\mathbf{g}_{i}^{(k)}\). We say \(\mathcal{G}_{1}\) and \(\mathcal{G}_{2}\) are \(k\)_-hop distinct_ if for all graph isomorphisms \(b\), there is some node \(i\in\mathcal{V}_{1},b(i)\in\mathcal{V}_{2}\) such that the corresponding \(k\)-hop subgraphs \(\mathcal{N}_{i}^{(k)}\) and \(\mathcal{N}_{b(i)}^{(k)}\) are distinct.

Otherwise, we say \(\mathcal{G}_{1}\) and \(\mathcal{G}_{2}\) are \(k\)_-hop identical_ if all corresponding \(k\)-hop subgraphs \(\mathcal{N}_{i}^{(k)}\) and \(\mathcal{N}_{b(i)}^{(k)}\) are the same up to group actions.

We can now formalise what geometric graphs can and cannot be distinguished by GWL and maximally powerful geometric GNNs, in terms of the number of iterations or depth.

**Proposition 3**.: _GWL can distinguish any \(k\)-hop distinct geometric graphs \(\mathcal{G}_{1}\) and \(\mathcal{G}_{2}\) where the underlying attributed graphs are isomorphic, and \(k\) iterations are sufficient._

**Proposition 4**.: _Up to \(k\) iterations, GWL cannot distinguish any \(k\)-hop identical geometric graphs \(\mathcal{G}_{1}\) and \(\mathcal{G}_{2}\) where the underlying attributed graphs are isomorphic._
Additionally, we can state the following results about the more constrained IGWL.

**Proposition 5**.: _IGWL can distinguish any \(1\)-hop distinct geometric graphs \(\mathcal{G}_{1}\) and \(\mathcal{G}_{2}\) where the underlying attributed graphs are isomorphic, and 1 iteration is sufficient._

**Proposition 6**.: _Any number of iterations of IGWL cannot distinguish any \(1\)-hop identical geometric graphs \(\mathcal{G}_{1}\) and \(\mathcal{G}_{2}\) where the underlying attributed graphs are isomorphic._

An example illustrating Propositions 3 and 6 is shown in Figures 2 and 3, respectively.

We can now consider the more general case where the underlying attributed graphs for \(\mathcal{G}_{1}=(\mathbf{A}_{1},\mathbf{S}_{1},\mathbf{\tilde{V}}_{1},\mathbf{\tilde{X}}_{1})\) and \(\mathcal{G}_{2}=(\mathbf{A}_{2},\mathbf{S}_{2},\mathbf{\tilde{V}}_{2},\mathbf{\tilde{X}}_{2})\) are non-isomorphic and constructed from point clouds using radial cutoffs, as conventional for biochemistry and material science applications.

**Proposition 7**.: _Assuming geometric graphs are constructed from point clouds using radial cutoffs, GWL can distinguish any geometric graphs \(\mathcal{G}_{1}\) and \(\mathcal{G}_{2}\) where the underlying attributed graphs are non-isomorphic. At most \(k_{\text{Max}}\) iterations are sufficient, where \(k_{\text{Max}}\) is the maximum graph diameter among \(\mathcal{G}_{1}\) and \(\mathcal{G}_{2}\)._

### Limitations of invariant message passing: failure to capture global geometry

Propositions 3 and 6 enable us to compare the expressive powers of GWL and IGWL.

**Theorem 8**.: _GWL is strictly more powerful than IGWL._

This statement formalises the advantage of \(\mathfrak{G}\)-equivariant intermediate layers for geometric graphs, as prescribed in the Geometric Deep Learning blueprint [6], in addition to echoing similar intuitions in the computer vision community. As remarked by Hinton et al. [35], translation invariant models do not understand the relationship between the various parts of an image (colloquially called the "Picasso problem"). Similarly, our results point to IGWL and \(\mathfrak{G}\)-invariant GNNs failing to understand how the 1-hop neighbourhoods in a graph are oriented w.r.t. each other.

As a result, even the most powerful \(\mathfrak{G}\)-invariant GNNs are restricted in their ability to compute global and non-local geometric properties.

**Proposition 9**.: _IGWL and \(\mathfrak{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._

Finally, we identify a setting where this distinction between the two approaches disappears.

**Proposition 10**.: _IGWL has the same expressive power as GWL for fully connected geometric graphs._

**Practical Implications.** Proposition 9 highlights critical theoretical limitations of \(\mathfrak{G}\)-invariant GNNs. This suggests that \(\mathfrak{G}\)-equivariant GNNs should be preferred when working with large geometric graphs such as macromolecules with thousands of nodes, where message passing is restricted to local radial neighbourhoods around each node. Stacking multiple \(\mathfrak{G}\)-equivariant layers enables the computation of compositional geometric features.

Two straightforward approaches to overcoming the limitations of \(\mathfrak{G}\)-invariant GNNs may be: (1) pre-computing non-local geometric properties as input features, _e.g._ models such as GemNet [21] and SphereNet [37] use two-hop dihedral angles. And (2) working with fully connected geometric graphs, as Proposition 10 suggests that \(\mathfrak{G}\)-equivariant and \(\mathfrak{G}\)-invariant GNNs can be made equally powerful when performing all-to-all message passing. This is supported by the empirical success of recent \(\mathfrak{G}\)-invariant 'Graph Transformers' [22, 38] for small molecules with tens of nodes, where working with full graphs is tractable.

### Role of scalarisation body order: identifying neighbourhood \(\mathfrak{G}\)-orbits

At each iteration of GWL and IGWL, the I-Hash function assigns a \(\mathfrak{G}\)-invariant colouring to distinct geometric neighbourhood patterns. I-Hash is an idealised \(\mathfrak{G}\)-orbit injective function which is not necessarily continuous. In geometric GNNs, this corresponds to scalarising local geometric information when updating the scalar features; examples are shown in equation 14 and equation 15. We can analyse the construction of the I-Hash function and the scalarisation step in geometric GNNs via the \(k\)-body variations \(\text{IGWL}_{(k)}\), described in Section 3. In doing so, we will make connections between IGWL and WL for non-geometric graphs.

Firstly, we formalise the relationship between the injectivity of I-Hash\({}_{(k)}\) and the maximum cardinality of local neighbourhoods in a given dataset.
**Proposition 11**.: \(\text{I-Hash}_{(m)}\) _is \(\mathfrak{G}\)-orbit injective for \(m=\text{max}(\{|\mathcal{N}_{i}|\mid i\in\mathcal{V}\})\), the maximum cardinality of all local neighbourhoods \(\mathcal{N}_{i}\) in a given dataset._

**Practical Implications.** While building provably injective \(\text{I-Hash}_{(k)}\) functions may require intractably high \(k\), the hierarchy of \(\text{IGWL}_{(k)}\) tests enable us to study the expressive power of practical \(\mathfrak{G}\)-invariant aggregators used in current geometric GNN layers, _e.g._ SchNet [14], E-GNN [10], and TFN [11] use distances, while DimeNet [16] uses distances and angles. Notably, MACE [20] constructs a _complete_ basis of scalars up to arbitrary body order \(k\) via Atomic Cluster Expansion [39], which can be \(\mathfrak{G}\)-orbit injective if the conditions in Proposition 11 are met. We can state the following about the \(\text{IGWL}_{(k)}\) hierarchy and the corresponding GNNs.

**Proposition 12**.: \(\text{IGWL}_{(k)}\) _is at least as powerful as \(\text{IGWL}_{(k-1)}\). For \(k\leq 5\), \(\text{IGWL}_{(k)}\) is strictly more powerful than \(\text{IGWL}_{(k-1)}\)._

Finally, we show that \(\text{IGWL}_{(2)}\) is equivalent to WL when all the pairwise distances between the nodes are the same. A similar observation was recently made by Pozdnyakov and Ceriotti [40].

**Proposition 13**.: _Let \(\mathcal{G}_{1}=(\mathbf{A}_{1},\mathbf{S}_{1},\mathbf{\tilde{X}}_{1})\) and \(\mathcal{G}_{2}=(\mathbf{A}_{2},\mathbf{S}_{2},\mathbf{\tilde{X}}_{2})\) be two geometric graphs with the property that all edges have equal length. Then, \(\text{IGWL}_{(2)}\) distinguishes the two graphs if and only if WL can distinguish the attributed graphs \((\mathbf{A}_{1},\mathbf{S}_{1})\) and \((\mathbf{A}_{1},\mathbf{S}_{1})\)._

This equivalence points to limitations of distance-based \(\mathfrak{G}\)-invariant models like SchNet [14]. These models suffer from all well-known failure cases of WL, _e.g._ they cannot distinguish two equilateral triangles from the regular hexagon [16].

## 5 Synthetic Experiments on Geometric GNN Expressivity

**Overview.** We provide synthetic experiments to supplement our theoretical results and highlight practical challenges in building maximally powerful geometric GNNs, _s.a._ oversquashing of geometric information with increased depth and the need for higher order tensors in \(\mathfrak{G}\)-equivariant GNNs. We hope that the accompanying codebase, geometric-gnn-dojo2, can be a pedagogical resource for advancing geometric GNN architectures in a principled manner. See Appendix C for details on experimental setup and hyperparameters.

\begin{table}
\begin{tabular}{l l c c c c c} \hline \hline  & (\(k=4\)-chains) & \multicolumn{5}{c}{**Number of layers**} \\  & **GNN Layer** & \(\lfloor\frac{k}{2}\rfloor\) & \(\lfloor\frac{k}{2}\rfloor+1=\mathbf{3}\) & \(\lfloor\frac{k}{2}\rfloor+2\) & \(\lfloor\frac{k}{2}\rfloor+3\) & \(\lfloor\frac{k}{2}\rfloor+4\) \\ \hline \multirow{4}{*}{\(\mathfrak{G}\)-invariant} & \(\text{IGWL}\) & \(50\%\) & \(50\%\) & \(50\%\) & \(50\%\) & \(50\%\) \\  & \(\text{SchNet}\) & \(50.0\pm 0.00\) & \(50.0\pm 0.00\) & \(50.0\pm 0.00\) & \(50.0\pm 0.00\) & \(50.0\pm 0.00\) \\  & DimeNet & \(50.0\pm 0.00\) & \(50.0\pm 0.00\) & \(50.0\pm 0.00\) & \(50.0\pm 0.00\) & \(50.0\pm 0.00\) \\ \hline \multirow{4}{*}{\(\mathfrak{G}\)-invariant} & \(\text{GWL}\) & \(50\%\) & \(100\%\) & \(100\%\) & \(100\%\) & \(100\%\) \\  & E-GNN & \(50.0\pm 0.0\) & \(50.0\pm 0.0\) & \(50.0\pm 0.0\) & \(50.0\pm 0.0\) & \(\mathbf{100.0\pm 0.0}\) \\  & GVP-GNN & \(50.0\pm 0.0\) & \(\mathbf{100.0\pm 0.0}\) & \(\mathbf{100.0\pm 0.0}\) & \(\mathbf{100.0\pm 0.0}\) & \(\mathbf{100.0\pm 0.0}\) \\  & TFN & \(50.0\pm 0.0\) & \(50.0\pm 0.0\) & \(50.0\pm 0.0\) & \(\mathbf{80.0\pm 24.5}\) & \(\mathbf{85.0\pm 22.9}\) \\  & MACE & \(50.0\pm 0.0\) & \(\mathbf{90.0\pm 20.0}\) & \(\mathbf{90.0\pm 20.0}\) & \(\mathbf{95.0\pm 15.0}\) & \(\mathbf{95.0\pm 15.0}\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: \(k\)_-chain geometric graphs._\(k\)-chains are \((\lfloor\frac{k}{2}\rfloor+1)\)-hop distinguishable and \((\lfloor\frac{k}{2}\rfloor+1)\) GWL iterations are theoretically sufficient to distinguish them. We train geometric GNNs with an increasing number of layers to distinguish \(k=4\)-chains. \(\mathfrak{G}\)**-equivariant GNNs may require more iterations that prescribed by GWL, pointing to preliminary evidence of oversquashing when geometric information is propagated across multiple layers using fixed dimensional feature spaces.** IGWL and \(\mathfrak{G}\)-invariant GNNs are unable to distinguish \(k\)-chains for any \(k\geq 2\) and \(\mathfrak{G}=O(3)\). Anomolous results are marked in \(\overline{\text{red}}\) and expected results in \(\overline{\text{green}}\).
### Depth, non-local geometric properties, and oversquashing

GWL assumes perfect propagation of \(\mathfrak{G}\)-equivariant geometric information at each iteration, which implies that the test can be run for any number of iterations without loss of information. In geometric GNNs, \(\mathfrak{G}\)-equivariant information is propagated via summing features from multiple layers in fixed dimensional spaces, which may lead to distortion or loss of information from distant nodes.

Experiment.To study the practical implications of depth in propagating geometric information beyond local neighbourhoods, we consider \(k\)-chain geometric graphs which generalise the examples from Schutt et al. [9]. Each pair of \(k\)-chains consists of \(k+2\) nodes with \(k\) nodes arranged in a line and differentiated by the orientation of the \(2\) end points. Thus, \(k\)-chain graphs are \((\lfloor\frac{k}{2}\rfloor+1)\)-hop distinguishable, and \((\lfloor\frac{k}{2}\rfloor+1)\) GWL iterations are theoretically sufficient to distinguish them. In Table 1, we train \(\mathfrak{G}\)-equivariant and \(\mathfrak{G}\)-invariant GNNs with an increasing number of layers to distinguish \(k\)-chains.

Results.Despite the supposed simplicity of the task, we find that popular \(\mathfrak{G}\)-equivariant GNNs such as E-GNN [10] and TFN [11] may require more iterations that prescribed by GWL. Notably, for chains larger than \(k=4\), all \(\mathfrak{G}\)-equivariant GNNs tended to require more than \((\lfloor\frac{k}{2}\rfloor+1)\) iterations to solve the task. Additionally, IGWL and \(\mathfrak{G}\)-invariant GNNs are unable to distinguish \(k\)-chains.

Table 1 points to preliminary evidence of the _oversquashing_ phenomenon [41, 42] for geometric GNNs. The issue is most evident for E-GNN, which uses a single vector feature to aggregate and propagate geometric information. This may have implications in modelling macromolecules where long-range interactions often play important roles.

### Higher order tensors and rotationally symmetric structures

In addition to perfect propagation, GWL is also able to injectively aggregate \(\mathfrak{G}\)-equivariant geometric information by making use of an auxiliary nested geometric object \(\mathbf{g}_{i}\). On the other hand, \(\mathfrak{G}\)-equivariant GNNs aggregate geometric information via summing neighbourhood features represented by either cartesian vectors (tensor order 1) or higher order spherical tensors. This choice of basis often comes with trade-offs between computational tractability and empirical performance.

Experiment.To demonstrate the utility of higher order tensors in \(\mathfrak{G}\)-equivariant GNNs, we study how rotational symmetries interact with tensor order. In Table 2, we evaluate current \(\mathfrak{G}\)-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 \(\frac{2\pi}{L}\) around a point (in 2D) or axis (3D). We consider two _distinct_ rotated versions of each \(L\)-fold symmetric structure and train single layer \(\mathfrak{G}\)-equivariant GNNs to classify the two orientations using the updated geometric features.

\begin{table}
\begin{tabular}{l l c c c} \hline \hline  & \multicolumn{4}{c}{**Rotational symmetry**} \\  & **GNN Layer** & 2 fold & 3 fold & 5 fold & 10 fold \\ \hline \multirow{3}{*}{\(\mathfrak{G}\)-equivariant} & E-GNN\({}_{L=1}\) & \(50.0\pm 0.0\) & \(50.0\pm 0.0\) & \(50.0\pm 0.0\) & \(50.0\pm 0.0\) \\  & GVP-GNN\({}_{L=1}\) & \(50.0\pm 0.0\) & \(50.0\pm 0.0\) & \(50.0\pm 0.0\) & \(50.0\pm 0.0\) \\ \hline \multirow{3}{*}{\(\mathfrak{G}\)-equivariant} & TFN/MACE\({}_{L=1}\) & \(50.0\pm 0.0\) & \(50.0\pm 0.0\) & \(50.0\pm 0.0\) & \(50.0\pm 0.0\) \\  & TFN/MACE\({}_{L=2}\) & \(\mathbf{100.0\pm 0.0}\) & \(50.0\pm 0.0\) & \(50.0\pm 0.0\) & \(50.0\pm 0.0\) \\  & TFN/MACE\({}_{L=3}\) & \(\mathbf{100.0\pm 0.0}\) & \(\mathbf{100.0\pm 0.0}\) & \(50.0\pm 0.0\) & \(50.0\pm 0.0\) \\  & TFN/MACE\({}_{L=5}\) & \(\mathbf{100.0\pm 0.0}\) & \(\mathbf{100.0\pm 0.0}\) & \(\mathbf{100.0\pm 0.0}\) & \(50.0\pm 0.0\) \\  & TFN/MACE\({}_{L=10}\) & \(\mathbf{100.0\pm 0.0}\) & \(\mathbf{100.0\pm 0.0}\) & \(\mathbf{100.0\pm 0.0}\) & \(\mathbf{100.0\pm 0.0}\) \\ \hline \hline \end{tabular}
\end{table}
Table 2: Rotationally symmetric structures. We train single layer \(\mathfrak{G}\)-equivariant GNNs to distinguish two _distinct_ rotated versions of each \(L\)-fold symmetric structure. **We find that layers using order \(L\) tensors are unable to identify the orientation of structures with rotation symmetry higher than \(L\)-fold.** This issue is particularly prevalent for layers using cartesian vectors (tensor order 1).
**Results.** We find that layers using order \(L\) tensors are unable to identify the orientation of structures with rotation symmetry higher than \(L\)-fold. This observation may be attributed to spherical harmonics, which are used as the underlying orthonormal basis and are rotationally symmetric themselves. Layers such as E-GNN [10] and GVP-GNN [8] using cartesian vectors are popular as higher order tensors can be computationally intractable for many applications. However, E-GNN and GVP-GNN are particularly poor at discriminating the orientation of rotationally symmetric structures. This may have implications for the modelling of periodic materials which naturally exhibit such symmetries [43].

## 6 Discrimination and Universality

**Overview.** Following Chen et al. [27], we study the equivalence between the universal approximation capabilities of geometric GNNs [44, 45] and the perspective of discriminating geometric graphs introduced by GWL, generalising their results to any isomorphism induced by a compact Lie group \(\mathfrak{G}\). We further study the number of invariant aggregators that are required in a continuous setting to distinguish any two neighbourhoods. Proofs are available in Appendix F.

In the interest of generality, we use a general space \(X\) acted upon by a compact group \(\mathfrak{G}\) and we are interested in the capacity of \(\mathfrak{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 \(\mathfrak{G}\) on \(Y\) might not be strictly defined since it might yield elements outside \(Y\). For our setting, the reader could take \(X=(\mathbb{R}^{d}\times\mathbb{R}^{f})^{n\times n}\) to be the space of \(n\times n\) geometric graphs and \(Y=\mathcal{X}^{n\times n}\), where \(\mathcal{X}\subseteq\mathbb{R}^{d}\times\mathbb{R}^{f}\).

**Definition 14**.: _Let \(\mathfrak{G}\) be a compact group and \(\mathcal{C}\) a collection of \(\mathfrak{G}\)-invariant functions from a set \(X\) to \(\mathbb{R}\). For a subset \(Y\subseteq X\), we say the \(\mathcal{C}\) is **pairwise \(\mathbf{Y_{\mathfrak{G}}}\) discriminating** if for any \(y_{1},y_{2}\in Y\) such that \(y_{1}\not\succeq y_{2}\), there exists a function \(h\in\mathcal{C}\) such that \(h(y_{1})\not\succeq h(y_{2})\)._

We note here that \(h\) is not necessarily injective, _i.e._ there might be \(y^{\prime}_{1},y^{\prime}_{2}\) for which \(h(y^{\prime}_{1})=h(y^{\prime}_{1})\). Therefore, pairwise discrimination is a weaker notion of discrimination than the one GWL uses.

**Definition 15**.: _Let \(\mathfrak{G}\) be a compact group and \(\mathcal{C}\) a collection of \(\mathfrak{G}\)-invariant functions from \(X\) to \(\mathbb{R}\). For \(Y\subseteq X\), we say the \(\mathcal{C}\) is **universally approximating** over \(Y\) if for all \(\mathfrak{G}\)-invariant functions \(f\) from \(X\) to \(\mathbb{R}\) and for all \(\epsilon>0\), there exists \(h_{\varepsilon,f}\in\mathcal{C}\) such that \(\|f-h_{\varepsilon,f}\|_{Y}:=\sup_{y\in Y}|\hat{f}(y)-h(y)|<\varepsilon\)._

**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 \(Y\) is a countable subset of \(X\).

**Theorem 16**.: _If \(\mathcal{C}\) is universally approximating over \(Y\), then \(\mathcal{C}\) is also pairwise \(Y_{\mathfrak{G}}\) discriminating._

This result further motivates the interest in discriminating geometric graphs, since a model that cannot distinguish two non-isomorphic geometric graphs is not universal. By further assuming that \(Y\) is finite, we obtain a result in the opposite direction. Given a collection of functions \(\mathcal{C}\), we define like in Chen et al. [27] the class \(\mathcal{C}^{+L}\) given by all the functions of the form \(\mathrm{MLP}([f_{1}(x),\ldots,f_{k}(x)])\) with \(f_{i}\in\mathcal{C}\) and finite \(k\), where the MLP has \(L\) layers with ReLU hidden activations.

**Theorem 17**.: _If \(\mathcal{C}\) is pairwise \(Y_{\mathfrak{G}}\) discriminating, then \(\mathcal{C}^{+2}\) is universally approximating over \(Y\)._

**Continuous 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_\(\mathfrak{G}\)-invariant functions over a 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 \(\mathfrak{G}\) acts continuously on \(X\).

**Theorem 18**.: _If \(\mathcal{C}\) can universally approximate any continuous \(\mathfrak{G}\)-invariant functions on \(Y\), then \(\mathcal{C}\) is also pairwise \(Y_{\mathfrak{G}}\) discriminating._

With the additional assumption that \(X=Y\), we can also prove the converse.

**Theorem 19**.: _If \(\mathcal{C}\), a class of functions over \(Y\), is pairwise \(Y_{\mathfrak{G}}\) discriminating, then \(\mathcal{C}^{+2}\) can also universally approximate any continuous function over \(Y\)._

We now produce an estimate for the number of aggregators needed to learn _continuous_ orbit-space injective functions on a manifold \(X\) based on results from differential geometry [46]. A group \(\mathfrak{G}\) acts freely on \(X\) if \(\mathfrak{g}x=x\) implies \(\mathfrak{g}=e_{\mathfrak{G}}\), where \(e_{\mathfrak{G}}\) is the identity element in \(\mathfrak{G}\).

**Theorem 20**.: _Let \(X\) be a smooth \(n\)-dim manifold and \(\mathfrak{G}\) an \(m\)-dim compact Lie group acting continuously on \(X\). Suppose there exists a smooth submanifold \(Y\) of \(X\) of the same dimension such that \(\mathfrak{G}\) acts freely on it. Then, any \(\mathfrak{G}\)-orbit injective function \(f:X\to\mathbb{R}^{d}\) requires that \(d\geq n-m\)
We now apply this theorem to the local aggregation operation performed by geometric GNNs. Let \(X=\mathbb{R}^{n\times d}\) and \(\mathfrak{G}=S_{n}\times O(d)\) or \(S_{n}\times SO(d)\). Let \(\mathbf{P}_{\mathfrak{g}}\) and \(\mathbf{Q}_{\mathfrak{g}}\) be the permutation matrix and the orthogonal matrix associated with the group element \(\mathfrak{g}\in\mathfrak{G}\). Then \(\mathfrak{g}\) acts on matrices \(\mathbf{X}\in X\) continuously via \(\mathbf{P}_{\mathfrak{g}}\mathbf{X}\mathbf{Q}_{\mathfrak{g}}^{\top}\). Then, \(\mathfrak{G}\) orbit-space injective functions on \(X\) are functions on point clouds of size \(n\) that can distinguish any two different point clouds.

**Theorem 21**.: _For \(n\geq d-1>0\) or \(n=d=1\), any continuous \(S_{n}\times SO(d)\) orbit-space injective function \(f:\mathbb{R}^{n\times d}\to\mathbb{R}^{q}\) requires that \(q\geq nd-d(d-1)/2\)._

We can also generalise this to \(O(d)\), with the slightly stronger assumption that \(n\geq d\).

**Theorem 22**.: _For \(n\geq d>0\), any continuous \(S_{n}\times O(d)\) orbit-space injective function \(f:\mathbb{R}^{n\times d}\to\mathbb{R}^{q}\) requires that \(q\geq nd-d(d-1)/2\)._

Overall, these results show that when working with point clouds in \(\mathbb{R}^{3}\) as is common in molecular or physical applications, at least \(q=3(n-1)\) aggregators are required. This result argues why a bigger representational width can help distinguish neighbourhoods. Finally, in the particular case of the zero-dimensional subgroup \(S_{n}\times\{e_{\text{SO(d)}}\}\simeq S_{n}\) we obtain a statement holding for all \(n\) and generalising a result from Corso et al. [47] regarding the aggregators for non-geometric GNNs. The original PNA result considers the case \(d=1\) and here we extend it to arbitrary \(d\).

**Proposition 23**.: _Any \(S_{n}\)-invariant injective function \(f:\mathbb{R}^{n\times d}\to\mathbb{R}^{q}\) requires \(q\geq nd\)._

## 7 Conclusion

We propose the Geometric Weisfeiler-Leman (GWL) framework to characterise the expressive power of geometric GNNs from the perspective of geometric graph isomorphism. Our work fills a key research gap as geometric graphs come with both relational structure and geometric attributes, making theoretical tools for standard GNNs inapplicable in this increasingly relevant real-world setting.

We demonstrate the utility of GWL for understanding how key design choices influence geometric GNN expressivity, summarised in Figure 1. Most notably, we formalise the advantages of equivariant GNNs over invariant GNNs, as equivariant layers can distinguish a larger class of graphs by propagating geometric information beyond local neighbourhoods. Invariant layers have limited expressivity as they cannot distinguish graphs where one-hop neighbourhoods are the same, nor compute non-local geometric properties. Additionally, we highlight the need for higher order order tensors and scalarisation in geometric GNNs.

Future Work.GWL provides an abstraction to study the theoretical limits of geometric GNNs. In practice, it is challenging to build provably powerful models that satisfy the conditions of Proposition 2, as GWL relies on perfect neighbourhood aggregation and colouring functions. Based on the understanding gained from GWL, future work will explore building maximally powerful, _practical_ geometric GNNs for applications in biochemistry and material science.

## Acknowledgements

We would like to thank Andrew Blake, Challenger Mishra, Charles Harris, David Kovacs, Erik Thiede, Gabor Csanyi, Hannes Stark, Ilyes Batatia, Iulia Duta, Justin Tan, Mario Geiger, Petar Velickovic, Ramon Vinas, Rob Hesselink, Soledad Villar, Weihua Hu, and the anonymous reviewers for helpful comments and discussions. CKJ was supported by the A*STAR Singapore National Science Scholarship (PhD). SVM was supported by the UKRI Centre for Doctoral Training in Application of Artificial Intelligence to the study of Environmental Risks (EP/S022961/1).
