- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies how different selection orders can produce the same independent set and reward but give different policy-gradient signals during training. The authors propose SOM, which averages these signals over alternative orders while sharing graph computations to reduce the additional cost. The theoretical analysis shows that the estimator achive the expected gradient and reduces its covariance under matched sampling. The paper also includes experiments on weighted and unweighted independent-set problems show improved training efficiency over RLOO.
Critical strengths
The paper addresses an interesting problem, different selection orders can produce the same independent set and reward but can have different training signals. The model averages equivalent orders for a solution containing vertices in operations. The theoretical analysis directly supports the proposed estimator. Under matched sampling, SOM preserves the expected gradient, , and reduces covariance, .
The experiments include separately tuned baselines, additional sampling, different backbones, and sparse-graph tests, and this is supportative to the main claims.
All the figures, plots and tables are clear and easy to follow.
Critical weaknesses
The covariance guarantee compares estimators under matched sampling rather than matched computation, so it does not establish when variance reduction outweighs the additional cost. The separation also concerns a specific local averaging scheme on unit-rate stars, rather than general graphs. Empirically, the training speed ratio decreases from to after separate tuning, while SOM does not establish better solution quality than native CHILS on MWIS or KaMIS on MIS. These results support a useful but relatively narrow training improvement.
Questions for authors
-
The Anonymus GitHub link has some errors and cannot be opened.
-
When SOM's variance reduction outweighs its computation and memory cost, especially on sparse graphs with long independent sets?
Dear Reviewer rt2j,
Thank you for your thoughtful review and positive assessment of our work. We are glad that you found the problem interesting and the theory supportive. Following your suggestions, we have fixed the code link and added a practical guideline on when SOM pays off. Our responses are below.
W1: The covariance guarantee compares estimators under matched sampling rather than matched computation, so it does not show when the variance reduction outweighs the additional cost.
A: Thank you for this important point. We would like to clarify that, while Prop. 3.1 is a matched-sampling result (as stated in Section 3.2), our experiments already address the matched-compute question. All efficiency results count the full cost of sampling, averaging, communication, and updates:
W2: The (L2) separation concerns a specific local averaging scheme on unit-rate stars, not general graphs.
A: Thank you for this point. We would like to clarify that the star result (Theorem B.2) is a mechanism example, not a claim about all graphs (Section 3.4; Appendix B.5). On general graphs, we support cyclic averaging empirically. Adding cyclic starts reduces parameter-score variance by 30.8% over fixed pairs (Lines 398–404), and SOM outperforms alternating-pair averaging.
W3: The speed ratio drops from 1.22× to 1.11× after separate tuning, and SOM does not beat native CHILS on MWIS or KaMIS on MIS. The improvement is useful but relatively narrow.
A: We agree that the gain is moderate, and we report both the fixed-configuration and separately tuned ratios (Line 413). SOM is a training estimator and does not aim to replace classical solvers. We have revised Section 4.2 to state this clearly (Lines 327–336). Within this scope, the benefit is consistent across three backbones, adds no inference cost, and requires no change to the model or sampler.
Q1: The anonymous GitHub link has errors and cannot be opened.
A: Thank you for pointing this out. The link in the paper used a wrong path. We have fixed it in the revision.
Q2: When does SOM's variance reduction outweigh its O(n+m+K2) computation and memory cost, especially on sparse graphs with long independent sets?
A: Thank you for this question. The ratio K2/(n+m) decides the regime. When it is small, as on MWIS-VR, the shared table is cheap and SOM reaches the target faster than RLOO (Section 4.3). On sparse graphs with long solutions, the table can dominate (Section 3.3). On our sparse stress panel, SOM needs 1.076× the GPU-hours of native RLOO to reach the target (Appendix C.12). In this regime, the separate-start evaluator computes the same estimator without the K2 table.