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_cc_2024_Conference
Published: 2024-05-15 15:58:59

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.

Main paper: 
 introduction: 
 Learning to Optimize (L2O) has emerged as a compelling research area, leveraging machine learning techniques to enhance the efficiency of optimization processes. Unlike traditional theory-driven optimization methods, L2O 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 [4, 21] .Recently, graph neural networks (GNN) have become increasingly popular in the field of L2O [6, 27] . GNNs are a 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 as 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-based reformulation method for LP to enhance the solver performance. Furthermore, Chen et al. [8] and As larger networks usually require more training examples and higher computational resources, addressing this question is not only of theoretical interest but also provides potential guidance to L2O 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-efficient 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-bound 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 [9-11, 23, 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.In this paper, we show that polylogarithmic-depth 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 LP and its dual covering LP are nonnegative LPs of the canonical form: max{c T • x | Ax ≤ b, x ≥ 0} and min{b T • y | A T y ≥ c, y ≥ 0} respectively. Here, A ∈ R n×m ≥0 , b ∈ R n ≥0 , and c ∈ R m ≥0 . Packing LPs and covering LPs are broad classes of linear programming problems that can be used to approximate or relax a 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 form [2] , where the vectors b and c are all-ones vectors and A ij 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 1 and 2), 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 (1 + ϵ)-approximate solution in polylog(mnA max /ϵ) iterations. Therefore, we affirm the feasibility of solving general packing and covering LPs with polylogarithmic-depth constant-width GNNs. Here, we remark that the polylogarithmic dependency on depth is also necessary. Specifically, Kuhn et al. [16] showed that: for the fractional maximum matching problem, a special kind of packing LP, every constant-factor approximation distributed algorithm requires at least Ω( log 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 Ω( log n/ log log n) 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 to given problem instance distributions. Experiments across various datasets demonstrate that GD-Net outperforms classical graph convolutional network (GCN), a predominant GNN architecture in L2O 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-efficient GNNs for L2O. This direction involves developing architectures that can simulate well-established, theoretically grounded algorithms, potentially leading to improvements in both computational efficiency and solution quality.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 algorithm) as GNNs, they suggest that message-passing neural networks with a 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 of 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. [7] 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 a unified optimization framework for GNNs. 
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 1 p×q denote the p × q-dimensional all-ones matrix, and 1 p denote the p-dimensional all-ones column vector. Similarly, we can define 0 p×q and 0 p .Algorithm for packing LPs. Awerbuch and Khandekar [2] proposed a simple (1+ϵ)-approximation algorithm for packing LPs of the normal form:EQUATIONwhere A ij , b i , c j are all non-negative and A ij is either 0 or ≥ 1. The algorithm is described as follows:given parameters µ = 1 ϵ • ln mAmax ϵ , α = ϵ 4 , β = α 10µ, and δ = α 10µnAmax ; -Start with x := 0 m ; Then, repeat the following procedure:1. y i := exp[µ • (A i x -1)] for each i ∈ [n]; 2. For any j ∈ [m] do (a) If A T j y ≤ 1 -α, then x j := max{x j • (1 + β), δ}; (b) If A T j y ≥ 1 + α, then x j := x j • (1 -β).Algorithm 1: Our variant of Awerbuch-Khandekar algorithm for packing LPsInput: A n × m matrix A where A ij is either zero or no less than 1, and ϵ > 0.Parameter:µ := 1 ϵ • ln mAmax ϵ , α = ϵ 4 , β = α 10µ , and δ = α 10µnAmax ; Initialize x 0 := 0; for k = 0 to K -1 do y k i := exp[µ(A i x k -1)] for any i ∈ [n]; for each j ∈ [m] do if A T j y k ≤ 1 -α then x k+1 j := x k j • (1 + β) + δ; if A T j y k ≥ 1 + α then x k+1 j := x k j • (1 -β); Output: x K .The intuition behind this algorithm is that it can be viewed as applying gradient descent on a carefully chosen potential function defined asΦ p (x) = n i=1 y i (x) µ - m j=1 x j = n i=1 exp[µ(A i x -1)] µ - m j=1x j , which enjoys the following nice properties [2] : (i) Φ p (x) is differentiable and convex; (ii) ∇Φ p (x) = A T y; and (iii) any stationary point of Φ p is a nearly optimal solution to the packing LP (1): For any x where ∇Φ p (x) = 0, x is feasible and1 T • x ≥ (1 -4ϵ) • OPT.It turns out that this algorithm has polylogarithmic convergence [2] . Precisely, given any ϵ > 0, this algorithm always maintains a feasible solution (i.e. x ≥ 0 and Ax ≤ 1 always hold), and returns a (1 + ϵ)-approximation solution to the packing LP (1) in Õ(ln 2 (mA max ) • ln 2 (nA max )/ϵ 5 ) iterations. Here Õ hides lower order terms like ln ln(mnA max ) and ln(1/ϵ).Algorithm for covering LPs. In the same paper [2] , Awerbuch and Khandekar also considered solving the dual covering LP of the normal formEQUATIONand designed the following algorithm: given µ := 1 ϵ • ln nAmax ϵ , α = ϵ 4 , β = α 20µ , and δ = α 20µmAmax , -Start with y := 1 n ; Then repeat the following procedure:1. x j := exp[µ • (1 -A T j y)] for each j ∈ [m]; 2. For any i ∈ [n] do (a) If A i x ≥ 1 + α, then y i := max{y i • (1 + β), δ}; (b) If A i x ≤ 1 -α, then y i := y i • (1 -β).Similarly, this algorithm can also be thought of as applying a variant of gradient descent on a carefully selected potential function [2] :Φ c (y) = m j=1 x j (y) µ + n i=1 y i = m j=1 exp[µ(1 -A T j y)] µ + n i=1 y i ,which satisfies that: (i) Φ c (y) is differentiable and convex; (ii) ∇Φ c (y) = 1 -Ax; and (iii) for any y where ∇Φ d (y) = 0, y is feasible and 1 T • y ≤ (1 + 4ϵ) • OPT. This algorithm was shown to enjoy polylogarithmic convergence as well [2] . Formally, this algorithm always maintains a feasible solution (i.e. y ≥ 0 and A T y ≥ 1 always hold), and returns a (1 + ϵ)-approximation solution to the covering LP (2) in Õ(ln 2 (nA max ) • ln 2 (mnA max )/ϵ 5 ) iterations.A variant of Awerbuch-Khandekar algorithms. We propose a variant of the Awerbuch-Khandekar algorithms, specifically Algorithm 1 for solving packing LPs (1) and Algorithm 2 for covering LPs (2) . The motivation and advantage of our variant is that it can be simulated more naturally by GNNs.Input: A n × m matrix A where A ij is either zero or no less than 1, and ϵ > 0.Parameter:µ := 1 ϵ • ln nAmax ϵ , α = ϵ 4 , β = α 20µ , and δ = α 20µmAmax ; Initialize y 0 := 1; for k = 0 to K -1 do x k j := exp[µ(1 -A T j y k )] for any j ∈ [m]; for each i ∈ [n] do if A i x k ≥ 1 + α then y k+1 i := y k i • (1 + β) + δ ; if A i x k ≤ 1 -α then y k+1 i := y k i • (1 -β) ; Output: y K .Basically, we replace x j ← max{x j (1 + β), δ} with x j ← x j (1 + β) + δ in their algorithm for packing LPs, and y j ← max{y j (1 + β), δ} with y j ← y j (1 + β) + δ in their algorithm for covering LPs. Through almost the same proof, one can verify that the polylogarithmic convergence still holds.Theorem 1. Algorithm 1 always maintains a feasible solution and returns a (1 + ϵ)-approximation solution to the packing LP (1) in Õ(ln 2 (mA max ) • ln 2 (nA max )/ϵ 5 ) iterations.Algorithm 2 always maintains a feasible solution and returns a (1 + ϵ)-approximation solution to the covering LP (2) in Õ(ln 2 (nA max ) • ln 2 (mnA max )/ϵ 5 ) iterations.Connection to GNN. For LPs, an instance can be naturally encoded as a labeled bipartite graph [1, 3, 15, 25] , where (a) a left node represents a variable, (b) a right node represents a constraint (and equivalently, the associated dual variable), and (c) a left node and a right node are connected if the corresponding variable participates the corresponding constraint. In our GD algorithms, the matrix-vector multiplication Ax (or A T y) can be interpreted as a message passing step from left 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 a single layer of GNN.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: Section 6 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 in 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 well-specification, asymptotic approximations only holding locally). The authors should reflect on 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
design of packing gd-net: 
 By combining the idea of Algorithm 1 and techniques from graph neural networks, we design a graph neural network architecture, named packing GD-Net, for solving packing LPs.One iteration of Algorithm 1 consists of two steps: first, the algorithm updates y from x, and calculates the gradient ∇Φ p (x) = A T y -1; second, using ∇Φ p (x), it applies a variant of gradient descent to update x. 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 k i = exp[µ(A i x k -1)]. We will fix the parameter α in ELU to 1, then ELU(t) + 1 = exp(t) for t ≤ 0. In addition, as mentioned in Theorem 1, A i x k -1 ≤ 0 always holds in the execution of Algorithm 1. Thus the ELU function can exactly replicate the y-update. Specifically, our packing GD-Net updates y as follows:EQUATION)Since α is fixed to 1 and µ is fixed to 1 ϵ • ln mAmax ϵ , no learnable parameters are involved here.Learnable gradient descent procedure. The gradient descent in Algorithm 1 can be rewritten as where f, g : R → R are sums of Heaviside step functions defined as:x k+1 j :=x k j + f A T j y k -1 • x k j + g A T j y k -1 = x k j + f (∂Φ p /∂x j ) • x k j + g ∂Φ p /∂x jEQUATIONAs the Heaviside step function can be naturally approximated by the sigmoid function σ(t) = 1 1+exp(-t) , the packing GD-Net adopts the following learnable functions as substitutes for f and g:EQUATIONandEQUATIONNote that it is guaranteed that f θ k (t) = -f θ k (-t), in particular f θ k (0) = 0, and g θ k (0) = 0. So if the packing GD-Net reaches a stationary point of Φ p , it will remain there. Additionally, the packing GD-Net applies the ReLU activation to keep x k j ≥ 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 x k into a (m × d)-dimensional matrix X k , and n-dimensional column vector y k into a (n × d)-dimensional matrix Y k . Now, we are ready to present the packing GD-Net architecture:-Initialize X 0 := 0 m×d and Y 0 = 0 n×d .-For k = 0, 1, 2, • • • , K -1 • Y k := ELU µ(A i X k -1 n×d ) + 1 n×d . • X k+1 = ReLU X k + f θ k A T Y k -1 m×d • X k + g θ k A T Y k -1 m×d • W k . -Output x f inal := X K • w K ∈ R m .Here, • denotes entry-wise multiplication (a.k.a. Hadamard product), and f θ k , g θ k : R → R are applied entrywise to the matrixA T Y k -1 m×d . The learnable parameter is Θ := {θ k , W k } K-1 k=0 ∪ {w K }, where θ k = {θ k ℓ,1 , θ k ℓ,2 , θ k ℓ,3 } L1 ℓ=1 ∪ {θ k ℓ,4 , θ k ℓ,5 , θ k ℓ,6 } L2 ℓ=1 , W k ∈ R d×d , and w K ∈ R d×1 . So the total number of parameters is K • (d 2 + 3L 1 + 3L 2 ) + d.The following theorem reveals the ability of the packing GD-Net to reproduce Algorithm 1 with arbitrarily small precision.Theorem 2. Given any network depth K, any network width d ≥ 1, and any precison η > 0, there exists a K-layer packing GD-Net with a specific choice of parameters such that, for any packing LP instance (1), ∥x f inalx alg ∥ ≤ η. Here, x alg is the output of K-iteration Algorithm 1.By combining Theorems 1 and 2, we conclude that the packing GD-Nets with polylogarithmic depth and constant width are sufficient to solve packing LPs. Theorem 3. Given any ϵ > 0 and η > 0, there exists a packing GD-Net of Õ(ln 2 (mA max ) • ln 2 (nA max )/ϵ 5 ) depth and constant width, using the parameter assignment Θ GD , that satisfies the following condition: For any packing LP instance (1), x f inal is η-close to being a (1+ϵ)-approximate solution. Remark 1. We can establish a 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. Specifically, 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 a constant.Network training. The training data set is a set I = {(A, x * )} of packing LP instances in the normal form. More specifically, the input of an instance is identified by the constraint matrix A, with b and c being both all-ones vectors; the label x * represents the corresponding optimal solution. Let x f inal (Θ, 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 Θ * minimizing loss function defined as:L p (I; Θ) = 1 |I| (A,x * )∈I ∥x f inal (Θ, A) -x * ∥ 2 .Feasibility resortation. Note that the x f inal returned by packing GD-Net may be infeasible. To restore feasibility, we implement the following post-processing procedure:-First, for each j ∈ [m], update x j := max(0, min(1, x j ));-Then, for i = 1 to n do• If A i x ≥ 1, then update x j := xj Aix for each j with A ij ̸ = 0.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: Our code can be found at https://anonymous.4open.science/r/GD-Net-6FC7/.The dataset is provided in Section 5.Guidelines:• The answer NA means that paper does not include experiments requiring code. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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 as 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 or 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
design of covering gd-net: 
 In one iteration of Algorithm 2, the process begins by updating x from y, followed by the calculation of the gradient ∇Φ d (y) = 1 -Ax. Finally, it applies a variant of gradient descent to update y. Our covering GD-Net retains the original x-update and gradient-calculation modules, but replaces the gradient descent with a learnable neural network block to accelerate convergence.Architecture of covering GD-Net. Similarly, we substitute the ELU activation with α fixed to 1 for the exp(•) function, and replace the x-updateEQUATIONAs we will show in Theorem 4, (7) can exactly simulate the x-update in Algorithm 2.The gradient descent procedure in Algorithm 2 can be rewritten asy k+1 i :=y k i + f 1 -A i x k • y k i + g 1 -A i x k = y k i + f (∂Φ d /∂y i ) • y k i + g ∂Φ d /∂y i 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 f and g with the learnable functions f θ k and g θ k defined in ( 5) and ( 6) respectively. In addition, we also apply ReLU to keep y k i ≥ 0. Besides, the channel expansion technique is also incorporated: similarly, we expandx k ∈ R m into X k ∈ R m×d , and y k ∈ R n into Y k ∈ R n×d .Then, we propose our covering GD-Net architecture:-Initialize Y 0 := 1 n×d and X 0 = 1 m×d .-For k = 0, 1, 2, • • • , K -1 • X k := ELU µ(1 m×d -A T Y k ) + 1 m×d ; • Y k+1 = ReLU Y k + f θ k 1 n×d -AX k • Y k + g θ k 1 n×d -AX k • W k . -Output y f inal := Y K • w K ∈ R n . The learnable parameter is Θ := {θ k , W k } K-1 k=0 ∪ {w K }, where θ k = {θ k ℓ,1 , θ k ℓ,2 , θ k ℓ,3 } L1 ℓ=1 ∪ {θ k ℓ,4 , θ k ℓ,5 , θ k ℓ,6 } L2 ℓ=1 , W k ∈ R d×d , and w K ∈ R d×1 . So the total number of parameters is K • (d 2 + 3L 1 + 3L 2 ) + d, the same as in packing GD-Net.Theorem 4. Given any network depth K, any network width d ≥ 1, and any precison η > 0, there exists a K-layer covering GD-Net with a specific choice of parameters such that, for any covering LP instance (2), ∥y f inaly alg ∥ ≤ η. Here, y alg is the output of K-iteration Algorithm 2.Theorems 1 and 4 together imply the capacity of polylogarithmic-depth constant-width covering GD-Nets for solving covering LPs.Theorem 5. Given any ϵ > 0 and η > 0, there exists a covering GD-Net of Õ(ln 2 (nA max ) • ln 2 (mnA max )/ϵ 5 ) depth and constant width, using the parameter assignment Θ GD , that satisfies the following condition: For any covering LP instance (2), y f inal is η-close to being a (1 + ϵ)approximate solution.Remark 2. Similar to Remark 1, we can establish a similar theorem with general-purpose 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, y * ) consisting of instances where y * is the optimal solution to the covering LP (2) with constraint matrix A. The goal of the training process is to find a parameter Θ * minimizing the following loss function:L c (I; Θ) := 1 |I| (A,y * )∈I ∥y f inal (Θ, A) -y * ∥ 2 2 ,Feasibility resortation. Since the y f inal may be infeasible, we implement the following postprocessing procedure to restore feasibility:-First, for each i ∈ [n], update y i := max(0, min(1, y i ));-Then, for j = 1 to m do• If A T j y ≤ 1, then update y i := yi A T j y for each i with A ij ̸ = 0.5 Experimental study 
