acceptodds
Under review as a conference paper at ICLR 2027

NeRD: Neural Replicator Dynamics for Maximum Clique Extraction

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Maximum Clique, Combinatorial Optimization, Neural Combinatorial Optimization, Graph Neural Networks

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_9CsCOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

NeRD combines a graph neural network with replicator dynamics to solve the maximum clique problem. The GNN predicts an initial distribution over vertices, which regularized replicator dynamics then refines. The method extracts a discrete solution by thresholding the final distribution. Training uses a short unrolling of the dynamics, a continuous optimization objective, and supervision from ground-truth clique numbers; inference runs the dynamics for substantially more steps. The authors evaluate the method on eight real-world datasets and eight synthetic graph families, reporting clique-number estimation, solution validity, and ablation results. The central contribution is learning an initialization for a classical optimization procedure.

Critical strengths

The method gives learning and optimization clear, complementary roles. The GNN learns where to initialize the search, while replicator dynamics refines the solution using a problem-specific objective. This is a simple, well-motivated design whose contribution is easy to understand. Short unrolling during training and longer refinement at inference also offer a reasonable way to control training costs. The comparisons against uniform initialization directly examine the value of the learned component and provide useful evidence for this research direction.

Critical weaknesses
  1. The main comparisons may use different graphs. Table A.1 describes the original molecular graphs, but the cited baseline results come from modular product graphs. For MUTAG, the mean clique numbers are 2.000 and 11.203, respectively. Appendix A.4 nevertheless says that both use the same data. The authors need to explain this difference before these comparisons can support their claims.

  2. The method does not always produce a valid clique. Consider the four-node cycle C4C_4. All nodes have the same structural features, so the GNN gives them equal weights. Replicator dynamics keep these weights unchanged. The method then selects all four nodes that do not form a clique, and more iterations do not help. The theory guarantees validity at asymptotically stable fixed points, but it does not show that the method always reaches one.

Questions for authors
  1. Please address the two concerns in Critical Weaknesses. Did NeRD and the cited baselines use the same test graphs? How does the implementation handle the uniform fixed point on C4C_4, and under what conditions does the feasibility guarantee hold?

  2. Table B.2 reports 91.2% exact accuracy and a mean output size of 1.58 on MUTAG, where every graph has clique number 2. If both metrics use the same extracted sets, the mean size should be at least 2×0.912=1.8242\times0.912=1.824. Could you explain how you computed these metrics?

3 comments
AuthorsOpenReview ↗

Response to Reviewer 9CsC

We thank the reviewer for a precise review. It led us to an error in the description of the cited baselines and to an inconsistent row in Table B.2, and both are corrected. We answer the three points in order.

Graphs used by the cited baselines. We thank the reviewer for catching this, and the reviewer is right. The entries marked †\dagger in the AIDS, PTC-MM, and MUTAG columns of Table 1 are reproduced from Roy et al. (2025), who evaluated on the modular-product versions of these datasets, whereas NeRD and the baselines that we ran ourselves were evaluated on the raw graphs. We have updated Appendix A.4 to state this difference and to say that NeRD can be compared directly with the †\dagger entries of these three columns. Every entry without †\dagger was run by us on the same graphs, splits, and ground-truth clique numbers as NeRD, and the comparison between replicator dynamics from the barycentre and the learned seed rests on these entries alone.

Validity on the four-cycle. We agree with the analysis. The four-cycle is vertex-transitive, so all vertices have the same structural features and the encoder returns the barycentre. The barycentre is a fixed point of the replicator update on this graph, and the support then contains all four vertices. It is a fixed point but not an asymptotically stable one. With α>0\alpha>0 it is not a local maximiser of the regularised objective, and a generic perturbation of the seed moves the trajectory to an edge.

The guarantee holds under the condition stated in Section 3, Section 4.1, and Appendix B, namely when the trajectory converges to an asymptotically stable fixed point of the dynamics with α∈(0,1)\alpha\in(0,1). The paper does not claim that every trajectory does so. Appendix A.2 describes exactly the case raised by the reviewer, since on a vertex-transitive graph any message-passing encoder returns the barycentre, and Appendix A.3 discusses the case α=0\alpha=0. The implementation does not treat this case in a special way, and such a graph counts as a failure in Table B.1. Table B.1 measures how often the condition fails in practice, which is on 0.2% of the real-world test graphs and on 0.5% of the synthetic ones.

The MUTAG row of Table B.2. The reviewer is right. With clique number 2 on every graph and an exact accuracy of 91.2%, the mean size cannot be below 1.824, so the size entries of this row were wrong. The mean size, its standard deviation, and the optimality gap of the MUTAG row have been updated in the revision.

