Year: 2021

Abstract:
Exploiting symmetries and invariance in data is a powerful, yet not fully exploited, way to achieve better generalisation with more efficiency. In this paper, we introduce two graph network architectures that are equivariant to several types of transformations affecting the node coordinates. First, we build equivariance to any transformation in the coordinate embeddings that preserves the distance between neighbouring nodes, allowing for equivariance to the Euclidean group. Then, we introduce angle attributes to build equivariance to any angle preserving transformation thus, to the conformal group. Thanks to their equivariance properties, the proposed models can be vastly more data efficient with respect to classical graph architectures, intrinsically equipped with a better inductive bias and better at generalising. We demonstrate these capabilities on a synthetic dataset composed of n-dimensional geometric objects. Additionally, we provide examples of their limitations when (the right) symmetries are not present in the data.

heading: 1 INTRODUCTION
text: Symmetries exist throughout nature. All the fundamental laws of physics are built upon the framework of symmetries, from the gauge groups describing the Standard Model of particle physics, to Einstein’s theories of general and special relativity. Once one understands the symmetry of a certain system, powerful predictions can be made. A notable example is that of Gell-Mann’s eightfoldway (Gell-Mann, 1961), built upon the symmetries observed in hadrons, that led to his prediction of the Ω− baryon, which was subsequently observed 3 years later (Barnes et al., 1964). The study of symmetries and invariance in deep learning has recently become a field of interest to the community (see, e.g., (Bronstein et al., 2021) for a comprehensive overview), and rapid progress has been made in constructing architectures with group theoretic structures embedded within. Two fundamental architectures in machine learning, the convolutional and graph neural networks, are invariant to the translation and permutation groups respectively.
Graph networks in particular are designed to learn from graph-structured data and are by construction invariant to permutations of the input nodes. They were originally proposed in (Gori et al., 2005; Scarselli et al., 2008) and have received a lot of attention in the last years (see, e.g., (Battaglia et al., 2018; Hamilton, 2020; Wu et al., 2020) for a comprehensive overview). Due to their properties, they find application in a broad range of problems like learning the dynamics of complex physical systems (Sanchez-Gonzalez et al., 2020; Pfaff et al., 2021), particle identification in particle physics (Dreyer & Qu, 2021), learning causal and relational graphs (Kipf et al., 2018; Li et al., 2020), discovering symbolic models (Cranmer et al., 2020), as well as quantum chemistry (Gilmer et al., 2017) and drug discovery (Stokes et al., 2020).
In this work, we decouple node coordinates from other node attributes to obtain invariance (and possibly equivariance) to many transformations affecting the node coordinates, possibly belonging to important groups, in addition to permutation invariance. First, we define the distance preserving graph network (DGN) whose updated node, edge and global attributes are invariant to any transformation in the coordinate embeddings that preserves the distance between neighbouring nodes, while node coordinates can be updated in an equivariant way. Examples of such transformations are rotations and translations, but also transformations on the Hoberman sphere, whose 3D shape changes while preserving distances between connected nodes. Equivariance to dilations in the coordinates can be obtained via the conformal orthogonal group with the inclusion of an additional input layer. Then, we define the angle preserving graph network (AGN), whose updated node, edge and global attributes (resp. node coordinates) are invariant (resp. equivariant) to any transformation preserving
the angles between triples of neighbouring nodes in the graph (a notable example being molecular conformations) and, thus, to the n-dimensional conformal group on Rn.
By constructing such architectures, we enable a wide range of possible transformations to be performed on graph-structured data, with the only requirement being that distances or angles between coordinates of neighbouring nodes are preserved. This means that the updated attributes/coordinates of both networks are invariant/equivariant to translations, rotations, reflections (i.e., the Euclidean group, E(n)), with the AGN allowing also invariance/equivariance to dilations, inversions and nonorthogonal rotations. In practice, this means the networks are able to filter out many copies of the same input whose coordinate embeddings have been transformed and therefore learn more efficiently than architectures which consider the inputs as distinct. In other words, a single sample contains the same information as many copies of it obtained by appropriately transforming it.
Finally, while the two architectures we present are partially overlapping in terms of symmetries, it is important to consider specific use cases where the use of one architecture over another would be preferred. We test the architectures on a synthetic dataset consisting of n-dimensional geometric shapes and other benchmark datasets. Moreover, we show examples of cases in which using our architectures is counterproductive due to the lack of symmetries in the data.

heading: 2 BACKGROUND

