Are Graph Neural Networks Optimal Approximation Algorithms?
In this work we design graph neural network architectures that capture
optimal approximation algorithms for a large class of combinatorial
optimization problems, using powerful algorithmic tools from semidefinite
programming (SDP). Concretely, we prove that polynomial-sized message-passing
algorithms can represent the most powerful polynomial time algorithms for Max
Constraint Satisfaction Problems assuming the Unique Games Conjecture. We
leverage this result to construct efficient graph neural network architectures,
OptGNN, that obtain high-quality approximate solutions on landmark
combinatorial optimization problems such as Max-Cut, Min-Vertex-Cover, and
Max-3-SAT. Our approach achieves strong empirical results across a wide range
of real-world and synthetic datasets against solvers and neural baselines.
Finally, we take advantage of OptGNN's ability to capture convex relaxations to
design an algorithm for producing bounds on the optimal solution from the
learned embeddings of OptGNN.
Morris Yau, Nikolaos Karalias, Eric Lu, Jessica Xu, Stefanie Jegelka
# Are Graph Neural Networks Optimal Approximation Algorithms?

###### Abstract

In this work we design graph neural network architectures that capture optimal approximation algorithms for a large class of combinatorial optimization problems using powerful algorithmic tools from semidefinite programming (SDP). Concretely, we prove that polynomial-sized message passing algorithms can represent the most powerful polynomial time algorithms for Max Constraint Satisfaction Problems assuming the Unique Games Conjecture. We leverage this result to construct efficient graph neural network architectures, OptGNN, that obtain high-quality approximate solutions on landmark combinatorial optimization problems such as Max Cut and maximum independent set. Our approach achieves strong empirical results across a wide range of real-world and synthetic datasets against classical algorithms. Finally, we take advantage of OptGNN's ability to capture convex relaxations to design an algorithm for producing dual certificates of optimality (bounds on the optimal solution) from the learned embeddings of OptGNN.

## 1 Introduction

Combinatorial Optimization is the class of problems that optimize functions subject to constraints over discrete search spaces. They are often NP-hard to solve and to approximate, owing to their typically exponential search spaces over nonconvex domains. Nevertheless, their important applications in science and engineering (Gardiner et al., 2000; Zaki et al., 1997; Smith et al., 2004; Du et al., 2017) has engendered a long history of study rooted in the following simple insight. In practice, CO instances are endowed with domain-specific structure that can be exploited by specialized algorithms (Hespe et al., 2020; Walteros and Buchanan, 2019; Ganesh and Vardi, 2020). In this context, neural networks are natural candidates for learning and then exploiting patterns in the data distribution over CO instances.

The emerging field at the intersection of machine learning (ML) and combinatorial optimization (CO) has led to novel algorithms with promising empirical results for several CO problems. However, similar to classical approaches to CO, ML pipelines have to manage a tradeoff between efficiency and optimality. Indeed, prominent works in this line of research forego optimality and focus on parametrizing heuristics (Li et al., 2018; Khalil et al., 2017; Yolcu and Poczos, 2019; Chen and Tian, 2019) or by employing specialized models (Zhang et al., 2023; Nazari et al., 2018; Toenshoff et al., 2019; Xu et al., 2021; Min et al., 2022) and task-specific loss functions (Amizadeh et al., 2018; Karalias and Loukas, 2020; Wang et al., 2022; Karalias et al., 2022; Sun et al., 2022). Exact ML solvers that can guarantee optimality often leverage general techniques like branch and bound (Gasse et al., 2019; Paulus et al., 2022) and constraint programming (Parajdis et al., 2021; Cappart et al., 2019), which offer the additional benefit of providing approximate solutions together with a bound on the distance to the optimal solution. The downside of those methods is their exponential worst-case time complexity. This makes it clear that striking a balance between efficiency and optimality is challenging, which leads us to the central question of this paper:
_Are there neural architectures for **general** combinatorial optimization that can learn to adapt to a data distribution over instances yet capture algorithms with **optimal** worst-case approximation guarantees?_

To answer this question, we build on the extensive literature on approximation algorithms and semidefinite programming. Convex relaxations of CO problems via semidefinite programming are the fundamental building block for breakthrough results in the design of efficient algorithms for NP-Hard combinatorial problems, such as the Goemans-Williamson approximation algorithm for Max Cut (Goemans & Williamson, 1995) and the use of the Lovasz theta function to find the maximum independent set on perfect graphs (Lovasz, 1979; Grotschel et al., 1981). In fact, it is known that if the Unique Games Conjecture (UGC) is true, then the approximation guarantees obtained through semidefinite programming relaxations are indeed the best that can be achieved (Raghavendra, 2008; Barak & Steurer, 2014). We will leverage these results to provide an affirmative answer to our question. Our contributions can be organized into theory and experiments.

First, on the theory side we show that a polynomial time message passing algorithm approximates the solution of an SDP with the optimal integrality gap for the class of Maximum Constraint Satisfaction Problems, assuming the UGC. The key theoretical insight is that a message-passing algorithm can be used to compute gradient updates for the augmented Lagrangian of an overparameterized reformulation of the SDP in (Raghavendra, 2008). This in turn leads to our main contribution, OptGNN, a graph neural network architecture that generalizes our message-passing algorithm and therefore captures its approximation guarantee.

Our second contribution is empirical. We show that our theoretical construction can be used directly within graph neural network pipelines for CO that are easy to implement and train. By training with the SDP objective as a loss function, OptGNN learns embeddings that can be regarded as feasible fractional solutions of an overparameterized low rank SDP, which are subsequently rounded to feasible integral solutions. On the primal side, we show OptGNN achieves strong empirical results against classical algorithms across a broad battery of datasets for landmark CO problems such as Max Cut and Vertex Cover.

Finally, to underscore the fact that OptGNN captures powerful convex relaxations, we construct dual certificates of optimality, i.e bounds that are provably correct, from OptGNN embeddings for the Max Cut problem that are virtually tight for small synthetic instances. See our discussion on general neural certification schemes for extracting dual certificates from OptGNN networks in Appendix B.2.

