Graph neural cellular automata cluster large datasets efficiently
G-NAC: Graph Neural Automata Clustering via Emergent Domain Formation
Machine Learning
Summary
Clustering means grouping similar items together, like sorting a messy box of mixed toys. The authors created a new way for items to interact on a network, following simple shared rules like cells communicating with neighbors, to form these groups by themselves. This method, called Graph Neural Automata Clustering (G-NAC), works well on many different datasets and can handle very large groups without needing a lot more time or memory. The rules that G-NAC learns from smaller groups also work on much bigger ones, as long as they are similar. This shows a new way to use local interactions on graphs to find patterns.
What this means in practice
- •For data engineers: Cluster very large graph-structured datasets efficiently using local interaction rules derived from smaller graphs.
- •For network analysts: Detect communities or domains in networks by simulating cellular automata rules on graph nodes to improve structure discovery.
Authors
Keith Miller, Tristan Crawford
Abstract
We introduce Graph Neural Automata Clustering (G-NAC), an unsupervised clustering method in which observations interact as cells on a fixed neighborhood graph. A shared recurrent graph-neural cellular rule evolves latent domain states through local interactions, which are converted into a rank-based spectral affinity for partitioning. Across 73 clustering tasks from 57 benchmark datasets, G-NAC achieved a mean adjusted Rand index (ARI) of 0.7951, comparable to Genie at 0.7941 and higher than the other evaluated baselines. Empirical training time and GPU memory scaled approximately linearly from 5,000 to 100,000 nodes. Learned transition rules also transferred from smaller source graphs to independent 100,000-node samples generated under matched conditions. These results demonstrate a recurrent graph-clustering formulation while identifying dependencies on graph quality, readout design, and source-target similarity.