Towards Explaining the Power of Constant-depth Graph Neural Networks for Structured Linear Programming

We greatly value the reviewer's suggestions and recommendations. We provide a detailed clarification to address the reviewer’s concerns.

Q1: About the numerical experiments.

R1: In the new version, we've designed a GNN by unrolling our distributed LP algorithm (Algorithm 2), and conducted numerical experiments to validate our main finding (the expressive power of our GNN in solving sparse binary LP). Besides, we've also conducted experiments to compare our GNN with GCN, and the results show that Our GNN achieves much better performance while using significantly fewer parameters. Please see General Response: 2. Experiments for details.

Q2: About the the chain of reductions.

R2: Thank you for this valuable suggestion. In the revised version, we have explicitly clarified the chain of reduction in generality:

"generic LP => packing/covering LP (a.k.a. non-negative LP) => sparse binary LP => row-sparse column-sparse binary LP."

Q3: Have you implemented an run your LP? I think numerical issues like precision could play an additional role.

R3: In the new version, we have designed and implemented the GNN by unrolling Algorithm 2.

When designing the GNN, we've intentionally addressed potential numerical issues. For instance, if $x$ is supposed to be positive, we use $\exp(-\mathrm{ReLU}(x))$ rather than $\exp(-x)$ to prevent excessively large values. In our experiments with the designed GNN, we did not encounter any significant numerical issues.

Q4: Are you aware of an explicit counter example? this + a randomized average case numerical evaluation could really round of this paper in my eyes.

R4: The fractional minimum vertex cover (Fractional MVC) is such an explicit counterexample (cf. first paragraph on page 6 in [JACM16]). Specifically, given a graph $G=(V,E)$, the goal of MVC is to find a minimum vertex subset $S\subset V$, such that for each edge in $E$ at least one of its endpoints is in $S$. Fractional MVC is the linear programming relaxation of MVC, depicted as:

$\max_{\vec x} \quad \sum_{v\in V} x_v$

$\mbox{s.t.}\quad x_u+x_v\leq 1, \forall (u,v)\in E$

$x_u\geq 0$

Note that Fractional MVC is a sparse binary LP. Kuhn proved that (see the first paragraph on page 6 in [JACM16]): for every $k>0$, there exists a graph $G$ such that every $k$-round distributed algorithm for the fractional MVC problem has approximation ratios at least $\Omega(n^{c/k^2}/k)$ for a positive constant $c$. Choosing $k$ appropriately, this implies that to achieve a constant approximation ratio, every Fractional MVC algorithm requires at least $\Omega(\log n/\log\log n)$ rounds.

[JACM16] Kuhn et al. Local computation: Lower and upper bounds. JACM, 2016.

We appreciate the reviewer’s constructive feedback and provide a detailed clarification to address the reviewer’s concerns:

Q1: I feel that this paper is just translating known results for distributed algorithms to GNN language:

R1: We would like to direct the reviewer to General Response: clarification of novelty where we summarized our contributions. Specifically,

• About our technical contribution: our main theorem, Theorem 3, is proved by designing and unrolling a new distributed algorithm, rather than directly unrolling existing algorithms.
• About our conceptual contribution: except the connection between distributed LP algorithm and GNN, another crucial observation says that "the performance of GNNs is measured based on the average-case instance". The average-case analysis is necessary in the proof of Theorem 3, and offers a potential explanation for the impressive empirical success of PDHG-net on PageRank [ICML24].

[ICML24] Li et al. PDHG-unrolled learning-to-optimize method for large-scale linear programming. ICML 2024.

Q2: If you fix $\epsilon$ and $\eta$, then Theorem 2 and Theorem 3 are direct corollaries of Chen et al. (2023).

R2： We would like to respectfully and explicitly clarify that Theorems 2 and 3 are not corollaries of Chen et al. (2023).

The key distinction lies in the fact that the depth (and width) in Theorems 2 and 3 is independent of the instance size $m$ and $n$. Specifically, if $\epsilon$ and $\eta$ are fixed, the GNN depth is bounded by a universal constant, regardless of how large the LP instance is. In contrast, the GNN depth in Chen et al. (2023) implicitly depends on $m$ and $n$, and will go to infinite as $m$ and $n$ grow.

Q3: There are no numerical experiments.