To summarize, the contribution of this paper is twofold:

* We construct a polynomial time message passing algorithm for solving the SDP of Raghavendra (2008) for the broad class of maximum constraint satisfaction problems (including Max Cut, max-SAT, etc.), that is optimal barring the possibility of significant breakthroughs in the foundations of algorithms.
* We construct graph neural architectures to capture this message passing algorithm and show that they achieve strong results against solvers and greedy algorithms.

## 2 Related Work

Optimal approximation algorithms.In theoretical computer science, it is typically quite difficult to prove that an algorithm achieves the best approximation guarantee for a given problem, as it is hard to rule out the existence of a more powerful algorithm. The Unique Games Conjecture (Khot, 2002) is a striking development in the theory of approximation algorithms because it is able to circumvent precisely this obstacle. If true, it implies several approximation hardness results which often match the approximation guarantees of the best-known algorithms (Raghavendra & Steurer, 2009b; Raghavendra et al., 2012). In fact, it implies something even stronger: there is a _general_ algorithm based on semi-definite programming that achieves the best possible approximation guarantees for several important problems (Raghavendra, 2008). Our theoretical contribution builds on these ideas to construct a neural architecture that is a candidate optimal approximation algorithm. For a complete exposition on the topic of UGC and approximation algorithms we refer the reader to Barak & Steurer (2014).
Semidefinite programming in machine learning.Semidefinite programming has already found applications in machine learning pipelines. In a similar spirit to our work, Wang et al. (2019) propose a differentiable SDP-based SAT solver based on previous works on low-rank SDPs (Wang and Kolter, 2019), while Krivachy et al. (2021) use neural networks to solve primal-dual SDP pairs for quantum information tasks. The key difference in our case is that our neural network architecture naturally aligns with solving a low-rank SDP and while our GNNs capture the properties of the SDP, in practice they can also improve upon it.

Other applications of semidefinite programming in machine learning include global minimization of functions by obtaining kernel approximations through an SDP (Rudi et al., 2020), deriving differentiable high-dimensional extensions of discrete functions (Karalias et al., 2022), and leveraging the connection between SVMs and the Lovasz theta function to efficiently find the largest common dense subgraph among a collection of graphs (Jethava et al., 2013).

Neural combinatorial optimization.Beyond semidefinite programming, prior work in the literature has examined the capabilities of neural networks to obtain solutions to combinatorial problems, including the ability of modern GNNs to achieve approximation guarantees for combinatorial problems Sato et al. (2019) and impossibility results for computing combinatorial properties of graphs (Loukas, 2019). It was previously shown that for maxSAT, a neural network can straightforwardly obtain a 1/2-approximation (Liu et al., 2021) which is also easily obtainable through a simple randomized algorithm Johnson (1973). SDPs can yield at least 3/4-approximations for max-SAT (Goemans and Williamson, 1995), so our approach improves significantly over previous results. Finally, a different divide and conquer approach was proposed by McCarty et al. (2021), which uses Baker's paradigm to solve maximum independent set on geometric intersection graphs by partitioning the problem into at most a linear number (on the size of the input) of subproblems of bounded size,

Figure 1: Schematic representation of OptGNN. During training, OptGNN produces node embeddings \(\mathbf{v}\) by calculating gradient updates in its forward pass using message passing on the input graph \(G\). These embeddings then used to compute the augmented Lagrangian loss \(\mathcal{L}_{p}(\mathbf{v};G)\). OptGNN is trained by minimizing the average loss over the training set. At inference time, the fractional solutions (embeddings) \(\mathbf{v}\) for an input graph \(G\) produced by OptGNN are rounded using randomized rounding and a greedy heuristic.
which allows them to use a neural network on each subproblem to obtain an approximation guarantee.

In order to obtain exact solvers that are guaranteed to find the optimal solution, a prominent direction in the field involves combining solvers with neural networks either to provide a "warm start" (Benidis et al., 2023), or to learn branching heuristics for branch and bound (Gasse et al., 2019; Nair et al., 2020; Gupta et al., 2020; Paulus et al., 2022) and CDCL SAT solvers (Selsam and Bjorner, 2019; Kurin et al., 2020; Wang et al., 2021). Owing to their integration with powerful solvers, those ML pipelines are able to combine some of the strongest elements of classical algorithms and neural networks to obtain compelling results. Other related work in this vein includes constructing differentiable solvers and optimization layers (Wang et al., 2019; Agrawal et al., 2019), and the paradigm of neural algorithmic reasoning (Velickovic and Blundell, 2021) which focuses on training neural networks to emulate classical polynomial-time algorithms and using them to solve various combinatorial problems (Ibarz et al., 2022; Georgiev et al., 2023). Other prominent neural approaches that have achieved strong empirical results with fast execution times follow different learning paradigms including reinforcement learning (Ahn et al., 2020; Bother et al., 2022; Tonshoff et al., 2022; Barrett et al., 2022) and unsupervised learning (Min et al., 2022; Ozolins et al., 2022).

The list of works mentioned here is by no means exhaustive, for a complete overview of the field we refer the reader to the relevant survey papers Cappart et al. (2023); Bengio et al. (2021).

## 3 Optimal approximation algorithms with neural networks

This section is structured as follows. In order to build intuition, we begin the section with the example of finding the maximum cut on a graph. We show that solving the Max Cut problem using a vector (low-rank SDP) relaxation and a simple projected gradient descent scheme amounts to executing a message-passing algorithm on the graph. This sets the stage for our main result for the class of constraint satisfaction problems (CSP) which generalizes this observation. We describe a semidefinite program (SDP 1) for maximum constraint satisfaction problems that achieves the optimal integrality gap assuming the UGC. Our theorem B.1 shows that similarly to the Max Cut example, SDP 1 can be solved with message-passing (Algorithm 1). This leads us to define an overparametrized version of Algorithm 1, dubbed OptGNN. We then show that by solving SDP 1, OptGNN can achieve optimal approximation guarantees for maximum constraint satisfaction problems.

