- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper combines a permutation-equivariant Pairformer with discrete flow matching within a PatternBoost-style loop for extremal graph search. The generator iteratively revises edge decisions and reuses its weights across graph sizes. Reward fine-tuning further optimizes the quality of proposals after local search. Experiments cover -free edge maximization and Ramsey construction. Notably, a frozen model trained on 33 vertices directly generates optimal -free graphs on 34–37 vertices, while an adapted model produces a 42-vertex graph with 137 edges, matching the best-known lower bound. A bounded-size expressivity result provides structural motivation for the architecture.
Critical strengths
- The 33-vertex checkpoint is selected using only training-size performance and generates optimal graphs at several unseen sizes before local search. This is a substantive demonstration that learned construction behavior can remain useful beyond the training size. Although optimal samples are rare, verified constructions are valuable outcomes in this setting.
- Reward fine-tuning improves mean refined quality across almost all tested adaptation/evaluation settings. The distinction between raw and refined outputs also reveals that less frequently feasible proposals can nevertheless become better search starts. Density-matched, extension, and random-start controls provide useful evidence that learned graph structure contributes to the results.
Critical weaknesses
- The structural basis and scope of transfer remain unclear. The strongest results concern -free graphs, whose low-order structural constraints closely match the pair-based architecture. The density and extension controls are useful, but they do not establish whether successful graphs at different sizes belong to a common construction family. Given the more limited transfer under Ramsey constraints, it remains unclear how much of the success depends on structures specific to the task. This limits the transfer results' broader implications.
- The adaptation and efficiency comparisons do not fully separate the effects of optimization, additional data, and model selection. RL receives fresh search feedback, whereas the denoising control uses a fixed corpus. Consequently, the comparison does not establish whether RL offers an advantage over continuing the PatternBoost loop with updated data under the same additional search budget. Moreover, Table 3 reports the costs of selected pipelines, excluding model-selection costs, and the adapted models are selected based on target-size results. The reported training-time savings do not establish an overall efficiency advantage.
Questions for authors
- Do the high-quality graphs found at training and unseen sizes belong to the same construction families, or have simple extension relationships? Beyond the extension control in Appendix F.5, to what extent could these structural relationships explain the observed transfer?
- RL receives fresh search feedback, whereas the denoising control uses a fixed corpus. Would the gains persist against continuing the PatternBoost loop with an updated corpus under the same additional sampling and local-search budget?
- Would the training-time savings in Table 3 remain after including model-selection costs, or when the adaptation size is chosen without evaluating candidate models at the target size?
3 comments
The author resolved my concern, and I will keep my score of 3.
We are glad that our response resolved the reviewer's concerns and thank them again for their initial valuable review.
We thank the reviewer for their positive assessment and thoughtful questions.
Q1 and W1: Structural relationships and scope. Some observed optima are related by vertex extensions, but they do not form a single chain. Deleting a vertex links the observed n=35, n=34 and some n=33 optima. However, none of the five observed n=36 optimum classes contains the n=35 optimum, while two of the three n=37 optimum classes contain an observed n=36 optimum.
The 137-edge n=42 construction contains none of the eight tested source/adaptation maximum classes as an induced subgraph. These checks exclude specific extension relationships, but do not determine broader construction-family membership or explain the transfer mechanism. The original training corpora were also not retained. We will keep broader transfer claims limited, given the stronger evidence for C4-free graphs than for Ramsey constraints.
Q2 and W2: Continued PatternBoost with fresh feedback. Yes, the gains persist in this comparison. Starting from the same three n=33 checkpoints, we compared continued PatternBoost with reward fine-tuning at n=36, giving each 100,000 additional proposals, the same local search and 2,000 updates. For continued PatternBoost, each round samples 10,000 new graphs from the current model and improves them with local search. We then train on the best 100 graphs from that round together with an archive of up to 50 elite graphs, using 200 updates of the original flow-matching objective. We repeat this for ten rounds, so the training data are refreshed as the model changes. After adaptation, we evaluate the final models at n=36,37,40,42 without further training.
Values are mean edges after local search ± SD across source seeds, using 10,000 fresh attempts per model and size. Reward fine-tuning improves this mean in every seed at every size, although raw feasibility decreases. It produces no raw feasible samples at n=40,42. Adaptation takes about 119 minutes versus 106 for continued PatternBoost on A40.
Q3 and W2: Selection cost and efficiency. Yes, the efficiency gains also hold in our new comparison without grid-based checkpoint selection. We fixed the pretraining and fine-tuning sizes at 25 and 40, retained all three seeds’ final models, and compared against training directly at size 40. Fine-tuning uses 100,000 additional proposals and 2,000 updates. Each final model is evaluated on 10,000 fresh samples with the same local search.
Best denotes the maximum across three seeds; means and feasibility show mean ± SD across seeds. All samples are feasible after local search. Timings include the full pretraining, fine-tuning and evaluation costs.
We still obtain similar average quality after local search and better best constructions with 47% less execution time, although fine-tuning varies more across seeds and relies more on local search. This comparison uses a fixed recipe at previously studied sizes. Of course, it still does not include the historical cost of finding that recipe. We will also clarify that the original Table 3 timings exclude model selection.
We thank the reviewer again for their useful comments, which helped us to further improve our work.