Fractional Langevin Dynamics for Combinatorial Optimization via Polynomial-Time Escape

We sincerely appreciate the effort you put into reviewing our paper. Below, we provide our responses to the weakness and questions you raised.

W1: The related work part seems to be too concise. It could be extended a little bit.

Thank you for your suggestion. We originally intended to include the Related Work in the main text, but due to space constraints we only provided a partial discussion and subsequently moved it to Appendix A. Unfortunately, submission time pressure prevented us from expanding it further. We apologize for this oversight and will fully supplement the Related Work section in the final version of our paper to provide a more comprehensive background review.

To Q1&Q2: Thank you for catching this error. We will make the corrections in the final version of our paper and include the correct version in the final submission.

If you have any additional questions, please don't hesitate to reach out. We would be more than happy to address any concerns.

We sincerely appreciate the effort you put into reviewing our paper. Below, we provide our responses to the weaknesses and questions you raised.

W1: The energy functions of the proposed method use simple penalty terms (Eq. 6); complex constraints (e.g., multi-objective or conditional) remain unaddressed.

Thanks for your constructive comment. While our paper employs a simple penalty term in the energy function and does not yet incorporate more sophisticated constraints, the scenarios we address are nonetheless highly challenging, and the case studies we present involve standard problems commonly used in prior work—on which we have achieved strong results. We believe that our proposed method can be extended to tackle more complex problems, and in future work we will expand our approach to include the elaborate penalty terms and complex constraints you mentioned.

W2: The evaluations omit comparisons with evolutionary strategies (e.g., CMA-ES) or modern heuristics tailored to specific problems (e.g., MaxCut solvers).

Thank you for raising this question. As far as we know, CMA‑ES is typically applied to continuous optimization problems, whereas our work focuses on discrete combinatorial optimization. If you could kindly point us to any relevant literature, we would be most grateful. Furthermore, our KaMIS baseline employs the ReduMIS algorithm, which conducts an evolutionary search on a reduced graph. As for MaxCut solvers, we present the results of a semi-definite programming method (SDP), which is a widely used baseline for MaxCut, in the table below and will include them in the final version of our paper.

W3: FLD-IG’s inference scalability for massive graphs (e.g., >10k nodes) needs deeper analysis.

We apologize for any misunderstanding. In our ER‑dataset experiments, training was conducted on ER‑[700–800], while inference was performed on ER‑[9000–11000]. The results suggest that our method may exhibit reasonable inference scalability even on massive graphs.

W4: The experimental results do not show significant advantage over existing methods.

Thank you for your question. We fully acknowledge your point: although our theoretical contributions are strong, the empirical improvements may not appear dramatic. Since prior solvers already approach the optimal solution, we focused on improving performance in the near‑optimal regime—which is substantially more challenging than improving cases far from optimal. Although our method yields improved results over previous approaches on most datasets, these gains are moderate and indicate that there is still plenty of scope for further refinement.

We sincerely hope that our response provides you with a clearer and more thorough understanding of our work. If you have any additional questions, please don't hesitate to reach out. We would be more than happy to address any concerns.

We sincerely appreciate the effort you put into reviewing our paper. Below, we provide our responses to the weaknesses and questions you raised.

W1: Authors do not dive deep into the truncation strategy introduced to improve stability for low $\alpha$.

We sincerely apologize for the lack of clarity in our description, which may have caused confusion. Since we initially applied our method to 0-1 integer programming problems, for problems where the values are limited to 0 and 1, large outliers can cause the solution to remain stuck at 0 or 1, which goes against our intention of using noise to facilitate escaping from local minima. Therefore, applying reasonable truncation to the outliers allows the iteration process to more easily escape from local optima. We also show in the table below that $d_{\mathrm{noise}}$ is easy to tune, and slight perturbations to $d_{\mathrm{noise}}$ do not significantly affect the performance.

W2: Could authors add variance accross runs to ensure consistency?

We sincerely apologize for not including the variance of the datasets in the paper to ensure consistency. We evaluate the variance of FLD-EG by using different seeds for 10 repeated experiments, and the results are reported below:

We will include the variance for all results of our methods in the final version of our paper.

W3: Is the idea novel? Has it been already done in adjacent fields?

Thank you for your question. We sincerely acknowledge that replacing Gaussian noise with $\alpha$-stable L'evy noise is not an entirely new strategy. However, it has not been explored in the field of CO problems. We recognized the potential of $\alpha$-stable L'evy noise in CO problems and have made preliminary attempts. Moving forward, we plan to extend these experiments to more complex problems. We apologize for not providing a detailed discussion of the application of FLD in other fields due to space limitations. We will include a more comprehensive review of the related work in the final version of our paper.

W4: Section 3.5 is unclear to me. Could the authors provide more details in the main paper to clarify it ?

We sincerely apologize for not providing a detailed description of FLD-IG in the main paper. Due to space limit, we included the specific method details and pseudocode in Appendix E.2. However, we would like to provide a more detailed explanation of the FLD-IG methods here:

Based on the differentiability of the energy function, we divide the FLD-based approach to solving CO problems into explicit gradient (FLD-EG) method in Section 3.4 and implicit gradient (FLD-IG) method in Section 3.5. In Section 3.5, when the energy function is not differentiable, we introduce an NN-based framework whose training procedure resembles reinforcement learning, alternating between sampling and update steps, and using auto-grad to approximate the gradient of the energy function.