experemental setup: 
 Datasets. We utilized four LP 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 [9, 29] . 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 instanceM i ≡ {A i , b i , c i } undergoes normalization to M i ≡ { Âi , 1 n , 1 m }.Subsequently, via the optimization solver SCIP [5] , we obtain the optimal solution and optimal objective value pair {x i , obj * i } for each instance M i . Finally, we utilize the input-target pair to compose the datasetD ≡ { Âi , x i } |M | i=1 .Models and Training settings. For comparison, our experiments also include the graph convolutional network (GCN), a predominant GNN architecture in L2O for LP and MILP. Specifically, we adopt the GCN implementation from [29] , which is tailored for predicting the optimal solutions 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 a 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, our code to conduct the experiments can be found at https://anonymous.4open.science/r/GD-Net-6FC7/.Metrics. To effectively evaluate the GNN's ability to solve LP problems, we employed two distinct metrics: the relative gap R. Gap = | obj i -obj * i |/obj * i and the absolute gap (A. Gap = | obj i -obj * i |), where obj i denotes the predicted objective value of the respective approach after feasibility restoration.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 1 , 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 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.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. Table 2 presents 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. To further demonstrate the effectiveness of the proposed framework, we include two additional baselines: the traditional first-order solver PDLP [19] 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 to 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. As shown in Table 3 , GD-Net consistently outperforms both general-purpose solvers on all datasets. Notably, PDLP, a first-order method known for its fast early-stage convergence, is unable to produce solutions of comparable quality to those of GD-Net in 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. In this case, it required up to 300× more time to converge to a solution of the same quality as GD-Net. These findings strongly support the effectiveness of GD-Net, demonstrating its capability to consistently generate high-quality solutions.Moreover, we also include experiments under a 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 L2O for MILP. Recall that GD-Nets can be viewed as unrolling the gradient descent on a carefully selected potential function with some good properties. For ( 2) and (3), a natural direction is to design other potential functions that still enjoy those good properties. 
