Learning Graph Cellular Automata
Authors: Daniele Grattarola
Lorenzo Livi
Cesare Alippi
Venue: NeurIPS 2021 Poster (2021)
Keywords: cellular automata
graph neural networks

Abstract: Cellular automata (CA) are a class of computational models that exhibit rich dynamics emerging from the local interaction of cells arranged in a regular lattice. 
In this work we focus on a generalised version of typical CA, called graph cellular automata (GCA), in which the lattice structure is replaced by an arbitrary graph. 
In particular, we extend previous work that used convolutional neural networks to learn the transition rule of conventional CA and we use graph neural networks to learn a variety of transition rules for GCA. 
First, we present a general-purpose architecture for learning GCA, and we show that it can represent any arbitrary GCA with finite and discrete state space. 
Then, we test our approach on three different tasks: 1) learning the transition rule of a GCA on a Voronoi tessellation; 2) imitating the behaviour of a group of flocking agents; 3) learning a rule that converges to a desired target state.

Learning Graph Cellular Automata
Daniele Grattarola Università della Svizzera italiana grattd@usi.ch
Lorenzo Livi University of Manitoba
Cesare Alippi
Università della Svizzera italiana Politecnico di Milano
Abstract
Cellular automata (CA) are a class of computational models that exhibit rich dynamics emerging from the local interaction of cells arranged in regular lattice. In this work we focus on a generalised version of typical CA, called graph cellular automata (GCA), in which the lattice structure is replaced by arbitrary graph. In particular, we extend previous work that used convolutional neural networks learn the transition rule of conventional CA and we use graph neural networks to learn a variety of transition rules for GCA. First, we present general-purpose architecture for learning GCA, and we show that can represent any arbitrary GCA with finite and discrete state space. Then, we test our approach on three different tasks: 1) learning the transition rule of a GCA on a Voronoi tessellation; 2) imitating the behaviour of a group of flocking agents; 3) learning a rule that converges to a desired target state.
Introduction
Cellular automata (CA) [ discrete computational models that consist of a regular lattice of cells, each associated with a state, and a transition rule. The transition rule is usually defined to update the state of each cell as function of its current state and the state of its neighbours. Even when using simple transition rules and low-dimensional lattices, CA can exhibit very intricate patterns that emerge from the repeated synchronous application of the transition rule. Despite being almost century-old idea, many different forms of CA are still studied today in dynamical systems theory ( In this paper, focus a generalised version of CA called graph cellular automata (GCA) which relaxes the assumption of the lattice structure and allows cells to have an arbitrary and variable number of neighbours.
Starting from the observation that GCA are a generalised version of lattice-based CA, in which the underlying lattice is replaced by an arbitrary graph, focus on the analogous parallel that exists between convolutional neural networks (CNNs) and graph neural networks (GNNs) 4 6) Namely, the goal of this paper is to study the application of GNNs learn desired GCA transition rule, setting that we refer to as Graph Neural Cellular Automata (GNCA).
The inspiration for this work comes from recent series of papers that studied how to train convolutional neural network to approximate desired CA transition rule, which we extend two significant ways. First, present general-purpose architecture for GNCA and show that it is sufficient to represent any arbitrary GCA with finite and discrete state space. Based on well-known results on the expressive power of neural networks and GNNs, also propose that the same architecture is expressive enough to represent any transition function on continuous state spaces. Then, present several classes of problems that can be formulated as computation with GCA. We use our architecture to learn a varied family of GCA with non-trivial features including discrete and continuous state spaces, complex unknown transition rules, dynamic graphs, and the ability to globally coordinate through local message exchanges. First, we train a GNCA to approximate a GCA defined on the Voronoi tessellation of random points, where the underlying graph fixed throughout the evolution of the system and the state space is binary. Then, we focus on a dynamic GCA with
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

P2 0.5
D.8G
Switched
MLP
MLP
0.66
Swisched
Pre-preeess
Message passing
state
P5
Switched
(a) Schematic view of GNCA computation.
(b) Voronoi GCA transition.
Figure I: (a) Schematic view of the GNCA computation. The central block represents the pesssag-passsngg function of Eq. (4) (b) Example transition of a Voronoi GCA with binary states (represented by colours) and transition rule as described in Eq. (5) with 0.6. Cells with neighbourhood density pi switch state.
continuous state space and variable connectivity between cells. We consider the Boids algorithm [7]. a Markovian and distributed multi-agent system designed to simulate the flocking of birds, and we train the GNCA to reproduce its behaviour. Finally, we consider the task of learning GNCA that converge to a target state in a continuous state space. Specifically, we train the GNCA to reconstruct the coordinates of a geometric point cloud.
The practical implications of this work are evident when considering that distributed systems are the norm in nature, where complex behaviour is observed as an emergent property of simple and distributed computation, and 2) ubiquitous in technology, with the advent of cyber-physical systems that need to operate and react to local events while coordinating to achieve a target behaviour (for example, self-driving cars that act locally to avoid crashes but must prevent traffic globally). By applying GNNs to model GCA on systems described by graphs, we enable the discovery of unknown rules that allow us to solve tasks through emergent and distributed computation.
2
Related works
This work extends the results of many foundational works on learning CA with neural networks, which so far have only focused regular lattices.
seminal work on the subject is that of Wulff and Hertz 8 who successfully trained small neural network (NN) to imitate 1D and 2D binary CA with chaotic or complex dynamics.
subsequent approach is that of Elmenreich and Fehérvári ()) who designed an evolutionary algorithm to identify a NN transition rule that would generate a desired pattern (a process called mor- phogenesis). Similarly, Nichele et al. (10) used the NEAT genetic algorithm [TT] and compositional pattern producing NNs [12] for morphogenesis and pattern replication in CA with discrete states.
Recently, Gilpin 1 showed how implement any CA transition rule using the receptive field of CNN, as well as showing that arbitrary binary rules can be learned end-to-end with gradient descent. In follow-up analysis, Springer and Kenyon [14] observed that CNNs often fail converge exact solutions when trained to reproduce the Game of Life ruleset and that they often require many more parameters than the minimal number necessary to implement the exact transition rule, as predicted by the lottery ticket hypothesis [15]. The idea of learning 2D CA transition rules was also explored by Aach al. (16), who proposed an encoder-decoder architecture with the ability to generalise to unseen neighbourhood configurations and sizes.
Mordvintsev et al. [17 recently introduced Neural Cellular Automata (NCA). The idea of NCA is to use CNN to learn the transition rule of a 2D CA with a continuous and mulli-dimmnnsooall state space, which they interpret as image. In particular, they trained the NCA to converge to specific image. They showed that, with proper training, NCA could reconstruct missing patches of the target image and were resilient to many classes of state perturbations. Randazzo al. (18) also showed that NCA can be used to classify MÑIST digits. This is an example local behaviour leading to a global agreement about the overall structure of the system.
Since a CNN can interpreted as particular case of a GNN with fixed-size neighbourhood and anisotropic filters, what propose here is a general extension of the works mentioned above.

---

3 Method
3.1 Graph Cellular Automata
A GCA is a 4-tuple (G,S,N,T) where G = (V, E)) is graph with node set V ([V) = n2 and edge
set E V x S S the state set, N V 2 is the neighbourhood function s.t. (V = (j
(j.i) E F), and r is local transition rule. Let E S indicate the state of node i. The transition rule then defined as
T(S)) : {s:) (sy |j E s/s
(I)
For brevity, we denote with S E S the state configuration for the entire automaton and we write S' == (S) to indicate the synchronous application
to all cells.
The original CA formalism allows for transition rules that can treat the different neighbours of a cell differently, according their position with respect the cell. This idea is, for instance, at the base of the Wolfram code for enumerating CA transition rules [19]. In GCA similar anisotropic behaviour can be obtained by uniquely enumerating the neighbours of each cell and adapting the transition rule accordingly. More generally, we can assign to each edge (i, E E an attribute eij E Rd encoding, for example, the direction, distance, or unique identification of node relative node j. is also possible to consider any arbitrary attributes associated with edges, representing abstract relations between any two neighbouring cells. short, we can see anisotropy in GCA as dependence of the transition rule on the specific relation that exists between a cell and neighbour:
(s.) { U (sy, e jj E (N)) + s.
(2)
The usefulness of this definition will become evident in later sections.
3.2 Graph Neural Networks
Graph Neural Networks (GNNs) are family of models designed to process graph-structured data. The core functionality of many GNNs can be described with a message-passing scheme. Let h; E gd represent vector attribute associated with the 7th node of a graph and eij E Rd. an edge attribute as defined above. A meessag--passing GNN is a function that computes a vector hf R according to the following scheme:
hy 7 (b,, (ev & hy, Czi))
where Φ the message function, D permutatiin-iinvarian operation aggregate the set of incoming messages, and is the update function. When Φ O. and are differentiable opera- tions, message-passen layers can be stacked and their parameters can be learned end-to-end with backpropagation and stochastic gradient descent.
In this work, specifically, we adopt a message-passing architecture inspired by You et al. 20 s.t.
h h,
ReI.U(Wh; + +b), JEN(()
Σ
(4)
where || indicates vector concatenation, ReLU is the Rectified Linear Unit activation, and W R24 xd. and b IR are trainable parameters. The message-passing block also preceded and followed by multi-layer perceptrons (MLPs) with ReLU activations, whose task is to learn non- relational transformations of the node features (20). The architecture is schematically shown in Fig. Tal Note that Eq. (4) can easily be extended to account for edge attributes as well, although we will see later sections that different use cases may benefit from different ways of incorporating that information. We mention two main techniques to achieve this kind of anisotropy. both based on making the message function & edge-dependent: 1) the weights matrix W can be computed as a function of ey,. through a kernel generating network (21) and 2) eys can be concatenated to h, to compute the messages.
3.3 Graph Neural Cellular Automata
The goal of this paper is to explore the parallel that exists between GCA and GNNs. In particular, here we consider a setting which the state transition function of generic GCA implemented with GNN, which we indicate as Graph Neural Cellular Automaton (GNCA).
3

---

The relation between the two models can be immediately seen by comparing Eqs. and (3), as the GNN model contains all the necessary elements to describe GCA transition rule. First, when so that d₁ = d/ then both functions are endomorphisms that depend only on node and its neighbourhood (i). Then, by considering S = Rdh the state of the GCA can be interpreted as a graph signal s.t. h. = s;- Finally, as previously mentioned, the GNN can be configured to take into account edge attributes, allowing it to model transition rules that can be both isotropic or anisotropic. We also note that CA rules with larger neighbourhoods (e.g., the Lenia CA (22) can be implemented by our GNCA by stacking multiple message- message-passing layers or by re-defining the neighbourhood function to include higher-order neighbours. This will be explored in future work.
the GNN is configumg
We indicate with r(S) the transition function of a GCA and with Ta (S) the transition function of a GNCA with learnable parameters 0. The dependency of either function on graph 9 is left implicit. Finally, we use
indicate the states' dimension. The specific GNN architecture of To that we consider in Eq. besides being motivated by the results of You et al. (20, has sufficiently high number of parameters which, as noted by Springer and Kenyon [4, can be a deciding factor for learning the transition rule of a CA. This requirement is also somewhat reflected by the architectural choices of Mordvintsev et al. 17
Implementing GCA with M-state space One of the main results of Gilpin 13 was to show different ways to implement an arbitrary Mtstee CA with a CNN. The most straightforward imple- mentation proposed by the author relied on two main neural computation blocks:
1. Two convolutional layers with 1x1 filters, to compute a one-hot encoding of the states;
2. One convolutional layer with 3x3 filters, to match all of the possible input patterns of the transition rule and compute the corresponding output.
The general principle used to design the transition rule of a CA with a CNN can be straightforwardly extended to GCA and GNNs. Consider GCA with state space S {1, M.. and n cells, with maximum node degree dmazz I n (and, usually, dmaz < n).
The first block of Gilpin's ' implementation remains the same, since it is a transformation applied individually each node, independently of its neighbours. The second block requires us to be more careful. First, we note that Gilpin's implementation covers the most general case in which the transition rule is anisotropic. By generalising this principle to the case of GCA, as discussed in Se.. we require that each cell has up to dmaa neighbours identified by unique one-hot vector edge attribute. The pattern matching mechanism proposed by Gilpin can then be implemented with bank of dmea weight matrices of shape M x M Mdmos, that is used to compute the message from each neighbour, according to its associated edge attribute (e.g., consider the work of Simonovsky and Komodakis (11).
We note, however, that this case represents an upper bound in complexity, since many GCA rely on isotropic rules and better implementations can be obtained if the structure of the GCA rule is known. For example, Conway's Game of Life can be implemented with CNN consisting of one convolutional layer with 3x3x5 filters, with one channel to implement the identity and four channels to count neighbours, and two convolutional layers with 1xIx5 filters for pattern-macching 13.. We note that the GNCA covers this result as it natively implements the identity (the concatenation of Eq. 44) can be replaced with a sum to match the exact implementation and neighbour counting can be achieved with W = [1, 1, 1] and b [-1, 2, -3, -4] (ef. [13 Appendix A)). Finally, the 1xlx5 convolutional layers are equivalent to the post-processee dense layers described in Sec. 3.2
In Sec. we will see a similar minimal implementation for an outer-totalistic GCA.
Extension continuous state space We can also conjecture that the architecture described in Sec. Sec.3.2 is expressive enough to represent any transition function for GCA with continuous state space. First, it is a well-known result of machine learning theory that two-layer MLP, when appropriately configured with a sufficient number of neurons, is a universal approximator for any Borel measurable function. The pre-processing MLP of the general GNCA architecture is therefore sufficient to compute any desired representation of the states. Then, building on the results of Zaheer et al. [23], we can also see that the structure of the GNCA allows us to model any permutation invariant function of the neighbours. Finally, by concatenating the representation of a node to the

---

1.5
He
Pg
10-4
Voli
Troin
Train Vilid
1.5
2.0
Entropy
1.0
10-1
0.8
Eskmayy
1.0
0.7
0.5
0.6
0.5
10-7
0.5
0.0
0.25
10
10'
Epach
Spoch
(a) Entropy vs. R.
(b) Loss.
(c) Accuracy.
(d) Entropics vs. training.
Figure 2: (a) Shannon He and word Hy entropy vs. threshold for the Voronoi GCA. The edge-of-chaos
transition is marked at x = 0.4. (h) Median training and validation loss of the GNCA, (c) Median training and validation accuracy of the GNCA Entropy of the GNCA as training progresses. The two "x" indicate the real entropy values of the target Voronoi GCA.
representation of its neighbours and giving the result as input to the post-processing MLP, we are also able to compute any transition to the following state. Of course, these results are conditioned on the two MLPs being sufficiently large, and there are no guarantees that the training algorithm will be able to identify the correct function.
4 Experiments
We now consider different experiments aimed at showcasing the capabilities of our GNCA architecture. We take inspiration from the literature learning lattiee-bsse CA to design three experimental settings with different goals. First, we show a basic application to confirm that the GNCA is indeed capable of learning desired GCA transition rule via supervised learning. Then, we extend this setting to a more complex case in which the state space is continuous and the underlying graph is dynamic, demonstrate the applicability of the GNCA to multi-agent systems modelling. Finally, we consider the task of learning an unknown transition rule simply by specifying the target behaviour of the GNCA. Specifically, we extend the work of Mordvintsev al. [17] the GCA case and train our GNCA to converge to desired state. Here we report a summary of the experiments and refer the reader the supplementary material for more details.
4.1 GNCA on Voronoi tessellation
We begin by studying binary GCA with density-based transition rules and threshold dynamics 24 and for which & is given by the Delaunay triangulation random 2D point cloud. The cells of this type of GCA are the cells of the Voronoi tessellation of the points. Let S {0, 1} be a binary state
space, P:-
[+] Σ Sj the neighbourhood density node, and x [o, 1] threshold, then the
JEN(1)
GCA rule is given by:
Si:
if if >
(S:)
=
(5)
An example transition such Voronoi GCA is shown in Fig. lb
The goal of this experiment is study the base case in which G is static and planar, which is the simplest extension of typical outer-totalistic CA (like the Game of Life) to the setting of an irregular arrangement of the cells. Having a binary state space simplifies the problem and allows us treat this as a node classification task.
Measures of GCA complexity Following the method of Marr and Hütt we quantify the complexity of our finite-state GCA using two entropy measures, estimated from the sequences of states observed by repeatedly applying transition rule. The average Shannon entropy is defined as H. Σn= 1 P loga P, where pt is the empirical probability that node is in state s. The
For Figs. 2b and 2c the curves have some significant outliers and therefore, instead of the mean and standard deviation, report the median and the median absolute standard deviation interval over 5 runs
5

---

- - logz p'),, where P is the number of constant words of length (for any state) found the state sequence node When combined, these two measures are informative enough to separate GCA into the four Wolfram classes of CA complexity
average word entropy is H = E (Ei=1
24 As shown in Fig. 2a the Voronoi GCA considered here has a sharp edge-of-chaos transition 25 at around k 0.4, above which the CA switches to non-chaotic dynamics. This is marked by a sharp decrease in Shannon entropy and by reaching peak word entropy (which indicates the occurrence of interesting patterns of states). In the following experiments, we consider 0.42 it exhibits both non-chaotic and non-trivial dynamics.
Training We start by computing G as the Delaunay triangulation of = 1000 random points sampled uniformly in [o, 1] x [0, I]. We generate training examples for the model by sampling mini-batches of 32 random binary states [S ,..., S(32), ((A) E S", and we train the GNCA by minimising the negative log-likelihood between the true successor states 7 (S(()) and the predicted next states TO (S()).
Results Figs. 2b and 2c show the evolution of the GNCA's loss and accuracy on the training and validation sets, averaged over 10 runs. We see that the model quickly converges to a near-perfect approximation of the transition function and that the loss continues to gradually improve even after reaching 100% validation accuracy. Fig. 2d shows the Shannon and word entropies of the model as training progresses. To evaluate the entropy at each training epoch, the GNCA is evolved autonomously (i.e., feeding its predictions back as input) for 1000 steps and the two entropy measures are computed from the observed state trajectories. Note that the GNCA's predictions are rounded to or during inference. This analysis lets us comment on two aspects. First, the GNCA able to quickly learn transition function with very similar entropy to the true transition function (marked with an "x" in the figure), although takes a while to reach the exact target values. Second, we see that the GNCA eventually learns robust approximation of the true transition function, which does not diverge from the true trajectory when evolved autonomously.
Minimal exact implementation As discussed in Sec. 3.3 when the form of the transition rule is known, it is often possible to provide a much more compact implementation of the GNCA. For the rule described in Eq. (5). we can see that the GNCA has to implement (or learn to implement) two main operations: calculating the density of alive neighbours and mapping the state to its successor as a function of the state itself, the density, and the threshold k. The first step can be achieved with minor modification to Eq. (4) to use an average aggregation instead of the sum, and by setting W = and b = 0. Alternatively, it is also possible to keep the sum aggregation and set W = [1.0] 0). b [0, 1] (one neuron to count alive neighbours, and one to count all neighbours), although this requires an extra neuron in the following block. We also remove the pre-processing MLP since the states themselves are enough compute the required representation. Then, the transition can be computed with the post-processing MLP of the GNCA. As shown in Fig. 3 we see that the transition rule of Eq. (5) is essentially equivalent to the famous XOR problem 26 27 and can therefore be solved with a MLP with 2 hidden neurons and one output neuron. We empirically trained one such architecture with ReL.U hidden activation and sigmoid output (mimicking the structure of the full post-pree post-processing MIP described above) and found that one possible solution is given by the following set of weights:
Density
0.5
0.0
Ourrent state
Figure 3: GCA rule of Eq. (5) Colours in- dicate the output: grey is O, orange is
- 1.98
1.64 -2.8
W
b [-4.6 0.17];
W2 10-33. [3.3 3.3); b2 [1-1.]]
2.63
4.2 GNCA for based modelling
Our second experiment consists of learning GCA with continuous state space and in which the connectivity between cells changes over time. Specifically, we take set of cells whose states represent their positions and velocities on a plane, G is dynamic graph given by a fixed-radius neighbourhood of each cell at each step, and the state of the cells is updated with the Boids algorithm 77]. This setting is more general than the previous two experiments, since G is now dynamic graph, and possibly more realistic approximation of many real-world phenomena. We still consider this

---

Train
vald
0.06
x
SampEn
0.04
X x
8
0.02
10.
GNCA
0.5
GNCA
0.00
20
40
60
80
20
60
80
Epoch
Epoch
Epoch
(a) Loss.
(b) SampEn and CD vs. training epoch.
(c) Examples of flocks.
Figure 4: (a) Average and standard deviation of the training and validation loss of the GNCA (5 runs). (b) SampEn and CD of the GNCA as training progresses. The horizontal lines indicate the true values the target hoids GCA. (c) Examples of flocks forming in the true boids system (purple) and the learned GNCA (yellow).
kind of CA since the characterising feature of CA is that the transition function depends cell's neighbours and is Markovian, although this setting is better described as a generic multi-agent system.
The transition function of the Boids algorithm is highly non-linear and is summarised in Al-
Algorithm 1: Pseudo-code for Boids 77..
gorithm (see the supplementary material for
Input: n. of boids; T: n. of steps;
details). Briefly, at each step, the velocity of each boid is updated and its position changes
for < 1 to n do
Initialise random Pa V; R
accordingly. The new velocity of each boid is
3 end
computed as function of its current velocity
for + 1 to T do Compute neighbours
and the positions and velocities of the neigh-
5
bours. Finally, some constraints on the max- imum speed and turn angle are enforced, as well as a soft-boundary condition that pushes the boids away from the edges of the simula- tion box.
for i < 1 to do if p. is close to boundary then as Steer away from boundary
end
10
a, f Avoid collisions with (i
11
a, - Align to velocity of N(i))
Training To train the GNCA we generate trajectories by letting 100 boids evolve for 500 steps, starting from randomly initialised posi- tions and velocities. We generate 300 trajec-
12
a. f Align to position of A(i))
13
+ a, + a. a
14
V; < V; + a;
15
Enforce speed and turn limits
tories for training. 30 for validation and early stopping. and 30 for testing the final perfor- mance of the GNCA. The model is trained, like the previous case, to approximate the true transition 7 r(S).
16
pj f- p. + V;
end
end
Table I:
Complexity measures for the true Boids system and the trained GNCA.
Results One key aspect of approximating a continuous- state GCA is that errors in the prediction will quickly accumulate, making almost impossible for the GÑCA to perfectly imitate the true system. For this reason, despite quickly reaching a training, validation, and test error in the order of 10-7, the GNCA cannot perfectly approximate the true trajectory of the target GCA when evolved autonomously. However, we can evaluate the quality of the learned transition function by using the sample entropy (SampEn) (28 and correlation dimension (CD) [29), two measures of complexity for real-valued time series. Table | compares the SampEn and CD of the true Boids system with the trained GNCA, computed from trajectories of 1000 steps and averaged over all boids and random initialisations of the system. We see that both systems have very similar complexity measures, indicating that their behaviour is generating comparable amount of information and is therefore similar. We report in Fig. 4b) an example of how the SampEn and CD change as the GNCA trained. Additionally, we see that the GNCA learns a flocking behaviour similar to the target system (shown in Fig. 4c). although with smoother and less precise trajectories. Notably, we observed that the GNCA has no trouble in learning the soft-boundary condition. We include videos of the GNCA trajcctories supplementary material.
SampEn
Corr. dim.
True GNCA
0.0369 0.0033
1.3125 + 0.44
0.0302 0.0079
1.3017 0.336
7

---

10-2
10a
10
40
Grid, GNCA trained with 10, example periodic behaviour
St.6
10t2
10-1
ENTOr
40
Bunny, GNCA trained with 20, example periodic behaviour.
Stop
10-1
Enror
10-2
CSP GSP
CSP
10-1
10-4
102
Logo, GNCA trained with 20, example of convergence.
9tep
10n2
Error
10--
10>
Minnesota, GNCA trained with [10, 20]. example of convergence.
10-4
Enror
100
10"
(e) SwissRoll, GNCA trained with E [10, 20), example of convergence.
Figure 5: Each row shows the state trajectory of the trained GNCA for 20 steps, starting from S. The plots to the right show the mean squared error between the current state and the target. complete list of figures for all graphs and is reported in the supplementary material.
4.3 GNCA that converge to fixed target
For our final experiment, we extend the previous work of Mordvintsev et al. [77 and study a setting in which GNCA is trained to converge specific target state from given initial condition. We consider several geometric graphs available in the PYGSP library [30] (BSD 3-Clause license), and set the target state to be the 2D 3D node coordinates, while G is kept fixed.
The goal of this experiment is twofold. First, we wish to study the setting in which the transition function that we are trying approximate is unknown. Second, and more importantly, our goal is to show that the GNCA can learn local transition rules that result global coordination of the cells.
Training The main challenge in this experiment is to make the target state an attractor of the GNCA. In other words, let S. S Raxd be the initial and target states, respectively, we wish to learn Tp s.t. (S) + S. Here, we consider as initial state normalisation of the target s.t. 8; = $:/1|&./|. Other normalisations or random positions are also possible. Note also that, for simplicity, we assume I-to-1 correspondence between each node and its target state.

---

Table 2: Type of attractor and minimum error reached by the trained GNCA, trained with different values for
Grid2d
Bunny
Minnesofa
Logo
SwissRoll
Type
Error
Type
Error
Type
Error
Type
Error
Type
Error
Periodic
1.52-10-
Periodic
4.19.10 5
Converge
1.26- 6
Periodic
7.35-10 9
Periodic 1.09-10
-- 20
Periodic
3.66 10
Periodic
2.18 18-1
Converge
1.72 10-
Converge
3.75-10-3
Converge 6.26-10
6 [10.20)
Converge
1-9-10-6
Converge 9.76-10-*
Converge
1.29. 10
Converge
2.49-10
Converge 1.33-10
To train the GNCA, we apply the transition for a given number of steps and use backpropagation through time (BPTT) to update the weights, with loss K " (+)(4) - $)2 for mini-batches of size K consisting of states ((k) for k = l,.... K. This ensures that the GNCA will learn to converge the target state in t steps. Second, during training, we use a cache store the states replay memory and train the GNCA on batches of states ((k) sampled from the cache. For every batch, the cache is updated with the new states reached by the GNCA after i steps, and one element of the cache is replaced with S avoid catastrophic forgetting. The cache has a size of 1024 states and is initialised entirely with S. By using the cache, the GNCA is trained also on states that result from a repeated application of the transition function. This strategy encourages the GNCA to remain at the target state after reaching it, while also ensuring an adequate exploration of the state space during training.
()(()))) reached by the GNCA after each forward pass. Then, we use the cache
Results We run our experiments on the following graphs from PyGSP: a regular 2D grid, the Stanford bunny geometric mesh, the Minnesota road network, the PyGSP logo, and a random point cloud sampled the Swiss roll manifold. Fig. S shows some of the state trajectories of the trained GNCA on different graphs, as well as the mean squared error between the current state and the target. We report results for & 10, t 20, and t [10, 20] randomly sampled at each forward pass during training, as also done by Mordvintsev et al. (17]. The specific values that we considered for ł are a trade-off between computational complexity, stability during training, and sufficient amount of time steps to allow the model to learn interesting dynamical patterns. Other values for t are possible but we leave this exploration as future work.
We see that the GNCA is always able to reach a state very close to the target in the prescribed number of steps, and we highlight two main patterns that emerge by analysing the behaviour of the GNCA on different graphs and values of f. For = 10, rather than remaining stable at the target, the GNCA learns produce a periodic behaviour that oscillates between high-error and low-error states (as shown in Fig. 5). While this behaviour can be partially ascribed to the use of the cache, which results in backpropagating the error only after k I steps for k N, see that the behaviour learned by the GNCA does not always have period of 10 (e.g., see Fig. 5b). Also, the error of the GNCA does not reach its minimum right away. but takes a few repetitions converge to a more stable periodic orbit. We observed this behaviour also for Grid and Bunny with f = 20.
stable attractor. This is expected for t E [10, 20). since the GNCA is trained to always reach the target state after any random amount of transitions. However, it is remarkable that we observe convergent behaviour also for 20, which seemingly points to some intrinsic differences between the kind of transition rules that best approximate different graphs (since, for 20, the GNCA still learns a periodic attractor for Grid and Bunny). A summary of the behaviour of the GNCA on different graphs is reported in Table 2 as well as the minimum error reached by the trained GNCA in its trajectory.
For 20 and E [10, 20), the GNCA learns to converge
5 Conclusions
We believe to have opened the way to a new line of research in which GNNs can unlock the power of GCA and implement desired behaviour through distributed and emergent computation. The possible applications of GNCA are clear in control problems, although we believe that many complex dynamical systems can be modelled as GCA (e.g., social, epidemiological, and technological networks). In general, GNCA allow us to learn transition rules on these systems instead of hand- designing them, and could lead to better understanding of their characteristics (e.g., how virus spreads). More research is required to address these issues since GNCA are currently not designed to be interpretable. Also, applying BPTT with GNNs can be expensive if the graph is big or dense. This a general limitation of deep GNNs that affects our model too, and could be addressed as the field advances.

---

Acknowledgments and Disclosure of Funding
This research was funded by the Swiss National Science Foundation project 200021 172671 "ALPS- FORT".
References
[1] J. Neumann, A. W. Burks al., Theory of reff-reproducing automata. University of Illinois press Urbana, 1966, vol. 1102024.
[2] K. Bhattacharjee, N. Naskar, S. Roy, and S. Das, "A survey of cellular automata: types, dynamics, non-uniformity and applications," Natural Computing, vol. 19, no. 2, pp. 433-461, 2020.
[3] C. Marr and M.-T. Hütt, "Outer-totalistic cellular automata on graphs," Physics Letters A, vol. 373, no. 5, pp. 546-549, 2009.
[4] M. Gori, Monfardini, and F. Scarselli, "A new model for learning in graph domains," in Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., vol. 2. IEEE, 2005, pp. 729-734.
[5] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, "The graph neural network model," IEEE Transactions on Neural Networks, vol. 20, no. 1, pp. 61 80, 2009.
[6] P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanzhez-Gonzalez, V. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner al., "Relational inductive biases, deep learning, and graph networks," arXiv preprint arXiv:1806.01266 2018
[7] C. W. Reynolds, "Flocks, herds and schools: distributed behavioral model," in Proceedings of the 14th annual conference on Computer graphics and interactive techniques, 1987, pp. 25-34.
[8] N. Wulff and J. A. Hertz, "Learning cellular automaton dynamics with neural networks," Advances in Neural Information Processing Systems, vol. 5, pp. 631-638, 1992.
[9] W. Elmenreich and I. Fehérvári, "Evolving self-organizing cellular automata based on neural network genotypes," in International Workshop on Self- Self-Organizing Systems. Springer, 2011,
pp. 16-25.
[10] Nichele, M. B. Ose, S. Risi, and G. Tufte, "Ca-neat: evolved compositional pattern producing networks for cellular automata morphogenesis and replication." IEEE Transactions on Cognitive and Developmental Systems, vol. 10, no. 3, pp. 687-700, 2017.
[11] K. O. Stanley and R. Miikkulainen, "Evolving neural networks through augmenting topologies." Evolutionary computation, vol. 10, no. 2, pp. 99-127, 2002.
[12] K. O. Stanley, "Compositional pattern producing networks: A novel abstraction of development." Genetic progranming and evolvable machines, vol. 8, no. 2, pp. 131-162, 2007.
[13] W. Gilpin. "Cellular automata as convolutional neural networks," Physical Review E, vol. 100, no. p. 032402, 2019.
[14] J. M. Springer and G. '.. Kenyon, "It's hard for neural networks to learn the game of life," arXiv preprint arXiv:2009. 01398, 2020.
[15] J. Frankle and M. Carbin, "The lottery ticket hypothesis: Finding sparse, trainable neural networks," arXiv preprint arXiv:/803 036655 2018.
[16] M. Aach, J. Goebbert, and Jitsev, "Generalization over different cellular automata rules learned by deep feed-forward neural network," ArXiv, vol. 055/2103.14888 2021.
[17] A. Mordvintsev, E. Randazzo, F. Niklasson, and M. Levin, "Growing neural cellular automata," Distill, vol. 5, no. 2, p. c23, 2020.
10

---

[18] E. Randazzo, A. Mordvintsev, E. Niklasson, M. Levin, and S. Greydanus, "Self-classifying mnist digits," Distill, 2020, https//disilll.pbb220o/sseiiii
[19] Wolfram, "Statistical mechanics of cellular automata," Reviews of modern physics, vol. 55, no. 3, 601, 1983.
[20] J. You, R. Ying, and J. Leskovec, "Design space for graph neural networks," arXiv preprint 0rXiv:2011.0884 2020.
[21] M. Simonovsky and N. Komodakis, "Dynamic edgeconditioned filters in convolutional neural networks graphs," in Proceedings of the IEFF Conference Computer Vision and Pattern Recognition, 2017.
[22] B. W.-C. Chan, "Lenia-biology of artificial life," arXiv preprint arXiv: 2018.
[23] M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R. R. Salakhutdinov, and A. J. Smola, "Deep sets," in Advances in neural information processing systems, 2017, pp. 3391-3401.
[24] C. Marr and M.-T. Hütt, "Cellular automata on graphs: Topological properties of er graphs evolved towards low-entropy dynamics," Entropy, vol. 14, no. 6, pp. 993-1010, 2012.
[25] C. G. Langton, "Computation the edge of chaos: Phase transitions and emergent computation," Physica D: Nonlinear Phenomena, vol. 42, no. 1-3, pp. 12-37, 1990.
[26] J. L. McClelland and D. E. Rumelhart, Explorations in parallel distributed processing: A handbook of models, programs. and exercises. MIT press, 1989.
[27] R. Bland, Learning XOR: exploring the space of a classic problem. Department of Computing Science and Mathematics, University of Stirling Stirling, 1998.
[28] S. Richman and J. R. Moorman, "Physiological time-series analysis using approximate entropy and sample entropy," American Journal of Physiology-Hese and Circulatory Physiology, 2000.
[29] Grassberger and Procaccia, "Characterization of strange attractors," " Physical review letters, vol. 50, no. 5, p. 346, 1983.
[30] M. Defferrard, L. Martin, R. Pena, and N. Perraudin, "Pygsp: Graph signal processing in python." [Online]. Available: htnps//gitubbcom//pplll////z////
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you deseribe the limitations of your work? [Yes] In Section 5
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material URL)? [Yes] Code is available online (see supplementary material).
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See supplementary material.
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes]

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See supplementary material.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as URL? [Yes]
Code is available online (see supplementary material).
(d) Did you discuss whether and how consent was obtained from people whose data you'le rrere using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "_5_VIN_V8M", "reviewer": "Reviewer_Tp3K", "summary": "This paper presents an approach to learn, what the authors call, graph cellular automata (GCAs). Graph neural networks are trained to learn transition rules for  GCAs and tested on three different domains: Voronoi tessellation, learning dynamics of flocking agents, and learning to approximate 2D/3D target structures. The main contribution is the application of graph neural networks to these three interesting problems. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is in general well written and clear. It also addresses an interesting and important topic, which is how can we train systems whose global behaviors arise purely through the local interaction of cells. Additionally, the three chosen domains show the diversity of behaviors that are learnable by a graph neural network. However, why exactly these three domains are chosen could be elaborated on and also what interesting future work they enable. \n\nMy main critique is that it’s not very clear how exactly the current system differs from a graph neural network. Isn’t a neural cellular automata a subset of a graph neural network already? It would be great if the authors could be more precise here on how exactly their system differs from a graph neural network or how both are defined exactly. For example, in the abstract, the authors note that: “...we use graph neural network to learn a variety of transition rules for GCA”. So in this case the GNN is regarded as the learning algorithm? Here it might also help to clearly state the unique contributions in the introduction of the paper. Currently, the paper looks more like “just” and application for GNN to three interesting problems.\n\nI wasn’t sure what the motivation is behind the minimal exact implementation. Some motivation would help the reader here. \n\nThere is some work from the evolutionary computation community to learn transition rules for cellular automata with neural networks, which predates the approaches mentioned in this paper. For example: \n\nEvolving Self-organizing Cellular Automata Based on Neural Network Genotypes. Elmenreich, W. and Fehervari, I., 2011. Self-Organizing Systems, pp. 16--25. Springer Berlin Heidelberg.\n\nCA-NEAT: Evolved Compositional Pattern Producing Networks for Cellular Automata Morphogenesis and Replication. Nichele, S., Ose, M.B., Risi, S. and Tufte, G., 2018. IEEE Transactions on Cognitive and Developmental Systems, Vol 10, pp. 687-700.\n\nLearning Cellular Automaton Dynamics with Neural Networks. Wulff, N.H. and Hertz, J.A., 1992.  Neural Information Processing Systems, pp. 631–638.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The potential societal impacts are not elaborate on. It could be worthwhile to elaborate a bit on the dangers and opportunities in systems that are based on the self-organization of locally-communicated parts. These systems might be even harder to control and impossible to predict. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "KDDIsmj6ifz", "reviewer": "Reviewer_bL59", "summary": "The paper presents the Graph Neural Cellular Automata (GNCA) architecture, a general-purpose architecture that uses a Graph Neural Network (GNN) to learn a desired Graph Cellular Automata (GCA). The proposed architecture is used to learn different transition rules in different kinds of space (discrete and continuous). In the paper, there is a brief (but complete) introduction to Graph Cellular Automata and Graph Neural Network. The GNCA architecture borns by the natural and clearly explained connection between GNN and GCA. The effectiveness of this architecture is demonstrated by three experiments that explore different scenarios: learning a transition rule via supervised learning in a discrete state space, learning a transition rule in a continuous state space, and learning an unknown transition rule to reproduce a target. Each result is discussed using different metrics in order to evaluate how well the model performs in that particular setting.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "* The paper is complete, well written, and clear in the explanation of the concepts;\n* the experiments are various and describe well the effectiveness of the architecture in different settings. A great contribution is given by the description in the supplementary material;\n* the paper proposes an interesting and simple architecture to learn transition rules in a more general setting with respect to previous works in the field;\n* some particular results from the experiments are highlighted and well-argued (e.g. the periodic behavior on figure 5).\n\nAs said above, the paper is well written and everything is defined precisely so there are no relevant weaknesses, only some clarifications:\n* Even if well described, it would be more clear if the model description in appendix's section 1.2 were moved in the paper, in section 3.3;\n* algorithm 1 is not clear in some of its points: at line 2, $p_i$ and $v_i$ are not clearly defined. I suppose they refer to the position and velocity of boid $i$, but at line 46 in the appendix, you use $p_x, p_y$ for position and $v_x,v_y$ for velocity, so this is a little bit confusing. Moreover, lines 10,...,16 (of algorithm 1) are not very clear;\n* there are no baselines. If the architecture had been compared with some existing methods we would have a more clear way to understand its validity;\n* a more in-depth explanation of the metrics used in the experiments would be interesting (e.g. SamplEn), maybe using some formulas. This could also be done in the appendix;\n* neither in the paper nor in the appendix there is a specification on how you chose the hyperparameters;\n* at line 301, what kind of normalization did you use? Have you tried different kinds of normalization? Why not try using random positions? Each starting point has a corresponding target point, is possible that two or more points exchange their target point? Because in your setting this would be considered as an error (that will increase the error). For example, if at the end $\\bar{s}_i = \\hat{s}_j$ and $\\bar{s}_j = \\hat{s}_i$ with $i\\neq j$ this is an error for you but the target is correctly reconstructed. I have understood your idea but it will be interesting if this were analyzed or only mentioned; \n* line 304 is not clear to me. Each mini-batch has size $K$ but you mention that each of them consists of initial states $S^{(k)}=1,\\dots, K$. This is misleading because it appears that each mini-batch is composed of the same points;\n* in the conclusion section, it would be interesting to read a \"future work\" analysis, describing how the work could continue (this has been done in some parts of the paper, but it would be more clear to have a dedicated section), and with a brief discussion about the limitations of the proposed architecture.\n\nMinor typos and errors:\n* In the code (README.md), you mention folder \"point_cloud\" but this does not exist in the code. I suppose that the correct name is \"fixed_target\";\n* at line 290 you refer to a video of the GNCA trajectories in the supplementary material, but there is not.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In general, the authors did not perform an in-depth analysis of the limitations of their work. For example, it would be interesting to see some experiments where the architecture does some errors, maybe trying different agent-based contexts (different from the one proposed in section 4.2). It would be interesting to see more than one experiment for each context (this has been done only for the convergence to a fixed target, section 4.3). In this way, we know that the architecture works pretty well only in the proposed experiments. However, for each experiment, when a particular behavior occurs, it has been described/investigated very well by the authors (an example is the periodic behavior explained starting from line 235).\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "1Yaru9yaU1", "reviewer": "Reviewer_ZxB8", "summary": "Authors present a general-purpose architecture for learning GCA, and we show that it can represent any arbitrary GCA with finite and discrete state space. Then, we test our approach on three different tasks: 1) learning the transition rule of a GCA on a Voronoi tessellation;\n2) imitating the behaviour of a group of flocking agents; 3) learning a rule that converges to a desired target state.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Authors have proposed a general-purpose architecture to achieve this, which we showed to be general enough to implement\nany arbitrary transition function for a large class of GCA. Authors have applied the GNCA model to learn a variety of GCA transition rules, including unknown rules for which we only specified a target state.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please addressed the limitations and potential negative societal impact of your work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Meta-review of "Learning Graph Cellular Automata"

This paper applies graph neural networks to learn transition rules of cellular automata. They demonstrate results on the proposed graph cellular automata (GCA) method on 3 different domains that are popular with CA-based approaches: Voronoi tessellation, learning dynamics of flocking agents, and learning to approximate 2D/3D target structures.

All reviewers agree that the paper is well written and explains concepts clearly, with particular emphasis on details for all the well-chosen experiments. The results further highlight how interactions of local cells can produce global coherent phenomena.

Reviewer Tp3K notes that there has been much work in the evolutionary computation community about learning transition rules for CA with neural nets, and suggested a few, so I highly recommend the authors update the work with a discussion on historical works. This is important, because this paper can help guide the NeurIPS community into CA's, and one must provide the right context to a mature field that has existed for a long time.

For all these reasons stated, I recommend acceptance of this work.

Decision: Accept (Poster)