Shape irregularity of Life-Like Network Automaton rules as an indicator of classification performance

Lucas C. S. Oliveira; Michiel Rollier; Jan Baetens; Odemir M. Bruno

cs.LGOct 7, 2026

Shape irregularity of Life-Like Network Automaton rules as an indicator of classification performance

Authors: Lucas C. S. Oliveira, Michiel Rollier, Jan Baetens, Odemir M. Bruno

Organizations: Institute of Mathematics and Computer Science University of S˜ao Paulo S˜ao Carlos, 13566-590, Brazil · BionamiX, Dept. of Data Analysis and Mathematical Modelling Ghent University Ghent, 9000, Belgium · AICS, S˜ao Carlos Institute of Physics University of S˜ao Paulo S˜ao Carlos, 13566-590, Brazil

Abstract

Complex Network (CN) classification requires high-level structural characterizations that are both scale-invariant and computationally efficient. Methods based on Life-Like Network Automata (LLNA) offer an interesting way to extract network descriptors by leveraging emergent temporal patterns without requiring provided features, but their efficacy is bottlenecked by a high-cost combinatorial optimization problem: the selection of the automaton transition rule. While current literature relies on exhaustive searches that are unfeasible for large-scale applications, this work reveals that the rule space is fundamentally structured by a property we term ``jaggedness'', that quantifies the resemblance of a LLNA transition function with a sawtooth shape. We demonstrate that this metric acts as a theoretical proxy for chaoticity and sensitivity -- properties essential for generating discriminative dynamic behaviors among network categories. Moreover, we introduce a heuristic search strategy that uses jaggedness to guide the rule selection. Experimental results show that our approach achieves classification accuracies within 5% of the global optimum while reducing computational overhead by 90% compared to exhaustive approach. Our findings provide a novel, efficient, framework for optimizing automata-based methods for pattern recognition.

Figures & tables

Panel of Figure 1 — Figure 1: Best reported rules in [ 14 ] for plant metabolic chains (top) and social circles (bottom) datasets. The density intervals that can lead to alive state in both born and survive conditions are not totally contiguous, giving a jagged appearance to the transition function.

Figure 2: Examples of the Game of Life transition rule operating on an infinite regular 2-D grid with Moore’s neighborhood (top) with the counting of states, on a network topology equivalent to the Moore’s neighborhood (middle) using density-based operation, and on a finite arbitrary network topology (bottom). Living cells/nodes are present in black, and dead ones in white, with their amount of living neighbors denoted (zeros are omitted).

Figure 3: General network classification pipeline based on LLNA. The boxes indicate the inputs and outputs, the arrows denote the action performed by the modules, and the ellipses list their hyper-parameters. The dashed rectangle delimit the end-to-end classification model.

Figure 4: Diagram of the born condition for rules $\varphi^{5}_{21,4}$ (top) and $\varphi^{5}_{19,4}$ (bottom). The green areas denote the density intervals composing the rules. The vertical lines mark all possible discontinuities between subsequent intervals for $\alpha=5$ : dashed (orange) for occurring discontinuities, dotted (gray) for non-occurring ones.

Figure 5: Correlation of the normalized jaggedness with genotype parameters, for rule families with resolution from 3 to 6.

Figure 6: Navigation in LLNA rule space inspired by the ILS perturbation procedure. Each plane denotes a rule family partitioned by jaggedness. The partitions $\Phi^{\alpha}_{n}$ are represented by the ellipses with their normalized jaggedness indicated. Arrows denote the perturbation, defined as a mapping that tries to preserve $\bar{J}$ . Bold arrows mark the exact mapping.

	dataset	# classes	# nets	nets/class	# nodes	avg. degree
[ 11 ]	classic	4	11200	2800	500 – 2000	4 – 16
[ 11 ]	scalefree	5	500	100	1000	8
[ 13 ]	noise=10%	8	800	100	1000	7.6 – 8.5
[ 13 ]	noise=20%	8	800	100	1000	7.6 – 8.5
[ 13 ]	noise=30%	8	800	100	1000	7.6 – 8.5
[ 13 ]	actinobacteria	3	229	63 – 96	803 – 1533	3.4 – 3.6

