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

arXiv:2610.10867 · cs.LG, nlin.CG · Submitted 2026-10-07 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "Shape irregularity of Life-Like Network Automaton rules as an indicator of classification performance".

Tom: The gist The jaggedness is a quantitative parameter based on the visual notion of rule’s shape irregularity,

Jane: First, who's behind it and why it matters.

Title and authors: Tom: So, to get into specifics on this paper, the title is "Shape irregularity of Life-Like Network Automaton rules as an indicator of classification performance," and it’s written by Lucas C. S. Oliveira, Michiel Rollier BionamiX, Jan Baetens BionamiX, and Odemir M. Bruno AICS.

Jane: And what they are doing is taking the LLNA framework—which uses network topology to drive dynamics—and adding this new metric of shape irregularity to see if it helps us pick the right rule for classification tasks.

Lu: It’s interesting because, as they point out on page one traditional methods for network classification often struggle because they need structural characterizations that are both scale-invariant and computationally efficient, and LLNA offers a way to extract temporal patterns without needing pre-defined features.

Meng: But the bottleneck is exactly what the abstract says: selecting the automaton transition rule. If you have many possible rules, trying every single one through exhaustive search is just not feasible for big networks.

Tom: Right, so this paper tackles that combinatorial optimization problem by suggesting that instead of searching everything, we can use jaggedness to guide our search process.

Jane: They define jaggedness formally as J(phi) = X s in S alpha X minus two k equals zero phi s, k alpha XOR phi s, k plus one alpha equals x minus two k equals zero (x k XOR x k plus one) + x minus two k equals zero (y K XOR y K plus one) <ref:2610.10867#pg1>.

Lu: That formula is pretty dense, but it's essentially counting the abrupt changes in the rule diagram within that unit interval. They then normalize it as J-bar equal to J squared over alpha minus one.

Tom: And they found that for a given resolution alpha, there are alpha minus one possible discontinuities for each criterion, and they calculated that the number of rules with the same jaggedness can be up to two to two times alpha minus one n <ref:2610.10867#pg3>.

Jane: That’s a lot of possibilities just based on the rule shape alone, so this metric is clearly trying to cut down the search space for finding good classification rules.

The paper's summary: Tom: Now, let's get into what they actually found in terms of their methodology and results with this paper on "Shape irregularity of Life-Like Network Automaton rules as an indicator of classification performance."

Jane: They set up a structured pipeline involving the network automaton, a feature extractor to map variable-size temporal data into fixed-length vectors, and finally, a tabular classifier that maps that vector to the network class.

Lu: The automaton part generates state-time matrices called time evolution patterns or TEPs. These patterns depend on the number of time steps T and the number of nodes N. The extractor then uses histogram-based aggregations to turn those variable-size temporal data into something fixed length for the classifier.

Meng: So, they are taking these complex, time-dependent network patterns and compressing them into a feature vector so a standard machine learning classifier can actually use them.

Tom: And the key contribution here is linking that rule's shape irregularity directly to classification performance. They tested this connection across twenty-three different datasets <ref:2610.10867#pg3>.

Jane: The results show varying patterns in median accuracy depending on the dataset, but they found that for thirteen out of those twenty-three datasets, there was a correlation between the accuracy achieved and the normalized jaggedness value of the rule used <ref:2610.10867#pg3>.

Lu: Specifically, they observed that the best rules often appear at high J-bar values. This suggests that rules with more discontinuities—rules that are more irregular—are generally better at being sensitive to changes in node state density within their neighborhood.

Tom: So, in plain terms, the paper is showing us that if you can measure how jagged a rule is, you get a hint about how effective that rule will be at sorting out different types of networks.

The paper's improvements: Jane: So what are the actual suggested improvements or the new strategies they propose to use this jaggedness metric? Because it’s not just saying "jaggedness matters," they have a path forward.

Tom: They move past the idea of exhaustive search by introducing a heuristic search strategy that uses jaggedness to guide rule selection. This strategy is inspired by perturbation procedure from the Iterated Local Search or ILS metaheuristic.

