On the Power of Small-size Graph Neural Networks for Linear Programming
Authors: Qian Li
Tian Ding
Linxin Yang
Minghui Ouyang
Qingjiang Shi
Ruoyu Sun
Venue: NeurIPS 2024 poster (2024)
Keywords: Learning to optimize
graph neural network
linear programming
gradient descent
efficiency
Primary area: graph_neural_networks
TL;DR: We show that polylogarithmic-depth constant-width GNNs are sufficient to solve packing and covering LPs.

Abstract: Graph neural networks (GNNs) have recently emerged as powerful tools for addressing complex optimization problems. It has been theoretically demonstrated that GNNs can universally approximate the solution mapping functions of linear programming (LP) problems. However, these theoretical results typically require GNNs to have large parameter sizes. Conversely, empirical experiments have shown that relatively small GNNs can solve LPs effectively, revealing a significant discrepancy between theoretical predictions and practical observations. In this work, we aim to bridge this gap by providing a theoretical foundation for the effectiveness of small-size GNNs. We prove that polylogarithmic-depth, constant-width GNNs are sufficient to solve packing and covering LPs, two widely used classes of LPs. Our proof leverages the capability of GNNs to simulate a variant of the gradient descent algorithm on a carefully selected potential function. Additionally, we introduce a new GNN architecture, termed GD-Net. Experimental results demonstrate that GD-Net significantly outperforms conventional GNN structures while using fewer parameters.