safeguards: 
 Question: Does the paper describe 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)? 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 a 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 a best faith effort. 12. Licenses for existing assets Question: 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? Answer: [Yes] Justification: All assets are properly cited. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators.  
 
 Appendix: Recall that a packing LP and its dual covering LP are nonnegative LPs of the canonical form:max x c T x (Packing LP) min y b T y (Covering LP) s.t. Ax ≤ b s.t. A T y ≥ c x ≥ 0 y ≥ 0where all A ij , b i , and c j are non-negative. Their norm forms are those where b and c are both all-ones vectors and A ij is either zero or greater than 1.max x 1 T x min y 1 T y s.t. Ax ≤ 1 s.t. A T y ≥ 1 x ≥ 0 y ≥ 0The reduction to the normal form proceeds as follows. First, we can assume that each b i > 0 since otherwise all variables x j with A ij > 0 have to be zero and y i can be set to zero; similarly, we can assume each c j > 0 since otherwise x j can be set to zero and all variables y i with A ij > 0 have to be zero. Then, we can replace A ij by Âij = Aij bicj , replace b and c by all-ones vector, and work with variables xj = c j x j and ŷi = b i y i . Finally, we replace Âij by Ãij =Âij min{ Âi ′ j ′ | Âi ′ j ′ >0 } and work with xj = xj • min{ Âi ′ j ′ | Âi ′ j ′ >0 } and ỹi = ŷi • min{ Âi ′ j ′ | Âi ′ j ′ >0 }.Proof. As increasing the network width d does not decrease the expressive power, it suffices to show the theorem for d = 1. When d = 1 and w K = 1, then packing GD-Net reduces to -Initialize x 0 := 0 m and y 0 = 0 n .-For k = 0, 1, 2, • • • , K -1 • y k i := ELU µ(A i x k -1) + 1 for each i ∈ [n]; • x k+1 j := ReLU x k j + f θ k A T j y -1 • x k j + g θ k A T j y -1 for each j ∈ [m]; -Output x f inal := x K .For the y-update part, recalling that in the execution of Algorithm 1, x is always feasible, thus A i x -1 ≤ 0 (Theorem 1). Additionally, since α is fixed to 1, ELU(t) + 1 = exp[t] for t ≤ 0. Therefore, in Algorithm 1, we can replace y k i := exp[µ(A i x k -1)] with y k i := ELU µ(A i x k -1) + 1 without altering the algorithm's behavior.For the x-update part, we rewrite this update in Algorithm 1 asx k+1 j := x k j + f A T j y -1 • x k j + g A T j y -1 ,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 a sigmoid function with arbitrarily small error. Specifically, by settingL 1 = 1, θ 1,1 = -β, θ 1,3 = α • θ 1,2, and making θ k 1,2 sufficiently large, f θ k can approximate f with arbitrary precision. Similarly, by settingL 2 = 1, θ k 1,4 = -δ, θ k 1,6 = α • θ k 1,5, and making θ k 1,5 large enough, g can be approximated arbitrarily well by g θ k . Therefore, in Algorithm 1, if we substitutex k+1 j := x k j + f θ k A T j y -1 • x k j + g θ k A T j y -1 ,we will get the above reduced packing GD-Net, and the change of the output x K can be made arbitrarily small by appropriately choosing the parameter Θ.Proof. The proof is very similar to that of Theorem 2. First, we only need to show the theorem for d = 1, because it does not decrease the expressive power to increase the network width d. When d = 1, and by letting w K = 1, the covering GD-Net reduces to -Initialize y 0 := 1 n and x 0 = 1 m .-For k = 0, 1, 2, • • • , K -1 • x k j := ELU µ(1 -A T j y k ) + 1 for each j ∈ [m]; • y k+1 i := ReLU y k i + f θ k (1 -A i x) • y k i + g θ k 1 -A i x for each i ∈ [n]; -Output y f inal := y K .For the x-update part, recalling that in the execution of Algorithm 2, y is always feasible, thus 1 -A T j y ≤ 0 (Theorem 1). Additionally, since α is fixed to 1, ELU(t)+1 = exp[t] for t ≤ 0. Therefore, in Algorithm 2, we can replace x k j := exp[µ(1 -A T j y k )] with x k j := ELU µ(1 -A T j y k ) + 1 without altering the algorithm's behavior.For the y-update part, we rewrite this update in Algorithm 1 asy k+1 i := y k i + f (1 -A i x) • y k i + g 1 -A i x, where f and g are defined in (4) . As shown in the proof of Theorem 2, f θ k and g θ k can approximate f and g respectively with arbitrary precision. Therefore, in Algorithm 1, if we substitutey k+1 i := y k i + f θ k (1 -A i x) • y k i + g θ k 1 -A ix , then we will reach the above reduced covering GD-Net, and the change of the output y K can be made arbitrarily small by appropriately choosing the parameter Θ.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 4 different sizes, namely small (S), medium (M), large (L), and generalization (Gen). The detailed sizes of each size can be found in Table 4 5 6 7 .For the IS benchmarks, we generated instances of specified sizes using the Ecole library [28] . For ECP, we initially created IS instances, then converted these into their dual forms to obtain ECP instances. Regarding the SC and Packing datasets, we produced matrices of size m × n with a density of only density% non-zero entries. We then formulated the corresponding problems by transposing the matrix A or leaving it as is, depending on the dataset requirements. In this section, we 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.The goal is to select as many vertices as possible from an undirected graph G = {V, E} such that, no two vertices form a edge.max x v∈V x v (IS) max x v∈V x v (LP relaxation) s.t. x u + x v ≤ 1, ∀(u, v) ∈ E s.t. x u + x v ≤ 1, ∀(u, v) ∈ E x ∈ {0, 1} |V | x ≥ 0Packing Problem. The goal is to maximize the profit from selecting from m items, while the selected items must fit in n resources constraints.max x m j=1 c j • x j (Packing) max x m j=1 c j • x j (LP relaxation) s.t. n j=1 A ij x j ≤ b i , ∀i ∈ [1, n] s.t. n j=1 A ij x j ≤ b i , ∀i ∈ [1, n] x ∈ {0, 1} m x ≥ 0Edge 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 at least one edge. minFor the sake of more practical settings, we also included the Bipartite Maxflow problem (BMP) [34] , which is a common model formulation applied to areas such as wireless communication. 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%, V ′ (and U ′ resp.) is a random subset consisting of half of the left nodes (and the right nodes). Based on the definition, we generated two sets of BMP problems with 1200 and 2000 nodes, respectively. In Table 8 , we report the performance of GD-Net and compare it against GCNs. Based on the results, GD-Net consistently achieves better predictions compared to GCN, with an average of 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 9 , we report the time for Ford-Fulkerson to find solutions with the same quality of solutions predicted by GD-Net. The results highlight that GD-Net is significantly faster than the Ford Fulkerson heuristic in achieving high-quality solutions, demonstrating its efficiency and effectiveness. To demonstrate the efficiency and scalability of GD-Nets, we present the average inference times of two models in Table 10 . We see that GD-Nets consistently achieve faster inference times than 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.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 2, 3, and 4, we prove theoretical theorems and propose NN architecture. In Section 5, we provide the experimental results. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in 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 or 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. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: **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.
