以 Life-Like 网络自动机规则的形状不规则性作为分类性能的指标

# Shape irregularity of Life-Like Network Automaton rules as an indicator of classification performance
Source: [https://arxiv.org/html/2610.10867](https://arxiv.org/html/2610.10867)
[Lucas C\. S\. Oliveira](https://orcid.org/0000-0002-7881-8414)Affiliation:Institute of Mathematics and Computer ScienceAffiliation:University of São PauloAffiliation:São Carlos, 13566\-590, BrazilEmail:[l\.caldeira@usp\.br](mailto:)[Michiel Rollier](https://orcid.org/0000-0001-8467-734X)Affiliation:BionamiX, Dept\. of Data Analysis and Mathematical ModellingAffiliation:Ghent UniversityAffiliation:Ghent, 9000, BelgiumEmail:[michiel\.rollier@ugent\.be](mailto:)[Jan Baetens](https://orcid.org/0000-0003-4084-9992)Affiliation:BionamiX, Dept\. of Data Analysis and Mathematical ModellingAffiliation:Ghent UniversityAffiliation:Ghent, 9000, BelgiumEmail:[jan\.baetens@ugent\.be](mailto:)[Odemir M\. Bruno](https://orcid.org/0000-0002-2945-1556)Affiliation:AICS, São Carlos Institute of PhysicsAffiliation:University of São PauloAffiliation:São Carlos, 13566\-590, BrazilEmail:[bruno@ifsc\.usp\.br](mailto:)

October 5, 2026

###### 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\.

*Keywords*network automata⋅\\cdotnetwork classification⋅\\cdotcellular automata⋅\\cdotthe Game of Life⋅\\cdotmetaheuristics

## 1Introduction

Network science is an interdisciplinary field that mainly encompasses graph theory and statistical physics, allowing the study of complex and nonlinear phenomena in their entirety\[[1](https://arxiv.org/html/2610.10867#bib.bib3)\]\. Due to its great power of generalization, modeling phenomena as a graph or a complex network \(CN\) has been used in diverse domains – social networks\[[2](https://arxiv.org/html/2610.10867#bib.bib28)\], metabolic chains\[[3](https://arxiv.org/html/2610.10867#bib.bib30)\], epidemics\[[4](https://arxiv.org/html/2610.10867#bib.bib29)\], etc\. – and in diverse applications – network classification\[[5](https://arxiv.org/html/2610.10867#bib.bib22)\], spatiotemporal forecasting\[[6](https://arxiv.org/html/2610.10867#bib.bib34)\], link prediction\[[7](https://arxiv.org/html/2610.10867#bib.bib38)\], identification of vulnerabilities and anomalies\[[8](https://arxiv.org/html/2610.10867#bib.bib39)\], and others\[[9](https://arxiv.org/html/2610.10867#bib.bib2)\]\.

In order to study CNs and capture more meaningful information that underlies their topology, a common approach is to compute some set of metrics that summarize certain structural aspects at node, edge and/or graph\-level\[[10](https://arxiv.org/html/2610.10867#bib.bib1)\]\. Yet, in cases as the network classification problem, where the objective is to identify the class of a given CN \(e\.g\.finding the taxonomic group of a metabolic network or if a given chemical compound is carcinogenic or not\), they may not be sufficiently informative or be incomplete/partially unavailable\[[11](https://arxiv.org/html/2610.10867#bib.bib11)\]\.

A method that has been successfully applied in this context is the Life\-Like Network Automaton \(LLNA\)\[[11](https://arxiv.org/html/2610.10867#bib.bib11),[12](https://arxiv.org/html/2610.10867#bib.bib23),[13](https://arxiv.org/html/2610.10867#bib.bib8),[14](https://arxiv.org/html/2610.10867#bib.bib7)\]\. Taking inspiration from Conway’s Game of Life\[[15](https://arxiv.org/html/2610.10867#bib.bib15)\], it relies on network topology as source of dynamical information, differing from other approaches that use only structural information\[[16](https://arxiv.org/html/2610.10867#bib.bib46),[17](https://arxiv.org/html/2610.10867#bib.bib14)\]and/or depend on detailed feature vectors provided beforehand\[[18](https://arxiv.org/html/2610.10867#bib.bib12),[19](https://arxiv.org/html/2610.10867#bib.bib13)\]\. In summary, the LLNA generates an initial configuration for the nodes and evolves them over time according to a transition function \(i\.e\.the automaton rule\), whose resulting state\-time diagram is used to extract rich information about network dynamics for the sake of classification\.

While this method does not require any prior information besides the network topology and is both scale\-invariant and computationally efficient to run, finding a good discriminant rule for the automaton is not trivial\. The classification can only be performed if the chosen rule is capable of generating patterns that share common properties between the the same class \(high intraclass similarity\) while being sufficiently different from other classes \(low interclass similarity\)\. Yet only a small portion of the rule space present this capability\. In practice, the selection of a satisfactory transition rule can be framed as a combinatorial optimization problem, which has been approached by doing an exhaustive search in the rule space\[[11](https://arxiv.org/html/2610.10867#bib.bib11),[13](https://arxiv.org/html/2610.10867#bib.bib8),[14](https://arxiv.org/html/2610.10867#bib.bib7)\]\. While increasing the size of the rule family tends to improve classification accuracy\[[20](https://arxiv.org/html/2610.10867#bib.bib25)\], an exhaustive search quickly becomes computationally unfeasible\.

As the rule optimization is a critical bottleneck of the method, this work investigates what property characterizes LLNA rules that lead to high classification accuracies, a question that has been neglected since the method was originally proposed\. After inspecting the reported best rules for some datasets, we noticed that they share certain \(visual\) characteristics\. The set of density intervals composing the best rules presents a degree of irregularity, what in a visual perspective translates to a transition function with sawtooth shape \(see[Figure 1](https://arxiv.org/html/2610.10867#S1.F1)\)\. We hypothesize that this jagged appearance can be a good indicator of classification performance\.

![Refer to caption](https://arxiv.org/html/2610.10867v1/image/best_rule_plants.png)

![Refer to caption](https://arxiv.org/html/2610.10867v1/image/best_rule_scircles.png)

Figure 1:Best reported rules in\[[14](https://arxiv.org/html/2610.10867#bib.bib7)\]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\.To assess these research questions, we define a formal measure of jaggedness and investigate to what extent it can be used to organize the rule space and guide the non\-exhaustive search for optimum LLNA rules\. In[Section 2](https://arxiv.org/html/2610.10867#S2)we present the theoretical background of the LLNA algorithm and its use for classifying networks\. In[Section 3](https://arxiv.org/html/2610.10867#S3)we formally define the jaggedness, explore how it can be used to partition the rule space, and outline a heuristic search strategy that benefits from this organization\. In[Section 4](https://arxiv.org/html/2610.10867#S4)we evaluate the connection between rule jaggedness, classification performance and rule space resolution, and discuss the use of jaggedness as an indicator of complex dynamical behavior\.

## 2Background

One of the objects of study in network theory is how the topological properties of a CN shape its emergent dynamics\. From the small\-world and scale\-free phenomena to hierarchy, modularity, and degree heterogeneity, structural properties – both local and global – influence how information and diseases spread, the resilience against random and targeted attacks, the sensitivity to small perturbations, and the emergence of collective ordered states\[[21](https://arxiv.org/html/2610.10867#bib.bib5),[22](https://arxiv.org/html/2610.10867#bib.bib4)\]\. Works such as Miranda’s\[[11](https://arxiv.org/html/2610.10867#bib.bib11)\]and Machicao’s\[[12](https://arxiv.org/html/2610.10867#bib.bib23)\]demonstrate that it is in fact possible to characterize a network based only on its dynamical behavior, therefore allowing for pattern recognition tasks such as classification\.

In this work we focus on LLNA, that generalize the born/survive dynamics from Conway’s Game of Life cellular automaton \(CA\) to a network topology\. Below we describe how one can define a CA for arbitrary networks and utilize it for characterization and classification purposes\.

### 2\.1Life\-like NAs

Anetwork automaton\(NA\) is a formalism that adapts the transition logic of a CA to the non\-regular topology of networks\. In other words, it uses the graph as “tessellation”, the nodes as cells and their edges as the neighborhood structure, with the transition rule acting as the criterion for cell’s state update according to its current state and neighboring cells’ configuration\. In his influential book\[[23](https://arxiv.org/html/2610.10867#bib.bib20)\], Watts discussed the computation of a CA in Small\-World networks for density classification and synchronization tasks\. The works of Marr and Hütt\[[24](https://arxiv.org/html/2610.10867#bib.bib16),[25](https://arxiv.org/html/2610.10867#bib.bib21)\]and Baetens and Baets\[[26](https://arxiv.org/html/2610.10867#bib.bib17),[27](https://arxiv.org/html/2610.10867#bib.bib18)\]approach the impact of the topology in the resulting dynamics, and propose different ways to implement CA transition rules on networks\.

Moreover, it is not trivial to adapt the local transition function from CAs, due to network’s intrinsic lack of ordering between nodes and unbounded number of neighbors\. The former is commonly solved by using totalistic rules\[[28](https://arxiv.org/html/2610.10867#bib.bib32)\], but there is no standard approach for the latter, with some restricting the neighborhood size to a maximum value and others implementing a degree\-based normalization, which transforms the state count operation into state density computing\. As an example of a NA with a density\-based transition function, we have the the so called LLNA\[[11](https://arxiv.org/html/2610.10867#bib.bib11)\], whose state space and transition function are inspired by the Game of Life\[[15](https://arxiv.org/html/2610.10867#bib.bib15)\]\. It works as follows\.

Each nodeviv\_\{i\}of the network𝒢\\mathcal\{G\}can take one of two states,alive\(1\) ordead\(0\)\. Given the initial configuration of the network𝐬0=\[si0\]∈𝒮N\\mathbf\{s\}^\{0\}=\\left\[s^\{0\}\_\{i\}\\right\]\\in\\mathcal\{S\}^\{N\}, wheresits^\{t\}\_\{i\}is the state ofviv\_\{i\}at timettandNNis the number of nodes, the state of eachii\-th node at the next time stept\+1t\+1is determined by its current statesits^\{t\}\_\{i\}and the states of its neighboring\{sjt\|vj∈𝒩i\}\\\{s^\{t\}\_\{j\}\\,\|\\,v\_\{j\}\\in\\mathcal\{N\}\_\{i\}\\\}\. The functionφ\\varphithat mapssits^\{t\}\_\{i\}tosit\+1s^\{t\+1\}\_\{i\}is called transition rule, and operates according to birth and survival criteria\.

For example, the transition rule of the original Game of Life states that any dead cell with exactly 3 living neighbors or any live cell with 2 or 3 living neighbors, out of its 8 neighbors, will have its next state set to alive, otherwise it will stay/become dead\. In the case of LLNA, the equivalent rule is obtained by computing the density of living neighbors and checking if the density falls into\[39,49\[\\left\[\\frac\{3\}\{9\},\\frac\{4\}\{9\}\\\!\\right\[, for the born criterion, or\[29,39\[∪\[39,49\[\\left\[\\frac\{2\}\{9\},\\frac\{3\}\{9\}\\\!\\right\[\\,\\cup\\left\[\\frac\{3\}\{9\},\\frac\{4\}\{9\}\\\!\\right\[, for the survive criterion\.[Figure 2](https://arxiv.org/html/2610.10867#S2.F2)illustrates this logic, where the count/density of living neighbors that will trigger the birth\-and\-survival rule is marked in red\.

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\)\.Formally, the LLNA is a Boolean outer\-totalistic NA defined by the quadruple⟨𝒢,𝒮,𝐬0,φα⟩\\left\\langle\\mathcal\{G\},\\mathcal\{S\},\\mathbf\{s\}^\{0\},\\varphi^\{\\alpha\}\\right\\rangle, with the transition ruleφα=φ\\varphi^\{\\alpha\}=\\varphioperating on a uniform partition with cardinalityα\\alphaof the unit interval\. Letℋkα\\mathcal\{H\}\_\{k\}^\{\\alpha\}be thekk\-th subset of the uniform partition,

ℋkα=\{\[kα,k\+1α\[,k=0,…,α−2;\[kα,k\+1α\],k=α−1\.\\mathcal\{H\}\_\{k\}^\{\\alpha\}=\\begin\{cases\}\\left\[\\frac\{k\}\{\\alpha\},\\frac\{k\+1\}\{\\alpha\}\\right\[&,\\;k=0,\\dots,\\alpha\-2;\\\\ \\left\[\\frac\{k\}\{\\alpha\},\\frac\{k\+1\}\{\\alpha\}\\right\]&,\\;k=\\alpha\-1\.\\\\ \\end\{cases\}\(1\)Aborncriterion is satisfied ifsit=0s^\{t\}\_\{i\}=0and the fraction of living nodes in the neighborhood ofviv\_\{i\}, given byρit=1di​∑vj∈𝒩isjt\\rho^\{t\}\_\{i\}=\\frac\{1\}\{d\_\{i\}\}\\sum\_\{v\_\{j\}\\in\\mathcal\{N\}\_\{i\}\}s^\{t\}\_\{j\}, falls in some interval covered by the setBX=⋃k∈XℋkαB\_\{X\}=\\bigcup\_\{k\\in X\}\\mathcal\{H\}\_\{k\}^\{\\alpha\}, wheredi=\|𝒩i\|d\_\{i\}=\\left\|\\mathcal\{N\}\_\{i\}\\right\|is the degree of the nodeii\. Analogously, asurvivecriterion is satisfied whensit=1s^\{t\}\_\{i\}=1andρit∈SY\\rho^\{t\}\_\{i\}\\in S\_\{Y\}, withSY=⋃k∈YℋkαS\_\{Y\}=\\bigcup\_\{k\\in Y\}\\mathcal\{H\}\_\{k\}^\{\\alpha\}\.

sit\+1=φ⁡\(sit,ρit\)=\{1if​sit=0​and​ρit∈BX;1if​sit=1​and​ρit∈SY;0otherwise\.s^\{t\+1\}\_\{i\}=\\varphi\(s^\{t\}\_\{i\},\\rho^\{t\}\_\{i\}\)=\\begin\{cases\}1&\\text\{if\}\\;s^\{t\}\_\{i\}=0\\;\\text\{and\}\\;\\rho^\{t\}\_\{i\}\\in B\_\{X\};\\\\ 1&\\text\{if\}\\;s^\{t\}\_\{i\}=1\\;\\text\{and\}\\;\\rho^\{t\}\_\{i\}\\in S\_\{Y\};\\\\ 0&\\text\{otherwise\.\}\\end\{cases\}\(2\)
Nonetheless, the parameterα\\alphais directly related to the term “neighborhood size” \(of the LLNA transition rule\) stated by Zielinski\[[20](https://arxiv.org/html/2610.10867#bib.bib25)\], as the latter is given byα−1\\alpha\-1\. The neighborhood size of a rule refers to the number of non\-zero neighborhood state configurations a given rule can distinguish\. In case of the Game of Life, it stands for the Moore’s neighborhood, allowing for 8 possible non\-equivalent configurations of living cells and one additional with all neighbors dead\. A LLNA rule that allows forα\\alphadifferent density intervals therefore has a neighborhood size ofα−1\\alpha\-1\. Here we prefer to name this parameterα\\alphaas the resolution of the rule’s density interval, or just rule resolution\.

### 2\.2Rule numbering scheme

A LLNA rule is described by the sets of indicesX,Y⊆\{0,…,α−1\}X,Y\\subseteq\\\{0,\\dots,\\alpha\-1\\\}and the resolutionα\\alpha\. Bigger values forα\\alphaallow more intricate – and possibly better discriminant – rules, at the cost of an exponentially increasing rule space\[[20](https://arxiv.org/html/2610.10867#bib.bib25)\]\. To avoid ambiguity when mentioning automata rules from distinct rule familiesΦα\\Phi^\{\\alpha\}\(i\.e\.the finite set of all rules with the same resolution\), we propose a more complete naming convention\.

The most direct way to represent a LLNA rule is by visualizingX,YX,Yas subscripts and the resolution highlighted, likeRαR\_\{\\alpha\}:BX​SYB\_\{X\}S\_\{Y\}\. Another way is by encoding those indices in a more compact form\. Letβ=∑k=0α−1xk​2k\\beta=\\sum\_\{k=0\}^\{\\alpha\-1\}x\_\{k\}2^\{k\}andσ=∑k=0α−1yk​2k\\sigma=\\sum\_\{k=0\}^\{\\alpha\-1\}y\_\{k\}2^\{k\}be the decimal encoding ofXXandYYrespectively, with the binary coefficientsxk=1⇔k∈Xx\_\{k\}=1\\iff k\\in Xandyk=1⇔k∈Yy\_\{k\}=1\\iff k\\in Y\. Then, a ruleφ\\varphican be expressed by the triple\(α,β,σ\)\(\\alpha,\\beta,\\sigma\), or simplyφβ,σα\\varphi^\{\\alpha\}\_\{\\beta,\\sigma\}\.

For instance, the transition rule from Game of Life is denoted byR9R\_\{9\}:B3​S2,3B\_\{3\}S\_\{2,3\}in the explicit format and byφ8,129\\varphi^\{9\}\_\{8,12\}, in the compact format\.

### 2\.3Network classification with LLNA

One of LLNA’s primary applications is feature extraction from CNs \(characterization task\) to predict their classes \(classification task\), which can be as simple as distinguish between fundamental CN models or as complicated as determine the taxonomic groups of metabolic networks\[[11](https://arxiv.org/html/2610.10867#bib.bib11),[12](https://arxiv.org/html/2610.10867#bib.bib23),[13](https://arxiv.org/html/2610.10867#bib.bib8),[14](https://arxiv.org/html/2610.10867#bib.bib7)\]\. The general LLNA\-based classification model follows a structured pipeline composed by three modules: network automaton, feature extractor, and tabular classifier\.

Theautomatongenerates the state\-time matrix𝐒=\[𝐬0​…​𝐬T\]∈𝒮N×\(T\+1\)\\mathbf\{S\}=\\left\[\\mathbf\{s\}^\{0\}\\dots\\mathbf\{s\}^\{T\}\\right\]\\in\\mathcal\{S\}^\{N\\times\(T\+1\)\}, also called time evolution patterns \(TEPs\), whose shape depends on the number of time stepsTTand the number of nodesNN\. This process is fully determined by the interaction between the network topology𝒢\\mathcal\{G\}, the transition ruleφ\\varphi, and the initial configuration𝐬0\\mathbf\{s\}^\{0\}\.

Theextractormaps the variable\-size temporal data into a fixed\-length feature vector by applying a set of feature extraction functions followed by histogram\-based aggregations\. Feature functions used in previous studies include: Shannon entropy, word entropy and Lempel\-Ziv complexity\[[11](https://arxiv.org/html/2610.10867#bib.bib11)\]; binary\-pattern encoding \(LLNA\-BP\), which performs a sliding window operation over binary sequences, analogous to a 1\-D convolution\[[13](https://arxiv.org/html/2610.10867#bib.bib8)\]; and the density/state\-density TEPs, which combines the node state evolution with the corresponding density matrix\[[14](https://arxiv.org/html/2610.10867#bib.bib7)\]\.

Finally, theclassifierperforms the network classification, mapping the feature vectorΨ\{\\Psi\}to the network classzz, wherezzcan be a Boolean variable \(binary classification\), –e\.g\.identifying if a molecule is carcinogenic – or a non\-binary categorical label \(multi\-class classification\) –e\.g\.pointing which social media community generated a specific interaction networks\. The discriminant capability of the classifier is entirely dependent on the preceding modules, considering that previous works reached optimum results with shallow machine learning models, such as linear kernel SVM andkk\-NN, which do not support representation learning\[[29](https://arxiv.org/html/2610.10867#bib.bib36)\]\.

[Figure 3](https://arxiv.org/html/2610.10867#S2.F3)illustrates the classification pipeline of a dataset\{\(𝒢,z\)\}\\left\\\{\(\\mathcal\{G\},z\)\\right\\\}\. Note that the vector𝐬0\\mathbf\{s\}^\{0\}does not need to be provided in advance, as it is generated at the data preprocessing step or during runtime\.

![Refer to caption](https://arxiv.org/html/2610.10867v1/image/classification-pipeline-simplified.png)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\.A key challenge in this framework is hyper\-parameter optimization\. While the classifier is the only module having learnable parameters, there are several hyper\-parameters in all modules to be optimized as well \(see[Figure 3](https://arxiv.org/html/2610.10867#S2.F3)\), with the automaton rule being the most critical\. The tuning of the classifier must be repeated for every rule in order to find the best configuration, which has a high computational cost when considering the commonly adopted routine of akk\-fold cross validation with a grid search for the hyper\-parameters\. It becomes even worse when considering the additional task of selecting the subset of rules to explore\. As the entire rule space is infinite, thus computationally intractable, previous works adopted a single rule family for the exhaustive search\. But it creates what could be framed as the rule family selection problem, which consists in choosing the smallest rule family that brings the highest classification accuracy in the rule space\. Notably, subsequent studies have largely adopted the best\-performing rules identified in the original work\[[11](https://arxiv.org/html/2610.10867#bib.bib11)\]obtained atΦ9\\Phi^\{9\}, bypassing further optimization due to its expense\.

Hence, it is crucial to identify which rules and rule families are more promising to generate good discriminant patterns, and restrict the automaton simulation and classifier training to them\. The next section provide an overview of existing methods to assess the transition rules, and introduces a novel parameter followed by a navigation strategy to better explore the rule space\.

## 3Methods

The possible ways a given automaton can evolve and what dynamics it can produce is strictly related to its discriminant capacity for network classification problems\. For instance, a transition rule that quickly converges to an uniform global configuration may be unable to distinguish between network classes, while a rule that allow for emergent patterns and periodic structures is much more likely to be useful for this matter\.

In this sense, Wolfram’s categorization\[[30](https://arxiv.org/html/2610.10867#bib.bib19)\]offers a good starting point addressing the automata dynamical behavior qualitatively\. By performing a visual inspection in the generated spatiotemporal patterns of the elementary CA, it groups the transition rules according to the convergence to a state of homogeneity \(class I\), periodicity \(class II\), chaoticity \(class III\) or complexity \(class IV\)\. However, it is impractical to be used at large scale, as it depends on manual observation, lacks formal definition, and allows for a same rule falling in multiple categories when evolved from different initial configurations\. A better approach is to use a summarizing parameter for quantitative analysis, which, ideally, should be able to partition the rule space into groups with meaningful properties\[[31](https://arxiv.org/html/2610.10867#bib.bib37)\]\. Below we present some well\-studied parameters, their formal definition and the interpretation regarding dynamical behavior\.

In the context of Boolean networks, the \(normalized\) Hamming weight accounts for the number of ones in the truth table of a Boolean functionφ\\varphiwithddinput variables,

HWd​\(φ\)=12d\+1​∑q=0d\(dq\)​∑s∈𝒮φ⁡\(s,qd\),\\text\{HW\}\_\{d\}\(\\varphi\)=\\frac\{1\}\{2^\{d\+1\}\}\\sum\_\{q=0\}^\{d\}\\binom\{d\}\{q\}\\sum\_\{s\\in\\mathcal\{S\}\}\\varphi\\\!\\left\(s,\\frac\{q\}\{d\}\\right\),\(3\)intuitively indicating the output bias of the automaton\. The outer sum and the binomial factor cycle through all neighborhood configurations and the inner part considers the activation ofφ\\varphifor a given densityq/dq/d\. Therefore, it represents the probability of obtainingφ⁡\(s,q/d\)=1\\varphi\(s,q/d\)=1given a random configuration in a neighborhood of sizedd\. Note that it can be easily adapted to NAs, such asHW𝒢=∑dP⁡\(d\|𝒢\)​HWd\\text\{HW\}\_\{\\mathcal\{G\}\}=\\sum\_\{d\}P\(d\|\\mathcal\{G\}\)\\text\{HW\}\_\{d\}, and⟨HW⟩\\left\\langle\\text\{HW\}\\right\\rangleas the average over a set of networks\{𝒢\}\\left\\\{\\mathcal\{G\}\\right\\\}\.

This measure is equivalent to Langton’s parameterλ\\lambdafor two state CAs, if the rule space is restricted to strongly quiescent rules and 0 is taken as the quiescent statesqs\_\{q\}\. Under this convention,λ=HWd​\(φ\)\\lambda=\\text\{HW\}\_\{d\}\(\\varphi\)gives the fraction of neighborhood configurations that do not map to the quiescent state for strongly quiescent rules, and serves as a proxy for dynamical regime: low values ofλ\\lambdaare associated with ordered, fixed\-point dynamics, high values with chaotic behavior, and intermediate values near the phase transition with complex, class IV dynamics\[[32](https://arxiv.org/html/2610.10867#bib.bib35)\]\. However,λ\\lambdais known to lose discriminative power for small state spaces \(\|𝒮\|<4\|\\mathcal\{S\}\|<4\), which motivates the search for alternative indicators in the Boolean setting\.

Finally, the average \(Boolean\) sensitivity\[[33](https://arxiv.org/html/2610.10867#bib.bib27)\], analogous to theμ\\mu\-sensitivity\[[34](https://arxiv.org/html/2610.10867#bib.bib26)\], measures the expected number of output changes in response to flipping a single input variable,

BSd​\(φ\)=12d\+1​∑q=0d\(dq\)​∑s∈𝒮\(∂φ∂s\+q​∂φ∂q−\+\(d−q\)​∂φ∂q\+\)=ISd​\(φ\)\+NSd​\(φ\),\\text\{BS\}\_\{d\}\(\\varphi\)=\\frac\{1\}\{2^\{d\+1\}\}\\sum\_\{q=0\}^\{d\}\\binom\{d\}\{q\}\\sum\_\{s\\in\\mathcal\{S\}\}\\left\(\\frac\{\\partial\\varphi\}\{\\partial s\}\+q\\frac\{\\partial\\varphi\}\{\\partial q^\{\-\}\}\+\(d\-q\)\\frac\{\\partial\\varphi\}\{\\partial q^\{\+\}\}\\right\)=\\text\{IS\}\_\{d\}\(\\varphi\)\+\\text\{NS\}\_\{d\}\(\\varphi\),\(4\)where∂φ∂s=φ⁡\(s,qd\)⊕φ⁡\(s⊕1,qd\)\\frac\{\\partial\\varphi\}\{\\partial s\}=\\varphi\\\!\\left\(s,\\frac\{q\}\{d\}\\right\)\\oplus\\varphi\\\!\\left\(s\\oplus 1,\\frac\{q\}\{d\}\\right\)and∂φ∂q±=φ⁡\(s,qd\)⊕φ⁡\(s,q±1d\)\\frac\{\\partial\\varphi\}\{\\partial q^\{\\pm\}\}=\\varphi\\\!\\left\(s,\\frac\{q\}\{d\}\\right\)\\oplus\\varphi\\\!\\left\(s,\\frac\{q\\pm 1\}\{d\}\\right\)are related to the concept of Boolean derivatives\[[35](https://arxiv.org/html/2610.10867#bib.bib31)\]and denote the impact of a state change in the central node \(identity\) and its neighborhood, respectively\[[36](https://arxiv.org/html/2610.10867#bib.bib33)\]\. Similar toHWd\\text\{HW\}\_\{d\}, all possible configurations are evaluated, but now in terms of how likely the transition function is to be affected by perturbations\. A high value ofBSd​\(φ\)\\text\{BS\}\_\{d\}\(\\varphi\)represents high sensitivity to small changes, therefore correlating to chaoticity\. Furthermore, the same aggregation can be applied to compute network\- and dataset\-level descriptors\.

These measures are what could be called genotype parameters, as they try to describe the dynamical behavior by looking at static attributes of the automaton and the network\. Opposed to the phenotype parameters, which actually assess the dynamical outcome, they offer a good glimpse of the system behavior without requiring the full simulation\[[31](https://arxiv.org/html/2610.10867#bib.bib37),[36](https://arxiv.org/html/2610.10867#bib.bib33)\]\.

Here we take one step back and disregard topology effects, investigating to what extent the transition rule itself correlates to the dynamic regime of a NA\. By removing the network topology from the analysis, we can focus on the global ability of the rule to generate interesting dynamics, which is a proxy to the automaton effectiveness in classification problems\. Below we introduce a novel genotype parameter called jaggedness, which considers only the shape of the transition rule\.

### 3\.1Measuring the rule irregularity

Consider two rulesφ21,45\\varphi^\{5\}\_\{21,4\}andφ19,45\\varphi^\{5\}\_\{19,4\}\. They are almost identical, differing only by one shifted density interval inBXB\_\{X\}: while the first rule is composed by three non\-adjacent intervals,ℋ05,ℋ25\\mathcal\{H\}\_\{0\}^\{5\},\\mathcal\{H\}\_\{2\}^\{5\}andℋ45\\mathcal\{H\}\_\{4\}^\{5\}, the second one has two contiguous blocks,ℋ05,ℋ15\\mathcal\{H\}\_\{0\}^\{5\},\\mathcal\{H\}\_\{1\}^\{5\}andℋ45\\mathcal\{H\}\_\{4\}^\{5\}\(see[Figure 4](https://arxiv.org/html/2610.10867#S3.F4)\)\. Even though both rules cover the same number of density intervals, we can say thatφ21,45\\varphi^\{5\}\_\{21,4\}is more irregular thanφ19,45\\varphi^\{5\}\_\{19,4\}, because its diagram is more “jagged” than the one of the latter\.

![Refer to caption](https://arxiv.org/html/2610.10867v1/image/jaggedness_comparison.png)Figure 4:Diagram of the born condition for rulesφ21,45\\varphi^\{5\}\_\{21,4\}\(top\) andφ19,45\\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α=5\\alpha=5: dashed \(orange\) for occurring discontinuities, dotted \(gray\) for non\-occurring ones\.More formally,jaggednesscan be defined as the number of discontinuities in rule diagram within\]0,1\[\]0,1\[\. Using the binary coefficientsxk,ykx\_\{k\},y\_\{k\}from the rule encoding and the XOR operator⊕\\oplus, we have

J⁡\(φα\)=∑s∈𝒮∑k=0α−2\(φ⁡\(s,kα\)⊕φ⁡\(s,k\+1α\)\)=∑k=0α−2\(xk⊕xk\+1\)\+∑k=0α−2\(yk⊕yk\+1\),\\begin\{split\}J\(\\varphi^\{\\alpha\}\)&=\\sum\_\{s\\in\\mathcal\{S\}\}\\sum\_\{k=0\}^\{\\alpha\-2\}\\left\(\\varphi\\\!\\left\(s,\\frac\{k\}\{\\alpha\}\\right\)\\oplus\\varphi\\\!\\left\(s,\\frac\{k\+1\}\{\\alpha\}\\right\)\\right\)\\\\ &=\\sum\_\{k=0\}^\{\\alpha\-2\}\(x\_\{k\}\\oplus x\_\{k\+1\}\)\+\\sum\_\{k=0\}^\{\\alpha\-2\}\(y\_\{k\}\\oplus y\_\{k\+1\}\)\\;,\\end\{split\}\(5\)which can be further normalized, as follows\.

J¯​\(φα\)=J⁡\(φα\)2​\(α−1\)\\bar\{J\}\(\\varphi^\{\\alpha\}\)=\\frac\{J\(\\varphi^\{\\alpha\}\)\}\{2\(\\alpha\-1\)\}\(6\)
For a given resolutionα\\alpha, there areα−1\\alpha\-1possible discontinuities for each transition criterion \(born and survive\) and each of them can be organized in\(α−1n\)\\binom\{\\alpha\-1\}\{n\}ways \(combinations\), whereJ⁡\(φα\)=n∈\{0,…,2​\(α−1\)\}J\(\\varphi^\{\\alpha\}\)=n\\in\\\{0,\\dots,2\(\\alpha\-1\)\\\}\. As a combination only indicates where there is a discontinuity, without informing which adjacent interval is present in the rule, a same combination can generate two distinct rules\. So, the number of rule with same jaggedness is

\|Φnα\|=\[2​\(α−1n\)\]born×\[2​\(α−1n\)\]survive≡4​\(2​\(α−1\)n\)\\left\|\\Phi^\{\\alpha\}\_\{n\}\\right\|=\\left\[2\\binom\{\\alpha\-1\}\{n\}\\right\]\_\{\\\!\\text\{born\}\}\\times\\left\[2\\binom\{\\alpha\-1\}\{n\}\\right\]\_\{\\\!\\text\{survive\}\}\\equiv 4\\binom\{2\(\\alpha\-1\)\}\{n\}\(7\)and, ultimately,\|Φα\|=∑n\|Φnα\|=22​α\\left\|\\Phi^\{\\alpha\}\\right\|=\\sum\_\{n\}\\left\|\\Phi^\{\\alpha\}\_\{n\}\\right\|=2^\{2\\alpha\}\.

Taking as example the top rule from[Figure 4](https://arxiv.org/html/2610.10867#S3.F4),φ=φ521,4=R5:B0,2,4S2\\varphi=\\varphi^\{5\}\_\{21,4\}=R\_\{5\}\\text\{:\}B\_\{0,2,4\}S\_\{2\}, there are 4 discontinuities inBXB\_\{X\}and 2 inSYS\_\{Y\}; as a resultJ⁡\(φ\)=6J\(\\varphi\)=6andJ¯​\(φ\)=0\.75\\bar\{J\}\(\\varphi\)=0\.75\. Rules with this jaggedness correspond to approximately 11% of the rule familyΦ5\\Phi^\{5\}\.

In terms of the impact of changes in the node’s states, the jaggedness shares the same interpretation asμ\\mu\-sensitivity and BS, but from a simpler and topology\-independent perspective\. Small values typically represent rules with boring behavior, meaning that a small changes on the neighborhood configuration rarely impacts the outcome of the transition function\. On the other hand, high values may allow for chaotic behavior, quickly amplifying any perturbation and leading unpredictable trajectories\.

This connection is also observed mathematically\. The BS can be understood as the probability of two distinct input configurations cause different outputs multiplied by the probability of one or more nodes being simultaneously disturbed, thus transforming one input configuration into the other\. Note that the latter only refers to the topology of the CN, but the former depends on the rule\. Furthermore, the rule\-dependent part can be separated in two effects: identity sensitivity \(IS\), which relates to a notion of jaggedness between transition criteria \(e\.g\.∑kxk⊕yk\\sum\_\{k\}x\_\{k\}\\oplus y\_\{k\}\); and neighborhood sensitivity \(NS\), which reflects a weighted version of the jaggedness wheneverdi=α−1d\_\{i\}=\\alpha\-1\.

![Refer to caption](https://arxiv.org/html/2610.10867v1/image/corr_pearson-x-jag.png)Figure 5:Correlation of the normalized jaggedness with genotype parameters, for rule families with resolution from 3 to 6\.
### 3\.2Navigating through rule families

Suppose we are interested in finding the rule that maximizes the classification performanceff\. It is known that the maximum value offfobtained for a given rule family,fmaxαf^\{\\alpha\}\_\{\\text\{max\}\}, tends to grow asymptotically asα\\alphaincreases, with diminishing improvements after each step\[[20](https://arxiv.org/html/2610.10867#bib.bib25)\]\. Also, in the absence of any information to guide the rule space exploration, finding this particular rule for higher resolutions is practically unfeasible\. To overcome this problem, one can define a neighborhood scheme in the rule space such that two neighboring rules may have similar values offf, upon a \(meta\)heuristic search could find a local optimumf′f^\{\\prime\}that approximates or equals the global optimumf∗f^\{\*\}\[[37](https://arxiv.org/html/2610.10867#bib.bib6), chapter II\.4\]\.

Assuming that the jaggedness is a good indicator of the rule discriminative behavior, we propose to use the rule space partitioned byα\\alphaandJJas the neighborhood schema, and to apply a neighborhood navigation strategy inspired by perturbation procedure from the Iterated Local Search \(ILS\) metaheuristic\[[38](https://arxiv.org/html/2610.10867#bib.bib24), chapter 12\]\(see[Figure 6](https://arxiv.org/html/2610.10867#S3.F6)\)\. Starting with a small family, we look for the best performing partition on average \(local search step\), then map it to new ones in the next family with similar normalized jaggedness \(perturbation step\), repeating until a stop condition is satisfied\.

![Refer to caption](https://arxiv.org/html/2610.10867v1/image/rule-space-navigation.png)Figure 6:Navigation in LLNA rule space inspired by the ILS perturbation procedure\. Each plane denotes a rule family partitioned by jaggedness\. The partitionsΦnα\\Phi^\{\\alpha\}\_\{n\}are represented by the ellipses with their normalized jaggedness indicated\. Arrows denote the perturbation, defined as a mapping that tries to preserveJ¯\\bar\{J\}\. Bold arrows mark the exact mapping\.We now describe in what circumstances it is possible to do such optimization task with a lower computational cost than exploring an entire rule family\. For that, it is important to consider two constraints\. As the heuristics does not guarantee to findf∗f^\{\*\}, it is only worth to apply it if the total number of explored rules during the navigation between partitions is much smaller than the size of the last explored family \(efficiency constraint\)\. Additionally, the perturbation step needs to reach more than one partition in order to avoid being stuck in local optimum regions \(variability constraint\)\.

First, let us investigate how a subset of rules grows when mapped to a new subset\. LetKGK\_\{\\text\{G\}\}denote the growth rate of the size of a rule subset given a mapping scheme\. In the trivial case we map the entire rule family, thusKG​\(α↦α\+1\)=\|Φα\+1\|/\|Φα\|=4K\_\{\\text\{G\}\}\(\\alpha\\mapsto\\alpha\+1\)=\\left\|\\Phi^\{\\alpha\+1\}\\right\|/\\left\|\\Phi^\{\\alpha\}\\right\|=4\. We can also map one partition to another with higher jaggedness in the same family, such thatKG​\(n↦n\+1\|α\)=\|Φn\+1α\|/\|Φnα\|=2​\(α−1\)−nn\+1K\_\{\\text\{G\}\}\(n\\mapsto n\+1\|\\alpha\)=\\left\|\\Phi^\{\\alpha\}\_\{n\+1\}\\right\|/\\left\|\\Phi^\{\\alpha\}\_\{n\}\\right\|=\\frac\{2\(\\alpha\-1\)\-n\}\{n\+1\}\. Finally, we can map to a new family preservingJ¯\\bar\{J\},

KG​\(\(α,n\)↦\(α\+1,m\)\|J¯\)=\|Φmα\+1\|\|Φnα\|=2​α​\(2​α−1\)​n\!​\(2​α−n−2\)\!m\!​\(2​α−m\)\!\.K\_\{\\text\{G\}\}\(\(\\alpha,n\)\\mapsto\(\\alpha\+1,m\)\|\\bar\{J\}\)=\\frac\{\\left\|\\Phi^\{\\alpha\+1\}\_\{m\}\\right\|\}\{\\left\|\\Phi^\{\\alpha\}\_\{n\}\\right\|\}=2\\alpha\(2\\alpha\-1\)\\frac\{n\!\(2\\alpha\-n\-2\)\!\}\{m\!\(2\\alpha\-m\)\!\}\.\(8\)
There are only 3 values ofnnthat satisfyJ¯​\(φ∈Φnα\)=J¯​\(φ∈Φmα\+1\)\\bar\{J\}\(\\varphi\\in\\Phi^\{\\alpha\}\_\{n\}\)=\\bar\{J\}\(\\varphi\\in\\Phi^\{\\alpha\+1\}\_\{m\}\)and, consequently, Eq\. \([8](https://arxiv.org/html/2610.10867#S3.E8)\), beingn∈\{0,α−1,2​\(α−1\)\}n\\in\\left\\\{0,\\alpha\-1,2\(\\alpha\-1\)\\right\\\}; thusJ¯​\(φ\)∈\{0,0\.5,1\}\\bar\{J\}\(\\varphi\)\\in\\left\\\{0,0\.5,1\\right\\\}\. When the exact mapping it is not possible, we can approximate it by identifying two consecutive integersm−,m\+∈ℕm^\{\-\},m^\{\+\}\\in\\mathbb\{N\}, such thatm\+−m−=1m^\{\+\}\-m^\{\-\}=1andJ¯​\(φ∈Φm−α\+1\)<J¯​\(φ∈Φnα\)<J¯​\(φ∈Φm\+α\+1\)\\bar\{J\}\(\\varphi\\in\\Phi^\{\\alpha\+1\}\_\{m^\{\-\}\}\)<\\bar\{J\}\(\\varphi\\in\\Phi^\{\\alpha\}\_\{n\}\)<\\bar\{J\}\(\\varphi\\in\\Phi^\{\\alpha\+1\}\_\{m^\{\+\}\}\), leading to

KG​\(\(α,n\)↦\(α\+1,\{m−,m\+\}\)\|J¯\)=\|Φm−α\+1\|\+\|Φm\+α\+1\|\|Φnα\|=\(2​α\+1\)​2​α​\(2​α−1\)\(2​α−n−1\)​\(n\+1\)​D,K\_\{\\text\{G\}\}\(\(\\alpha,n\)\\mapsto\(\\alpha\+1,\\\{m^\{\-\},m^\{\+\}\\\}\)\|\\bar\{J\}\)=\\frac\{\\left\|\\Phi^\{\\alpha\+1\}\_\{m^\{\-\}\}\\right\|\+\\left\|\\Phi^\{\\alpha\+1\}\_\{m^\{\+\}\}\\right\|\}\{\\left\|\\Phi^\{\\alpha\}\_\{n\}\\right\|\}=\\frac\{\(2\\alpha\+1\)2\\alpha\(2\\alpha\-1\)\}\{\(2\\alpha\-n\-1\)\(n\+1\)D\},\(9\)whereD=2​α−nD=2\\alpha\-nif0<n<α−10<n<\\alpha\-1andD=n\+2D=n\+2ifα−1<n<2​\(α−1\)\\alpha\-1<n<2\(\\alpha\-1\)\.

Note that the exploration variability constraint is already satisfied by the approximated mapping but not by the exact one\. The expected behavior can be, therefore, achieved by includingn↦m±1n\\mapsto m\\pm 1in the exact operation\. Equation \([10](https://arxiv.org/html/2610.10867#S3.E10)\) summarizes the correct mapping between partitions,

Φnα↦\{Φmα\+1∪Φm\+1α\+1if​n=0;Φmα\+1∪Φm\+1α\+1∪Φm−1α\+1if​n=α−1;Φmα\+1∪Φm−1α\+1if​n=2​\(α−1\);Φm−α\+1∪Φm\+α\+1otherwise\.\\Phi^\{\\alpha\}\_\{n\}\\mapsto\\begin\{cases\}\\Phi^\{\\alpha\+1\}\_\{m\}\\cup\\Phi^\{\\alpha\+1\}\_\{m\+1\}&\\text\{if\}\\;n=0;\\\\ \\Phi^\{\\alpha\+1\}\_\{m\}\\cup\\Phi^\{\\alpha\+1\}\_\{m\+1\}\\cup\\Phi^\{\\alpha\+1\}\_\{m\-1\}&\\text\{if\}\\;n=\\alpha\-1;\\\\ \\Phi^\{\\alpha\+1\}\_\{m\}\\cup\\Phi^\{\\alpha\+1\}\_\{m\-1\}&\\text\{if\}\\;n=2\(\\alpha\-1\);\\\\ \\Phi^\{\\alpha\+1\}\_\{m^\{\-\}\}\\cup\\Phi^\{\\alpha\+1\}\_\{m^\{\+\}\}&\\text\{otherwise\}\.\\\\ \\end\{cases\}\(10\)
Now, letcα\+i=∑\{n\}\|Φnα\+i\|c\_\{\\alpha\+i\}=\\sum\_\{\\left\\\{n\\right\\\}\}\\left\|\\Phi^\{\\alpha\+i\}\_\{n\}\\right\|be the cardinality of the partitions explored inΦα\+i\\Phi^\{\\alpha\+i\}, subject to\{n\}⊂\{0,…,2​\(α\+i−1\)\}\\left\\\{n\\right\\\}\\subset\\left\\\{0,\\dots,2\(\\alpha\+i\-1\)\\right\\\}\. Assuming an average⟨KG⟩\\left\\langle K\_\{\\text\{G\}\}\\right\\ranglefor the mapping\(α\+i,\{n\}\)↦\(α\+i\+1,\{m\}\)\(\\alpha\+i,\\\{n\\\}\)\\mapsto\(\\alpha\+i\+1,\\\{m\\\}\), the exploration rate,i\.e\.the number of rules explored after a finite sequence of mappingsα↦α\+1↦…↦α\+l\\alpha\\mapsto\\alpha\+1\\mapsto\\dots\\mapsto\\alpha\+ldivided by the size of the final rule family, is given by the geometric series

KE=∑i=0lcα\+i\|Φα\+l\|=∑i=0lcα​⟨KG⟩i\|Φα\+l\|=cα4l​\|Φα\|​\(⟨KG⟩l\+1−1⟨KG⟩−1\)\.K\_\{\\text\{E\}\}=\\frac\{\\sum\_\{i=0\}^\{l\}c\_\{\\alpha\+i\}\}\{\\left\|\\Phi^\{\\alpha\+l\}\\right\|\}=\\frac\{\\sum\_\{i=0\}^\{l\}c\_\{\\alpha\}\\left\\langle K\_\{\\text\{G\}\}\\right\\rangle^\{i\}\}\{\\left\|\\Phi^\{\\alpha\+l\}\\right\|\}=\\frac\{c\_\{\\alpha\}\}\{4^\{l\}\\left\|\\Phi^\{\\alpha\}\\right\|\}\\left\(\\frac\{\\left\\langle K\_\{\\text\{G\}\}\\right\\rangle^\{l\+1\}\-1\}\{\\left\\langle K\_\{\\text\{G\}\}\\right\\rangle\-1\}\\right\)\.\(11\)
The efficiency constraint thus requiresKE≪1K\_\{\\text\{E\}\}\\ll 1, which, for⟨KG⟩=4\\left\\langle K\_\{\\text\{G\}\}\\right\\rangle=4\(worst case\), is obtained whenevercα≪34​\|Φα\|c\_\{\\alpha\}\\ll\\frac\{3\}\{4\}\\left\|\\Phi^\{\\alpha\}\\right\|\. As example, by starting the exploration at the 3 central partitions ofΦ4\\Phi^\{4\}and considering⟨KG⟩=4\\left\\langle K\_\{\\text\{G\}\}\\right\\rangle=4, we havec4≈0\.20​\|Φ4\|c\_\{4\}\\approx 0\.20\\left\|\\Phi^\{4\}\\right\|andliml→∞KE≈0\.26\\lim\_\{l\\to\\infty\}K\_\{\\text\{E\}\}\\approx 0\.26, which is a relevant improvement compared to the exhaustive search\.

Also, it is possible to improve the theoretical computational efficiency by adopting any local search that does not fully explore the selected partitions\. For instance, a simple random sampling of half of the partition rules will double the efficiency, although its impact in the overall efficacy, in terms of the resultingf′f^\{\\prime\}, is unknown\. The experiments in the next section analyze some scenarios, with full and partial \(sampled\) exploration of the partitions, and also restricting the rules to a subset of predefinedJ¯\\bar\{J\}range or only to quiescent ones\.

A final remark about the proposed optimization method is that, although being more efficient than the exhaustive search, the naive implementation of the local search as done here, consisting of a full \(or partial\) exploration of rule family partitions, still implies in an exponential time complexity in terms of resolution increase\. For real applications, it is recommended to implement more sophisticate \(meta\)heuristics for the local search step, with predefined convergence and stopping criteria, thus ensuring a polynomial time complexity\.

## 4Results and Discussion

To evaluate the real effectiveness of the jaggedness to organize the rule space and its usefulness for guiding a search\-based optimization procedure, we selected a total of 23 network datasets, half of which have been studied in LLNA\-related works\[[11](https://arxiv.org/html/2610.10867#bib.bib11),[13](https://arxiv.org/html/2610.10867#bib.bib8),[14](https://arxiv.org/html/2610.10867#bib.bib7),[20](https://arxiv.org/html/2610.10867#bib.bib25)\]and the other half in works applying deep learning models for graphs\[[17](https://arxiv.org/html/2610.10867#bib.bib14),[19](https://arxiv.org/html/2610.10867#bib.bib13),[39](https://arxiv.org/html/2610.10867#bib.bib9)\]\. They vary in terms of size, connectivity, number of classes and balancing \([Table 1](https://arxiv.org/html/2610.10867#S4.T1)\), covering a broad number of scopes111For additional explanation of the network datasets and data availability, we refer the reader to TUD and SNAP projects\[[40](https://arxiv.org/html/2610.10867#bib.bib45),[41](https://arxiv.org/html/2610.10867#bib.bib10)\]and Zenodo repositories\[[42](https://arxiv.org/html/2610.10867#bib.bib47),[43](https://arxiv.org/html/2610.10867#bib.bib48)\]\.:

- •5 synthetic datasets generated using combinations of theoretical models \(ER, BA, WS, geographic, non\-linear BA\), with and without noise \(chance to permute an edge\);
- •6 social networks datasets, most of them being groups of ego nets from different communities at the same social media, others being friendship bounds from distinct media;
- •5 bioinformatics datasets, with networks representing chemical compounds labeled according to desired properties \(e\.g\.carcinogenic or not\);
- •7 metabolic networks datasets, describing interactions between molecules from taxonomic groups of living beings \(e\.g\.fungi, plants, fish, mammals\)\.

dataset\# classes\# netsnets/class\# nodesavg\. degree\[[11](https://arxiv.org/html/2610.10867#bib.bib11)\]classic4112002800500 – 20004 – 16\[[11](https://arxiv.org/html/2610.10867#bib.bib11)\]scalefree550010010008\[[13](https://arxiv.org/html/2610.10867#bib.bib8)\]noise=10%880010010007\.6 – 8\.5\[[13](https://arxiv.org/html/2610.10867#bib.bib8)\]noise=20%880010010007\.6 – 8\.5\[[13](https://arxiv.org/html/2610.10867#bib.bib8)\]noise=30%880010010007\.6 – 8\.5\[[13](https://arxiv.org/html/2610.10867#bib.bib8)\]actinobacteria322963 – 96803 – 15333\.4 – 3\.6\[[13](https://arxiv.org/html/2610.10867#bib.bib8)\]animals464161392 – 19193\.3 – 3\.4\[[13](https://arxiv.org/html/2610.10867#bib.bib8)\]firmicutes\-bacilli445486 – 143530 – 12673\.2 – 3\.6\[[13](https://arxiv.org/html/2610.10867#bib.bib8)\]fungi46817624 – 15403\.0 – 3\.4\[[13](https://arxiv.org/html/2610.10867#bib.bib8)\]kingdom419649448 – 20952\.9 – 3\.5\[[13](https://arxiv.org/html/2610.10867#bib.bib8)\]plant333111241 – 18703\.4 – 3\.5\[[13](https://arxiv.org/html/2610.10867#bib.bib8)\]protist4287598 – 14012\.9 – 3\.4\[[11](https://arxiv.org/html/2610.10867#bib.bib11)\]social\-circles21104131 – 9735 – 49380\.9 – 363\[[17](https://arxiv.org/html/2610.10867#bib.bib14)\]imdb\-binary210005005 – 381\.2 – 4\.6\[[17](https://arxiv.org/html/2610.10867#bib.bib14)\]reddit\-binary2200010006 – 14001\.0 – 4\.7\[[44](https://arxiv.org/html/2610.10867#bib.bib44)\]deezer\-egos296294159 – 54704 – 1230\.9 – 7\.1\[[44](https://arxiv.org/html/2610.10867#bib.bib44)\]twitch\-egos212709458761 – 683335 – 331\.0 – 5\.7\[[44](https://arxiv.org/html/2610.10867#bib.bib44)\]github\-stargazers2127255917 – 68085 – 3970\.9 – 9\.7\[[45](https://arxiv.org/html/2610.10867#bib.bib41)\]dd21178487 – 69115 – 22771\.0 – 3\.9\[[46](https://arxiv.org/html/2610.10867#bib.bib42)\]mutag218863 – 1256 – 171\.1 – 2\.1\[[47](https://arxiv.org/html/2610.10867#bib.bib43)\]nci1241102053 – 20574 – 820\.6 – 2\.2\[[47](https://arxiv.org/html/2610.10867#bib.bib43)\]nci109241272048 – 20796 – 810\.5 – 2\.1\[[48](https://arxiv.org/html/2610.10867#bib.bib40)\]proteins21113450 – 6634 – 2630\.7 – 3\.8Table 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\.For each dataset, a small and balanced subset of a maximum of 20 networks per class was created, on which all rules from familiesα∈\{2,…,7\}\\alpha\\in\\\{2,\\dots,7\\\}were applied forT=100T=100time steps\. The feature vectors were generated using density TEPs with segmentation by node degree\[[14](https://arxiv.org/html/2610.10867#bib.bib7)\], framed in histograms with 40 bins\. The overall classification pipeline was evaluated by a55\-fold cross validation procedure repeated three times, having a Support Vector Machine with linear kernel as classifier in accordance with previous LLNA works\. The chosen performance metricffwas the classification accuracy,i\.e\.the fraction of network samples classified correctly\.

Below we present how the size of the rule family and the jaggedness is correlated with the classification accuracy\. We applied the classification pipeline to the 23 datasets and for all of them it was possible to find at least one rule withf≥60%f\\geq 60\\%, which is the minimum accuracy threshold adopted\.

### 4\.1Impact of resolution on the classification accuracy

First let us analyze the accuracy for LLNA rule familiesα=2,…,7\\alpha=2,\\dots,7\([Figure 7](https://arxiv.org/html/2610.10867#S4.F7)\)\. This analysis complements a recent study\[[20](https://arxiv.org/html/2610.10867#bib.bib25)\]by considering entire rule families instead of just the best\-performing rules and by its broader scope\.

![Refer to caption](https://arxiv.org/html/2610.10867v1/image/acc_distrib-x-rule_res.png)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\.In general, the maximum accuracy grows as the resolution increases asymptotically, confirming previous findings\[[20](https://arxiv.org/html/2610.10867#bib.bib25)\]\. The median accuracy, however, presents varying patterns: an increase for all the top dataset, and a constant or slightly oscillating curve for the bottom ones\. Also, while some datasets reach 100% accuracy already for small resolutions, such as any synthetic, others may demand an exploration in much larger rule families \(e\.g\.fungi networks\)\.

These results highlight the difficult trade\-off between the computation cost of the rule optimization and the classification performance gain\. It is not clear if a bigger rule family or a particular rule restriction would improve the current optimum accuracy, and not even if this improvement could be obtained by randomly testing new rules or just through the exhaustive exploration – which reinforces the necessity for better, informed search strategies for the rule space\.

### 4\.2Impact of topology on the classification accuracy

Besides the similarities in the calculation and interpretation of jaggedness and the sensitivity measures \(specially BS and its neighborhood\-dependent part\), it is expected that richer measures such as BS and HW perform better in capturing the dynamical behavior of the automaton, as the jaggedness is, by definition, simpler\. Particularly, it cannot identify which density interval has the biggest impact on sensitivity, as it depends on the node degree distribution\. It is surprising that, when comparing the correlation of the accuracy with the jaggedness and other genotype parameters over the networks of each dataset, the former exhibits a stronger correlation \([Figure 8](https://arxiv.org/html/2610.10867#S4.F8)\)\.

![Refer to caption](https://arxiv.org/html/2610.10867v1/image/corr_pearson-x-acc.png)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\.A possible explanation is that, in contrast with⟨BS⟩\\left\\langle\\text\{BS\}\\right\\rangle, by giving equal importance to every density interval the jaggedness can be more affected by the discontinuities between intervals close to the extremities, which may be crucial for the dynamics used for classification\. While for the⟨HW⟩\\left\\langle\\text\{HW\}\\right\\rangle, the simple chance for a given output seems insufficient to describe the dynamical behavior related to the rules good for network classification\.

In total, 13 out of the 23 considered datasets show some degree of correlation between accuracy and normalized jaggedness, being consistent across different rule families\.

### 4\.3Impact of jaggedness on the classification accuracy

Now let us consider how the jaggedness organizes the rule families in terms of accuracy \(see[Figure 9](https://arxiv.org/html/2610.10867#S4.F9)\)\. We will limit this analysis to four datasets and resolutions 4 to 7, as the findings extend to the other datasets and larger rule families\.

![Refer to caption](https://arxiv.org/html/2610.10867v1/image/jaggedness_distrib_noise10.png)

![Refer to caption](https://arxiv.org/html/2610.10867v1/image/jaggedness_distrib_actinobacteria.png)

![Refer to caption](https://arxiv.org/html/2610.10867v1/image/jaggedness_distrib_socialcircles.png)

![Refer to caption](https://arxiv.org/html/2610.10867v1/image/jaggedness_distrib_redditbinary.png)

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\.Starting with the synthetic noisy dataset andα=4\\alpha=4, the best accuracy found is 97% for a rule withJ¯=0\.5\\bar\{J\}=0\.5, but the average accuracy in this region is around 85%, while forJ¯=1\.0\\bar\{J\}=1\.0we have rules that are much better on average, and the best rule is almost as good as the global best\. Proceeding to the diagrams with higherα\\alpha, the general shape remains the same: high performance variation forJ¯<0\.4\\bar\{J\}<0\.4, low variation forJ¯≥0\.8\\bar\{J\}\\geq 0\.8and better chances to find rules among the top 1% when0\.5≤J¯<1\.00\.5\\leq\\bar\{J\}<1\.0\.

The same analysis applies to the other three datasets\. The 2\-D histograms maintain their general shape over increasing resolution, and the average accuracy curve – denoted by the circles and triangles – quickly stabilizes\. The only feature that is not present for all datasets is the skewed distribution\. In the top datasets \(synthetic and metabolic\), there are particular values ofJ¯\\bar\{J\}for which the rules accuracies vary much less and still can reach a very high classification performance\. The datasets at the bottom do not have the same characteristic, being either insensitive to changes in the jaggedness or having an inconsistent sensitivity\.

It is reasonable that, for those datasets where jaggedness provide some structure, the best rules appear in general at highJ¯\\bar\{J\}, which are more sensitive to state density changes in the neighborhood, but rarely atJ¯≈1\.0\\bar\{J\}\\approx 1\.0, as it could be too sensitive and therefore chaotic\. For the other datasets, the absence of a clear pattern could either indicate that the jaggedness does not correlate with the properties that a good discriminative rule must have, or that any existing structure is only visible at bigger rule families\. Particularly, the social\-circles dataset was the only case with inconsistent pattern of accuracy distribution among consecutive families\.

### 4\.4Effectiveness of heuristic optimization

The performance of the heuristic search is compared with the exhaustive approach in two scenarios\. First, we test its effectiveness in finding good classification rules when exploring whole rule family partitions \([Figure 10](https://arxiv.org/html/2610.10867#S4.F10)\)\. Then, we evaluate the impact of the partial exploration in the heuristic search performance, by applying a sampling in the rule partitions \([Figure 11](https://arxiv.org/html/2610.10867#S4.F11)\)\. For each sampling fraction, the heuristic search was repeated 25 times\. Three metrics are used for this comparison:

- •The rank of a ruleφ∈Φα\\varphi\\in\\Phi^\{\\alpha\}, given byrank¯​\(φ\)=i/\|Φα\|\\overline\{\\text\{rank\}\}\(\\varphi\)=i/\|\\Phi^\{\\alpha\}\|, denotes the chance of finding a rule of equal or higher accuracy, wherei∈\{1,…,22​α\}i\\in\\\{1,\\dots,2^\{2\\alpha\}\\\}means thatφ\\varphiis theii\-th best rule in that family;
- •The exploration ratioKEK\_\{\\text\{E\}\}accounts for how many rules were evaluated since the beginning of the exploration divided by the size of the current rule family;
- •The current accuracy error is the relative difference between the accuracy of the best current rule to the global optimum of the current rule family:Δ​f¯c=1−f′/fmaxα\\Delta\\bar\{f\}\_\{c\}=1\-f^\{\\prime\}/f^\{\\alpha\}\_\{\\text\{max\}\}

The first scenario shows the performance of the heuristic approach \(see[Figure 10](https://arxiv.org/html/2610.10867#S4.F10)\)\. As the resolution increases, the heuristic finds rules closer to the current global optimum \(left plot\) with aKEK\_\{\\text\{E\}\}that decays exponentially and approaches 20% on average \(middle plot\)\. Also,Δ​f¯c\\Delta\\bar\{f\}\_\{c\}indicates that even without finding the rule with best accuracy it can find competitive solutions for the rule optimization problem \(right plot\), sometimes even surpassing the result obtained by the exhaustive search \(Δ​f¯c<0\\Delta\\bar\{f\}\_\{c\}<0\)\. This unexpected behavior is explained by the accuracy versus resolution curve that is not strictly monotonic\. As occurs for the github\-stargazers and twitch\-egos social datasets \([Figure 7](https://arxiv.org/html/2610.10867#S4.F7)\), the incremental optimization of ILS\-based heuristics can find particular rules in smaller rule families that are better than all other rules in the immediately subsequent families\.

![Refer to caption](https://arxiv.org/html/2610.10867v1/image/heuristics-scope.png)Figure 10:Performance of the heuristic search executing a full exploration of the rule family partitions, segmented by dataset scope, with 95% confidence interval\.The second scenario highlights the robustness of the method and the trade\-off between computational complexity and classification performance \(see[Figure 11](https://arxiv.org/html/2610.10867#S4.F11)\)\. Even when we reduce the fraction of rules explored in the selected partitions and, consequently the exploration rateKEK\_\{\\text\{E\}\}, the resulting increase ofΔ​f¯c\\Delta\\bar\{f\}\_\{c\}remains low\. Notably, the method maintainsΔ​f¯c<4%\\Delta\\bar\{f\}\_\{c\}<4\\%despite the sampling fraction of 0\.4, the case whereKEK\_\{\\text\{E\}\}approaches 10% – half of the value obtained in the first scenario\.

![Refer to caption](https://arxiv.org/html/2610.10867v1/image/heuristics-sampling.png)Figure 11:Performance of the heuristic search executing a partial exploration of the rule family partitions, segmented by sampling fraction, with 95% confidence interval\.Ultimately, the rules explored by the heuristic strategy have better general performance than the exhaustive approach \(see[Figure 12](https://arxiv.org/html/2610.10867#S4.F12)\), resulting in a distribution with higher median accuracy for 22 of the 23 datasets \(p​\-value≤0\.05p\\text\{\-value\}\\leq 0\.05\)\.

![Refer to caption](https://arxiv.org/html/2610.10867v1/image/heuristics-distrib.png)Figure 12:Accuracy distribution of rules explored by exhaustive search \(α=7\\alpha=7\) versus heuristic search \(α=3,…,7\\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\.

## 5Conclusion

The jaggedness is a quantitative parameter based on the visual notion of rule’s shape irregularity, and provides valuable insight into the behavior of Life\-Like Network Automata when classifying networks, guiding the understanding and prediction of rule accuracy\.

From a theoretical standpoint, the jaggedness aligns with established measures such as Hamming weight and Boolean sensitivity, but distinguishes itself by offering an intuitive perspective on automaton dynamics that is independent of network topology\. Although it may not seem to be the most descriptive metric, it effectively serves as a fundamental starting point to understand how much the automaton rule is a determining factor into the generation of different dynamics, being a better indicator of rule suitability for classification than the aforementioned measures\.

In terms of computational efficiency, the reduction of the search space complexity brings feasibility to large\-scale applications\. By analyzing the accuracy of the rules according to their jaggedness at low resolution rule families and discovering where the best rules are, it is possible to extrapolate it to higher resolutions and gradually improve the rule quality, dispensing the need to scan the entire rule space\. The experiments showed an efficiency gain of 10x as the exploration ratio approximates a fixed value \(KE→10%K\_\{\\text\{E\}\}\\to 10\\%\), what could be improved even more by using more sophisticated local search procedures and hybrid metaheuristics\.

Lastly, this work extends the findings about the dependence between the accuracy and the resolution of the rule space to more datasets, reinforcing the applicability of the LLNA as a method to characterize CNs in a wide range of contexts\.

## CRediT authorship contribution statement

Lucas Caldeira de Oliveira:Conceptualization, Methodology, Software, Writing \- Original Draft, Writing \- Review & Editing\.Michiel Rollier:Methodology, Writing \- Review & Editing\.Jan M\. Baetens:Supervision, Writing \- Review & Editing\.Odemir M\. Bruno:Conceptualization, Funding acquisition, Supervision\.

## Declaration of competing interest

The authors declare that we have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper\.

## Acknowledgments

This work has been partially supported by the São Paulo Research Foundation \(FAPESP\) regular grant \#2024/02727\-0 and internship abroad grant \#2024/16345\-1; by the Brazilian Federal Agency for Support and Evaluation of Graduate Education \(CAPES\) grant \#88887\.841805/2023\-00; by the Research Foundation Flanders \(FWO\) grant with project title “An analysis of network automata as models for biological and natural processes” \[3G0G0122\]; by the FWO travel grant with file name V412625N; and by the FWO congress participation grant K105625N\.

## References

- \[1\]\(2016\)Network science\.1 edition,Cambridge University Press\.External Links:ISBN 9781107076266Cited by:[§1](https://arxiv.org/html/2610.10867#S1.p1.1)\.
- \[2\]P\. S\. Dodds, R\. Muhamad, and D\. J\. Watts\(2003\)An experimental study of search in global social networks\.Science301\.External Links:[Document](https://dx.doi.org/10.1126/science.1081058),ISSN 00368075Cited by:[§1](https://arxiv.org/html/2610.10867#S1.p1.1)\.
- \[3\]H\. Jeong, B\. Tombor, R\. Albert, Z\. N\. Oltvai, and A\. Barabási\(2000\)The large\-scale organization of metabolic networks\.Nature407,pp\. 651–654\.External Links:[Document](https://dx.doi.org/10.1038/35036627),ISSN 0028\-0836Cited by:[§1](https://arxiv.org/html/2610.10867#S1.p1.1)\.
- \[4\]L\. F\.S\. Scabini, L\. C\. Ribas, M\. B\. Neiva, A\. G\.B\. Junior, A\. J\.F\. Farfán, and O\. M\. Bruno\(2021\)Social interaction layers in complex networks for the dynamical epidemic modeling of covid\-19 in brazil\.Physica A: Statistical Mechanics and its Applications564,pp\. 125498\.External Links:[Document](https://dx.doi.org/10.1016/J.PHYSA.2020.125498),ISSN 0378\-4371Cited by:[§1](https://arxiv.org/html/2610.10867#S1.p1.1)\.
- \[5\]F\. Errica, M\. Podda, D\. Bacciu, and A\. Micheli\(2019\)A fair comparison of graph neural networks for graph classification\.8th International Conference on Learning Representations, ICLR 2020\.Cited by:[§1](https://arxiv.org/html/2610.10867#S1.p1.1)\.
- \[6\]L\. C\. Oliveira, J\. T\. Oliva, M\. H\. D\. Ribeiro, M\. Teixeira, and D\. Casanova\(2022\)Forecasting the covid\-19 space\-time dynamics in brazil with convolutional graph neural networks and transport modals\.IEEE Access10,pp\. 85064–85079\.External Links:[Document](https://dx.doi.org/10.1109/ACCESS.2022.3195535),ISSN 2169\-3536Cited by:[§1](https://arxiv.org/html/2610.10867#S1.p1.1)\.
- \[7\]L\. Lü and T\. Zhou\(2011\)Link prediction in complex networks: a survey\.Physica A: Statistical Mechanics and its Applications390,pp\. 1150–1170\.External Links:[Document](https://dx.doi.org/10.1016/j.physa.2010.11.027),ISSN 03784371Cited by:[§1](https://arxiv.org/html/2610.10867#S1.p1.1)\.
- \[8\]Y\. Liu, Z\. Li, S\. Pan, C\. Gong, C\. Zhou, and G\. Karypis\(2022\)Anomaly detection on attributed networks via contrastive self\-supervised learning\.IEEE Transactions on Neural Networks and Learning Systems33,pp\. 2378–2392\.External Links:[Document](https://dx.doi.org/10.1109/TNNLS.2021.3068344),ISSN 21622388Cited by:[§1](https://arxiv.org/html/2610.10867#S1.p1.1)\.
- \[9\]L\. d\. F\. Costa, O\. N\. Oliveira, G\. Travieso, F\. A\. Rodrigues, P\. R\. V\. Boas, L\. Antiqueira, M\. P\. Viana, and L\. E\. C\. Rocha\(2011\)Analyzing and modeling real\-world phenomena with complex networks: a survey of applications\.Advances in Physics60,pp\. 329–412\.External Links:[Document](https://dx.doi.org/10.1080/00018732.2011.572452),ISSN 0001\-8732Cited by:[§1](https://arxiv.org/html/2610.10867#S1.p1.1)\.
- \[10\]L\. F\. Costa, F\. A\. Rodrigues, G\. Travieso, and P\. R\. Villas Boas\(2007\)Characterization of complex networks: a survey of measurements\.Advances in Physics56,pp\. 167–242\.External Links:[Document](https://dx.doi.org/10.1080/00018730601170527),ISSN 0001\-8732Cited by:[§1](https://arxiv.org/html/2610.10867#S1.p2.1)\.
- \[11\]G\. H\. B\. Miranda, J\. Machicao, and O\. M\. Bruno\(2016\)Exploring spatio\-temporal dynamics of cellular automata for pattern recognition in networks\.Scientific Reports6\.External Links:[Document](https://dx.doi.org/10.1038/srep37329),ISSN 20452322Cited by:[§1](https://arxiv.org/html/2610.10867#S1.p2.1),[§1](https://arxiv.org/html/2610.10867#S1.p3.1),[§1](https://arxiv.org/html/2610.10867#S1.p4.1),[§2\.1](https://arxiv.org/html/2610.10867#S2.SS1.p2.1),[§2\.3](https://arxiv.org/html/2610.10867#S2.SS3.p1.1),[§2\.3](https://arxiv.org/html/2610.10867#S2.SS3.p3.1),[§2\.3](https://arxiv.org/html/2610.10867#S2.SS3.p6.1),[§2](https://arxiv.org/html/2610.10867#S2.p1.1),[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.14.1),[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.2.1),[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.3.1),[§4](https://arxiv.org/html/2610.10867#S4.p1.1)\.
- \[12\]J\. Machicao, E\. A\. Corrêa, G\. H\.B\. Miranda, D\. R\. Amancio, and O\. M\. Bruno\(2018\)Authorship attribution based on life\-like network automata\.PLoS ONE13\.External Links:[Document](https://dx.doi.org/10.1371/journal.pone.0193703),ISSN 19326203Cited by:[§1](https://arxiv.org/html/2610.10867#S1.p3.1),[§2\.3](https://arxiv.org/html/2610.10867#S2.SS3.p1.1),[§2](https://arxiv.org/html/2610.10867#S2.p1.1)\.
- \[13\]L\. C\. Ribas, J\. Machicao, and O\. M\. Bruno\(2020\)Life\-like network automata descriptor based on binary patterns for network classification\.Information Sciences515\.External Links:[Document](https://dx.doi.org/10.1016/j.ins.2019.09.063),ISSN 00200255Cited by:[§1](https://arxiv.org/html/2610.10867#S1.p3.1),[§1](https://arxiv.org/html/2610.10867#S1.p4.1),[§2\.3](https://arxiv.org/html/2610.10867#S2.SS3.p1.1),[§2\.3](https://arxiv.org/html/2610.10867#S2.SS3.p3.1),[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.10.1),[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.11.1),[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.12.1),[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.13.1),[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.4.1),[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.5.1),[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.6.1),[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.7.1),[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.8.1),[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.9.1),[§4](https://arxiv.org/html/2610.10867#S4.p1.1)\.
- \[14\]K\. M\. C\. Zielinski, L\. C\. Ribas, J\. Machicao, and O\. M\. Bruno\(2022\)A network classification method based on density time evolution patterns extracted from network automata\.arXiv preprint\.Cited by:[Figure 1](https://arxiv.org/html/2610.10867#S1.F1),[§1](https://arxiv.org/html/2610.10867#S1.p3.1),[§1](https://arxiv.org/html/2610.10867#S1.p4.1),[§2\.3](https://arxiv.org/html/2610.10867#S2.SS3.p1.1),[§2\.3](https://arxiv.org/html/2610.10867#S2.SS3.p3.1),[§4](https://arxiv.org/html/2610.10867#S4.p1.1),[§4](https://arxiv.org/html/2610.10867#S4.p2.1)\.
- \[15\]M\. Gardner\(1970\)Mathematical games: the fantastic combinations of john conway’s new solitaire game ”life”\.Scientific American220,pp\. 120–123\.External Links:[Document](https://dx.doi.org/10.1038/scientificamerican1070-120),ISSN 0036\-8733Cited by:[§1](https://arxiv.org/html/2610.10867#S1.p3.1),[§2\.1](https://arxiv.org/html/2610.10867#S2.SS1.p2.1)\.
- \[16\]N\. Shervashidze, P\. Schweitzer, E\. J\. van Leeuwen, K\. Mehlhorn, and K\. M\. Borgwardt\(2011\)Weisfeiler\-lehman graph kernels\.Journal of Machine Learning Research12,pp\. 2539–2561\.External Links:[Document](https://dx.doi.org/10.5555/1953048.2078187),ISSN 1532\-4435Cited by:[§1](https://arxiv.org/html/2610.10867#S1.p3.1)\.
- \[17\]P\. Yanardag and S\. V\.N\. Vishwanathan\(2015\)Deep graph kernels\.Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining2015\-August,pp\. 1365–1374\.External Links:[Document](https://dx.doi.org/10.1145/2783258.2783417),ISBN 9781450336642Cited by:[§1](https://arxiv.org/html/2610.10867#S1.p3.1),[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.15.1),[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.16.1),[§4](https://arxiv.org/html/2610.10867#S4.p1.1)\.
- \[18\]M\. Zhang, Z\. Cui, M\. Neumann, and Y\. Chen\(2018\)An end\-to\-end deep learning architecture for graph classification\.In32nd AAAI Conference on Artificial Intelligence,pp\. 4438–4445\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v32i1.11782),ISSN 2159\-5399Cited by:[§1](https://arxiv.org/html/2610.10867#S1.p3.1)\.
- \[19\]R\. Ying, C\. Morris, W\. L\. Hamilton, J\. You, X\. Ren, and J\. Leskovec\(2018\)Hierarchical graph representation learning with differentiable pooling\.Advances in Neural Information Processing Systems2018\-December,pp\. 4800–4810\.External Links:ISSN 10495258Cited by:[§1](https://arxiv.org/html/2610.10867#S1.p3.1),[§4](https://arxiv.org/html/2610.10867#S4.p1.1)\.
- \[20\]K\. M\. C\. Zielinski, L\. Scabini, L\. C\. Ribas, and O\. M\. Bruno\(2024\)Exploring neighborhood variancy for rule search optimization in life\-like network automata\.In2024 14th International Conference on Pattern Recognition Systems \(ICPRS\),pp\. 1–7\.External Links:[Document](https://dx.doi.org/10.1109/ICPRS62101.2024.10677825),ISBN 979\-8\-3503\-7565\-7Cited by:[§1](https://arxiv.org/html/2610.10867#S1.p4.1),[§2\.1](https://arxiv.org/html/2610.10867#S2.SS1.p7.1),[§2\.2](https://arxiv.org/html/2610.10867#S2.SS2.p1.1),[§3\.2](https://arxiv.org/html/2610.10867#S3.SS2.p1.1),[§4\.1](https://arxiv.org/html/2610.10867#S4.SS1.p1.1),[§4\.1](https://arxiv.org/html/2610.10867#S4.SS1.p2.1),[§4](https://arxiv.org/html/2610.10867#S4.p1.1)\.
- \[21\]M\. Mitchell\(2009\)Complexity a guided tour\.Oxford University PressNew York, NY\.External Links:[Document](https://dx.doi.org/10.1093/oso/9780195124415.001.0001),ISBN 9780195124415Cited by:[§2](https://arxiv.org/html/2610.10867#S2.p1.1)\.
- \[22\]V\. Latora, V\. Nicosia, and G\. Russo\(2017\)Complex networks: principles, methods and applications\.1 edition,Cambridge University Press\.External Links:ISBN 9781107103184Cited by:[§2](https://arxiv.org/html/2610.10867#S2.p1.1)\.
- \[23\]D\. J\. Watts\(1999\)Small worlds: the dynamics of networks between order and randomness\.Princeton University Press\.External Links:ISBN 9780691005416Cited by:[§2\.1](https://arxiv.org/html/2610.10867#S2.SS1.p1.1)\.
- \[24\]C\. Marr and M\. Hütt\(2009\)Outer\-totalistic cellular automata on graphs\.Physics Letters A373,pp\. 546–549\.External Links:[Document](https://dx.doi.org/10.1016/j.physleta.2008.12.013),ISSN 03759601Cited by:[§2\.1](https://arxiv.org/html/2610.10867#S2.SS1.p1.1)\.
- \[25\]C\. Marr and M\. Hütt\(2012\)Cellular automata on graphs: topological properties of er graphs evolved towards low\-entropy dynamics\.Entropy14\.External Links:[Document](https://dx.doi.org/10.3390/e14060993),ISSN 10994300Cited by:[§2\.1](https://arxiv.org/html/2610.10867#S2.SS1.p1.1)\.
- \[26\]J\. M\. Baetens and B\. D\. Baets\(2011\)On the topological sensitivity of cellular automata\.Chaos: An Interdisciplinary Journal of Nonlinear Science21\.External Links:[Document](https://dx.doi.org/10.1063/1.3535581),ISSN 1054\-1500Cited by:[§2\.1](https://arxiv.org/html/2610.10867#S2.SS1.p1.1)\.
- \[27\]J\. M\. Baetens and B\. D\. Baets\(2012\)Cellular automata on irregular tessellations\.Dynamical Systems27,pp\. 411–430\.External Links:[Document](https://dx.doi.org/10.1080/14689367.2012.711300),ISSN 1468\-9367Cited by:[§2\.1](https://arxiv.org/html/2610.10867#S2.SS1.p1.1)\.
- \[28\]M\. Rollier, K\. M\.C\. Zielinski, A\. J\. Daly, O\. M\. Bruno, and J\. M\. Baetens\(2025\)A comprehensive taxonomy of cellular automata\.Communications in Nonlinear Science and Numerical Simulation140,pp\. 108362\.External Links:[Document](https://dx.doi.org/10.1016/j.cnsns.2024.108362),ISSN 10075704Cited by:[§2\.1](https://arxiv.org/html/2610.10867#S2.SS1.p2.1)\.
- \[29\]W\. L\. Hamilton\(2020\)Graph representation learning\.Synthesis Lectures on Artificial Intelligence and Machine Learning14,pp\. 1–159\.External Links:[Document](https://dx.doi.org/10.2200/S01045ED1V01Y202009AIM046),ISSN 1939\-4608Cited by:[§2\.3](https://arxiv.org/html/2610.10867#S2.SS3.p4.1)\.
- \[30\]S\. Wolfram\(1984\)Cellular automata as models of complexity\.Nature311,pp\. 419–424\.External Links:[Document](https://dx.doi.org/10.1038/311419a0),ISSN 0028\-0836Cited by:[§3](https://arxiv.org/html/2610.10867#S3.p2.1)\.
- \[31\]M\. Vispoel, A\. J\. Daly, and J\. M\. Baetens\(2022\)Progress, gaps and obstacles in the classification of cellular automata\.Physica D: Nonlinear Phenomena432,pp\. 133074\.External Links:[Document](https://dx.doi.org/10.1016/J.PHYSD.2021.133074),ISSN 0167\-2789Cited by:[§3](https://arxiv.org/html/2610.10867#S3.p2.1),[§3](https://arxiv.org/html/2610.10867#S3.p6.1)\.
- \[32\]C\. G\. Langton\(1990\)Computation at the edge of chaos: phase transitions and emergent computation\.Physica D: Nonlinear Phenomena42,pp\. 12–37\.External Links:[Document](https://dx.doi.org/10.1016/0167-2789%2890%2990064-V),ISSN 0167\-2789Cited by:[§3](https://arxiv.org/html/2610.10867#S3.p4.1)\.
- \[33\]I\. Shmulevich and S\. A\. Kauffman\(2004\)Activities and sensitivities in boolean network models\.Physical Review Letters93,pp\. 048701\.External Links:[Document](https://dx.doi.org/10.1103/PhysRevLett.93.048701),ISSN 0031\-9007Cited by:[§3](https://arxiv.org/html/2610.10867#S3.p5.1)\.
- \[34\]P\. M\. Binder\(1993\)A phase diagram for elementary cellular automata\.Complex Systems7,pp\. 241–247\.Cited by:[§3](https://arxiv.org/html/2610.10867#S3.p5.1)\.
- \[35\]G\. Y\. Vichniac\(1990\)Boolean derivatives on cellular automata\.Physica D: Nonlinear Phenomena45\.External Links:[Document](https://dx.doi.org/10.1016/0167-2789%2890%2990174-N),ISSN 01672789Cited by:[§3](https://arxiv.org/html/2610.10867#S3.p5.2)\.
- \[36\]M\. Rollier, L\. C\. de Oliveira, O\. M\. Bruno, and J\. M\. Baetens\(2025\)Essential metrics for life on graphs\.Physica D: Nonlinear Phenomena483,pp\. 134950\.External Links:[Document](https://dx.doi.org/10.1016/j.physd.2025.134950),ISSN 01672789Cited by:[§3](https://arxiv.org/html/2610.10867#S3.p5.2),[§3](https://arxiv.org/html/2610.10867#S3.p6.1)\.
- \[37\]S\. Russel and P\. Norvig\(2009\)Artificial intelligence: a modern approach\.3 edition,Pearson\.External Links:ISBN 9780136042594Cited by:[§3\.2](https://arxiv.org/html/2610.10867#S3.SS2.p1.1)\.
- \[38\]F\. Glover and G\.A\. Kochenberger\(2010\)Handbook of metaheuristics\.Vol\.146,Springer US\.External Links:[Document](https://dx.doi.org/10.1007/978-1-4419-1665-5),ISBN 978\-1\-4419\-1663\-1Cited by:[§3\.2](https://arxiv.org/html/2610.10867#S3.SS2.p2.1)\.
- \[39\]R\. Xin, J\. Zhang, and Y\. Shao\(2020\)Complex network classification with convolutional neural network\.Tsinghua Science and Technology25,pp\. 447–457\.External Links:[Document](https://dx.doi.org/10.26599/TST.2019.9010055),ISSN 18787606Cited by:[§4](https://arxiv.org/html/2610.10867#S4.p1.1)\.
- \[40\]C\. Morris, N\. M\. Kriege, F\. Bause, K\. Kersting, P\. Mutzel, and M\. Neumann\(2020\)TUDataset: A collection of benchmark datasets for learning with graphs\.CoRR\.Cited by:[footnote 1](https://arxiv.org/html/2610.10867#footnote1)\.
- \[41\]J\. Leskovec and A\. Krevl\(2014\)SNAP Datasets: Stanford large network dataset collection\.External Links:[Link](http://snap.stanford.edu/data/)Cited by:[footnote 1](https://arxiv.org/html/2610.10867#footnote1)\.
- \[42\]J\. Machicao, K\. Zielinski, L\. C\. Ribas, and O\. M\. Bruno\(2023\)Synthetic networks for classification methods\.External Links:[Document](https://dx.doi.org/https%3A//doi.org/10.5281/zenodo.7749500),[Link](https://zenodo.org/records/7749500)Cited by:[footnote 1](https://arxiv.org/html/2610.10867#footnote1)\.
- \[43\]J\. Machicao, K\. Zielinski, L\. C\. Ribas, and O\. M\. Bruno\(2023\)Real world networks for network classification method evaluation\.External Links:[Document](https://dx.doi.org/https%3A//doi.org/10.5281/zenodo.7749514),[Link](https://zenodo.org/records/7749514)Cited by:[footnote 1](https://arxiv.org/html/2610.10867#footnote1)\.
- \[44\]B\. Rozemberczki, O\. Kiss, and R\. Sarkar\(2020\)Karate club\.InProceedings of the 29th ACM International Conference on Information & Knowledge Management,pp\. 3125–3132\.External Links:[Document](https://dx.doi.org/10.1145/3340531.3412757),ISBN 9781450368599Cited by:[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.17.1),[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.18.1),[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.19.1)\.
- \[45\]P\. D\. Dobson and A\. J\. Doig\(2003\)Distinguishing enzyme structures from non\-enzymes without alignments\.Journal of Molecular Biology330,pp\. 771–783\.External Links:[Document](https://dx.doi.org/10.1016/S0022-2836%2803%2900628-4),ISSN 0022\-2836Cited by:[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.20.1)\.
- \[46\]A\. K\. Debnath, G\. Debnath, C\. Hansch, R\. L\. de Compadre, and A\. J\. Shusterman\(1991\)Structure\-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds\. correlation with molecular orbital energies and hydrophobicity\.Journal of Medicinal Chemistry34,pp\. 786–797\.External Links:[Document](https://dx.doi.org/10.1021/JM00106A046/ASSET/JM00106A046.FP.PNG%5FV03),ISSN 15204804Cited by:[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.21.1)\.
- \[47\]N\. Wale, I\. A\. Watson, and G\. Karypis\(2008\)Comparison of descriptor spaces for chemical compound retrieval and classification\.Knowledge and Information Systems14,pp\. 347–375\.External Links:[Document](https://dx.doi.org/10.1007/S10115-007-0103-5/METRICS),ISSN 02193116Cited by:[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.22.1),[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.23.1)\.
- \[48\]K\. M\. Borgwardt, C\. S\. Ong, S\. Schönauer, S\. V\.N\. Vishwanathan, A\. J\. Smola, and H\. P\. Kriegel\(2005\)Protein function prediction via graph kernels\.Bioinformatics21,pp\. i47–i56\.External Links:[Document](https://dx.doi.org/10.1093/BIOINFORMATICS/BTI1007),ISSN 1367\-4803Cited by:[Table 1](https://arxiv.org/html/2610.10867#S4.T1.2.24.1)\.