### Solving combinatorial optimization problems with message passing

To build intuition, we begin with the canonical example for the usage of semidefinite programming in combinatorial optimization: the Maximum Cut (henceforth Max Cut) problem. Given a graph \(G=(V,E)\) with vertices \(V\), \(|V|=N\) and edge set \(E\), in the Max Cut problem we are looking to find a set of nodes in \(G\) that maximize the number of edges with exactly one endpoint in that set. Formally, this means solving the following nonconvex quadratic integer program.

\[\max_{(x_{1},x_{2},\ldots,x_{N})} \sum_{(i,j)\in E}\tfrac{1}{2}(1-x_{i}x_{j})\] (1) subject to: \[x_{i}^{2}=1 \forall i\in[N].\]

The global optimum of the integer program is the Max Cut. Unfortunately the discrete variables are not amenable to the tools of continuous optimization. A standard technique is to 'lift' the problem and solve it with a rank constrained SDP. Here we introduce a matrix \(X\in\mathbb{R}^{N\times N}\) of variables, where we index the \(i\)'th row and \(j\)'th column entry as \(X_{ij}\).

\[\max_{X} \sum_{(i,j)\in E}\tfrac{1}{2}(1-X_{ij})\] subject to: \[X_{ii}=1 \forall i\in[N]\] \[X\succeq 0\] \[\text{rank}(X)=r\]
The intuition is that a rank \(r=1\) solution to Algorithm 2 is equivalent to solving the integer program. A common approach is to replace the integer variables \(x_{i}\) with vectors \(v_{i}\in\mathbb{R}^{r}\) and constrain \(v_{i}\) to lie on the unit sphere.

\[\min_{v_{1},v_{2},\ldots,v_{N}} -\sum_{(i,j)\in E}\tfrac{1}{2}(1-\langle v_{i},v_{j}\rangle)\] (3) subject to: \[\|v_{i}\|=1 \forall i\in[N]\] \[v_{i}\in\mathbb{R}^{r}\]

For \(r=\Omega(\sqrt{N})\) the global optimum of this optimization is equivalent to the standard SDP optimum with no rank constraint (Barvinok, 1995; Pataki, 1998). Burer & Monteiro (2003) proposed a fast iterative algorithm for descending this loss. The landscape of this nonconvex optimization is benign in that all local minima are approximately global minima Ge et al. (2016) and variations on stochastic gradient descent converge to its optimum Bhojanapalli et al. (2018)Jin et al. (2017) under a variety of smoothness and compactness assumptions. Thus, for large \(r\), simple algorithms such as block coordinate descent Erdogdu et al. (2019) can find an approximate global optimum of the objective. For this extensive literature on low rank matrix factorization see Chi et al. (2018). However, for large \(r\), it is unclear how to transform, i.e., round, the vectors \(\mathbf{v}\) into a solution to the integral problem. Thus we need an approach that generalizes projected gradient descent that performs well for small \(r\). In iteration \(t\) (and for \(T\) iterations), projected gradient descent updates vector \(v_{i}\) in \(\mathbf{v}\) as

\[\hat{v_{i}}^{t+1}=v_{i}^{t}-\eta\sum\nolimits_{j\in N(i)}v_{j}^{t} \tag{4}\]

\[v_{i}^{t+1}=\frac{\hat{v_{i}}^{t+1}}{\|\hat{v_{i}}^{t+1}\|}, \tag{5}\]

where \(\eta\in\mathbb{R}^{+}\) is an adjustable step size and we let \(N(i)\) denote the neighborhood of node \(i\). The gradient updates to the vectors are local, i.e., each vector is updated by aggregating information from its neighboring vectors, so we can interpret the projected gradient descent steps as message-passing iterations.

Overparametrized message passing.Intuitively, our main contribution in this paper builds on the following observation. We may generalize the dynamics described above by considering an overparametrized version of the gradient descent updates in equations 4 and 5. Let \(\{M_{1,t}\}_{t\in[T]}\in\mathbb{R}^{r\times r}\) and \(\{M_{2,t}\}_{t\in[T]}\in\mathbb{R}^{r\times r}\) each be sets of \(T\) learnable matrices corresponding to \(T\) layers of a neural network. Then for layer \(t\) in max iterations \(T\), for embedding \(v_{i}\) in \(\mathbf{v}\), we have

\[\hat{v_{i}}^{t+1} :=M_{1,t}v_{i}^{t}-M_{2,t}\sum\nolimits_{j\in N(i)}v_{j}^{t}+b_ {t} \tag{6}\] \[v_{i}^{t+1} :=\frac{\hat{v_{i}}^{t+1}}{\|\hat{v_{i}}^{t+1}\|}, \tag{7}\]

where \(\{b_{t}\}_{t\in[T]}\) is a learnable affine shift. More generally, we can write the dynamics as

\[\hat{v_{i}}^{t+1} :=\text{UPDATE}(M_{1,t},v_{i}^{t},b_{t},\text{AGGREGATE}(M_{2,t},\{v_{j}^{t}\}_{j\in N(i)})) \tag{8}\] \[v_{i}^{t+1} :=\text{NONLINEAR}(\hat{v_{i}}^{t+1}), \tag{9}\]

for efficiently computable functions \(\text{UPDATE}:\mathbb{R}^{r\times r}\times\mathbb{R}^{r}\times\mathbb{R}^{r} \times\mathbb{R}^{r}\rightarrow\mathbb{R}^{r}\) and \(\text{AGGREGATE}:\mathbb{R}^{r\times r}\times\mathbb{R}^{r|N(i)|}\rightarrow \mathbb{R}^{r}\) and \(\text{NONLINEAR}:\mathbb{R}^{r}\rightarrow\mathbb{R}^{r}\). It is straightforward to see that these update dynamics can be represented by a Graph Neural Network (GNN), which we call OptGNN. It will become clear that the dynamics in 4, 5 can be generalized to a large class of CO problems. Examples include vertex cover, maximum clique, and maximum constraint satisfaction problems (see additional derivations for maximum clique and vertex cover in A).

