Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: A machine learning framework for constructing heuristics for certain geometric graph optimization problems is proposed. Such graphs are derived from points on a 2d grid, for example. This geometric structure is typically useful for the design of approximation algorithms. This insight inspires the main question addressed in this paper: does the geometric structure also help improve ML approaches for graph optimization problems such as Maximum Independent Set (MIS), both theoretically and practically?

The authors answer affirmatively by leveraging an existing algorithmic paradigm from Baker (1994). The key idea is to decompose the space into a number of independent subproblems (linear in the graph size) of bounded sizes, then heuristically solving those small subproblems using an ML model. The ML model may be a convolutional network that see the subproblem is a pixel grid, or a graph neural network that acts directly on the small graph. The ML model may also be trained by supervision or without. 

Theoretically, it is shown that if the ML model has universal approximation guarantees (e.g., 1-layer neural network), meaning that it can accurately approximate the function mapping from subproblem to subproblem optimum, then one obtains a bicriteria approximation guarantee on the global optimization solution, which is assembled appropriately from subproblem solutions.

Experimentally, it is shown that this decomposition approach can be combined with three different ML model classes, improving their original performance on a number of random problem families for MIS and vertex cover.

main_review: A machine learning framework for constructing heuristics for certain geometric graph optimization problems is proposed. Such graphs are derived from points on a 2d grid, for example. This geometric structure is typically useful for the design of approximation algorithms. This insight inspires the main question addressed in this paper: does the geometric structure also help improve ML approaches for graph optimization problems such as Maximum Independent Set (MIS), both theoretically and practically?

The authors answer affirmatively by leveraging an existing algorithmic paradigm from Baker (1994). The key idea is to decompose the space into a number of independent subproblems (linear in the graph size) of bounded sizes, then heuristically solving those small subproblems using an ML model. The ML model may be a convolutional network that see the subproblem is a pixel grid, or a graph neural network that acts directly on the small graph. The ML model may also be trained by supervision or without. 

Theoretically, it is shown that if the ML model has universal approximation guarantees (e.g., 1-layer neural network), meaning that it can accurately approximate the function mapping from subproblem to subproblem optimum, then one obtains a bicriteria approximation guarantee on the global optimization solution, which is assembled appropriately from subproblem solutions.

Experimentally, it is shown that this decomposition approach can be combined with three different ML model classes, improving their original performance on a number of random problem families for MIS and vertex cover.


Overall, there is no shortage of creative algorithmic work in this paper. The experiments demonstrate a clear benefit to the proposed decomposition strategy compared to ML on the original full graph. However, the experiments do not go further to demonstrate that the NN-Baker approach can outperform the pure Baker approach without any NN. In particular, the NN replaces enumeration within each subproblem. Instead of enumeration, one could use integer programming through branch and bound (which is only enumeration in the very worst case, and empirically performs much better than that). Alternatively, one could use the (learnable) greedy heuristic for MIS of Gupta, Rishi, and Tim Roughgarden. "A PAC approach to application-specific algorithm selection." SIAM Journal on Computing 46.3 (2017): 992-1017. What I'm trying to say is that while Baker-NN can improve over NN, it is not clear that it can improve over Baker-ILP or Baker-(other types of ML). Because adapting the Baker approximation framework to new combinatorial problems (on geometric graphs) requires some serious algorithmic work, I suspect that the proposed framework has limited applicability beyond the problems studied herein. 

Nonetheless, the paper is of high quality and so I lean towards accepting. I am eager to hear the authors' thoughts on my criticisms. 

Other questions/comments:
- Baker paradigm: The way Algorithm Baker-MIS is presented at the moment, it is hard to tell how much of it is known from Baker's paper. Some discussion of exactly how you are extending/modifying/specializing the Baker paradigm would be good.

- Experimental results: you report the approximation ratio of a method's MIS to the optimum. This optimum respects the unit-ball constraint, whereas a learning method's MIS might not. How is that factored into the reported ratios? Am I missing anything?

Minor:
- line 6: "algorithm that is linear in graph size" --> "algorithm that runs in time linear in the graph size"
- line 13 "approximately solve"; this is only true if the NN being used is actually a universal approximator, which makes me think that the claim in this phrase is a bit too strong.
- line 84 "exponential in terms of the parameters", what parameters?
- Figure 1, "paradigmfor" --> "paradigm for"
- Figure 1, "$X_C/X_C^{'}", should that be a backward slack instead to denote set difference?
- line 159, shouldn't it be $\alpha > 1$, as in line 164?
- line 160, the cardinality of the set $Y$ should be used in the in the inequalities, as you do in line 166.
- lines 161-166: it would be good to articulate the definition of the bi-criteria approximation guarantee in words as well, "The algorithm is guaranteed to return an $\alpha$-approximate solution to the problem, while the unit-ball constraint by a factor of at most $\beta$."
- Algorithm Baker-MIS (page 5) is a bit difficult to parse. There is lots of notation and the figure is good but too simplified to allow for a reimplementation. Pseudocode or a clearer exposition in the appendix might be worthwhile.
- line 217: "Detials" --> "Details"
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a polynomial time approximation scheme that can utilize neural networks
to efficiently solve combinatorial problems like maximum independent set and minimum vertex cover
on geometric interesection graphs. The method decomposes a problem instance into multiple smaller
instances of bounded size located on a grid, which are then solved with the help of a neural network. The neural network
is either a graph neural network applied on the intersection graph or a CNN that treats the problem
as a segmentation task. To discretize the output of the network the authors use a greedy 
rounding strategy that preserves feasibility.
main_review: 
### Strengths:
- The idea of reducing a problem to instances of bounded size in order to obtain an approximation guarantee in an ML setting is interesting.
- The use of neural networks (NN-Baker) seems to provide an improved theoretical result over the standard Baker approach, which is nice.
- Figures help build intuition and improve the readability of the paper considerably.
- Related work is sufficiently discussed. Experiments include models from recently published works.
- Seems to consistently improve the performance of models from the literature.
- Nice experiment on generalization.


