Are Graph Neural Networks Optimal Approximation Algorithms?

We thank the reviewer for their feedback. We are glad that the reviewer finds that the paper is well-presented and explained and that they value both the empirical and theoretical aspects of this work!

Next, we address the weaknesses/questions in order:

Take the example of Max-Cut problem as an example, how to show the optimization problem are the same in equation (2) and the message-passing diagram shown in equation (3)? Same for other optimization problems discussed in the paper.

Let's take the Max-Cut problem as an example (equation 1). To update the embedding $v_i$ corresponding to node $i$ we take the gradient of the Lagrangian $\frac{\partial{\mathcal{L}(\mathbf{v})}}{\partial v_i}$. The update will be as follows: $v_i' = v_i - \eta \frac{\partial{\mathcal{L}(\mathbf{v})}}{\partial v_i}.$ For the Max-Cut problem, we can enforce the constraint by normalizing the embeddings. So we just need derivatives with respect to the objective from equation 1. It is hopefully easy to see that computing $\frac{\partial{\mathcal{L}(\mathbf{v})}}{\partial v_i}$ of the objective in equation 1 leads to the expression in the parenthesis in equation 2. The normalization for equation 2 enforces the constraint in equation 1. The central observation is that this kind of approach to minimizing the Lagrangian using gradient steps will lead to message-passing steps on the constraint graph for constraint satisfaction problems. In equation 3 we show a simple way to parameterize this message passing by adding learnable matrices.

For the question:

In Table 2, what's the usual setting for the clause? Since the ratio is relatively high. What's the relationship between the total computational complexity and this ratio?

The ratio is the clauses-to-variables ratio. This means that the higher the ratio the more constrained the instance will be, which will typically make it harder or potentially impossible to solve. More specifically, it is known that there is a phase transition point at a ratio of 4.26. Formulae with higher ratios than that become increasingly more likely to be unsatisfiable. Formulae with ratios at this phase transition point are typically considered to be hard.

Limitations: Based on my review, this part is not well addressed by the authors. But since myself is not an expert in optimization approximation algorithms, please the authors/ACs kindly refer to the weaknesses and questions raised by pother reviewers.

The main limitation of this work has to do with its applicability to different combinatorial optimization problems. The theoretical connection to optimal approximability results only holds for Max-CSPs. Of course, our method can be applied to essentially any SDP/polynomial optimization problem in practice. The main practical challenge in that case is enforcing the feasibility of the solutions. For example, consider the Travelling Salesperson Problem (TSP). In that case, our model requires a way of enforcing that the solutions produced by the model are valid tours. That would have to be solved with a post-processing step. Covering such cases is no trivial task and would require additional arguments and empirical work to be done in a clean and mathematically coherent way. We believe this is certainly a promising avenue for future work.

Again, we thank the reviewer for the comments and we will make sure to include an extensive discussion of the limitations in the final version of the paper. We would also like to encourage the reviewer to have a look at our responses to the other reviewers as well, in case that helps further clarify some of their concerns. We hope our response addresses the concerns of the reviewer! If the reviewer finds our answers satisfactory, we would be grateful if they could further increase their score.

Regarding the question:

In Table 2, what's the usual setting for the clause? Since the ratio is relatively high. What's the relationship between the total computational complexity and this ratio?

We wanted to mention that higher ratios means larger constraint graphs (because the number of clauses increases) which implies also larger memory costs. As we said in our response to reviewer WeYu, for a graph with vertices $|V|$ and edges $|E|$ , for embedding dimension $d$, and depth $L$, the total runtime of OptGNN is $O(Ld^\omega |V| + Ld|E|)$, where $\omega$ is the matrix multiplication constant.

We thank the reviewer for the positive feedback and for appreciating both the empirical and theoretical elements of the paper's contributions.

We would like to thank the reviewer for the detailed feedback. We appreciate their positive comments on the soundness and the structure of the paper!

To address the weaknesses:

The paper lacks a comprehensive analysis of how well OptGNN scales with increasing graph sizes and complexity.

The cost of OptGNN scales linearly with the size of the graph (number of nodes/edges) as it is a message passing GNN. Empirically, we show that OptGNN runs on graphs of several thousands of nodes (GSET and 3-SAT experiments) without scalability issues.

Although the out-of-distribution generalization of OptGNN has been tested, an analysis of its generalization over problem size is missing.

Our Max-Cut GSET results act also as both size and OOD generalization tests since the training was done on ER graphs of 500 nodes with a fixed edge density, and the testing was done on the GSET instances which can have tens of thousands of nodes and are not from the same ER distribution. The model performs competitively on up to an order of magnitude larger graphs than the ones it was trained on.

Could you clarify how the proposed approach scales with increasingly large problem instances, particularly regarding computational complexity and performance stability?

Please see answers above and our response to reviewer WeYu.

What are the generalization capabilities over problem scale of the proposed approach?

It is not quite clear what is meant by this question. Is this is about generalization to other problems, e.g., training on Max-Cut and testing on Vertex Cover? If that is what is meant by the reviewer, OptGNN in that case will typically not be able to transfer its performance to different problems without further training. It is certainly an interesting question to explore whether pre-training on certain problems and fine-tuning on others can impact performance in a positive way.

What are the limitations of OptGNN? please explain in the text.

Thank you for pointing this out! We will make sure to discuss limitations and scaling in more detail in the paper. Briefly, the main two limitations are that the applicability of our theoretical result only covers CSPs and not all CO problems. Empirically, there is also the issue of "rounding" a convex relaxation to a integral solution, which is typically undertaken by a branch and bound tree search (i.e for producing a valid tour in the TSP). Tackling this issue is an important avenue for future work and would require non-trivial additions to our framework. Please also see our response to reviewer Ubhy for the same question.

Again, we thank the reviewer for their comments. If this answer has addressed your concerns please consider raising your score. In any case, we will gladly respond to any further questions!

We thank the reviewer for all their detailed comments and review of our work! To address the concerns in order.

1. For a graph $G$ with vertices $V$ and edges $E$, for embedding dimension $d$, and depth $L$, the total runtime of OptGNN is $O(L d^\omega |V| + Ld|E|)$ where $\omega$ is the matrix multiplication constant $2.37$. That is, the computational cost scales linearly in the size of the graph just as it does with message passing neural networks. In practice, the max cut GSET instances serve as a scalability test.
   The GSET dataset is comprised of graphs with up to tens of thousands of nodes, whereas the OptGNN training set was comprised of graphs with up to 500 nodes. We observe the model maintains strong performance for instances that are up to 3000 nodes and subsequently tapers off when the number of nodes substantially exceeds 3000.
2. The OptGNN construction can be performed for any polynomial optimization subject to polynomial constraints (polynomial system solving). Any polynomial system, of which MaxCSP is a prominent example, admits a vector form SDP relaxation corresponding to the degree-2 Lasserre hierarchy relaxation. A prominent example of a problem that does not have a well known formulation as a polynomial optimization is the traveling salesman problem.
3. Promising avenues of research include constructing tighter bounds on optimality for the outputs of neural architectures/OptGNN. Tighter bounds directly translate to superior performance for branch and bound tree searches that require a certificate of optimality for termination. This would be a promising avenue for empirical investigation.
4. Weaknesses: Indeed, further empirical work is required to achieve state of the art across a wide variety of benchmarks. With respect to the UGC, although its truth is yet undetermined, another way to think about it is from the perspective of algorithms. OptGNN captures the algorithms with the best approximation ratios for Max CSP that are known in the literature.

We once again thank the reviewer for their questions and time in reviewing our work, and hope our response addresses their concerns!

I have read the authors response and I would like to keep my score.