In the rest of this section, we will show that the OptGNN formulation can be used for all maximum constraint satisfaction problems (max-CSPs). Max-CSPs include Max Cut, max-SAT, etc. Moreover, we will show that OptGNN can implement a message-passing (see B.1 for definition) algorithm for max-CSPs that can be shown to achieve optimal approximation guarantees, assuming the Unique Games Conjecture.
### Message passing for max-CSPs

Given a set of constraints over variables, Max-CSP asks to find a variable assignment that maximizes the number of satisfied constraints. Formally, a Constraint Satisfaction Problem \(\Lambda=(\mathcal{V},\mathcal{P},q)\) consists of a set of \(N\) variables \(\mathcal{V}:=\{x_{i}\}_{i\in[N]}\) each taking values in an alphabet \([q]\) and a set of predicates \(\mathcal{P}:=\{P_{z}\}_{z\subset\mathcal{V}}\) where each predicate is a payoff function over \(k\) variables denoted \(X_{z}=\{x_{i_{1}},x_{i_{2}},...,x_{i_{k}}\}\). Here we refer to \(k\) as the arity of the Max-k-CSP. We adopt the normalization that each predicate \(P_{z}\) returns outputs in \([0,1]\). We index each predicate \(P_{z}\) by its domain \(z\). The goal of Max-k-CSP is to maximize the payoff of the predicates.

\[OPT:=\max_{(x_{1},...,x_{N})\in[q]^{N}}\frac{1}{|\mathcal{P}|}\sum_{P_{z}\in \mathcal{P}}P_{z}(X_{z}), \tag{10}\]

where we normalize by the number of constraints so that the total payoff is in \([0,1]\). Therefore we can unambiguously define an \(\epsilon\)-approximate assignment as an assignment achieving a payoff of \(OPT-\epsilon\). Since our result depends on a message passing algorithm, we will need to define an appropriate graph structure over which messages will be propagated. To that end, we will leverage the constraint graph of the CSP instance. We define the constraint graph associated with a Max-CSP instance \(\Lambda\) as follows. Given a Max-k-CSP instance \(\Lambda=(\mathcal{V},\mathcal{P},q)\) a constraint graph \(G_{\Lambda}=(V,E)\) is comprised of vertices \(V=\{v_{\phi,\zeta}\}\) for every subset of variables \(\phi\subseteq z\) for every predicate \(P_{z}\in\mathcal{P}\) and every assignment \(\zeta\in[q]^{k}\) to the variables in \(z\). The edges \(E\) are between any pair of vectors \(v_{\phi,\zeta}\) and \(v_{\phi^{\prime},\zeta^{\prime}}\) such that the variables in \(\phi\) and \(\phi^{\prime}\) appear in a predicate together.

Optimal message passing for max-CSP.In order to construct OptGNN for this problem, we first establish that message passing can be optimal for max-CSPs. To show this, consider the SDP of Raghavendra (2008) which is known to possess the optimal integrality gap assuming the UGC. This Unique-Games-optimal program can be equivalently reformulated as described in SDP 1. Then, for Max-k-CSP we define its approximation ratio to be

\[\text{Approximation Ratio}:=\min_{\Lambda\in\text{Max-k-CSP}}\frac{OPT( \Lambda)}{SDP(\Lambda)},\]

where the minimization is being taken over all instances \(\Lambda\) with arity \(k\). The approximation ratio is always smaller than one. Similarly the integrality gap is defined to be the inverse of the approximation ratio and is always greater than one. There is no polynomial time algorithm that can achieve a superior (larger) approximation ratio assuming the truth of the conjecture. Furthermore, there is a polynomial time rounding algorithm (Raghavendra & Steurer, 2009a) that achieves the integrality gap of the SDP of (Raghavendra, 2008), and therefore outputs an integral solution with the optimal approximation ratio. Our main theoretical result is a polynomial time message passing algorithm (detailed in Algorithm 1) that solves the Unique Games optimal SDP.

**Theorem 3.1**.: _(Informal) Given a Max-k-CSP instance \(\Lambda\), there exists a message passing Algorithm 1 on constraint graph \(G_{\Lambda}\) with a per iteration update time of \(poly(|\mathcal{P}|,q^{k})\) that computes in \(poly(\epsilon^{-1},|\mathcal{P}|,q^{k},\log(\delta^{-1}))\) iterations an \(\epsilon\)-approximate solution to SDP 1 with probability \(1-\delta\). That is to say, Algorithm 1 computes a set of vectors \(\mathbf{v}\) satisfying constraints of SDP 1 to error \(\epsilon\) with objective value denoted \(OBJ(\mathbf{v})\) satisfying \(|OBJ(\mathbf{v})-SDP(\Lambda)|\leq\epsilon\)._

For the formal theorem and proof see Theorem B.1. Our algorithm is remarkably simple: perform gradient descent on the quadratically penalized objective of SDP 1. We observe that the gradient takes the form of a message-passing algorithm. For each predicate, we associate \(q^{k}\) vectors, one vector for each assignment to each subset of \(k\) variables, for a total of \(|\mathcal{P}|q^{k}\) vectors. The updates on each vector only depend on the vectors appearing in the same predicates. Therefore, if each variable \(x_{i}\) appears in no more than \(C\) predicates, every message update in the algorithm depends no more than \(Cq^{k}\) vectors rather than the total set of \(|\mathcal{P}|q^{k}\) vectors. For Max Cut for example this would mean each vector corresponds to a node that is updated as a function of the vectors in adjacent vertices, as described earlier in equations 4 and 5. For more complicated CSPs this gradient iteration can be defined analogously by taking gradients of a penalized objective of the reformulated SDP 1 which is equivalent to the optimal SDP of Raghavendra (2008).

