CS Paper Radar

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

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

cs.LG nlin.CG ·submitted 2026-10-07 20:12 UTC · v1
unusual

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Spectral Braids: A Topological Descriptor for Dynamic Directed Networks

cs.SI cs.LG ·2026-10-27 ·Mehmet Emin Aktas, Esra Akbas
published similarity 0.57
Abstract · 15 pages, 5 figures, 2 tables. Accepted at the 2026 IEEE International Conference on Big Data (IEEE BigData 2026)

Eigenvalues are a workhorse of graph machine learning: spectral clustering, spectral graph neural networks, and graph kernels all summarize a network by the eigenvalues of a matrix. These eigenvalues are almost always treated as a static list of numbers. When a graph changes, however, its eigenvalues move, and when the matrix is not symmetric, they move in the complex plane, where they can wind around each other. The pattern of this winding is a braid, a classical object from topology. We propose spectral braids, a methodology for dynamic directed networks: each snapshot is aggregated into a community-level transition matrix, its complex eigenvalues are tracked over time, and the braid they trace is read off as a word. The word is then mapped to a matrix by the Burau representation, which gives a fixed-size feature vector for any classifier. The braid has a concrete meaning: each eigenvalue describes how a group of communities behaves, and each crossing records one group overtaking another. We evaluate the method on dynamic network classification, using synthetic networks of online communities whose labels describe how the network evolved between the same starting and ending states. Our experimental results show that the proposed features reach 97.1% accuracy on four classes, against 44.5% for the best feature set that does not track eigenvalues, and that the Burau features also separate networks containing the same events in a different order, which simple counts of crossings cannot do. To the best of our knowledge, this is the first study that defines braids and braid monodromy on graph data and uses them as features for learning on dynamic networks.

0.36

The Tangled Web They Weave: Exploring Neural Representations with Directed Simplicial Complexes

cs.LG ·2026-10-31 ·Michael Bleher
published similarity 0.55
Abstract · 52 pages, 16 figures. Accepted at NeurReps 2026 (Symmetry and Geometry in Neural Representations)

Understanding how artificial neural networks (ANNs) represent and combine features internally is a central challenge in mechanistic interpretability. Existing neural circuit-discovery methods represent neuron interactions as pairwise edges in a graph. But distributed neural representations consist of large groups of neurons that are inherently linked by higher-order causal dependencies: suppressing a subgroup of neurons in concert may shift the activation of other neurons in the feature representation. We propose a method to construct filtered directed simplicial complexes (DSCs) that give a topological representation of such dependencies, built from the activation profiles of an ANN on a given set of inputs. Our approach treats ANNs as structural causal models and uses counterfactual ablations to test for causal links between groups of internal neurons within specific input contexts. As a proof of concept, we apply the approach to a pair of small multilayer perceptron (MLP) architectures in a synthetic two-dimensional quadrant classification task. In these examples, DSCs recover the designed feature pathways and coordinated class transitions, and the complexes of trained networks are higher-dimensional than those of their handcrafted references. As validation, we compare our method with graph-based circuit-discovery baselines and find that their 1-skeletons agree within the relations that a weight graph can represent. These results support DSCs as context-dependent descriptions of multi-neuron computation and may thus provide a novel, orthogonal framework to study the phenomenon of distributed feature representations and polysemanticity.

0.33

ConwayNet: Interpretability, Activation Coherence, and Noise Resilience via a Game-of-Life-Inspired Lateral Inhibition in Artificial Neural Networks

cs.LG ·2026-11-07 ·Yair Cohen, Scott M. Gilmore
similarity 0.54
Abstract

Deep neural networks achieve universal function approximation by stacking interconnected nonlinearities, but as a consequence they are sensitive to noise and resist mechanistic interpretation. In contrast, the local update rules of cellular automata, such as Conway's Game of Life, give rise to not merely interpretable but programmable dynamics. We explore a bridge between these worlds: a lateral inhibition in neural networks based on continuous Game-of-Life rules that derives inhibitory and excitatory responses from the layer input and blends them into the activation map in a state-conditioned way. The mechanism is differentiable and architecture-agnostic, and its regulation is imposed rather than learned: the rule's parameters are fixed and are not optimised, while the rule's values and derivatives shape training throughout the network. Wired into fully connected, convolutional, wide-residual and graph convolutional networks, it gives rise to several properties. Activation maps become coherent across space, depth and seeds, with coarse structure persisting through depth while fine detail is renewed at every layer. The co-activation graph of the hidden units departs from an Erdős--Rényi random graph: it is laid out on the image and its giant component grows in steps, as in a spatial graph. Networks started from nearly identical initialisations, under label noise, disagree on thirty times fewer test images. Saliency maps rest on the object rather than the background, and resilience to pixel noise not seen in training is substantially improved.

0.21

Motifs in temporal hypergraphs

cs.SI cs.DSphysics.soc-ph ·2026-09-10 ·Quintino Francesco Lotito, Lorenzo Betti, Federico Battiston, Giuseppe Francesco Italiano
similarity 0.53
Abstract

Network motifs, recurrent local patterns of interactions in graphs, provide fundamental insights on the interplay between structure and functionality in complex systems. Many real-world systems are not well represented by traditional static pairwise networks, as interactions may involve groups of nodes, occur over time, or encode directionality. In this paper, we introduce temporal motifs for hypergraphs and directed hypergraphs, extending motif analysis to timestamped many-body interactions. We formalize the corresponding mining problem, study the combinatorial structure of these motifs, and develop exact algorithms for their enumeration. In particular, we propose a dynamic programming algorithm that substantially reduces the computational cost of motif mining, achieving orders of magnitude speedups on empirical datasets. We also introduce a null model for temporal hypergraphs to assess the statistical over- and under-expression of motifs. Applying the proposed framework to real-world datasets from different domains, including face-to-face contacts, scientific collaborations, e-mail exchanges, and Bitcoin transactions, we show that temporal hypergraph motifs reveal distinct forms of local organization across systems. Finally, we demonstrate their use as an exploratory tool through focused case studies on persistent patterns in scientific collaborations and e-mail communications.

