- 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
-
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.
-
The method does not always produce a valid clique. Consider the four-node cycle . 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
-
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 , and under what conditions does the feasibility guarantee hold?
-
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 . Could you explain how you computed these metrics?
3 comments
Thank you for the clarifications. The revised statistics resolve my original arithmetic concern, but I still have two concerns:
- 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.
- 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 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 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
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 † 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 † entries of these three columns. Every entry without † 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 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). 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. 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.