acceptodds
Under review as a conference paper at ICLR 2027

Provable Speedups from Linkage Learning in Evolutionary Algorithms for Graph Optimisation

Abstract

Graph ordering problems, such as the NP-hard Feedback Arc Set (FAS) problem, are commonly attacked with evolutionary algorithms and greedy reinsertion heuristics. These methods search in permutation spaces and are guided solely by the objective value. As a result, they expose the immediate precedence constraints of the graph but leave transitive structure hidden. We show that this constitutes a genuine obstruction to efficient search. To this end, we show that even for a simple special case of FAS, namely to compute a topological ordering of a graph, an evolutionary algorithm (RLS) needs weakly exponential time. Building on linkage learning mechanisms developed for binary spaces, we transfer this machinery to permutation spaces and prove that it learns arcs of the underlying graph and never reports false ones. We then design a mutation operator that employs the learned arcs to identify sets of elements that are jumped together, thereby handling transitive structure implicitly. Equipping RLS with this operator, we show that learning and search reinforce each other: in every non-optimal step, the algorithm improves the fitness or enables the detection of a new arc with probability at least . Hence, the improved algorithm orders any DAG in expected polynomial time without having to recover the entire graph. This exponential speedup demonstrates the usefulness of the enhanced operator in settings with hidden transitive structure. Experiments on instances with progressively removed transitivity information confirm this gap and indicate that the same operator remains effective on cyclic FAS instances.

Primary area:
optimization
Keywords:
black-box optimization, combinatorial optimization, evolutionary algorithms, runtime analysis, theory, permutation spaces, feedback arc set, linkage learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_rcEsOpenReview ↗
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
  1. 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.
  2. 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
  1. 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 �0��0� 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.

  2. Tables 3 and 5 report an initial fill ratio of 1.000 for all subdivided settings (�1�)(�1�), 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
  1. 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?
  2. For the �0��0� instances with incomplete initial DSMs, does freezing the DSM after initialization change the success rate or runtime compared with updating it during search?
1 comment

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)O(n^2) 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=0k=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 n2n^2 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)O(n^2m) 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.

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

The paper studies evolutionary algorithms for topological ordering and shows that previously used jump-based and reinsertion operators can perform poorly. In particular, jump-based RLS can require exponential time to find a topological ordering even on a simple DAG when transitive information is not explicitly available.

To overcome this limitation, the authors use a Non-Monotonicity Check (NMC) method to infer arcs and incorporate the learned structure into a new mutation operator. The resulting algorithm, DSM-RLS, computes a topological ordering of any DAG in polynomial time, establishing an exponential worst-case separation from vanilla RLS.

Critical strengths

I find the questions interesting and the results are nontrival.

Critical weaknesses
  1. The scope of the theoretical results is somewhat limited. The main guarantees apply only to DAGs and do not extend to the general Feedback Arc Set (FAS) problem that motivates the study. It would strengthen the paper to clarify whether the proposed approach provides theoretical benefits beyond the acyclic setting.

  2. I also have reservations about the paper’s fit for ICLR. Its connection to the conference’s broader interests in learning and representation is not sufficiently clear. Given its emphasis on evolutionary algorithms and their runtime analysis, the paper seems more naturally suited to a venue such as GECCO.

Questions for authors

NA

1 comment

Regarding the scope of the theoretical results, we agree that extending our guarantees beyond DAGs would strengthen the paper. While the general Feedback Arc Set (FAS) problem is NP-hard, this does not preclude obtaining meaningful guarantees for finding solutions with desirable properties, even if global optimality cannot be guaranteed in polynomial time.

Upon revisiting our proofs in light of your comment, we noticed that our theoretical results can be extended to general, possibly cyclic, directed graphs with only moderate changes to Section 4 of the paper. In fact, most of the arguments in the proofs of Lemma 4.2 and Theorem 4.3 also apply in this more general setting. In particular, we are confident that we can show that, within the expected time bound established in Theorem 4.3, DSM-RLS computes an inclusion-wise minimal feedback arc set (FAS), represented by the back arcs of the resulting permutation. Such a FAS is a local optimum with respect to removing individual back arcs. The key observation is that, as established in our current proofs, with probability at least 1/n21/n^2, each relevant step either identifies new linkage or removes at least one back arc. The latter event remains possible whenever the current FAS is not inclusion-wise minimal. This would extend our theoretical guarantees beyond DAGs and provide a positive result for general FAS instances. Our current result for DAGs would then follow as a special case of this more general guarantee.

Regarding the fit for ICLR, we acknowledge that our work is rooted in evolutionary computation and that both our theoretical analysis and experiments focus on evolutionary algorithms. Nevertheless, we believe the paper connects to ICLR's broader interests in learning and representation. In particular, our work investigates how an evolutionary algorithm can learn structural dependencies in its search space and exploit this information to guide optimization. The linkage learning mechanism is central to our approach: it allows the algorithm to discover properties of the underlying problem that are not directly captured by the objective function. Our theoretical results demonstrate how incorporating this learned information can fundamentally improve the efficiency of the search process. We believe that the combination of learning structural information, adapting the search process based on the acquired knowledge, and theoretically analysing the resulting benefits provides a meaningful connection to ICLR's interests in learning and optimization.

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

