- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper introduces the ScoreMixer-in-Attention mechanism, which can successfully encode CO instances with relations between items. Together with the proposed warm-up layer and instance-preserving normalizer, the proposed model outperforms existing NCO methods in terms of generalization and complexity. Although the work has an important practical gain, questions about its originality and methodology remain.
Critical strengths
(S1) The practical gain is clear: the proposed method is faster, requires less memory and generalizes better to larger instances.
(S2) Detailed evaluation metrics: wall-clock time, memory, FLOPs and training cost are the right metrics for this study.
Critical weaknesses
This paper has three stated contributions: ScoreMixer-in-Attention (SMA), the warm-up layer, and the instance-preserving normalizer.
(W1) SMA is claimed as the main architectural contribution, but it combines known components: an additive edge bias on the attention logits is presented in [1], refinement of a pairwise representation through an MLP in [2], and mixing of logits across the head dimension in [3]. Admittedly, these works are not from the NCO field, but they are established and well known in the graph transformer community and cannot be ignored. The related work covers only edge-aware attention mechanisms in NCO (GOAL and MatNet) and ignores many important works on graph transformers in general.
(W2) The second contribution, the warm-up layer, is not convincing. There is a clear gain on OP but only a small gain on large-size ATSP, while the warm-up layer performs worse on small-size ATSP. This raises the question of whether there is a real gain from introducing the warm-up layer.
[1] Ying et al., Do Transformers Really Perform Badly for Graph Representation?, NeurIPS 2021
[2] Ma et al., Graph Inductive Biases in Transformers without Message Passing, ICML 2023
[3] Shazeer et al. Talking-heads attention. arXiv:2003.02436, 2020
Questions for authors
Q1. Could you explicitly explain the novelty of your SMA mechanism compared with the methods presented in [1], [2] and [3]?
Q2. Table 5 provides the node initialization ablation only for ATSP and OP. I would like to see the same for the other problems as well.
Q3. As mentioned above, the warm-up layer does not bring much on ATSP, and it even degrades performance at problem sizes closer to the training size. Since ATSP is the only problem in this work without any node features, could this gap come from that property? That could be a major limitation for a model that claims to be a generic model for CO, since many CO problems have that property.
Q4. I do not understand the ablation presented in Table 1. It measures the impact of input normalization on MatNet, and I cannot see how the conclusion can be generalized to other models, including yours. How can we conclude that, because z-norm helps MatNet generalize, it will also help other models, including GECO, generalize?
Q5. Table 11 could answer the question about the usefulness of the normalization choices, but only OP has results without normalization (“None”). I would like to see the same for all problems, i.e. how the model performs without any normalization.
Q6. At present, this work addresses four routing problems and one scheduling problem. This may not be enough to claim a general model for graph combinatorial optimization. Did you try to apply your model to another problem family? It would be nice to see whether this method works when the input graph is sparse and defined by adjacency, as for example in the Maximal Independent Set problem.
Bonus question (not related to assessing the quality of this work): Just out of curiosity, did you try to train one model for all problems in a multi-task setting, like GOAL? I know this is outside the scope of this paper, but it seems to me that there is no (structural) limitation preventing this paradigm. Is that correct?
5 comments
Response (2 / 4)
W2 / Q3: The warm-up layer gives a clear gain on OP but only a small gain on large ATSP instances, and it is worse on small ATSP instances. Could this come from ATSP having no node features, and is that a limitation for a generic model?
We thank the reviewer for this careful reading of Table 5. We agree that on ATSP the gain of the warm-up is small, and that random identifiers are slightly better at the training size. We would like to add three observations.
First, the difference at small ATSP sizes is of the size of the variation between training runs, and at ≥ 500 the warm-up is ahead. The difference at ATSP100 (0.31 against 0.23) is close to the standard deviation between runs (0.06, measured over three further seeds).
Second, on ATSP the warm-up already contains what identifiers provide: adding random IDs on top of it brings nothing. The combined variant gives 0.35 / 0.61 / 0.85 / 1.02. The warm-up is also deterministic, with no artificial randomness at inference.
Third, on node features (Q3), we agree with the reviewer's observation: without node features, random identifiers have an edge near the training size, while the warm-up is ahead at the largest sizes. We tested this directly on a new problem, minimum vertex cover (MVC), which has no node features and no edge weights (set-up under Q6). All models are trained at = 100 (gap in %):
| Model | = 100 | 200 | 500 | 1000 |
|---|---|---|---|---|
| GOAL (official released checkpoint) | 0.27 | 0.75 | 15.96 | 15.87 |
| GECO, random-ID initialization | 0.14 | 0.37 | 2.18 | 6.44 |
| GECO, warm-up | 0.33 | 0.70 | 2.22 | 3.34 |
Where the GOAL row is the checkpoint released by the GOAL authors for this problem, run with their official code. At = 100 the test set is GOAL's own, with 10,000 graphs. For the larger sizes we generated graphs of the same kind: 128 per size, and 64 at = 1000. The gap is measured against the optimal cover at ≤ 200, and against the best cover found by a local-search solver at ≥ 500.
As on ATSP, random identifiers are more accurate at the training size, and the order reverses at = 1000, where the warm-up reaches 3.34 against 6.44. So the benefit of the warm-up is in size generalization, which is the purpose we claim for it. We will state this explicitly in the paper.
Q2: Table 5 gives the node-initialization ablation only for ATSP and OP. I would like to see the same for the other problems.
We thank the reviewer for this suggestion. Following it, we added CVRPTW and a combined variant, and the warm-up is ahead of random identifiers at ≥ 500 on all three tasks (gap in %, = 100 / 200 / 500 / 1000). Entries already in the paper (Tables 2 and 5) are repeated from it, and all other entries use one seed:
| Initialization | ATSP | CVRPTW | OP |
|---|---|---|---|
| random IDs | 0.23 / 0.52 / 0.89 / 0.98 | 4.04 / 5.60 / 6.48 / 3.10 | -0.16 / 0.65 / 4.96 / 10.58 |
| warm-up + random IDs | 0.35 / 0.61 / 0.85 / 1.02 | 4.10 / 5.94 / 6.16 / 3.21 | -0.18 / 0.30 / 3.98 / 6.02 |
| warm-up: GECO | 0.31 / 0.55 / 0.81 / 0.87 | 4.21 / 5.37 / 5.55 / 2.26 | -0.34 / 0.27 / 2.98 / 5.11 |
On CVRPTW, the new task, the two are close at ≤ 200, and the warm-up is ahead by 0.9 points at = 500 and 0.8 at = 1000. This is the pattern of OP in Table 5. On CVRP at = 1000, random identifiers give 6.51 against 4.79 in Table 2.
Overall, on these routing problems the warm-up gives its gain in size generalization, without any random input. We will add these results to Table 5.
Response (3 / 4)
Q4: Table 1 measures input normalization on MatNet. How can its conclusion be generalized to other models, including GECO?
We would like to clarify that Table 1 is only a motivating observation on MatNet, and it does not show by itself that normalization helps GECO. We apologize for the confusion. The direct evidence is now on GECO itself (next answer): without input scaling, GECO fails beyond the training size on ATSP, CVRP and CVRPTW.
Q5: Only OP has results without normalization ("None"). I would like to see the same for all problems.
We thank the reviewer for this suggestion. Following it, we ran GECO without any input scaling on the other routing problems, and also with GOAL's hand-designed scaling (gap in %, = 100 / 200 / 500 / 1000). Entries already in the paper (Tables 2 and 11) are repeated from it, and all other entries use one seed:
| Variant | ATSP | CVRPTW | OP |
|---|---|---|---|
| GOAL's input scaling instead of our normalizer | 0.62 / 0.80 / 0.85 / 1.09 | 3.93 / 5.50 / 6.27 / 3.38 | GOAL applies none (next row) |
| no input scaling at all | 0.39 / 0.91 / 3.96 / 104.28 | 54.91 / 64.50 / 72.51 / 70.24 | -0.19 / 1.43 / 3.90 / 10.37 |
| our normalizer: GECO | 0.31 / 0.55 / 0.81 / 0.87 | 4.21 / 5.37 / 5.55 / 2.26 | -0.34 / 0.27 / 2.98 / 5.11 |
Without any scaling, the model fails beyond the training size: the gap reaches 104% on ATSP1000, 61% on CVRP1000 and 55–73% on CVRPTW at every size. On CVRP the full row is 3.27 / 14.36 / 21.25 / 61.37, against 2.37 / 2.37 / 3.36 / 4.79 in Table 11. With GOAL's hand-designed scaling, accuracy drops on ATSP at small sizes and on CVRPTW at large sizes. We will add these rows to Table 11.
Response (1 / 4)
We sincerely thank the reviewer for the careful review, for the positive assessment of the practical gain and of the evaluation metrics, and for the pointers to the graph-transformer literature. Below we address the novelty of SMA, the warm-up layer, the normalizer, and the problem coverage.
We thank the reviewer for pointing us to these works, we admitted that we did not have a thorough search on the existing literature. We agree that they are closely related, and will add a paragraph on graph transformers (Graphormer [1], GRIT [2] and talking-heads [3], and also SAN [4], EGT [5] and GraphGPS [6]).
We agree that each ingredient has a precedent, and SMA differs from the three works in its nonlinear mixer on edge-fused logits, its budget of 12 numbers per pair, and its calibration of the logits:
Our contribution is therefore the combination that makes score-space edge fusion work for step-wise construction, where the cost recurs at every step. It joins a nonlinear residual mixer across heads, a calibration stage on the logits and an explicit per-pair budget, with the analysis of what this design can and cannot represent (Appendix C).
To test whether the earlier designs would suffice, we built them inside GECO with everything else unchanged, and both are far behind SMA (gap in %, N = 100 / 200 / 500 / 1000, SMA as in Table 2, other rows with one seed):
Wider pair states, the direction of [2], cost 1.8–2.1× the time and 2.9–4.2× the memory in GECO and are not more accurate on ATSP, CVRP or CVRPTW. They are represented by GECO-MatNet, which keeps a hidden activation per pair and head (Tables 3 and 6, and 4.88 / 6.12 / 6.57 / 3.22 on CVRPTW). The additive bias and the linear head mixing are far behind the nonlinear residual mixer on both tasks with intrinsic edge attributes.
We will add this discussion and the table to the revised paper.
References