Thank you for the clarifications. The revised statistics resolve my original arithmetic concern, but I still have two concerns:

  1. Table 1 continues to rank results that Appendix A.4 says are not directly comparable. The rankings and related performance claims should be revised to reflect this.
  2. Given the counterexample, the feasibility claims need to make the convergence condition explicit. Could you clarify whether the remaining failures are due to insufficient iterations or convergence to fixed points whose supports are not cliques?

For now, I am keeping my current rating.

We thank the reviewer for the follow-up and are glad that the arithmetic concern is resolved.

1. Ranking in Table 1. The entries marked †\dagger are reported as published by Roy et al. (2025), and Appendix A.4 states how they were obtained. The ranking is not affected by this. If the AIDS, PTC-MM, and MUTAG columns are ranked only over the methods evaluated on the same graphs, NeRD is still first in all three, followed by replicator dynamics from the barycentre. The performance claims of Section 5.1 therefore hold under either reading.

2. Convergence condition. The condition is stated in Section 3, Section 4.1, and Appendix B. The support is a maximal clique when the dynamics with α∈(0,1)\alpha \in (0,1) converge to an asymptotically stable fixed point, and Section 4.1 notes that the correspondence is asymptotic. Fixed points that are not asymptotically stable, such as the barycentre of

Reviewer_S6TAOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper tackles and interesting and relevant graph theory problem: maximum clique finding. The authors provide NeRD, with a simple but plausible idea, trying to add a better "neural" start of computation (using a GNN) to a more "classical" clique algorithm (replicator dynamics) trying to show its potential for improving the results. They provide 7 local node features to a GNN encoder that outputs a vector h of node probabilities that is then used with (linear or exponential) replicator dynamics (RD). The final output is not just a prediction of the size of the maximum clique, but also the nodes that form that clique.

The main contributions claimed are that by combining the GNN with RD they tackle the main problems when using on of these methods in isolation: GNNs do not always provide even a feasible clique and RD lack a principled starting point. The empirical results show that the tested GNNs area always a lot worse than RD and NeRD, hat NeRD always improved against RD on the real networks tested, and that on harder synthetic networks (inspired by the classical DIMACS) it is better on the majority of networks tested.

They also provide an anonymous github code repository and thorough appendix section, including details on the networks used, extraction quality, contribution of the initialization, computational cost and some ablation studies.

Critical strengths
  • A simple but elegant coupling of two different ideas that help each other and that is naturally "feasible" (i.e., it always provides a clique, even if it not the maximum one) that seems to improve the results on almost every benchmark used and a reminder for the neural community that sometimes classical methods (RD and its connection with Motzkin–Straus) can be much better that they current state-of-the-art neural "competitors" (suggesting also a new angle on the efforts to improve results on this problem)

  • Thorough appendix section that provides details on the mains results and informs the reader about the choices made, complemented with an anonymous github that ensures reproducibility

Critical weaknesses
  • One of the main claims (that the GNN encoder solves the initialization problem of RD) is in my view very weakly tested as a direct idea by itself (when it could/should be the main aspect being tested here besides overall MSE results); furthermore the authors claim that "The GNN supplies the symmetry-breaking initialisation RD lacks on highly symmetric instances" seems to always be contradicted by their own results, as the gain is smaller on highly symmetric instances (see table D.1); the authors also do not test any other starting points for RD (other than the barycentre)

  • The empirical evidence provided has some suspicious aspects. For instance, there seesm to be repeated number on the tables (see questions to the authors) and the single run on the main table that is always better than the average of 5 runs of random seeds.