Lu: The neighborhood scheme for this search is partitioned based on both resolution alpha and jaggedness, which allows them to navigate the rule space more intelligently than just searching randomly.

Meng: They suggest applying a neighborhood navigation strategy that uses perturbation procedure, and they found that achieving expected behavior often involves including seven to m plus or minus one in the exact operation.

Tom: And they also have an efficiency constraint: for this method to be efficient, the cost needs to be less than one. This happens whenever the constant c alpha is smaller than three over four times phi alpha, which keeps things manageable computationally.

Jane: The authors are basically saying that instead of brute force, you use this jaggedness information within a guided search structure to find high-performing rules much faster.

Conclusion: Tom: So to wrap up on the "Shape irregularity of Life-Like Network Automaton rules as an indicator of classification performance," what’s the final word on what this paper actually means for network science?

Jane: It establishes jaggedness as a quantitative parameter based on the visual look of a rule's shape irregularity, and it gives us a fundamental starting point to understand how much the automaton rule itself determines the resulting dynamics.

Lu: It effectively serves as a way to quantify how much the automaton rule acts as a determining factor in generating different types of network behaviors for classification purposes.

Meng: Practically speaking, this means if you’re trying to classify something—say, metabolic networks or chemical compounds—you can look at their underlying rules and try to estimate that jaggedness to predict how accurate your final classification will be without running a massive search.

Tom: Right. It’s about moving from just looking at the structure of the network itself to looking at the structure of the logic governing its evolution, which is where this paper points us next.

Jane: Exactly. We’re going to see how this idea fits with other things we've been discussing, so stick around for our next paper discussion.

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

Institute of Mathematics and Computer Science, University of Sao Paulo · BionamiX, Department of Data Analysis and Mathematical Modelling, Ghent University

cs.LG, nlin.CG

Submitted: 2026-10-07

Updated: 2026-10-07

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 74/100

The gist: The gist 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

Key concepts

Life-Like Network Automaton (LLNA): The LLNA is a system inspired by Conway’s Game of Life, adapted to model complex networks. It uses the network topology as the environment where nodes evolve based on local neighborhood rules, generating dynamic patterns for analysis.
Jaggedness: Jaggedness is a quantitative measure of how irregular an LLNA rule's diagram is within a specific resolution. It counts the number of discontinuities in the rule's shape, providing a numerical way to assess the complexity or irregularity of the transition logic.
Network Classification Pipeline: This is a three-step process used to classify networks. It involves an LLNA generating time evolution patterns (TEPs), extracting features from these variable-size patterns into fixed vectors, and finally using a classifier to assign a network class.
Resolution ($\alpha$): Resolution refers to the level of detail used when defining the LLNA rule. It directly relates to the 'neighborhood size' of the transition rule, determining how finely the network structure is partitioned for state updates.

Summary

The gist 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.

Background

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. 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] chains [3], epidemics [4], etc. – and in diverse applications – network classification [5], spatiotemporal forecasting [6], link prediction [7], identification of vulnerabilities and anomalies [8], and others [9]. 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]. A method that has been successfully applied in this context is the Life-Like Network Automaton (LLNA) [11, 2] Taking inspiration from Conway’s Game of Life [15], it relies on network topology as source of dynamical information, differing from other approaches that use only structural information [16, 2] and/or depend on detailed feature vectors provided beforehand [18, 19]. 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.

LLNA Formalism

A network automaton (NA) is a formalism that adapts the transition logic of a CA to the non-regular topology of networks. 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. The LLNA is a Boolean outer-totalistic NA defined by the quadruple G, S, s0, φα where the transition rule φ operates on a uniform partition with cardinality α of the unit interval. A born criterion is satisfied if s t i = 0 and the fraction of living nodes in the neighborhood of vi, given by ρ t i = 1/d i di P vj∈Ni s t j, falls in some interval covered by the set BX = S k∈X Hαk, where di = Ni is the degree of the node i. Analogously, a survive criterion is satisfied when s t i = 1 and ρ t i ∈ SY, with SY = S k∈Y Hαk. The state update rule is defined by s t+1 i = φ(s t i, ρt i) = 1 if s t i = 0 and ρt i ∈ BX; 1 if s t+1 i = 1 and ρt+1 in SY; 0 otherwise. The parameter α is directly related to the term “neighborhood size” (of the LLNA transition rule) stated by Zielinski [20] as α − 1.