### OptGNN for maximum constraint satisfaction problems

By inspection of the gradient iteration of Algorithm 1 we see that for a Max-k-CSP instance \(\Lambda\), Algorithm 1 is a message-passing algorithm (for a precise definition see B.1) on the associated
constraint graph \(G_{\Lambda}\). This message-passing form allows us to define OptGNN, a natural GNN generalization that captures this gradient iteration.

Definition (OptGNN).: Given a Max-k-CSP instance \(\Lambda\), an OptGNN\({}_{(T,r,G_{\Lambda})}(\mathbf{v})\) is a \(T\) layer, dimension \(r\), neural network over constraint graph \(G_{\Lambda}\) with learnable matrices \(\{M_{1,t}\}_{t\in[T]}\), \(\{M_{2,t}\}_{t\in[T]}\) and stochastic affine shift \(\{b_{t}\}_{t\in[T]}\) that generalizes the gradient iteration equation 32 of Algorithm 1 with an embedding \(v\in\mathbf{v}\) for every node in \(G_{\Lambda}\) with updates of the form

\[v_{w}^{t+1}=\text{UPDATE}(M_{1,t},v_{w}^{t},\text{AGGREGATE}(M_{2,t},\{v_{j} ^{t}\}_{j\in N(w)},v_{w}^{t}))\]

\[v_{w}^{t+1}=\text{NONLINEAR}(v_{w}^{t+1})+b_{t}\]

For arbitrary polynomial time computable functions \(\text{UPDATE}:\mathbb{R}^{r\times r}\times\mathbb{R}^{r}\times\mathbb{R}^{r} \rightarrow\mathbb{R}^{r}\), \(\text{AGGREGATE}:\mathbb{R}^{r\times r}\times\mathbb{R}^{r\prime}\times \mathbb{R}^{r\prime}\rightarrow\mathbb{R}^{r}\), and \(\text{NONLINEAR}:\mathbb{R}^{r}\rightarrow\mathbb{R}^{r}\). Here by 'generalize' we mean there exists an instantiation of the learnable parameters \(\{M_{1,t}\}_{t\in[T]}\) and \(\{M_{2,t}\}_{t\in[T]}\) such that OptGNN is equivalent to equation 32.

Naturally, we may conclude that an appropriately parameterized OptGNN solves SDP 1. To make this connection formal, we must ensure that a small amount of additive stochastic noise \(\{b_{t}\}_{t\in[T]}\) is added at each layer for the sake of theoretical gradient convergence. We then arrive at the following corollary.

Corollary 1.: Given a Max-k-CSP instance \(\Lambda\), there is an OptGNN\({}_{(T,r,G_{\Lambda})}(\mathbf{v})\) with \(T=poly(\delta^{-1},\epsilon^{-1},|\mathcal{P}|q^{k})\) layers, \(r=|\mathcal{P}|q^{k}\) dimensional embeddings, such that there is an instantiation of learnable parameters \(\{M_{1,t}\}_{t\in[T]}\) and \(\{M_{2,t}\}_{t\in[T]}\) and a random shift \(\{b_{t}\}_{t\in[T]}\) that outputs a set of vectors \(\mathbf{v}\) satisfying the constraints of SDP 1 and approximating its objective, \(OBJ_{\text{SDP}}(\Lambda)\), to error \(\epsilon\) with probability \(1-\delta\) over the randomness in \(\{b_{t}\}_{t\in[T]}\).

It is also straightforward to conclude that the rounding of Raghavendra & Steurer (2009a) achieves the integrality gap of SDP 1, and any OptGNN that approximates its solution. For the sake of completeness, we discuss the implications of the rounding. Let the integrality gap curve \(S_{\Lambda}(c)\) be defined as

\[S_{\Lambda}(c):=\inf_{\begin{subarray}{c}\Lambda\in\text{Max-k-CSP}\\ OBJ_{\text{sync}}(\Lambda)=c\end{subarray}}OPT(\Lambda),\]

which leads to the following statement about rounding.

Corollary 2.: The OptGNN of Corollary 3, which by construction is equivalent to Algorithm 1, outputs a set of embeddings \(\mathbf{v}\) such that the rounding of Raghavendra & Steurer (2009a) outputs an integral assignment \(\mathcal{V}\) with a Max-k-CSP objective OBJ(\(\mathcal{V}\)) satisfying \(OBJ(\mathcal{V})\geq S_{\Lambda}(OBJ_{\text{SDP}}(\Lambda)-\epsilon)-\epsilon\) in time \(\exp(\exp(\text{poly}(\frac{kg}{\epsilon})))\) which approximately dominates the Unique Games optimal approximation ratio.

We defer the proofs of the corollaries to subsection B.3

Obtaining neural certificates.The goal of OptGNN is to find high quality solutions to CO problems by capturing powerful classes of convex relaxations. To underscore this point, we construct dual certificates of optimality (a proof) from the embeddings of OptGNN. The key idea is to "guess" the dual variables of SDP 1 from the output embeddings/SDP solution \(\mathbf{v}\). Since we use a quadratic penalty for constraints, the natural dual guess is one step of the augmented method of lagrange multipliers on the SDP solution which can be obtained straightforwardly from the overparameterized primal variables \(\mathbf{v}\). Of course, this "guess" need not be dual feasible. To handle this problem we analytically bound the error in satisfying the KKT conditions of SDP 1. See B.2 for derivations and extended discussion, and 4.2 for an experimental demonstration.

### OptGNN in practice

