G-NAC: Graph Neural Automata Clustering via Emergent Domain Formation
arXiv:2609.24823v1 [cs.LG] 21 Sep 2026
Keith Miller, Tristan Crawford September 2026 Abstract We introduce Graph Neural Automata Clustering (G-NAC), an unsupervised method for partitioning numerical feature vectors without clusterlabel supervision. Each observation is represented as a cell on a fixed neighborhood graph, and a shared recurrent graph-neural cellular rule evolves hidden and domain states through local interactions. The final output is one cluster assignment per observation; reference partitions are withheld from model fitting and used only for external evaluation. GNAC combines graph smoothness with variance, covariance, dispersion, and temporal regularization, then converts the evolved relational state into a rank-based sparse spectral affinity for partitioning. We evaluate the complete pipeline on 73 dataset/K tasks from 57 datasets in the four established clustering benchmark batteries. G-NAC achieved mean ARI 0.7951, comparable in observed mean to Genie (0.7941) and higher than the other evaluated baselines. Controlled corruption experiments showed little aggregate degradation when up to half of each node’s directed neighbor slots were deleted and retraining was performed, but progressive degradation under edge rewiring and measurement noise. For fixed graph degree and model configuration, empirical fit time and peak allocated GPU memory scaled approximately as N 1.02 and N 0.99 , respectively, over 5,000–100,000 nodes. Finally, frozen transition rules trained on smaller source graphs transferred to independent 100,000-node samples from the same generating process; on the harder noisy-blobs family, training on 5,000 source observations reduced target ARI by less than 0.009 relative to 100,000-node source training. These results support G-NAC as a recurrent graph-clustering formulation while identifying dependencies on graph quality, readout design, and matched source–target structure.
1
Introduction
Clustering seeks to recover meaningful structure from unlabeled observations, where each observation is represented by a numerical feature vector xi ∈ Rd . Classical approaches include k-means (MacQueen, 1967), Gaussian mixture modeling commonly fit by expectation–maximization (Dempster et al., 1977),
1
hierarchical methods such as Ward clustering (Ward, 1963), and graph-based spectral clustering (von Luxburg, 2007). Modern deep clustering methods instead learn representations intended to facilitate partitioning. Despite substantial differences in implementation, these approaches generally seek either a partition of the observations or a representation from which such a partition can be obtained. In the unsupervised setting considered here, the objective is to assign the observations to K groups without using reference cluster labels during model fitting. Where benchmark reference partitions are available, they are used only after clustering to quantify agreement with the recovered partition rather than as targets for training. An alternative is to treat clustering as an emergent dynamical process in which repeated local interactions between observations reorganize an initially ambiguous system into coherent domains. This perspective has a long history in cellular automata and self-organizing systems, including cellular-automata and cellular-learning-automata approaches to clustering and community detection (Shuai et al., 2007; de Lope and Maravall, 2013; Dündar and Korkmaz, 2018; Esnaashari and Meybodi, 2007; Zhao et al., 2015). These methods, however, generally employ prescribed stochastic or learning-automata rules rather than a differentiable graph-neural cellular transition rule learned directly from the unlabeled observations. Graph Neural Cellular Automata (GNCA) provide a natural framework for learning such dynamics (Grattarola et al., 2021). A GNCA associates states with graph nodes and repeatedly applies a shared neural transition function through local graph interactions. This raises a different possibility for unsupervised learning: rather than training a neural network to predict clusters, can a learned cellular system organize observations into clusters through its recurrent dynamics? We investigate this question through Graph Neural Automata Clustering (GNAC). A fixed neighborhood graph specifies which observations may interact, while a shared learned transition rule recurrently evolves hidden and domain states at every node. Training balances local graph coherence with variance, covariance, and dispersion regularizers that penalize representational collapse. Rather than directly predicting cluster labels, G-NAC learns a common rule of local evolution through which coherent latent domains can emerge. To the best of our knowledge, we have not identified prior work that trains a GNCA transition rule itself as a general-purpose unsupervised data-clustering mechanism. This novelty claim is intentionally narrow: cellular automata have previously been used for clustering, and graph neural networks have extensively been used for graph clustering. Useful G-NAC organization need not correspond to coordinate convergence toward a fixed state. Instead, the relative ordering of domain-space distances along graph edges can exhibit high agreement across successive recurrent checkpoints while the coordinates themselves continue to change. G-NAC therefore uses successive edge-distance rank agreement as an empirical stopping criterion and constructs its final sparse spectral affinity from global ordinal ranks of 2
Conventional clustering features X
−→
direct clustering model
−→
assignments C
−→
recurrent rule FθT
G-NAC features X
−→
fixed graph G
∗
↓ assignments C
←−
(Z)
rank affinity A
←−
Figure 1: Conceptual comparison of direct clustering and G-NAC. G-NAC inserts a learned recurrent graph-neural cellular process between the observed feature vectors and the final partition. Reference labels are not inputs to the recurrent model. domain-space edge distances. The rank criterion measures relational stability rather than certifying fixed-point convergence. Figure 1 summarizes the distinction between a conventional direct clustering pipeline and G-NAC. The complete state updates, objective, stopping rule, and readout equations are given in Section 3. We evaluate G-NAC on 73 dataset/K tasks drawn from 57 externally curated clustering datasets against classical, spectral, self-organizing, and deep clustering baselines. We further examine stochastic stability, measurement and graph corruption, computational scaling, and transfer of learned cellular rules from smaller source graphs to independent 100,000-node target graphs. Section 4 provides the benchmark composition and clarifies the experimental task and evaluation protocol. The principal contributions of this work are: • We introduce G-NAC, an unsupervised clustering framework in which a shared graph-neural cellular transition rule organizes observations into latent domains through recurrent local interaction. • We formulate an unsupervised domain-formation objective that combines local graph coherence with variance, covariance, and dispersion regularization to encourage coherent, noncollapsed representations without clusterlabel supervision. • We introduce a relational inference procedure based on graph-edge distancerank stability and a global edge-rank affinity. At fixed graph support and tie convention, the resulting affinity is invariant to strictly increasing transformations of the learned edge distances. • We evaluate G-NAC against ten classical, spectral, self-organizing, and deep clustering baselines and characterize its stochastic stability, response to measurement and graph corruption, and empirical computational scaling. 3
∗
evolved domain state Z (T )
• We demonstrate transfer of learned cellular rules across graph scale and independent graph realizations under matched generating conditions, including deployment of rules trained on smaller source graphs to independent 100,000-node targets without retraining. These results establish learned domain formation as an alternative formulation of clustering in which a shared local dynamical rule reorganizes a relational system before partitioning.
2
Related Work
G-NAC lies at the intersection of several established research directions: cellularautomata-based clustering, graph neural cellular automata, deep representation learning for clustering, and graph-structured clustering. These areas provide important precedents for individual components of the proposed method, but differ from G-NAC in the role assigned to the recurrent cellular dynamics.
2.1
Cellular Automata for Data Clustering
Cellular automata have been used for unsupervised clustering well before the development of modern neural cellular automata. Early approaches treated observations as cells whose local interactions reorganize the data into groups. Generalized cellular automata formulated clustering as a stochastic self-organizing process (Shuai et al., 2007), while de Lope and Maravall (2013) proposed a linear cellular-automata clustering algorithm in which observations are reorganized through local dynamics. Stochastic cellular automata have likewise been applied directly to data clustering (Dündar and Korkmaz, 2018). These methods demonstrate that local cellular interactions can produce unsupervised partitions, but use algorithmically prescribed rather than learned neural transition rules. Related work in cellular learning automata (CLA) extends cellular organization to irregular graph structures. Esnaashari and Meybodi (2007) introduced irregular cellular learning automata (ICLA), allowing cells to interact over arbitrary graph topologies, and applied the framework to clustering in sensor networks. Building on ICLA, Zhao et al. (2015) proposed CLA-net for community detection, in which graph nodes contain learning automata whose collective evolution reveals community structure. These approaches are structurally related to G-NAC but employ a different learning mechanism. Cellular learning automata update action-probability distributions according to learning-automata rules, whereas G-NAC shares a differentiable neural transition function across cells and trains it through recurrent gradient-based optimization. Moreover, CLA-based community-detection methods primarily seek structure represented by the input graph, while G-NAC uses a neighborhood graph as the interaction substrate over which learned latent domain states evolve.
4
2.2
Graph Neural Cellular Automata
Neural cellular automata replace hand-designed transition rules with learned neural functions, and Graph Neural Cellular Automata (GNCA) generalize this formulation from regular lattices to arbitrary graph topologies. Grattarola et al. (2021) introduced a framework in which a graph neural network parameterizes a shared cellular transition rule, demonstrating that repeated local graph interactions can produce coordinated global dynamics across tasks including pattern formation and dynamical-system simulation. This formulation provides the principal architectural foundation for G-NAC. Both approaches associate recurrent states with graph vertices, reuse a shared neural transition function over time, and obtain global organization through repeated local message passing. They differ primarily in objective and interpretation: the original GNCA framework learns dynamics for specified tasks or target configurations, whereas G-NAC uses an unsupervised domain-formation objective and interprets the resulting relational organization as cluster structure. Subsequent work has extended GNCA to learned graph topology (Dwyer and Omwenga, 2023), E(n)-equivariant pattern formation and dynamical modeling (Gala et al., 2024), and physics-informed dynamical systems (Navarin et al., 2024). These extensions broaden the GNCA framework but do not formulate the learned cellular rule as a general-purpose unsupervised data-clustering mechanism. The novelty boundary is therefore intentionally narrow. Cellular automata have previously been used for clustering, and graph neural networks have extensively been used for graph clustering; G-NAC instead uses a shared recurrent graph-neural cellular rule whose unsupervised dynamics generate a clusterrevealing state.
2.3
Deep Representation Learning for Clustering
A large body of deep clustering work instead approaches clustering as a representationlearning problem. Deep Embedded Clustering (DEC) jointly learns a nonlinear mapping into a latent space and refines cluster assignments using a clusteringoriented objective (Xie et al., 2016). Improved Deep Embedded Clustering (IDEC) augments this formulation with reconstruction-based structure preservation, reducing distortion of the learned feature space during clustering (Guo et al., 2017). These methods differ fundamentally from G-NAC in their computational organization. DEC and IDEC learn a feed-forward embedding in which observations become easier to partition. G-NAC instead learns a recurrently applied local transition rule. The representation of a cell therefore depends not only on its initial feature vector but also on the evolving states of its graph neighbors over multiple recurrent steps. This distinction is relevant because G-NAC does not optimize point-wise cluster assignments directly. Rather, clustering emerges from repeated local
5
interactions constrained by a graph substrate. However, DEC and IDEC are important comparison methods because they represent the established paradigm of explicitly learning a latent representation for unsupervised clustering. The unsupervised objective of G-NAC also draws on recent self-supervised representation-learning methods to prevent representational collapse. Variance and covariance regularization are inspired by VICReg (Bardes et al., 2022), which maintains feature-wise variance while discouraging redundant latent dimensions. The term non-neighbor dispersion is related to the objective of Gaussian-potential uniformity of Wang and Isola (2020). These methods were primarily developed for representation learning over independently sampled observations. G-NAC adapts related anti-collapse principles to an evolving graphconnected domain state, balancing local graph smoothness against global representational dispersion.
2.4
Deep Graph Clustering
Deep graph clustering methods combine graph representation learning with unsupervised clustering objectives. Representative approaches include DAEGC, which couples graph-attention embeddings with self-training (Wang et al., 2019), and SDCN, which combines autoencoding with graph convolution to incorporate structural information during clustering (Bo et al., 2020). DMoN instead learns graph representations through a differentiable modularity objective, directly optimizing graph partition structure without pseudo-label supervision (Tsitsulin et al., 2023). G-NAC likewise exploits local graph structure, but differs in both its dynamics and the role assigned to the graph. Rather than using a finite feed-forward graph encoder, G-NAC repeatedly applies a shared cellular transition rule, making the learned object a rule of graph-state evolution rather than only an embedding function. Moreover, its kNN graph is constructed from observations and serves as an interaction substrate rather than necessarily being the object to be partitioned. The recurrent dynamics instead transform latent relations on this fixed topology before the resulting representation is clustered.
2.5
Self-Organizing Neural Clustering
G-NAC is also conceptually related to self-organizing neural clustering methods. The Self-Organizing Map (SOM) (Kohonen, 1982), Neural Gas (Martinetz and Schulten, 1991), and Growing Neural Gas (Fritzke, 1995) organize representative units according to the distribution and topology of observed data. Such methods demonstrate that useful cluster structure can emerge through repeated local or competitive adaptation rather than explicit supervised targets. The similarity is primarily conceptual. In both self-organizing clustering and G-NAC, global organization emerges from repeated local adaptation. However, classical competitive-learning methods update prototype vectors or network topology according to competitive adaptation rules. G-NAC instead maintains one graph cell per observation and learns a shared neural transition rule 6
that updates latent cellular states through conductance-weighted neighbor interactions. The graph dynamics therefore operate directly over the observations rather than through a separate set of learned prototypes.
2.6
Relational and Rank-Based Cluster Readout
The final G-NAC readout is related to rank-based similarity and spectral clustering. Point-wise neighbor orderings have been used as similarity signals in rank-order clustering (Zhu et al., 2011), while shared-neighbor information has been used to construct affinities for spectral clustering (Ye and Sakurai, 2016). G-NAC instead globally ranks learned domain-space distances over the edges of the fixed graph. The same relational ordering underlies both the empirical rankstability stopping criterion and the final affinity construction, linking recurrent evolution to the partition readout. Learned spectral clustering provides a complementary precedent. SpectralNet learns a nonlinear representation by approximately optimizing a spectral clustering objective (Shaham et al., 2018). G-NAC instead learns a shared recurrent cellular transition rule through local graph interactions and applies spectral partitioning only to the resulting edge-rank affinity. Spectral clustering therefore serves as a readout of the learned cellular organization rather than as the objective defining the representation.
2.7
Positioning of G-NAC
The preceding literature establishes several important precedents. Cellular automata have been used directly for data clustering; cellular learning automata have been used for community detection; GNCAs provide learned recurrent dynamics on arbitrary graphs; and deep graph clustering learns graph-informed representations for unsupervised partitioning. G-NAC combines these themes but assigns a different role to the cellular dynamics. Specifically, G-NAC learns a shared graph-neural cellular transition rule whose recurrent unsupervised evolution transforms a fixed neighborhood graph into a cluster-revealing relational state. Cluster structure is therefore treated as an emergent domain organization of the learned graph dynamics rather than as the direct output of a feed-forward clustering head, a hand-designed cellular rule, or a community-detection objective applied to the original graph.
3
Method
3.1
Problem Formulation
Let X = {xi }N i=1 ,
7
xi ∈ Rd ,
(1)
denote N observations represented by d-dimensional feature vectors. Graph Neural Automata Clustering (G-NAC) seeks a partition C = {ci }N i=1 ,
ci ∈ {1, . . . , K},
(2)
without cluster-label supervision. Rather than predicting assignments directly, G-NAC represents observations as cells on a graph and learns a shared local transition rule whose repeated application produces a cluster-revealing relational state: X, G, Z (0) −→ Z (1) −→ · · · −→ Z (T ) −→ C. (3) The requested number of clusters K is used only by the final componentresolved or spectral readout; it is not supplied during training or recurrent inference. In the benchmark experiments, K is taken from the reference-partition metadata and supplied equally to methods requiring a cluster count; in deployment it must be specified externally or estimated by a separate procedure. Input preprocessing is likewise external to G-NAC, and the estimator does not internally standardize X. The formulation requires N > 1, dz > 1, at least one graph edge, and graph non-neighbor pairs for the dispersion term. Small positive offsets are used in local-scale and bandwidth calculations to handle zero distances numerically; inputs violating the structural requirements require explicit handling.
3.2
Fixed Neighborhood Graph and Edge Geometry
G-NAC first constructs a fixed Euclidean k-nearest-neighbor (kNN) graph G = (V, E),
(4)
with one graph vertex for each observation. For every vertex, the k nearest neighbors are computed using Euclidean distance. Because the directed kNN relation is not generally symmetric, it is converted to an undirected relation by union: (i, j) ∈ E ⇐⇒ j ∈ Nk (i) ∨ i ∈ Nk (j). (5) This is the conventional symmetrized kNN construction used in similarity-graph methods and spectral clustering (von Luxburg, 2007). The adjacency is fixed throughout both training and inference. G-NAC therefore does not rewire the graph. Instead, it learns recurrent cellular states and time-varying message conductances on the fixed neighborhood substrate. Each undirected edge is stored in both directions for message aggregation. Two distinct quantities are associated with each edge. First, a fixed Gaussian edge weight wij is computed from the Euclidean input-space distance and is used by the graph-smoothness regularizer: dij = ∥xi − xj ∥2 ,
(6)
σ = median ({dij : (i, j) ∈ Edir }) ,
(7)
8
and d2ij wij = exp − 2 2σ
! .
(8)
Second, a three-dimensional geometry vector gij is supplied to the learned cellular transition rule: h i gij = deij Jij Mij , (9) where deij is a locally normalized Euclidean distance, Jij is the Jaccard overlap between the original directed kNN neighbor sets, and Mij indicates whether the original neighbor relation is mutual. For each node, let si = median ({diℓ : ℓ ∈ Nk (i)}) .
(10)
The locally normalized distance is dij . −8 2 (si + sj ) + 10
deij = 1
(11)
The neighborhood-overlap feature is Jij =
|Nk (i) ∩ Nk (j)| , |Nk (i) ∪ Nk (j)|
(12)
and the mutual-neighbor indicator is Mij = I [j ∈ Nk (i) ∧ i ∈ Nk (j)] .
(13)
The fixed graph weight wij should be distinguished from the learned conductance introduced below. The former represents input-graph similarity and is used for regularization, whereas the latter is a time-dependent quantity learned by the cellular transition rule and controls recurrent message exchange.
3.3
Graph Neural Cellular Dynamics
G-NAC builds upon the Graph Neural Cellular Automata (GNCA) formulation of Grattarola et al. (2021), in which a graph neural network parameterizes a shared cellular transition rule over an arbitrary graph. As in a GNCA, the same learned transition rule is reused across graph cells and recurrent steps, allowing global organization to emerge through repeated local interactions. Each cell maintains the immutable observed feature vector xi , an internal recurrent hidden state (t) hi ∈ Rdh , (14) and an explicit domain state (t)
zi
∈ Rdz .
9
(15)
The complete cellular state can therefore be represented as (t) (t) (t) si = xi , hi , zi .
(16)
The hidden state serves as internal computational memory for the transition rule, whereas the domain state is the latent representation whose relational organization is subsequently used for clustering. 3.3.1
State Initialization
At the beginning of each training rollout, a fresh Gaussian seed ξi ∈ Rdξ ,
ξi ∼ N (0, I),
(17)
is sampled independently for every cell. This weak stochastic initialization provides symmetry breaking between otherwise similar cellular configurations. The initial hidden state is (0)
hi
= tanh (fx (xi ) + sξ fξ (ξi )) ,
(18)
where fx and fξ are learned encoders and sξ controls the contribution of the stochastic seed. The initial domain state is generated from the concatenated observation and scaled seed: (0) zi = fz,0 ([xi , sξ ξi ]) . (19) The domain initializer has no final squashing activation, allowing the anticollapse objective to establish the scale of the domain coordinates. 3.3.2
Learned Edge Conductance and Message Construction
For every stored directed edge i → j, G-NAC compares the endpoint observations, hidden states, domain states, and fixed edge geometry. The edge representation is i h (t) (t) (t) (t) (t) eij = |xi − xj |, |hi − hj |, |zi − zj |, gij . (20) A learned edge network maps this representation to a scalar conductance: (t) (t) αij = sigmoid fe (eij ) . (21) The conductance is learned entirely through the unsupervised objective; it is not trained as a supervised boundary classifier. Conductance-weighted signed disagreement messages are then formed for the hidden and domain states: (t) (t) (t) (t) (22) mij,h = αij hi − hj , (t)
(t)
mij,z = αij
(t)
(t)
zi − zj
10
.
(23)
These messages are mean-aggregated at the destination node: (t)
(t)
(24)
(t)
(t)
(25)
mj,h = meani:(i,j)∈Edir mij,h , mj,z = meani:(i,j)∈Edir mij,z . 3.3.3
Recurrent Hidden and Domain Updates
The hidden-state update receives the current hidden state, aggregated hidden disagreement, current domain state, and immutable observation: (t) (t) (t) (t) ∆hj = fh [hj , mj,h , zj , xj ] . (26) The resulting residual update is (t+1)
hj
(t) (t) = tanh hj + η∆hj ,
(27)
where η is the recurrent update scale. The domain update uses the newly updated hidden state, current domain state, aggregated domain disagreement, and observation: (t) (t) (t+1) (t) ∆zj = fz [hj (28) , zj , mj,z , xj ] , followed by (t+1)
zj
(t)
(t)
= zj + η∆zj .
(29)
Both update networks terminate in hyperbolic-tangent activations, thereby bounding each proposed update. The hidden state is additionally passed through an outer tanh following the residual update. The accumulated domain state is not externally squashed, allowing its coordinate scale to evolve under the anticollapse objective. The same functions fe , fh , and fz , and therefore the same learned parameters, are applied to every graph cell and at every recurrent step. G-NAC consequently learns a shared local rule of cellular evolution rather than node-specific parameters or directly supervised cluster assignments.
3.4
Unsupervised Domain-Formation Objective
G-NAC is trained without ground-truth cluster assignments. Its objective combines local graph coherence, anti-collapse regularization, weak non-local dispersion, and late-rollout temporal stabilization: L = λs Lsmooth + λv Lvar + λc Lcov + λu Lunif + λt Ltemp .
11
(30)
3.4.1
Weighted Graph Smoothness
Graph-based learning commonly assumes that strongly connected observations should receive similar representations or function values. Weighted squared differences over graph edges are a standard graph-Laplacian smoothness construction (Belkin et al., 2006; Zhu et al., 2003). G-NAC applies this principle to the final domain state of the training rollout: X wij ∥zi − zj ∥22 Lsmooth =
(i,j)∈Edir
X
wij + 10−8
.
(31)
(i,j)∈Edir
Because each undirected edge is stored in both directions with the same weight, the directed storage does not alter the normalized value relative to summing once per undirected edge. In isolation, graph smoothness admits the trivial globally collapsed solution z1 = z2 = · · · = zN .
(32)
The remaining objective terms therefore provide complementary anti-collapse and differentiation pressures. 3.4.2
Variance Regularization
To penalize dimensional collapse, G-NAC uses a variance regularizer inspired by Variance-Invariance-Covariance Regularization (VICReg) (Bardes et al., 2022). For domain coordinate q, the implementation computes the population variance across the N cells: q σq = Varpop (z·q ) + 10−4 . (33) The variance loss is d
Lvar =
z 1 X max(0, γ − σq ), dz q=1
(34)
where γ denotes the target minimum standard deviation. The term penalizes coordinate standard deviations below γ but does not impose a hard variance floor or guarantee avoidance of collapsed stationary states. It also does not reward coordinates for increasing their standard deviation beyond γ. 3.4.3
Covariance Regularization
Variance alone does not ensure that different domain coordinates encode distinct information. G-NAC therefore incorporates a VICReg-inspired covariance penalty (Bardes et al., 2022). Let Zc = Z − Z, 12
(35)
where Z contains the coordinate-wise means. The sample covariance matrix is Σz =
Zc⊤ Zc . N −1
(36)
G-NAC penalizes the mean squared off-diagonal covariance: X (Σz )2pq Lcov =
p̸=q
dz (dz − 1)
.
(37)
This differs slightly in scaling from the original VICReg covariance penalty: G-NAC averages over the off-diagonal entries rather than normalizing only by the representation dimension. 3.4.4
Non-Neighbor Dispersion
G-NAC additionally applies a weak pairwise dispersion term inspired by the Gaussian-potential uniformity objective of Wang and Isola (2020). Their formulation encourages uniformity among independently sampled, unit-normalized representations on the hypersphere. G-NAC instead adapts the Gaussian-potential principle to the relational structure of the graph. Let PNN ⊂ {(i, j) : i ̸= j, j ∈ / NG (i)} (38) denote a randomly sampled set of explicit graph non-neighbor pairs. The GNAC loss is X 1 Lunif = exp −τ ∥zi − zj ∥22 . (39) |PNN | (i,j)∈PNN
This term is not identical to the uniformity loss of Wang and Isola. GNAC does not constrain z to the unit hypersphere, omits the outer logarithm, and samples graph non-neighbors rather than independent global pairs. Consequently, the term is more precisely interpreted as a weak non-neighbor dispersion pressure than as hyperspherical uniformity. Importantly, non-neighboring cells are not assumed to belong to different ground-truth clusters. Two observations belonging to the same cluster or manifold may be sufficiently distant that they are not directly connected in the kNN graph. The term is therefore assigned a comparatively small coefficient and serves only as a weak non-local anti-collapse pressure. 3.4.5
Temporal Domain Stability
Because G-NAC defines clustering through recurrent dynamics, the training objective additionally encourages the final portion of each rollout to change gradually. For a sequence of domain states near the end of the rollout, h i 1 X Ltemp = MSE z (t+1) , sg z (t) , (40) |T | t∈T
13
where sg[·] denotes stop-gradient. The preceding state is therefore treated as a detached target for the current state. This discourages abrupt late-rollout changes without forcing earlier cellular states to remain static. With the benchmark configuration of 16 recurrent training steps and four retained tail states, the temporal loss contains the three successive transitions between those final four states. This training regularizer is distinct from the Spearman rank-stability criterion used for adaptive inference. 3.4.6
Objective Interpretation
The complete objective can be interpreted as a competition between local attraction and global differentiation: Lsmooth
→
local coherence,
Lvar
→
anti-collapse,
Lcov
→
coordinate decorrelation,
Lunif
→
weak non-local dispersion,
Ltemp
→
late-rollout stabilization.
(41)
Graph smoothness encourages neighboring cells to organize into similar domain states, but alone favors global consensus. Variance and non-neighbor dispersion oppose this collapse, while covariance regularization discourages redundant latent coordinates. The desired configuration is therefore neither global collapse nor unrestricted separation, but a set of locally coherent and globally differentiated domains.
3.5
Training and Unsupervised Checkpoint Selection
At every training epoch, G-NAC samples a fresh Gaussian cellular seed, initializes the hidden and domain states, and unrolls the same shared transition rule for a fixed number of recurrent steps. Graph non-neighbor pairs are sampled anew for the weak dispersion term. The five loss components in Eq. (30) are then evaluated and differentiated through the recurrent rollout. Optimization uses AdamW with gradient-norm clipping. Model selection remains entirely unsupervised. Following a burn-in period, the parameter state having the lowest total unsupervised training loss is retained. Ground-truth labels and external clustering metrics such as ARI, AMI, and NCA are not used for training or checkpoint selection. For the publication benchmark, the frozen configuration is summarized in Table 1. All benchmark experiments use a fixed training budget of 100 epochs unless otherwise stated.
14
Table 1: Frozen G-NAC configuration used in the publication benchmark. Parameter Value Role k Training rollout Training epochs Learning rate Weight decay Gradient clip λs λv λc λu λt γ Non-neighbor pairs τ Temporal tail dh dz dξ η sξ Burn-in
3.6
20 16 100 2 × 10−3 1 × 10−5 5.0 1.0 4.0 0.10 0.10 0.05 1.0 3000 2.0 4 48 8 4 0.15 0.10 40 epochs
kNN graph degree Recurrent updates per epoch Benchmark training budget AdamW learning rate AdamW weight decay Maximum gradient norm Graph smoothness Variance anti-collapse Covariance regularization Non-neighbor dispersion Temporal stabilization Target standard deviation Sampled per epoch Dispersion temperature Retained final states Hidden-state dimension Domain-state dimension Stochastic-seed dimension Recurrent update scale Seed scale Checkpoint eligibility
Relational Stability and Adaptive Inference
After training, the best unsupervised parameter checkpoint is restored and the cellular rule is evaluated from a deterministic inference seed. Rather than requiring the absolute domain coordinates to approach a fixed point, G-NAC measures stabilization of the relative organization of graph edges. At recurrent checkpoint T , Euclidean domain-space distances are computed over the unique undirected graph-edge set Eu : h i (T ) (T ) D(T ) = ∥zi − zj ∥2 . (42) {i,j}∈Eu
Relational stability is measured by the Spearman rank correlation between the edge-distance vectors at successive checkpoints: ρT = ρS D(Tprev ) , D(T ) . (43) The implementation passes the distance vectors directly to Spearman’s statistic; the statistic itself evaluates the correlation between their ranks. The frozen checkpoint schedule is C = {2, 4, 8, 16, 32, 64, 128}. 15
(44)
The first eligible stopping decision occurs at T = 4, comparing the states at T = 2 and T = 4. The selected recurrent depth is T ∗ = min {T ∈ C : T ≥ 4, ρT ≥ 0.95} .
(45)
If no checkpoint satisfies the criterion, T ∗ = 128. This criterion is used as an empirical rank-stability stopping rule: inference may terminate when successive checkpoint edge-distance rankings are highly correlated even if the latent coordinates continue to change in absolute scale or position. A single threshold crossing does not guarantee future convergence, stability of every individual edge, or partition invariance at later rollout depths. The G-NAC implementation may either compute the complete rollout to T = 128 and subsequently select T ∗ , or exit when the same stopping condition is satisfied. This implementation-level optimization changes the computational cost but not the mathematical stopping rule.
3.7
Global Edge-Rank Affinity and Spectral Readout
G-NAC is trained to organize relationships between graph-connected cells rather than to impose a prescribed metric scale on the latent space. The final readout therefore uses the relative ordering of domain-space edge distances rather than their absolute magnitudes. This is related to previous rank-based clustering and spectral affinity methods (Zhu et al., 2011; Ye and Sakurai, 2016), but G-NAC ranks learned domain-space distances globally over the edges of the fixed graph. Let Eu denote the set of M = |Eu | unique undirected graph edges. At the selected inference step T ∗ , define (T ∗ )
de = ∥zi
(T ∗ )
− zj
∥2 ,
e = {i, j} ∈ Eu .
(46)
re ∈ {0, . . . , M − 1},
(47)
Each edge is assigned its global ordinal rank re = rank (de ; {de′ }e′ ∈Eu ) ,
with the smallest distance assigned rank zero. For M > 1, qe =
re , M −1
while qe = 0 for M = 1. The corresponding affinity is ae = max 1 − qe , 10−6 .
(48)
(49)
The implementation obtains ordinal ranks using a stable ascending sort. Exact distance ties are therefore resolved by deterministic edge ordering rather than assigned a common average rank. Average-rank tie handling would provide a permutation-compatible alternative. Subject to fixed edge support and the same tie convention, the affinity is invariant to strictly increasing transformations of the edge distances; changes in latent scale that preserve their ordering therefore leave the affinity unchanged. 16
The sparse symmetric affinity matrix A(Z) retains the support of the original (Z) neighborhood graph and uses unit diagonal affinities, Aii = 1. Before spectral partitioning, G-NAC checks the connected components of its off-diagonal support. If the graph contains exactly K components, their labels are returned directly. Otherwise, normalized spectral clustering is applied to A(Z) as a precomputed similarity matrix (von Luxburg, 2007), followed by K-means with 20 initializations. Thus, ( Components(A), c(A) = K, RK (A) = (50) Spectral(A, K), c(A) ̸= K. The requested cluster count K therefore enters only through the final readout RK , not during training, checkpoint selection, or recurrent inference. Both adaptive stopping and affinity construction depend on the ordering of graphedge distances: the former detects high rank agreement between successive checkpoints, while the latter converts the selected ordering into the affinity used for partitioning.
3.8
Algorithm Summary
Algorithm 1 summarizes the complete G-NAC procedure. Figure 2 provides the corresponding detailed model architecture, complementing the conceptual workflow in Figure 1.
17
G-NAC: Graph Neural Automata Clustering Fixed neighborhood graph → recurrent domain formation → relational readout
B Shared recurrent cellular dynamics xᵢ hᵢ⁽ᵗ⁾ zᵢ⁽ᵗ⁾
Edge features |xᵢ−xⱼ|, |hᵢ−hⱼ|, |zᵢ−zⱼ|, gᵢⱼ
Ce ll i
Training: smoothness + variance + covariance + non-neighbor dispersion + temporal consistency
Edge GNN fₑ
Ce ll j
xⱼ hⱼ⁽ᵗ⁾ zⱼ⁽ᵗ⁾
Repeat until 𝝆spearman > cutoff
αᵢⱼ⁽ᵗ⁾ ∈ [0,1] Messages αᵢⱼ(hᵢ−hⱼ) αᵢⱼ(zᵢ−zⱼ)
Mean aggregation over neighbors
Hidden update fₕ
Domain update fz
Shared parameters at every node and recurrent step → hᵢ⁽ᵗ⁺¹⁾ , zᵢ⁽ᵗ⁺¹⁾
A Fixed neighborhood graph
C Relational readout
x ₂
x ₁
Final domain states Z⁽ᵀ⁾ x ₃
Graph-edge distances ‖zᵢ−zⱼ‖₂
x ₄
x ₅
Global edge ranks → sparse affinity A x ₆
C(A)=K spectral readout
Euclidean kNN, k = 20 Cluster labels Observed features xᵢ remain fixed; local geometry gᵢⱼ is precompute d.
Figure 2: Detailed G-NAC model architecture and recurrent information flow.
18
Algorithm 1 Graph Neural Automata Clustering (G-NAC) Require: Feature matrix X, requested cluster count K, graph degree k Ensure: Cluster assignments C 1: Construct Euclidean kNN graph G = (V, E) 2: Symmetrize the directed neighbor relation by union 3: Compute fixed smoothness weights wij and geometry gij 4: Initialize shared GNCA parameters θ 5: for e = 1, . . . , Etrain do 6: Sample fresh cellular seeds ξi ∼ N (0, I) 7: Initialize H (0) and Z (0) from X and ξ 8: for t = 0, . . . , Ttrain − 1 do 9: for all directed edges i → j do 10: eij ← [|xi − xj |, |hi − hj |, |zi − zj |, gij ] 11: αij ← sigmoid(fe (eij )) 12: mij,h ← αij (hi − hj ) 13: mij,z ← αij (zi − zj ) 14: end for 15: Mean-aggregate incoming messages at each destination 16: Update H (t+1) using the shared hidden rule 17: Update Z (t+1) using the shared domain rule 18: end for 19: Sample graph non-neighbor pairs PNN 20: Compute Lsmooth , Lvar , Lcov , Lunif , and Ltemp 21: Zero optimizer gradients 22: Compute total objective using Eq. (30) 23: Backpropagate through the recurrent rollout 24: Clip the global gradient norm to 5 25: Apply one AdamW optimizer step 26: if burn-in is complete and total loss is the lowest observed then 27: Store parameter checkpoint θ∗ 28: end if 29: end for 30: Restore θ ∗ 31: Initialize cellular states from deterministic inference seed 32: for T ∈ {2, 4, 8, 16, 32, 64, 128} do 33: Evolve the shared GNCA rule to checkpoint T 34: Compute unique-edge latent-distance vector D(T ) 35: if T ≥ 4 then 36: ρT ← ρS (D(Tprev ) , D(T ) ) 37: if ρT ≥ 0.95 then 38: T∗ ← T 39: break 40: end if 41: end if 42: Tprev ← T 43: end for 44: if no checkpoint satisfied the stopping criterion then 45: T ∗ ← 128 19 46: end if ∗ 47: Rank unique graph-edge distances at Z (T ) 48: Convert ranks to affinities using Eq. (49) 49: Form symmetric sparse affinity matrix A(Z) (Z) 50: Set Aii ← 1 51: (c, ℓ) ← ConnectedComponents(A(Z) ) 52: if c = K then
4
Datasets and Experimental Tasks
4.1
Benchmark Collections
The primary benchmark uses the versioned Clustering Benchmarks suite (Gagolewski, 2022; Gagolewski et al., 2022). It contains 73 dataset/K tasks drawn from 57 datasets in four batteries: the Fundamental Clustering and Projection Suite (FCPS) (Ultsch and Lötsch, 2020), the SIPU benchmark collection (Fränti and Sieranoja, 2018), the Graves collection (Graves and Pedrycz, 2010), and the WUT collection. WUT is distributed as part of the same versioned Clustering Benchmarks suite rather than cited here as a separate standalone source. The benchmark observations are numerical feature vectors rather than applicationspecific images, signals, or class decisions. Across the retained tasks, datasets contain 120–10,000 observations with two or three observed features, and the reference partitions contain between 2 and 50 clusters. Table 2 summarizes the composition by battery. Table 2: Composition of the primary ClustBench evaluation. Ranges are computed over the retained dataset/K tasks used in the study. Battery
Datasets
Tasks
N range
d range
K range
FCPS SIPU Graves WUT
9 16 10 22
10 21 17 25
212–4096 240–7500 200–1050 120–10000
2–3 2 2 2–3
2–7 2–50 2–5 2–10
Total
57
73
120–10000
2–3
2–50
A benchmark task consists of an unlabeled feature matrix X and a requested cluster count K. A method returns one cluster assignment for every observation. The reference partition is withheld from fitting and used only after clustering to compute external agreement metrics. Thus, the benchmark is an unsupervised partition-recovery problem rather than supervised classification, and there is no supervised training/test split for the 73 benchmark tasks. When a dataset contains more than one valid target value of K, each dataset/K combination is treated as a separate task. The requested K is obtained from the benchmark reference-partition metadata and supplied to every method that requires a cluster count. The reference assignments themselves are never provided to G-NAC during training, checkpoint selection, or recurrent inference. All methods receive the same feature representation for a given task.
4.2
Benchmark Methods and Performance Measures
Eleven methods are evaluated: G-NAC; K-means (MacQueen, 1967); Gaussian mixture modeling (GMM), fit by the expectation–maximization framework 20
(Dempster et al., 1977); Ward and average-linkage hierarchical clustering (Ward, 1963; Jain, 2010); BIRCH (Zhang et al., 1996); spectral clustering (von Luxburg, 2007); Genie (Gagolewski et al., 2016); DEC (Xie et al., 2016); IDEC (Guo et al., 2017); and SOM (Kohonen, 1982). These baselines span centroid-based, probabilistic, hierarchical, graph-spectral, self-organizing, and deep embedded clustering approaches. Performance is quantified using Adjusted Rand Index (ARI) (Hubert and Arabie, 1985), Adjusted Mutual Information (AMI) (Vinh et al., 2010), and Normalized Clustering Accuracy (NCA) as implemented by genieclust and used in the benchmark suite (Gagolewski, 2022). These metrics compare the recovered partition with the withheld reference partition after clustering; they do not participate in G-NAC optimization or checkpoint selection.
4.3
Controlled Scaling and Transfer Tasks
The robustness experiment reuses the same 57 datasets and 73 benchmark tasks while perturbing either the observed features or graph relations. The scalability and transfer experiments are separate controlled synthetic studies. Scalability uses a balanced K = 8, d = 16 isotropic Gaussian-mixture problem with graph size varied from 1,000 to 100,000 observations. Sparse-to-full transfer uses two d = 16, K = 8 synthetic families—a Gaussian mixture and noisy blobs—with independently sampled source and 100,000-node target graphs. Unlike the primary benchmark, this transfer experiment therefore has an explicit source/target distinction: model parameters are learned on the source graph, frozen, and then evaluated on an independently sampled target graph from the same generating process.
5
Experimental Evaluation
We evaluate G-NAC through four experiments. First, a multi-battery benchmark compares clustering performance and stochastic stability against ten classical, spectral, self-organizing, and deep clustering baselines. Second, measurementnoise and graph-corruption experiments examine dependence on the observed features and local interaction topology. Third, a controlled scaling experiment measures runtime and memory requirements from 103 to 105 graph cells. Finally, a sparse-to-full transfer experiment tests whether cellular rules learned on smaller source graphs can be deployed without retraining on independent 100,000-node target graphs.
5.1
Experimental Protocol
Stochastic methods were evaluated using ten algorithm seeds, S = {7, 17, 27, 37, 47, 57, 67, 77, 87, 97},
21
(51)
while deterministic methods were evaluated once per dataset/K task. G-NAC used the fixed configuration in Table 1 throughout: k = 20, a 16-step training rollout, 100 epochs, and the relational stopping rule of Section 3.6. No benchmark-specific G-NAC tuning was performed. ARI, AMI, and NCA are defined in Section 4, with ARI used as the primary metric. For datasets with multiple valid same-K reference partitions, the maximum agreement over compatible references was computed separately for each metric. Runtime denotes total wall-clock execution time and is reported as an empirical cost measure rather than a hardware-independent complexity comparison.
5.2
Statistical Analysis
Descriptive summaries use the 73 dataset/K tasks, with stochastic runs first averaged within each task. Because some underlying datasets contribute multiple values of K, inferential comparisons instead use the dataset as the independent unit. For baseline b, task-level paired differences are (b)
∆t
(b)
− ARIt . = ARIG-NAC t
(52)
Multiple task effects from the same dataset were averaged before inference. Twosided paired Wilcoxon signed-rank tests were applied to the resulting datasetlevel scores, with Holm correction across the ten G-NAC–baseline comparisons. Confidence intervals for mean ARI differences were obtained by nonparametric bootstrap resampling of datasets. Thus, benchmark means, medians, and win/tie/loss counts are descriptive task-level quantities, whereas confidence intervals and hypothesis tests use the underlying dataset as the independent unit.
5.3
Overall Benchmark Performance
Table 3 summarizes performance across the 73 dataset/K tasks. G-NAC achieved the highest mean and median ARI among the eleven evaluated methods, with a mean ARI of 0.7951 and a median ARI of 0.9379. Genie produced nearly identical mean ARI, achieving 0.7941, with a median ARI of 0.9152. The difference in mean ARI between G-NAC and Genie was therefore only approximately 0.795072 − 0.794053 = 0.001019.
(53)
Spectral clustering was the next strongest method by mean ARI at 0.7011, followed by GMM at 0.6510. The remaining methods obtained mean ARI values between approximately 0.47 and 0.56. The three agreement metrics do not produce exactly the same ordering. Although G-NAC achieved the highest mean ARI, Genie obtained the highest mean AMI (0.8503 versus 0.8350 for G-NAC). Their mean NCA values were 22
Table 3: Aggregate clustering performance across the 73 dataset/K tasks in the benchmark experiment. Stochastic methods are first averaged across algorithm seeds within each task. Seed SD denotes the mean within-task standard deviation of ARI across stochastic seeds. Method Mean ARI Median ARI Mean AMI Mean NCA Seed SD Time (s) G-NAC Genie Spectral GMM K-means IDEC Ward DEC SOM Average BIRCH
0.7951 0.7941 0.7011 0.6510 0.5580 0.5572 0.5559 0.5388 0.5330 0.5215 0.4691
0.9379 0.9152 0.7668 0.8306 0.5819 0.5694 0.6015 0.5722 0.5771 0.5197 0.4458
0.8350 0.8503 0.7747 0.7024 0.6256 0.6294 0.6338 0.6190 0.6104 0.6010 0.5709
0.8463 0.8461 0.7840 0.7394 0.6909 0.6979 0.6898 0.6801 0.6668 0.6549 0.6257
0.0193 0.0000 0.0222 0.0300 0.0022 0.0637 0.0000 0.0575 0.0201 0.0000 0.0000
nearly identical (0.8463 for G-NAC and 0.8461 for Genie). These results indicate that the two methods exhibit comparable overall benchmark performance while emphasizing slightly different partition characteristics. In contrast, G-NAC showed a considerably larger separation from ordinary spectral clustering. Mean ARI increased from 0.7011 for spectral clustering to 0.7951 for G-NAC, corresponding to an absolute mean improvement of approximately 0.094. This comparison is particularly relevant because both methods operate on graph structure. However, ordinary spectral clustering partitions its similarity graph directly, whereas G-NAC evolves node states through a learned recurrent cellular rule and then constructs a rank-based sparse affinity for its general spectral readout. The comparison therefore establishes a difference between the complete G-NAC pipeline and the evaluated ordinary spectral baseline, but does not by itself isolate the separate contributions of recurrent learning, graph support, and rank-affinity construction. 5.3.1
Paired Statistical Comparisons
Aggregate rankings can obscure whether performance differences are consistent across datasets. We therefore compared G-NAC against each baseline using dataset-level paired ARI effects as described in Section 5.2. Table 4 reports the mean dataset-level difference ∆ARI = ARIG-NAC − ARIbaseline , together with dataset-bootstrap 95% confidence intervals and Holm-adjusted two-sided Wilcoxon signed-rank p-values. The win/tie/loss counts remain descriptive counts over the 73 dataset/K tasks. 23
10.968 0.005 0.335 0.055 0.070 3.189 0.091 2.716 0.126 0.072 0.014
Table 4: Paired ARI comparisons between G-NAC and the baseline methods. Positive ∆ARI favors G-NAC. Stochastic runs are first averaged within each dataset/K task; paired effects from multiple K tasks are then averaged within each underlying dataset for inference. Confidence intervals are obtained by bootstrap resampling of datasets. Win/tie/loss counts are descriptive task-level counts. pHolm denotes the Holm-adjusted two-sided Wilcoxon signed-rank pvalue from the dataset-level analysis. Baseline Mean ∆ARI 95% CI Task W/T/L pHolm BIRCH Average linkage DEC SOM IDEC Ward K-means GMM Spectral Genie
+0.3587 +0.2945 +0.2922 +0.2900 +0.2679 +0.2649 +0.2627 +0.1651 +0.0834 +0.00025
[0.2729, 0.4466] [0.2045, 0.3900] [0.2129, 0.3759] [0.2030, 0.3816] [0.1902, 0.3497] [0.1771, 0.3589] [0.1733, 0.3586] [0.0785, 0.2597] [0.0352, 0.1371] [-0.0695, 0.0634]
62/3/8 54/6/13 56/2/15 57/2/14 60/0/13 53/6/14 50/7/16 41/9/23 38/16/19 34/20/19
1.31 × 10−8 7.06 × 10−7 1.59 × 10−7 1.59 × 10−7 5.05 × 10−8 3.60 × 10−7 2.12 × 10−6 0.00131 0.00607 0.358
After accounting for repeated cluster-count tasks from the same underlying datasets, the inferential conclusions were unchanged for the full benchmark. G-NAC differed significantly from nine of the ten evaluated baselines after Holm correction. Relative to ordinary spectral clustering, the datasetlevel mean paired ARI difference was 0.0834 (95% bootstrap CI [0.0352, 0.1371]; pHolm = 0.00607). Because the ordinary spectral baseline differs from G-NAC in more than the recurrent state evolution, this significant whole-pipeline difference should not be interpreted as a mechanism-isolating ablation. It establishes that the complete G-NAC procedure differs from the evaluated ordinary spectral baseline under the benchmark protocol; matched graph/readout controls are required to attribute that difference specifically to recurrence or learned conductance. G-NAC also differed significantly from GMM in the full benchmark, with a dataset-level mean paired improvement of 0.1651 (95% bootstrap CI [0.0785, 0.2597]; pHolm = 0.00131). In contrast, no statistically significant difference was observed between GNAC and Genie. Their dataset-level mean paired ARI difference was 0.00025, with a 95% bootstrap confidence interval spanning zero ([−0.0695, 0.0634]) and pHolm = 0.358. At the descriptive task level, G-NAC won 34 tasks, tied on 20, and lost 19. The near-zero observed mean difference therefore does not establish statistical equivalence; the interval remains compatible with non-negligible differences in either direction.
24
Table 5: Mean ARI by benchmark battery for the strongest methods. Values are averaged over dataset/K task means within each battery.
5.3.2
Method
FCPS
SIPU
Graves
WUT
G-NAC Genie Spectral GMM
0.9530 0.9249 0.8786 0.7646
0.8074 0.8004 0.6444 0.7203
0.7953 0.7837 0.7553 0.5718
0.7214 0.7434 0.6409 0.6013
Performance Across Benchmark Batteries
Table 5 separates performance by benchmark battery. G-NAC obtained the highest mean ARI on FCPS (0.9530), SIPU (0.8074), and Graves (0.7953), while Genie was highest on WUT (0.7434 versus 0.7214 for G-NAC). G-NAC exceeded ordinary spectral clustering in mean ARI across all four batteries, while the relative ordering of G-NAC and Genie varied by collection. 5.3.3
Stochastic Stability
G-NAC exhibited a mean within-task ARI standard deviation of 0.0193 across stochastic seeds, compared with 0.0222 for spectral clustering, 0.0300 for GMM, 0.0575 for DEC, 0.0637 for IDEC, and 0.0201 for SOM. Thus, G-NAC showed relatively low, although nonzero, sensitivity to stochastic initialization. 5.3.4
Computational Cost
G-NAC incurred substantially greater computational cost than the classical baselines, with mean task runtime 10.97 s compared with 0.005 s for Genie, 0.335 s for spectral clustering, 0.070 s for K-means, and 0.055 s for GMM. It was also slower than DEC (2.72 s) and IDEC (3.19 s). Large-scale runtime and memory behavior are examined separately in Section 5.5.
5.4
Robustness to Measurement and Graph Corruption
The robustness experiment reused the 57 datasets and 73 dataset/K tasks under additive Gaussian feature noise, random deletion of directed kNN slots, and random rewiring of directed kNN slots at R = {0, 0.05, 0.10, 0.20, 0.30, 0.50}.
(54)
Each condition used the same ten matched corruption and algorithm seeds as the main benchmark. Gaussian noise was scaled so that its expected RMS vector magnitude was r rX , where rX is the RMS Euclidean radius of the clean sample. All methods received the same perturbed observations, and graph-based methods rebuilt their graphs. For graph corruption, X remained fixed while a fraction r of 25
Table 6: Mean task-level ARI under measurement and graph corruption. Values first average the ten matched replicates within each of the 73 dataset/K tasks. The shared spectral control uses the same corrupted graph support as G-NAC. Corruption
Method
0
0.05
0.10
0.20
0.30
0.50
Gaussian noise
G-NAC Genie Spectral GMM
0.7951 0.7941 0.7011 0.6510
0.7571 0.7581 0.6790 0.6392
0.7090 0.6781 0.6599 0.6227
0.5899 0.5425 0.5793 0.5405
0.4786 0.4289 0.4476 0.4615
0.3119 0.2543 0.3034 0.3353
Edge deletion
G-NAC Shared spectral
0.7951 0.6944
0.7944 0.6929
0.7957 0.6950
0.7966 0.6982
0.7977 0.6964
0.7990 0.6955
Edge rewiring
G-NAC Shared spectral
0.7951 0.6944
0.6684 0.5914
0.5729 0.5486
0.5306 0.5063
0.4875 0.4479
0.4240 0.3583
each node’s k = 20 directed neighbor slots was either deleted or replaced by sampled non-neighbors before union symmetrization. Local distance scales and the clean RBF scale remained fixed; overlap and mutual-neighbor attributes were recomputed, no connectivity repair was applied, and G-NAC was retrained for every condition. Graph-corruption experiments additionally included a shared-support spectral control using the same corrupted sparse support as G-NAC. Replicates were averaged within dataset/K tasks and repeated K tasks within datasets were then averaged for dataset-level inference. Bootstrap intervals and two-sided Wilcoxon tests were Holm-corrected within each corruption family and metric. Table 6 summarizes mean task-level ARI across the corruption conditions. 5.4.1
Measurement Noise
G-NAC mean ARI decreased progressively from 0.7951 on clean data to 0.7571, 0.7090, 0.5899, 0.4786, and 0.3119 as corruption increased from r = 0.05 to 0.50. Every nonzero condition differed significantly from clean performance after Holm correction (pHolm ≤ 0.003); Figure 3 shows the corresponding curves. Relative to Genie, G-NAC’s dataset-level mean ARI advantage was 0.0494, 0.0476, and 0.0588 at r = 0.20, 0.30, and 0.50, respectively, with pHolm = 0.0188, 0.0031, and 3.6 × 10−5 . This does not imply uniformly slower degradation than every baseline: at r = 0.50, for example, GMM obtained mean ARI 0.3353 versus 0.3119 for G-NAC. 5.4.2
Missing Versus Incorrect Graph Relationships
Edge deletion produced little aggregate degradation. Mean G-NAC ARI remained within 0.004 of clean performance and reached 0.7990 after deletion of 50% of directed neighbor slots; none of the five nonzero levels differed significantly from clean after Holm correction. Mean component count changed only from 1.96 to 1.99, with no isolated nodes. The shared-support spectral control
26
Figure 3: Mean ARI as noise increases. likewise remained near ARI 0.69. G-NAC maintained a mean advantage of approximately 0.086–0.090 over this control at every level (pHolm ≤ 0.0019), but their degradation rates were not significantly different. Rewiring was substantially more damaging. G-NAC mean ARI fell from 0.7951 to 0.6684 at 5% rewiring and 0.4240 at 50%, with every nonzero condition differing from clean (pHolm ≤ 3.4 × 10−5 ). Mean component count also fell from 1.96 to 1.00 at 5%, eliminating component-resolved readouts. G-NAC remained above the shared-support spectral control at every level, although only the 5% comparison remained significant after family-wise correction. Under this corruption-and-retraining protocol, deletion of directed neighbor slots was therefore tolerated substantially better than their replacement by incorrect relationships. This asymmetry indicates dependence on trustworthy local topology rather than an ability to recover useful structure from arbitrary connectivity. 5.4.3
Component-Resolved Readout Sensitivity
The component-resolved branch was activated on 15 of the 73 clean tasks, all with ARI = 1. Because these outputs are determined by the fixed graph connectivity, the analysis was repeated without them, leaving 58 tasks from 47 datasets. Mean task-level ARI was 0.7421 for G-NAC, 0.7623 for Genie, 0.6981 for GMM, and 0.6741 for spectral clustering. G-NAC remained significantly different from spectral clustering at the dataset level (∆ARI = 0.0619, 95% CI [0.0178, 0.1101], pHolm = 0.0392), whereas comparisons with Genie (−0.0206, pHolm = 0.573) and GMM (0.0610, 95% CI [−0.0140, 0.1465], pHolm = 0.455) were not significant.
27
Table 7: Empirical G-NAC scalability. Times and memory values are medians across three algorithm seeds. Power exponents α are fitted over N ≥ 5,000 using log y = α log N + β to reduce the influence of fixed startup overhead at the two smallest sizes. CUDA memory is reported in MiB. Quantity Total fit time (s) Graph construction (s) Fit excluding graph (s) End-to-end time (s) Peak CUDA allocated (MiB) Peak CUDA reserved (MiB)
5k
10k
20k
50k
100k
α
R2
15.27 0.54 14.74 15.80 364.8 482
30.75 1.11 29.64 31.88 717.7 942
60.55 2.48 58.05 62.86 1421.9 1930
153.27 7.51 145.82 159.55 3548.5 4732
333.34 17.25 315.93 346.79 7085.3 9230
1.023 1.166 1.016 1.025 0.991 0.989
0.9995 0.9993 0.9995 0.9995 1.0000 0.9999
Rewiring sensitivity also persisted: mean G-NAC ARI followed 0.7421 → 0.6663 → 0.6182 → 0.5887 → 0.5413 → 0.4645 from r = 0 to 0.50. Thus, the component-resolved cases contribute to aggregate performance but do not fully explain the spectral comparison or sensitivity to incorrect graph relationships.
5.5
Time and Memory Scalability
A third experiment isolated scaling with the number of graph cells N . A single balanced isotropic Gaussian-mixture distribution with K = 8 clusters and d = 16 observed features was sampled once at Nmax = 100,000. Cluster centers were placed at radius 4.0 and each component used unit isotropic standard deviation. Smaller datasets were nested prefixes of the same master sample, so X1k ⊂ X2k ⊂ X5k ⊂ · · · ⊂ X100k .
(55)
N ∈ {1,000, 2,000, 5,000, 10,000, 20,000, 50,000, 100,000}.
(56)
The tested sizes were
At every scale G-NAC retained the frozen G-NAC configuration used throughout this study: k = 20, 16 recurrent training steps, 100 epochs, FP32 arithmetic, activation checkpointing, and the same adaptive inference rule. Three algorithm seeds (7, 17, and 27) were evaluated per size. The experiment separately timed neighborhood-graph construction, training after graph construction, adaptive inference, and final readout. CUDA peak allocated and reserved memory were measured with PyTorch, while process resident-set size was sampled independently. CUDA operations were synchronized around timed stages. All runs were performed on an NVIDIA GeForce RTX 5070 with 12 GB device memory under Windows 11. No componentresolved readout occurred at any scale, so the large-N timing curve reflects the nontrivial spectral-readout path. Table 7 summarizes the resulting timing and GPU-memory measurements. For N ≥ 5,000, total fit time scaled empirically as N 1.023 , fit time excluding graph construction as N 1.016 , and end-to-end time as N 1.025 . Graph construction was mildly superlinear (N 1.166 ) but required only 17.25 s of the 333.34 s 28
median fit time at N = 100,000. Peak CUDA allocated and reserved memory scaled as N 0.991 and N 0.989 , reaching 7085 MiB (6.92 GiB) and 9230 MiB (9.01 GiB), respectively. Median end-to-end execution at this scale was 346.79 s. Mean ARI remained between 0.961 and 0.974 across all seven sizes and reached 0.9736 at N = 100,000. Near-linear scaling also persisted when the static edge-difference cache was disabled at 100,000 nodes after exceeding its configured 128 MB cap. These measurements are hardware- and implementationspecific, but indicate approximately linear empirical time and GPU-memory scaling over the tested range for fixed graph degree and model configuration.
5.6
Sparse-to-Full Inductive Rule Transfer
The final experiment tested whether a cellular rule must be trained at its eventual deployment scale. Rules learned on source graphs of varying size were frozen and deployed without optimization on independent 100,000-node target graphs from the same generating process. 5.6.1
Experimental Design
Two d = 16, K = 8 synthetic families were used: an isotropic Gaussian mixture and a more difficult noisy-blobs family. Ten independent source–target pairs were generated per family with matched generating parameters and disjoint observations. Targets contained Ntarget = 100,000 observations, while nested source samples used Nsource ∈ {1,000, 2,000, 5,000, 10,000, 20,000, 50,000, 100,000}. Each source graph was constructed only from observations available at that size. Three training seeds were evaluated using the same fixed G-NAC configuration as the preceding experiments. After training, only the learned transition-rule parameters were transferred. Fresh cellular states were initialized for deployment either on the complete source realization or on the independent 100,000-node target. Direct targettrained G-NAC, target rank-affinity spectral clustering, K-means, and an untrained randomly initialized G-NAC rule served as controls; K = 8 was used only by the final readout. Statistical comparisons used the independent source–target pair as the experimental unit after averaging its three training seeds. An ARI difference of 0.03 was selected prospectively as the practical noninferiority margin relative to complete 100,000-node source training. 5.6.2
Transfer across graph size and realization
Table 8 summarizes independent-target performance as a function of source training size. On the Gaussian mixture, target performance was nearly invariant to source size. A rule trained using only 1,000 observations achieved mean ARI
29
Table 8: Sparse-to-full transfer to independent 100,000-node target graphs. ∆noisy denotes the mean ARI difference relative to a rule trained on the complete 100,000-node source graph. Training time is shown for the noisy-blobs source condition. Nsource Gaussian ARI Noisy ARI ∆noisy Fit time (s) 1,000 5,000 20,000 100,000
0.9729 0.9735 0.9737 0.9739
0.7343 0.7621 0.7685 0.7709
-0.0366 -0.0089 -0.0025 0.0000
10.0 15.2 60.0 328.5
0.9729 after deployment to an independent 100,000-node target, compared with 0.9739 for rules trained on all 100,000 source observations. The more difficult noisy-blobs family exhibited a clearer sample-size dependence. Rules trained on 1,000 and 2,000 source observations achieved mean independent-target ARI values of 0.7343 and 0.7240, respectively, corresponding to reductions of 0.0366 and 0.0469 relative to complete-source training. Both exceeded the prespecified 0.03-ARI practical tolerance. In contrast, increasing the source sample to 5,000 observations raised mean target ARI to 0.7621, compared with 0.7709 for complete 100,000-node source training. The paired difference was ∆sparse = −0.0089,
95% CI = [−0.0114, −0.0064],
placing the 5,000-node condition comfortably within the prespecified practical noninferiority margin. The remaining difference continued to decrease with source size, reaching −0.0025 at 20,000 observations and approximately zero at 50,000 observations. Importantly, the transfer behavior was not explained by reuse of source observations. Across source sizes, performance on the overlapping within-realization graph and the completely disjoint target graph was nearly identical. For example, at Nsource = 5,000, the mean noisy-blobs ARI was 0.7647 under withinrealization deployment and 0.7621 on the independent target. Similar differences of only a few thousandths of ARI were observed throughout the source-size sweep. Full-scale transfer further isolated the cost of changing graph realizations from that of sparse training. For the Gaussian family, a rule trained on an independent 100,000-node source graph differed from a rule retrained directly on the target by only ∆transfer = −0.00007 ARI, with a 95% confidence interval of approximately [−0.00015, 0.00000]. For noisy blobs, the corresponding difference was ∆transfer = +0.00027, 30
with a 95% confidence interval of [−0.00112, 0.00219]. Thus, once the source graph was sufficiently sampled, transferring the learned cellular rule to an unseen graph incurred essentially no additional performance penalty relative to retraining G-NAC directly on that graph. 5.6.3
Sparse Rule Learning and Computational Cost
On noisy blobs, 5,000-node source training required approximately 15.2 s and 365 MiB peak allocated CUDA memory, compared with 328.5 s and 7.0 GiB at 100,000 nodes. The 5% source condition therefore reduced training time by approximately 21.6× and memory by roughly 19–20× while reducing independenttarget ARI by less than 0.009. No component-resolved source readouts occurred. Sparse-source self-performance could be substantially lower than target performance of the same rule. At 1,000 nodes, noisy-blobs self-ARI was 0.5506, whereas independent-target ARI was 0.7343; the difference approached zero by 100,000 observations. Thus, rule quality and the quality of the finite graph on which that rule is expressed appear partially separable. 5.6.4
Relation to Local Graph Geometry
Local normalization provides one possible explanation for scale transfer. On noisy blobs, mean raw edge distance decreased from approximately 5.83 at 1,000 source observations to 4.00 on the 100,000-node target, whereas the normalized distance dij deij = 1 2 (si + sj ) + ϵ remained approximately 1.0485 and 1.0487. The Gaussian family showed similar behavior. This association is consistent with reduced dependence on sampling density but does not establish a causal role for normalization. Other graph properties changed with density. On noisy blobs, cross-cluster edges decreased from approximately 0.386 to 0.189, while target-domain boundary AUC increased from approximately 0.634 after 1,000-node source training to 0.749 after complete-source training. Improved local neighborhood fidelity may therefore contribute to the observed source-size dependence. The controls constrain the interpretation of the transfer result. On 100,000node targets, direct rank-affinity spectral clustering achieved ARI approximately 0.9745 and 0.7670 on Gaussian and noisy data, respectively; K-means achieved 0.9768 and 0.6622; an untrained G-NAC rule achieved 0.9728 and 0.7634; and transferred complete-source G-NAC achieved 0.9739 and 0.7709. Thus, these experiments establish transferability and sample efficiency of fitted G-NAC rules, not the necessity of fitting for strong performance on these synthetic distributions.
31
5.7
Summary of Experimental Findings
Across the 73 benchmark tasks, G-NAC achieved the highest overall mean and median ARI among the eleven evaluated methods using a single fixed hyperparameter configuration. Dataset-level paired analysis showed significant differences from nine baselines, including ordinary spectral clustering, while no significant difference was observed between G-NAC and Genie. These results establish the complete G-NAC pipeline as competitive across the evaluated benchmark, although they do not isolate the contribution of recurrent learning from the graph construction and rank-based readout. The subsequent experiments clarify the conditions and costs associated with this performance. G-NAC was comparatively insensitive to deletion of directed neighbor slots under the tested retraining protocol, but degraded progressively under erroneous rewiring and measurement noise, indicating greater sensitivity to incorrect than incomplete local relationships. For fixed graph degree and model configuration, training time and GPU memory scaled approximately linearly over 5,000–100,000 nodes. Finally, learned transition rules transferred without retraining to substantially larger, independently sampled graphs from the same generating processes. On the more difficult noisy-blobs family, a rule trained on 5,000 nodes achieved target performance within 0.009 ARI of 100,000node source training while requiring approximately 21.6× less training time and roughly 19–20× less peak allocated GPU memory. Taken together, the experiments characterize G-NAC as a competitive but computationally more expensive clustering procedure whose performance depends on meaningful local graph structure, whose empirical cost scales approximately linearly over the tested range, and whose learned cellular rule can transfer across graph size and independent graph realizations under matched generating conditions.
6
Discussion
G-NAC is best understood as a learned dynamical process operating over local relational structure rather than simply as a neural embedding method. A neighborhood graph defines local interactions, while repeated application of a shared graph-neural cellular rule reorganizes node states into a cluster-revealing relational representation. Clusters therefore emerge from collective graph-state evolution rather than direct prediction of assignments.
6.1
Clustering as Learned Domain Formation
A useful interpretation of G-NAC is that clusters correspond to domains of an evolving cellular system. The graph defines the interaction topology, while the learned transition rule determines how information propagates across it. The unsupervised objective encourages local coherence while penalizing representational collapse, allowing distinct regions of the graph to emerge through the recurrent dynamics. 32
The partition is consequently a readout of these dynamics rather than their direct optimization target. This perspective also explains why the useful information need not reside in a globally stationary latent coordinate system: cluster structure can instead be expressed through relationships between cells.
6.2
Relational Rank Stability Rather Than Coordinate Convergence
Successful G-NAC inference does not necessarily correspond to a fixed-point attractor. In several experiments, domain coordinates continued to evolve after their cluster-relevant relational ordering changed much more slowly. Coordinatewise convergence is therefore not required by the present inference procedure. This behavior motivates both the empirical rank-stability criterion and the final edge-rank affinity. The former detects high rank correlation between successive edge-distance configurations, while the latter constructs the partitioning affinity from their ordinal relationships. The threshold ρ ≥ 0.95 is an empirical stopping rule rather than a convergence certificate or guarantee of future partition stability. At fixed edge support and tie convention, the rank affinity is invariant to strictly increasing transformations of edge distances. Changes in latent scale therefore do not affect the readout when edge ordering is preserved, providing a readout compatible with relational rather than coordinate convergence.
6.3
The Role of the Initial Graph
G-NAC cannot recover arbitrary structure absent from its interaction graph. Sparse graphs may preserve locally correct relationships while fragmenting manifolds, whereas denser graphs can restore connectivity while introducing crosscluster shortcuts. Consequently, strong local edge discrimination does not imply that the fixed graph contains sufficient global information to recover the desired partition. G-NAC presently transforms states and learned relations on a fixed topology rather than rewiring that topology. Its natural operating regime is therefore a graph with meaningful local connectivity but sufficient ambiguity for relational refinement to be useful. In this sense, G-NAC is better viewed as learned graph re-embedding or refinement than as a general solution to graph construction.
6.4
Transferability of the Cellular Rule
Sparse-to-full transfer suggests that the learned dynamics are not intrinsically tied to the graph realization used for optimization. Under matched synthetic generating conditions, sufficiently sampled source graphs produced frozen rules that transferred to substantially larger independent graphs with little additional loss relative to target-scale training. This behavior is consistent with learning a shared local rule rather than node-specific parameters. Locally normalized geometric inputs also changed 33
substantially less across sampling densities than raw neighbor distances, providing one plausible mechanism for scale transfer. Moreover, some sparse-source rules performed substantially better after deployment to densely sampled targets than on their own source graphs, suggesting partial separation between the quality of a learned rule and the finite graph substrate on which it is expressed. Whether these properties extend beyond matched generating processes remains open.
6.5
Robustness and Stability
The corruption experiments distinguish incomplete from incorrect local topology. Deletion of up to 50% of directed neighbor slots before union symmetrization produced no statistically detectable aggregate loss under retraining, whereas rewiring those slots to non-neighbors caused substantial degradation. Because the shared-support spectral control was also insensitive to deletion, this robustness is better attributed to redundancy of the neighborhood substrate than to unique error correction by the recurrent dynamics. These experiments characterize robustness of the fitting procedure, since G-NAC was retrained after each corruption. They indicate that the method tolerates substantial loss of local relationships when those remaining are meaningful but is sensitive to false connectivity. Gaussian feature noise provides an intermediate case because it simultaneously perturbs observations and their induced graph geometry. G-NAC also showed relatively low stochastic variability across the benchmark. Difficult cases nevertheless produced distinct outcomes, consistent with the possibility of multiple dynamical regimes under different initial conditions. Characterizing these regimes more formally remains future work.
6.6
Computational Considerations
G-NAC is substantially more expensive than conventional clustering because its recurrent transition rule must be optimized before partitioning. Its computational motivation therefore lies in problems where relational structure justifies this additional cost rather than in replacing inexpensive methods on simple cluster geometries. For fixed graph degree and model configuration, however, the controlled experiment showed approximately linear empirical scaling in training time and GPU memory over 5,000–100,000 nodes. Graph construction and spectral readout remain separate costs whose scaling can become important beyond this range. Sparse rule learning offers a complementary reduction in training cost. On noisy blobs, 5,000-node source training retained independent-target ARI within 0.009 of 100,000-node source training while requiring approximately 21.6× less training time and 19–20× less peak allocated GPU memory. This does not reduce deployment-graph construction, recurrent inference, or final readout costs,
34
but suggests that gradient-based rule learning can be decoupled from deployment scale under suitable conditions.
6.7
Limitations and Future Directions
The experiments evaluate the complete G-NAC pipeline more directly than they isolate its individual mechanisms. Ordinary spectral clustering does not simultaneously control graph support, affinity construction, and representation, while graph-only rank affinities and untrained recurrent controls were already strong on the synthetic transfer families. The benchmark therefore establishes performance of the complete procedure rather than attributing its differences specifically to recurrence, learned conductance, or individual objective terms. Matched mechanism ablations remain an important next step. G-NAC also depends fundamentally on initial graph quality. Missing relationships and cross-cluster shortcuts can constrain what fixed- topology dynamics can recover, motivating future work on jointly learned or adaptive topology. In addition, K is currently required by the final readout despite being absent from training and recurrent inference; estimating the number of emergent domains directly from the evolved relational state would provide a fully unsupervised readout. The demonstrated rule transfer is limited to independent graphs sharing the same synthetic generating parameters. It establishes inductive graph transfer within a generating process, not transfer across distribution shift, unrelated datasets, or application domains. Testing reuse across changes in feature distributions and graph geometry is therefore necessary. Finally, the current formulation uses a single graph scale and level of cellular organization. Hierarchical graph-neural cellular systems, in which coarse and fine domains interact, provide a natural extension for multiscale structured data.
7
Conclusion
We introduced G-NAC as an unsupervised clustering formulation in which a shared graph-neural cellular transition rule reorganizes observations before a final partition is read from learned graph-edge relationships. The method treats clustering as emergent domain formation on a fixed neighborhood graph rather than direct prediction of cluster labels. On the 73-task benchmark, the complete pipeline was competitive with the strongest evaluated baseline, while corruption, scalability, and transfer experiments characterized the graph-quality assumptions and computational conditions under which the approach remains useful. The results also delimit the present claims. G-NAC depends on meaningful local graph structure, requires K at the final readout, and is more computationally expensive than conventional clustering. Strong graph-only and untrained controls on the synthetic transfer tasks, together with componentresolved benchmark cases, mean that the observed performance cannot be at-
35
tributed uniformly to learned recurrence alone. The next steps are therefore matched mechanism ablations, adaptive or learned graph construction, automatic estimation of emergent domain count, and tests of cellular-rule transfer beyond matched generating processes.
Code and Data Availability A public implementation of G-NAC and the experimental scripts supporting this study are being prepared for release. Until that release, materials needed to reproduce the reported experiments are available from the authors upon reasonable request. The primary benchmark datasets are drawn from the publicly available, versioned Clustering Benchmarks suite cited in the text.
References Adrien Bardes, Jean Ponce, and Yann LeCun. VICReg: Variance-invariancecovariance regularization for self-supervised learning. In International Conference on Learning Representations, 2022. Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 7:2399–2434, 2006. Deyu Bo, Xiao Wang, Chuan Shi, Meiqi Zhu, Emiao Lu, and Peng Cui. Structural deep clustering network. In Proceedings of The Web Conference 2020, pages 1400–1410. Association for Computing Machinery, 2020. doi: 10.1145/3366423.3380214. Javier de Lope and Darı́o Maravall. Data clustering using a linear cellular automata-based algorithm. Neurocomputing, 114:86–91, 2013. doi: 10.1016/ j.neucom.2012.08.043. Arthur P. Dempster, Nan M. Laird, and Donald B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B (Methodological), 39(1):1–22, 1977. doi: 10.1111/j. 2517-6161.1977.tb01600.x. Burak Dündar and Emin Erkan Korkmaz. Data clustering with stochastic cellular automata. Intelligent Data Analysis, 22(4):735–750, 2018. doi: 10.3233/IDA-173488. Daniel Dwyer and Maxwell M. Omwenga. Training topology with graph neural cellular automata. In 2023 IEEE International Conference on Electro/Information Technology (eIT), pages 424–429, 2023. doi: 10.1109/ EIT57321.2023.10187381.
36
Mehdi Esnaashari and Mohammad Reza Meybodi. Irregular cellular learning automata and its application to clustering in sensor networks. In Proceedings of the 15th Conference on Electrical Engineering (ICEE), pages 14–28, Tehran, Iran, 2007. Telecommunication Research Center. Pasi Fränti and Sami Sieranoja. K-means properties on six clustering benchmark datasets. Applied Intelligence, 48(12):4743–4759, 2018. doi: 10.1007/ s10489-018-1238-7. Bernd Fritzke. A growing neural gas network learns topologies. In Advances in Neural Information Processing Systems 7, pages 625–632. MIT Press, 1995. Marek Gagolewski. A framework for benchmarking clustering algorithms. SoftwareX, 20:101270, 2022. doi: 10.1016/j.softx.2022.101270. Marek Gagolewski, Maciej Bartoszuk, and Anna Cena. Genie: A new, fast, and outlier-resistant hierarchical clustering algorithm. Information Sciences, 363: 8–23, 2016. doi: 10.1016/j.ins.2016.05.003. Marek Gagolewski et al. A benchmark suite for clustering algorithms: Version 1.1.0, 2022. Gennaro Gala, Daniele Grattarola, and Erik Quaeghebeur. E(n)-equivariant graph neural cellular automata. Transactions on Machine Learning Research, 2024(04), 2024. Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Learning graph cellular automata. Advances in Neural Information Processing Systems, 34:20983– 20994, 2021. Daniel Graves and Witold Pedrycz. Kernel-based fuzzy clustering and fuzzy clustering: A comparative experimental study. Fuzzy Sets and Systems, 161: 522–543, 2010. doi: 10.1016/j.fss.2009.10.021. Xifeng Guo, Long Gao, Xinwang Liu, and Jianping Yin. Improved deep embedded clustering with local structure preservation. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, pages 1753–1759, 2017. doi: 10.24963/ijcai.2017/243. Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of Classification, 2:193–218, 1985. doi: 10.1007/BF01908075. Anil K. Jain. Data clustering: 50 years beyond K-means. Pattern Recognition Letters, 31(8):651–666, 2010. doi: 10.1016/j.patrec.2009.09.011. Teuvo Kohonen. Self-organized formation of topologically correct feature maps. Biological Cybernetics, 43:59–69, 1982. doi: 10.1007/BF00337288.
37
James B. MacQueen. Some methods for classification and analysis of multivariate observations. In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, volume 1, pages 281–297. University of California Press, 1967. Thomas Martinetz and Klaus Schulten. A “neural-gas” network learns topologies. In Artificial Neural Networks, pages 397–402. Elsevier, 1991. Nicolò Navarin, Paolo Frazzetto, Luca Pasa, Pietro Verzelli, Filippo Visentin, Alessandro Sperduti, and Cesare Alippi. Physics-informed graph neural cellular automata: An application to compartmental modelling. In 2024 International Joint Conference on Neural Networks (IJCNN), pages 1–9, 2024. doi: 10.1109/IJCNN60899.2024.10650578. Uri Shaham, Kelly Stanton, Henry Li, Boaz Nadler, Ronen Basri, and Yuval Kluger. Spectralnet: Spectral clustering using deep neural networks. In International Conference on Learning Representations, 2018. Dianxun Shuai, Yumin Dong, and Qing Shuai. A new data clustering approach: Generalized cellular automata. Information Systems, 32(7):968–977, 2007. doi: 10.1016/j.is.2006.10.002. Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Müller. Graph clustering with graph neural networks. Journal of Machine Learning Research, 24(127):1–21, 2023. Alfred Ultsch and Jörn Lötsch. The fundamental clustering and projection suite (fcps): A dataset collection to test the performance of clustering and data projection algorithms. Data, 5(1):13, 2020. doi: 10.3390/data5010013. Nguyen Xuan Vinh, Julien Epps, and James Bailey. Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. Journal of Machine Learning Research, 11(95):2837–2854, 2010. Ulrike von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395–416, 2007. Chun Wang, Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, and Chengqi Zhang. Attributed graph clustering: A deep attentional embedding approach. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, pages 3670–3676, 2019. doi: 10.24963/ijcai.2019/509. Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through alignment and uniformity on the hypersphere. In Proceedings of the 37th International Conference on Machine Learning, 2020. Jr. Ward, Joe H. Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 58(301):236–244, 1963. doi: 10.1080/01621459.1963.10500845. 38
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In Proceedings of the 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 478–487. PMLR, 2016. Xiucai Ye and Tetsuya Sakurai. Robust similarity measure for spectral clustering based on shared neighbors. ETRI Journal, 38(3):540–550, 2016. doi: 10.4218/ etrij.16.0115.0517. Tian Zhang, Raghu Ramakrishnan, and Miron Livny. BIRCH: An efficient data clustering method for very large databases. In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, pages 103–114, 1996. doi: 10.1145/233269.233324. Yuxin Zhao, Wen Jiang, Shenghong Li, Yinghua Ma, Guiyang Su, and Xiang Lin. A cellular learning automata based algorithm for detecting community structure in complex networks. Neurocomputing, 151:1216–1226, 2015. doi: 10.1016/j.neucom.2014.04.087. Chunhui Zhu, Fang Wen, and Jian Sun. A rank-order distance based clustering algorithm for face tagging. In 2011 IEEE Conference on Computer Vision and Pattern Recognition, pages 481–488. IEEE, 2011. doi: 10.1109/CVPR. 2011.5995680. Xiaojin Zhu, Zoubin Ghahramani, and John Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International Conference on Machine Learning, 2003.
39