NN-Baker: A Neural-network Infused Algorithmic Framework for Optimization Problems on Geometric Intersection Graphs
Authors: Evan McCarty
Qi Zhao
Anastasios Sidiropoulos
Yusu Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: neural networks
graph combinatorial optimization problems

Abstract: Recent years have witnessed a surge of approaches to use neural networks to help tackle combinatorial optimization problems, including graph optimization problems. However, theoretical understanding of such approaches remains limited. In this paper, we consider the geometric setting, where graphs are induced by points in a fixed dimensional Euclidean space. We show that several graph optimization problems can be approximated by an algorithm that is polynomial in graph size n via a framework we propose, call the Baker-paradigm. More importantly, a key advantage of the Baker-paradigm is that it decomposes the input problem into (at most linear number of) small sub-problems of fixed sizes (independent of the size of the input). For the family of such fixed-size sub-problems, we can now design neural networks with universal approximation guarantees to solve them. This leads to a mixed algorithmic-ML framework, which we call NN-Baker that has the capacity to approximately solve a family of graph optimization problems (e.g, maximum independent set and minimum vertex cover) in time linear to input graph size, and only polynomial to approximation parameter. We instantiate our NN-Baker by a CNN version and GNN version, and demonstrate the effectiveness and efficiency of our approach via a range of experiments.

