E(n)-equivariant Graph Neural Cellular Automata
Authors: Gennaro Gala
Daniele Grattarola
Erik Quaeghebeur
Venue: Accepted by TMLR ()

Abstract: Cellular automata (CAs) are notable computational models exhibiting rich dynamics emerging from the local interaction of cells arranged in a regular lattice.
Graph CAs (GCAs) generalise standard CAs by allowing for arbitrary graphs rather than regular lattices, similar to how Graph Neural Networks (GNNs) generalise Convolutional NNs.
Recently, Graph Neural CAs (GNCAs) have been proposed as models built on top of standard GNNs that can be trained to approximate the transition rule of any arbitrary GCA.
We note that existing GNCAs can violate the locality principle of CAs by leveraging global information and, furthermore, are anisotropic in the sense that their transition rules are not equivariant to isometries of the nodes' spatial locations.
However, it is desirable for instances related by such transformations to be treated identically by the model.
By replacing standard graph convolutions with E(n)-equivariant ones, we avoid anisotropy by design and propose a class of isotropic automata that we call E(n)-GNCAs.
These models are lightweight, but can nevertheless handle large graphs, capture complex dynamics and exhibit emergent self-organising behaviours.
We showcase the broad and successful applicability of E(n)-GNCAs on three different tasks: (i) isotropic pattern formation, (ii) graph auto-encoding, and (iii) simulation of E(n)-equivariant dynamical systems.

