NeurIPS 2020

GCOMB: Learning Budget-constrained Combinatorial Algorithms over Billion-sized Graphs

Meta Review

Three reviewers rated this paper as weak accept, and one as reject. All reviewers felt the paper combined learning-based techniques effectively to achieve impressive performance on combinatorial optimization problems in massive graphs. Reviewers describe the work as a combination of heuristics and modules consisting of existing techniques, but largely view the overall system as being significant, and comment on its impressive performance and an ablation study to justify individual components. The main criticisms were about missing comparisons to baselines. It was observed that the proposed method essentially does well on submodular coverage style problems where the greedy algorithm is often nearly optimal in practice and its main advantage is being much faster. The reviewers pointed out that a number of faster variants of the greedy algorithm are available and requested comparisons to these. In the rebuttal, the authors show significant gains relative to three additional baselines: CELF, SG, and OPIM. This was enough to convince R2 to raise their score. R3 felt that at least one relevant baseline was still missing. Some ambiguity remains here, but overall the meta-reviewer feels the authors provided significant evidence that their approach performs very well relatively to a range of baselines on a number of different problems. The authors are encouraged to improve the paper with the contents of the rebuttal and also consider the remaining comments of R3.