### Criticism, comments, and questions:

- In terms of writing quality, there are plenty of typos and minor mistakes.
Here are some examples:

line 53: "Does a proposed ML pipeline has the expressiveness capacity..."

line 115: "Our NN Baker framework instead calls the neural network involved only linear time."

Text in Figure 1: "(Step 2) of Baker's paradigmfor each cell"

table 1 caption: "...approaches to groud truth"

line 217: "Detials ae in the supplement."


lines 231-232: is at most and \epsilon|OPT(X)|.

line 349: "For each of the five setup,"

line 366-367: "As shown in Table 1, using Baker framework consistently improve the performance of these SOA
neural networks on geometricMIS problem."

line 374: "(including variance of these accuracy)"

line 378-379: "The advancement in neural network architectures, and their power in potentially better adapting to
problem structure and input distribution in a data-driven manner, have brought new ways..."

- Another comment on the structure of the paper:  Currently, you explain the greedy discretization in the CNN-Baker section, 
but since you also use it in GNN baker it would improve the clarity of the text if you described it in a separate paragraph.

- In the introduction, to motivate your approach you mention the existence of
real-world problems that involve geometric intersection graphs. Your experiments are
on synthetic randomly sampled instances. It would be nice to include experiments on real-world data.

- While we can see that the NN-Baker method performs well on large graphs, we are not given information about
how quickly it runs. Your framework seems to improve results across the board but it's not clear at what time cost this happens. Furthermore, showing results of NN-Baker on varying graph sizes like it was done in Figure 3
would help build a stronger case for your framework. 

- In the paper, you claim that your framework extends to other problems like maximum acyclic subgraph.
 Having experimental results on at least one of them would help improve the paper's experimental section, both
in terms of novelty and in terms of providing evidence for your theoretical results.

- Minor detail regarding Theorem 3.2: The result from 3.1 gives you a universal approximation result for a function 
that maps a vector to a real number, while the function you want in Step 2' of NN-Baker 
is $g_\mathcal{N}: [0,1]^k \rightarrow [0,1]^k$. The result from 3.1 extends to vector-valued outputs but it should
be explicitly stated for the sake of clarity.

- An ablation study on NN-Baker would also help illustrate its benefits over the non-neural version.
  For instance, is it possible to compare with the non-neural Baker framework, or is it too slow because of the brute force enumeration?
  Could you replace the subset enumeration in step 2 with a maximum independent set heuristic? I understand that you 
  may lose the approximation guarantee that way, but heuristics can perform very well so it is important
 to understand whether the neural networks are indeed beneficial in practice.

- In line 212, you claim that in practice you can start adding the points that were close to the grid back to the solution as long
as they don't violate your condition. Do you actually do this in your experiments? If you do, it would be good to have an ablation study that shows the contribution of this "post-processing" step in your results.

### Recap: 

Overall, I find the contributions and the direction of the paper interesting.  Theoretical guarantees are particularly appealing
in the context of machine learning. 
However, given that the paper's scope is already limited on a particular class of graphs and a specific subset of combinatorial problems, I believe that more thorough experimental demonstrations are necessary (I provided some examples) to make a strong case for this method.  Finally, some refinement is necessary in terms of writing in order to improve the clarity and quality of the paper. 

For now, I will give the paper a 5 but I am willing to adjust my grade after the rebuttal.



limitations_and_societal_impact: The authors have discussed the limitations of their work sufficiently.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies graph optimization problems in the geometric domain and proposes a novel paradigm of neural combinatorial optimization, NN-Baker. NN-Baker breaks down the original problem into local subproblems of bounded sizes. Neural networks can solve the subproblems with theoretical guarantees thanks to the universal approximation theorem. The proposed method performs better than vanilla methods in several synthetic datasets.
main_review: # Strengths

* The proposed framework, NN-Baker, is motivated by results from theoretical computer science and seems quite novel in the machine learning literature. It provides the machine learning community with some insights.
* While the method is principled from the theoretical perspective, the resulting strategy is simple and intuitive.
* Thanks to the partitioning and coarsening mechanism, the subproblems neural networks actually need to learn are small, which leads a good training strategy for large combinatorial tasks.
* Figures 1 and 2 describe the method well.

# Weaknesses

* Task information is lost in three steps. First, peripheral points in each cell are ignored. Second, points are discretized into pixels. Third, the subproblems are solved by neural networks. I'm wondering about how much information is lost in each step. It would be interesting to see the performance when the subproblem in each cell is solved exactly.
* Only synthetic data are used. It would strengthen the paper if motivating real-world data could be used. City and sensor data can be candidates.
limitations_and_societal_impact: They are discussed in Section 5.
review_title: null

Meta-review: All reviewers found the papier interesting and appreciated the articulation with theoretical guarantees.
The reviewers have asked a number of questions and made a number of comments: the authors are strongly encourage to take them into account and to use the elements that they provided in their responses to the reviewers to prepare the final version of the paper.
Decision: Accept (Poster)