Rule Numbering and Classification Pipeline

A LLNA rule is described by the sets of indices X, Y ⊆ S α−1 and the resolution α. The most direct way to represent a LLNA rule is by visualizing X, Y as subscripts and the resolution highlighted, like Rα:BXSY. A key challenge in this framework is hyper-parameter optimization. The general LLNA-based classification model follows a structured pipeline composed by three modules: network automaton, feature extractor, and tabular classifier. The automaton generates the state-time matrix S = s0... sT ∈ SN×(T +1), also called time evolution patterns (TEPs), whose shape depends on the number of time steps T and the number of nodes N. The extractor maps the variable-size temporal data into a fixed-length feature vector by applying a set of feature extraction functions followed by histogram-based aggregations. Finally, the classifier performs the network classification, mapping the feature vector Ψ to the network class z.

Jaggedness as a Discriminative Metric

The paper introduces a novel genotype parameter called jaggedness, which considers only the shape of the transition rule. Jaggedness can be formally defined as the number of discontinuities in rule diagram within]0, 1[. The formula for jaggedness is J(φα) = X s∈S αX−2 k=0 φ s,kα XOR φ s,k + 1α = αX−2 k=0 (xk XOR xk+1) + αX−2 k=0 (yk XOR yk+1). This can be further normalized as J¯(φα) = J(φα) squared / (α − 1). For a given resolution α, there are α − 1 possible discontinuities for each transition criterion (born and survive) and each of them can be organized in α−1n ways. The number of rule with same jaggedness is Φα = P n Φα = 2 2(α − 1)n.

Heuristic Optimization Strategy

To overcome the computational bottleneck of exhaustive search, a heuristic search strategy is introduced that uses jaggedness to guide the rule selection. The proposed navigation strategy is inspired by perturbation procedure from the Iterated Local Search (ILS) metaheuristic. This strategy involves a neighborhood scheme partitioned by α and J as the neighborhood schema, and applying a neighborhood navigation strategy inspired by perturbation procedure. The expected behavior can be achieved by including n 7→ m ± 1 in the exact operation. The efficiency constraint requires KE ≪ 1, which is obtained whenever cα << (3/4)Φα.

Experimental Results

The experiments evaluated the connection between rule jaggedness, classification performance and rule space resolution. The median accuracy exhibits varying patterns across datasets. In total, 13 out of the 23 considered datasets show some degree of correlation between accuracy and normalized jaggedness. The best rules appear in general at high J¯, which are more sensitive to state density changes in the neighborhood.

Conclusion

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

Improvements for AI systems

The AI system can perform network classification by leveraging LLNA rules guided by jaggedness, which is defined as the number of discontinuities in rule diagram within ]0, 1[. This allows the system to select transition rules that are a theoretical proxy for chaoticity and sensitivity essential for generating discriminative dynamic behaviors among network categories.
The system can optimize the selection of LLNA transition rules using a heuristic search strategy that uses jaggedness to guide rule selection, achieving classification accuracies within 5% of the global optimum while reducing computational overhead by 90% compared to exhaustive approach.
The AI system can navigate the rule space efficiently by employing a neighborhood navigation strategy inspired by perturbation procedure from the Iterated Local Search (ILS) metaheuristic, utilizing partitions based on resolution alpha and jaggedness to find high-performing rules with a computational efficiency gain of up to 10x.
The system can generate network descriptors through density/state-density TEPs, which combines the node state evolution with the corresponding density matrix, enabling characterization tasks such as determining the taxonomic groups of metabolic networks or classifying chemical compounds.

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.