heading: 2.1 GROUP THEORY AND EQUIVARIANCE
text: Group theory provides the mathematical formulation for symmetries of systems, with symmetry operations represented by individual group elements. A group can be defined as a set G equipped with a binary operation, which enables one to combine two group elements to form a third, whilst preserving the group axioms (associativity, identity, closure and inverse). A function unaffected by a group action is said to be invariant, which is particular instance of equivariance. Formally, let X ⊆ Rn and ϕg : X → X be a transformation on X for a group element g ∈ G. Then, the linear map Φ : X → Y , Y ⊆ Rn, is equivariant to G if ∀g ∈ G, ∃ϕ′g : Y → Y such that
Φ(ϕg(x)) = ϕ ′ g(Φ(x)) , ∀ϕg : X → X .
When ϕ′g is the identity, we say that Φ is invariant to G. The functional form of Φ is determined by the specific group of interest. It is worth pointing out that, whilst not often expressed in group theoretic notation, equivariance exists in common deep learning architectures; the convolution operation used in CNNs is equivariant under the translation group and approximate invariance is typically achieved via pooling operations. Graph neural networks are invariant to the permutation group.
Euclidean group The translation and orthogonal groups (T (n) andO(n) respectively) act through translations, orthogonal rotations and reflections. The semidirect product of these two groups E(n) = T (n) o O(n) is known as the Euclidean group, which consists of transformations that preserves distances. A function that is invariant under E(n) is ‖xi−xj‖22, for any xi,xj ∈ En (see Appendix A for a proof).
Conformal group The conformal group Conf(Rn,0) is the group of transformations ϕ : Rn → Rn that preserve angles. Formally, for any triple of vectors xj ,xi,xk ∈ Rn, let us denote by ∠(xj ,xi,xk) the angle centred on xi with rays given by xj − xi and xk − xi. Then, a conformal transformation ϕ satisfies
∠(xj ,xi,xk)→ ∠(ϕ(xj), ϕ(xi), ϕ(xk)) = ∠(xj ,xi,xk) . (1) By definition, the transformations of the conformal group include translations, rotations, reflections (which collectively form the Euclidean group E(n), as well as dilations, inversions and other features. An important subgroup is the conformal orthogonal group, which requires transformations to be orthogonal (and thus, inversions are not allowed).

heading: 2.2 GRAPHS AND COORDINATE EMBEDDINGS
text: A graph is defined as G(V, E) where V = {1, . . . , N} is the set of nodes and E = {(j, i)} ⊆ V × V is the set of (directed) edges connecting nodes in V (where j and i denote the source and target nodes
respectively). We define Ni , {j | (j, i) ∈ E} as the set of (in-)neighbours of node i. Moreover, we associate node and edge features, vi ∈ Rnv , ∀i ∈ V , and eji ∈ Rne , ∀(j, i) ∈ E respectively, to each node and edge in the graph as well as a global attribute u ∈ Rnu . We assume that node features vi consist of node coordinates xi ∈ Rnx and additional features hi ∈ Rnh (unrelated to coordinates), so that vi = [xi,hi], nv = nx + nh. With a slight abuse of notation, we denote GX(V, E) and GY (V, E) as different coordinate embeddings of the same graph, meaning that they differ only in their node coordinates xi, while having the same node, edge and global attributes hi, eji and u. Finally, let A ∈ V ×V ×V be the set of (ordered) triples of nodes in a graph G that form an angle, i.e., A , {(j, i, k) | j, k ∈ N ui , j 6= k, ∀i ∈ V} with N ui , {j | (j, i) ∈ E ∨ (i, j) ∈ E} being the set of in- and out-neighbors of node i.
We define relative distance and angle preserving maps as follows (see Figure 1).
Definition. Let GX(V, E) and GY (V, E) be such that ‖xi − xj‖2 = ‖yi − yj‖2, ∀(i, j) ∈ E . Let x+i = ψ(i,GX) and y+i = ψ(i,GY ) for some function ψ : RK → Rn, K ∈ Z+. We say that ψ is a relative distance preserving map if ‖x+i − x+j ‖2 = ‖y+i − y+j ‖2, ∀(i, j) ∈ E . Definition. Let GX(V, E) and GY (V, E) be such that ∠(xj ,xi,xk) = ∠(yj ,yi,yk) ∀(j, i, k) ∈ A. Let x+i = ψ(i,GX) and y+i = ψ(i,GY ) for some function ψ : RK → Rn, K ∈ Z+. We say that ψ is a relative angle preserving map if ∠(x+j ,x + i ,x + k ) = ∠(y + j ,y + i ,y + k ), ∀(j, i, k) ∈ A.
The simplest map satisfying the above definitions is the identity function
x+i = ψ(i,GX) = xi (2)
which keeps the coordinates unchanged during the update step. Updating all the coordinates in the same way also trivially preserves both relative distances and angles. In the case where the coordinate embedding X is a Conformal orthogonal transformation of Y a possible map ψ is defined by
x+i = xi + ∑ j∈Ni aji(xj − xi). (3)
with aji possibly being a parametric function of other graph attributes. A thorough discussion and proofs are reported in in Appendix C.

heading: 3 EQUIVARIANT GRAPH NETWORKS
text: We start this section by recalling the structure of a standard graph network block. Then, we introduce two novel architectures with additional invariance and equivariance properties with respect to different node coordinate embeddings. We stress that while we build our discussion upon equivariance with respect to node coordinates (since there is, in general, no sense of equivariance of the network’s node or edge embeddings), there may be cases in which our discussion can be extended to node or edge embeddings.

heading: 3.1 THE STARTING POINT - GRAPH NETWORK BLOCK (GN)
text: A general standard graph network block can be defined in terms of edge, node and global updates as
e+ji = φ e ( vj ,vi, eji,u ) , ∀(j, i) ∈ E (4a)
v+i = φ v ( vi, ρ e→v({e+ji}j∈Ni),u), ∀i ∈ V (4b) u+ = φu ( ρv→u({v+i }i∈V), ρe→u({e+ji}(j,i)∈E),u ) (4c)
where φe : R2nv+ne+nu → Rn+e , φv : Rnv+n+e +nu → Rn+v , φu : Rn+v +n+e +nu → Rn+u are update functions (usually defined as neural networks whose parameters are to be learned) and ρe→v, ρe→u, ρv→u are aggregation functions reducing a set of elements of variable length to a single one via an input’s permutation equivariant operation like element-wise summation or mean.

heading: 3.2 DISTANCE PRESERVING GRAPH NETWORK BLOCK (DGN)
text: By decoupling the updates of node coordinates and features (xi and hi), the DGN block is defined through the following updates
e+ji = φ e ( eji,hi,hj , ‖xi − xj‖22,u ) , ∀(j, i) ∈ E (5a)
h+i = φ h ( ρe→h ( {e+ji}j∈Ni ) ,hi,u ) , ∀i ∈ V (5b)
x+i = ψ x (i,GX) , ∀i ∈ V (5c) u+ = φu ( ρe→u({e+ji}(j,i)∈E), ρh→u({h+i }i∈V), ρx→u({‖x+i − x+j ‖22}(j,i)∈E),u ) (5d)
where φe : Rne+2nh+nu+1 → Rn+e , φh : Rn+e +nh+nu → Rn+h , φu : Rn+e +n+h+nu+1 → Rn+u are the update functions, ρe→h, ρe→u, ρh→u are aggregation functions and ψx : RK → Rnx , K ∈ Z+ is some, possibly parametric, relative distance preserving map.
Because of the way in which node coordinates are processed to update edge and global embeddings (i.e., only through their relative distances), it can be easily seen that e+ji, h + i and u
+ are, by construction, invariant to any transformation of the input coordinates that locally maintains their relative distances along the edges defined by the graph structure (a notable example being the one of Euclidean transformations; see Appendix D for a proof). Moreover, updated node coordinates x+i can be invariant or equivariant to (some of) those transformations, depending on the particular structure of ψx. For example, using equation 3 or the trivial identity function (equation 2) would result in coordinates being updated in an equivariant way with respect to Euclidean transformations, with aji possibly being parametric functions (e.g., aji = φx(eji)).

heading: 3.3 ANGLE PRESERVING GRAPH NETWORK BLOCK (AGN)
text: Given a graph G(V, E), let αjik ∈ Rnα be the angle embedding associated to each angle (j, i, k) ∈ A and assume that αjik contain no information about the angles ∠(xj ,xi,xk). Moreover, defineAi
as the set of (ordered) couples of nodes forming an angle whose vertex is node i, i.e., Ai , {(j, k) | (j, y, k) ∈ A, y = i}. Then, the AGN block is then characterised by the following updates α+jik = φ
α(hi,hj ,hk,αjik,∠(xj ,xi,xk),u), ∀(j, i, k) ∈ A (6a) e+ji = φ e ( hj ,hi, eji,u ) , ∀(j, i) ∈ E (6b)
h+i = φ h ( hi, ρ e→h({e+ji}j∈Ni), ρα→h({α+jik}(j,k)∈Ai),u), ∀i ∈ V (6c) x+i = ψ
x(i,GX), ∀i ∈ V (6d) u+ = φu ( ρh→u({h+i }i∈V), ρe→u({e+ji}(j,i)∈E), ρα→u ( {α+jik}(j,i,k)∈A ) ,u ) (6e)
where φα, φe, φh, ψx, φu are the update functions1, and ρe→h, ρα→h, ρh→u, ρe→u, ρα→u are the aggregation functions, with ψx being a (possibly parametric) relative angle preserving map. Variants of this network that still preserve its properties can be easily constructed by, e.g., using edge embeddings to update the angle embeddings, using angles to update edges or not considering angle attributes at all. Some examples are reported in Appendix F.1. It can be easily seen that α+jik, e + ji,h + i ,u
+ are invariant to any transformation of the coordinate embeddings that preserves the angles created by neighbouring nodes in the graph, while updated coordinates x+i can be invariant or equivariant to (some of) the same transformations, depending on the structure of ψx. As with the DGN, equivariance to the conformal orthogonal group can be achieved by using equation 3. A particular case of transformations the AGN can deal with is the one of conformal transfomations (see Appendix E for a formal discussion).

heading: 4 DISCUSSION
text: In the previous section we introduced two novel graph architectures. To construct them we have mainly built upon the actions on a coordinate system of two transformations that preserves distances and angles between neighbouring nodes in a graph. These transformations include as particular cases those in the Euclidean and conformal groups. Equivariance under E(n) means equivariance to orthogonal rotations and translations, while by considering the full conformal group, we can further generalise our neural network architecture. Conformal n-dimensional transformations consist of the groups containing translations, dilations, rotations and inversions with respect to an n − 1 sphere. A conformal transformation is therefore a powerful tool for mapping data points onto each other, and hence, building a neural network architecture invariant to the conformal group enables the architecture to be invariant to a wide selection of interesting subgroups. By introducing distance and angle preserving transformations that take into account the structure of the graph, invariance and equivariance under more general transformations have been achieved. A notable example is that the DGN architecture, whose updates are invariant to any transformation of a Hoberman sphere, while both the DGN and AGN can be invariant to transformations affecting only subsets of their nodes, as shown below.
In summary, by taking advantage of the powerful tools of group theory, and performing operations on a vector space which are invariant or equivariant under group transformations, we can build a neural network architecture which can take advantage of these group properties. Such an architecture will be able to deal with rotated, translated, dilated (or more generally transformed) data more efficiently than a standard graph network which does not have the above group properties built into it.

heading: 4.1 BEYOND GLOBAL TRANSFORMATIONS
text: So far, we have talked about global transformations in the coordinate space. In general, a global symmetry ϕg , as defined in Section 2.1 acts on a function ψ(x) as
ψ(x)→ ϕgψ(x) . (7) A local group symmetry ϕl(x) is instead defined as
ψ(x)→ ϕl(x)ψ(x) , (8) 1The update functions in equation 6 live in the function spaces φα : R3nh+nα+1+nu → Rn + α , φe :
R2nh+ne+nu → Rn + e , φh : Rnh+n + e +n + α+nu → Rn + h , ψx : RK → Rnx , for an appropriate K ∈ Z+ depending on the actual number of parameters, and φu : Rn + h +n+e +n + α+nu → Rn + u .
where now the group action can differ at all points.
The architectures we present are also able to deal with some local symmetries. Namely, the DGN and AGN preserve local distances and angles respectively where a suitable subgraph must be defined. As an example consider a transformation that rotates only some nodes of a graph; all nodes which are in the neighbourhoods of the nodes will, in the angular architecture, have their angles preserved, and in the distance-preserving architecture, the distances between nodes will be preserved. A pertinent use-case for such a symmetry is that of molecular conformations, where the spatial arrangement of the atoms can be interconverted by rotations about formally single bonds). Both the DGN and the AGN updates would be invariant to such a transformation at the level of the two distinct subgraphs separated by the bond in question, thus enabling one to learn conformation-invariant properties.