R3: We've conducted numerical experiments to validate our findings (Theorem 3) and to support the applicability of our theory. Specifically, we've designed a GNN by unrolling our distributed LP algorithm (Algorithm 2), and then conducted numerical experiments to validate the expressive power of our GNN in solving sparse binary LP. Besides, we've also conducted experiments to compare our GNN with GCN, and the results show that Our GNN achieves much better performance while using significantly fewer parameters. Please see General Response: Experiments for details.

Hi, there,

As the discussion phase is coming to a close, we would like to ask whether your concerns have been addressed or you have any further comments.

Thank you,

The Authors

We appreciate the reviewer’s constructive feedback and provide a detailed clarification to address the reviewer’s concerns:

1. the title may overstate the contributions:

• While our main theorem (Theorem 3) focuses on specific classes of LPs, our key observations—(i) the connection between distributed LP algorithms and GNNs for LPs, and (ii) the necessity of average-case analysis—apply to general LPs as well.
• The inclusion of "towards" in the title is intended to reflect the exploratory nature of our work, highlighting its contribution to advancing understanding rather than claiming a complete solution. Constructing a constant-depth GNN (e.g., with ≤10 layers) for all LPs seems to be an overly ambitious goal.
• That said, we fully understand the reviewer’s concern. To better align with the scope of the paper, we change the title to "Towards Explaining the Power of Constant-depth Graph Neural Networks for Structured Linear Programming".

2. The novelty:

(2.1 The connection between GNN message passing and factorization-free LP algorithms is straightforward):

While we are not entirely certain of the precise definition of "factorization-free LP algorithms," we are not sure about the assertion that any $k$-iterations of such algorithms can always be simulated by a $k$-depth GNN. GNNs operate under specific communication constraints, where only variables and constraints directly connected in the bipartite graph (i.e., $u_j$ and $v_j$ where $A_{ij} \neq 0$) can exchange information in a single layer. This communication pattern may not align with the operations of all factorization-free LP algorithms.

(2.2 The results presented in this paper represent only a subset of these):

• We politely point out that Distributed LP algorithms are not a subset of first-order algorithms. While first-order methods (FOMs) typically involve gradient-based updates or matrix-vector operations, distributed LP algorithms are designed for communication-constrained environments, introducing computational complexity that extends beyond first-order methods.

• For example, distributed LP algorithms can include inherently combinatorial computations, such as localized subproblem optimizations, which are outside the standard framework of first-order algorithms (see [SODA06] for an example).

• Furthermore, as far as we know, existing first-order algorithms, such as PDHG or PDLP, can also be viewed as distributed LP algorithms. We acknowledge that we missed citing these important works and have included these citations in the new version.

(2.3 The theoretical contribution of this paper appears limited):

• Our main theorem, Theorem 3, is proved by designing and unrolling a new distributed algorithm, rather than directly unrolling existing algorithms.
• To the best of our knowledge, no existing FOMs can achieve constant-depth complexity when unrolled into a GNN, even for row-sparse column-sparse binary LPs. Such algorithms inherently depend on $m$ and $n$, either explicitly or implicitly. For instance, their convergence rates often depend on structural properties of the LP (e.g. $\|A\|_2$), which scale with the problem size $(m,n)$. This distinguishes our work, where we explicitly construct constant-depth GNNs for certain LP instances.

[SODA06] Kuhn et al. The price of being near-sighted. SODA 2006.

3. Practical effectiveness:

• For Theorem 2, the constant hidden in the big-O notation is $\leq 10$ after a careful analysis.

• For Theorem 3, the constant hidden in the big-O notation is $\leq 10\gamma\beta \cdot \log(\gamma\alpha\beta)/\epsilon^2$.

  For instance, if the GNN is required to output a 2-approximate solution for 99% fraction of LP instances where $m=n$ and $nnz(A)=10(m+n)$, then the upper bound is 54079, independent with the problem size $(m,n)$.

• While the theoretical constants may be large, in the new version, we have empirically demonstrated that a 5-layer GNN designed by unrolling Algorithm 2 is capable of solving sparse binary LPs. Specifically, we've designed a GNN by unrolling our distributed LP algorithm (Algorithm 2), and conducted numerical experiments to validate Theorem 3 (the expressive power of our GNN in solving sparse binary LP). Besides, we've also conducted experiments to compare our GNN with GCN, and the results show that Our GNN achieves much better performance while using significantly fewer parameters. Please see General Response: Experiments for details.

4. Absence of Experiment: We conduct numerical experiments to validate our findings and to support the applicability of our theory. Please refer to General Response: Experiments for experimental results.