0.22

AutoHGNN: Robust and Efficient Neural Architecture Search for Hypergraph Neural Networks

cs.LG cs.AI ·2026-09-27 ·Sirui Li, Pietro Liò b, Xinsheng Li, Baisong Liu, Chengbin Peng
publishedbenchmark similarity 0.53
Abstract

Hypergraph neural networks have achieved significant success in recent years. However, manual architecture crafting is labor-intensive and often fails to capture complex, higher-order relations, making the automation of hypergraph neural network structure design crucial. To improve the automation and adaptability of hypergraph learning, this paper proposes AutoHGNN, a neural architecture search framework tailored for hypergraph neural networks. First, we introduce a Hyper-Interaction Module (HIM) into the search space to address the mismatch between conventional graph neural network designs and hypergraph data. Second, we propose Hypergraph Stable Topological Distance (HyperSTD) as a structural selection criterion to identify architectures that best preserve the intrinsic structural affinities of the original hypergraph during differentiable search. Extensive experiments on various benchmark datasets demonstrate that AutoHGNN consistently outperforms manually designed and automatically searched baselines in classification accuracy and time efficiency, proving that the discovered architectures are significantly more effective.

0.40

Emergence in Network Systems is Bounded by Boundary-Crossing Paths

cs.SI physics.soc-phnlin.AO ·2026-09-29 ·Johnny Jingze Li, Gabriel A. Silva
similarity 0.53
Abstract

Emergence, features of a whole that no part shows alone, is central to complex systems but rarely measured so as to locate its source. Viewing a system structurally, as a network of interacting parts, we evaluate emergence as what observing the coupled whole reveals beyond, or erases from, the combined observations of the parts. For observations that build what they see route by route, we show that every emergent feature is produced by its own route across the interface between parts, a route that traces it to the components and interactions responsible. We show the number of all such boundary-crossing paths bounds the total emergence discrepancy, and equals the emergence of measures that count routes. The bound is computed locally around the interface, validated through network examples, and in a nervous system the routes show that interneurons relay most of the emergence. Our work associates emergence with path structure in the network system that can be anticipated, attributed, and engineered.

0.33

Similarity-Guided Optimization Strategies for Approximate Network Symmetry Detection

cs.NE cs.LGq-bio.NC ·2026-11-12 ·David Hartman, Jaroslav Hlinka, Dominik Klepl, Anna Pidnebesna, Petra Vidnerová
similarity 0.53
Abstract · 90 pages, 15 figures and 2 tables in the main text; supplementary material with 64 figures and 7 tables included

Symmetry in complex networks is a structural property with broad implications for network function, dynamics, and robustness. While classical approaches rely on exact automorphisms and thus remain highly sensitive to small perturbations, recent work of Liu has introduced approximate formulations that relax the strict invariance condition and recast symmetry detection as an optimization problem over permutations. We investigate how node-level similarity information can be used to bias the search toward structurally plausible vertex correspondences, with network centralities serving as one interpretable instance. Building on this perspective, we adapt simulated annealing, genetic algorithms, tabu search, particle swarm optimization, differential evolution and the quadratic symmetry approximator to this problem, add similarity guidance to each, and introduce Bilinear Approximate Symmetry Inference (BASIN), which learns a soft assignment matrix via bilinear embeddings. Using a unified evaluation pipeline, we compare their guided and unguided variants, BASIN and a random baseline on four synthetic graph families, structural brain connectomes, and three empirical networks with known automorphism groups. Node-similarity guidance is decisive where a planted orbit exists that the unguided search misses, and algorithm-dependent elsewhere, on synthetic and empirical networks alike. Overall, tabu search achieves the strongest performance; its guided variant (SGTS) has the lowest median score among the guided variants in all 44 synthetic conditions, while BASIN is the better of the continuous relaxations on rewired lateral graphs. The effect of node-similarity guidance is therefore regime-dependent rather than uniformly positive.

0.37

A Topological Encoder Decoder Framework for Temporal Graph Learning

cs.AI cs.LG ·2026-11-07 ·Ronan Buck, Kiarash Shamsi, Tran Gia Bao Ngo, Astrit Tola, Baris Coskunuzer +1 more
similarity 0.53
Abstract

Most temporal graph learning methods reduce future prediction to discriminative inference over past interactions, focusing on edges or node labels for a largely persistent set of nodes. This view breaks down when new nodes and edges appear, since the future graph becomes a new object with changing size, composition, and structure. We address this gap by framing temporal graph prediction as an inverse topology problem. Instead of predicting edges directly, we first predict a multiscale topological descriptor of the future graph and then reconstruct a plausible future snapshot that realizes this descriptor under inductive constraints. This approach makes global structure and node churn explicit prediction targets and produces forecasted graphs that downstream tasks can evaluate without retraining. Across 14 temporal graph datasets, we evaluate our method, TOPOGED, on node, link, and graph property prediction and compare it against state-of-the-art temporal graph models. TOPOGED significantly improves node-level forecasting accuracy over the strongest baseline, with a macro average of 0.49 versus 0.05. It also outperforms baselines in 60% of graph-structure metric evaluations and substantially increases macro-average edge prediction metrics, from near-zero to 0.12. Our results show that topology-guided graph forecasting can predict inductive future snapshots whose structure supports multiple downstream evaluations.

0.15