heading: 4.2 COMPARING AND EXTENDING THE TWO ARCHITECTURES
text: As mentioned, the two architectures we presented are partially overlapping in terms of equivariance features. Whilst both of them contain invariance to E(n), the DGN can deal with non-orthogonal transformations that preserve the distance between neighbouring nodes (such as with the Hoberman sphere) while the AGN is invariant to the conformal group which includes non-orthogonal transformations that preserve angles but not distances (see Figure 3).
The DGN can be equipped with a sense of scale invariance through an input scaling layer that makes it invariant to the conformal orthogonal group. Let γ = α/max(i,j)∈E ‖xi − xj‖ for some α ∈ R, where we identify γ as satisfying the dilation condition required under the conformal orthogonal group. Then, conformal orthogonal invariance can simply be obtained by computing scalenormalised coordinates x̃i = γxi and using them as the coordinates in equation 5.
Introducing coordinate scaling therefore enables the DGN to be scale invariant, under the condition that all transformations remain orthogonal. With the AGN, we can relax this condition and be invariant under the full conformal group. This larger group invariance enables us to work with very powerful transformations on data, which can also be dangerous. For example, if the scale is an important property of the dataset, the AGN will not recognise it and so will learn incorrect information about the data. Similarly, one must also not use the DGN blindly and irrespective of the properties of the dataset; as the architecture is invariant to transformations that preserve distance between neighbouring nodes but not angles it is able to, for example, map a square onto a line. The two architectures we presented can be also combined together at the price of losing some features, while generalising to both distance and angle preserving transformations.