I sincerely thank the authors for their efforts in revising the paper, particularly for adding numerical results, which have addressed some of my initial concerns. Accordingly, I have raised my score. However, I still recommend rejection, as several of my concerns remain unaddressed.

First, I still find the main message of the paper unconvincing. The paper essentially consists of two main components: (i) it acknowledges that shallow GNNs are effective in practice, presenting a newly added set of experiments to support this; and (ii) it provides an upper bound on the depth of GNNs (with an example of calculated value of 54079), which is actually quite large and cannot be considered "shallow." The paper attempts to integrate these two components into a cohesive narrative. However, I find that the connection between the main theoretical results (specifically Theorem 3) and the practical usage of shallow GNNs is not established.

Regarding the issue of overclaiming, I appreciate the authors' decision to change the title, which addresses most of my concerns in this regard. Nevertheless, in the updated paper, you assert that the "observations" apply to general LPs. This is somewhat confusing, as observations typically represent high-level ideas rather than rigorously proven results.

This leads me to the following questions. I would greatly appreciate it, and may consider further raising my score, if you can address them:

In my previous comment, I mentioned that the connection between GNN message passing and factorization-free LP algorithms is straightforward. I apologize for not providing clear definitions at that time. I would like to clarify by distinguishing between different classes of LP algorithms:

(a) Algorithms that use direct solvers (e.g., LU factorization, Cholesky factorization).

(b) Algorithms that can be translated into message passing on a graph, such as bipartite or tripartite graphs. Many first-order methods (FOMs) belong to this class, except those that use factorization for preconditioning. This class also includes certain combinatorial algorithms, such as shortest paths when expressed in a message-passing framework.

(c) Other algorithms or frameworks for solving LPs, including column generation, Benders decomposition, etc.

In my previous comment, I was specifically referring to algorithms in the second class, noting that it is straightforward to establish a correspondence between these algorithms and GNNs.

Based on this clarification, I have two specific questions for the authors:

1. In your Observation 1, does the term "any d-round distributed LP algorithm" refer to algorithms in any of the above classes, or is it more general and encompasses multiple classes?

2. You claim that "distributed LP algorithms can include inherently combinatorial computations, such as localized subproblem optimizations, which are outside the standard framework of first-order algorithms." Could you provide an example of such an algorithm (which includes localized subproblem optimizations) and assert that it can still be simulated by d-round GNNs?

Q: My primary concern with this paper is the applicability of its theoretical findings to practical GNNs. Specifically, if one were to train a GNN to solve packing/covering LPs, would the trained model align with the theoretical framework presented here? Do the theoretical observations in this paper truly correspond with practical outcomes?

R: Thank you for raising this insightful question. We've designed a GNN by unrolling our distributed algorithm (Algorithm 2), and conducted numerical experiments to validate Theorem 3 (the expressive power of our GNN in solving sparse binary LPs). Besides, we've conducted experiments to compare our GNN with GCN, and the results show that: compared to GCN, our GNN achieves much better performance while using significantly fewer parameters. Please refer to General Response: experiments for details.

We hope that these experiments could address your concerns.

2. Experiments

We appreciate the reviewers’ suggestions regarding numerical experiments to validate our findings. We have conducted experiments and summarized the outcomes below.

1. Compared to GCN, our GNN achieves much better performance while using significantly fewer parameters.

To assess the representational power of our method, we report the training loss after the model has converged. Additionally, we evaluate the relative gap. Using feasibility restoration (see Appendix), the final values $x^{final}$ and $y^{final}$ returned by our GNN are used to compute $x'$ and $y'$. The relative gaps are then calculated as follows: the relative gap of the primal is denoted as $RP=\frac{\text{obj}(x')-\text{opt}}{\text{opt}}$ and the relative gap of the dual is denoted as $RD=\frac{\text{obj}(y')-\text{opt}}{\text{opt}}$. A lower value of RP and RD indicate better performance.

The number of parameters in our method(2K) does not exceed 0.8% of the number of GCN parameters(250K), but basically, better results are realized.

2. Besides, we also conducted numerical experiments to validate Theorem 3 (the expressive power of our GNN in solving sparse binary LP). | Layers | L=1 | L=2 | L=3 | L=4 | L=5 | |---------|-----------|---------|---------|---------|---------| | Training loss | 0.0363 | 0.0088 | 0.0096| 0.0085| 0.0086| We report the relationship between the converged training loss and the number of layers $L$. Even for very small $L$, the training loss for convergence can already be close to 0