Are Graph Neural Networks Optimal Approximation Algorithms?

Summary

This paper draws analogy between the optimization of, e.g., Max-Cut and Max-SAT problems, and the message-passing algorithm, and accordingly constructs OptGNN to implement the message-passing algorithms towards the problems. The generated optimal solutions are shown with provable bounds. Finally, empirical studies show the effectiveness and efficiency of the proposed OptGNN.

Strengths

1. The logic of the paper in writing/presentation are absolutely easy to read and understand, and the project in design are reasonable. 2. The proposal is presented with theoretical guarantees, i.e. the bounds of the optimal solutions are shown. 3. The proposed framework OptGNN is easy to implement and the empirical studies are consistent and demonstrate the effectiveness of the proposal. 4. The discussion of related work is extensive and satisfactory.

Weaknesses

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

Questions

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

Rating

7

Confidence

2

Soundness

3

Presentation

4

Contribution

3

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.

Summary

The papers propose graph neural architectures that can be used to capture optimal approximation algorithms for a large class of combinatorial optimization problems.

Strengths

- The paper for the most part is well written with clear motivation. - The contributions made in the paper are manifold across various optimization problems like Max-cut, Min-vertex cover etc. and have shown commendable performance. - The paper also showcases a good theoretical basis.

Weaknesses

No significant weakness as such. Fig1. and Fig. 2 the visibility could be improved.

Questions

NA.

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

Yes, the authors has provided limitations section.

Summary

The paper establishes that polynomial-sized message-passing GNNs, can learn and replicate the optimal approximation capabilities of traditional algorithms based on SDP relaxations for Max-CSP under the assumption of the UGC. The authors propose OptGNN, which effectively integrates the theoretical framework of SDP to produce high-quality solutions for combinatorial problems such as Max-Cut, Min-Vertex-Cover, and Max-3-SAT.

Strengths

The paper explores integrating semidefinite programming into GNNs under the Unique Games Conjecture to optimally approximate combinatorial optimization problems. It introduces the OptGNN, a model designed to utilize polynomial-time message-passing algorithms and low-rank SDP relaxations to effectively solve problems such as Max-Cut and Max-3-SAT. The paper establishes OptGNN's potential through PAC learning arguments and empirical validation against traditional solvers and neural baselines. The paper is well-structured and mathematically sound.

Weaknesses

- The paper lacks a comprehensive analysis of how well OptGNN scales with increasing graph sizes and complexity. - Although the out-of-distribution generalization of OptGNN has been tested, an analysis of its generalization over problem size is missing.

Questions

1. Could you clarify how the proposed approach scales with increasingly large problem instances, particularly regarding computational complexity and performance stability? 2. What are the generalization capabilities over problem scale of the proposed approach? 3. What are the limitations of OptGNN? please explain in the text.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Authors need to discuss the limitation of their work.

Summary

This work presents a significant advancement in the field of combinatorial optimization by developing a graph neural network (GNN) architecture named OptGNN. The authors demonstrate that OptGNN can capture optimal approximation algorithms for a broad class of combinatorial optimization problems, leveraging the power of semidefinite programming (SDP) and the Unique Games Conjecture (UGC). They prove that polynomial-sized message-passing GNNs can learn the most powerful polynomial-time algorithms for Max Constraint Satisfaction Problems, resulting in high-quality approximate solutions for challenges such as Max-Cut, Min-Vertex-Cover, and Max-3-SAT. Additionally, OptGNN provides a method for generating provable bounds on the optimal solution from the learned embeddings. The empirical results show that OptGNN outperforms classical heuristics, solvers, and state-of-the-art neural baselines across various datasets, making it a robust tool for efficient and optimal combinatorial optimization.

Strengths

1. The paper is theoretically solid. It builds on well-established concepts in approximation algorithms and semidefinite programming, providing a strong theoretical basis for its claims. 2. The development of OptGNN, a graph neural network that can capture optimal message-passing algorithms for combinatorial optimization problems, seems to be a significant innovation. This architecture leverages message-passing updates use SDP relaxations to prove its high-quality approximate solutions. 3. The paper includes a variety of evaluations, such as out-of-distribution tests and ablation studies, which help validate the practical utility and robustness of OptGNN.

Weaknesses

1. Although OptGNN shows strong performance on several benchmarks, it does not outperform all state-of-the-art methods. This indicates room for improvement in the model’s optimization and training processes. 2. The theoretical guarantees provided by OptGNN rely on the truth of the UGC, which, while widely believed, remains unproven. This dependence could limit the certainty of the results. That being said, I consider this more like a limitation than weakness. 3. The writing needs to be improved, there are multiple typos and inconsist notations.

Questions

1. Can you elaborate on the scalability of OptGNN for very large graphs or more complex real-world problems? What are the practical limitations in terms of computational resources and time? 2. How adaptable is OptGNN to new combinatorial optimization problems that were not directly addressed in the paper? What modifications would be necessary to extend its applicability? 3. Can you also point out some future directions for this research? Both application and theoretical wise are good.

Rating

8

Confidence

4

Soundness

4

Presentation

3

Contribution

4

Limitations

Yes.

Appreciate the authors' responses

I believe my questions are well addressed by the response, and I am happy to increase my score to 7 accordingly.