heading: 5 RELATED WORK
text: The study and formulation of group equivariant neural networks have flourished in the last years and they have proven to be extremely powerful in many tasks. The first example is probably that of convolutional neural networks (LeCun et al., 1990), which explots translation equivariance and invariance, thanks to the convolution and pooling operations respectively, and have led to breakthroughs in most vision tasks. CNNs have been generalised to exploit larger groups of symmetries. G-CNNs are proposed in (Cohen & Welling, 2016) to deal with more general symmetries, including rotations and translations, and extended in (Bekkers, 2020; Finzi et al., 2020) to deal with Lie groups. Equivariance to arbitrary symmetry groups can be achieved via self-attention mechanisms in (Romero & Cordonnier, 2021). Continuous convolutions are used in SchNet (Schütt et al., 2017)
to achieve E(n) invariance, and SE(3) equivariance is achieved in Thomas et al. (2018) via the use of spherical harmonics. The drawback of many of these methods is their limited applicability due to computational complexity.
There has been some work on constructing general MLPs that are equivariant to different groups; a layer equivariant to general matrix groups is presented in Finzi et al. (2021), whilst equivariance to the Lorentz group for physics applications has recently been explored (Bogatskiy et al., 2020). Further applications include (Mattheakis et al., 2019), where physical symmetries are embedded in neural networks via embedding physical constraints in the structure of the network, and in (Barenboim et al., 2021) where the ability of neural networks to discover and learn symmetries in data is explored.
Graph neural networks are, by construction, permutation invariant (Scarselli et al., 2008; Battaglia et al., 2018). Recently, there has been a lot of work on building equivariance to other interesting groups in GNNs. There has been particular interest in the Euclidean group with results for the subgroups SE(3) and E(3) obtained in (Thomas et al., 2018; Fuchs et al., 2020; Köhler et al., 2020; Finzi et al., 2020; Batzner et al., 2021; Yang et al., 2020). Extending these architectures, a messagepassing convolutional graph layer is proposed in (Satorras et al., 2021) which implements E(n) invariance for edge and node features and equivariance for node coordinates, leading to state of the art results in a variety of tasks, including n-body particle systems simulations and molecular property predictions. A similar idea has been also proposed in (Farina & Slade, 2021), where a general E(n) equivariant GNN is presented, and in (Horie et al., 2021), in which equivariance to isometric transformations is considered. These E(n) equivariant networks can be seen as special instances of our DGN architecture, where particular aggregation functions are applied and a particular choice is made for the distance preserving map ψx (see Appendix G). In (Satorras et al., 2021), for example, the map ψx is chosen so that relative distances between all possible pairs of node in the graph are preserved, thus allowing only for rigid transformations in E(n).
Angular information is used in (Smith et al., 2017) but no attention is explicitly paid to equivariance. DimeNET is proposed in (Klicpera et al., 2020), where both distance and angle embeddings computed through embeddings in novel orthogonal basis functions are used in a message passing graph network to achieve equivariance. State of the art results are obtained on molecular property and dynamics prediction datasets. We note, however, that while DimeNET produces state of the art results, it is restricted to atomic data, due to the requirement of Gaussian radial and Bessel functions as the basis representations. Additionally, angular embeddings computed in the isometric invariant layer in (Horie et al., 2021) corresponds to the extraction of both relative distances and angles of each pair of vertices. Again, these approaches are special instances of our networks where particular aggregation and learnable functions or hand engineered distance and/or angle embeddings are used (see Appendix G). In this sense, our network is unconstrained and can learn what it needs. Moreover, thanks to its general form it can achieve invariance to the conformal group (and more) which, to the best of our knowledge, does not hold for known architectures.
In summary, most of the existing equivariant graph architectures are at most equivariant to the Euclidean group (represented as the intersection set in Figure 3), whilst the architectures we propose allow, in their general form, more general transformations.

heading: 6 EXPERIMENTAL RESULTS
text: In this section we give an insight into the performance of the architectures we proposed and on their limitations. First, we demonstrate that perfect generalisation to unseen data can be achieved on datasets with a large number of symmetries, possibly accompanied by a faster convergence rate (as shown for QM9 in Appendix H.4). Then, we show that, when used on datasets with few symmetries, using our architectures can be counterproductive. In general, when the right symmetries are present, equivariant architectures experience both increased accuracy and convergence speed, as demonstrated by state of the art results obtained on a number of tasks by architectures that can be obtained as particular instances of the ones proposed here. Examples include n-body system dynamics prediction, molecular dynamics and molecular property prediction tasks (Satorras et al., 2021; Klicpera et al., 2020; Horie et al., 2021).

heading: 6.1 POLYTOPES CLASSIFICATION
text: We consider a n-dimensional polytopes classification problems for n = 3, 4, 5. The datasets are composed of graph representations of regular polytopes and the number of classes varies with n. Simplexes, hypercubes and orthoplexes are considered for all values of n. For n = 3 also dodecahedra and icosahedra are added, while for n = 4 we consider 24−, 120− and 600− cell polytopes. Additional results are reported in Appendix H.2. The training dataset consists of a single graph per polytope where the graph is specified in terms of node coordinates xi (so that the resulting polytope is inscribed in a hypersphere of radius 1) and list of edges E (and possibly angles A); node, edge and possible angle attributes (hi, eji,αjik) are fixed to be equal to 0 for every node in the graph. This makes the problem intrinsically harder since only coordinates can be used to discern between polytopes. The test set is composed of randomly transformed versions of those in the training set, whose coordinates are obtained as x̃i = γAxi + q for some γ ∈ R, A ∈ Rn×n and q ∈ Rn. Note that, while even a standard GN could learn to correctly classify transformed polytopes, a much larger training dataset is needed in order to do so, as shown in Appendix H.
We compare graph networks built with AGN, DGN and standard (GN) blocks, as well as EGNN (Satorras et al., 2021), DimeNET (Klicpera et al., 2020) and SE3-Transformer (Fuchs et al., 2020), the latter only for n = 3. The DGN block is also combined with a scaling layer (SDGN) as in Section 4.2 to obtain equivariance to dilations. Architectures based on AGN, DGN and GN blocks employ sum aggregation functions ρ and ψx set to equation 3 (other cases are considered in the appendix). Results are reported in Table 1.
We note that all models reach a perfect accuracy on the training set. As for the test accuracy, results vary across the different models, in line with what one expects from their invariance properties. The standard GN cannot generalise to any type of transformation. When only orthogonal transformations are performed in the test set (i.e., A>A = I , γ = 1) all models (except GN) perfectly generalise to unseen data. However, as expected, when also adding dilations (i.e., A>A = γI , γ ∈ R), only AGN and SDGN (and the SE3-Transformer for n = 3) can generalise well. Finally, when adding random non-orthogonal transformations (i.e., µ = E[‖A>A− I‖F ] > 0, γ ∈ R), something possibly unexpected occurs. The AGN (and partially also the SDGN and the SE3-Transformer for n = 3) perfectly generalises to unseen polytopes whose neither angles nor edge lengths have been preserved (due to the non-orthogonality of A). This is probably due to the networks having learnt to distinguish polytopes based on the sum (or mean) of their angles which is preserved under nonorthogonal transformations due to the Gram–Euler theorem. While this behaviour turns out to be useful in the task at hand, one can easily envisage cases in which it may cause issues.