OptGNN is a neural network architecture that uses message passing to solve a low-rank semidefinite program (SDP) for a given combinatorial optimization problem. This is jointly achieved through the forward and backward pass. The message-passing steps in the forward pass are gradient updates to the node embeddings towards the direction that minimizes the augmented Lagrangian of the SDP. The backward pass aids this process by backpropagating derivatives from the augmented Lagrangian
to the parameters of the neural network. Figure 1 summarizes the OptGNN pipeline for solving CO problems. Consider the Max Cut problem as an example. Given a distribution over graphs \(\mathcal{D}\), for an input graph, OptGNN computes node embeddings \(v_{1},v_{2},\ldots,v_{N}\in\mathbb{R}^{r}\) which are then plugged into the loss function. The loss in that case would be the Lagrangian which is calculated as \(\mathcal{L}(\mathbf{v};G)=-\sum_{(i,j)\in E}\frac{1}{2}(1-\langle v_{i},v_{j} \rangle)\) (see Appendix A for a minimum vertex cover example). The network is then trained in a completely unsupervised fashion by minimizing \(\mathbb{E}_{G\sim\mathcal{D}}[\mathcal{L}_{p}(\mathbf{v};G)]\) with a standard automatic differentiation package like Pytorch (Paszke et al., 2019).

Our theoretical result pertains to capturing the convex relaxation of Raghavendra (2008). As a message-passing algorithm, OptGNN does not deal with the issue of rounding fractional solutions. In practice, when implementing OptGNN, we round its fractional solutions using randomized rounding. Specifically, for each node with embedding vector \(v_{i}\), its discrete assignment \(x_{i}\in\{-1,1\}\) is calculated by \(x_{i}=\text{sign}(v_{i}^{\top}y)\), for a random hyperplane vector \(y\in\mathbb{R}^{r}\). We use multiple hyperplanes to obtain multiple solutions and then pick the best one. The solution is then post-processed with a simple heuristic. This enables fast inference while also helping ensure feasibility in the case of problems with constraints.

## 4 Experiments

### Comparisons with classical algorithms

We report experimental measurements of the performance of the OptGNN approach on two NP-Hard combinatorial optimization problems, _Maximum Cut_ and _Minimum Vertex Cover_. We obtain results for several datasets and compare against greedy algorithms, a state-of-the-art MIP solver (Gurobi). For details of the experimental setup see Appendix C.

Results.Overall, we may clearly see that OptGNN can consistently outperform a greedy algorithm and is competitive with Gurobi when execution time is taken into account. Table 1 presents results for the maximum cut problem. Specifically, we report the average integral cut value achieved

\begin{table}
\begin{tabular}{l r r r r r} \hline \hline Dataset & OptGNN & Greedy & Gurobi & Gurobi & Gurobi \\  & & & 0.1s & 1.0s & 8.0s \\ \hline \hline BA\({}^{\text{A}}\) (50,100) & 351.49 (18) & 200.10 & 351.87 & 352.12 & 352.12 \\ BA\({}^{\text{A}}\) (100,200) & 717.19 (20) & 407.98 & 719.41 & 719.72 & 720.17 \\ BA\({}^{\text{A}}\) (400,500) & 2197.99 (66) & 1255.22 & 2208.11 & 2208.11 & 2212.49 \\ \hline ER\({}^{\text{A}}\) (50,100) & 528.95 (18) & 298.55 & 529.93 & 530.03 & 530.16 \\ ER\({}^{\text{A}}\) (100,200) & 1995.05 (24) & 1097.26 & 2002.88 & 2002.88 & 2002.93 \\ ER\({}^{\text{A}}\) (400,500) & 16387.46 (225) & 8622.34 & 16476.72 & 16491.60 & 16495.31 \\ \hline HK\({}^{\text{A}}\) (50,100) & 345.74 (18) & 196.23 & 346.18 & 346.42 & 346.42 \\ HK\({}^{\text{A}}\) (100,200) & 709.39 (23) & 402.54 & 711.68 & 712.26 & 712.88 \\ HK\({}^{\text{A}}\) (400,500) & 2159.90 (61) & 1230.98 & 2169.46 & 2169.46 & 2173.88 \\ \hline WC\({}^{\text{A}}\) (50,100) & 198.29 (18) & 116.65 & 198.74 & 198.74 & 198.74 \\ WC\({}^{\text{A}}\) (100,200) & 389.83 (24) & 229.43 & 390.96 & 392.07 & 392.07 \\ WC\({}^{\text{A}}\) (400,500) & 1166.47 (78) & 690.19 & 1173.45 & 1175.97 & 1179.86 \\ \hline MUTAG\({}^{\text{b}}\) & 27.95 (9) & 16.95 & 27.95 & 27.95 & 27.95 \\ ENZYMES\({}^{\text{b}}\) & 81.37 (14) & 48.53 & 81.45 & 81.45 & 81.45 \\ PROTEINS\({}^{\text{b}}\) & 102.15 (12) & 60.74 & 102.28 & 102.36 & 102.36 \\ IMDB-BIN\({}^{\text{b}}\) & 97.47 (11) & 51.85 & 97.50 & 97.50 & 97.50 \\ COLLAB\({}^{\text{b}}\) & 2622.41 (22) & 1345.70 & 2624.32 & 2624.57 & 2624.62 \\ \hline REDDIT-BIN\({}^{\text{c}}\) & 693.33 (186) & 439.79 & 693.02 & 694.10 & 694.14 \\ REDDIT-M-12K\({}^{\text{c}}\) & 568.00 (89) & 358.40 & 567.71 & 568.91 & 568.94 \\ REDDIT-M-5K\({}^{\text{c}}\) & 786.09 (133) & 495.02 & 785.44 & 787.48 & 787.92 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Performance of OptGNN, Greedy, and Gurobi 0.1s, 1s, and 8s on Maximum Cut. For each approach and dataset, we report the average cut size measured on the test slice. Here, higher score is better. In parentheses, we include the average runtime in _milliseconds_ for OptGNN.
by OptGNN and classical baselines on a variety of datasets. We note that Greedy achieves poor performance compared to OptGNN and Gurobi on every dataset, indicating that for these datasets, finding Maximum Cut is not trivial. On the worst case, WS (400, 500), OptGNN achieves a cut value within 1.1% on average of Gurobi with an 8s time limit. On other datasets, OptGNN is typically within a fraction of a percent. Notably, OptGNN is within 0.1% of Gurobi 8s on all the TU datasets.