Published in Transactions on Machine Learning Research (04/2024)
E()e-equivariant Graph Neural Cellular Automata
Gennaro Gala
g.golu@lue.tt
Department of Mathematics and Computer Science Findhoven University of Technology, The Netherlonds
Daniele Grattarola
monidle.rataanlll@@maa.coo
Independent researcher
Erik Quaeghebeur
e. ..guaeghebeurr@ue...l
Department of Mathematics and Computer Science Findhoven University of Technology, The Netherlands
Reviewed on OpenReview: https: opwnreveeweeee...o net/ forum? 7PNJzAmks
Abstract
Cellular automata (CAs) are notable computational models exhibiting rich dynamics emerging from the local interaction of cells arranged in regular lattice. Graph CAs (GCAs) generalise standard CAs by allowing for arbitrary graphs rather than regular latticos, similar to how Graph Neural Networks (GNNs) generalise Convolutional NNs. Recently, Graph Neural CAs (GNCAs) have been proposed as models built on top of standard GNNs that can be trained approximate the transition rule of any arbitrary GCA. We note that existing GNCAs can violate the locality principle of CAs by leveraging global information and, furthermore, are anisotropic in the sense that their transition rules not equivariant to isometries of the nodes' spatial locations. However, it is desirable for instances related by such transformations to be treated identically by the model. By replacing standard graph convolutions with E(m)-equivariant ones, we avoid anisotropy by design and propose a class of isotropic automata that we call F(n)-GNCAS. These models are lightweight, but can nevertheless handle large graphs, capture complex dynamics and exhibit emergent self-organising behaviours. We showcase the broad and successful applicability of E(n)- GNCAs three different tasks: (i) isotropic pattern formation, (ii) graph auto-encoding, and (iii) simulation of E(n) -qqivvaaan dynamical systems.
1 Introduction
The design of collective intelligence, i.c. the ability of group of simple agents to collectively cooperate towards a unifying goal, is growing area of machine learning research aimed at solving complex tasks through emeryent computation (Ha & Tang 2022 The interest in these techniques stems from their striking similarity to real biological systems such as insect swarms and bacteria colonies and from their natural
scalability as distributed systems (Mitchell
2009
Cellular automata (CAs) (von Neumann 1963) represent a natural playground for studying collective intelligence and morphogenesis (shape-formil processes), because of their discrete-time and Markovian dynamics [uring 1952). CAs computational models inspired by the biological behaviors of cellular growth. As such, they are capable of producing complex emergent global dynamics from the iterative, possibly asynchronous application of localized transition rules (a.k.a. update rules), that can but do not need to have an analytical formulation (Adamatzky 2010
Research on applying neural nets for learning and designing CA rules can be tracod back to Wulff & Hertz 1992). with subsequent notable contributions by Elmenreich & Fehérvári] (2011). Nichele et al. (2018). and Gilpin (019). Recently, Neural Cellular Automata. (NCAs) have been proposed CAs with transition

---

Published in Transactions on Machine Learning Research (04/2024)
rules encoded as typically light-weight-nennn networks. They have been successfully applied for designing sell-organizing systems for morphogenesis in 2D and 3D (Mordvintsev et al. 2020 Sudhakaran et al. 2021 )
image generation and classification (Palm et al. 2022 Randazzo et al. 2020 reinforcement learning (Huang
ct al. 2020), pathfinding and graph-diameter computation Earle ct al. (2023 and many other subdomains of machine learning. This line of work has a common theme: It assumes fixed discrete geometry for the CA cells, which are typically arranged in n-dimensional, equispaced, and oriented lattices.
Subsequently, Grattarola et al. [021]] introduced GNCAs (Graph NCAs) by extending NCAs to the general setting of graphs, and showed that Graph Neural Networks are natural and universal engines for learning any desired transition rule. Their architecture, however, does not allow nodes to have hidden states, which have been proven to be useful for encoding perception and evolution history (Mordvintsev et al., 2020). More crucially, their formulation allows nodes to be aware of their global locations and sticks to a fixed frame of reference, therefore ignoring the possible symmetrics in the state space even for states represcnting spatial information like position and velocity.
By building -qqivvaaaar Graph Neural Networks (Satorras et al. 2021b elegantly overcome these relevant issues and present GNCAs that respect isometries in the state space by design, leading to truly self-organizing systems. Our contributions are twofold:
We propose the first -sytropic-by-deeign GNCAs, which we name E(n)-GNCAs. More specifically, these models are E(n)-qquivariant and, crucially, cannot globally localise the nodes. In this way, unlike standard GNCAs, it is impossible to violate the core locality principle of CAs, making it essential to solve unifying, shared goal:
We provide extensive guidelines on how to train E(n)-GNCAs and showcase their broad, successful applicability on three different tasks: (i) pattern formation, (ii) graph auto-encoding, and (iii) simulation (self-organizing) -quivvaaan dynamical systems.
Our model and results represent a step forward in the design of self-organizing neural systems and can have concrete impact in modeling and understanding natural systems governed by strong local interactions, ranging from chemical to social phenomena (Ha & Tang 2022)
2 Preliminaries and Related Work
We here introduce necessary concepts of and relevant prior work on cellular automata and (equivariant) graph neural networks. These support and contextualize the model we propose.
Graphs A graph g = EV,E) consists of an unordered set of nodes == [L...., [ and a set of edges EC V V. Its neighbourhood function N' is defined for every node E by N(i) = (j E V (i.j) E E). A graph can be equivalently defined with an adjacency matrix E {0, 1111 where As is if and only if (i,j) E
We can attach a state s; S to each node and an attribute ei A each edge (i,j), where for now we leave the state space S and attribute set A unspecified. A node state s; typically consists of components such as location x,, velocity Vi, and (hidden) node features h, Jointly for all nodes and edges, we write S-with components X, V, and H and E respectively, which implicitly carry with them the underlying graph.
2.1 Graph (Neural) Cellular Automata
Graph Cellular Automata A Graph Cellular Automaton (GCA) is triple (G, S, where G = (V.E) is a graph and S is a discrete or continuous state space. The map 7 S x 25 - is used as a local transition rule to update the state s; E of each of the graph's nodes E V as a function of its current state and its neighbour's states:
s = (s, :j (())).
(1)
We will compactly write S' 7S) (((SStt to indicate the synchronous application of to all nodes in g. Standard CAs like elementary CAs (Wolfram 2018) and Conway's 's Game of Life (Adamatzky' 2010 use simple
2

---

Published in Transactions on Machine Learning Research (04/2024)
grid for the underlying graph 9, have integer-valued locations x, Z" and use single binary value for their features h;
Anisotropy & Isotropy Of great importance for CAs are the properties anisolropy and isolropy: The former implies being directionally dependent, as opposed to the latter, which indicates homogeneity in all directions. Anisotropic transition rules account for not only the neighbor states of a given node, but also their absolute position in a (vector) space of reference. Furthermore, anisotropic transition rules are not invariant to rotations, translations and reflections of the states, thus resulting in nodes being oriented in a specific direction and prohibiting the existence of differently oriented states of interest (Mordvintsev et al., 2022 Grattarola ct al. 2021). In contrast, isotropy allows transition rules to act similarly regardless of how the nodes are oriented, thus allowing proper design of self-organssigg (and living) systems.
Neural Cellular Automata A neural cellular automaton (NCA) uses a light- neural net with parameters for its transition rule To (Mordvintsev et al.) 2020). In this setting, states are represented as typically low-dimensional vectors. The differentiability of the transition rule allows for optimisation of its parameters 0 via. backpropagation through time (Lillicrap & Santoro 2019). Recent work has shown the successful application of deep learning techniques for NCAs, showing that neural Iransition rules can be efficiently learned to exhibit complex desired behaviors [Mordvintsev et al. 2020 2022 Tesfaldet et al. 2022
Grattarola et al. 2021
Palm et al. 2022
Note that (N)CAs are unoware of lime and their execution not constrained by a finile time interval. Furthermore, they can only be inspected via simulation from a state of interest and that represents key feature of these models. For instance, clementary CAs (Wolfram 2018), , c.g. Rule 30, can run forever and, crucially, arbitrary future state cannot be predicted from a current one unless via simulation, i.e. by iteratively applying the transition rule up to the time step of interest.
As already pointed out by Tesfaldet et al. 2022). NCAs are not structurally equivalent to (doep) foed-forward neural nets, where an acyclic directed computation graph induces a finite impulse response. Instead, NCAs can be viewed as Recurrent Neural Networks (Rumelhart et al.) 1986), where a cyclic directed computation graph induces an infinite impulse response, enabling feedback and time-delayed interactions. Notably, RNNNs
and CAs and by consequence NCAs are known to be Turing complete (Pérez et al. 2019
2.2 Graph Neural Networks
Graph Neural Networks (GNNs) Gooi et al., 2005) have become the go-to method for representation learning graphs. The core functionality of GNNs is the message- passing scheme. Let s; R represent the feature vector of node i and Cjj E R the (possibly available) feature vector of edge (i,j). A messago-passing layer updates the features of node i as follows:
$ = 7s: SSE o(s,, Sy, ej:),
22)
where @ is the message function, + is a messages, and 7 is the node update function. The differentiable operators Φ; θ and 7 allow peassag--aassigg layers to be stacked sequentially and then optimised with (stochastic) gradient descent.
invariant operation aggregate the set of incoming
2.3 E(n) -quivarria Graph Neural Networks
Our work builds on E(n)-qquivariant GNNs (EGNNs) (atorras et al. 2021b). In this setting, every graph node i has coordinates X; E IR" and node features h, E R", and an edge (1,5) E E can possibly have attributes eij E RR. FGNNs represent a class of GNNs explicitly designed to be permutation equivariant with respect, to the nodes (like any GNN), and translation, rotation and reflection equivariant with respect to nodes" coordinates. The isometry group corresponding to these symmetrics is callod the Euclidean group E(n). We will formally discuss the key features of EGNNs while presenting our method in Section 3
-equivratar Graph Convolutions Given graph G, node coordinates {x:}, node features {h:}
and optional edge attributes {ei} an F(n)-equivariant Graph Convolution (FGG) sequentially performs:
3

---

Published in Transactions on Machine Learning Research (04/2024)
m (m hy hy,
(3)
x = + Wil Ejerro xx))a (m)))
(5)
= EjEN()) Mij
(4)
h = %% (h, m,)
(6)
where pm R 11+2/+e - RT 0z Rm + R' and 0% R h
+
R are MLPs. Concisely, we write
T.H'=EGO' H) If M = h, a skip connection can be used in Equation as follows:
h = t (h,, m,) = (h, m,) + h
(7)
E(nn-cqquvariant Graph Convolutions with Attention messages, we can use allention and replace Eq. with:
To assign different weights when aggrogating
m = EjEN() o (a
(8)
where de R - [0, 1]' is an MLP that takes message mij input and outputs its attention weight da (m.y) We will use this formulation in Section 4.3 Note that, attention weights are particularly advantageous when
a very dense (possibly fully connected) graph is used (Satorras et al. 2021b; Vaswani et al., 2017).
-qqiivaannr Graph Convolutions with Velocity When nodes represent bodies with velocities, we can extend the previous formulation to explicitly account for velocity. Given node velocities {vi} we can replace the coordinate update in Equation with the following two steps:
1 v = Se (h,, llvellllv, + [V EjeN(y (m.))(
(9)
x X;
+ V
(10)
where ou IR 1+1 + R is an MLP. Without affecting equivariance, and different from Satorras et al. du has not only h, but also ||v as an argument, since we found it to be very beneficial in practice (cf. Scction 4.3 Conciscly, we write X', V H' = EGC(X, V, H).
(2021b),
E ((n))equivarian GNNs An E( n) equivariant GNN is a stack é 1 EGCs applied sequentially, Conciscly, we write X', H' EGNN, X, E) to denote the application of an EGNN with layers.
3 Equivainn Graph Neural CAs
Our work builds on the connection between isotropic GCAs and EGNNs. This becomes apparent by comparing Equation Twth Equations 5 B Specifically, we consider setting which a neural parametrised transition rule To is implemented with single E(n)-cquivariant Graph Convolution (EGC) acting continuous state space S = Ba or S = 22++h when velocity is included. We call such model -(n)--quivariant GNCAs, E(n)-GNCAs for short. Similarly to standard CAs, is repeatedly applied over time:
X', H' (XX H) o X H
(11)
timess
where X represents input node coordinates and H represents input node features. Note that (i) to avoid clutter Equation we did not consider possibly available edge attributes E, (ii) a similar formulation is possible when velocities are available (cf. Equation 9h, and (iii) the dependency of та on a static graph G is left implicit in order to keep notation uncluttered. The overall state configuration S of E(n)-GNCA is defined as S = [X, HJ, or S = [X, H, VJ when velocity is available, and consequently we denote the I-limes application of the model transition rule as S' (S). Note that the transition rules consider is 1-step Markovian, meaning that automaton state at step t + 1 is fully determined by the state at step t.
On the Single-layered architecture Using a single layer for to entails (i) optimizing less parameters and (ii) having the strictest possible locality bottlenock, i.c. nodes are exclusively influenced by their immediate surroundings and do not have direct access to the global state of the entire system. In fact, using more layers would make the tasks will study (ef. Section less local and less challenging because the model
4

---

Published in Transactions on Machine Learning Research (04/2024)
can account for larger and more informative receptive field when transitioning from S to 4+1 This is
a common design choice in NCA literature (Mordvintsev et al. 2020 2022 Palm et al. 2022 Grattarola et al. (021). However, a layered EGNN is still a viable approach for OO if we want to account for higher-order neighbours when performing a state update, as in the artificial life system Lenia (Chan
2019).
E(n) -quivvaiiir,,, E(niiinvaiaance and Isotropy Analogously to plain EGNNs (Satorras et al., 2021b), for any positive integer E N+, orthogonal matrix Q E R and translation vector b E R", our neural transition rule Ty satisfies
X
X'HH'
600
OD
T
46 (X ) H'
H)),
(12)
600
where X', = + X HJ and &b (X) ( QX + b is short- hand for (Qx1 + b...., Q + b) The function v is an isometry, and represents a rotation-reflection translaainnn of the coordinates. As such, v preserves the Euclidean distance between every pair of nodes. In other words, applying se to input coordinates X and then running tran- sition rule TJ will give the same results as first running T and then applying &b to X', shown in Figure 1 As a consequence, output coordinates X' and output node features H' are respectively Equi-eqquvarraan and E(n)- invariant to isometries of input coordinates X. Intuitively, these properties are consequence of only processing rel- ative positions and never being aware of absolute node The E(n)-invariaace
V
900
000
10
O#S
( [X)
(x(X') III
Figure 1: E(n)-GNCA commutative diagram: For any mumber of steps t the transition rule Ta is run, output coordinates X' and node features H' are respectively E(i)-qquivariant and E(n)- invariant to isometries of input coordinates X. Node features are represented with 3 colored dots.
locations (cf. Equations and
of the node features and the E (2) equivariance of the node coordinates make L(nR)GNCAS GNCAs isotropic by design.
Hidden States & Perception Similarly to Mordvintsev el al. 2020 2022), Palm et al. (022) and Chan (2019), but different from Grattarola et al. (2021), our model has the necessary inductive bias for modelling hidden states, it offers location-independent node features H. These features are crucial because they can encode past evolutionary history as well as higher-order geometrie information. This is not possible with original GNCAs, where node locations represent the whole state of the system (i.e. X = S), without hidden states allowing to encode other kind of information. As Mordvintsev et al. (2020), we interpret our hidden states as a signal mechanism for orchestrating morphogenesis: All nodes share the same genome, i.e. the transition rule, and only differ from the information encoded by the signaling they receive, emit, and store internally, i.e. their node features. In case node features are not available in advance, we can either set them to or randomly initialize them, and give the model the freedom to learn and use them while evolving. Further, messages [m,y] } (cf. [Equation 3 are similar in spirit to the perception vectors of Mordvintsev ct al. 2020 2022), as they encode what nodes perceive of the environment from commuicating with their neighbors
Given (i) the interest in what would happen as + oo and (ii) the recurrent architecture of our model, we normalise node fcature H after cach transition rule application so as to mitigate problems like over-smoothing, vanidshin/ gradients, and training instabilities. Specifically, after every transition rule application, normalise node features H with either PairNorm (7hao & Akoglu 2020) NodeNorm (Zhou al. 2021) helpful perameter-free normalisation techniques for deep GNNs. Furthermore,
use the hyperbolic tangent
(anH() as non-linear activation function common design choice in RNNs (Lipton et al.
2015) and the
skip connection defined in Equation which has proven to be beneficial for deep GNNs
(Xu et al. 2021
Zhao & Akoglu 2020).
Note that if volocity V is involved, it would be transformed QV.
Satorras all 2021b Appendix) provide formal proof of the equivariancc/Iivariane of EGNNs.
'In image domain, similar behavior is exhibited by CNN-basee NCAs: Rotating the perceptive field of the Sohel convolutional kernels leads to equivalently rotated target images (Modvintsev al. 2020 experiment 4).
5

---

Published in Transactions on Machine Learning Research (04/2024)
Global propagation from local interactions Message-passing GNNs require E layers to allow communi- cation between nodes that are E-hops away. Several tasks in graph MI. tend to be very challenging when the diameter of the underlying graph G is larger than the number of layers used, and that is because the receptive field of the network may not comprise the whole graph (Zhao & Akoglu 2020 Alon & Yahav 2021). Further, to avoid severe over-smoothing (Li et al. 2018), most popular GCN-style networks (Kipl & Welling 2017) tend to be shallow, with narrow receptive fields, Icading to under-reaching (Wenkel et al., 2022). To avoid this limitation, it is common to exchange messages among all nodes and provide the edge information (i.5) & as Boolean flag within the edge attributes (Liu et al., 2019 Satorras et al. 2021b ab. This is computationally quadratic in the number of nodes, and therefore very challenging and computationaly expensive when processing large graphs
In our setting, due to the 1-step Markovian property of Tg, the effective receptive field of E(n)-GNCA localized message- pastaggggagnnngggggg grows larger with each state update until eventually encompassing the whole graph. In this way global propagation of information arises from localized interactions of nodes. In other words, iterative local ressage-passing circumvents the quadratic complexity and related challenges of exchanging messages among all nodes at each step. This self-organizing process does not require any external control or centralized leader: nodes communicate with their neighbors to make collective decisions about the final configuration of the nodes. This globally consistent and complex behaviour, which arises from strictly local interactions, is a particular feature of (N)CAs as we show in our experiments. Finally, we emphasise shat-despp the localized model computation we are allowed to express global information within the loss function used for training. In other words, the training signal can account for the distance between two nodes that are actually not connected via edge, as will do in Equations B and 15
On locality & time Very often in the literature, GNN computation graphs are decoupled from the input graphs. For instance, Satorras et al. (2021b) and Satorras ct al. (2021a) use layered EGNNs with fully-connected computation graphs despite input graphs being sparse (e.g. molecules). E(n)-GNCAs, instead, always use sparse computation graphs. Moreover, GNN-based diffusion models-amn often also neural simulator (Chen et al. 2018) 2018)aare are aware of time, which is usually included in node fcatures via concatenation HHogeboom et al. 2022) and that allows training using mini-batchen of sub-trajectories extracted at different time steps (Yang et al. 2022). F(n))GNCAs are instead unaware of time, making tasks only solvable through simulation from an initial state of interest. These are fundamental design choices which highly impact the tasks we will study. Finally, note that diffusion-based models and neural simulators often only care about a finite rollout, whereas, as we show in our experiments, we care about open-endedness, i.e. infinite rollouts.
4 Experiments
We showcase the successful applicability of E(n)-GNCAs in three different tasks: (i) pattern formation, (ii) graph autoencoding and (iii) simulation of E(w)-equivariant dynamical systems. We set h = 16 (hidden dimension) and m = 32 (message dimension) throughout all experiments, leading to an overall automaton size of only 5K parameters irrespective of the coordinate dimension being used. We are grateful to the developers of the main software packages used for this work: Pytorch (Paszke et al.] 2019). PyTorch Geometric (Fey) & Tenssen 2019) and Lightning (Falcon & The PyTorc Lightning team. 2019). Our code available at github.com. gengala/egnes All experiments are run on an NVIDIA Quadro P1000 16GB, and each run does not take more than 2.5 hours to complete.
4.1 Pattern Formation
Inspired by prior work on CA morphogenesis (Mordvintsev et al. 2020 2022
Grattarola et al. 2021). we
show how E(n)-GNCAs can be trained to converge to a given fixed target state. In our case, the target is a sparse geometric graph & that visually defines a recognisable 2D or 3D shape. Specifically, the goal is to learn a transition rule To that morphs randomly initialised coordinates X to a given target point cloud X by convolving over G and assuming a prior 1-to-1 correspondence between nodes in X and X.
6

---

Published in Transactions on Machine Learning Research (04/2024)
t= Eyp 177813
t= faw 1.1179
t= 16 Low 0. 0.00684
t= 24
Ewy 0.00101
t'=24 Cav 0.00969
t= Eay 0.00021
2.34665
1.19499
0.00655
0.00212
0.00327
t- 0.00031
Cav 2.35641
Cou 2.14854
Cay m 0.00400
[w24 fow 0.00258
F- Lnw 00472
Figure 2: E(n)-GNCA convergence 2D grid (top), 3D torus (middle) and the Stanford geometric bunny (bottom). The first 4 columns show E(n)-GNCA states at different time steps. The second to last column shows either a local or global damage of coordinates at / = 24. Finally, the last column shows regeneration and persistency abilities by running the transition rule for 1000 extra steps after perturbation has occurred. Note that, if we were to apply any isometry at any point in time, convergence and persistency would still be guaranteed. We report LINV (cf. Equation 13) for the state in each figure. The nearest-neighbor edges the Stanford bunny are not shown so as to avoid clutter. We report complete trajectorics in Appendix Best. viewed digitally and zoomed in.
objective Contrary to Grattarola et al. 2021 are not interested in specific orientation of X and therefore we do not optimise the model by minimising the MSE between coordinates reached by = ([X,, The former, morcover, would
the model and target coordinates, i.c. |X'-X| 1 where not be suitable objective for our automata since it accounts for specific global locations which are unknown our model that only uses relative positions during its computation (cf. Equations 3 and 5). Therefore, for every pair of nodes (i,j) E V V, we minimise the MSE between their distance in the model's final configuration and the target one. Formally, define E(n) invarint objective follows:
1 LINV MI Eosteexx (1xx) x,1l ||:; x;11)²
(13)
This objective accounts for all pairwise distances, this is necessary to uniquely identify the target state, which cannot be done if we only considered the edges of the graph However, this does not make the model less local: Even if global information is used in the loss function, the model itself still only uses local communication to perform the task. Equation 13 provides a much weaker supervision signal than the one by Grattarola et al. (2021), therefore leading to a much more challenging task. That is because their model every node aware of its global location and has only a single constraint satisfy, i.e. being close to specific global location. Moreover, being aware of global location violates the locality principle of CAs and makes pattern formation rather easy to hack: We found that 3-layer MLP with Fourier features TTancik et al. 2020) can transform any given initial state to target one in a few optimisation steps, without. relying on a neighborhood graph. In our case, however, nodes are not aware of their global location, and
For instance, consider simple square: If only minimize the distances of edges, the model could converge whose loss value sero hut that does form square (e-g,, when two opposite vertices share the location).

---

Published in Transactions on Machine Learning Research (04/2024)
have |V] -1 constraints to satisfy, i.e. its distances w.r.t. all the other nodes in 9, not only its neighbors. Interestingly, optimizing for Eqquation 13 results in learning a transition rule To such that [X', H = (X, 1)) and X' = (xX for any arbitrary isometry v). In other words, our objective gives the model the freedom to converge in any possible orientation of the target. In practice, one could avoid evaluating (11))) distances by only considering randomly sampled subset of node pairs when computing Equation 13 Our objective is similar in spirit to the one by Mordvintsev et al. 2002), where a rotation-reflection invariant objective is used in the image domain. Similarly, Equation 13 is an E(n)-invarian loss function that uniquely characterizes a target point cloud up to isometries when it is equal to zero, and fits well with the model isotropy. However, the objective is not node-permutation invariant as it relies on a 1-to-1 correspondence between initial and larget nodes: If the initial and larget states were equal (up isometries) but the correspondence between nodes did not match, the loss value would not be zero. Although this represents a limitation of the current loss function and may lead to sub-optimal dynamics, the feasibility of the task still entirely depends on local communication, which represents the core of our experimental investigation.
Training We mostly follow the experimental setup in (Mordvintsev el al. First, we create large pool (a.k.a. cache) of K states {S"")] {X [X, 1), where X ~ NO, o1). Then, randomly sample mini-batch from the pool and use it as input to transition rule Te, which runs for number of time steps t sampled uniformly from the interval [15, 25 Once a mini-batch is processed, we apply backpropagation through time (BPTT) (Liliccrpp & Santoro 2019) to update parameters 0 according to Equation 13 To promote persistency, we use the pool as a replay memory, i.c. once an optimisation stop performod, we replace the pool state S(k) with (S((s)) for every S(h) in the current batc. This allows further training iterations to account for states that already result from a
2020 Grattarola et al. 2021
H
R k= each initialised
repeated application of the transition rule, thus encouraging the model to persist in the target state after reaching it. Furthermore, before processing a mini-batch, the state with the highest loss value is replaced with the initial state [X. 1| so as to both stabilise training and, more importantly, avoid catastrophic forgetting. Finally, to also promote regeneration, we perturb half of the point clouds in the batch by adding Gaussian noise: A part is perturbed globally and another only locally.
Results We consider 8 different geometric graphs, and succeed with all of them, although only a repre- sentative subset is reported in the main text due to limited space: A 2D grid (256 nodes), 3D torus (256 nodes) and the Stanford bunny (2503 nodes) (Defferrard et al. 2017). Figure 2 shows (part of) E(n)-GNCA trajectorics as well as the loss value (Equation 13) w.r.t. the coordinates at cach time step shown. Remarkably, our model learns to converge to a stable attractor of the given geometric graph, i.e. the model can maintain the target state after any number of time steps >> 15, as shown in the last column of Figure 2] Furthermore, the model exhibits regeneration abilities by being robust against perturbations of the nodes. More details, animations and results can be found in Appendix A and supplementary material.
On Isotropic Pattern Formation Isotropy is a well-established property in CAs and it is very desirable in our context. In fact, isotropic pattern formation besidds being more challenging to achieve is more general and subsumes its anisotropic counterpart. This means that if directional dependence needed, we could manipulate the automata such that the target states will be placed at any desired orientation. This is not possible with original GNCAs, given their awareness of global locations, which violates locality. We refer the reader to Figure A.9 for a visual example of the concept above.
4.2 Graph autoencoding with Cellular Automata
In this section, we show how E(n)-GNCAs can be deployed as performant Graph AutoEncoders (GAEs) Kipf & Welling 2016), despite their single-layered architecture and recurrent computation. In graph autoencoding one has available a set of (possibly featureless) graphs } and wants to learn node representations that can be used to reconstruct the underlying ground-truth adjacency matrices (Satorras et al., 2021b Liu al. 2019h. Specifically, we will deal with graph autoencoding in Fuclidean space, i.e. two nodes will be connected
Thh interval considered represents a trade-off between computational complexity, stability during training, and a sufficient. number of time steps to allow the model learn dynamical patterns for the desired behavior.
8

---

Published in Transactions on Machine Learning Research (04/2024)
if their distance is below equal to given threshold f, which can be fine-tuned the validation set after training. For this task, we report more details and additional results in Appendix B
Datasets We consider five datasets of featureless graphs of varying size, connectivity and properties: COMM- S (100 graphs, communities, 12-20 nodes) (Liu et al. 2019), PLANAR-S (200 planar graphs, 12-20 nodes), PLANAR-L (200 planar graphs, 32-64 nodes), SBM (200 stochastic block model graphs, 2-5 communities, 44-187 nodes) (Martinkus et al., 2022) and PROTEINS (918 graphs, 100-500 nodes) (Dobson & Doig 2003).
Figure B.10 shows some examples of such graphs. Planar graphs generated by first uniformly sampling 2D points in [0, 1 and then applying Delaunay triangulation. We split all datasets into training (80%),
validation (10%) and test (10%) sets.
t=0 0 LECE 13.28
t= LacE = 9.01
t= LEcE 6.60
t= 16 CacE 0.39
t= 24
LECE 0.19
t= 1000
CacE 0.18
Figure 3: E(n)-GNCA coordinates different time steps for test-set graph in COMM-S. In each figure, we plot the ground-truth edges and report the binary cross-entropy (ef. Equation 15).
Training For each training graph Gn we create a small pool of K states [[x(m.)) H( Every H(n,)) is again initialised as 1 whereas input node coordinates ((.)) now follow an isotropic Gaussian M(0, o As such, the model can be viewed as a generative model conditioned on G. A mini-batch now created by first considering a random subset of training graphs and then sampling a random pool state each. Every mini-batch state ((n.k) is then run by To for E [f1,t]] random time steps, eventually reaching state X', H'l (S(.k))) Finally, apply E(n)-invariant decoding scheme based on distances between nodes X' so that the reconstructed soft adjacency matrix Å E [0, 1]IIXI| X
defined as:
Aij 1 + exp(62((1x) x,13-- -11) E [0, 1],
(14)
where ôj and 82 are learnable positive scalars. The model is trained by minimising the binary cross-entropy (BCE) between the ground-truth adjacency A and the predicted soft one A, namely:
LBCE = E., An In(Ai))) + (1 (1)) In(1 -ay).
(15)
Equation 15 can be seen as more relaxed version of Equation 13 although it still requires the 1-to-1 correspondence, but is E(n)-invariant. Furthermore, we require our autoencoders to be persistent, namely, it should always be possible to correctly docode a graph 9 after a sufficient number of time steps. This is a particular feature of our model, that differ from standard autoencoders, which are not trained to be stable over time. To promote persistency, we use a multi-target replay strategy-similar to the one-target version Section 4.1 so as ensure an adequate exploration of the state space during training. Specifically, after every optimisation step, replace the reached state [X', H'] with the pool state that originated it, and randomly re-initialise pool states after a given number of maximum replacements as to avoid catastrophic forgetting.
A 3D demo In a first demo experiment, we use COMM-S and PLANAR-S and set n 3 so as to visualise automaton trajectories in 3D. The experiment shows persistent autoencoding, conditional generation of 3D
point clouds and graph drawing abilitics (Eades 1984 Tamassia 2013). We randomly sample in [15, 25)
Injecting Gaussian noise as initial nade features has originally been proposed Liu way of overooming the symmetry problem and over-smonthing (Satorras al. 2021b Sato 2021 Godwin
2019 and then also used
2022

---

Published in Transactions on Machine Learning Research (04/2024)
B(n)-GNCA
EGNNA
30
GNCA
GNN
GNNo0
COMM-S
1.00+00.00
0.91110.33
1.00=1.000
0.95:10.01
0.88+1004
1.00
PLANAR-S
0.99
0.83#00011
0.99=0.02
0.88+0.01
0.82+0.05
0.98#0.03
PLANAR-L
0.90110.01
0.88+0035
0.99
0.85110009
0.8410.25
0.97
PROTEINS
0.95#00004
0.84+0.01
0.97=0003
0.82++0.08
0.82+0.03
0.95=0.05
SBM
0.92++0.02
0.76++0.01
0.96++0.04
0.86++0.11
0.75+00.07
0.93++0.3
Table 1:
Autoencoding results. F1 scores (the higher the better) averaged over 10 different runs, (E(n)-)
GNCAs are evaluated at time 100. More details can be found Figure B.11
at each optimisation step. We reach an average and persistent Fl score of 0.98 and 0.96 for COMM-S and PLANAR-S respectively over 10 different runs. Figure 3 shows the learned dynamics of our autoencoder.
Autoencoding Results E(n)-GNCA autoencoders can scale to higher Euclidean spaces and significantly larger graphs, without increasing the size of the models nor losing persistency. We set 8 for all datasets except SBM where it is set to 24, and randomly sample È in 25J. We compare against standard 4- and 30-layered GNNs (Kipl' et al. 2018). 4- and 30-layered EGNNs, and GNCAs (Grattarola et al. 2021 For a fair comparison, we do not allow fully connected GNN computational graphs, as opposed to Satorras et. al. (021b), but instead use as computation graph the same graph to autoencode. [Table 1 reports autoencoding results. Remarkably, E(n)-GNee GNCA outperforms 4-laycrod (E)GNN and achieves comparable level of performance of a 30-layer (E)GNN. Several examples of graph reconstructions are available in Figure B.10 Different. from standard GE)GNN autoencoders, F(n))GNCA autoencoders also exhibit persistent dynamics (ef. Figure B.11 for all datasets except SBM, which, given the variable clustered topology, represents the most challenging dataset.
E(n)-GNCAs are multi-target E(n)-GNCA autoencoders are multi-target as they can reach many target states, contrary to what is shown in our previous task and previous work (Grattarola et al. 2021 Mordvintsoy al. 2020 2022). We suppose this to be the consequence of more relaxed training objective (ef. Eqquation 15 than the previous one (ef. Equaaton 13p. Tn graph autoencoding, in fact, target states are not explicitly given but rather a condition that they must satisfy is (ef. Equations 14 and [5 Therefore, since are only interested in reconstructing the ground-truth A via Equation 14 E(n)-GNo C--NNAAs can converge to any possible configuration from which decoding is possible.
4.3 Simulation of -quiivarrva dynamical system
We show the applicability of B(n)-GNCAs as simulators of E(x)--quivvariat dynamical systems. The goal is to learn the transition rule underlying observed trajectories. Specifically, we train F(n)-GNCAs to simulate the Boids Algorithm [Reynolss] 1987), Markovian and distributed multi-agent system designed to simulate flocks of birds using set of hand-crafted rules. The graph G is obtained as a fixed-radius nearest neighbourhood of the nodes at each time step-G changes dynamically over time. This dynamical system (i) can be formulated as GCA (cf. Equation I and (ii) is E(n) equivariant. This task very different from the previous ones as we want to approximate existing dynamics and not discover some that converge to a given state.
Dataset We extend the 2D simulation of Graltarola et al. (2021) to 3D space. We create a dataset of 500 trajectories using the ground-truth simulator. Each trajectory has duration of 500 time steps and is obtained by evolving 100 boids initialised with random positions and velocities.
Training We use attention weights (ef. Equation 8) and Equations 9 and 10 to explicitly account for velocities. We create a mini-batch randomly sampled sub- tub-trajectories of length L 20. For each mini-batch sub-trajectory (X) v(0] we input To with state S(1) [X(1), V(I), H() and run for L stops, obtaining predicted states [X Vi( H' Finally, we optimize the MSE of the estimated velocities with the ground truth ones, i.e.
10

---

Published in Transactions on Machine Learning Research (04/2024)
true 20
50
100
true
true
300
true t=0
pred t= 20
pred
==
pred
t= 100
pred
t= ==200
pred
t= 300
Figure 4: Boids simulation. First (Second) row shows a ground-truth (predicted) trajectory at different time steps. E(n)-GNCA learns a flocking behaviour similar the target system, although with smoother and less precise trajectories.
L MSSE Σ llvo 110
(16)
As Satorras et al. 2021bb node features (1) are initialised as the output of a linear layer taking [V[] as input.
Results As already pointed out by Grattarola et al. 20021 one key aspect of simulating continuous (and chaotic) dynamical systems with GNCAs is that small errors in prediction will quickly accumulate, making it almost impossible for the model to perfectly simulate the true dynamics. Therefore, despite reaching a small validation error, the model canmot perfectly approximate the true trajectories. However, following Grattarola et al. (2021), we can quantitatively evaluate the quality of the learned transition rule by using the sample entropy (SE) (Richman Moorman 2000) and correlation dimension (CD) (Grassberger Procaccia 1983). measures of complexity for real-valued time series. On average, ground-truth trajectories (of length 500) report an average SE and CD of 0.04 + 0.01 and 1.02 + 0.22 respectively, whereas E(n)-GNCA trajectories measures. The closeness of the measures indicates that
report 0.04 + 0.02 and 1.08 + 0.15 for the E(n)-GNCA trajectorios generate amount of information comparable to the ground-truth ones, therefore capturing the essence of the underlying rule, Figure 4.
Note that original GNCAs also succeed at capturing the Boids rule. However, them being aware of the global locations, the task casier solve. Crucially, morcover, the GNCA model would be unable work different reference frames except for the one used during training (e.g. [0, 1J3), while our model can transfer, by design, new frames.
5 Discussion
We introduced B(n)-GNCAs, isotropic automata showing and promising a wide range of applicability. F(n)- GNCA local interactions have been proven powerful enough to reach globally consistent target conditions and capture complex dynamics. To the best of our knowledge, this is the first work proposing isotropic-by-desiee graph neural cellular automata.
Scope of the paper This work does focus on GE)GNNs, nor physical simulation, nor graph autoencoding. Instead, our focus is designing and learning CA rules, as well as showcasing the properties of local, isotropic,
11

---

Published in Transactions on Machine Learning Research (04/2024)
open-ended and distributed self-organizing systems. To give context, note that in NCA papers (Mordvintsev et al. 2020 Palm et al. 2022), the focus is not image generation but image generation through emergent computation. All our experiments are designed to answer the crucial question underlying CAs: How can we design a CA transition rule that behaves according to some high-level specification (c.g. forming a gridy? Since general the answer to this question requires some (impossible) complex engineering, recent. literature leveraged neural networks to learn these rules.
Isn't it just an EGNN layer? We make no claim of novelty in the design of EGNN itself (except Equation 9), but rather in the way that EGNN can be trained and used to implement the open-ended local computation that characterizes CAs. However, our model differs from FGNNs in very fundamental aspects like the training procedure, the open-ended inference, and the uncommon single-layered architecture. Morcover, by definition, NCAs are CAs in which the transition rule is parametrized by neural net: In original NCAs (Mordvintsev et al., 2020 Palm et. al. 2022 (resp. GNCAs (Grattarola et al. 2021)), the neural net is composition of convolutional layers (resp. message-passing layers). In our paper, the neural net consists of an EGNN layer. The chosen neural net endows the NCA with inductive biases that allow it to model specific transition rules and self-organizing systems. The study of these families lies at the core of the NCA literature.
Broader scope The possible implications of our work are evident when considering that distributed and self-organizing systems ubiquitous both in nature and technology (Collinet & Lecuit 2021p. Furthermore, isometries very common in dynamical systems (e.g. swarming (Reynolds] 1987). particle simulations (Kipf et al. 2018)), active matter (Cichos et al.) 2020), and in many practical applications (e.g. point cloud processing, 3D molecular structures (Ramakrishnan et al. 20144). Our model and its inductive biases are particularly useful in all these scenarios, since they allow to learn and discover recoherr-rather than hand-design the transition rules underlying these systems, while accounting for symmetries.
Notably, one of the most remarkable demonstrations of self-organisation can be found in swarm robotics and active matter modeling (Brambilla et al. 2013 Vicsek et al.) 1995). Nowadays, can program tiny robots to locally interact and form a given pattern, Mergeable Nervous Systems (Mathews et al. 2017) and Kilobots [Rubenstein et al., 2012] demonstrated. To the best of our knowledge, such programs are currently designed by humans. Our work can enable a line of research in which GNNs further unlock the power of GCAs to implement a desired behavior through differentiable, distributed and emergent computation.
Limitations & Future Work Training E(n)-GNCAs is not easy: We faced problems such exploding gradients, which mitigated using weight decay and gradient clipping. Furthermore, the 1-to-1 correspon- dence between initial and target nodes does not make Equations 13 and 15 mode-oodemeene peroutpermttatinn invariant, and this represents a sub-optimal design choice as it leads to abrupt dynamics especially in the first time steps. In future work, we aim to drop this correspondence by adopting ideas from Terimal-Transport (Poyré & Meliss el al. (2019). Furthermore, we plan to use more expressive GNNs (Joshi et al., 2023 Thomas et al.) 2018 Batatia et al. 2022 Fuchs al. 2020). and scale to even bigger graphs using structured seeds (Mordvintsov et al. 2022
Cuturi 2019
Acknowledgments
The Eindhoven University Technology authors received support from their Department of Mathematics and Computer Science and the Findhoven Artificial Intelligence Systems Institute.
References
Andrew Adamatzky. Game of life cellular aulomala, volume 1. Springer, 2010. do::1001007797711110999---
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021. URL http:ss//pperrrvvee..ooooo wtt.arrrrrioo.ttt///uur......
1800PhOCVH2
12

---

Published in Transactions on Machine Learning Research (04/2024)
David Alvarez-Melis, Stefanie Jegelka, and Tommi S Jaakkola. Towards optimal transport with global invariances. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1870-1877 PMLR, 2019.
Nyes Batatia, David P Kovacs, Gregor Simm, Christoph Ortnor, and Gábor Csányi Mace: Higher order cquivariant message passing neural networks for fast and accurate force fields. Advances in Neural Information Processing Systems, 35:114233 11436, 2022.
Manuele Brambilla, Eliseo Ferrante, Mauro Birattari, and Marco Dorigo. Swarm robotics: a review from the swarm engineering perspective. Swarm Intellignnce, 7(1):1-41, 2013. 0b/100.007/11772--112407777
Bert Chak Chan. Lenia: Biology of artificial life. Complez Systems, 28(3):251-28) 2019.
doi 10.20088888 Saapsss//CColexxSSeeees...... 28.32255
Angel X Chang, Thomas Funkhouser, Leonidas Guibas, Pat Hanrahan, Qixing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, et al. Shapenet: An information-rich 3d model repository. Xiv preprint arXiv: 10.11111.0000 23011, 2015.
Ricky T. Q. Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential equations. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (ods.), Aduances in Neural Information Processing Systems, volume 31. Curran nww.eiipi.nnn...na...... pdf.
Associates, Inc., 2018. URL httt::://proceednngs.oooo neuripa. cc/paper saneerrfflls/eeeeeeeeeeeeeeeeese filles/paper/221//filll 6B3ddfebbbiaaee22244466666996
Frank Cichos, Kristian Gustavsson, Bernhard Mehlig, and Giovanni Volpe. Machine learning for active matter. Nature Machine Intelligence, 2(2):94-103, 2020. doi
Claudio Collinet and Thomas Lecuit. Programmed and self-organized flow information during morphogenesis. Nature Reviews Molecular Cell Biology, 22(4):245-225 2021. doi
Michaël Defferrard, Lionel Martin, Rodrigo Pena, and Nathanaël Perraudin. PyGSP: Graph signal processing in Python, 2017. URL http:::://g.ttbb...oo///ttt-/-/-
Paul D. Dobson and Andrew J. Doig. Distinguishing enzyme structures from non-cnzymes without alignments. Journal of Molecular Biology, 330(4):771 (7837777-788, 2003. doi (00000000//5002223330))00033333
Peter Eades, A heuristic for graph drawing. Congressus numerantium, 42:149-166 160, 1984.
Sam Earle, Ozlem Yildiz, Julian Togelius, and Chinmay Hegde. Pathfinding neural cellular automata, 2023.
Wilfried Elmenreich and István Fehérvári. Evolving self-organizing cellular automata based on neural network
genotypes. In Self-Orggngging Systems, volume 6557 of Lecture Notes in Computer Science, pp. 16 25. Springer, 2011. doi 10. [0.100779978-336622-11666
William Falcon and The PyTorch Lightning team. PyTorch Lightning, 3 2019. URL httLttt//giituub.ccom com/ Lightniing-AT/ighttnii Version 1.4.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PoTorcc Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019. htw.//500//XX1.1.1....0
Joël Foramitti, AgentPy: A package for agent-based modeling in Python. Journal of Open Source Software, 6(62):3065, 2021. doi 10.21105//oss.00365
Fabian Fuchs, Daniel Worrall, Volker Fischer, and Max Welling. Se (3)-transformers: 3d roto-translation equivariant attention networks. Advances in newral information processing systems, 33:1970-1981, 2020.
William Gilpin. Cellular automata as convolutional neural networks. Physcal Review E, 100:032402, Sep 2019. 0oo0000.100//hyseeee...0...000
13

---

Published in Transactions on Machine Learning Research (04/2024)
Jonathan Godwin, Michael Schaarschmidt, Alexander L Gaunt, Alvaro Sanchez-Gonzalez, Yulia Rubanova, Petar Veličković, James Kirkpatrick, and Peter Battaglia. Simple GNN regularisation for 3D molecular property prediction and beyond. In International Conference on Learning Representations, 2022. URL
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. Proceedings. 2005 IEEE International Joint Conference on Neural Networks, volume 2, pp. 229-734, 2005. doi 1001100110//IICNNN20000 2005
Peter Grassberger and Itamar Procaccia. Characterization of strange attractors. Physical Review Letters, 50 (5):346-349, Jan 1983. doi
Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Learning graph cellular automata. In Advances in Neural Information Processing Systems, volume 34, pp. 20983 20994, 2021. URL ltttps://proceeetee Paper. pdf
David Ha and Yujin Tang. Collective intelligence for deep learning: A survey of recent developments. Collective Intelligence, (1):333331372222114477 2022. doi 10.11177/63311172221111
Emiel Hoogeboom, Viclor Garcia Satorras, Clément Vignac, and Max Welling, Equivariant diffusion for molecule generation in 3d. In International conference on machine learning, pp. 8867 8887. PMTR, 2022.
Wenlong Huang, Igor Mordatch, and Deepak Pathak. One policy to control them all: Shared modular policies for agent-agnostic control. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 4455-4464. PMLR, 2020. URL
https://prooceedings mlr, press /tress/v199/ v119/ http////119/hhaa//eee// html
Chaitanya K. Joshi, Cristian Bodnar, Simon V Mathis, Taco Cohen, and Pietro Lio. On the expressive power of geometric graph neural networks, 2023. URL https: http://paaaaeeereeeooeooooorarea ntt.:/orruum.dddRellCCC...
Diederik Kingma and Jimmyy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015. doi 10.48550/ aiv. 1412...1
Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard Zemel. Neural relational
inference for interacting systems. In Proceeding of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2688-2697. PMLR, 2018. URL https:
//proceedings.. mlr. wttp:emlm.....rsseeeeee pwtps//v///kppppppppeeppp
html
Thomas N. Kipf and Max Welling. Variational graph auto-encoders. In Bayesion Deep Learning Workshop (NIPS 2016), 2016. 10.55000 1rv..1111.000
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2017. URL httpp://opearrevieee.ee//fooorre
SJU4ayYg1
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- supervised learning. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pp. 3538 3545. AAAI Press, 2018.
Timothy P. Lillicrap and Adam Santoro. Backpropagation through time and the brain. Current Opinion in Neurobiology, 55:82-89, 89, 2019. doi 1t1.10666..ombb2211.0....0
Zachary C Lipton, John Berkowitz, and Charles Elkan. A critical review of recurrent neural networks for sequence learning, 2015. URL
Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows. In Advances Neural Information Processing Systems, volume 32, 2019. URL httpattss//proceiinggs.noot cc/
14

---

Published in Transactions on Machine Learning Research (04/2024)
Karolis Martinkus, Andreas Loukas, Nathanaël Perraudin, and Roger Wattenhofer. SPECTRE: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 15179. PMLR, 17-23 Jul 2022. URL https://proceeednngs mlr wttpppss//vv/maaatiiiiiiii
html
Nithin Mathews, Anders Lyhne Christensen, Rchan O'Grady, Francesco Mondada, and Marco Dorigo. Mergeable nervous systems for robots. Nature communications, 8(1):1-7, 2017. do1110.003//11146-0077 00109-2
Melanie Mitchell. Complexity: A guided tour. Oxford university press, 2009.
Alexander Mordvintsev, Ettore Randawzo, Eyvind Niklasson, and Michael Levin. Growing neural cellular automata. Distill, 5(2)) 2020. 10..23915 distill.00023
Alexander Mordvintsev, Ettore Randazzo, and Craig Fouts. Growing isotropic neural cellular automata. arXiv preprint, 2022. 10.155.55550/aat aivi 22...022228
Stefano Nichele, Mathias Berild Ose, Sebastian Risi, and Gunnar Tufte, CA-NEAT: evolved compositional pattern producing networks for cellular automata morphogenesis and replication. IEEE Transactions on Cognitive and Developmental Systems, (0(3):687-700) 2018. doi (0.10077TCS 2017.2377022
Rasmus Berg Palm, Miguel González Duque, Shyam Sudhakaran, and Sebastian Risi. Variational neural collular automata. In International Conference on Learning Representations, 2022. URL https://
openreview mett/forummidd77/44400BB
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Proceedings of the 39rd International Conference on Newral Information Processing Systems, 2019. 10.55555 (0.55665334422773455555
Gabriel Poyré and Marco Cuturi. Computational optimal transport: With applications data science. Poundations and Trends in Machine Learning, 11(5-6):355 607, 2019. 661110.1561/200000073 URL
Jorge Pérez, Javier Marinković, and Pablo Barceló. On the turing completeness of modern neural network architectures. In International Conference on Learning Representations, 2019. URL https:://oenrevvier het/formm21deHHyGBBo0003
Raghumathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):1 7, 2014. doi 10. 1038 (008//sdaaa... /sas/sdaaa.... 2014..2.
Ettore Randazzo, Alexander Mordvintsev, Eyvind Niklasson, Michael Levin, and Sam Greydanus. Self- classifying MNIST digits. Diställ, 5(8)2e0002 -022 2020. doi 223911/distilll00000
Craig W. Reynolds. Flocks, herds and schools: A distributed behavioral model. SIGGRAPH Compuler Graphics, 21(4):25-34 34, aug 1987. doi /1.144//444..74000
Joshua S. Richman and J. Randall Moorman. Physiological time-series analysis using approximate entropy and sample entropy. American Journal of Physiology-Hoen Heart and Circulatory Phyysiology, (2239-))H233-HH244) 2000. 1a.10.115///jphhar... 200.......0.0............
Michael Rubenstoin, Christian Ahler, and Radhika Nagpal. Kilobot: low cost scalable robot system for collective behaviors. In 2012 IEEE international conference on robolics and aulomalion, pp. 3293 3298.
IEEE, 2012. doi 01100//CCA...122..2..
D. E. Rumelhart, G. E. Hinton, and R. J. Williams. Learning internal representations by error propagation. In Parallel Distributed Processing: Explorations in the Microstructure of Cognition, Vol. 1: Foundations, chapter 8, pp. 318-362. MIT Press, Cambridge, MA, USA, 1986. 1011000555/11422.112222 URL http::/www.ce. ca. toronto. hwtp:eeetttto/aaaassseeeeeaaaaee
15

---

Published in Transactions on Machine Learning Research (04/2024)
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Dala Mining (SDM), pp. 333-341. STAM, 2021.
(601100137719781111177777
Victor Garcia Satorras, Emiel Hoogeboom, Fabian Fuchs, Ingmar Posner, and Max Welling, E((n) equivariant normalizing flows. In Advances in Neural Information Processing Systems, volume 34, pp. 4181 4192, 2021a. URL
RoWVA
Victor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E(n) equivariant graph neural networks. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 0923-9332. PMLR, 2021b. URL httpp:://proceedingg mlr press/v139/
satorras2la.
Shyam Sudhakaran, Djordje Grbic, Siyan Li, Adam Katona, Elias Najarro, Claire Glanois, and Sebastian Risi. Growing 3D artefacts and functional machines with neural cellular automata. In ALIFE 2021: The 2021 Conference on Artificial Life, 07 2021. doi 10.1162 //sal a 00451
Roberto Tamassia. Handbook of graph drawing and visualization. CRC press, 2013.
Matthew Tancik, Pratul Srinivasan, Ben Mildenhall, Sara Keii,, Nithin Raghavan, Utkarsh Singhal, Ravi Ramamoorthi, Jonathan Barron, and Ren Ng. Fourier features let networks learn high frequency functions in low dimensional domains. In Advances in Neural Information Processing Systems, volume 33, pp. 7537-7547. Curran Associates, Inc., 2020. URL htttps:/pproceedingg.. wttp:occeediinn.nnnnunnnreeeeeee www.neus..cccpppeeeeeee.e files//
pdf
Mattie Tesfaldet, Derek Nowrouzezahrai, and Chris Pal. Attention Attention-based neural cellular au- tomata. In Aduances in Neural Information Processing Systems, volume 35, pp. 8174-8186. Cur- Associates, Inc., 2022. URL httpp::/pproceeedns..eeee neurips....ppppp..... cc/paper httppaaee..elleeeaaapeeeeeeeeeee filess/paper/222/fiill/ 2ag01110000001100006666222----00
Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang, Li Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rolation-and transsation--equivvriial neural networks for 3d point clouds. arXie preprial WrXiv:1802.08219 2018.
Alan Mathison Turing. The chemical basis of morphogenesis. Philosophical Transalions of the Royal Sociely B: Biological Sciences, 237 (37()33) 1952. doi 1tt99///stb.192..000
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advonces in Neural Information Processing Systems, volume 30, 2017. URL https://procceddngs. Bf5oe2255/ddee1ff0003..ceda Papera.d..pppp............
Tamás Vicsek, Andrés Czirók, Eshel Ben-Jacob, Inon Cohen, and Ofer Shochet. Novel type of phase transition in a system of self-driven particles. Physical Review Letters, 75(6):1226-1222) 1229, Aug 1995.
John von Neumann. The general and logical theory of automata. In Abraham Haskel Taub (ed.), Collected works Design of computers, theory of automala and numerical analysis, volume V, pp. Pergamom Press, 1963.
Frederik Wenkel, Yimeng Min, Matthew Hirn, Michael Perlmutter, and Guy Wolf. Overcoming over- smoothness graph convolutional networks via hybrid scattering networks. arXie preprint, 2022.
A6o00000/00/rxxxv2222...0 220.0220000
Stephen Wolfram. Cellular automata and complesity: collected papers.
erc
Press, 2018.
doi 10. /20000001/7700194909333
N. Wulff and A Hertz. Learning cellular automaton dynamics with neural networks. In Advances Neural Information Processing Systems, volume 5, pp. 631-638, 1992. URL http://////pp
http://oocediing..uurur.s......p paper fnnerrffleee http://aappppeeoooo..oc.ooooeoe0
16

---

Published in Transactions on Machine Learning Research (04/2024)
Keyulu Xu, Mozhi Zhang, Stefanie Jegelka, and Kenji Kawaguchi. Optimization of graph neural networks: Implicit acceleration by skip connections and more depth. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 11592 11602. PMLR, jul 2021. URL https://proceedings mlr wttpsp//w/////2///./ xu21k. html
Ling Yang, Zhilong Zhang, Yang Song, Shenda Hong, Runsheng Xu, Yue Zhao, Yingxia Shao, Wentao Zhang, Bin Cui, and Ming-Hsuan Yang. Diffusion models: A comprehensive survey of methods and applications. arXiv preprint (1i::2209000796 2022.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in GNNs. In International Conference Learning Representations, 2020. URL URL http:s///ppaaneevveveeeeerrrrrrr
Kuangqi Zhou, Yanfei Dong, Kaixin Wang, Wee Sun Lee, Bryan Hooi, Huan Xu, and Jiashi Feng. Understand- ing and resolving performance degradation in doep graph convolutional networks. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, CIKM '21, pp. 2728 2737, New York, NY, USA, 2021. Association for Computing Machinery. do110..144/34556337 3482488
17

---

Published in Transactions on Machine Learning Research (04/2024)
A Pattern Formation
A.1 Implementations details
Model Let n, h and m respectively be coordinate, hidden state and message dimensionality. We set h = 16, m = 32, and n = or n =3 3 depending on the larget geometric graph. We normalise node features H using PairNorm Zhao & Akoglu 2020 Our MLPs (5,300 parameters overall) are defined as follows:
Message MLP om 2 R (cf. Equation 3):
LinearLayerr2hh + 1, m), TanH(), LinearLayer(m, m)) TanH[],
Coordinate MLP Oz :
IR R (cf. Equation 5):
[LinearLayer(m, m), TanH(), (ye 1), TanH(],
Hidden state MLP @n RR++m R (ef. Equation 7
[LineaLLayer(m h, h), TanHO, (iner,ayrr,,, h)].
using Adam (Kingma & Ba 2015 with initial learning rate 0.0005. The learning rate then decreased during training using a reduce- on-ooon--pppee pll-plateeu schedule. We use gradient clipping and weight decay as regularisation techniques. We increase the batch size during training (from minimum of to 32) batch size leads to more frequent re-initialisation of the pool states in the early training steps. We train the model to convergence, by monitoring the validation loss with fixed patience of training steps. For all details, we refer the reader to our code. All experiments are run on an NVIDIA Quadro P1000 16GB.
Training We train the model by minimising Equation 13
to promote faster convergence, and that is because small
A.2 Full trajectories & Visualizations
In this subsection, we report the full trajectories of our model for the following geometric graphs: Line
F Figure A.1 2D grid Figure A.2 an X-shaped pattern Figure A.3 3D torus Figure A.4. 3D cube Figuuee A.5) a 3D pyramid Figure A.6 3D vase Figure A.7 and the Stanford bunny | Vigure A.S Furthermore,
a visual example of the key feature anisotropic pattern formation showed in Figure A.9
18

---

Published in Transactions on Machine Learning Research (04/2024)
Tap- 224045
Aryy
Age 223247
Gar 371023
Fax 2.2002
Iw5 Far
twb fap 1.7553
tw? Avy m 144203
I-8 115480
Ieg 18252
tw10 day 232588
c-ll 00
Gay-
t-13 2n1-022936
fas 65.957
200035
(+1) 20000:00
te18 2x0-000157
te19 0.0097
t= Cau m 6.0081
[w2) Zuym 5.00055
t+ Ca- 20000
C+ 000050
fwr
Figure A.1: Convergence to a Line. We report the loss value Equation 13) in each figure. Global damage
occurs at = 25. Best viewed digitally and zoomed in.
19

---

Published in Transactions on Machine Learning Research (04/2024)
t= Cyp 178143
t=1 Ca 1.63566
t=2 Cew 1.78507
t=3 Faw 1.73248
tod Car 2.13508
C=5 Cos 2.01176
Lwy 188201
t-7 Dew 1.56206
t-8 Pew -1.3199
I-9 Eae 1.02025
1-10 Cav 0.69949
[- 11 Anv 0,44814
Dar 0,23648
1-13 Gu 0.12144
t-14 fow 0. 0.04227
t=15 Caw - 0.01308
[-16 dav 0.00684
[- 1=17 Lue 0.00424
Car 0.00305
Cow 0.002234
0.00193
Caw 2.00167
Cav 0.00141
Cave 0.00118
t= Caw 0.00101
2= 00097
Figure A.2: Convergence to a 2D grid. We report the loss value Equation 13) in cach figure. Best viowed digitally and zoomed in. Regeneration and persistency are showed Figure 2
20

---

Published in Transactions on Machine Learning Research (04/2024)
Tap-
153402
Cmb 1.75244
LwB 1.2522
109 12703
1w:00 227675
toll 00
Swe 0.1565
(+l)
18 Owr 00206
to 19 00019
t- 600500
[=2) fue 500030
t+ Caw 200LIS
C+ C=-00113
Figure A.3: Convergence to an X-shaped pattern. We report the loss value Equation 13 in each figure.
Damage occurs at t' 25. Best viewed digitally and zoomed in.
21

---

Published in Transactions on Machine Learning Research (04/2024)
Ca 2.34665
Caw 1.93509
Caw 1.9199
(=4 Lay 16504
Exp- 1.54195
Lav
Law
Lav
t= Las
Lav 0.441.0
t-13 Zun
Gwr 0.09873
1-15 Cow 0.01303
Cav 00655
t- Eac
Sav 0.00330
1- Aue 0.00300
t-20 Gur -
t-21 Gw 0.00704
Las
t-23 Eas
2= = 0.00212
25 Aur = 0.00243
Figure A.4: Convergence torus. We report the loss value Eqqatiin 13 each figure. Best viewed digitally and zoomed in. Regeneration and persistency are showed in Figure 2
22

---

Published in Transactions on Machine Learning Research (04/2024)
Coy 0.46235
[m1 Kav m 0.17075
1=2 Cav 0.17909
Lm3 Kay m 0.25101
1m4 Cav 0.27634
1=5 Kav 0.27006
cm Cas 025136
tm7 Law 021412
1=8 Cav 0:16732
tm9 Kay 0.12259
1=10 Cav 0.08785
(= Cay 0.06260
Ew 0.04214
Tw13 Gav 0.02330
1w14 Cav 0.01101
I=15 Cav 0.00489
Cav. 0.00308
[=17 Cas 0.00208
Fav
Cev 0.00107
Cav
Car
Car
Cwo 0.00072
Gev
Cow
Figure A.5: Convergence to 3D Cube. We report the loss value (Equation 13) in each figure. To avoid clutter, neirest-neighhor edges are not shown. Best viewed digitally and zoomed in.
23

---

Published in Transactions on Machine Learning Research (04/2024)
t=0 Eay 2.31566
t=1 Eay 1.74997
t=2 Cav 1.38960
t=3 Eay - 1.49148
1-d 1.72170
2-5 Pau 1.74623
t- 5 Eap 1.58399
t=7 Lov 2.46414
t Cav 2.20162
t Cav 0.89267
t- 10 Ewr 0.63538
t= Ew 0.40988
t=12 Cwy 024116
t= 13 4wy = 0.12981
t=14 Cav 0.06446
t Car 0.03484
t 16 Cm 0.02290
t.17 Ew 0.01701
= 19 Coy 0.01348
t=19 Cav = 0.01095
20 Cav 0 00927
t= 21 <wv 0.00828
t 22 <w 0.00743
t= 23 Cw 0.06708
t= 24
Cow 0.00889
t= Cav = 00004
=5 Cav 0.00720
t= Ow 0 0.00612
Figure A.6: Convergence a 3D pyramid. We report the loss value (Equation 13 each figure. Damage occurs at 25. To avoid clutter, nearest-neighhor edges are not shown. Best viewed digitally and zoomed in.
24

---

Published in Transactions on Machine Learning Research (04/2024)
t=0 Eay = 1.66911
[=1 Cav 0.50010
1=2 Cove 2.29149
t=3 Cay = 6,2036
1=d Cay 12.02967
(=5 Cuw 12,61370
t= Cow = 6.11300
t=7 Cav 2.30192
1=8 Cmv=14445 14430
t= Oww 1.05379
t= Cow 7.008
c= Ew 0.51615
12 Cowy 4.90066
t= Cow 32950
1=14 Cav 0. 18416
1= Cwv = 0.18937
t= 16 Cav 0.07968
t= Cw = 0.01961
18 Cuw = 0.00492
t=19 Cay = 0.0095
20 Cyv 00329
t= Cav 0.00302
t 22
Car 0.00330
t= 23 Gw 0.00175
24 Cow 0.00078
t= Kay 020101
25 4yw 7.2005
tm 2. Car 0.00116
Figure A.7: Convergence 3D vase from Shapenet (Chang al. 2015 We report the loss value Equation 13) in each figure. Global damage occurs at t' 25. To avoid clutter, nearest-neighbor edges are not shown. Best viewed digitally and zoomed in.
25

---

Published in Transactions on Machine Learning Research (04/2024)
t= Cow = 2.35641
t=1 Kay 155220
1=2 Cny 2. 65410
[=3 Ope 166196
1=4 Cav 1.04192
Car 2,64312
c-6 Cay 2.06859
t-7 Law 2.09006
1-8 Cnv 2,149
1-9 Cav L88903
t-10 Gre 11--1000 1.79725
t- Eay 1.40552
t=32 Cow 1.0024
1=23 Cay 0.3033
t=14 Cav 000390
t= Cav 0.0099
1= Can 0.00400
t= Day 0.00392
18 Cow 0.00319
t= 19 Cow = 00295
t0 Cyw 00277
t= Cav 0. 0.00270
t= 22 Fev 0,00205
t= Eay 0.00262
24 Cyw = 0.00258
25 4ay 00254
Figure A.8: Convergence the Stanford bunny. We report the loss value (Equation 13 in each figure. To avoid clutter, nearest-neighbor edges are not shown. Best viewed digitally and zoomed in. Regeneration and persistency are showed in Figure 2
26

---

Published in Transactions on Machine Learning Research (04/2024)
emO 1.70506
2.49139
ts10 O 0.60523
1- for 0.1146
1=20 Ean 0.00155
1=25 Eew 0.00000
to Ewo 2.70596
t= Die 2,49819
to Eoe 0.00523
15 4wo 3.01440
tw Co 0.00115
t Can 0,00098
Figure A.9: Anisotropic grid pattern formation. First two rows show the formation of 2D grid starting from a random initial state at different time steps. Last two rows show the same except that before applying the model transition rule т to go from S, to state St+1, apply random isometry to all the nodes. The image aims to show that there is no frame dependency and no awareness of global locations: The model acts as if nothing had happened since nodes are only aware of their relative positions to their neighbors. This behaviour still valid both when perturbations of the nodes occur and when more complex patterns are used (e.g. Stanford bunny), but easier to show with a simple grid. Such behaviour not possible with original GNCAs GGrattarola
2021
27

---

Published in Transactions on Machine Learning Research (04/2024)
B Graph autoencoding with E(n)-GNCAs
B.1 Implementation details
Model
We use the exact same architecture as the one detailed in Appendix
Training We train the model to minimise Equation 14 using Adam (Kingma Ba 2015) with initial learning rate of 0.0005. The learning rate then decreased during training using a reduce-on on saaice-on-llateen plateau schedule. We set the batch size to 32 and train the model by monitoring the validation loss with patience of 20 epochs. We use negalive edge sampling when computing the loss as to have balanced supervisory signal when processing sparse graphs. For all details, we refer the reader to our codc.
Testing In order to effectively evaluate the quality a graph reconstruction, we first need to binarize its soft adjacency matrix Á E [0, M]|M (ef. Equation 14p. Therefore, at test time, we fine-tune a threshold E (0, 1) on the validation set as maximize the Fl score of validation-set graph reconstructions. Once we have threshold I, binarize soft adjaceney matrices of Lest-set graphs and then compute the F1 scores thereof.
B.2
Reconstructions
Figure B.10
shows examples of test-set reconstructions from our autoencoding task (cf. sections 4.2
B.3
Persistency test
F
Figure B.11
shows the Fl-score trend over time for E(n)-GNCA autoencoders (cf. sections 4.2
C Simulation of E(n)-equivariant system
C.1
Implementation Details
Model Let n, f and m respectively be coordinate, hidden state and message dimensionality, We set / = 16,
m = 32, and n 3. Our MLPs (5500 paramoters overall) are then defined as follows:
Message MLP om 2k TM (cf. Equation 3):
[LineaLLayer (2h h + 1, m), Linearlyrrm, m), TanH());
Attention MLP oa Rm + [0, 11º (ef. Equation 8
LinearLayer(mm 1), Sigmoid()),
Velocity MLP &n B1+1 + B (cf. Equation 9
LinearLayer(m, m), TanH(), LinearLayer(m, 1), TanH(),
Coordinate MLP dx R R (cf. Equation 9
[LinearLayer(hh + 1,h/2), TanH(), LinearLayer(h/
Hidden state MLP on B + R (cf. Equation 7
LinearLayer(mn h,)), TanH(), LinearLayer(h,, hi].
Training We train the model to minimise the MSE between ground-truth and predicted trajectories, using Adam Kingma & Ba 2015) with initial learning rate of 0.001. The learning rate then decrcased during training using a reduce-on-platen schedule. We the batch size 16 and train the model by monitoring the validation loss with patience of 20 epochs. For all details, we refer the reader to our code.
28

---

Published in Transactions on Machine Learning Research (04/2024)
true edges
f1-0.99
edges
pred edges
f1-1.00
edges
pred edges
f1-1.00
true edges
pred edges
f1-0.99
true edges
pred edges
f1-1.00
true edges
pred edges
f1-1.00
true edges
pred edges
f1-0.97
true edges
pred edges
f1-0.99
true edges
pred edges
f1-1.00
true edges
pred edges
f1=0.96
true edges
pred edges
f1=0.95
true edges
pred edges
f1=0.94
edges
edges
f1=0.97
edges
edges
f1=0.96
edges
pred edges
Figure B.10: Test-set graph reconstructions at time step { = 100 for COMM-S (Ist row), PLANAR-S (2nd row), PLANAR-L (3rd row), PROTEINS (4th row) and SBM (5th row). In alternating columns, we first have ground truth graphs and then respective reconstructions with F'l scores attached on top. The position of the nodes is fixed for both ground-truth and reconstructed graphs so as to visually inspect the quality of the reconstructions. Best viewed digitally and zoomed in.
29

---

Published in Transactions on Machine Learning Research (04/2024)
1.0
1.0
0.9
0.9
0.8
f1 scooee
f1
0.7
0.7
0.6
community
planar-small
0.5
0.5
80K
90K
100k
1.0
f1 score
0.8
0.6
planar-large
60
80
90k
100k
0.9
0.9
score
0.8
fl score
0.8
0.7
0.7
0.6
proteins
0.5
0.5
100k
100K
Figure B.11: Persistency test for F(n)-GNCA autoencoders. We run transition rule for up to 100,000 time steps and report the Fl-score (y-axis) at different time steps (x-axis) for each dataset. Trends are averaged over 10 different runs. E(n)-GNCAs exhibit a persistent autoencoding trend for all datasets except SBM, which, given its clustered topology, represents the most challenging dataset.
30

---

Published in Transactions on Machine Learning Research (04/2024)
C.2
The Boids Algorithm
Our implementation of the Boids algorithm is mainly inspired by the one available in AgentPy Foramitti 2021), which in turn is based on the seminal work of Reynolds (1987). Each boid has location x E R and velocity v E R The simulation takes place a squared 3D fix-sized box. We compute the underlying graph G at each step the algorithm by connecting the boids that are within a given radius from each other. At each step of the algorithm, we sequentially apply the following transformations synchronously to all boids compute the change in each boid velocity and location:
cohesion force is applicd to bring the position of each boid closer to its neighbours;
An alignment force is applied to match the velocity of each boid to the average velocity of its neighbours;
If the distance between a boid and its neighbours is lower than a uscr-defined threshold, a seporation force is applied to steer the boid away from these excessively close neighbours;
If a boid within a user-defined radius from the bounding box, a force is applied to steer the boid towards the centre;
For each boid, the resulting force is sumined to the current velocity thus determining the new velocity;
Finally, the position of each boid is updated according the new velocity.
We show trajectories in Figure 4 For all details, we refer the reader to our code.
31


Reviews:
[{"review_id": "VQ7TOfiWEJ", "reviewer": "Reviewer_9ZGL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper is very well-written and pedagogical. The experiments are well-designed, and one of the main strength of the paper is undoubtedly the successful but challenging training of such models, with quite a lot of hacks and tricks both in the architecture itself (layer normalization etc) and in the experimental design itself (the way pools and batches are handled, updated, etc.)\n\nWeaknesses:\nAs acknowledged by the authors, the model has limited novelty: all its components were already known, and the main novelty lies in the way the layers are stacked in a recursive fashion and trained.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors introduce Equivariant Graph Neural Cellular Automata, which is an architecture combining EGNN, that is, GNN that respect additional equivariance/invariance on (part of) their node features such as equivariance to isometric transform, and NCA, which are Recurrent neural net designed to learn particular transition rules. They illustrate their models on learning pattern formation from random noise, learning Graph auto-encoders, and learning dynamical systems.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "A point that could be better explained is the potential \"scale ambiguity\" in the model, if the pairwise distance are against a trainable weight then both could be multiplied by a factor and its inverse. For instance, in the graph autoencoder part, if both x_i and delta_2 are trainable, then they could be rescaled with no change. I believe it may be handled by the various normalizations implemented by the authors to fight oversmoothing and such, but it deserves to be written.\n\nSome concepts that could also be better explained:\n- what is the \"locality bottleneck\"? Why is it important?\n- what is exactly the \"inductive bias necessary to model hidden states\" mentioned by the authors? Why are location-independent features important for these \"hidden states\"?\n\nTypo:\n- undelying (p2)", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "wEeh6WdOr5", "reviewer": "Reviewer_EyWQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper was a delight to read -- simple, clear and straight-to-the-point. The related work is clearly exposed, the paper does a good job delimiting its own contributions with respect to it, and the use of E(n) equivariance to model cellular automata is an elegant and simple idea. The experiments are diverse, relevant for the CA community, and feature nice additions (like modelling unattributed graph distributions). The results are presented in a way that is likely to be useful to researchers building up on this work.\n\nIn my opinion, the leading weakness of the work is the fact that, conceptually, it is a really straightforward application of E(n)-GNNs onto the CA domain (of course, this does not take into account the complexities of training equivariant GNNs in this domain). Hence, there is no strong core algorithmic merit to the work, and I would treat it more as applied work: an architecture was identified to have the properties necessary for GNCAs to do better, and its direct application was tested. More architectural investigations and variations -- especially those that may be more closely aligned to the CA domain would have strengthened the work's significance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this work, the authors combine prior art on designing graph neural cellular automata (GNCAs) with E(n)-equivariance constraints (following the popular work of Satorras et al.). The inclusion of E(n) symmetries into the model allows for designing an isotropic model, and one that respects the fundamental principle of cellular automata -- that all rule applications are local. Further, the paper also presents a series of benchmarks, investigations and insights on how to train such systems in a stable manner.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "As far as TMLR is concerned, I think this paper is an open-and-shut case. It presents research that has a clear audience (the CA community), with convincing results, and has no outstanding issues with clarity.\n\nHence, my recommendation will be to accept the paper.\n\nThat being said, if the authors would want some ideas for improving the work further---or inspiring future work---here are a few suggestions:\n\n* E(n)-GNNs from Satorras et al. offer only one solution for satisfying E(n)-equivariance, and one that is rather ad-hoc. It would be interesting to see how more exhaustive approaches (e.g., the SE(3)-Transformer) would perform as a base model in this setting. _[Note that SE(3)-Transformers have a notion of neighbourhood, so they would not violate locality.]_\n* In my opinion, algorithmic execution tasks may be seen as related to CA---especially if the execution operates over a neighbourhood. It might be interesting to see how the proposed architecture performs on some tasks in the CLRS-30 benchmark. Further, recent work on this benchmark, such as G-ForgetNet (Bohde et al., ICLR'24; https://openreview.net/forum?id=Kn7tWhuetn) explicitly call out and leverage the Markovian property of execution tasks, meaning they may be relatable here as well.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Qeqr1IDWXI", "reviewer": "Reviewer_fNG5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is clearly written. I enjoyed the introduction which presents CAs, GCAs, GNNs and E(n)-GNNs. Though, I am familiar with all these topics (except for GCAs) -- and indeed I found the part on GCA less clear, probably because I didn't know about them beforehand.\n- The proposed approach seems to truly address the learning of a local rule, by a local-only (and isotropic) model. This is especially convincingly shown on task 3 (section 4.3).\n- The building of GNCA seems at first like a low-activity niche topic. However, I feel that this work has broad concrete applications (as I suggest below, for learning real-life active matter rules)\n\nWeaknesses:\n- The losses used (in task 1 and 2) are non-local (involve all pairs of nodes), contradicting some of the claims. See requested changes.\n- The losses used (in task 1 and 2) break node-permutation equivariance, contradicting some of the claims. See requested changes.\n- Some definitions are not provided, making the paper not self-sufficient, and a few other informations are not provided. See requested changes.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper addresses the learning of local Cellular Automaton (CA) rules by Neural Nets (Neural CA, NCA) by combining recent ideas:\n- Graph NCA (as opposed to NCA that operate on grids)\n- E(n)-equivariant GNNs, and in particular the EGCN layer, that are E(n)-equivariant operations, that produce  E(n)-equivariant output.\n- A simple graph-attention mechanism (preserving equivariance) is used for an experiment.\n\nRoughly half of the paper is used to introduce these recent ideas, and the other half to present results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "## Critical adjustments:\n- after Eq (12): when using $E(n)$ and not $SE(n)$, i.e. when including reflections, it is a bit confusing to call $\\psi$ \"*rigid transformation*\". Usually, the term \"*rigid motion*\" refers to elements of $SE(n)$ (also denoted $E^+(n)$). You could use only the term isometry, which refers to both direct and indirect isometries (chirality + or -). Note: \"*rigid transformation*\" appears again in page 7.\n- \"*these properties are a consequence of only processing relative distances and never being aware of absolute node locations*\". Here I would replace \"*relative distances*\" (Scalars) with \"*relative positions*\" (vectors of $R^n$). In the current form, there is a mistake. Equation 3 (as in Eq (3) of Satorras) is indeed independent of positions and only depends on relative distances (scalars). However, and this is crucial to obtain an equivariant layer (which is strictly more expressive than an invariant one), the relative orientation must be taken into account, as it is the case in Eq (5) (eq (4) of Satorras).\n- the graph auto-encoding task (that I am not familiar with) is not presented in a sufficiently pedagogical manner that the paper would be self-sufficient. In the current form it seems the reader has to go read other paper(s) to understand what are these experiments (section 4.2) about.\n- section 4.2, \"*For a fair comparison, we do not allow underlying fully connected graphs, as opposed to Satorras et al. (2021b)*\" I do not understand how the comparison is fair. First, using $25<t<35$ is effectively similar to using 35-layered (Reccurrent) NNs. Comparing a RNN and a feed-forward 4-layers numerical network is not obvious, but that's the spirit of your original approach, so that point is fine, although it's not obvious how many layers should be allowed. Maybe the number such that the number of parameters would be equivalent. The search for and discussion about what is a \"*fair comparison*\" should be extended.\n- (Very important) The loss functions (Eq 13, 15) are implicitly fully-connected-like losses, because they involve all pairs of nodes. Although the single-node output of one iteration step is only computed from the values at the nodes and from the (relative) positions of that node's neighbors (and their features), the parameters updates involve a global knowledge. In other words, although the model (the graph-features update) is strictly local, the teaching is made with global supervision. This kind of subtlety should be addressed (maybe not in sec 4.2 but before, e.g. sec 3). At least, providing the losses early on (sec 3?) could help the reader have a better sense of how E(n)-GNCA works in practice.  This is a crucial point since the conclusions state that \"*All our experiments are designed to answer the crucial question underlying CAs: How can we design a CA transition rule that behaves according to some high-level specification (e.g. forming a grid)?*\"\n- As far as I understand, the loss for the 3rd task (by far the most interesting, in my opinion) is indeed truly local. The (sadly, unnumbered) equation towards the end of page 10 seems to only involve node-related costs, that are simply summed over the graph (since we have weight-sharing over nodes, this global aggregation is of course ok). I think the difference with the 2 previous tasks should be stressed, as it is a crucial claim of the paper (that one can learn strictly local rules -- implicitly, through local learning).\n- (Very important) Still about non locality of the losses (13) and (15): I also note that such losses break node-permutation invariance. For instance, in task #1, with eq (13), if I start from the perfect Stanford bunny and swap two nodes, the loss is no longer 0 and the network will attempt to reverse the swap. This is not intuitively what the task is supposed to be: rules are not purely local, each player as a pre-defined role. This should be discussed somewhere. This is also true for Eq (15), as far as I understood this task. On the contrary, task #3 respects the node-permutation symmetry, which is excellent. So again, the claim that rules are local is impeded by the non-locality of the losses used (supervision has a global blueprint, and does not occur through local rules only --except for task #3). I note that currently this is somehow alluded to at the end of the paper: \"*the 1-to-1 correspon-dence between initial nodes and target nodes is a non-optimal design choice as it leads to abrupt dynamics especially in the first time steps.*\", but the issue is presented as a mere computational issue.\n- An important point of clarity: the connectivity of the graphs in 4.1, 4.2 are not provided. Are the GNN fully connected networks ? Or is connection based on distance ? But distance changes over the course of iterations.. so which one is used for back-propagation ? In 4.3, it is specified: \"*The graph G is obtained as a fixed-radius nearest neighborhood of the nodes at each time step—G changes dynamically over time.*\" But in practice, what is the radius used ?\n\n\n### Non critical but suggested changes:\n- it is mentioned quite late in the paper that an attention mechanism will be used for task #3. It think this can be considered as important.\n- section 1 and 2 are rather clear, although it was not instantaneous for me to understand what NCA (or GCNA's) are meant to do/how they operate in practice. In particular I was wondering: on what kind of training data do they learn ? I initially though they could learn the local rules (or rather a NN approximation of them) from observing a simulation of a cellular automaton. This is confirmed by your sec 4.3, but is quite different from the experiments 4.1 and 4.2. Probably you could clarify this by presenting a typical use case of NCAs, specifying in particular what is the training data, how training is done if it's not obvious, and how test performance is evaluated (if it is not trivial).\n- why specify that NodeNorm and PairNorm are \"*parameter-free normalisation techniques*\" ? Why is that important for this work ?\n- When referring to more evolved rotation-equivariant GNN schemes (you cite Joshi et al., 2023), I think you could refer to Tensor field networks (Thomas et al 2018), to the e3nn library, and maybe also to the recent MACE paper, *MACE: Higher order equivariant message passing neural networks for fast and accurate force fields*). The networks one can build with such layers are much more expressive than the original GCN-layer based networks.\n- Table 1: provide the number of parameters for each model ? And maybe also the training time. And also memory footprint. Ideally, CO2 footprint when known.\n- the sample entropy and correlation dimensions are not defined. Although they can read from Wikipedia, it is necessary to define them at least in the appendix of the paper, and provide some intuition about what they compute. Currently it is simply stated that they are \"*two measures of complexity for real-valued time series*\". In practice indeed they seem characterize sets of time series (or clouds of points for CD). I guess the Lyapunov exponent could also be reported.\n- About sample entropy and correlation dimension: Having equal or very similar SE and CD is a necessary but not sufficient condition for the time series to be very similar. Although Fig.4 is quite convincing, a more direct comparison, e.g. even the MSE at 1 iteration averaged over a large number of initial configurations, would be a simple measure, where various models could be compared.\n- The term \"*Broader Impact*\" has been used in a different way than intended by TMLR, I suppose. Maybe \"Broader Scope\" would be better.\n- In terms of Broader Scope (I may be naive since I am not familiar with recent works in GCA/CA/NCA), I would have added the potential use to model real systems and in particular active matter, e.g. biological systems (e.g. cells assemblies) that we know respect local rules, but for which we do not know the rules. That is, from observed time series, infer the rules using GNCAs rather than a time-consuming expert hand0cerafting of the rules. In this sense the goal is not to reproduce some designed behavior but rather to have a reduced-order model, that can then be used to probe unseen situations (less costly test than actual experiments).\n- the location of fig 4 seems wrong: it appears before table 1, although table 1 refers to sec 4.2 and figure 4 refers to sec 4.3.", "broader_impact_concerns": "None, we are far from a recipe to design a killer-bots swarm. Rather, by observing one, this algorithm may help figure out its functioning.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper has been praised by reviewers and clearly deserves to be published at TMLR. Congratulations!
Decision: Accept (poster)