- Rating
- 2(−1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The paper introduces N-FPT, an approach for improving solutions on neural combinatorial optimisation problems based on neural advice, assuming that a treewidth decomposition can be made. With perfect advice, the method guarantees optimality. The paper also presents NIC-FPT and NRD-FPT variants, which use incremental confidence and random deferral respectively in order to improve the solutions of imperfect advice. The approaches can also be used to provide feedback to neural models during training. The paper demonstrates that the method is useful for improving neural approximations without retraining through several experiments.
Based on the strengths outlined in S1 and S2, I recommend acceptance, as I believe the ideas presented to be useful to the NCO community. However, the paper would be greatly strengthened by addressing the weaknesses outlined in W1 and W2. In particular, it is important to understand how the method compares to alternative, less informed post-hoc solution improvement approaches, and to understand the method's limitations.
Critical strengths
- [S1]: The proposed NIC-FPT and NRD-FPT methods provide useful approaches for improving the performance of neural approximations, building on a useful theoretical foundation.
- [S2]: The use of N-FPT for providing feedback in the training process is an interesting insight, and demonstrably improves the performance of the trained solvers.
Critical weaknesses
- [W1]: The proposed method has some important trade-offs which are not the subject of much discussion or analysis. In particular, graph width is a severe limiting factor due to the exponential relationship, but no analysis is provided to demonstrate which problem types or graph types for which this becomes restrictive. Furthermore, the dependence of improvement of N-FPT on advice quality has not been investigated. Without these analyses, it is difficult to determine the settings in which N-FPT is practical.
- [W2]: No baselines are provided for other post-hoc solution improvement approaches.
- [W3]: The writing is convoluted and difficult to parse throughout the paper. I recommend that much of the writing, especially the introduction, should be rewritten with a focus on clarity to avoid the abstruse, telegraphic language and ensure that terms are properly defined and precisely used.
Questions for authors
- [Q1]: The improvements in Table 1 seem quite small in some cases. Can you provide confidence intervals for these values?
- [Q2]: Can you explain why you have chosen to use regular graphs for some experiments, and RGG/King graphs for others?
- [Q3]: It is my understanding that the problem formulation only allows for problems where the solution is constructed by selecting an unordered node subset. Is there any way to extend the paradigm to ordered sequences (e.g. TSP), or does that prohibit the tree decomposition?
- [Q4]: Are there any further limitations to your proposed method?
- [Q5]: How does your method compare to more traditional post-hoc improvement methods, such as beam search?
6 comments
[Authors Response (2/3)]
Post-hoc comparison (W2 & Q5) We clarify that it is not our focus to integrate beam search with neural networks. It requires extra engineering effort beyond our focus: showing that our methods can improve both training and inference ability for neural solvers for combinatorial optimization tasks.
To meet the reviewer's curiosity, we apply the standard beam search as the post-hoc process, that is after training neural model, we use it to score the available nodes and keep the best 20, we select the best moves, and repeat the standard beam search procedure. Within the limited time and computation budget, we run quick tests on the subset regular graph dataset, in total 80 instances, and 20 for each settings.
| Setting | NIC-FPT, average | N-Beam, average | NRD-FPT, best of 20 | N-Beam, best of 20 |
|---|---|---|---|---|
| SS | 291.488 | 290.956 | 297.600 | 295.050 |
| SD | 172.845 | 172.323 | 178.900 | 176.900 |
| LS | 368.522 | 368.325 | 377.650 | 373.200 |
| LD | 230.020 | 229.584 | 235.950 | 233.650 |
Presentation (W3). We agree with the reviewer that the writing should be improved. We aimed to explain the more complex procedures through visual illustrations and plain language, but the presentation still has room for improvement. Following the reviewer's advice, we will revise the writing, especially the introduction. We thank the reviewer for this helpful note.
Other questions:
Q1. Confidence intervals for Table 1. Most of the small values in Table 1 are the average gains of N-FPT alone. By Eq. (2), the gain of N-FPT equals the completion loss, the value that the neural solver loses when it completes its own advice, so a small gain means that the neural solver already completes its advice almost optimally. Proposition 3.1 also guarantees that, for the same advice, this gain is never negative. NIC-FPT and NRD-FPT go further and improve the advice itself. For GNN+RL, whose N-FPT gains in Table 1 are the smallest, the table below reports each gain over the standalone solver with a 95% confidence interval over the 300 pairs of test graph and training seed in each setting:
| Setting | N-FPT, average gain | NIC-FPT, average gain | NRD-FPT, best-of-20 gain |
|---|---|---|---|
| SS | |||
| SD | |||
| LS | |||
| LD |
The intervals of N-FPT and NRD-FPT win in every setting, and neither method does worse than the standalone solver on any of the 300 pairs. On SD and LD, the gains of N-FPT round to zero in Table 1; however, their intervals still stay above zero. Even where the gain is this small, N-FPT certifies every returned solution as the best achievable completion of its advice.
NIC-FPT changes the advice by design: in each round, NIC-FPT fixes the vertices that most samples select, and the next round redraws only the decisions that remain open. The final advice of NIC-FPT therefore differs from the advice of the standalone solver. If NIC-FPT used the same advice as the standalone solver, its gain could never be negative, exactly as Proposition 3.1 guarantees and as the N-FPT column shows. A vertex that most samples select can still be a poor choice, so the advice of NIC-FPT is rarely worse than an independent sample; even so, the average gain of NIC-FPT over the standalone solver is still positive, and stronger than N-FPT in every setting. For GFlowNet, across the three training seeds, we have the same statistical observation. We will add these intervals to Appendix B.
Q3. Other problems such as TSP. The tree decomposition does not prohibit ordered solutions. N-FPT needs only a dynamic program over a tree decomposition that accepts fixed decisions. By Courcelle's theorem (lines 46–48) and its extension to optimization [1, 2], such programs exist for every problem expressible in monadic second-order logic, which includes Hamiltonian cycles. For TSP specifically, Bodlaender et al. [3] give a deterministic dynamic program over a tree decomposition whose running time is single exponential in the treewidth and polynomial in the graph size. TSP is therefore fixed-parameter tractable parameterized by treewidth, and N-FPT can directly use this dynamic program to complete neural advice for TSP. Adapting the advice and the dynamic program to tours requires design changes and experiments that we leave to future work.
We hope our explanation meets the reviewer's expectation, and if possible, can lead to a positive reconsideration. We thank for your time and effort.
[Authors Response (3/3)]
[1] Courcelle, Information and Computation, 1990.
[2] Arnborg, Lagergren, and Seese, Journal of Algorithms, 1991.
[3] Bodlaender, Cygan, Kratsch, and Nederlof, Information and Computation, 2015.
[4] Maniu, Senellart, and Jog, ICDT, 2019.
[Authors Response (1/3)]
We thanks the reviewer for their time and effort. We especially appreciate the recognition on the impact of this work to the NCO community. This indeed is our motivation.
Within the limited time, we response by priority based on our understanding to the reviewer's comment.
W1 and Q4: width, advice quality, and limitations.
Width. A natural concern is that exact computation grows exponentially with the width of the graph, so that wide graphs would make N-FPT impractical. However, N-FPT never runs the dynamic program at the width of the input graph. We first choose a target width (Appendix B.8), and then remove a modulator so that every remaining bag fits this width. The cost of exact completion is therefore exponential only in the chosen target width and linear in the number of bags, whatever the width of the input graph (lines 156–161). A wider graph changes only the size of the modulator, that is, how many decisions the neural solver makes. The two parts therefore share the computation: the neural solver decides the vertices that would make exact computation too expensive, and the dynamic program optimizes every other decision exactly. Our dense settings, such as regular graphs of degree 16 and BA graphs (Table 10), test this regime directly.
The target width decides how the two parts share the work: a larger target width shrinks the modulator and trades more exact computation for better solutions. To test this trade-off, we applied N-FPT to two diffusion-based solvers, SDDS (SOTA) and DiffUCO, on their 800 graphs of the standard RB-small benchmark:
Raising η from 10 to 65 shrinks the modulator from 48% to 13% of the vertices, and the average gain of N-FPT rises from 0.0014 to 0.1875 for SDDS and from 0.0074 to 0.3298 for DiffUCO. Even the average gain of 0.0014 has a 95% confidence interval above zero. In every row, N-FPT makes no graph worse, as Proposition 3.1 guarantees.
Advice quality. Since the neural solver decides the modulator, the final solution depends on the quality of its advice, and we study this dependence in four ways. In theory, Eq. (2) and Proposition 3.1 show that N-FPT returns the best achievable completion of any advice: a global optimum when the advice is perfect, and never a worse solution than the neural solver's own. Across solvers, Eq. (2) shows that the gain of N-FPT equals the completion loss, the value that a solver loses when it completes its own advice; in the table above, DiffUCO, the weaker model, gains more than SDDS in all four comparisons. In a controlled comparison, N-FPT and NIC-FPT or NRD-FPT run the same exact completion and differ only in advice quality, and better advice gives better results (Table 1). Under distribution shift, solvers tested away from their training distribution give worse advice, and N-FPT still recovers part of the loss (Figs. 3 and 9–12). This dependence motivates the rest of the paper: two inference-time methods and one training method, each of which improves the advice.
Limitations. The main limitation is: our method based on the shape of tree decomposition. However, finding the thinnest tree decomposition is NP-hard itself. The practically fast way remains heuristics, despite prior empirical work [4] has shown that they are strong. Thinner tree decomposition can certainly help our framework on both modulator size and the practical runtime, yet that falls into another research direction. Another angle to interpret the limitation is: Which graph and problem types admit small modulators. In parameterized complexity, this is an exciting but extremely challenging direction.