Table 2 presents the average size of the Vertex Cover achieved by OptGNN and classical baselines on our datasets. For this problem OptGNN also performs nearly as well as Gurobi 8s, remaining within 1% on the TU datasets and 3.1% on the worst case, ER (100, 200). OptGNN in certain cases outperforms Gurobi when considering execution time. Indeed, OptGNN requires only a few milliseconds to execute and is able to frequently outperform Gurobi when the latter is given a comparable time budget (0.1s). However, Gurobi with a 1s time budget is able to solve many of the datasets to optimality. While more computationally expensive than OptGNN, this constitutes only a small increase in total execution time for the entire dataset so Gurobi remains an extremely strong baseline.

### Experimental demonstration of neural certificates.

In this section, we provide a simple experimental example of our neural certificate scheme on small synthetic instances. Deploying this scheme on Max Cut on random graphs, we find this dual certificate to be remarkably tight. An example can be seen in figure 3. For \(100\) node graphs with \(1000\) edges our certificates deviate from the SDP certificate by about \(20\) nodes but are dramatically faster to produce. The runtime is dominated by the feedforward of OptGNN which is \(0.02\) seconds vs. the SDP solve time which is \(0.5\) seconds on cvxpy. See B.2 for extensive discussion and additional results.

\begin{table}
\begin{tabular}{l c c c c c} \hline \hline Dataset & OptGNN & Greedy & Gurobi & Gurobi & Gurobi \\  & & & 0.1s & 1.0s & 8.0s \\ \hline \hline BA\({}^{\text{a}}\) (50,100) & 42.88 (27) & 51.92 & 42.82 & 42.82 & 42.82 \\ BA\({}^{\text{a}}\) (100,200) & 83.43 (25) & 101.42 & 83.19 & 83.19 & 83.19 \\ BA\({}^{\text{a}}\) (400,500) & 248.74 (27) & 302.53 & 256.33 & 246.49 & 246.46 \\ \hline ER\({}^{\text{a}}\) (50,100) & 55.25 (21) & 68.85 & 55.06 & 54.57 & 54.67 \\ ER\({}^{\text{a}}\) (100,200) & 126.52 (18) & 143.51 & 127.83 & 123.47 & 122.76 \\ ER\({}^{\text{a}}\) (400,500) & 420.70 (41) & 44.84 & 423.07 & 423.07 & 415.52 \\ \hline HK\({}^{\text{a}}\) (50,100) & 43.06 (25) & 51.38 & 42.98 & 42.98 & 42.98 \\ HK\({}^{\text{a}}\) (100,200) & 84.38 (25) & 100.87 & 84.07 & 84.07 & 84.07 \\ HK\({}^{\text{a}}\) (400,500) & 249.26 (27) & 298.98 & 247.90 & 247.57 & 247.57 \\ \hline WC\({}^{\text{a}}\) (50,100) & 46.38 (26) & 72.55 & 45.74 & 45.74 & 45.74 \\ WC\({}^{\text{a}}\) (100,200) & 91.28 (21) & 143.70 & 89.80 & 89.80 & 89.80 \\ WC\({}^{\text{a}}\) (400,500) & 274.21 (31) & 434.52 & 269.58 & 269.39 & 269.39 \\ \hline MUTAG\({}^{\text{b}}\) & 7.79 (18) & 12.84 & 7.74 & 7.74 & 7.74 \\ ENZYMES\({}^{\text{c}}\) & 20.00 (24) & 27.35 & 20.00 & 20.00 & 20.00 \\ PROTEINS\({}^{\text{a}}\) & 25.29 (18) & 33.93 & 24.96 & 24.96 & 24.96 \\ IMDB-BIN\({}^{\text{b}}\) & 16.78 (18) & 17.24 & 16.76 & 16.76 & 16.76 \\ COLLAB\({}^{\text{b}}\) & 67.50 (23) & 71.74 & 67.47 & 67.46 & 67.46 \\ \hline REDDIT-BIN\({}^{\text{c}}\) & 82.85 (38) & 117.16 & 82.81 & 82.81 & 82.81 \\ REDDIT-M-12K\({}^{\text{c}}\) & 81.55 (25) & 115.72 & 81.57 & 81.52 & 81.52 \\ REDDIT-M-5K\({}^{\text{c}}\) & 107.36 (33) & 153.24 & 108.73 & 107.32 & 107.32 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Performance of OptGNN, Greedy, and Gurobi 0.1s, 1s, and 8s on Minimum Vertex Cover. For each approach and dataset, we report the average Vertex Cover size measured on the test slice. Here, lower score is better. In parentheses, we include the average runtime in _milliseconds_ for OptGNN.
### Out Of Distribution generalization

It is reasonable to examine whether our model learns a general combinatorial optimization algorithm or if it merely learns to fit the data distribution. A potential proxy for this is its out of distribution generalization, i.e., its ability to perform well on data distributions that it was not trained on. We test this using a collection of different datasets.

Specifically, for each dataset in our collection, we train a model and then test the trained model on a subset of datasets in the collection. The results are shown in Table 3. It is apparent from the results that the model performance generalizes well to different datasets. Strikingly, we frequently observe that the model reaches its peak performance on a given test dataset even when trained on a different one. This suggests that the model indeed is capturing elements of a more general process instead of just over