questions: 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?
2. What are the limitations in terms of scalability when dealing with extremely large datasets or more complex network architectures?
limitations: 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.

Although 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: The paper lacks significant contributions.

- The idea of conceptualizing iterative algorithms as GNNs is not novel:
  - Yang et al. "Graph Neural Networks Inspired by Classical Iterative Algorithms." ICML 2021.
  - Zhang and Zhao. "Towards Understanding Graph Neural Networks: An Algorithm Unrolling Perspective." 2022.

- 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:
  - Wang and Shroff. "A New Alternating Direction Method for Linear Programming." NeurIPS 2017.
  - Applegate et al. "Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness." Mathematical Programming 2023.

Note 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.

- 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.
questions: questions: Refer to "Weaknesses".
limitations: limitations: This theoretical paper appears to have no potential negative societal impact.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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".

1. The presentation of Theorems 2-4, given that GD-Net is an unrolled version of the AK algorithm, appears somewhat straightforward (Question 1,2).

2. 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).

3. 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).
questions: 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?

2. 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?

3. 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.

4. 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.

5. 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:
- Training on medium-scale datasets and testing on both small and large-scale datasets;
- Introducing the performance of GCNs as baselines for a direct comparison;
limitations: limitations: Yes

Comments: title: Response to authors
comment: > **Q2: Additional experiments. The results still appear unconvincing, as the "GD-Net Obj" is significantly higher than "Obj." Does this indicate that the objective/solution obtained by GD-Net is far from optimal? What are the accuracy (stopping tolerance) parameters for Gurobi and PDLP?**