NN-Baker: A Neural-network Infused Algorithmic Framework for Optimization Problems on Geometric Intersection Graphs
Evan McCarty
Qi Zhao
Department of Computer Science University of Illinois, Chicago emccartyQuic.ee
Computer Science and Engineering Department University of California, San Diego qiz0320ucsd.
Anastasios Sidiropoulos Department of Computer Science University of Illinois, Chicago sidiropo@uic.edt
Yusu Wang
Halıcoğğu Data Science Institute University of California, San Diego yusuwanguucsd.c edu
Abstract
Recent years have witnessed surge of approaches to neural networks help tackle combinatorial optimization problems, including graph optimization problems. However, theoretical understanding of such approaches remains limited. In this paper, we consider the geometric setting, where graphs are induced by points in fixed dimensional Euclidean space. It turns out that several graph optimization problems can be approximated (in a bicriteria manner) by an algorithm that runs time linear in graph size n via framework that call the Baker-pan petter-prrdigm... key advantage of the Baker-paradign is that it decomposes the input problem into (at most linear number of) small sub-problems of bounded sizes (independent of the size of the input). For the family of such bounded-sizz sub- sub-problems, we can now design neural networks with universal approximation guarantees to solve them. This leads to a mixed algorithmic-ME framework, which we call NN-Baker that has the capacity to approximately solve a family of graph optimization problems (e.g, maximum independent set and minimum vertex cover) in time linear in the input graph size. We instantiate our NN-Baker by CNN version and GNN version, and demonstrate the effectiveness and efficiency of our approach via range of experiments.
Introduction
Many tasks in science and engineering can be naturally modeled by combinatorial optimization problems over graphs, such as maximum independent set, minimum vertex cover, minimum multi- way cut, maximum clique, and great effort devoted to developing efficient approximation algorithms. However, many such problems hard to approximate in the general setting as well: for example, it is known that the maximum independent set problem is Na-hard, and it is even NP-hard to approximate within n I-e on n-vertex graphs, for any fixed
These problems
often NP-hard. Hence there has been
[
the other hand, many of these hard problems admit PTAS in the geometric setting when the graphs are assumed to be induced by points in fixed-dimensional Euclidean space. Here, PTAS
Equul contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

(polynomial-tine approximation scheme) is a polynomial time algorithm which for any fixed E > 0, can approximate a maximization problem within a factor of (1 E) (or within a factor of (1 2) for a minimization problem). One most prominent example is the travelling salesman problem (TSP), where in general there is no PTAS available (and currently the best known approximation algorithm achieves factor of 3/2 a, for some > 10 10-36 (2).. However a PTAS, more specifically in this case a near linear time (1 + -aapproximation algorithm, was developed for the Euclidean TSP problem in a ground breaking work by Arora (3. The maximum independent set problem is known to remain NP-hard in the geometric setting 4.. but is known that it also admits a PTAS [5 6 77.
Nevertheless, for problems of large size, even these PTAS are still not practical, especially since many of them involve large constants that are exponential in some fixed parameter (e.g. having a term like n where (1 + E) is the approximation factor). In applications, practitioners often rely on handcrafted heuristic search strategies to find high-quality solutions.
Recently, there has been surge on using machine learning (ML) for combinatorial optimization problems; see the review paper by Bengio et al. [8] which also provides a nice categorization of different ways that a ML component may contribute to the combinatorial optimization problems. Earlier such approaches focus on several graph combinatorial optimization problems. including TSP, minimum vertex cover and maximum independent sets; see e.g..
[3 [5] [6].
More recently, there has been range of approaches developed to tackle more general mixed integer linear programming problems (MILP); e.g. [1 19 description of some related work.
20 21.
See Section for more detailed
In general, an ML framework can be trained solve an optimization problem in an end-to-end manner (e.g, [10 II 12 15 [6)). Alternatively, many recent approaches use ML module as a cegoorihhmicfrrmewoorr framework help make hopefully better (either in terms of quality or efficiency) decisions during the execution of this algorithm: such as using imitation learning or reinforcement learning to learn good policy decide which variable branch in a branch-and and-boundddd algorithm [18 20). Despite the tremendous progress in combining ML with optimization problems, theoretical understanding remains limited: Does proposed MI. pipeline have the expressiveness capacity to solve the combinatorial optimization problem exactly or approximately? What is a suitable model for input data distribution to talk about generalization?
component within a specific algorithmic
Consider the capacity question: While neural networks are known to have many universal approxi- mation results for real or complex valued continuous functions (or some other special families of functions), e.g, 22 23 24 255. combinatorial optimization problems, say finding the maximum independent set, cannot be easily modeled fit into such function approximation frameworks. Never- theless, a very interesting recent work [13] shows that for graph combinatorial optimization problems, the so-called vector-vector consistent graph neural networks (VVc-GNNs), can solve the same family of problems as the distributed local algorithms in the so-called porb-nuube models. Leveraging the literature in distributed local algorithms 26 27 this leads to several positive results on the capacity of GNNs for approximating minimum vertex cover or maximum matching problems with certain constant factors, however only for graphs with bounded degrees intuitively, the depth of the GNN will depend on the bound A on the maximum node degree of input graphs. Unfortunately, the connection to distributed local algorithms also leads to negative results: roughly speaking, these constant factor approximations for the special family of constant-degree graphs are the best that GNN can do for these graph optimization problems. See [3] for details.
Our work. The aforementioned results (on the capacity of GNNs) are for the case where GNNs are used to solve an optimization problem in an end-to-end manner, and other than the bound on max-degree, the input graphs are abstract graphs. In this paper, we advocate the study of using ML for optimization problems in the geometric setting where (graph) optimization problems are induced by points in fixed dimensional Euclidean space Rd. This is rather common scenario in practice, such as solving TSP in road networks spanned by cities in TR22, or solving maximum independent set in communication network spanned by sensor nodes in R /R (i.e, the unit-ball model that we will introduce in Section 2. Such graphs can also be the result of an embedding of an input arbitrary graph into a certain latent space. At the same time, the geometric setting brings special structures to the problem at hand, which an algorithm and also ML can then leverage.
In particular, using the maximum independent set (MIS) problem an example, we first propose what we call the Baker-pann paradigm in Section 2 which is an approximation framework for geometric
2

---

optimization problems inspired by Baker's work in (28]. We show that the Baker-paradin gives a bi-criteria approximation for the MIS in the Euclidean setting (Theorem (. The running time is only linear in the size of input point set, but exponential in terms of the parameters. This framework general and can be extended to several other geometric optimization problems (Section 2.3
A key advantage of our Baker- parkkrr-pradigmmmm is that it decomposes the problem into (at most a linear number of) small sub-problems of fixed size (independent of size of input graphs). For the family of such fixed-size sub-problems, we can now design neural networks with universal approximation guarantees to solve them. Using such a neural network to replace (Step-2) of our Baker-paradign we then obtain a mixed algorithmic-A ML framework, which we refer to as NN-Baker, that has the capacity to produce a bi-criteria approximation of MIS within any constant factor in near linear time (i.e, a bi-criteria PTAS); see Section 3. and Theorem 3.2 Note that while Theorem already gives a near-linear time bi-criteria PTAS for MIS, the constant involved in the time complexity is exponential in the approximation parameters, making it inefficient in practice. In contrast, the NN-Baker will replace the costly component by neural network component, and only call this neural network at most n times. Other than calls to neural networks, the time needed is (nn) where the constant contains only terms polynomial in the approximation paramters. The resulting mixed algorithmic-ML. framework is very efficient, as we show in Section 4
we provide two instantiations of the NN component for our NN-Baker: based on CNN and GNN respectively. We present a range of experimental results in Section 4 to show the effectiveness of both the CNN-Bake and GNN-Baker frameworks. Note that our NN-Baker can be used together with other SOA NN framework to solve combinatorial optimization problems and to further improve them (sometimes significantly). For example, we deploy different SOA GNNs for graph optimization problems to instantiate (Step-2) in NN-Baker, including TGS of 122 in the supervised setting, LwD of [6] in the reinforcement learning setting, as well as ErdÖs-GNN [15] in the unsupervised setting. We show that as the problem size increases, the performance of each original GNN decreases (the GNN is always trained and tested on problems of similar sizes). However, using GNN-Baker significantly improves the performance of the original GNN as the problem size increases This is partly because, independent of the problem size, in (Step 2) our GNN-Baker only needs to train and test the GNN component on small graph (of bounded size). Thus the trained GNN can adapt to the problem structure much better and require much fewer training samples.
In Section 3.2,
Our NN-Baker is, to our best knowledge, the first (bi-criteria) PTAS for combinatorial problem for an ML-bbaed approach (in terms of expressiveness). The recent line of work of using a ML. component (e.g GNN trained by imitation learning) to make branching decisions within the branch- and-bound algorithmic framework [18 20 may solve the exact problem given enough running time. However, the number of times the algorithm calls the NN component may be exponential in the input size. Instead, our NN-Baker framework calls the neural network (which has a bounded size) only a linear number of times. Our approach can open new directions to design NN-infused algorithmic frameworks with theoretical guarantees, by for example, leveraging divide and conquer paradigm and replacing certain algorithmic components by neural components.
1.1 More on related work
The idea of using neural networks to tackle optimization problems traces back to the 1980's. One of the most important frameworks in this direction the Hopfield Neural Network (HNN) 29 30 In particular, the HNN is feedback neural network with pre-specified weights (whose assignments depend on the optimization problem at hand), which encodes a dynamic system whose associated energy function characterize the optimization problem to be solved. To use it to solve an optimization problem, one starts with an initial state, and iterates till convergence.
As branch-and-bowe bound (B&B) has been proven to be a powerful framework in solving optimization problems, especially in MILP (mixed integer-linear programing) problems, researchers proposed different machine learning algorithms to boost B&B. [17] provided list of features of variables and
designed a learning- to-rnkkk model on selecting branching variables. [18] 20 21 developed GNN approaches to learn the policy of choosing branching variables after formulating MILP problems as graphs by imitation learning or reinforcement learning. Besides MILP problems, GNNs are also applied on graph combinatorial optimization problems. [ encodes the input graphs as sequences and takes an attention RNN to process the sequences. It can be used to compute convex hulls or 32 [6] takes reinforcement learning on graphs to solve routing
solve problems like TSP. 100
31
3

---

problems like TSP, and other problems like maximum independent set. [22 solves graph theory problems by supervised learning setup after solving set of cases as training set by existing solvers. while [5] introduces unsupervised approaches by designing loss function and training setup based that study
on objective functions and variables constraints. In addition, there are works [3 33 34
the power of GNN on solving different kinds of combinatorial optimization problems.
2 The Baker-paradign
We now propose a framework to obtain approximation algorithms for certain geometric optimization problems based on the work of Baker [28]. Baker's technique has been applied successfully to a plethora of optimization problems on planar graphs, including Maximum Independent Set, Mini- mum Vertex Cover, Minimum (Bdge) Dominating Set, Maximum Triangle Matching, Maximum H- H-Matching, TSP, and many others. Furthermore, the technique has been adapted the geometric setting (see [35] for a survey). From the geometric setting, the most relevant work to ours is (36), where the authors obtain approximation algorithms for maximum independent set and minimum vertex cover on unit disk graphs. We will show in the next section how neural networks can be used to obtain efficient algorithms within this framework. We begin with some definitions.
2.1 Preliminaries
We consider the geometric setting: i.c., combinatorial optimization problems on geometric intersection graphs. We present our methods for the case when the input is unit-ball graph, which is the intersection graph of unit balls in RR Specifically, graph nodes correspond to a set of balls of unit radius in Rdd and two nodes are connected by an edge iff the two balls intersect. Our approach can be extended to intersection graphs of several other geometric objects such as unit hypercubes, ellipsoids of bounded aspect ratio, and so on. For the sake of succinetness, we focus on the case of unit balls.
Approximations and bi-criteria relaxations. The algorithms we will develop are bi-criteria ap- proximations. The precise definition of a bi-criteria optimization problem depends on the space of feasible solutions. For concreteness, let us focus on the d-dimensional Maximum Independent Set of Unit Balls problem (denoted by d-MIS), for some fixed dimension d E N: The input to the d-MIS problem is a set of points X C R4, which corresponds to the set of centers of unit balls. Let Gx = (X, E') denote the intersection graph spanned by points in X, where (r., x²) E if the unit balls ball(z, 1) and ball(z', 1) intersect (meaning that || - z'|l I 2). The goal is to find the maximum independent set of Gx. which is equivalent to finding some maximum cardinality subset of disjoint balls centered at X. Let OPT(X) denote the size of maximum independent set for Gx. For any > 0, an algorithm is an a-approximaatio for d-MIS if on any input X c Rd,, it outputs some independent set Y C X, with OPT(X)/a S |Y| S OPT(X).
The bi-criteria version of the problem is defined as follows. Let e > O. We say that some Y C X (1 + e)-independent if the balls of radius 1/(1 + =) centered at the points in Y are disjoint; that is, for all p. q E Y. we have ||p 4/12 > 2/(1 + E). We denote the size of the maximum (1 + -)-independent subset of X by OPT [+ (X). For any a 2 1. 3 2 I, We say that an algorithm is (a,, -biic-riite approximation if on any input X Rdd outputs some 3--nddependett set Y C X, with OPT(X)/o S |Y| S (X).
Randomization. The algorithms we present for d-MIS randomized, and thus the size of the output is a random variable. We use the following standard extensions of the above definitions in this setting. We say that randomized algorithm a-approximation in expectation if any input X it outputs a solution Y with OPT(X)/e < E|Jy|] S OPT(X). We say that a randomized algorithm is (a, ---bi-criteria approximation in expectation if any input X it outputs solution Y with OPT(X)/a < Y| < (X).
2.2 Baker's paradigm for d-MIS
In this section, we describe our Baker-paradigm to obtain an approximation algorithm for d-MIS. We will later see that the same method can be extended to several other optimization probelms on geometric intersection graphs. Let e > 0 be arbitrarily small but fixed. The algorithm proceeds the following steps: See Figure for an illustration.

---

Input points X
call C and Xe
discestiaation into pixels
solvve MIS Vc GRa
MIS Yo E Xee
f2
(Step 1)
(Step 2) of Baleer's paradigm for each cell
Figure I: Illustration of Baker- lakkerp in 2D. First we put a randomly shifted grid on input points X. Consider a C, empty dots close boundary are X2. then snap points in Xc),Xć into pixels a second level grid; and those dark (non-empty) pixels form Xc. The MIS Vc (bigger orange nodes) then computed the graph Gxe spanned by dark pixels Xc; note that for clarity of illustration, in the 4-th picture we use the center of each pixel to represent this pixel (instead of its bottom-left comner. The solution Yc is then converted MIS Yc C Xc \ X In (Step 3), the union of all Yc for cells is returned as the final MTS.
Algorithm Baker-MIS: The input is set of points X C IRd, with |X| n, where each point in X the center of a unit ball. The algorithm has three steps.
Step 1: The randomly shifted grid. Let I be an axis axis-parallel hyper-grid, where each cell is a d-D
axis skis-parallel hypercube of side-length 2d Specifically, let I U Usezth, 2d es). where 61, ed ed is the standard orthonormal basis, and for [1,d] dl, h4 is the (d-1)-D hyperplane that passes through the origin and is orthogonal to eq. Pick E [0, 2d/s)d uniformly at random. Let + T denote the grid obtained by shifting by the vector т.
Step 2: Bi-criteria solution for the problem locally on each cell. Now given cell C of I + T. for any P C Rd. let Pc = P n C denote the restriction of P within C. Let X' be the set of centers of the unit balls in X that intersect the shifted grid + (i.e., these are points within distance- 1 to the hyperplanes (or gridlines for the 2D case) in the grid). Let ó > 0, and set 8' = 5/vd. We partition each cell C of r + 7 to a d-dimensional grid of pixels, where each pixel a d-dimensional hypercube of side length 8'. We snap each point in X X' to the corner of the pixel containing it that is closest to the origin, thus obtaining the set X, ignoring multiplicities; that is
X
U P
{(8'L
P1 8
80
Pd 8
1)}.
Now for each cell of T + Nc (the restriction of X C) consists of the bottom-left corners of those pixels containing some points in X X Let G x be the intersection graph the radius-(1 - 5) balls with centers in Xc. Note that the size of Xc is at most ( (24) )d and thus the graph G &. is of bounded size. Furthermore, note that any independent set of G&e can be of size at most = Va( 2d yd (due to a simple packing argument). where Va denotes the volume of the d-dimensional ball of radius (1 8). We can then compute the maximum independent set Yc S Xc in Gx² by brute-force enumeration all subsets of X of cardinality at most s, and returning the maximum cardinality subset that is independent in G Finally, we compute Yc Xc by mapping each point p E Yc to an arbitrary point p E Xc \, Xt6 that lies in the pixel that ò represents.
Step 3: The final solution
Uc Yc, the union of MIS returned within all non-empty cells.
The proof of the following theorem can be found in the Supplement.
Theorem 2.1. Let E, The algorithm Baker-MIS is a (1 (()))
approxi- mation in expectation for MIS. On input of size the algorithm runs in time (L/(=d))(d/a)om)
Recall that our algorithm removes those points X' within distance the grid. Intuitively, we need randomly shifted grid so that this X' does not contain too many points from an optimal maximum
5

---

independent set in expectation. Note that in practice, we can further improve the quality of the output: Specifically, currently, all points within distance 1 to the shifted grid I (i.e, X' C X) are removed. The reason is to ensure that solutions (max-independent sets) of neighboring cells do not conflict each other. We can add some of those points from X' back to the solution Y as long as they do not cause conflict (i.e, within distance 2) to any points in Y. We can do so in a greedy manner in practice to obtain an even better solution. Our theorem above holds for this greedily improved solution as remains an independent set and is superset of YY
Removing the Bi-Criteria Condition. We remark that directly using the original Baker idea one can in fact obtain (1 + >)aaprroximation for MIS (instead of a bi-criteria approximation), by not having a second-level discretization in each cell in (Step 2). This is effectively a randomized version of the algorithm from [36.. The standard details can be found in the Supplement. As shown in the following theorem, the price to pay is that the dependency of time complexity on increases from previous n (i.e, linear) to (1)))) which is significant.
Theorem 2.2. We can modify Baker-paradige to provide a (1 for MIS. On input set of size n, this modified algorithm runs in time n (1/))00
in expectation
2.3 Other graph optimization problems
We now briefly discuss how the above general framework can be extended to other problems on unit ball graphs, with only minor modifications. We describe some representative such problems.
Minimum vertex cover. In the Minimum Vertex Cover (MVC) problem, we are given a graph G and the goal is to find minimum cardinality set U C V(G), such that all edges in G have at least one endpoint in U. In the case were G is a unit ball graph in Rd, this problem can be solved by modifying the Baker paradigm as follows. In Step 2, we enlarge each cell T + T by increasing its side length to 2 + 2d/e. Thus, any two adjacent cells have intersection of width 2, and some points in X may fall in multiple cells. By the linearity of expectation, it follows that the expected number of points in any optimal solution that fall in multiple cells (counting multiplicities) is at most =(OPT(X)] ). Therefore, by solving the problem independently on each cell and taking the union of all the solutions we obtain (1 + -pprroxxie solution for the initial problem X. Discretizing each cell into further pixels gives rise to a more efficient, but bi-criteria approximation.
Maximum Acyelic Subgraph, Planar Subgraph, and F-Minor Free Subgraph. In the Maxi- mum Acyelic Subgraph problem we are given graph G and the goal is to compute subgraph of G with maximum number of vertices that is acyclic. It follows by the linearity of expectation, that the expected number of balls in any optimal solution that intersect the randomly shifted grid is at most =|OPT(X)] Thus, solving the problem on each cell and taking the union of all the acyclic subgraphs found, results in a (1 + -paapooxxee optimal acyclic subgraph of the input. (Similar to MVC, discretizing each cell into further pixels gives rise to a more efficient, but bi-criteria approximation.) The exact same argument works also for the Maximum Planar Subgraph problem, where the goal is to find subgraph with maximum number of vertices that is planar. Finally, the same argument extends to the case of the more general Maximum F-Minor Free Subgraph problem, where the goal find a subgraph with maximum number of vertices that does not contain as a minor any of the graphs in a fixed family F. We note that this problem generalizes the Maximum Acyclic Subgraph problem (when F contains the triangle graph) and the Maximum Planar Subgraph problem (when F contains K₂ and K3,3).
3 A NN-Baker framework
3.1 Infusing neural network inside the Baker-paradigm
Instead of solving (Step 2) of Baker-paradigm in brute-force manner, we can replace it by a neural network, and we refer to the resulting generic paradigm as NN-Baker. Roughly speaking, we will replace the exact computation of a MIS in Step of algorithm MaS by neural network. More specifically, consider the following:
Step 2'.
We follow the same notations as in Step 2 of algorithm Baker-MIS. For each cell C of the grid I + 7, we proceed as follows. Recall X is set of corners of all non-empty pixels

---

(i.e, containing some point from X \ X') in C. Let Wc be the set of all pixels in C, and let
Pc be the powerset of c. Let fMIS Pc Pc be such that for all Z Pc, f (Z) is some optimal solution to the MTS problem on input Z w.r.t. radius (1 - 0); that is, fMus maps an instance to an optimal MIS solution for the intersection graph formed by radius (1 - 5) balls. Since every point in Xc X is at distance at most 5 from some point in Xc, it follows that fxus(Xc) is a (1,1+ + ((6))-bi-criter)
solution for the set of points in Xc \ X (see the argument in the proof of Theorem 2.1 in Supplement). We can view faus as mapping between indicator vectors of subsets of Wc: i.c. fxis: {0, 1 + {0, 13 where k: = |Pcl 2(24/(=6)) Let JMIS [0, 10 - [0, 1] be any continuous extension of fMIs. We then approximate ÍMIS by a function gv [o, 11 - [0, 1] as computed by a neural network A. We round coordinate-win
the output of IMIS to vector in {0, 1}%, by setting every value greater than 1/2 to 1, and all other values to O. We thus obtain the indicator vector of some Yc C Wc. Alternatively, we can produce discrete solution by the following greedy strategy: We sort the points in Wc in non-increasing order of their values in the vector (Xc), and take Yc to be maximal prefix of this sorted order that forms an (1 + -ideeeennee set in G G&c- Finally, we compute Yc S Xc \ X by mapping each point P E Yc to any point p E Xc within the pixel represented by p.
Universal-Baker We now give a theoretical instantiation of NN-Baker using the neural network obtained by the following universal approximation result.
Theorem 3.1 (Cybenko 122). Let a be any continuous sigmoidal function. Let m E N, and let C be a compact subset of TR m. Let J C + IK be continuous function, and 7 > Then, there exists
N E N, 01.....,0. ON E R2 y1, yN E RRm, and O,,...,0, ON E IR, such that the function C - TR, with g(x) = 1 0: x + 0,), satisfies supaec (g(x)= fxx) < %
Using the neural network given by the above result, we can then argue that our NN-Baker has the capacity (expressiveness) of solving MIS problem (for unit-ball graphs) in a bi-criteria approximation. The simple proof of this theorem can be found in the Supplement.
Theorem 3.2. Let e, 5 > 0. There exists N = Níe, 5, d), such that the following holds. Suppose that the function 9N- in Step 2' of the NN-Baker framework is computed by the neural network N given by Theorem 3.7 with a single hidden layer of size N. Then, the resulting algorithm is (1+ 1 + ( -bi-criteriia approximation in expectation for d-MIS, and it will call this (same) neural network al most n times where n is the number of points generating the input graph.
Remark 3.1. A similar statement to Theorem 3.2 holds for the Vertex Cover problem, yielding (1 (()), + -biic-iii approximation using the modifications discussed in Section 2.3
3.2
Instantiation of NN-Baker
Above we introduce generic NN-Baker framework and a theoretical instantiation. We now provide two specific practical instantiations of this framework: CNN- and a ENN-Baker where (Step 2') of NN-Baker (or equivalently, (Step 2) of our Baker-paradigm is implemented by a CNN or by a specific GNN. We provide details below. Specifically, recall that the input is a set of points
X C Rd, and for randomly shifted grid 1 + r, let us focus on a specific grid cell C P + 7. Recall that in NN-Baker, given C and Xc, we will use neural network to compute a subset of Ýe which ideally approximates a maximum independent set of the (unit-ball) geometric intersection graph G xx
spanned by Xc. The set Ec (of pixels) is further relaxed to a subset Yc C Xx as an independent set solution within cell C.
CNN-Baker. We can view the set of pixels in a cell as an image of size 3d= = x 3 where 3 3- O ) Specifically, given grid cell C and subset of pixels Z, we detine the Iz over 8d such that Iz (p = if p E Z and I2[p] = otherwise. We call such an image an induced image by C. and denote the space of images of size by SpIm. Now, in (Step 2') of NN-Baker we given subset of pixels =)& within a cell C, and aim to compute a subset Fc S Xc that forms an independent set for the unlt-ball graph spanned by Z = Xc. Our CNN-Baker uses a CNN architecture Ne to compute a map INC SpIm + SpIm, which takes as input Ig. and outputs Ig.- Since the input and output are both images of the same size, this problem can be also viewed as an image
7

---

X6 \ X in cell
2' Yc
CNN (UNes)
(Pt)
01.
GNN model
0.7
0.35
0.6
0,96
&
initial mode foatures
last layer node Jeaturess
7'=
Figure 2: Given the set points Xc X contained cell C, the top row shows the processing of by a CNN component as in CNN- Baker, while the bottom row shows for a GNN component GNN-Baker. Ye in the figure corresponds to the set of pixels containing points from Yc.
segmentation problem, and thus we can use a UNet architecture for the map Nc. More specifically, the input is a binary image Xx.- and the output is grayscaled image 7' where the value at each pixel, [[d E [0, 1]. indicates the likelihood that this pixel belongs to maximum independent set in the geometric intersection graph &c.
In (Step 2*) of NN-Baker, we describe an alternative greedy approach convert this likelihood map to a subset of points Yc C Xc \ X as the output MIS. However, in our implementation for both CNN-Baker and -NNeBB we will make slight modification: particular, note that the output from (Step 2') will be (1 + ((()))indeeenden subset of Xc. In practice, we would like to guarantee that we output valid MIS for Xc (i.e, any two points in our output Yc should be at least distance apart). We thus follow the greedy approach as outlined in (Step 2') but with small modification: We sort all pixels in Z = Xc in decreasing order of their pixel values, and assume Z = {21,- ze} this sorted list. We then inspect them one-by-one in order. At the beginning. initialize an output set Y' be empty. Then in the i-th iteration, let Y4 be any point from Xc \ X in pixel 2;. If ys is independent to all points in Y" (i.e, it more than away for all points in Y"), add to Y'; and otherwise, do nothing. In the end after l iterations, pixels) which guaranteed to be an independent set for the unit-ball graph spanned by points in Xc. Set Yc Y' and return the independent set for this call C. This will further guarantee that the final output Uc Ye computed by our CNN-Baker will be a valid MIS for the unit-ball graph spanned by input points X.
obtain set of Y" C Xc X points (not
GNN-Baker. For GNN-Baker, we instead directly use the unit-ball graph GR. as input, with the initial node feature n² (v). At the last L-th layer, the node feature y=²(v) gives the likelihood that is in the maximum independent set. We then retrieve an independent set Yc by the same greedy approach for the case of CNN-Baker. For the specific choice of the GNN architecture, we can any of the
339. GAT [40], and VVG-GNN [13] In our later experiments, we will use TGS 222 and LwD 16 our GNN-Bake framework, these are state-of-thed thee-arrt (SOA) approaches specifically designed for graph combinatorial problems. (Our experiments show that using general purpose GNN has much worse performance than TGS and LwD.) In particular, TGS, supervised learning approach, takes GCN to process reduced graphs and use tree search approach label nodes whether they are an independent set or not. LwD reinforcement-leammee learning based, and designs policy network and value network each MIS problem state with GraphSAGE architecture. We will also use the Erdös-GNN [15] designed for optimization problems in the ansupervised setting. Erdōs-GNN takes multiple GIN layers followed by GAT layer to learn graphs' distribution. designs differentiable loss function based on expectations of optimization problems objective functions and probabilistic penalty function.
existing models, such as GCN 377. GraphS AGE 38 GIN

---

1.0
T05
4.35
Ratin to grmund
sizes fnumher moddes)
Figure 3: Results Erdos-GNN, TGS and LwD on MIS problems with different sizes of graphs 2D setting. We report the ratio to ground truth computed by KaMIS.
4 Experimental results
We present results for d-MIS here. More results, including for minimum vertex cover (MVS), can be found in the Supplement. We consider 5 families of unit-ball graphs: (2D-dense) consists of a set of graphs, each with points distributed uniformly on 2D rectangular region with around 40K - 50K points. (2D-sparse) consists of set of graphs, each with 40k 50k points distributed uniformly on 2D rectangular region four times larger than the dense region (2D-Gaussian) consists of graphs each spanned by points sampled from a "raussian-mixtur distribution with 40K 50K points over the same region size as the dense region. (3D) consists of graphs each spanned by points sampled from a 3D region. (Torus-4D) consists of graphs each spanned by points sampled from torus embedded in RRd (see Supplement for details).
First, note both CNN-Baker and GNN-Baker return valid MIS for the input unit-ball intersec- tion graphs (as detailed in the implementation of CNN-Baker). To report accuracy, we will need ground truth solutions. However, computing exact solutions for all our test cases is computationally intractable. Instead, we use the output of a SOA solver KaMIS 41 as the ground truth solutions, and report the average ratio of MIS obtained over this ground -tutth MIS sizes as a metric for accuracy (so the larger this ratio is the better). To validate the accuracy of KaMIS on our training and test data, we compared against an exact solution 42 for 20 test sets and found that the accuracy of KaMIS exceeded 99.9% of the optimal solution in all cases. On the other hand, regardless the accuracy of KaMIS, since we are taking the ratio as the metric for accuracy, higher ratio is always better.
Before we show results CNN- and GNN--Baerr we first show how the SOA GNN-based approaches, TGS [12]. LwD (66 and Erdōs-GNN [5). all of which are specifically designed for graph optimization problems (see discussions in Section 3.2), perform as the size of graph increases. Here for each target size, 1000 graphs spanned by points sampled from the same dense distribution in 2D are used for training, then tested on 100 graphs of roughly the same target size. As shown in Figure the accuracy decreases as the size of (geometric) graphs increase.
Table 1:
The ratio of MIS results from different GNNs, GNN- Baker approaches and K-Baker approach to ground truth. (Larger values are better.)
UNetBaker
Erdós
ErdósBaker
TGS
TGSBaker
LwD
LwDBaker
2D-dense
0.915
0.834
0.923
0.915
0.936
0.917
0.955
2D-sparse
0.919
0.822
0.917
0.909
0.931
0.908
0.926
2DGaussian
0.917
0.769
0.848
0.905
0.927
0.911
0.925
3D
0,856
0.930
0.924
0.948
0.902
0.954
Torus-4D
0.812
0.926
0.923
0.937
0.910
0.937
NN-Baker setup. For each of the five setups, we train on 1000 graphs and test on 200 graphs each containing between 40k- 50k points. However, inside our NN-Baker framework, the input domain is partitioned into cells of side-length 12.8, and each cell is further partitioned into 128 x 128 pixels (each with side-length that the training set for the NN component involved contains only small graphs restricted to such cells. In the end, each training graph consists of around 400 points for the cases of (2D-dense). (3D) and Torus-4D) and around 100 125 points for the case of (2D-sparse). The size of each small
0.1). In other words, each cell can be viewed a 128x 128 image. This means

---

training graph for Gaussian case is non-uniform. For CNN-Baker, we apply UNet which reduces the input 128x 128 image to an 8x8 image after 4 down-scaling layers, each of which consists of two convolutional layers, a dropout layer and max pooling layer. From the 8x8 image, there are then 4 upsampling/concatenaaii
layers bring the size back to 128x128. This model is denoted by UNet- Baker in Table T For GNN-Baker, as mentioned in Section 3.2 we test TGS- "GG--Baker, LwD-Baker, and Erdös-Baker. For each individual neural network involved, we use the same training setup and nyperparameters as those in their official implementations. For LwD and Erdōs-GNN, we use node degree as initial node features, while for TGS, we simply use a constant vector. The accuracy of these different methods over the 5 families of graphs shown in Table I The number of parameters for these GNN-Bakerg range from 50K to 600K, while the UNet-Bake uses around 80M parameters.
As shown in Table L using Baker framework consistently improves the performance of these SOA neural networks on geometrie MIS problems. The improvement over the unsupervised Erdós- GNN (i.e, Erdós-Baker vs. Erdos-GNN) is particularly significant. We remark that we have also experimented with using a simple multi-layer fully connected NN (i.e., a multi-layer version of the NN used in Theorem 3.2) to instantiate our NN-Baker, and the performance (under similar number of parameters as our UNet-Baker) is much worse, between 70%-80%. We can also use NN-Baker trained on one type of graphs (e.g, 2D-dense) but apply it to graphs from the other families to study the generalization of the resulting framework we observe that the accuracy decreases but still improves the non non-Baker version. See the Supplement for these more results, well as the performance of -aker for minimum vertex cover problem.
Timing. To show that the NN-Baker is efficient compared to a traditional Baker paradigm, we compare the runtime of our models against a non-neural network based approach. For this, we use KaMIS as our solver for each cell, and call the resulting framework K-Baker. In Table we show the average time taken to solve a problem with 40k-50k points. We show the runtime of K-Baker set to achieve similar performances to UNetBaker in the table. If we set similar runtime to UNetBaker, then K- K-Baker's performances on 2D-dense, 2D-sparse and 2DGaussian are 0.753, 0.672 and 0.674, which are much poorer than our NN-Baker.
Table 2: Average solve times of KaMIS, NN-Baker and K-Baker (seconds)
KaMIS
K-Baker
UNetBaker
ErdösBaker
TGSBaker
LwDBaker
2D-dense
3385.1
415.19 402.57 420.83
18.06
32.36
15.72
44.55
2D-sparse
2468.8
59.97
68.95
33.74
81.06
2DGaussian
3166.7
58.05
47.45
28.38
62.59
5
Concluding remarks
The advancement in neural network architectures and their potential to adapt to the structure and input distribution of a problem in a data-driven manner, have brought new ways to tackle traditionally challenging tasks, such as graph optimization problems. In this paper, we advocate two points of view: (1) Problems in geometric settings can provide structures that both algorithms and neural networks can leverage; for example, they can help to decompose problems into local versions of bounded size and thus lead to more effective NN components. (2) Infusing NN + learning into an algorithmic paradigm can lead to more powerful framework for hard problems, potentially with theoretical guarantees. While the latter is a view that has already attracted momentum in recent years, our work provides new perspectives (e.g, the decomposition into bounded-size sub-problems) together with some theoretical guarantees, and we show that the resulting method is indeed more powerful empirically too. Our present algorithms currently apply to only geometric intersection graphs. Nevertheless, we believe that such ideas go beyond the geometric setting which we hope to explore in the future, such to frameworks to obtain algorithms for graphs with bounded rretwwidth. Indeed, the algorithms and theoretical computer science community has developed many beautiful algorithmic paradigms that may be suitable be infused with NN+ML ideas. Finally, to our best knowledge, this work does not have direct negative societal impacts.
This work in part supported by the National Science Foundation (NSF) under grants CCF-1815145, -IS- 1815697, and OCF-2112665.
Acknowledgement.
10

---

References
[1] Johan Håstad. Clique is hard to approximate within n 1- Acta Mathematica, 182(1):105-142, 1999.
[2] Anna R Karlin, Nathan Klein, and Shayan Oveis Gharan. A (slightly) improved approximation algorithm for metric tsp. arXiv preprint arXiv:2007.04409 2020.
[3] Sanjeev Arora. Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. Journal of the ACM (JACM), 45(5):753-782, 1998.
[4] Robert Fowler, Michael S Paterson, and Steven L Tanimoto. Optimal packing and covering in the plane are np-complete. Information processing letters, 12(3):133-137 1981.
[5] Timothy M Chan. Polynomial-time approximation schemes for packing and piercing fat objects. Journal of Algorithms, 46(2):178-189, 2003.
[6] Thomas Erlebach, Klaus Jansen, and Eike Seidel. Polynomial-time approximation schemes for geometric intersection graphs. SIAM Journal on Computing, 34(6);1302-1323, 2005.
[7] Timothy M Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. Discrete & Computational Geometry, 48(2):373-392, 2012.
[8] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' d'horizon. European Journal of Operational Research, 2020.
[9] Oriol Vinyals. Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Proceedings of the 28th International Conference on Neural Information Processing Systems- Volume 2, pages 2692-2700, 2015.
[10] Irwan Bello, Hieu Pham, Quoe Le, Mohammad Norouzi, and Samy Bengio. Neural combi- natorial optimization with reinforcement learning. 5th International conference on Learning Representations Workshop Track, 2017.
[11] Hanjun Dai, Elias B Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Proceedings of the 31 International Conference on Neural Information Processing Systems, pages 6351-6361, 2017.
[12] Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolu- tional networks and guided tree search. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 537-546, 2018
[13] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. Proceedings of the 33rd International Conference neural Information Processing Systems, 2019.
[14] Thomas Barrett, William Clements, Jakob Foerster, and Alex Lvovsky. Exploratory combina- torial optimization with reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3243 3243-3250, 2020.
[15) Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. In Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
[16] Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning what to defer for maximum in- dependent sets. In International Conference on Machine Learning, pages 134-144. PMLR, 2020.
[17] Elias Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.

---

[18] Maxime Gasse. Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. In Advances in Neural Information Processing Systems 32, 2019.
[19] Aaron Ferber, Bryan Wilder, Bistra Dilkina, and Milind Tambe. Mipaal: Mixed integer program as a layer. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 1504-15111 2020.
[20] Prateek Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigonda, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. Advances in Neural Information Processing Systems, 33, 2020.
[21] Vinod Nair. Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012. 2020.
[22] George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
[23] Allan Pinkus. Approximation theory of the mlp model in neural networks. Acta Numerica, 1954,-195, 1999.
[24] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. Computational capabilities of graph neural networks. IEEE Transactions on Neural Networks, 20(1):81-102, 2008.
[25] Jorge Pérez, Javier Marinković, and Pablo Barceló. On the turing completeness of modern neural network architectures. In International Conference on Learning Representations, 2018. 8.
[26] Dana Angluin. Local and global properties in networks of processors. In Proceedings of the twelfth annual ACM symposium on Theory of computing, pages 82- 23, 1980.
[27] Matti Ästrand, Patrik Floréen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, and Jara Uitto. A local 2-approximation algorithm for the vertex cover problem. In International symposium on distributed computing, pages 191-205. Springer, 2009.
[28] Brenda S Baker. Approximation algorithms for np-complete problems on planar graphs. Journal of the ACM (JACM), 41(1):153-180, 1994.
[29] John Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the national academy of sciences, 7968):2554-2558, 1982.
[30] John Hopfield and David W Tank. "neural" computation of decisions in optimization problems. Biological cybernetics, 52(3):141-15,, 1985.
[31] Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Marisn Rousseau. Learning heuristics for the tsp by policy gradient. In International conference on the integration of constraint programming. artificial intelligence, and operations research, pages 170-181. Springer, 2018
[32] Marcelo Prates, Pedro HC Avelar, Henrique Lemos, Luis C Lamb, and Moshe Y Vardi. Learning to solve up-complete problems: A graph neural network for decision tsp. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4731-4738, 2019.
[33] Keylu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? International Conference on Learning Representations, 2020.
[34] Andreas Loukas.
What graph neural networks cannot learn: depth vs width. In International Conference Learning Representations, 2019.
[35] Sanjeev Arora. Approximation schemes for np-hard geometric optimization problems: A survey. Mathematical Programming, 97(1):43-69, 2003.
12

---

[36] Dorit S Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems image processing and vlsi. Journal of the ACM (JACM). 32(1):130-136, 1985.
[37] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017.
[38] William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. In Proceedings of the s1 International Conference on Neural Information Processing Systems, pages 1025-1035, 2017.
[39] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019.
[40] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations, 2018.
[41] Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F. Werneck. Finding near-optimal independent sets at scale. J. Heuristics, 23(4):207-229, 2017.
[42] Mingyu Xiao and Hiroshi Nagamochi. Exact algorithms for maximum independent set. Infor- mation and Computation, 15::126-466 2017.
13


Reviews:
[{"review_id": "y8-Wh6ZEgzN", "reviewer": "Reviewer_88CS", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Strengths\n\n* 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.\n* While the method is principled from the theoretical perspective, the resulting strategy is simple and intuitive.\n* 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.\n* Figures 1 and 2 describe the method well.\n\n# Weaknesses\n\n* 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.\n* 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They are discussed in Section 5.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "MKuulgtU99M", "reviewer": "Reviewer_JP57", "summary": "The paper proposes a polynomial time approximation scheme that can utilize neural networks\nto efficiently solve combinatorial problems like maximum independent set and minimum vertex cover\non geometric interesection graphs. The method decomposes a problem instance into multiple smaller\ninstances of bounded size located on a grid, which are then solved with the help of a neural network. The neural network\nis either a graph neural network applied on the intersection graph or a CNN that treats the problem\nas a segmentation task. To discretize the output of the network the authors use a greedy \nrounding strategy that preserves feasibility.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n### Strengths:\n- The idea of reducing a problem to instances of bounded size in order to obtain an approximation guarantee in an ML setting is interesting.\n- The use of neural networks (NN-Baker) seems to provide an improved theoretical result over the standard Baker approach, which is nice.\n- Figures help build intuition and improve the readability of the paper considerably.\n- Related work is sufficiently discussed. Experiments include models from recently published works.\n- Seems to consistently improve the performance of models from the literature.\n- Nice experiment on generalization.\n\n\n### Criticism, comments, and questions:\n\n- In terms of writing quality, there are plenty of typos and minor mistakes.\nHere are some examples:\n\nline 53: \"Does a proposed ML pipeline has the expressiveness capacity...\"\n\nline 115: \"Our NN Baker framework instead calls the neural network involved only linear time.\"\n\nText in Figure 1: \"(Step 2) of Baker's paradigmfor each cell\"\n\ntable 1 caption: \"...approaches to groud truth\"\n\nline 217: \"Detials ae in the supplement.\"\n\n\nlines 231-232: is at most and \\epsilon|OPT(X)|.\n\nline 349: \"For each of the five setup,\"\n\nline 366-367: \"As shown in Table 1, using Baker framework consistently improve the performance of these SOA\nneural networks on geometricMIS problem.\"\n\nline 374: \"(including variance of these accuracy)\"\n\nline 378-379: \"The advancement in neural network architectures, and their power in potentially better adapting to\nproblem structure and input distribution in a data-driven manner, have brought new ways...\"\n\n- Another comment on the structure of the paper:  Currently, you explain the greedy discretization in the CNN-Baker section, \nbut since you also use it in GNN baker it would improve the clarity of the text if you described it in a separate paragraph.\n\n- In the introduction, to motivate your approach you mention the existence of\nreal-world problems that involve geometric intersection graphs. Your experiments are\non synthetic randomly sampled instances. It would be nice to include experiments on real-world data.\n\n- While we can see that the NN-Baker method performs well on large graphs, we are not given information about\nhow 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\nwould help build a stronger case for your framework. \n\n- In the paper, you claim that your framework extends to other problems like maximum acyclic subgraph.\n Having experimental results on at least one of them would help improve the paper's experimental section, both\nin terms of novelty and in terms of providing evidence for your theoretical results.\n\n- Minor detail regarding Theorem 3.2: The result from 3.1 gives you a universal approximation result for a function \nthat maps a vector to a real number, while the function you want in Step 2' of NN-Baker \nis $g_\\mathcal{N}: [0,1]^k \\rightarrow [0,1]^k$. The result from 3.1 extends to vector-valued outputs but it should\nbe explicitly stated for the sake of clarity.\n\n- An ablation study on NN-Baker would also help illustrate its benefits over the non-neural version.\n  For instance, is it possible to compare with the non-neural Baker framework, or is it too slow because of the brute force enumeration?\n  Could you replace the subset enumeration in step 2 with a maximum independent set heuristic? I understand that you \n  may lose the approximation guarantee that way, but heuristics can perform very well so it is important\n to understand whether the neural networks are indeed beneficial in practice.\n\n- 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\nas 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.\n\n### Recap: \n\nOverall, I find the contributions and the direction of the paper interesting.  Theoretical guarantees are particularly appealing\nin the context of machine learning. \nHowever, 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. \n\nFor now, I will give the paper a 5 but I am willing to adjust my grade after the rebuttal.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have discussed the limitations of their work sufficiently.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "3u1Y3tVXK38", "reviewer": "Reviewer_YGgd", "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?\n\nThe 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. \n\nTheoretically, 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.\n\nExperimentally, 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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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?\n\nThe 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. \n\nTheoretically, 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.\n\nExperimentally, 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.\n\n\nOverall, 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. \n\nNonetheless, the paper is of high quality and so I lean towards accepting. I am eager to hear the authors' thoughts on my criticisms. \n\nOther questions/comments:\n- 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.\n\n- 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?\n\nMinor:\n- line 6: \"algorithm that is linear in graph size\" --> \"algorithm that runs in time linear in the graph size\"\n- 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.\n- line 84 \"exponential in terms of the parameters\", what parameters?\n- Figure 1, \"paradigmfor\" --> \"paradigm for\"\n- Figure 1, \"$X_C/X_C^{'}\", should that be a backward slack instead to denote set difference?\n- line 159, shouldn't it be $\\alpha > 1$, as in line 164?\n- line 160, the cardinality of the set $Y$ should be used in the in the inequalities, as you do in line 166.\n- 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$.\"\n- 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.\n- line 217: \"Detials\" --> \"Details\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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)