\begin{table}
\begin{tabular}{l c c c c c} \hline \hline Train Dataset & MUTAG & ENZYMES & PROTEINS & IMDB-BIN & COLLAB \\ \hline \hline BA (50,100) & **7.74** & 20.12 & 27.66 & 17.57 & 74.15 \\ BA (100,200) & **7.74** & 20.35 & 26.03 & 16.86 & 69.29 \\ BA (400,500) & 8.05 & 21.00 & 26.54 & 17.34 & 70.17 \\ \hline ER (50,100) & **7.74** & 20.37 & 28.17 & 16.86 & 69.07 \\ ER (100,200) & 8.05 & 21.52 & 27.72 & 16.89 & 68.83 \\ ER (400,500) & 7.79 & 21.55 & 28.60 & 16.78 & 68.74 \\ \hline HK (50,100) & **7.74** & 20.42 & 25.60 & 17.05 & 69.17 \\ HK (100,200) & 7.84 & 20.43 & 27.30 & 17.01 & 70.20 \\ HK (400,500) & 7.95 & 20.63 & 26.30 & 17.15 & 69.91 \\ \hline WC (50,100) & 7.89 & **20.13** & 25.46 & 17.38 & 70.14 \\ WC (100,200) & 7.79 & 20.30 & 25.45 & 17.91 & 71.16 \\ WC (400,500) & 8.05 & 20.48 & 25.79 & 17.12 & 70.16 \\ \hline MUTAG & **7.74** & 20.83 & 26.76 & 16.92 & 70.09 \\ ENZYMES & **7.74** & 20.60 & 28.29 & 16.79 & 68.40 \\ PROTEINS & 7.89 & 20.22 & **25.29** & 16.77 & 70.26 \\ IMDB-BIN & 7.95 & 20.97 & 27.06 & **16.76** & 68.03 \\ COLLAB & 7.89 & 20.35 & 26.13 & **16.76** & **67.52** \\ \hline \hline \end{tabular}
\end{table}
Table 3: Models for Vertex Cover trained on “dataset” were tested on a selection of the TU datasets (ENZYMES, PROTEINS, MUTAG, IMDB-BINARY, and COLLAB). We observe that the performance of the models generalizes well even when they are taken out of their training context.

Figure 2: Experimental comparison of SDP versus Opt-GNN Dual Certificates on random graphs of 100 nodes for the Max Cut problem. Our Opt-GNN certificates track closely with the SDP certificates while taking considerably less time to generate.
### Ablation

In order to better understand the effectiveness of the OptGNN architecture, we compare it against other commonly used GNN architectures from the literature that have been trained using the same loss function. We present the comparison of their performance to OptGNN for maximum cut in Table 4; please see subsection C.2 for the analogous table for minimum vertex cover. It is clear that OptGNN consistently outperforms the other architectures on every dataset that we tested. Note that while OptGNN was consistently the best model, other models were able to perform relatively well; for instance, GatedGCNN achieves average cut values within a few percent of OptGNN on nearly all the datasets (excluding COLLAB). This points to the overall viability of training using an SDP relaxation for the loss function.

## 5 Conclusion

We have presented OptGNN, a GNN that can capture provably optimal message passing algorithms for a large class of combinatorial optimization problems. OptGNN achieves the appealing combination of obtaining approximation guarantees while also being able to adapt to the data to achieve improved results. Empirically, we observed that the OptGNN architecture achieves strong performance on a wide range of datasets and on multiple problems. Since the landscape of combinatorial optimization is expansive, there are still important challenges that have to be addressed within the scope of this work such as the extension of our approach to problems with more complex constraints and objectives. OptGNN offers a novel perspective on the connections between general approximation algorithms and neural networks, and opens up new avenues for exploration. These include the design of more powerful and sound (neural) rounding procedures that can secure approximation guarantees, the construction of neural certificates that improve upon the ones we described in Appendix B.2, and the design of neural SDP-based branch and bound solvers.

## 6 Acknowledgment

The authors would like to thank Ankur Moitra, Sirui Li, and Zhongxia Yan for insightful discussions in the preparation of this work. Nikolaos Karalias is funded by the SNSF, in the context of the project "General neural solvers for combinatorial optimization and algorithmic reasoning" (SNSF grant number: P500PT_217999). Stefanie Jegelka acknowledges support from NSF award 1900933 and NSF AI Institute TILOS (NSF CCF-2112665).

\begin{table}
\begin{tabular}{l l l l l l} \hline \hline Dataset & GAT & GCNN & GIN & GatedGCNN & OptGNN \\ \hline \hline ER\({}^{2}\) (50,100) & 525.92 (25) & 500.94 (17) & 498.82 (14) & 526.78 (14) & **528.95** (18) \\ ER\({}^{2}\) (100,200) & 1979.45 (20) & 1890.10 (26) & 1893.23 (23) & 1978.78 (21) & **1995.05** (24) \\ ER\({}^{2}\) (400,500) & 16317.69 (208) & 15692.12 (233) & 15818.42 (212) & 16188.85 (210) & **16387.46** (225) \\ \hline MUTAG\({}^{\text{b}}\) & 27.84 (19) & 27.11 (12) & 27.16 (13) & **27.95** (14) & **27.95** (9) \\ ENZYMES\({}^{\text{b}}\) & 80.73 (17) & 74.03 (12) & 73.85 (16) & 81.35 (9) & **81.37** (14) \\ PROTEINS\({}^{\text{b}}\) & 100.94 (14) & 92.01 (19) & 92.62 (17) & 101.68 (10) & **102.15** (12) \\ IMDB-BIN\({}^{\text{b}}\) & 81.89 (18) & 70.56 (21) & 81.50 (10) & 97.11 (9) & **97.47** (11) \\ COLLAB\({}^{\text{b}}\) & 2611.83 (22) & 2109.81 (21) & 2430.20 (23) & 2318.19 (18) & **2622.41** (22) \\ \hline \hline \end{tabular}
\end{table}
Table 4: Performance of various model architectures for selected datasets on Maximum Cut. Here, higher is better. GAT is the Graph Attention network (Velicković et al., 2018), GIN is the Graph Isomorphism Network (Xu et al., 2019), GCNN is the Graph Convolutional Neural Network (Morris et al., 2019), and GatedGCNN is the gated version (Li et al., 2015).