**A2:** In our previous experiments, 

1. The parameter $\epsilon$ in GD-Net is set to be 0.2, which means GD-Net is expected to output a $(1+\epsilon)=1.2$-approximation solution. 
2. We run Gurobi and PDLP with default relative tolerance (precisely $10^{-6}$ for Gurobi, and $10^{-9}$ for PDLP), and stop them once they achieve the same objective value to the output of GD-Net.

We acknowledge that, in general, an L2O network may not achieve the very high precision of $10^{-6}$ or $10^{-9}$ that traditional optimization algorithms can reach. This is because traditional algorithms can run for an arbitrary number of iterations, given sufficient resources, while the layers of a neural network are fixed after training.

**However, L2O networks can still help accelerate the solving of optimization problems that require higher precision.** Specifically, as demonstrated in many related studies [R10, R11, R12], the L2O approach is often used to quickly generate feasible solutions or to provide strong initial warm-starts for traditional optimization algorithms. **Combining L2O networks with traditional optimization algorithms can achieve the desired precision faster than using traditional optimization algorithms alone.**

To demonstrate the practical utility of GD-Net, we conducted experiments to assess how effectively GD-Net can serve as a warm start to enhance the efficiency of PDLP. We measured the time it takes to solve problems via PDLP using warm starts provided by GD-Net, aiming to meet predefined stopping criteria. The relative tolerance was set at 1e-3, which is a typical precision requirement in real-world applications. We also recorded the time PDLP required to resolve instances for comparison. Additionally, we calculated the improvement ratio by comparing the time taken by PDLP alone with the time taken when using GD-Net's output as a warmstart.

