- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies how learning dependencies from objective evaluations can speed up evolutionary search for graph ordering. It shows that ordinary jump-based randomized local search (RLS) can require weakly exponential expected time on a simple double-star DAG. The authors adapt the Non-Monotonicity Check to permutations to detect directed dependencies without false positives, and introduce DSM-jump to coordinate vertex moves using these dependencies. They prove that the resulting DSM-RLS finds a topological ordering of any DAG in polynomial expected time, without first recovering the entire graph. The key argument is that search can progress either by improving the objective or by revealing a new dependency. Experiments on subdivided trees and random directed graphs support the operator’s effectiveness and provide preliminary evidence of benefits on cyclic feedback arc set instances.
Critical strengths
- The paper proves a weakly exponential expected runtime for ordinary RLS on a simple DAG, while establishing polynomial expected runtime for DSM-RLS on any DAG. This provides an interpretable example of how exploiting dependencies can fundamentally change search efficiency.
- The analysis shows that progress can occur through either objective improvement or discovery of a new dependency, explaining how the proposed operator can succeed with incomplete structural knowledge.
Critical weaknesses
-
In Section 4.1 and Appendix C, the authors could explain more clearly how their detector differs from existing adjacent-swap probing. Under the same query model, the adjacent-swap probing procedure in Przewozniczek et al. (2021a) can recover the full DAG in objective evaluations if it also records the sign of each objective change. The authors should clarify what the detector itself adds, separately from DSM-jump and the runtime analysis.
-
Tables 3 and 5 report an initial fill ratio of 1.000 for all subdivided settings , meaning that the algorithm already knows all dependencies when search begins. On these instances, the experiments support DSM-guided mutation, but they do not show whether later dependency updates improve search. The authors could test this by comparing fixed and updated DSMs on instances where the initial DSM misses some dependencies. This would clarify the practical value of continued learning; the theoretical runtime guarantee does not depend on this comparison.
Questions for authors
- Would replacing NMC with adjacent-swap probing that records the sign of objective changes preserve the polynomial-time guarantee? If not, which step of the proof relies specifically on NMC?
- For the instances with incomplete initial DSMs, does freezing the DSM after initialization change the success rate or runtime compared with updating it during search?
We thank the reviewer for pointing out this alternative probing procedure. We agree that adjacent-swap probing can be modified to recover the adjacency matrix of the underlying graph in O(n2) fitness evaluations by recording the sign of each objective change. Then the sign of the fitness difference will reveal whether an edge between these vertices exists. There are, however, two important differences that motivate our detector.
First, the original linkage detection mechanism of Przewozniczek et al. (2021a) is not directly suitable for FAS and related linear ordering problems. As shown in Lemma C.1, it can detect linkage between vertices that are not connected by an edge in the underlying graph. Thus, simply adopting their original mechanism would not provide the structural information required by our mutation operator. There are several possible ways to address this issue. We chose to adapt the NMC mechanism, which is a state-of-the-art detector in pseudo-Boolean optimization and therefore provides a promising starting point for linkage learning in permutation spaces. Our results demonstrate that this adaptation successfully identifies useful structural dependencies and can be exploited to obtain provable performance improvements on FAS.
Second, our objective is not to develop a detector specifically tailored to reconstructing the adjacency matrix of a graph. Rather, we aim to develop effective linkage learning mechanisms for permutation spaces that can serve as building blocks for evolutionary algorithms across a broader range of problems. From this perspective, a problem-specific probing procedure that directly tests whether an edge exists is not necessarily preferable, even if it requires fewer fitness evaluations on this particular problem. We consider the development and analysis of a more general linkage learning mechanism a worthwhile objective in its own right.
Regarding your second question, we have not yet conducted a systematic comparison between freezing the DSM after initialization and continuing to update it during the search. On the small instances considered, with k=0 and incomplete initial DSMs, plain RLS consistently finds the optimum quickly. Consequently, DSM-RLS also finds the optimum quickly in these cases, even with an incomplete initial DSM, since it behaves like RLS when no linkage information is available. However, these results do not allow us to draw conclusions about the relative success rates or runtimes of the two DSM strategies on larger or more challenging instances. A systematic investigation would therefore be needed to answer this question reliably. We thank the reviewer for this valuable suggestion and leave this comparison to future work.
As a final remark to the second question, you may find the new evaluation of an adapted DSM-RLS of interest, which we conducted to answer a question of reviewer QZ2c. It uses insights of Lemma 4.2 and Theorem 4.3 to drop the number of fitness evaluations per generation from order n2 to constant and still maintains the theoretical guarantee of Theorem 4.3. It thereby only performs a single NMC per iteration and still computes a topological ordering within O(n2m) generations and fitness evaluations. Analogous plots to the evaluation plots of Figure 4 are uploaded as supplementary material and will be incorporated to the final version together with a corresponding corollary and discussion. The evaluation shows an immense speed up and the algorithm reliably finds the optimum both on trees and cyclic instances.