heading: 6.2 BENCHMARK DATASETS
text: Now we consider benchmark datasets from (Dwivedi et al., 2020) for which node coordinates are provided. In particular, we consider MNIST, CIFAR10 as graph classification problems and TSP as an edge classification one. When treated as images, MNIST and CIFAR10 are usually examples of datasets containing symmetries. However, when represented as graphs as in (Dwivedi et al., 2020),
those symmetries are mostly lost. This is due to, for example, the fact that both the foreground and the background of the images are embedded in the graphs. Furthermore, in TSP there are no apparent symmetries. In these cases, as one may expect, using an equivariant network would not produce any benefits. Rather, as we show, negative effects can appear.
We trained our models and a standard GNN on these datasets. All models have roughly the same number of parameters and the results are reported in Table 2. As can be seen, treating node coordinates as if they can posses some symmetric between among different samples turns out to be counterproductive both in terms of convergence speed and accuracy. In particular we see that while the standard GN has the best performance, the DGN is slightly better than the AGN. This is probably due to the fact that, while some non-orthogonal transformations mostly preserving local distances may be present in the dataset, angle preserving ones are much more rare. On TSP in particular, using angle related properties results in a significant drop in performance.

heading: 6.2.1 COMPUTATIONAL COMPLEXITY
text: All the experiments have been run on an NVIDIA V100 GPU. The average time required for each training step (i.e., forward pass, back-propagation and optimiser step for a batch of data) is reported in Table 3 for the architectures presented in this paper, normalised with respect to the batch-size. For the polytopes classification experiment we report the results obtained by using equation 2 and equation 3 (in parentheses). Using the scaling layer for the DGN drastically increase the computational complexity. Moreover, it can be seen that while the AGN and DGN have similar complexities for dataset in which the number of edges (and hence angles) is relatively low, when graphs are (nearly) complete (like in TSP) or highly connected, the AGN has an overhead with respect to the DGN (due to the need of updated and computing angles in addition to edges).

heading: 7 CONCLUSION
text: In this paper we have presented novel deep learning architectures which are equivariant to distance and angle preserving transformations in graph coordinate embeddings. In particular, we have shown invariance or equivariance to the E(n), CO(Rn,Q) and Conf(Rn,0) groups in addition to permutation invariance. Invariance to local symmetries can also be achieved when the different transformations are applied to suitable subgraphs. We have applied our models to a synthetic dataset composed of n-dimensional regular polytopes as well as to several benchmark datasets. We have shown that the architectures we propose are significantly more accurate and data efficient than a standard graph network on datasets where there are large numbers of symmetries in the data. We also explicitly show examples where our architecture produces unexpected results or would not be applicable, due to a lack of symmetry in the data.