|dataset|size|time for PDLP alone (s)|time for GD-Net + PDLP (s)|Improvement Ratio|
|-:|-:|-:|-:|-:|
|Packing|5000|5.461|4.920|9.906%|
|Covering|5000|6.893|5.619|18.483%|
||||||

The experimental results show that utilizing GD-Net as warm-starts can reduce the time of solving by about 10% and 18% respectively for Packing and Covering dataset, comapred to using PDLP alone.

We thank the reviewer again for the valuable comments and suggestions. We will include the above results and discussions in the manuscript.  

[R10] Qinyu Han et al. A GNN-guided predict-and-search framework for mixed-integer linear programming. ICLR, 2023.

[R11] Rajiv Sambharya et al. Learning to Warm-Start Fixed-Point Optimization Algorithms. JMLR, 2024.

[R12] Rajiv Sambharya et al. End-to-end learning to warm-start for real-time quadratic optimization. Learning for Dynamics and Control Conference, 2023.
**Contribution of our paper**: Despite the above discussion, we would like to kindly provide further comment on our paper's contribution. Our main contribution is not merely "proposing another new GNN architecture by unrolling another iterative algorithm." Instead, our major contribution is twofold.

1. We present a new **theoretical explanation** of the empirical phenomenon that small-size GNNs can solve LPs. Specifically, we show that polylog-depth constant-width GNNs are expressive enough to solve a broad class of LPs. Moreover, **this polylog bound is also tight** (Please see Part 5: Tightness of Our Bound in "Author Rebuttal" for details). 
2. For **practical use**, we propose a parameter-efficient and interpretable GNN architecture, namely GD-Net, for LPs. Experiments verifies its efficiency and effectiveness. Notably, GD-Net generates better solutions with an order of magnitude fewer parameters than GCN.

