On the Power of Small-size Graph Neural Networks for Linear Programming

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?

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

By 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$.

Thanks for the comment. We will add this discussion in the next version.

Q2: Could the authors discuss how close these findings are to the theoretical lower bound of what is required to solve LP problems?

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

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.

A3: 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).

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

We 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:

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

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.

A4: 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:

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

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: -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;

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

We see that while GD-Net requires much fewer parameters, it still achieves comparable or even better generalization as GCN does.

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

[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] Guohao Li, et al. Deepergcn: All you need to train deeper GCNs, 2020.

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.

Thanks for raising this insightful comment. We would like to make several clarifications on our contributions:

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

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

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

For example, consider the LP instance $\max_{x\geq 0} \quad 1^T x$ $\mbox{s.t.} \quad Ax \leq 1$ where 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)$.

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.

A2: 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:

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

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

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?

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

Q2: What are the limitations in terms of scalability when dealing with extremely large datasets or more complex network architectures?

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

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.

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.

Thanks for the inspiring comments. We will add the above discussion on Q1 and Q2 in the next version.