The paper proposes a modified evolutionary approach to black-box graph ordering (no access to the graph itself, but only to a function that scores full permutations of the nodes). It starts by claiming that RLS requires in expectation weakly exponential time for topological sorting on some DAGs. The authors hypothesise that this is because of missing transitive dependencies that are not "captured" by the fitness function. They prove this by showing that when all transitive relations are present in a DAG, RLS takes polynomial optimisation time, i.e. number of fitness calls, (Theorem 3.1), while on a handcrafted adversarial example where transitive edges are missing it takes weakly exponential optimisation time (Theorem 3.2). Then, the main algorithmic contribution of the paper is adapting non-monotonicity check (NMC - a linkage learning approach learning direct ordering constraints via fitness queries) as an improvement of RLS in order to propagate corrective jumps to linked variables to close this complexity gap.

In more detail, the algorithm relies on a dependency structure matrix (DSM) that accumulates discovered explicit (reflected by the fitness function) dependencies between pairs of nodes. The NMC algorithm runs on each new accepted permutation, therefore dependencies can potentially be discovered until DSM recovers the adjacency matrix, although that is not required. Based on this iteratively refined matrix, the RLS random jump (the mutation operator) can be corrected by moving other nodes back or forward together with that node according to the DSM. For example, if node i has to jump forward over some nodes, then if any of those nodes had to be after i according to the DSM, then they are also moved after i in an order-preserving fashion (this is an intuitive simplification, the mechanism relies on DSM paths) if that doesn't worsen the fitness.

The main claim of the paper is that this NMC/DSM enriched version of the RLS mutation operator achieves expected polynomial number of generations and fitness queries for DAGs. It does that by implicitly exploiting hidden transitive structure during jump mutations. NMC is proven to never yield a false positive edge, and each step of the DSM-RLS algorithm either enables the finding of a new dependency (edge) or improves fitness with probability lower bounded at 1/n21/{n^2} (Theorem 4.3). The algorithm does not have to recover the full set of edges in the graph to converge.

Critical strengths

This is a sound theoretical paper with a clear motivation and a good execution. The paper builds on a hypothesis (proven through two theorems) to establish the problem. The suggested algorithm: DSM-RLS is then carefully analysed and its speed-up to polynomial number of queries and iterations is soundly proven.

Critical weaknesses

The paper starts by placing the work in the geeneral context of the NP-hard FAS and linear ordering problems. However, then the theoretical contribution is restricted to DAGs where the only challenge is hidden transitivityi, while the empirical evaluation on cyclic FAS instances is limited to small synthetic graphs. Although this is fairly communicated and accepted as a limitation by the authors, it is still the main weakness of the paper. This leaves a gap between the broader framing around NP-hard FAS and the scope of the results. To better understand where this algorithm's relevance to FAS, it could be empirically evaluated against standard ordering heuristics on non-syntethic instances.

Second, also acknowledged by the authors, the algorithm apparently suffers from an extreme evaluation overhead. O(n4m)O(n^4 m) evaulations could mean O(n6)O(n^6) evaluations, which means constructing the DSM dominates computation. The paper's own ablation experiments (Tables 3-5) confirm this. It is less important in a theoretical paper, but it impacts its application in practice.

Questions for authors

Authors suggest a heuristic for improving the number of fitness evaluations per permutation by performing a non-exhaustive NMC: restricting the verifications only to elements that changed positions. Does theorem 4.3 still work in that case?

1 comment

We thank the reviewer for these constructive comments. We believe that our theoretical results can be extended to general, possibly cyclic, directed graphs with only moderate changes to Section 4 of the paper. In fact, most of the arguments in the proofs of Lemma 4.2 and Theorem 4.3 also apply in this more general setting. In particular, we are confident that we can show that, within the expected time bound established in Theorem 4.3, DSM-RLS computes an inclusion-wise minimal feedback arc set (FAS), represented by the back arcs of the resulting permutation. Such a FAS is a local optimum with respect to removing individual back arcs. The key observation is that, as established in our current proofs, with probability at least 1/n21/n^2, each relevant step either identifies new linkage or removes at least one back arc. The latter event remains possible whenever the current FAS is not inclusion-wise minimal. This would extend our theoretical guarantees beyond DAGs and provide a positive result for general FAS instances. Our current result for DAGs would then follow as a special case of this more general guarantee.

We agree that the computational overhead of constructing and updating the DSM leaves considerable room for improvement. In particular, the number of fitness evaluations alone does not fully reflect the computational cost of DSM-RLS, since maintaining the DSM can itself be expensive. Nevertheless, we would like to point out that, in our experiments (Figure 4), DSM-RLS achieves substantially better solution quality than plain RLS within the same wall-clock time. This advantage becomes more pronounced as more transitive information is hidden (i.e., as kk increases). Thus, despite its computational overhead, the linkage information appears to provide a practical benefit in the considered instances.

Moreover, we have investigated a modification that substantially reduces this overhead while preserving our theoretical guarantees. Regarding the question about Theorem 4.3, we can reduce the number of fitness evaluations without affecting its time bounds. In particular, it suffices to perform a single NMC per generation. With a slight modification to DSM-RLS, we can therefore reduce the number of fitness evaluations to O(1)O(1) per generation, while retaining the expected O(n2m)O(n^2m) bound on the number of generations required to obtain an inclusion-wise minimal FAS. This yields an expected O(n2m)O(n^2m) bound on the total number of fitness evaluations, improving the previous bound by a factor of order n2n^2. We will incorporate the corresponding discussion and corollary into the revised paper. We tested the refined DSM-RLS that performs only a single NMC per iteration on the synthetic instances in the paper. The reviewers can find the plots as supplementary material. The adapted algorithm is much faster on both test instances with solutions found reliably within seconds, whereas before the speedup it took a minute for trees and an hour for the cyclic instances. The fact that it reliably finds the optimum also on cyclic instances supports the conjecture above that it can in fact find inclusion-minimal FAS.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.