We believe the above contribution is not straightforward because of the following reasons.

1. This work is motivated by observing a significant gap between empirical phenomenon and theoretical explanation in L2O (learning to optimize). Precisely, in practice, GNN with a modest width and fewer than ten layers often suffice to achieve good performance in approximating LP with hundreds of nodes and constraints. However, the best-known theoretical explanation [R9] requires the depth of GNN to grow polynomially with the problem size.

2) The selection of AK algorithm is nontrivial. AK-algorithm can be viewed as applying a variant of gradient descent on a potential function. The design of potential function is careful and nontrivial, since it is required to be differentiable and convex; and more importantly, any stationary point of the potential function should be a nearly optimal solution. These properties make AK algorithm has low computational complexity. We are not aware of any existing other first-order algorithm such that unrolling it would lead to a polylog depth GNN. 

[R9] Chendi Qian, et. al. Exploring the power of graph neural networks in solving linear optimization problems. AISTATS 2024.
Thanks for your valuable feedback.

>  **Q1：Novelty. As I mentioned earlier, the concept of unrolling a first-order method as a GNN is not new. The two papers I referenced are just examples of this topic. I strongly recommend that the authors thoroughly review the references within these papers, as well as those that cite them. A comprehensive discussion of the existing literature would be beneficial.**