On the Power of Small-size Graph Neural Networks for Linear Programming
Qian Lil2", Tian Ding! Linxin Yang2*' Minghui Ouyang", Qingjiang Shi;, Ruoyu Sun 12.M Shenzhen International Center For Industrial And Applied Mathematics, Shenzhen, China
Shenzhen Research Institute of Big Data, Shenzhen, China School of Data Science, The Chinese University of Hong Kong, Shenzhen, China Peking University, Beijing, China Tongji University, Shanghai, China
Abstract
Graph neural networks (GNNs) have recently emerged powerful tools for ad- dressing complex optimization problems. It has been theoretically demonstrated that GNNs can universally approximate the solution mapping functions of linear programming (LP) problems. However, these theoretical results typically require GNNs have large parameter sizes. Conversely, empirical experiments have shown that relatively small GNNs can solve LPs effectively, revealing a significant discrepancy between theoretical predictions and practical observations. this work, we aim to bridge this gap by providing theoretical foundation for the effec- tiveness of smaller GNNs. We prove that polylogarihmiicdeethh. constant-width GNNs are sufficient to solve packing and covering LPs, two widely used classes of LPs. Our proof leverages the capability of GNNs to simulate variant of the gradient descent algorithm on carefully selected potential function. Addition- ally, we introduce new GNN architecture, termed GD-Net. Experimental results demonstrate that GD-Net significantly outperforms conventional GNN structures while using fewer parameters.
Introduction
Learning to Optimize (L20) has emerged as compelling research area, leveraging machine learning techniques to enhance the efficiency of optimization processes. Unlike traditional theory-driven optimization methods, L20 approaches are primarily data-driven, learning optimization strategies from existing problem instances. This new paradigm has yielded notable advancements in both continuous optimization
22 and combinatorial optimization 21
Recently, graph neural networks (GNN) have become increasingly popular the field of L20 6 GNNs are class of neural networks specifically designed to process and analyze data structured as graphs, leveraging the relationships between nodes to perform tasks such as node classification, link prediction, and graph classification 35 Due to their properties of permutation equivariance and
natural adaptation to varying input dimensions, GNNs are well-suited for graph-related optimization problems such minimum vertex covering [30] and traveling salesman [13]. Recent research has demonstrated that GNNs can effectively accelerate the solving process for both linear programming (LP) and mixed integer linear programming (MILP) problems, which are among the most important and widely applied types of optimization problems. For instance, Li et al. [17] proposed a GNN- reformulation method for LP enhance the solver performance. Furthermore, Chen et al. 8 and
"These authors contributed equally to this work. Cooresponding Author. Email: sanal::snnruoyueuuh edu.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Qian et al. 29 explored the potential of GNNs to approximate the solution mapping of LP and reported encouraging results. Additionally, several studies have proposed various approaches guide MILP solvers with GNNs 10
14
T 26 32
Despite the numerical success, the theoretical foundation of using GNN to solve optimization problems remains less clear. Initial steps towards a theoretical understanding have been made by Chen et al. (8) and Qian al. [29]. They demonstrated that with a sufficient number of parameters,
GNNs can approximate the solution mapping of LPs with arbitrary precision. However, significant gap persists between the theoretical progress and empirical evidence. The proof in [8] relies heavily on the universal approximation theorem for multi-layer perceptions (MLP), which necessitates a large number of parameters in principle. Similarly, the result of (29) requires the depth of GNN be polynomial in the problem dimension. In practice, however, GNN with modest width and fewer than ten layers often suffice to achieve good performance in approximating the optimal solution of LP with hundreds of nodes and constraints.
This gap between theory and practice raises an intriguing open question:
When and why can small-size GNNs effectively solve LPs?
As larger networks usually require more training examples and higher computational resources, addressing this question not only of theoretical interest but also provides potential guidance L20 practitioners. While current GNNs may not yet rival theoretically grounded LP solvers in precision, they could still accelerate LP solving by providing high-quality initializations to warm-start traditional solvers. Understanding the principles behind the success of small-sized GNNs can potentially lead to more parameter-efficien models, thus reducing the computational resources required for LP solving. Moreover, these insights could potentially enhance MILP solvers. Specifically, the leading approach for MILP is the branch-and-bou -nd--ounddddd framework, which involves selecting variables and dividing the search space. A prevalent variable selection approach is strong branching, where variables are scored by solving associated LPs to guide the branching decisions. Researchers have exploited GNNs to score these variables, with GNNs essentially solving the associated LPs [1 31 By uncovering the mechanism behind the success of small-sized GNNs in solving LPs, these models could be further improved, leading to more efficient MILP solving.
1.1 Our contribution
In this paper, we show that polylogarihhmi--epth constant-width GNNs can approximate the solution mapping for a broad class of LPs, namely packing LPs and covering LPs, with arbitrary precision (Theorem 3 and Theorem 5). This result advances previous theoretical results on general LPs 8 29]. narrowing the gap between existing theoretical progress and empirical evidence.
Packing and covering LPs and their norm form. A packing LPP and its dual covering L.P are nonnegative LPs of the canonical form: max(c"".. x Ax < b, x 2 0} and min(b".. y AT Z c, 2 0} respectively. Here, A E B b E Ro and c m Packing LPs and covering LPs broad classes of linear programming problems that can be used approximate relax wide range of fundamental problems in combinatorial optimization. They include fractional versions of the vertex cover problem, the set cover problem, the hypergraph matching problem, the dominating set problem, and the maximum independent set problem. Without loss of generality, we assume the packing and covering LPs are presented in their normal [2, where the vectors b and c are all-ones vectors and A. is either zero or greater than 1. The details of the reduction to the normal form can be found in the appendix.
Our results. We present a new theoretical explanation of the phenomenon that small-size GNNs can solve general packing LPs and covering LPs, by unrolling gradient descent algorithms. Specifically, we first propose a variant of the gradient descent (GD) algorithm proposed by Awerbuch and Khandekar [2 for solving packing and covering LPs (Algorithms [T] and [).. so that our variant can be more naturally simulated by GNNs, where one iteration of the algorithm can be simulated by one GNN layer of constant width. Importantly, our variant of GD is guaranteed to output a iterations. Therefore, we affirm the feasibility
(1 --approximmat solution in volylog(mnAAmas) of solving general packing and covering I.Ps with polylogarithmic-dept constant-widd GNNs. Here, remark that the polylogarithmic dependency on depth is also necessary. Specifically, Kuhn et
2

---

al. [16] showed that: for the fractional maximum matching problem, special kind of packing LP, every constant-factor factor approximation distributed algorithm requires at least 22V1log n/ log log n) rounds. Moreover, since one layer of GNNs can be naturally simulated by one round of distributed LP algorithms (see, e.g., the second paragraph on page 5 in [16], we conclude that GNNs need at least S2( (oo/ log log n1) layers.
Building on our theoretical proof, we propose a new GNN architecture, termed GD-Net, for solving packing and covering LPs. We empirically demonstrate that, when appropriately trained, GD-Net can effectively adapt given problem instance distributions. Experiments across various datasets demonstrate that GD-Net outperforms classical graph convolutional network (GCN), a predominant GNN architecture in L20 for LP and MILP solving. Specifically, GD-Net generates better solutions with an order of magnitude fewer parameters than GCN. These performance enhancements become increasingly significant as the problem dimensions expand. The numerical success of GD-Net not only corroborates our theoretical framework but also suggests a potential direction for designing more parameter-effiieen GNNs for L20. This direction involves developing architectures that can simulate well-established, theoretically grounded algorithms, potentially leading to improvements in both computational efficiency and solution quality.
1.2 Related works
The design of GD-Net is based on the concept of unrolling iterative algorithms as GNNs. Indeed, there is a body of research that has explored this approach. For example, Velickovic et al. [33 investigated solving basic graph problems (e.g., the shortest path, the minimum spanning tree) by GNNs. By unrolling classical graph algorithms (e.g., breadth-first search, Prim's 's algorithm) as GNNs, they suggest that message- passing neural networks with maximization aggregator may be best suited for such graph problems. Aiming at mitigating oversmoothing, long-range dependencies, and spurious edges issues of GNNs, Yang et al. [36] proposed a new family of GNN layers by unrolling and integrating the update rules two classical iterative algorithms, namely the proximal gradient descent and iterative reweighted least squares. Papers (20 38 showed that many existing GNN models (such as GCN, GAT, APPNP) can be viewed as unrolling gradient descent serving specific graph signal denoising problems. Chen et al. 77] proposed new GNNs to improve graph signal denoising by unrolling sparse coding and trend filtering algorithms. Papers 24 39 37 bridge the gap between graph convolution and iterative algorithms by providing unified optimization framework for GNNs.
2 Gradient descent algorithm for packing and covering LPs
Throughout the paper, we use boldface to represent vectors or matrices, e.g., x and A. Let 1pxg denote the p x q-dimensional all-ones matrix, and 1p denote the p-dimensional all-ones column vector. Similarly, we can define Opxq and Op-
Algorithm for packing LPs.. Awerbuch and Khandekar proposed simple approxxiipooiiaaoioon algorithm for packing LPs of the normal form:
max x 1 S 1, 2 0}
(1)
where Aij, be, ej are all non-negative and Ai is either 0 or 2 1. The algorithm is described as follows: given parameters μ = In m.mmax a 1. 10g
a and 10pmAmass
-Strrt with x Om: Then, repeat the following procedure:
1. y4 == explμ (A,x - 1)] for each i e [m]]
2. For any j E [m] do
(a) If A y < 1 a, then xy == max(x; (1 + B);
(b) If A y > 1 + a. then Iz == Zj (1 3).
3

---

Algorithm 1: Our variant of Awerbuch- Awerbuch-Khandeear algorithm for packing LPs
Input: A n x m matrix A where Aij either zero or no less than 1, and 6. 0. and 10pnAmax
2 Parameter: ja: :-=- - mAmax
i. B Iüp
Initialize x.0 = 0:
for k = 0 to
do
uf = explu( A,a* 1)] for any E [n]]
for each E [m]] do
if A y <
2 A+1 == 25 (1 3) d; if A T y 2 1 + a then k+1 == z/ (1 B);
then
Output: =
The intuition behind this algorithm is that it can be viewed as applying gradient descent on a carefully chosen potential function defined as
Vi
explu(A;2 - 1)]
(x(x))
which enjoys the following nice properties 2 (i) p is differentiable and convex; (ii) p A" y; and (iii) any stationary point of Φ is a nearly optimal solution to the packing LP I For any a where (xx = O, x: is feasible and 1" x 2 (1 4c) -OPT. It turns out that this algorithm has polylogarithmic convergence (2. Precisely, given any O, this algorithm always maintains feasible solution (i.e. x 2 0 and Ax < 1 always hold), and returns a (1 apappooximmttoon solution (mx))) iterations. Here Ô hides lower order
to the packing LP L in (0nn2mmmmaa terms like In Amax) and In(1/e).
Algorithm for covering LPs. In the same paper 2 Awerbuch and Khandekar also considered solving the dual covering LP of the normal form
min(1".. y A 1, 0).
and designed the following algorithm: given fu == 1 In nAmaz a = 3. 4.
and 20yem.Aaaxx
20g
Starrt with y : 1,; Then repeat the following procedure:
1. 2y == explu (1 - A3 y)] for each j [m]:
2. For any i E [m] do
(a) If A, 2 + a. then y4 == max (y: (1 + B),
(b) If A < 1 - a; then yi == y: (1 - 3).
Similarly, this algorithm can also be thought of applying a variant of gradient descent on a carefully selected potential function (2)
m
m expla(1
-A, v)
2
+
Vi:
1
1
j=1
1=1
im1
which satisfies that: (i) (v( is differentiable and convex; (ii) V.. =
Ax; and (iii) for any where ( = 0, is feasible and 1s y < (1 + 4c) OPT. This algorithm was shown to enjoy polylogarithmic convergence well (2] Formally, this algorithm always maintains a feasible solution (i.e. y and A y always hold), and returns a (1 + appapooxxinttion solution the covering LP 2 in ÓIn Amz) In2 (mmnmax)/e" iterations.
A variant of Awerbuuch-Khandekee Khandekar algorithms. We propose variant of the Awerbuch-Khandekee algorithms, specifically Algorithm | for solving packing LPs ①1) and Algorithm for covering IPs The motivation and advantage of our variant is that it can be simulated more naturally by GNNs.

---

Algorithm 2: Our variant of Awerbuch-Khandeeat algorithm for covering LPs
Input: A n x m matrix A where Aij either zero or no less than 1, and 6. 0.
2 Parameter: μ :-=-; In nAmax a 1. 3
e and 5 20pm.Amax
20p
Initialize y0 =
4 for k = 0 to
do
2 = exppp(11 A } for any j E [m]];
for each i E [n] do
if A 2 + a then Vi k+1 : u (1 + 3) +
if A I 1 then s. == vt -1-1111 3);
Output: y
Basically, we replace Iy + m (1 (1+ 8), with zj + 21 B)+ + in their algorithm for packing LPs, and y, ma + 6) with By t 1)(1+ B)+ their algorithm for covering LPs. Through almost the same proof, one can verify that the polylogarithmic convergence still holds.
Theorem 1. Algorithu D aawways maintains feasible solution and returns (1 + c) caapproxiimation
solution to the packing LP ① in Ö (mAAns)) In (n e
iterations.
Algorithm always maintains a feasible solution and returns a (1 -apprrxximation solution the covering LP 2 in (nAAma)) In² Amxx)))))/)) iterations.
Connection to GNN. For LPs, an instance can be naturally encoded labeled bipartite graph 13 15 25), where (a) a left node represents a variable, (b) right node represents a constraint (and equivalently, the associated dual variable), and (c) left node and right node are connected the corresponding variable participates the corresponding constraint. our GD algorithms, the matrix-vector multiplication Ax (or ATy) can be interpreted nodes to right nodes (or from right nodes to left nodes). In the next sections, we will demonstrate how one iteration of our GD algorithms can be transformed into single layer of GNN.
message passing step from left
3 Design of packing GD-Net
By combining the idea of Algorithm I and techniques from graph neural networks, design graph neural network architecture, named packing GD-Net, for solving packing LPs.
One iteration of Algorithm D consists of two steps: first, the algorithm updates y from æ, and calculates the gradient v A y 1; second, using (m), it applies variant of gradient descent to update æ. Our packing GD-Net modifies the second step by replacing it with a learnable neural network block, while leaving the first step unchanged. Thus, the packing GD-Net can also be viewed as utilizing a neural network block to accelerate the convergence of the gradient descent.
ELU activation for y-update. We apply the Exponential Linear Unit (ELU) activation function to replicate the y-update: y = (xxp)((,,zz - 1)]. We will fix the parameter a ELU to 1, then ELU(tt) + exp(t) for t S 0. In addition, as mentioned Theorem [ A, S always holds in the execution of Algorithm I Thus the ELU function can exactly replicate the y-update. Specifically, our packing GD-Net updates y as follows:
1)] +
Since is fixed to and is fixed to 1 In mAmax, no learnable parameters are involved here.
Learnable gradient descent procedure. The gradient descent in Algorithm can be rewritten as
- $SAA yA -1) 2 v(AFv² - 1) = - + (00 2 g(00 00r,)
5

---

A
x
ELU
yk
y
BLU
x
AP
-A
f
fa
g
g
ReLU
ReLU
we
-Iaad
Ipxd
1
-A"
x
ykr1
yk+1
ELU
X
Figure 1: The architectures of a single layer in packing (left) and covering (right) GD-Nets. Learnable parameters are colored in red.
where f.g: - R are sums Hcaviside step functions defined as:
if v -a; s(t) = 0, if - S a
B,
6,
if -a;
and g(t)
(4)
0, otherwise.
-B,
if a.
As the Heaviside step function be naturally approximated by the sigmoid function ott) I+exp(-tj the packing GD-Net adopts the following learnable functions as substitutes for f and g:
L1 Co 00 1+ 02,3) + 02,1 000/22 02 0221
Se (1) Σ 8m1
(5)
and
9ot (1) = Σ 6=1
0 [o + 02 o
(6)
Note that it is guaranteed that (t)= for (-t), in particular for (0) O, and g0- (0) 0. So if the packing GD-Net reaches a stationary point of Pp. will remain there. Additionally, the packing GD-Nct applies the ReLU activation to keep x5 2 0.
Channel expansion and architecture of packing GD-Net We integrate the channel expansion technique to further strengthen the expressive power. Specifically, we expand the m-dimensional column vector & into a (m x dddiinnnsional matrix X and n-dimensional column vector y into a (n x diddiennsoo matrix y Now, we are ready to present the packing GD-Net architecture:
Initialize X = Omxd and Y Onxd-
For = , K-1
y = ELU VEL[L(AA,X' [x(A,** Inxa]] + lnxd-
x x+1 = ReLU (fx* for (ATy 1 1mxd] x + gor [A Imxd]] } w²).
-Output final = x K E R
Here, denotes entry-wise multiplication (a.k.a. Hadamard product), and for Ioh : - R are
applied entrywise to the matrix A y 1 1mxa- The learnable parameter is O = ( W w*jk- K-1 U (wK). where gh [0%,1 0% 8k La U (0) 0% 1/2 W E dddd and w E Rdxl, So 22,1tm1
TR=0
the total number parameters is K (d2 + 3T, 3l22 + The following theorem reveals the ability of the packing GD-Net to reproduce Algorithm I with arbitrarily small precision.

---

Theorem 2. Given any network depth K. any network width d 2 1, and any precison > 0, there exists a K --layer packing GD-Ner with a specific choice of parameters such that. for any packing LP _ S Here, a is the oulput of K K-iteration Algorithm
instance a innl
By combining Theorems and and constant width are sufficient to solve packing LPs.
conclude that the packing GD-Nets with polylogarithmic depth
Theorem Given any e > O and 1i > O, there exists a packing GD-Net of (m In (nAmsx)/e)) depth and constant width, using the parameter assignment @GD. that satisfies the following condition: For any packing LP instance ① x. finat is s-close being a (1+c) (1+tc)-aprrxiimat solution.
Remark We can establish similar theorem with general- purpose GNNs (such as GCNs) where we can still derive polylogarithmic depth in the bound but constant width is no longer guaranteed. Specif- ically, by the universal approximation theorem, the ELU function can be simulated with arbitrary precision by a 2-layer and sufficiently wide perceptron. So if we replace each occurrence of ELU with this 2-layer perceptron, we then obtain a GCNs. Note that this GCN still has polylogarithmic depth but the required width is no longer constant.
Network training. The training data set is a I {AA +[), of packing LP instances in the normal form. More specifically, the input of an instance is identified by the constraint matrix A, with 6 and being both all-ones vectors; the label x" represents the corresponding optimal solution. Let x final (e, A) denote the output of the packing GD-Net parameterized by θ running on the input A. The goal of the training process is to find a parameter O" minimizing loss function defined as:
(I;
1
Σ (AT
lx final (0, A) x= x12
I
Feasibility resortation. Note that the x: fimal returned by packing GD>Neet may be infeasible. To restore feasibility, we implement the following post-processing procedure:
First, for each j E [m]] update zÿ == max(0, min(1, x1,;;);;
Then, for i to do
If A,æ: > 1, then update Ty A.æ
for each with Ai 0.
4 Design of covering GD-Net
In one iteration of Algorithm the process begins by updating æ from y. followed by the calculation of the gradient Vœa(y) 1 Ax. Finally, it applies variant of gradient descent update y. Our covering GD-Net retains the original u-uudate and gradicnt-calculation calculation modules, but replaces the gradient descent with learnable neural network block to accelerate convergence.
Architecture of covering GD-Net. Similarly, we substitute the ELU activation with fixed to for the exp(-) function, and replace the x-update 2/ exp|p(1 A, "/''' with
ELUUp(C A y²) + 1.
As will show in Theorem 4 can exactly simulate the x-update in Algorithm
The gradient descent procedure in Algorithm 2 can be rewritten
1/ A+1 -- f A v. 9 A,**) v. + f (0.,/0y) v/ + g(00a/0m))
where f.g R + R are the same functions as those defined in (4) for packing GD-Net. So, in the covering GD-Net, we also substitute ff and g with the learnable functions for and 9ø* defined in (5) and 66) respectively. In addition, we also apply ReLU to keep y. 2
Besides, the channel expansion technique is also incorporated: similarly, expand æ E R into x ma and x E IR" into * E gn Then, propose our covering GD-Net architecture:
Inittialize Y = 1nxd and x 1mxd-
For A 0, 1, K -
7

---

x = ELU
mmxd mxx A ["]] + +1mxd:
= ((r* + Se Inxd - AX y + g0a [nxa - AX wa).
Output fimal = Y w IR".
k== The learnable parameter is θ = f0r w K-1 U {w*", where oº
-00 02,2 0%,3 1 U
{0),a, 5/ (6 W Rdxd and w E Rdx1 So the total number of parameters is (d?
3L1 + 3L2) + d, the same as in packing GD-Net.
Theorem 4. Given any network depth K, any network width 2 and any precison > 0, there exists K -layer covering GD-Net with a specific choice of parameters such that, for any covering | final
LP instance
2.
y S Here. y the output of K K-iteration Algorithm 2
Theorems and together imply the capacity of polylogarithmic-dephh constant-width covering GD-Nets for solving covering LPs.
Theorem 5. Given any > 0 and n O, there exists covering GD-Net of (n.Ar))))))) In (mn depth and constant width, using the parameter assignment @GD. that satisfies the following condition: For any covering LP instance 2 y T'nal is 1--clos to being (1 + e)- approximate solution.
Remark 2. Similur to Remark [
we can establish a similar theorem with generul-purposs GNNs where the polylogarithmic bound on the depth still holds but constant width is no longer guaranteed.
Network training. The training dataset is a set I = (A, (A, consisting of instances where y² is the optimal solution the covering LP (2) with constraint matrix A. The goal of the training process is to find a parameter O* minimizing the following loss function:
C. = I
Σ
ly Final
Final (0, A) -
(ATT))E
Feasibility resortation. Since the final may be infeasible, we implement the following post- processing procedure to restore feasibility:
First, for each E [n]. update y == max(0, min (1,y)));
-Then for j = 1 to m do
If A < 1, then update yi = A3 for each with Aij F 0.
5 Experimental study
5.1 Experemental Setup
Datasets. We utilized four L.P relaxations of publicly available mixed-integer optimization instances as benchmarks. Specifically, we included the Maximal Independent Set (IS), Packing Problem (Packing). Edge Covering Problem (ECP), and Set Covering (SC). The problem definitions are adopted from p [2)] Each benchmark comprises four sets of problem instances with varying sizes, including one set designated for the generalization experiment. Detailed information regarding the problem sizes and data splitting ratios can be found in the appendix.
To construct datasets for training, each instance M, = {A c') undergoes normalization to M, = (A', 1,, }. Subsequently, via the optimization solver SCIP (5), we obtain the optimal solution and optimal objective value pair [bj; } for each instance M, Finally, we utilize the input-target pair to compose the dataset D = {A', ..
M
Models and Training settings. For comparison, our experiments also include the graph convo- lutional network (GCN), predominant GNN architecture in L20 for LP and MILP. Specifically,

---

we adopt the GCN implementation from (29], which is tailored for predicting the optimal solu- tions for LPs. Both the GCN and the proposed GD-Net utilize a four-layer architecture with 64 hidden units in each layer. Consequently, the number of parameters is 1,656 for GD-Net and 34,306 for GCN. Note that our GD-Net has an order of magnitude fewer parameters compared to GCN. For GD-Net, we set 0.2. All models were trained using learning rate of 10-3 We trained each model for 10,000 epochs, and the checkpoint with the lowest validation loss was saved for evaluation. For reproducibility, code to conduct the experiments can be found at .orrrnouusooo.n.....mmm www.sceereeeeeeeeeeeeeeeee -Fctt66FC7
Metries. To effectively evaluate the GNN's ability solve LP problems, we employed two distinct metrics: the relative gap R. Gap = lobj, - obj 1/obj? and the absolute gap (A. Gap lobj. obj; D. where obj, denotes the predicted objective value of the respective approach after feasibility restoration.
5.2 Comparing against GCNs
In this section, we assess the effectiveness of the proposed GD-Net and the GCNs adopted from [29 in predicting the optimal solution for LP problems. As shown in Table [ we report relative and absolute gaps, along with validation and test errors, to evaluate the quality of solutions generated by each model. The results indicate that GD-Net typically achieves narrower gaps compared
Table I: Results of comparing the proposed GD-Net against GCNs from 229 errors measured by MSE (V.E and the relative/absolute objective gap from the optimal solution (R. Gap/A.Gap). Better performances are highlighted in bold. Results are averaged across 100 instances.
We report valid/test
Dataset
Size
GD-Net
GCNs 29
V. Err
T. Err
Gap
A. Gap
V. Err
T. Err
R. Gap
Gap
0.062
0.062
4.41%
1.478
0.145
0.122
15.46%
5.155
IS
0.156
0.135
3.55%
12.201
0.156
0.135
16.18%
55.318
L
0.085
0.085
6.84%
43.073
0.154
0.131
15.35%
96.785
3.40E-4
3.39E-4
16.53%
0.184
2.7E-4
2.6E-4
19.50%
0.220
Packing
M
6.53E-4
6.53E-4
10.68%
0.118
5.05E-4
5.09E-4
10.69%
0.118
L
2.18E-4
2.20E-4
7.35%
0.082
1.69E-4
1.69E-4
7.37%
0.082
S
0.099
0.097
7.84%
1.478
0.173
0.153
36.83%
12.41
ECP
0.129
0.115
21.51%
74.80
0.172
0.153
38.73%
134.50
L
0.123
0.115
18.28%
116.05
0.172
0.153
39.22%
249.06
3.12E-4
2.91E-4
26.68%
0.297
2.53E-4
2.54E-4
21.91%
0.244
SC
M
6.64E-6
6.50E-6
13.09%
0.145
5,05E-6
5.10E-6
10.91%
0.121
L
2.19E-6
2.19E-6
8.42%
0.094
1.81E-6
1.77E-6
8.90%
0.099
to GCNs. Even in instances where GD-Net does not surpass GCNs, the performance discrepancy remains minimal, which is noteworthy given GD-Net's significantly fewer parameters. Notably, in scenarios like Packing-L, although GD-Net records a higher test error, it still outperforms GCNs. This suggests that GD-Net may better capture the structural nuances of the problem. Overall, GD-Net generally demonstrates superior performance over conventional GCNs.
5.3 Generalization to larger instances
In this section, we evaluate the generalization capability of our proposed GD-Net, trained on smaller instances, to larger problem domains. We train GD-Nets on the largest dataset available for each problem and subsequently test these models on problem instances with 10% more constraints and variables. Tarsee]ssseetts the results, showcasing relative and absolute gaps, along with validation and test errors. The results reveal that GD-Nets possess a notable ability to generalize to larger problem instances with only minimal performance degradation. This suggests robustness in handling increased problem complexity, underscoring the adaptability and scalability of the proposed GD-Nets.

---

Table 2: Results of generalizing GD-Nets trained on smaller instances to larger instances. All models are trained on datasets of size L.. We report valid/test errors measured by MSE (V.Er//T.Em) and the relative/absolute objective gap from the optimal solution (R. Gap/A.Gap). Results are averaged across 100 instances.
dataset
V. Err
T. Err
R. Gap
A. Gap
IS Packing
[1100, 1300]
[1100,
1300]
0.085
0.085
6.81%
47.681
11000. 1300
11100. 1300]
2.18E-4
1.85E-6
7.06%
0.078
ECP
1100. 1300]
11000 1300]
0.123
0.115
17.48%
120.63
SC
[1100, 1300]
[1100, 1300]
2.19E-6
1.87E-6
10.68%
0.119
5.4 Comparing against more Baselines
To further demonstrate the effectiveness of the proposed framework, we include two additional baselines: the traditional first-order solver PDLP [9] and the commercial solver Gurobi (12). Specifically, we used Gurobi's primal simplex method, which efficiently produces feasible primal solutions. The table below shows the time taken by each method achieve solutions with the same precision level as GD-Net's solutions, The experiment was conducted on both the SC and Packing datasets across all three size variants.
Table 3: Performance comparison of GD-Net, Gurobi, and PDLP on achieving the same precision.
Instance #Vars.
Optimal Obj.
GD-Net Obj. GD-Net Time Gurobi Time PDLP Time
1,000
3.334
3,701 130.931
0.105s
0.244s
0.919s
SC
5,000
100.667
0,218s
9.40Is
0.921s
10,000
407.386
546.666
0.335s
103.322s
1.001s
1,000
3.334
3.018
0.095s
0.208s
0.746s
Packing
5,000
100.88
78.994
0.216s
3.980s
0.756s
10,000
406.946
302.04
0.314s
8.593s
0.809s
As shown in Table 3 GD-Net consistently outperforms both general-purpose solvers all datasets. Notably, PDLP, a first-order method known for its fast early-stage convergence, is unable to produce solutions of comparable quality those of GD-Net shorter time. This further highlights GD-Net's ability to efficiently generate high-quality solutions. Additionally, as previously mentioned, the simplex method requires matrix factorization, which is computationally expensive. this case, required up to 300x more time to converge to a solution of the same quality as GD-Net. These findings strongly support the effectiveness of GD-Net, demonstrating capability to consistently generate high-quality solutions.
Moreover, we also include experiments under more practical setting and compare the inference time, which can be found in Appendix G and H
Conclusion
Inspired by Awerbuch and Khandekar's gradient descent algorithms for packing and covering LPs, we introduce packing and covering GD-Net, and prove that they can approximate the solution mapping of packing and covering LPs respectively. Importantly, they only need polylogarithmic depth and constant width, significantly narrowing the gap between existing theoretical prediction and empirical evidence. Experiments are also conducted to demonstrate their effectiveness. We list some directions for future work: (1) How to further reduce the size of GNNs theoretically, since there is still a gap between our theoretical progress and empirical evidence; (2) How low the size of GNNs can go for solving general LPs, noting that our nets only work for packing and covering LPs; (3) To explore our nets in L.20 for MILP. Recall that GD-Nets can be viewed as unrolling the gradient descent carefully selected potential function with some good properties. For (2) and (3), a natural direction to design other potential functions that still enjoy those good properties.
10

---

Acknowledgments
This paper is supported by the National Key Research and Development Project under grant 2022YFA1003900 Hetao Shenzhen-Hong Kong Science and Technology Innovation Cooperation
Zone Project No..HZQSWS-KCCYS --22Y0-)) University Development Fund UDF01001499 the Chinese University of Hong Kong, Shenzhen; Guangdong Provincial Key Laboratory of Mathemat- the Guangdong Major Project of Basic and Applied Basic Research (202330303000001) Qian Li and Minghui Ouyang's work was additionally supported by the National Natural Science Foundation of China Grants No. 62.002222.. Tian Ding's s work was additionally supported by the Internal Project of Shenzhen Research Institute of Big Data under Grant J00220240005.
ical Foundations for Artificial Intelligence 00233121201000
References
[1] M. Ahmadi, Kuhn, and R. Oshman. Distributed approximate maximum matching in the CONGEST model. In U. Schmid and J. Widder, editors. 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, volume 121 of LIPles, pages 6:1 6:17. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2018
[2] B. Awerbuch and R. Khandekar. Stateless distributed gradient descent for positive linear programs. SIAM J. Comput., 38(6):2468 2242266666666,, 2009.
[3] Y. Bartal, J. W. Byers, and D. Raz. Global optimization using local information with applications to flow control. In 38th Annual Symposium Foundations of Computer Science, FOCS '97, Miami Beach, Florida, USA, October 19-22, 1997, pages 303-312. IEEE Computer Society, 1997.
[4] Y. Bengio, A. Lodi, and A. Prouvost. Machine learning for combinatorial optimization: methodological tour d'horizon. European Journal of Operational Research, 290(2))405-421, 2021.
[5] S. Bolusani, M. Besançon, K. Bestuzheva, A. Chmiela, J. Dionísio, Donkiewicz, van Doornmalen, L. Eifler, M. Ghannam, A. Gleixner, C. Graczyk, K. Halbig, I. Hedtke, A. Hoen, C. Hojny, R. van der Hulst, D. Kamp, Koch, K. Koffer. J. Lentz, J. Manns, G. Mexi, E. Mühmer, M. E. Pfetsch, F. Schlösser, F. Serrano, Y. Shinano, M. Turner, S. Vigerske, D. Weninger, and L. Xu. The SCIP Optimization Suite 9.0. Technical report, Opti- mization Online, February 2024. URL httpe:://otimiiationn ceeeeeooniinnee.nee org/2024/02/
che-scip-optiimzzaiioo. www.on-ssuett--eeeeeee
[6] Q Cappart, D. Chételat, E. B. Khalil, A. Lodi, C. Morris, and P. Velickovic. Combinatorial optimization and reasoning with graph neural networks. J. Mach. Leurn. Res., 24:130:1-130:6. 2023.
[7] Chen, Y. C. Eldar, and L. Zhao. Graph unrolling networks: Interpretable neural networks for graph signal denoising. IEEE Trans. Signal Process., 07-3669--713 2021. doi: 10.1109/TSP. 2021.3087905. URL http::://doo..rgge 11000...110///0 1109/TSP 2021 00921.0083 3087905
[8] Z. Chen, J. Liu, X. Wang, and W. Yin. On representing linear programs by graph neural networks. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
[9] M. Gasse, D. Chételat, N. Ferroni, L. Charlin, and A. Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32, 2019.
[10] P. Gupta, M. Gasse, E. B. Khalil, P. K. Mudigonda, A. Lodi, and Y. Bengio. Hybrid models for learning to branch. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[11] Gupta, E. B. Khalil, D. Chételat, M. Gasse, A. Lodi, Bengio, and M. P. Kumar. Lookback for learning to branch. Trans. Mach. Learn. Res. (TMLR), 2022, 2022.

---

[12] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL hattps:/wwx gurobi com
[13] B. Hudson, Q. Li, M. Malencia, and Prorok. Graph neural network guided local search for the traveling salesperson problem. In International Conference on Learning Representations, 2021.
[14] E. B. Khalil, C. Morris, and A. Lodi. Mip-gnn: A data-driven framework for guiding combi- natorial solvers. In Proceedings of the AAAI Conference on Artificial Intellgence, volume 36, pages 10219-10227) 2022.
[15] F. Kuhn, T. Moscibroda, and R. Wattenhofer. The price of being near-sighted. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pages 980-989. ACM Press, 2006.
[16] F. Kuhn, T. Moscibroda, and R. Wattenhofer. Local computation: Lower and upper bounds. J. ACM, 63(2):17:1-17:44 2016.
[17] X. Li, Q Qu, F. Zhu, J. Zeng, M. Yuan, K. Mao, and J. Wang. Learning reformulate for linear programming. arXiv preprint arXiv:2201.062. 062116, 2022.
[18] D. Liu, M. Fischetti, and A. Lodi. Learning to search in local branching. In Proceedings of the aaai conference artificial intelligence, volume 36, pages 3796-3803, 2022.
[19] H. Lu and J. Yang. A practical and optimal first-order method for large-scale convex quadratic programming, 2024. URL http:/ttts//aaatee /wtpvv//aiivvv//. wtw.gbs//////ao..e//..//.eeeeee/ http//bb//3311.... 2311.07710
[20] Y. Ma, X. Liu, T. Zhao, Liu, Tang, and N. Shah. A unified view on graph neural networks as graph signal denoising. In G. Demartini, G. Zuccon, J. S. Culpepper. Z. Huang, and H. Tong, editors, CIKM '21: The 30th ACM International Conference on Information and Knowledge Management, Virtual Event, Queensland, Australia, November I 5, 202/, pages 1212-1211. ACM, 2021. doi: 10. 10. n..1145/345963...0 3482225. https://::///o. org 10. 1145//456677 3482225
[21] N. Mazyavkina, S. Sviridov, S. Ivanov, and E. Burnaev. Reinforcement learning for combinato- rial optimization: A survey. Computers & Operations Research, 134:105400, 2021.
[22] V. Monga, Y. Li, and Y. C. Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. IEEE Signal Processing Magazine, (3(2):88444 2021.
[23] V. Nair, Bartunov, F. Gimeno, I. von Glehn, P. Lichocki, I. Lobov, B. O'Donoghue, Son- nerat, C. Tjandraatmadja, P. Wang, R. Addanki, T. Hapuarachchi, T. Keck, J. Keeling, P. Kohli, I. Ktena, Y. Li, O. Vinyals, and Y. Zwols. Solving mixed integer programs using neural networks. CoRR, abs/2012. 133499 2020.
[24] X. Pan, X. Han, C. Wang. 7. Li, S. Song, G. Huang, and C. Wu. A unified framework for convolution-based graph neural networks. Puttern Recognit, 155:1 10597, 2024. doi: 10.10 PATCOG.2024.1 110509 TRLpttts:://ooi org/ 10. 1016/ j. patcog 2024. 110597
[25] C. H. Papadimitriou and M. Yannakakis. Linear programming without the matrix. In S. R. Kosaraju, D. S. Johnson, and A. Aggarwal, editors. Proceedings of the Twenty- Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 121-129. ACM, 1993.
[26] M. B. Paulus, G. Zarpellon, A. Krause, L. Charlin, and C. Maddison. Learning cut by looking ahead: Cutting plane selection via imitation learning. In International conference on machine learning, pages 17584-17600. PMLR, 2022.
[27] Y. Peng, B. Choi. and J. Xu. Graph learning for combinatorial optimization: a survey of sfate-of-the-art, Data Science and Engineering, 6(2):119-141 2021.
[28] A. Prouvost, J. Dumouchelle, L. Scavuzzo, M. Gasse, D. Chételat, and A. Lodi. Bcole: A gym-like library for machine learning in combinatorial optimization solvers. In Learning Meets Combinatorial Algorithms at NeurIPS2020, 2020. id=IVc9hogibyB
wttprrvvviieeeeeefrrreeee net/forum?
12

---

[29] C. Qian, D. Chételat, and C. Morris. Exploring the power of graph neural networks in solv- ing linear optimization problems. In International Conference on Artificial Intelligence and Statistics, pages 1432-1440. PMLR, 2024.
[30] R. Sato, M. Yamada, and H. Kashima. Approximation ratios of graph neural networks for combinatorial problems. Advances in Neural Information Processing Systems, 32, 2019.
[31] M. Seyfi, A. Banitalebi-Dehkord:: Z. Zhou, and Y. Zhang. Exact combinatorial optimization with cemporo-attentioon graph neural networks. In D. Koutra, C. Plant, M. G. Rodriguez, E. Baralis, and F, Bonchi, editors, Machine Learning and Knowledge Discovery in Databases: Research Track European Conference, ECML PKDD 2023, Turin, Italy, Seplember 18-22, 2023, Proceedings, Part IV, volume 14172 of Lecture Notes in Computer Science, pages 268 283. Springer, 2023.
[32] Y. Shen, Y. Sun, A. Eberhard, and Li. Learning primal heuristies for mixed integer programs. In 2021 international joint conference on neural networks (ijenn), pages 1 1-8. IEEE, 2021.
[33] P. Velickovic, R. Ying, M. Padovano, R. Hadsell, and C. Blundell. Neural execution of graph algorithms. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https://openrevier net/forum?ie SkgidddEtggS
[34] L. Wang, H. Wu, W. Wang, and K.-C. Chen. Socially enabled wireless networks: Resource allocation via bipartite graph matching. IEEE Communications Magazine, 53(10):128-13) 135, 2015.
[35] Z. Wu, S. Pan. F. Chen, G. Long, C. Zhang, and S. Y. Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4-24, 2020.
[36] Y. Yang, T. Liu, Y. Wang, J. Zhou, Q. Gan, 7. Wei, 7. Zhang, 7. Huang, and D. Wipf. Graph neural networks inspired by classical iterative algorithms. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 11773- 11783. PMLR, 2021. URL http: http:://proceedingg. mlr pttss///13//aagg2/// html
[37] H. Zhang, T. Yan, 7. Xie, Y. Xia, and Y. Zhang. Revisiting graph convolutional network semi-supervised node classification from an optimization perspective. CoRR, abs/2009.11469, https: / http//axxvvvv.. www.xxii.ooo//aaa. 2020. URL
www./rg////aaeeeeeee...eeeeeeeee abw//////.0000 11469.
[38] Z. Zhang and Z. Zhao. Towards understanding graph neural networks: An algorithm unrolling perspective. CoRR, abs/2206.04471,, 2022. doi: 10.4550/ARXIV.2206.444 URL https
//doi.org/11 1...0.4855/aaaa wrwiv. 220..
[39] M. Zhu, Wang, C. Shi, Ji, and Cui. Interpreting and unifying graph neural networks with an optimization framework. In Leskovec, M. Grobelnik, M. Najork, J. Tang, and I.. Zia, editors, WWW '1: The Web Conference 2021, Virtual Event / Ljubljana, Slovenia, April 19-23, 2021, pages 1215- 1226. ACM/ IW3C2, 2021. doi: 10. 10.1144/3442381..444 https://ddee http:::///ooo.rr/100/ 1111://00001111111111111/111 114.11..1144/1/18811 3449953
URL
13

---

A
Packing and covering LP: reduction to the normal form
Recall that packing LP and its dual covering LP are nonnegative LPs of the canonical form:
max cf x
(Packing LP)
min
b" y
(Covering LP)
S.L.
Ax 2
s.t.
A y c
y 2 0
where all Aij. b, and ej are non-negative. Their norm forms are those where and e. are both all-ones vectors and Aij is either zero or greater than 1.
1
min y
1F y
s.t. A 1
s.t.
A y'y21 y 2 0
x 20
The reduction the normal form proceeds follows. First, otherwise all variables Ij with Aij > 0 have to be zero and yi can be set to zero; similarly, we can assume each Cj since otherwise 2i be set to and all variables ys with Aij have be zero. Then, we can replace Asy by Aij- = Asi replace b and c by all-ones vector, and work with Å. variables 3 cj and y: b,yi- Finally, we replace Åig by Å. min( M4 and work with ūj ăj. min Avg Avgrso) and jú min(Avy Auyzo].
assume that each b, > 0 since
brey"
B Proof of Theorem 2
Proof. As increasing the network width d does not decrease the expressive power, it suffices to show the theorem for d = 1. When d and w then packing GD-Net reduces to
Initialize x. = O, and dd O,,
For h:
K 1
v. ELU (=ELUU((AAE)) 1)] + for each i [n];
k+1 = ReLU (ut + So (Af - x + So (A 1 1)] for each j E [m]]
Output x final = K
x is always feasible, thus A, 1 < 0 (Theorem []. Additionally, since a fixed to 1, ELU(t)) + exp(t) for S Therefore, in
For the ypudate part, recalling that in the execution of Algorithm]] 1
Algorithm I can replace yर = exp[u(A,a** 1)] with v = ELU [u(A A 1)] without
altering the algorithm's behavior.
For the x-update part, rewrite this update in Algorithm as
2t+1 : + (A]
+
where f and g are defined in 4.. Both f and g can be expressed as the sum of at most two Heaviside step functions, which can be naturally simulated by sigmoid function with arbitrarily small error. Specifically, by setting L1 = 1, f1,1 -3, 01.3 = a 81,2, and making 0 sufficiently large, for can approximate f with arbitrary precision. Similarly, by setting T-2 = 1, 0 - 6, of. 0 and making 0f large enough, 9 can be approximated arbitrarily well by gøa. Therefore, in Algorithm [ we substitute
-- S0 (A)y x + g0 (Af 11/y-11 1),
we will get the above reduced packing GD-Net, and the change of the output K can be made arbitrarily small by appropriately choosing the parameter e.
D
14

---

C Proof of Theorem
Proof. The proof is very similar that of Theorem 2 First, only need to show the theorem for 1, because does not decrease the expressive power to increase the network width d. When
d = and by letting w 1, the covering GD-Net reduces reduces to
-Initialize yd : 1, and x² mm.
For h 0, K -1
2 ELU [m(1 A3 yt) + for each j E [m]]
ReLU lut for (1)) ot go A.x)] for each E [n]]
Vi
Output f = yk
For the 2z-update part, recalling that in the execution of Algorithm 2 y is always feasible, thus A7 y S (Theorem Additionally, since a fixed 1, ELU(t) +1 exp(t) for = Therefore,
in Algorithm we can replace x exp[a(1 - A y*)] with 2f = [LU[((1 A y" + without altering the algorithm's 's behavior.
For the y-update part, we rewrite this update in Algorithm ass
De vt 5 A.æ) v/ + A,æ))
where f and are defined in 4 As shown in the proof of Theorem 2 for and Iør can approximate and respectively with arbitrary precision. Therefore, in Algorithm [ we substitute
y = vfth + for (1 -1- A,x) y. 9 (1 A,=)
then we will reach the above reduced covering GD-Net, and the change of the output yK can be made arbitrarily small by appropriately choosing the parameter +
D Dataset specification
For all experiments, involved models are trained with datasets split into 5,000 training instances, 100 validation instances, and 100 test instances. Each problem contains different sizes, namely small (S), medium (M), large (L), and generalization (Gen). The detailed sizes of each size can be found in Table
For the benchmarks, we generated instances of specified sizes using the Ecole
Table 4: Sizes of Maximum Independent Set problems
Size
Row
Col.
S
[50- 70]
[50 70]
M
[500 700]
[500 700]
L
1000 1200
1000 1200
Gen
1100 1300
1100 1300
Table 5: Sizes of Packing problems
Size
# Row
# Col.
Density
S
[50- 70
[50 - 70]
60%
M
[500
700]
[500 700]
60%
L
1000 1200
1000 1200
60%
Gen
1100 1300
1100 1300
60%
For ECP, we initially created IS instances, then converted these into their dual forms to obtain ECP instances. Regarding the SC and Packing datasets, produced matrices of size m with density of only density% non-zero entries. We then formulated the corresponding problems by transposing the matrix A or leaving it as is, depending the dataset requirements.
library 288
15

---

Table 6: Sizes of Edge Covering problems
Size
Row
Col.
S
[50- 70]
[50 70]
[500 700
[500 700]
L
1000 1200
1000 1200
Gen
1100 - 1300
1100 1300
Table Sizes of Set Covering problems
Size
# Row
# Col.
Density
S
[50 70]
[50 70]
60%
M
[500 700]
[500 700
60%
L
1000
1200
1000
1200
60%
Gen
1100 1300]
1100 1300]
60%
E Hardware/Software specification
All experiments were performed on server machine equipped with an Intel(R) Xeon(R) Platinum 8280 CPU @ 2.70GHz and 2.95 TB RAM. Data collection for training utilized Ecole 0.7.3 and Pyscipopt 4.2.0 for generating and solving instances. Model implementations were developed using PyTorch 2.1.
Problem Definitions
In this section, give the problem definitions and the specific formulations, as well as their LP relaxations of the original mixed-integer optimization problems used to generate data.
Maximum Independent Set (IS). The goal is to select as many vertices as possible from an undirected graph (V, F. such that, no two vertices form a edge.
max
Σ
(IS)
max
Σ Z
(L. relaxation)
VEV
VEV
s.t. T. Iu S ((U,))
s.t.
Eu
+
x E [0,1)
Packing Problem. The goal is to maximize the profit from selecting from m items, while the selected items must fit in n resources constraints.
max
C 3j
(Packing)
max
Cj Ii
(L.P relaxation)
j=1
1=1
s.t.
Ayjz I b,, e [1.m]
s.t.
Ayæz S b,, Vi
[1,n]
==1
j=1
æ [0, 1)
Edge Covering Problem (SC). This is the dual problem of the Maximum Independent Set problem, which minimizes the number of chosen edges such that every vertice touches least edge.
min
Σ Ve
(EC)
min
Σ V
(LP relaxation)
E
CEE
s.t.
Σ ye 2 1, Vu
s.t.
Σ
Ye
2 1, Ve
e
eBe
y E {0, 1]
2 0
16

---

Set Covering (SC), Given a family of subsets S = {s1. few subsets as possible cover all elements in [n].
8m where S
[n], the goal is to select
min
Σ
U
(SC)
min
Σ ys
(LP relaxation)
SES
#ES
s.t.
Σ
V/
2 1, Vie [n]
s.t.
Σ
Vs 2 1, vi E [n]
#31
#31
10.
y 2 0
G Practical Problem
For the sake of more practical settings, we also included the Bipartite Maxflow problem (BMP) R4 which is common model formulation applied to areas such wireless communication. In our dataset, each bipartite graph obtained by deleting all edges between V' and U from fully connected bipartite graph, and then randomly sample from the remaining edges with probability of 60%, V' (and U' resp.) ) is a random subset consisting of half of the left nodes (and the right nodes). Based on the definition, respectively. In Table we report the performance of GD-Net and compare it against GCNs.
generated two sets of BMP problems with 1200 and 2000 nodes,
Table 8: Comparison of GD-Net and GCN BMP dataset
GD-Net
GCNs
#Nodes
Obj
A. Gap
R. Gap
Obj
A. Gap
R. Gap
1200
35398.62
429.8
1.20%
31206
4622.41 7703.14
12.89%
2000
58844.8
943.33
1.58%
52085
12.88%
Based on the results, GD-Net consistently achieves better predictions compared to GCN, with an average only a 1% optimality gap from the optimal solutions.
Additionally, we evaluated GD-Net against the conventional Ford-Fulkerson method, which is specifically designed for solving Maxflow problems. In Table we report the time for Ford-Fulkerson to find solutions with the same quality of solutions predicted by GD-Net.
Table 9: Comparison of GD-Net and Ford-Fulkerson on different datasets
#Nodes
GD-Net Obj
GD-Net Time
Ford-Fulkerson Time
1200
35398.69 62
0.592s
2.152s
2000
58844.80
1.691s
9.184s
The results highlight that GD-Net is significantly faster than the Ford Fulkerson heuristic in achieving high-quality solutions, demonstrating its efficiency and effectiveness.
Table 10: Inference profiling of the proposed GD-Net and GCNs from 29 Both the Inference time and the number of parameters are reported. All times are reported seconds. Results are averaged across 100 instances.
Model
# Parms.
IS
Packing
ECP
SC
S
M
L
S
M
S
M
S
M
L
GCNs 29
34,306
0.671
2.791
1.731
0.819
1.115
1.356
0.649
2.618
3.079
0.765
3.302
3.159 0.080
GD-Net
1,656
0.004
0.063
0.099
0.044
0.065
0.081
0.102 0.105 0.240
0.046
0.102
H Inference time profiling
To demonstrate the efficiency scalability GD-Nets, we present the average inference times of two models in Table I0] We that GD-Nets consistently achieve faster inference times than
17

---

GCNs do. Furthermore, GD-Nets display strong scalability: their inference times remain comparably acceptable even as problem sizes increase. In contrast, GCNs require substantially more time to process and predict for larger problem instances.
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In Sections
and we prove theoretical theorems and propose NN architecture. In Section we provide the experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Section discusses the limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
19

---

We put the proof of theoretical results in the appendix, and the algorithm we cited was accurately described in Section 2 and followed by a brief explanation of why is correct.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide all information of our GNN architectures in Sections 3 and and the experiment setting and code in Section
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
20

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Our code can be found at https//aaaoyyoooosspppsssccccccc The dataset is provided in Section 5
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
public/guides/ Soaeleess/CooeSSSmmmsiiinoooee
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ https/cccppllligggddeeeeeeeeeeee Coaee///ddeSebmmmcia ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We specify all the training and test details in Section 5 and the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: We did not provide the error bar since the experiments are relatively expensive repeat for multiple runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
21

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Section 5 and the appendix provide sufficient information on the computer resources needed to reproduce the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question:
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htilgggttttss///arrrr...pppoo/op
Answer: [Yes]
Justification: The research conducted in this paper conforms with the NeurlPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper about GNN's ability to solve LPs, which doesn't have direct societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
22

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All assets are properly cited.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
23

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing experiments nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing experiments research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
24

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "FYIQzYV3NC", "reviewer": "Reviewer_xnS6", "summary": "The paper investigates the capability of small-sized Graph Neural Networks (GNNs) to solve linear programming (LP) problems, specifically focusing on polylogarithmic-depth, constant-width GNNs. It provides both theoretical proofs and empirical evidence demonstrating that these GNN architectures can effectively solve packing and covering LPs, which are common in various optimization contexts. The introduction of a novel GNN architecture, termed GD-Net, is highlighted, showing superior performance in terms of parameter efficiency and problem-solving capability compared to traditional GNNs.", "questions": "1. Could the authors elaborate on potential modifications or extensions of the GD-Net architecture that might enable it to handle a broader range of LPs or even mixed integer linear programming problems?\n2. What are the limitations in terms of scalability when dealing with extremely large datasets or more complex network architectures?", "limitations": "**Generalizability**: The techniques are validated primarily on packing and covering LPs, and there is limited discussion on their effectiveness for other classes of LPs or more complex optimization tasks.\n\nAlthough I am not an expert in this specific area, the encouraging results give the L2O community some guidance on designing GNN architectures and sizes. I defer to other reviewers for a more detailed critique.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. **Theoretical Foundation**: The paper successfully bridges the gap between theoretical predictions and empirical results by proving that small-sized GNNs can efficiently solve packing and covering LPs.\n2. **Innovative Architecture**: The introduction of GD-Net, which significantly outperforms existing GNN models using fewer parameters, provides practical insights into the design of efficient neural network architectures for optimization problems.\n3. **Comprehensive Experiments**: Extensive empirical evaluations demonstrate the effectiveness of the proposed approach across different datasets and problem sizes, which solidifies the paper’s claims.\n4. **Impactful**: As you noted, the results are inspiring and provide valuable guidance for the L2O community on GNN structure and size design.", "weaknesses": "**Scope of Applicability**: The paper primarily focuses on packing and covering LPs. The generalizability of the proposed methods to other types of LPs or optimization problems is not addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **Q1: Could the authors elaborate on potential modifications or extensions of the GD-Net architecture that might enable it to handle a broader range of LPs or even mixed integer linear programming problems?**\n\nA1: Intuitively, GD-Nets can be viewed as unrolling the gradient descent on a carefully selected potential function. This potential function is differentiable and convex; more importantly, any stationary point of the potential function is a nearly optimal solution. For a broader class of LPs and even MILPs, a natural potential modification of the GD-net is to design another potential function that still enjoys the above good properties.\n\n---\n> **Q2: What are the limitations in terms of scalability when dealing with extremely large datasets or more complex network architectures?**\n\nA2: If we understand the question correctly (please tell us if not so), \"extremely large datasets\" means datasets on large problem dimensions, say, LPs with 10,000 variables or above. When dealing with such datasets, we need complex network architectures with more parameters. There are two main limitations in terms of scalability that need to be addressed. \n\n**Computational resources**: Handling large datasets requires longer training time, a larger amount of memory, and higher costs for infrastructure. Systems with limited resources would struggle to handle large datasets, resulting in performance issues and inefficiencies. In that sense, designing more parameter-efficient L2O networks is crucial for scaling up and enhancing performance in resource-constrained systems. Our GD-Net, for example, offers an improvement in parameter efficiency compared to traditional GCNs. Besides, efficient training and inference methods are also needed to reduce computational costs. \n\n**Number of training examples**: As the problem dimension grows and the network becomes more complex (with more parameters), the risk of overfitting (a.k.a. poor generalization) also increases. To mitigate overfitting, the number of training examples should grow along with the problem dimension and model parameters. This post a challenge on data collection. Efficient data generation methods or self-supervised training paradigms can be leveraged to resolve this challenge.\n\nThanks for the inspiring comments. We will add the above discussion on Q1 and Q2 in the next version.", "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": "", "extra_scores": {}}, {"review_id": "Os44Gb4MvH", "reviewer": "Reviewer_hJjQ", "summary": "This paper examines the expressive power of GNNs in representing linear programs (LPs). The authors first introduce a first-order iterative algorithm for packing and covering LPs, conceptualizing this algorithm as a GNN called GD-Net, applied to these LP types. They then provide a convergence rate of the proposed first-order algorithm, deriving a complexity upper bound for GNNs representing LPs. Finally, numerical experiments compare the performance of GD-Net with a general GCN.", "questions": "Refer to \"Weaknesses\".", "limitations": "This theoretical paper appears to have no potential negative societal impact.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 1, "strengths": "The writing is clear and easy to follow. The mathematical aspects of the paper are technically correct.", "weaknesses": "The paper lacks significant contributions.\n\n- The idea of conceptualizing iterative algorithms as GNNs is not novel:\n  - Yang et al. \"Graph Neural Networks Inspired by Classical Iterative Algorithms.\" ICML 2021.\n  - Zhang and Zhao. \"Towards Understanding Graph Neural Networks: An Algorithm Unrolling Perspective.\" 2022.\n\n- The convergence rate of first-order algorithms for LPs is not new, even though GD-Net is not exactly the same with existing algorithms. For example:\n  - Wang and Shroff. \"A New Alternating Direction Method for Linear Programming.\" NeurIPS 2017.\n  - Applegate et al. \"Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness.\" Mathematical Programming 2023.\n\nNote that these papers provide exact linear convergence rates, which are better than GD-Net's sublinear rate that only converges to an approximate solution. Additionally, the sublinear rate itself is not new, as it is provided by Awerbuch and Khandekar.\n\n- The empirical performance of GD-Net is not convincing. The paper only compares GD-Net with GCN, without showing advantages over traditional algorithms like ADMM or PDHG. Furthermore, comparing with commercial LP solvers like CPLEX or Gurobi would be a more ambitious but necessary goal to demonstrate real-world applicability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **Q1: The idea of conceptualizing iterative algorithms as GNNs is not novel. The convergence rate of first-order algorithms for LPs is not new. Given existing linear rates, the sublinear rate of GD-Net is not good enough.** \n\nThanks for raising this insightful comment. We would like to make several clarifications on our contributions:\n \n(1) Our complexity bound of GD-Net focuses better **dependency (polylog) on problem sizes** $(m, n)$ rather than **better dependency on accuracy** $\\epsilon$. (The latter is the focus of most convergence rate analysis of optimization algorithms.) In terms of dependency on problem sizes, our result improves the best-known bound of L2O networks **from polynomial to polylogarithmic**.  \n\nWe remark that the polylogarithmic dependency on $n$ is a little surprising, as it means that: For packing/covering LPs, which are **global optimization** problems, GD-Net can solve a near optimal solution based on **very local information**.\n\n(2) Our bound is established by unrolling a carefully chosen algorithm (i.e., AK algorithm). We are not aware of any other existing first-order algorithm such that unrolling it would lead to a polylog depth GNN. \n\nFor example, consider the LP instance\n$$\\max_{x\\geq 0} \\quad 1^T x$$\n$$\\mbox{s.t.} \\quad Ax \\leq 1$$\nwhere A is an $n\\times n$ Boolean matrix and contains three ones in each row and each column. Observe that the optimal solution is $(1/3,1/3,…,1/3)$. For any constant $\\epsilon$, then the algorithm proposed by the paper “A New Alternating Direction Method for Linear Programming” needs $\\Omega(n)$ iterations (since $R_x=\\sup_k |x^k|=\\Omega (n)$); in contrast, the GD-net only needs $\\mathrm{polylog}(n)$ layers, exponentially better than $\\Omega(n)$.\n\n---------------------------------------------------\n\n> **Q2: The empirical performance of GD-Net is not convincing. The paper only compares GD-Net with GCN, without showing advantages over traditional algorithms like ADMM or PDHG. Furthermore, comparing with commercial LP solvers like CPLEX or Gurobi would be a more ambitious but necessary goal to demonstrate real-world applicability.**\n\nA2: We conduct experiments comparing GD-Net with PDLP [R1] and Gurobi. The table below presents the time taken by each method to achieve the same optimality to our GD-Net:\n\n| Ins.    | #Vars. |     Opt | GD-Net Obj | GD-Net time |   Gurobi |   PDLP |\n| :------ | -----: | ------: | ---------: | ----------: | -------: | -----: |\n|         |  1,000 |   3.334 |      3.701 |  **0.105s** |   0.244s | 0.919s |\n| Cover   |  5,000 | 100.667 |    130.931 |  **0.218s** |   9.401s | 0.921s |\n|         | 10,000 | 407.386 |    546.666 |  **0.335s** | 103.322s | 1.001s |\n|         |        |         |            |             |          |        |\n|         |  1,000 |   3.334 |      3.018 |  **0.095s** |   0.208s | 0.746s |\n| Packing |  5,000 |  100.88 |     78.994 |  **0.216s** |   3.980s | 0.756s |\n|         | 10,000 | 406.946 |     302.04 |  **0.314s** |   8.593s | 0.809s |\n|         |        |         |            |             |          |        |\n\nIt shows that GD-Net consistently outperforms both Gurobi and PDLP in terms of speed while achieving comparable or superior objective values. More complementary experiments are presented in Author Rebuttal to bolster the robustness of our methods. \n\n[R1] David Applegate, et. al. Practical large-scale linear programming using primal-dual hybrid gradient, 2022.", "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": "", "extra_scores": {}}, {"review_id": "Ok3nJS3sH9", "reviewer": "Reviewer_h5Xh", "summary": "This paper explores the effectiveness of small-sized GNNs in solving LP problems, addressing the discrepancy between theoretical predictions requiring large GNNs and empirical observations showing small GNNs' capability. The authors provide a theoretical foundation for the success of compact GNNs by proving that GNNs with polylogarithmic depth and constant width can solve specific LP classes, such as packing and covering LPs, by simulating a variant of the gradient descent algorithm. They introduce a novel GNN architecture, GD-Net, which outperforms traditional GNN models with fewer parameters. This understanding could lead to more efficient MILP solvers and reduce computational resources needed for solving LPs.", "questions": "1. The paper claims that it closes the gap between theoretical and empirical perspectives in GNN-based LP solvers by illustrating the relationship between GD-Net and the AK algorithm. However, it has been observed that previous empirical studies predominantly utilized general-purpose GNNs, such as GCNs. Could similar theorems be achieved with general GNN backbones?\n\n2. The demonstration that polylogarithmic-depth and constant-width GNNs can approximately solve LP problems is compelling. To better understand the significance of this result, could the authors discuss how close these findings are to the theoretical lower bound of what is required to solve LP problems?\n\n3. This paper relaxes MILP problems to LPs and uses them as benchmarks, which may not fully reflect the practical significance of the proposed method. I suggest adopting more standard LP benchmarks and comparing GD-Net with heuristic algorithms.\n\n4. In the specific setting described by [23], it is noted that GCNs underperform compared to GEN. To provide a comprehensive evaluation landscape, would it be possible for the authors to include GEN as a baseline in Table 1? This addition would help readers better assess the relative performance enhancements introduced by GD-Net.\n\n5. The paper highlights the unique advantage of unrolling methods in achieving exceptional size generalization. However, the current presentation in Table 2 might not fully capture this advantage. Would the authors consider augmenting their experimental setup to include:\n- Training on medium-scale datasets and testing on both small and large-scale datasets;\n- Introducing the performance of GCNs as baselines for a direct comparison;", "limitations": "Yes", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper successfully establishes a novel and intriguing link between the AK algorithm and GNNs. This connection is not only innovative but also has the potential to spark interest and pave the way for future research in the field. \n\n2. The introduction of the unrolled GNN architecture represents a contribution to GNN-based LP and MILP solvers.", "weaknesses": "There are several areas where improvements could significantly enhance its contributions. Addressing these points satisfactorily would make a strong case for elevating the paper's status to \"Accept\".\n\n1. The presentation of Theorems 2-4, given that GD-Net is an unrolled version of the AK algorithm, appears somewhat straightforward (Question 1,2).\n\n2. To convincingly demonstrate the performance superiority of the proposed methods, it is crucial to include more realistic benchmarks and baselines for comparison (Question 3, 4).\n\n3. Given that unrolled neural networks typically enjoy several advantages over more general neural architectures, it would be highly beneficial for the paper to explicitly verify these benefits in the context of the proposed GD-Net (Question 5).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **Q1: It has been observed that previous empirical studies predominantly utilized general-purpose GNNs, such as GCNs. Could similar theorems be achieved with general GNN backbones?**\n\nA1: Yes, we can establish similar theorems with general-purpose GNNs. We can still derive polylog-depth in the bound, but constant width is no longer guaranteed. \n\nBy the universal approximation theorem, the ELU activation function can be simulated with arbitrary precision by a 2-layer and sufficiently wide perceptron. So if we replace each occurrence of ELU in GD-net with this 2-layer perceptron, we then obtain a GCN. Note that this GCN still has polylog-depth but the required width is no longer constant in $\\epsilon$.\n\nThanks for the comment. We will add this discussion in the next version.\n\n> **Q2: Could the authors discuss how close these findings are to the theoretical lower bound of what is required to solve LP problems?**\n\nA2: The polylogarithmic depth is also the lower bound, and thus our bound is tight. Due to the space limit, we kindly refer Reviewer to **Part 5: Tightness of Our Bound** in \"Author Rebuttal\" for further elaboration. Thanks for the great comment. We will add this lower bound in the next version.\n\n> **Q3: This paper relaxes MILP problems to LPs and uses them as benchmarks, which may not fully reflect the practical significance of the proposed method. I suggest adopting more standard LP benchmarks and comparing GD-Net with heuristic algorithms.**\n\nA3:  We consider the Bipartite Maxflow, a common model formulation applied to areas such as wireless communication [R1]. In our dataset, each bipartite graph is obtained by deleting all edges between $V'$ and $U'$ from a fully connected bipartite graph, and then randomly sample from the remaining edges with a probability of 60%, where $V'$ (and $U'$ resp.) is a random subset consisting of half of the left nodes (and the right nodes). \n\n|        |          | GD-Net |           |       | GCN     |        |\n| ------ | -------- | ------ | --------- | ----- | ------- | ------ |\n| #Nodes | Obj      | A. Gap | R. Gap    | Obj   | A. Gap  | R. Gap |\n| 1200   | 35398.62 | 429.8  | **1.20%** | 31206 | 4622.41 | 12.89% |\n| 2000   | 58844.8  | 943.33 | **1.58%** | 52085 | 7703.14 | 12.88% |\n||||||||\n\nAccording to the result, GD-Net consistently obtains better prediction compared to GCN, with only 1% optimality gap from optimal solutions.\n\nWe also conducted comparisons against the Ford Fulkerson heuristic, specifically designed for solving maximum network flow problems. The table below presents the time taken to achieve the same optimality to GD-Net:\n\n| #Nodes | GD-Net Obj | GD-Net time | Ford Fulkerson time |\n| -: | -: | -: | -: |\n|1200 |35398.62 |0.592s |2.152s |\n|2000 |58844.80 |1.691s |9.184s |\n|||||\n\nGD-Net is significantly faster than the Ford Fulkerson heuristic in achieving high-quality solutions, demonstrating its efficiency and effectiveness.\n\n> **Q4: In the specific setting described by [23], it is noted that GCNs underperform compared to GEN. To provide a comprehensive evaluation landscape, would it be possible for the authors to include GEN as a baseline in Table 1? This addition would help readers better assess the relative performance enhancements introduced by GD-Net.**\n\nA4: We implemented the GEN [R2] model using the DGL package. The GEN model has 4 layers and a width of 64, the same as the implemented GD-Net. Experiment results show that GEN struggles with high training loss and consequently yields significantly lower-quality predictions compared to GD-Net and GCN:\n\n| Model  | #Params. | V. Err (Cover) | V. Err (Packing) |\n| ------ | -------- | -------------- | ---------------- |\n| GD-Net | 1,656    | 2.19E-6| 2.18E-4          |\n| GCN    | 34,306   | 1.81E-6        | 1.69E-4          |\n| GEN    | 18,177   | 0.021          | 0.024            |\n|||||\n\nNote that we have tuned hyper-parameters of GEN such as learning rate and dropout level, but GEN still under-performs GD-Net and GCN. This seems to contradict the results in [23] where GEN performs similarly or better than GCN. A potential reason for such discrepancy is that [23] applies GEN based on a tripartite modeling of LP, while our paper adopts the conventional bipartite modeling in [7].\n\n> **Q5: The paper highlights the unique advantage of unrolling methods in achieving exceptional size generalization. However, the current presentation in Table 2 might not fully capture this advantage. Would the authors consider augmenting their experimental setup to include:\n-Training on medium-scale datasets and testing on both small and large-scale datasets;\n-Introducing the performance of GCNs as baselines for a direct comparison;**\n\nA5: We train GD-Net on instances with 500 variables and generalize it to instances with 50 and 1,000 variables. The results are presented in the below table. \n||||GD-Net|||GCN||\n|:-|-:|-:|-:|-:|-:|-:|-:|\n|Ins| #Vars.|Obj|A. Gap|R. Gap|Obj|A. Gap|R. Gap |\n|Cover|50|5.009|1.631|**48.30%**|5.027|1.649|48.80%|\n||1000|6.186|2.788|83.60% |6.056|2.722|**81.70%**|\n|Packing|50|0.399|2.959|**88.10%**|0.331|3.028|90.20%|\n||1000|3.001|0.333|**10.00%**|3.001|0.333|**10.00%**|\n|||||||||\n\nWe see that while GD-Net requires much fewer parameters, it still achieves comparable or even better generalization as GCN does. \n\nThe results might not be satisfactory for scenarios with huge differences in problem sizes. However, our method can still accelerate the solving of non-negative LPs where training and testing distributions are similar. To our knowledge, no existing work in L2O has tackled the generalization problem across such a huge size gap. Resolving this issue is an interesting research topic for future.\n\n[R1] Li Wang, Huaqing Wu, Wei Wang, and Kwang-Cheng Chen. Socially enabled wireless networks: Resource allocation via bipartite graph matching. IEEE Communications Magazine, 53(10):128–135, 2015.\n\n[R2] Guohao Li, et al. Deepergcn: All you need to train deeper GCNs, 2020.", "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": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank the reviewers for their valuable comments. We provide detailed responses individually to each reviewer. Note that more than one reviewer suggested additional numerical experiments to bolster the robustness of our findings. We conduct these experiments and summarize as below.

---
**1. Comparison with Traditional Algorithms and Commercial Solvers:**

We include two additional baselines: a traditional algorithm PDLP [R2] and a commercial solver Gurobi. The table below presents the time taken by each method to achieve the same optimality to our GD-Net:

| Ins.    | #Vars. |     Opt | GD-Net Obj | GD-Net time |   Gurobi |   PDLP |
| :------ | -----: | ------: | ---------: | ----------: | -------: | -----: |
|         |  1,000 |   3.334 |      3.701 |  **0.105s** |   0.244s | 0.919s |
| Cover   |  5,000 | 100.667 |    130.931 |  **0.218s** |   9.401s | 0.921s |
|         | 10,000 | 407.386 |    546.666 |  **0.335s** | 103.322s | 1.001s |
|         |        |         |            |             |          |        |
|         |  1,000 |   3.334 |      3.018 |  **0.095s** |   0.208s | 0.746s |
| Packing |  5,000 |  100.88 |     78.994 |  **0.216s** |   3.980s | 0.756s |
|         | 10,000 | 406.946 |     302.04 |  **0.314s** |   8.593s | 0.809s |
|         |        |         |            |             |          |        |

GD-Net consistently outperforms both Gurobi and PDLP in terms of speed while achieving comparable or superior objective values.

---
**2.Comparison with GEN [R3]**

We implemented the GEN model using the DGL package. The GEN model has 4 layers and a width of 64, the same as the implemented GD-Net. Experiment results show that GEN struggles with high training loss and consequently yields significantly lower-quality predictions compared to GD-Net and GCN:

| Model  | #Params. | V. Err (Cover) | V. Err (Packing) |
| ------ | -------- | -------------- | ---------------- |
| GD-Net | 1,656    | 2.19E-6        | 2.18E-4          |
| GCN    | 34,306   | 1.81E-6        | 1.69E-4          |
| GEN    | 18,177   | 0.021          | 0.024            |
|        |          |                |                  |

---
**3. More Practical Setting**

We consider the Bipartite Maxflow, a common model formulation applied to areas such as wireless communication [R1]. In our dataset, each bipartite graph is obtained by deleting all edges between $V'$ and $U'$ from a fully connected bipartite graph, and then randomly sample from the remaining edges with a probability of 60%, where $V'$ (and $U'$ resp.) is a random subset consisting of half of the left nodes (and the right nodes). 

||| GD-Net ||| GCN     |        |
| ------ |-|-|-|-|-|- |
| #Nodes | Obj      | A. Gap | R. Gap    | Obj   | A. Gap  | R. Gap |
| 1200   | 35398.62 | 429.8  | **1.20%** | 31206 | 4622.41 | 12.89% |
| 2000   | 58844.8  | 943.33 | **1.58%** | 52085 | 7703.14 | 12.88% |
||||||||

According to the result, GD-Net consistently obtains better prediction compared to GCN, with only 1% optimality gap from optimal solutions.

We conducted comparisons against the Ford Fulkerson heuristic, specifically designed for solving maximum network flow problems. The table below presents the time taken to achieve the same optimality to GD-Net:

| #Nodes | GD-Net Obj | GD-Net time | Ford Fulkerson time |
| -: | -: | -: | -: |
|1200 |35398.62 |0.592s |2.152s |
|2000 |58844.80 |1.691s |9.184s |
|||||

GD-Net is significantly faster than the Ford Fulkerson heuristic in achieving high-quality solutions, demonstrating its efficiency and effectiveness.


---
**4. Size Generalization**

We train GD-Net on instances with 500 variables and generalize it to instances with 50 and 1,000 variables. The results are presented in the below table.

|         |          |       | GD-Net |            |       |    GCN |            |
| :------ | -------: | ----: | -----: | ---------: | ----: | -----: | ---------: |
| Ins     | #Vars. |   Obj | A. Gap |     R. Gap |   Obj | A. Gap |     R. Gap |
| Cover   |       50 | 5.009 |  1.631 | **48.30%** | 5.027 |  1.649 |     48.80% |
|         |     1000 | 6.186 |  2.788 |     83.60% | 6.056 |  2.722 | **81.70%** |
| Packing |       50 | 0.399 |  2.959 | **88.10%** | 0.331 |  3.028 |     90.20% |
|         |     1000 | 3.001 |  0.333 | **10.00%** | 3.001 |  0.333 | **10.00%** |
|         |          |       |        |            |       |        |            |

We see that the GD-Net while requiring much fewer parameters, still achieves comparable or even better generalization as GCN does. To the best of our knowledge, no existing work in L2O has tackled the generalization across such a huge size gap. Improving the large-gap size generalization is an interesting research topic for future research.


---
**5. Tightness of Our Bound**

Our main result says that “polylogarithmic-depth constant-width GNNs are expressive enough to solve packing/covering LPs." Here, we remark that the polylogarithmic dependency on depth is also necessary. 

Specifically, Kuhn et al. showed that (first paragraph on page 6 in [R4]): For the fractional maximum matching problem, a special kind of packing LP, every constant-factor approximation distributed algorithm requires at least $\Omega(\sqrt{\log n/\log\log n})$ rounds. Moreover, since one layer of GNNs can be naturally simulated by one round of distributed LP algorithms (see the second paragraph on page 5 in [R4]), we conclude that GNNs need at least $\Omega(\sqrt{\log n/\log\log n})$ layers.

[R1] Li Wang, Huaqing Wu, Wei Wang, and Kwang-Cheng Chen. Socially enabled wireless networks: Resource allocation via bipartite graph matching. IEEE Communications Magazine, 53(10):128–135, 2015.

[R2] David Applegate, et. al. Practical large-scale linear programming using primal-dual hybrid gradient, 2022.

[R3] Guohao Li, et al. Deepergcn: All you need to train deeper GCNs, 2020.

[R4] Fabian Kuhn, et. al. Local Computation: Lower and Upper Bounds. J. ACM 63(2): 17:1-17:44 (2016).

Meta-review: The paper studies the effectiveness of GNNs for solving LPs, through connections with a variant of gradient descent on specific potential functions. The reviewers found the proposed method effective and of interest to the community.
Decision: Accept (poster)