We sincerely hope that our response provides you with a clearer and more thorough understanding of our work. If you have any additional questions, please don't hesitate to reach out. We would be more than happy to address any concerns.

We sincerely appreciate the effort you put into reviewing our paper. Below, we provide our responses to the weaknesses and questions you raised.

W1: The description of the FLD-IG and FLD-EG methods is too brief.

We sincerely apologize for not providing a detailed description of FLD-IG and FLD-EG in the main paper. Due to space limitation, we included the specific method details and pseudocode in Appendix E. However, we would like to provide a more detailed explanation of the FLD-IG and FLD-EG methods here:

Based on the differentiability of the energy function, we divide the FLD-based approach to solving CO problems into explicit gradient (FLD-EG) and implicit gradient (FLD-IG) methods. For FLD-EG, we provide a recursive expression with gradient and noise truncation, where a multi-step sampling and recursion approach can approximate the optimal solution. For FLD-IG, when the energy function is not differentiable, we introduce an NN-based framework whose training procedure resembles reinforcement learning, alternating between sampling and update steps, and using auto-grad to approximate the gradient of the energy function.

We will include this detailed explanation of the FLD-IG and FLD-EG methods in the final version of our paper.

W2: Not find the explicit statement about the overall pipeline complexity and memory consumption.

We sincerely apologize for not providing the complexity and memory consumption of the method pipeline in the main paper. Compared with the RLSA and RLNN methods, the complexity in the single-step sampling phase of FLD-IG and FLD-EG is similar. However, due to the stronger escape ability of FLD with symmetric $\alpha$-stable noise compared to LD with Gaussian noise, the FLD-IG and FLD-EG methods have fewer iteration steps. In contrast to other learning-based methods, FLD-IG and FLD-EG only involve sampling and updating steps, resulting in a lower cost in a single iteration.

The memory consumption is summarized in the table below:

Here, we report only a single result for each case; in the final version of our paper, we will include the complete set of experimental results.

W3: Does the proposed methods have a training stage?

The FLD-EG method is a training-free method, while the FLD-IG method involves a training stage. The time consumption is shown in the table below. In Tables 1 and 2, the runtime includes only the model inference time and does not account for the time spent in the training stage. However, the training stage does not take very long time, and for each problem, the training stage will be carried out only once.

Here, we report only a single result for each case; in the final version of our paper, we will include the complete set of experimental results.

To Q1: We sincerely apologize for any confusion caused by the phrasing in our paper. Equation (6) represents the Lagrangian function, not a pure penalty function. This linear term naturally arises from the dualized constraints in dual theory, ensuring that when the KKT conditions are satisfied, the primal and dual problems are equivalent (strong duality holds for convex problems).

To Q2: In Equation (20), during the discrete sampling process, there is the gradient of the energy function. If the energy function is differentiable, the explicit gradient can be directly incorporated into the recursive expression, and the optimal solution is approximated through iterative updates in the sampling steps. This is referred to as FLD-EG. If the energy function is non-differentiable, the gradient of the energy function is implicitly approximated using auto-grad, which is referred to as FLD-IG.

To Q3&Q5: The truncation parameter $d$ is applied for both the gradient and the $\mathcal{S}\alpha \mathcal{S}$ noise in the Equation (29). We apply the Top-$d$ truncated indicator to $\nabla H$, ensuring that only the $d$ components with the largest magnitude influence the update and apply the Top-$d_{\mathrm{noise}}$ truncated indicator to the sampled noise vector, truncating extreme values to stabilize the sampling process. The second term in the Equation (29) regularizes the expected Hamming distance between the two solutions, with $\lambda'$ being the regularization coefficient.

To Q4: The value of $\alpha$ in the ablation study is consistent with the one presented in Table 3 and Table 4.

To Q6: We sincerely appreciate your valuable suggestions. In the ablation study, we explored the use of "fractional Langevin dynamics to escape from the narrow local minima faster than the classical Langevin dynamics." Below, we present specific data to demonstrate the escape ability of FLD.

As external links aren’t permitted in the rebuttal phase, we’re unable to include images here. Instead, we provide a textual description below to address your question: For the MIS problem on an ER‑[700–800] instance, LD required 50 steps to reach the Best Energy of –39, whereas FLD did so in just 16 steps. To attain the Best Energy of –41, LD needed 210 steps, compared to only 100 steps for FLD. Likewise, on a BA‑[200–300] instance of the MaxCut problem, LD took 32 steps to reach –800, while FLD achieved the same in just 8 steps.

To Paper Formatting Concerns: Thanks for your kind suggestion. We have rewrite the sentence in lines 190-193: "Similarly, we provide the discrete proposal for the escape time of both LD and FLD. We state upfront that the Markov chains of LD and FLD are reversible if they satisfy the detailed balance conditions. Additionally, $p_{\tau}(x)$ is a positive stationary distribution, given that the symmetric proposal and the Metropolis-Hastings acceptance criterion are satisfied for constructing discrete LD and FLD."

We sincerely hope that our response provides you with a clearer and more thorough understanding of our work. If you have any additional questions, please don't hesitate to reach out. We would be more than happy to address any concerns.