NeRD: Neural Replicator Dynamics for Maximum Clique Extraction

Neural approaches to the Maximum Clique Problem (MCP) have made substantial progress, yet they share two persistent limitations: they depend on non-differentiable decoders to extract discrete solutions from soft node scores, and they offer no guarantee that the returned set is even a valid clique. We propose NeRD (Neural Replicator Dynamics), an end-to-end differentiable model that resolves both issues by combining a graph neural network with replicator dynamics on the probability simplex. The GNN maps an input graph to a distribution over nodes that concentrates mass where the clique is likely to be, providing a warm start that steers the dynamics away from suboptimal fixed points; the dynamics then refine this initialisation to an asymptotically stable fixed point whose support is, by construction, a maximal clique—no post-hoc decoder required. Training is driven by the Motzkin–Straus quadratic objective, which is differentiable through both components and yields a free lower bound on the clique number as a by-product. We further show that the GNN's learned representations act as a symmetry-breaking mechanism that resolves the historical Achilles' heel of replicator dynamics: its sensitivity to initialisation on hard, structured instances where the uniform starting point consistently falls into small local maxima. Experiments on eight real-world graph benchmarks and eight DIMACS-inspired synthetic families confirm that the two components are strictly complementary: NeRD achieves state-of-the-art clique-number prediction across the majority of benchmarks, consistently outperforming both GNN-only baselines and standalone replicator dynamics, with the largest gains precisely on the families where existing neural methods struggle most.