heading: C RELATIVE DISTANCE AND ANGLE PRESERVING MAPS
text: Many different relative distance and/or angle preserving maps to be used in the coordinate update can be obtained in different ways, eventually requiring further assumptions on the data.
The simplest one is the identity function
x+i = ψ(i,GX) = xi (12) which keeps the coordinates unchanged during the update step. In this case both relative distances and angles are trivially preserved. Updating all the coordinates in the same way also trivially preserves both relative distances and angles. Examples include
x+i = axi, a ∈ R, (13) x+i = xi + a, a ∈ Rnx (14) x+i = Qxi + a, Q ∈ Rnx×nx , Q>Q = I,a ∈ Rnx (15)
where a,a, Q can be learnable parameters or parametric functions of other network parameters, e.g., a = φx(u). The matrix Q can also be non orthogonal, provided that the obtained transformation preserves distances or angles.
Devising more complex forms for ψ for arbitrary coordinate embeddingsX , Y satisfying the relative distance or angle preserving property, is quite tricky and further assumptions are in general required. To see this, consider a relative distance preserving transformation. Any transformation X → Y , such that ‖xi − xj‖2 = ‖yi − yj‖2, can be obtained as xi = γiAiyi + qi, where γi, Ai and qi, i ∈ V , are solutions to the system
‖γiAiyi + qi − γjAjyj + qj‖2 = ‖yi − yj‖2, (i, j) ∈ E .
with γi ∈ R, A>i Ai = I , qi ∈ Rnn , ∀i ∈ V . In this general case, defining a (non trivial) map ψ such that, after its application, one has ‖x+i − x+j ‖2 = ‖y+i − y+j ‖2∀(i, j) ∈ E is hard without any assumption on, at least, the topology of the graph GX (or, equivalently GY ). A similar reasoning can be applied also to relative angle preserving maps.
If we restrict ourselves to the case in which γi = γ, Ai = A, qi = q, ∀i ∈ V , this results inX being a Conformal orthogonal transformation of Y . In this case, a possible map ψ is defined by
x+i = xi + ∑ j∈Ni aji(xj − xi). (16)
with aji possibly being a parametric function of node/edge/angle/global attributes, e.g., aji = φx ( e+ji,v + j ,v + i ,u ) . Notice that, under conformal orthogonal transformations (hence also E(n) transformations) yi = ϕg(x) = Ax + b, AA> = I , one has that equation 16 is an equivariant map.
In fact,
y+i = yi + ∑ j∈Ni aji(yj − yi)
= γAxi + b+ ∑ j∈Ni aji(γAxi + b− γAxj + b)
= γA xi + ∑ j∈Ni aji(xi − xj) + b = γAx+i + b
Thus, when this map is used as ψx in the DGN or AGN block, node coordinates can be updated in an equivariant way with respect to conformal orthogonal transformations. Using the same argument, it is easy to show that equation 13 is also equivariant, but equation 14 is not.
Now we show that equation 16 is both relative distance and angle preserving. For the sake of notation, we assume γ = 1, however the same arguments can be applied when γ 6= 1.
Relative distance preservation of equation 16 To show that equation 16 satisfies the definition of a distance-preserving map it is sufficient to show that, since xi = Ayi + q, one has
x+i = xi + ∑ j∈Ni aij(xj − xi)
= Ayi + q + ∑ j∈Ni aij(Axj + q−Axi − q)
= Ayi + q + ∑ j∈Ni aij(Axj −Axi)
= A yi + ∑ j∈Ni aij(xj − xi) + q = Ay+i + q (17)
which implies
‖x+i − x+j ‖2 = ‖Ay+i + q−Ay+j − q‖2
= ‖A(y+i − y+j )‖2 = (y+i − y+j )>A>A(y+i − y+j ) = ‖y+i − y+j ‖2
where in the last line we used the fact that A>A = I .
Relative angle preservation of equation 16 While equation 17 implies that angles are preserved since xi is an E(n) transformation of yi, one can show this explicitly by recalling that the angle between two vectors xj − xi and xk − xi can be computed as
cos∠(xj ,xi,xk) = (xj − xi)>(xk − xi) ‖xj − xi‖‖xk − xi‖
Then, one has
(x+j − x+i )>(x+k − x+i ) ‖x+j − x+i ‖‖x+k − x+i ‖ = (Ay+j + q−Ay+i − q)>(Ay+k + q−Ay+i − q) ‖Ay+j + q−Ay+i − q‖‖Ay+k + q−Ay+i − q‖
= (Ay+j −Ay+i )>(Ay+k −Ay+i ) ‖Ay+j −Ay+i ‖‖Ay+k −Ay+i ‖ = (y+j − y+i )>A>A(y+k − y+i )√
(y+j − y+i )>A>A(y+j − y+i ) √ (y+k − y+i )>A>A(y+k − y+i )
= (y+j − y+i )>(y+k − y+i ) ‖y+j − y+i ‖‖y+k − y+i ‖
where in the last line we used the fact that A>A = I .
Local symmetry transformation of equation 16 Suppose we have a local symmetry transformation, A(x̃) which only acts on a subgraph G̃ ∈ G, such that v = (ṽ1, ṽ2, . . . ṽn,vn+1, . . .vm), and similarly for the edge, coordinate and angle features. The action of A(x̃) is then
A(x̃)x = (A(x̃)x̃1, A(x̃)x̃2, . . . A(x̃)x̃n, A(x̃)xn+1, . . . A(x̃)xm)
= (A(x̃)x̃1, A(x̃)x̃2, . . . A(x̃)x̃n,xn+1, . . .xm) .
By defining the 2 subgraphs as containing the coordinate features which are and are not affected by the symmetry transformation, we can therefore write a coordinate update equation 16 for both subgraphs; Eq. equation 16 for the xi and, for the x̃i,
x̃+i = x̃i + ∑ j∈Ni aji(x̃j − x̃i).
We have shown above that this coordinate update preserves distances and angles for global group transformations; by defining the 2 subgraphs as above, we can promote the local symmetry transformation A(x̃) to global transformations on subgraphs. Whilst here we have shown this for only 2 subgraphs, one can generalise the argument to any number of local transformations so long as the subgraphs are defined as above. As we have to subdivide the graph into subgraphs, we note that these local transformations cannot be defined arbitrarily as there must be a sense of a neighbourhood of nodes within each subgraph. A local transformation which affects unrelated nodes identically (which is a valid class of local symmetry) is not valid for this reason.

heading: D EUCLIDEAN GROUP EQUIVARIANCE OF THE DGN BLOCK
text: To show equivariance toE(n) transformations of the input coordinates for the DGN block, we begin with the edge update in equation 5a. Since ‖xi − xj‖22 is invariant under an E(n) transformation, x 7→ Qx + z, for some rotation matrix Q ∈ O(n) and translation vector z ∈ Rn, then
φe ( eji,vi,vj , ‖xi − xj‖22,u ) → φe ( eji,vi,vj , ‖Qxi + z−Qxj − z‖22,u ) = φe ( eji,vi,vj , ‖xi − xj‖22,u ) .
Invariance of the node and global updates in equation 5 follows naturally as they are composed of invariant quantities. The coordinate update in equation 5c can be invariant or equivariant underE(n) depending on the structure of ψx.

heading: E CONFORMAL GROUP INVARIANCE OF THE AGN BLOCK
text: As discussed in Section 2.1, the conformal group consists of transformations that preserve angles between all possible triples of coordinates (see equation 1). To show that the AGN block is invariant
to conformal transformations it is sufficient to note that given a conformal transformation, ϕ, one has that the angle update equation 6a is invariant to it since
φα(vi,vj ,vk,αjik,∠(xj ,xi,xk),u)→ φα(vi,vj ,vk,αjik,∠(ϕ(xj), ϕ(xi), ϕ(xk)),u) = φα(vi,vj ,vk,αjik,∠(xj ,xi,xk),u) .
Invariance of the other updates is trivially satisfied by construction. The coordinate updates can also be constructed to be equivariant to conformal orthogonal (and hence Euclidean) transformations, with an appropriate choice of ψx. We stress that equivariance to the conformal group includes by definition equivariance to the Euclidean group as we are only concerned with transformations on Rn. The orthogonal rotations and translations of the Euclidean group are therefore a subset of possible conformal transformations on Rn as they are angle-conserving transformations. Angular information can be extremely powerful in tasks where classical (or distance-based) GNNs fail, like in graph isomorphism tests where, e.g., a hexagon is not distinguished from two triangles.

heading: F ADDITIONAL FORMULATIONS