Questions for authors
  • Can you verify if your tables have wrong numbers, perhaps with copy+paste that was forgotten? In particular, the main result tables 1 and 2 have the same exact first 4 numbers (up to 3 decimal places) on the 2nd column: COLLAB and RB start with 33.093, 27.771, 35.347 and 30.235.

  • Can you provide an explanation on why table C.1 shows that the single run used for the main tables is always better, in all 16 benchmarks, than the average of 5 seeds. Shouldn't it be, by definition of average, be worse in at least some of the benchmarks?

  • Can you explain why the gain against RD starting with the barycentre is way smaller on the harder instance and precisely the ones you stated your method could improve? If the used encoder struggles with the same problems and outputs a seed that "stays close to the barycentre", does not this contradict what you state on the abstract and introduction as a main claim? ("We further show that the GNN’s learned representations act as a symmetry-breaking mechanism (...) with the largest gains precisely on the families where existing neural methods struggle most"

  • The evidence for selecting the 7 local structural node properties of section 4.1 is in my opinion a bit weak and lacks more convincing arguments or systematic choice. Did you do some king of ablation study here to understand how each of the 7 features is contributing? Did you try any other features? (given the main goal of providing a good start, this step is for me crucial and is very undertested and almost seen as "passing thought")

  • Did you try any other starting points other than 7 features given to a GNN or the "simple" barycentre? For instance, you state "The encoder plays the role that annealing and external restarts play in the classical literature" but as far as I understood here you did not use for instance annealing and the external restarts or any non-learned initialization?

  • Could you provide some form of measurement (e.g. overlap) on how close to the actual maximum clique "basin" the GNN and the barycentre are?

  • To better assess computational cost, can you provide the time it took for the ground-truth computation using gurobi? And total time for your proposed method? Did you compare the time on the same instance with any (classical, non-learned) heuristic approaches?

1 comment
AuthorsOpenReview ↗

Response to Reviewer S6TA

We thank the reviewer for the careful reading of the paper and of its appendix. The review caught an error in our tables, which we have corrected, and raises several thoughtful questions that we answer in order below.

Repeated numbers in Tables 1 and 2. The reviewer is right, and the error is ours. The GNN-only block of Table 2 was written starting from Table 1, leaving COLLAB values in the RB column—and, as we found during auditing, in C_random across the same four rows. Both columns now carry the exact values from our logs, with the eight corrected cells marked in yellow. All other rows were verified and are unchanged, as is their role in showing that an encoder trained without dynamics sits far behind the bottom three rows of each table.

Single run against the mean of five seeds. The reviewer's statistical intuition applies to a random run, whereas the main tables report the specific run on which the configuration of Table A.4 was selected on the validation split, so its hyperparameters are tuned to that seed. Table C.1 reuses this exact configuration across five fresh seeds without retuning. As expected, the selected run sits below the five-seed mean on all sixteen benchmarks, yet remains within one seed standard deviation on every dataset. Appendix C.1 reports this openly, notes that on IMDB and ENZYMES the margin over MXNET lies within one seed standard deviation (so we claim no advantage there), and confirms that NeRD's baseline ranking holds under the more conservative five-seed mean.

Smaller gain on the symmetric families. Agreed: the gain over replicator dynamics from the barycentre is ~10% on hamming-style and keller-style, versus 35–39% on RB, dsjc-style, and brock-style, and 36–96% on real-world graphs. As explained in Section 5.1, Appendix A.2, and Appendix D, every vertex in a vertex-transitive graph shares identical structural features and 1-WL colour, causing a message-passing encoder to return the barycentre; perturbed Hamming and Keller graphs sit close to this regime, which we note as a limitation in the conclusion. The abstract's reference to the largest gains targets camouflaged and CSP-style families where neural solvers struggle and our synthetic gains peak. While symmetry breaking yields ~10% when subtle cues exist (as in Figure 3), we agree the introduction's mention of Hamming and Keller graphs reads stronger than Table D.1 warrants, and we will align its wording with Section 5.1.

Whether the claim on initialisation is tested directly. Table D.1 is the direct controlled test: it compares NeRD against replicator dynamics from the barycentre under the identical payoff matrix, update rule, and step count, isolating the starting point. Table B.1 offers a complementary view on the synthetic suite, where valid clique recovery rises from 94.8% from the barycentre to 99.5% from the learned seed.

Choice of the seven structural features. We use the exact same seven label-free structural features across all experiments and baselines for fair comparison (Section 4.1): two capture scale, three local density, and two the neighbourhood homogeneity separating a clique's interior from its boundary, all computed once per graph. Tables 1, 2, and the four backbones in Table E.4 evaluate the encoder as a whole; a per-feature ablation would be a valuable addition.

Other starting points. The barycentre is the standard deterministic, vertex-neutral reference start in classical replicator dynamics for maximum clique. Our encoder provides a single learned start and trajectory per graph—avoiding the inference multiplier of random restarts and external annealing schedules—so comparing against the barycentre cleanly isolates the value of that learned start. All other baselines follow standard neural combinatorial protocols and benchmarks for fair comparison across the field.

How close the seed is to the basin of the maximum clique. Table F.1 offers an indirect proxy via the t=0t=0 Motzkin–Straus bound, which has the closed form 1/(1−2∣E∣/n2)1/(1-2|E|/n^2) at the barycentre. With the edge counts of Table A.2, the barycentre gives ~2.6 on dsjc-style, 4.7 on brock-style, and 9.9 on gen-style, versus 3.82, 6.45, and 13.56 from the learned seed—confirming that the seed starts substantially higher on the objective. We agree direct basin overlap would be a sharper diagnostic.

Computational cost. Per Table G.3, training takes 6–50 seconds per epoch and inference takes 5–76 milliseconds per graph, covering both the encoder forward pass and all replicator steps. Gurobi is run strictly offline without a time limit to generate ground-truth labels and plays no role in training or inference. Because replicator iterations dominate inference time (Appendix G.3), NeRD and barycentre-started replicator dynamics have essentially the same inference cost.

Reviewer_JS7SOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes to combine graph neural networks and replicator dynamics to solve combinatorial optimization problems by leveraging a differentiable quadratic objective.

Critical strengths
  1. The integration of replicator dynamics into GNNs is novel and interesting
  2. The replicator dynamics provide a powerful mechanism by which to determine initial values and restarts
Critical weaknesses

This paper claims to resolve the issue that other GNNs have in that they may not return a valid clique. However, I do not see evidence of that. Indeed, in the experiments, what is reported is the MSE between the predicted clique number and the true clique number, which could correspond to a support set for an invalid clique. The proposed approach predicts that support set as a probability distribution, so I don't see why it should be guaranteed to lead to a valid maximal clique, through invalid cliques can still give you good predicted clique numbers.

Questions for authors

Why do you use DIMACS-inspired benchmarks as opposed to applying your methods to the actual DIMACS graphs?

1 comment
AuthorsOpenReview ↗

Response to Reviewer JS7S

We thank the reviewer for the positive assessment of the idea. The weakness and the question raised in the review are both addressed in the submitted paper, and we point to the exact places below.

Evidence that the returned set is a valid clique. This evidence is in Appendix B, and the main text points to it from Section 4.1 and from Section 5. Table B.1 takes the set that NeRD actually returns and checks whether it is a clique of the input graph and whether it is maximal. The returned set is a valid clique on 99.8% of the test graphs of the real-world suite and on 99.5% of the synthetic suite, and every valid set is also maximal. The same table reports the two reference points. A GNN whose scores are thresholded without the dynamics returns a valid clique on 14.2% and 1.1% of the graphs, and replicator dynamics from the barycentre on 98.7% and 94.8%. Table B.2 adds the exact accuracy and the optimality gap, again measured on the returned set. The claim is therefore measured on the extracted sets and is not inferred from the MSE.

Whether a good MSE can come from an invalid set. In principle it can, and this is why we report Table B.1 next to the MSE. The MSE on the clique number is the standard metric of this line of work, and we keep it so that NeRD can be compared with the published methods on equal terms. In NeRD the predicted clique number is read from the final iterate, and at a clique characteristic vector it equals the size of the returned support (Appendix A.4). Together with Table B.1, this means that on more than 99% of the test graphs the number that enters the MSE is the size of a valid maximal clique.

Why the output is a maximal clique. The output of NeRD is not the distribution produced by the GNN. That distribution is only the starting point of the replicator dynamics, and the output is the point to which the dynamics converge. By the classical results of Pelillo (1999) and Bomze et al. (1999), the asymptotically stable fixed points of the replicator dynamics on A+αI\mathbf{A}+\alpha\mathbf{I} are exactly the barycentric indicators of the maximal cliques of the graph. Such a point puts equal mass on the vertices of one maximal clique and zero mass everywhere else, so its support is that clique. This is what separates NeRD from thresholding a GNN score, and the top row of Figure 3 shows the difference on one instance. The result is asymptotic, as we state in Section 4.1 and in Appendix B. At a finite number of steps we report the empirical rate, and the failures that remain, below 1% on both suites, are graphs on which the iterate has not converged.

DIMACS-inspired families instead of the DIMACS graphs. The paragraph "Relation to DIMACS" in Appendix A.2 states that none of the canonical instances is used and that the suffix -style in the names marks this. The reason is that NeRD is a learned method. We follow the protocol of Roy et al. (2025), in which every dataset is split 60/20/20 into training, validation, and test, with exact clique numbers from Gurobi. The canonical DIMACS collection offers only a handful of graphs per family, three Keller graphs for example, which is not enough to train, validate, and test a model per family. The largest of them are also beyond what an exact solver certifies without a time limit. We therefore generate 1000 graphs per family with the construction of the corresponding DIMACS family, and we state in Appendix A.2 that our numbers must not be compared with published results on the instances of the same name.

We hope that these pointers resolve the concern, and we would be grateful if the reviewer could reconsider the score in their light.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.