Table 1: Properties of the selected network datasets and their respective sources, vertically grouped by scope, respectively: synthetic, metabolic, social, and bioinformatics. Ranges denote minimum and maximum values.

Figure 7: Box plot of the classification accuracy by rule resolution (exhaustive evaluation) for different datasets, organized in 4 groups. The box spans the inter-quartile range, with the median shown as a horizontal line and outliers as individual points.

Figure 8: Correlation of the classification accuracy with the normalized jaggedness and the average Hamming weight and Boolean sensitivity, for rule family with resolution 6.

Panel of Figure 9 — Figure 9: Accuracy distribution for the network datasets. Circles in the heatmap represent the average value for each subset of rules with same jaggedness, triangles mark the average for the subsets where there is at least one rule in the top 1% best ones.

Figure 10: Performance of the heuristic search executing a full exploration of the rule family partitions, segmented by dataset scope, with 95% confidence interval.

Figure 11: Performance of the heuristic search executing a partial exploration of the rule family partitions, segmented by sampling fraction, with 95% confidence interval.

Figure 12: Accuracy distribution of rules explored by exhaustive search ( $\alpha=7$ ) versus heuristic search ( $\alpha=3,\dots,7$ ) without sampling, grouped by dataset scope. The box spans the inter-quartile range, with the median shown as a horizontal line and outliers as individual points.

Explore similar work

It's Much Easier for Neural Networks to learn Game of Life Dynamics with the Right Activation Function: Polynomial Kolmogorov-Arnold Networks
Jun 22, 2026Tashin Ahmed, Q. Tyrell DavisPolynomial Neural Networks Cellular Automata
Independent Researcher · Work completed while at Cross Labs, Cross Compass Ltd., Japan.
A New Kind of Network? Review and Reference Implementation of Neural Cellular Automata
Apr 27, 2026Martin Spitznagel, Janis KeuperNeural Cellular Automata Cellular Automata
Institute for Machine Learning and Analytics (IMLA), Offenburg University, Germany · University of Mannheim, Germany
Kolmogorov-Arnold Classifier Systems as Universal Approximators
Sep 29, 2026Hiroki Shiraishi, Hisao Ishibuchi, Masaya NakataUniversal Approximation
Graduate School of Engineering Science, Yokohama National University, Yokohama 240-8501, Japan · Digital Healthcare Research Department, Hitachi, Ltd., Tokyo 185-8601, Japan · Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China +1

Jun 22, 2026, cs.LGJ/K move · Enter open · S save

It's Much Easier for Neural Networks to learn Game of Life Dynamics with the Right Activation Function: Polynomial Kolmogorov-Arnold Networks

Tashin Ahmed, Q. Tyrell Davis

Independent Researcher · Work completed while at Cross Labs, Cross Compass Ltd., Japan.

Polynomial Neural Networks Cellular Automata Neural Network Activation Functions Kolmogorov-Arnold Networks

Open paper AskPDF arXiv

Previous work has found a gap between the scale of neural networks that reliably learn Conway's Game of Life, and minimal networks capable of representing the classic cellular automaton with hard-coded parameter values. Viewing neural network learning as a search process suggests a dependence on networks large enough to contain sub-networks with lucky initializations (sometimes known as 'winning tickets') that actually learn the task. In this work, we reorient our perspective from discovering Life rules as a search problem back to a learning problem, and reason that with fitting inductive biases, the problem should be much more amenable to minimal networks. We find that network variants with several alternative activation functions meaningfully outperform the default choice of Rectified Linear Units, and in particular, that a 2nd degree polynomial activation function consistently learns Life dynamics with or without the benefit of learning neural weights. Our results provide an informative demonstration of the benefits of matching learning to the task at hand and challenge the easy default choice of scale for all problems. In particular, we advocate for the use of cellular automata as simple test domains for developing strategies that can benefit machine learning for science, physics-based deep learning, and interpretable machine learning.

Abstract

Explore similar work

It's Much Easier for Neural Networks to learn Game of Life Dynamics with the Right Activation Function: Polynomial Kolmogorov-Arnold Networks

A New Kind of Network? Review and Reference Implementation of Neural Cellular Automata

Kolmogorov-Arnold Classifier Systems as Universal Approximators