heading: F.1 ALTERNATIVE FORMULATIONS FOR THE ANGLE PRESERVING GRAPH NETWORK
text: A number of variations can be proposed for the angle preserving graph network:
• Edge attributes can be used in angle updates
α+jik = φ α(vi,vj ,vk, eij , eik,αjik,∠(xj ,xi,xk),u), ∀(j, i, k) ∈ A.
• Relative distances can be used in the angle updates
α+jik = φ α(. . . , ‖xi − xj‖22, ‖xi − xk‖22,∠(xj ,xi,xk),u), ∀(j, i, k) ∈ A.
• Angle attributes can be used in edge updates e+ij = φ e ( eij ,vi,vj , ρ α→e({α+ijk}k∈Aij), ρα→e({α+jik}k∈Aji),u), ∀(i, j) ∈ E whereAij = {k | (y, z, k) ∈ A, y = i, z = j} is the set of angles whose first ray is defined by (i, j).
• Angle embeddings can be ignored and node attributes can be updated with the angles themselves
e+ji = φ e ( vj ,vi, eji,u ) , ∀(j, i) ∈ E
v+i = φ v ( vi, ρ e→v({e+ji}j∈Ni), ρα→v({∠(xj ,xi,xk)}(j,k)∈Ai),u), ∀i ∈ V x+i = ψ
x(i,GX), ∀i ∈ V u+ = φu ( ρv→u({v+i }i∈V), ρe→u({e+ji}(j,i)∈E),u ) .

heading: F.2 COMBINED ARCHITECTURE
text: The DGN and AGN architectures can be combined in a single architecture. An example is
α+jik = φ α(vi,vj ,vk,αjik,∠(xj ,xi,xk),u), ∀(j, i, k) ∈ A e+ji = φ e ( vj ,vi, eji, ‖xi − xj‖22,u ) , ∀(j, i) ∈ E
v+i = φ v ( vi, ρ e→v({e+ji}j∈Ni), ρα→v({α+jik}(j,k)∈Ai),u), ∀i ∈ V x+i = ψ
x(i,GX), ∀i ∈ V u+ = φu ( ρv→u({v+i }i∈V), ρe→u({e+ji}(j,i)∈E),u ) where the global update can contain aggregated information about angles and distances and also the other updates can be generalised as shown above. This architecture is by construction equivariant to transformations in the coordinate embeddings for which both relative distances and angles are preserved.

heading: G OBTAINING OTHER ARCHITECTURES AS SPECIAL INSTANCES
text: In this appendix we will represent some of the architectures discussed in the main text explicitly as instances of our architecture.

heading: G.1 DIMENET (KLICPERA ET AL., 2020)
text: Dimenet can be obtained from the AGN by considering edge and distance information in the angle update and using sum aggregation functions as
α+ijk = φ α(eji, ‖xi − xj‖22,∠(xi,xj ,xk)), ∀(j, i, k) ∈ A
e+ji = φ e(eji, ∑ i∈Nj α+ijk), ∀(j, i) ∈ E
x+i = xi, ∀i ∈ V v+i = φ v ( vi, ∑ j∈Ni e+ji ) , ∀i ∈ V
where ‖xi − xj‖22 is defined represented within a set of orthogonal basis functions eRBF and the angles ∠(xi,xj ,xk) within a basis defined as αSBF .

heading: G.2 EGNN (SATORRAS ET AL., 2021)
text: The EGNN network is obtained from the DGN by selecting a specific form for the coordinate update function ψx, using the sum aggregation function as φe→v , and not propagating updated edges, i.e.,
e+ji = φ e ( vj ,vi, e in ji , ‖xi − xj‖22 ) , ∀(j, i) ∈ E ,
x+i = xi + ∑ j 6=i (xi − xj)φx(e+ji), ∀i ∈ V,
v+i = φ v ( vi, ∑ j∈Ni e+ji )
,∀i ∈ V,
where einji are the edge attributes of the input data (implying that e + ji is not propagated to any subsequent layer, as in message passing networks).
G.3 ISOGNN (HORIE ET AL., 2021)
The IsoGNN architecture is defined for tensors of rank-n; to compare with the other architectures presented here, we show below the architecture for rank-1 tensors.
e+ji =  ∑ k,l∈V,k 6=l Tijkl(xk − xl) vj , ∀(j, i) ∈ E x+i = xi, ∀i ∈ V v+i = φ v ( vi,
∑ j∈Ni e+ji ) , ∀i ∈ V
where Tijkl is an untrainable 2-dimensional matrix which is translation and rotation invariant, and determined offline from the data for each class of problem.

heading: G.4 OTHER NETWORKS
text: Standard graph networks can be obtained from ours by skipping some updates or not considering equivariant information. Also other variants, including SchNet (Schütt et al., 2017) or TFN (Thomas et al., 2018), can be cast as message passing architectures as shown in (Satorras et al., 2021).

heading: H ADDITIONAL EXPERIMENTS AND IMPLEMENTATION DETAILS

heading: H.1 COMMON IMPLEMENTATION DETAILS
text: The update functions of the networks are all implemented as MLPs. After the graph layers, the produced node embeddings are passed through another MLP, a global pooling layer and a final MLP with output dimension equal to the number of classes for graph classification tasks. For edge classification tasks (TSP), the architecture after the graph layers is a single MLP taking as input source and target nodes and predicting the class of each edge. Each network is trained starting from 10 different initial conditions. The results in the tables contains the mean and standard deviation resulting from the 10 initialisations.

heading: H.2 POLYTOPES CLASSIFICATION

heading: H.2.1 SPECIFIC IMPLEMENTATION DETAILS
text: All the MLPs have one hidden layer containing 64 neurons and swish activation function. We used 2 graph layers for AGN and DimeNet and 3 for the DGN, GN and EGNN with embeddings in the hidden layers having dimension 32. Aggregation functions and the pooling layer implements mean or sum operations (and are specified in the results’ tables) for our architectures. As for DimeNet, we use distances and angles directly instead of their RBF embeddings since we do not consider atomistic quantities. Adam (Kingma & Ba, 2015) is used to train the all the models with a learning rate α = 0.001 and no regularisation for 1000 epochs. The batch-size is equal to the number of training samples (so 5, 6, 3 respectively, for n = 3, 4, 5).

