Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 

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. 

My 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.

I wasn’t sure what the motivation is behind the minimal exact implementation. Some motivation would help the reader here. 

There 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: 

Evolving Self-organizing Cellular Automata Based on Neural Network Genotypes. Elmenreich, W. and Fehervari, I., 2011. Self-Organizing Systems, pp. 16--25. Springer Berlin Heidelberg.

CA-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.

Learning Cellular Automaton Dynamics with Neural Networks. Wulff, N.H. and Hertz, J.A., 1992.  Neural Information Processing Systems, pp. 631–638.


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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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;
2) imitating the behaviour of a group of flocking agents; 3) learning a rule that converges to a desired target state.
main_review: Authors have proposed a general-purpose architecture to achieve this, which we showed to be general enough to implement
any 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.
limitations_and_societal_impact: Please addressed the limitations and potential negative societal impact of your work.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.
main_review: * The paper is complete, well written, and clear in the explanation of the concepts;
* 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;
* 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;
* some particular results from the experiments are highlighted and well-argued (e.g. the periodic behavior on figure 5).

As said above, the paper is well written and everything is defined precisely so there are no relevant weaknesses, only some clarifications:
* 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;
* 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;
* 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;
* 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;
* neither in the paper nor in the appendix there is a specification on how you chose the hyperparameters;
* 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; 
* 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;
* 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.

Minor typos and errors:
* 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";
* at line 290 you refer to a video of the GNCA trajectories in the supplementary material, but there is not.

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).
review_title: null

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)