**A1**: Thanks for the comment and the helpful advice.

**Existing works on unrolling iterative algorithms as GNNs**: We acknowledge the reviewer’s point that unrolling first-order methods as GNNs has been explored in prior research. We will incorporate a comprehensive literature review in the revised version, as presented below. Please let us know if any other relevant works are missing from this review.

> 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. [R1] 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 algorithm) as GNNs, they suggest that message-passing neural networks with a 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. [R2] proposed a new family of GNN layers by unrolling and integrating the update rules of two classical iterative algorithms, namely the proximal gradient descent and iterative reweighted least squares. References [R3, R4] 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. [R5] proposed new GNNs to improve graph signal denoising by unrolling sparse coding and trend ﬁltering algorithms. References [R6, R7, R8] bridge the gap between graph convolution and iterative algorithms by providing a unified optimization framework for GNNs. 

[R1] Petar Velickovic, et. al. Neural Execution of Graph Algorithms. ICLR 2020.

[R2] Yongyi Yang, et. al. Graph Neural Networks Inspired by Classical Iterative Algorithms. ICML 2021.

[R3] Yao Ma, et. al. A unified view on graph neural networks as graph signal denoising. CKIM 2021.

[R4] Zepeng Zhang, and Ziping Zhao. Towards Understanding Graph Neural Networks: An Algorithm Unrolling Perspective. KDD 2022.

[R5] Siheng Chen, et. al. Graph unrolling networks: Interpretable neural networks for graph signal denoising. IEEE Transactions on Signal Processing, 2021.

[R6] Xuran Pan, et. al. A unified framework for convolution-based graph neural networks. Pattern Recognition, 2024.

[R7] Meiqi Zhu, et. al. Interpreting and unifying graph neural networks with an optimization framework, Proceedings of the Web Conference, 2021.

[R8] Hongwei Zhang, et. al. Revisiting graph convolutional network on semi-supervised node classification from an optimization perspective, *arXiv preprint arXiv:2009.11469* (2020).
I sincerely appreciate the authors' efforts during the rebuttal stage, including their responses to my questions and the additional experiments provided.

- The polylog complexity. I overlooked this aspect in my initial review. Thanks for pointing this out! I would like to tune my score based on this point.
- Novelty. As I mentioned earlier, the concept of unrolling a first-order method as a GNN is not new. The two papers I referenced are just examples on this topic. I strongly recommend that the authors thoroughly review the references within these papers, as well as those that cite them. A comprehensive discussion of the existing literature would be beneficial.
- Additional experiments. The results still appear unconvincing, as the "GD-Net Obj" is significantly higher than "Obj." Does this indicate that the objective/solution obtained by GD-Net is far from optimal? What are the accuracy (stopping tolerance) parameters for Gurobi and PDLP?
We greatly value your suggestions and recommendations. We will certainly incorporate the new results into our revised manuscript, as they not only strengthen our argument but also bridge the gap between theoretical bounds and practical applications.
Thank you for your encouraging and insightful feedback. We greatly appreciate your recognition of our efforts. Your insights are valuable as we advance our work. We will definitely incorporate these new results into our revised manuscript to further enhance our work.
Thank you for your detailed and thoughtful rebuttal. I appreciate the insights you've provided on extending the GD-Net architecture to handle a broader range of LPs and potentially MILPs, as well as the considerations for scalability with large datasets and complex network architectures. I'm genuinely excited to see how your work progresses and its potential application in the MILP domain. I will maintain my score, and I look forward to the future developments of your research.
Thanks for your detailed response. The response has addressed my concerns and I have raised my rating to 7. This work establishes a link between the AK algorithm and GNNs and develops the lower bound matching GNNs for LP problems. This connection is not only innovative but also has the potential to spark interest and pave the way for future research in the field. For instance, it may inspire future GNN works in MILP, which is a more challenging and significant area.