heading: H.2.2 ADDITIONAL EXPERIMENTS
text: In the main paper we reported results when the identity function equation 12 was used to perform the coordinate update together with a sum aggregation function. In Tables 4, 5 and 6 we report also the results obtained when using equation 16 for the coordinate updates and possibly mean aggregation function. As can be seen, using the mean aggregation function usually causes a drop in performance. In particular, the SDGN with mean aggregation function is unable to correctly classify the polytopes even at training time. This is because, after rescaling the coordinates, all edges have the same length and, employing a mean aggregation results in always the same output for all polytopes. This is partially alleviated by using equation 16 as the node coordinate update function, which allows one to differently remap coordinates of different polytopes. The other results are qualitatively similar.
Adding not all-identical node features The experiments run so far used datasets containing only information about node coordinates and the presence of edges. If we add (not-all-identical) node features, then also SDGN with mean aggregation function is able to correctly classify all the polytopes. This happens thanks to the additional features breaking a symmetry making the graphs of the simplex and the orthoplex look identical to the SDGN layer.
Data efficiency To emphasise the advantage of having a network that is able to exploit symmetries in the dataset in terms of data efficiency, we study how many samples in the training set are necessary for a standard GNN to reach reasonable generalisation performance. For the set of transformations we considered in the previous sections, we augmented the training set with {2, 3, . . . , 100} randomly transformed (as in the respective test set) copies of each polytope. We trained a standard GNN on these augmented datasets and observed the resulting test accuracy after 1000 epochs. Results are reported in Figure 4 for each set of transformations in terms of mean and standard deviation over 10 random initialisations. It can be seen that 20 samples per polytope may be sufficient when only orthogonal transformations are considered. Adding also dilations and non-orthogonal transformations further increases the number of data points that are required. This shows that while data augmentation can be successfully exploited, it is provably sub-optimal in terms of sample complexity (Mei et al., 2021) and architectures with built-in equivariance properties represent a more efficient strategy to consider.

heading: H.3 MNIST, CIFAR10, TSP
text: MNIST and CIFAR10 are classical image classification datasets converted into graphs using superpixels and assigning the super-pixel coordinates as node coordinates and the intensity as node fea-
tures. TSP (based on the Travelling Salesman Problem) tests link prediction on 2D Euclidean graphs to identify edges belonging to the optimal TSP solution given by the Concorde solver.
For this datasets we use the same splits as specified in (Dwivedi et al., 2020).

heading: H.3.1 SPECIFIC IMPLEMENTATION DETAILS
text: The MLPs have one hidden layer containing 64 neurons, swish activation function and dropout layers with dropout rate 0.01. We used 2 graph layers for AGN and 3 for both the DGN and GN with embeddings in the hidden layers having dimension 64. Aggregation functions and the pooling layer implements sum operations. The models are trained with Adam with learning rate α = 0.001 and no regularisation for 100 epochs. Batch-size 128 is used for MNIST and CIFAR10, and 8 for TSP.

heading: H.4 MOLECULAR PROPERTY PREDICTION - QM9
text: The QM9 dataset (Wu et al., 2017) is comprised of small molecules (hydrogen, carbon, nitrogen, oxygen, flourine) with the target properties being 12 chemical properties. As the target properties are equivariant to Euclidean transformations of the atoms’ coordinates, and also to the order in which atoms are processed, QM9 is an excellent benchmarking dataset for a GNN, especially if E(n) invariant. Indeed, state of the art results have been achieved on this dataset by EGNN, Dimenet, SE3-Transformer (Satorras et al., 2021; Klicpera et al., 2020; Fuchs et al., 2020). Here we show that, in addition to leading to better accuracy, employing equivariant networks give a significant improvement in convergence speed.
Figure 5 show the evolution of the mean squared error on the test set on all the target properties for both architectures. We see that both the AGN and DGN outperform the standard GN in two aspects; the model trains more rapidly, and also reaches a lower loss.

heading: H.4.1 SPECIFIC IMPLEMENTATION DETAILS
text: The QM9 dataset is composed of roughly 134k molecules: we used 100k for training and the remaining for testing. The AGN and DGN networks receive the embedding of the atomic properties as initial node features and the coordinates of each atom as coordinate features, while in the standard GNN they are stacked and provided as node features. Edge embeddings representing bond types are also provided.
The networks consist of 4 graph layers (3 for the AGN) with each MLP having 2 hidden layers of 128 nodes, swish activation function and dropout rate of 0.01. The node embeddings of the last graph layer are passed through an MLP, a global mean pooling layer and a last MLP to map them to the target chemical property. The last two MLPs each have a single hidden layer of 128 nodes, swish
activation and dropout rate of 0.01. The target chemical properties are all standardised by subtracting the mean and dividing by the standard deviation for each target. The networks are trained for 1000 epochs using ADAM with a learning rate of 0.0005 and mean squared error loss.

Review summaries:
The paper seeks to develop invariance and equivariant graph neural networks.  Based on the assumption that node feautures can be separated into a node coordinate feature vector and coordinate-independent node feature vector, the authors develop a GNN architecture, called "angle preserving graph network" (AGN), that is  equivariant to  the Euclidean group and conformal group. The method is evaluated using the "benchmark" graph datasets produced in (Dwivedi et al., 2020) from, e.g., MNIST and CIFAR10 datasets.

This paper proposes two kinds of equivariant GNNs, including the distance preserving graph network (DGN) that is equivariant to the Euclidean transformations and angle preserving graph network (AGN) that is equivariant to the Conformal group. The proposed frameworks generalize several typical previous architectures. The advantage is experimentally evaluated on a synthetic dataset composed of n-dimensional geometric objects. 

The authors propose distance preserving Graph Network and Angle Preserving Graph Networks which are equivariant to node permutation as well distance preserving transformations/ angle preserving transformations of the coordinates associated with the nodes. The authors generalize the E(N) GNN work to include group symmetries to the conformal group and to the case when not all nodes in the graph are connected. Experiments on the  polytopes classification dataset show that the model is effective when symmetries are present in the data, and ineffective when they are not (MNIST, CIFAR and TSP).

This paper proposes two graph networks that are equivariant to distance and angle preserving transformations in graph coordinates. It moves one step forward based on GN (Graph Network) by decoupling node coordinates from other node attributes. The experiments on synthetic datasets shows the capabilities of the proposed symmetry-driven graph networks.