Are Graph Neural Networks Optimal Approximation Algorithms?

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 02:49:22

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

Main paper: 
 introduction: 
 Combinatorial Optimization is the class of problems that optimize functions subject to constraints over discrete search spaces. They are almost always 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 & Buchanan, 2019; Ganesh & Vardi, 2020) . In this context, neural networks are natural candidates for learning and then exploiting patterns in the data distribution over CO instances.The emergence of research directions at the intersection of machine learning (ML) and CO which have obtained promising empirical results at 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 focuses on parametrizing heuristics (Li et al., 2018; Khalil et al., 2017; Yolcu & Póczos, 2019; Chen & 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 & 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 (Parjadis 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 Figure 1 : Message-passing neural networks for constraint satisfaction problems. Neural networks trained using the SDP objective as a loss function can be used to produce strong empirical results on Maximum Cut and Minimum Vertex Cover. We observe Maximum Cut performance of within 0.7% and Minimum Vertex Cover performance of within 3.1% of the integral value reported by Gurobi running with a time limit of 8 seconds.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 Lovász theta function to find the maximum independent set on perfect graphs (Lovász, 1979; Grötschel et al., 1981) . In fact, it is known that if the Unique Games Conjecture 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 Unique Games Conjecture. 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 messagepassing 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 and neural baselines across a broad battery of datasets for landmark CO problems such as Max Cut, Vertex Cover, and Max Clique.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.1.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 classical and neural baselines. 
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 (UGC) (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, 2009; 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 & Kolter, 2019) , while Kriváchy 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 an 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 a 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 Lovász 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 & 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, 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 & Bjørner, 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 (Veličković & 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; Böther et al., 2022; Tönshoff 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) .OptGNN is a neural network architecture that uses message passing to solve a semidefinite program (SDP) for a given combinatorial optimization problem. The model learns to produce a feasible low rank solution to a semidefinite program for the max-CSP. 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 L to the parameters of the neural network.Before we define our OptGNN architecture, we first provide the basic technical background and intuition behind the central claim of the paper. First, we show that solving the Max Cut SDP via a simple projected gradient descent scheme amounts to executing a message-passing algorithm on the graph. This sets the stage for our main result which generalizes this observation. We describe a general maximum constraint satisfaction problem (CSP) and the standard semidefinite program (Optimization 1) that computes an approximate solution. Then we formally define OptGNN and show that message passing with OptGNN (algorithm 2) for a general CSP can solve the general SDP in Optimization 1. 
solving sdps with message passing: 
 To build intuition, we begin with the canonical example for the usage of semidefinite programming in combinatorial optimization: the Maximum 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 quadratic integer program over variables x = (x 1 , x 2 , ..., x N ). maxEQUATIONsubject to:x 2 i = 1 ∀i ∈ [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 ∈ R N ×N of variables, where we index the i'th row and j'th column entry as X ij .maxEQUATIONsubject to:X ii = 1 ∀i ∈ [N ] X ⪰ 0 rank(X) = rThe intuition is that a rank r = 1 solution to Algorithm 2 is equivalent to solving the integer program. Thus we wish to solve the optimization problem 2 for small r. A common approach is to replace the integer variables x i with vectors v i ∈ R r and constrain v i to lie on the unit sphere.EQUATIONsubject to:∥v i ∥ = 1 ∀i ∈ [N ] v i ∈ R rFor r larger than Ω( √ N ) Burer & Monteiro (2003) the landscape of this nonconvex optimization is benign in that all local minima are approximately global minima. Thus, for large r, simple algorithms such as projected gradient descent can find an approximate global optimum of the objective. However, for large r, it is unclear how to transform, i.e., round, the vectors 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 updatesEQUATIONwhere η ∈ R + is an adjustable step size and we let N (i) denote the neighborhood of node i. We explore a natural dynamic that we call OptGNN-MaxCut r (v) which generalizes gradient descent to the following form. Let {M 1,t } t∈[T ] ∈ R r×r and {M 2,t } t∈[T ] ∈ R r×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 v, we haveEQUATION)where b is a learnable affine shift. Even more generally, we can write our dynamics asEQUATIONEQUATIONFor efficiently computable functions UPDATE : R 3r → R r and AGGREGATE : R r×r × R r|N (i)| → R r and NONLINEAR : R r → R r . That is to say, our dynamic OptGNN-MaxCut(r) is a GNN. For an analogous discussion on Vertex Cover and Max Clique see A.Rounding vs. Rank: To be clear, we do not regard OptGNN to be an SDP solver. Indeed we demonstrate numerous empirical examples where OptGNN outcompetes the SDP solver. Of course, on instances where the SDP is optimal, we should expect OptGNN to match the SDP performance though this is not a guarantee. We also do not regard OptGNN as an algorithm for learning a 'rounding'. The term 'rounding' is a vague 'catch-all' term for all post-processing of convex relaxations.Observe that 'rounding' is inextricably intertwined with the solving of low rank SDP formulations as for r = 1 no rounding is even necessary. Succinctly, OptGNN finds good CO solutions that captures powerful classes of convex relaxations. Our theory result, which we dive into next, pertains entirely to capturing the convex relaxation of Raghavendra (2008) .Given a set of constraints over variables, Max-CSP asks to find a variable assignment that maximizes the number of satisfied constraints. Max-CSP includes Max Cut, 3-SAT, boolean satisfiability, etc. Formally, we define Max-CSP as follows. Definition 3.1 (Max-k-CSP). A Constraint Satisfaction Problem Λ = (V, P, q) consists of a set of N variables V := {x i } i∈[N ] each taking values in an alphabet [q] and a set of predicates P := {P z } z⊂V where each predicate is a payoff function over k variables denoted X z = {x i1 , x i2 , ..., 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.OP T := maxEQUATIONwhere we normalize by the number of constraints so that the total payoff is in [0, 1]. Therefore we can unambiguously define an ϵ-approximate assignment as an assignment achieving a payoff of OP T -ϵ.There is a reformulation of the SDP of Raghavendra (2008) detailed in Optimization 1 that possesses the optimal integrality gap assuming the Unique Games conjecture. Precisely, for Max-k-CSP we define the approximation ratio to be Approximation Ratio := minΛ∈Max-k-CSP OP T (Λ) SDP (Λ) ,where the minimization is being taken over all instances Λ with arity k. Then there is no polynomial time algorithm that can achieve a superior approximation ratio assuming the truth of the conjecture. Furthermore, there is a polynomial time rounding algorithm that achieves the integrality gap of SDP Optimization 1 (Raghavendra, 2008) . Our main theoretical result is the following. Theorem 3.1. (Informal) Given a Max-k-CSP instance Λ, there exists a message passing Algorithm 2 on constraint graph G λ with a per iteration update time of poly(|P|, q k ) that computes in poly( 1 ϵ , |P|, q k , log(δ -1 )) iterations an ϵ-approximate solution to SDP Optimization 1 with probability 1 -δ. That is to say, Algorithm 2 computes a set of vectors v satisfying constraints of Optimization 1 to error ϵ with objective value denotedOBJ(v) satisfying |OBJ(v) -SDP (Λ)| ≤ ϵ.For the formal theorem and proof see Theorem B.1. Our algorithm is remarkably simple: perform gradient descent on the quadratically penalized objective of the reformulated SDP Optimization 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 |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 |P|q k vectors. For Max Cut for example this would mean each vector corresponds to a node which is updated as a function of the vectors in adjacent vertices. This message passing form allows us to define a natural GNN generalization that captures the gradient iteration of Algorithm 2.To make the above discussion precise, we define the constraint graph associated so a Max-CSP instance Λ as follows.Definition 3.2. [Constraint Graph G Λ = (V, E)] Given a Max-k-CSP instance Λ = (V, P, q) a constraint graph G Λ = (V, E) is comprised of vertices V = {v ϕ,ζ} for every subset of variables ϕ ⊆ z for every predicate P z ∈ P and every assignment ζ ∈ [q] k to the variables in z. The edges E are between any pair of vectors v ϕ,ζ and v ϕ ′ ,ζ ′ such that the variables in ϕ and ϕ ′ appear in a predicate together.Furthermore, we define message passing algorithms on the constraint graph G Λ as follows. Definition 3.3. [Message Passing Algorithm] Given a graph G = (V, E) with a set of vectors v = {v i } i∈V a message passing algorithm for T iterations is an update of the form; for vector v i in v and for iteration t ∈ [T ],v t i = UPDATE({v t j } j∈N (i) , v t i ) For an arbitrary polynomial time computable function UPDATE : R r(|N (i)|+1) → R rThen by inspection of the gradient iteration of Algorithm 2 we see that for a Max-k-CSP instance Λ, Algorithm 2 is a message passing algorithm on the associated constraint graphG Λ . Definition 3.4 (OptGNN). Given a Max-k-CSP instance Λ, an OptGNN (T,r,GΛ) (v) is a T layer, dimension r, neural network over constraint graph G Λ with learnable matrices {M 1,t } t∈[T ] , {M 2,t } t∈[T ], and affine shift {b t } t∈[T ] that generalizes the gradient iteration equation 32 of Algorithm 2 with an embedding v ∈ v for every node in G Λ with updates of the formv t+1 w = UPDATE(M 1,t v t w , AGGREGATE(M 2,t , {v t j } j∈N (w) , v t w ), b t ) v t+1 w = NONLINEAR(v t+1w ) For arbitrary polynomial time computable functions UPDATE : R 3r → R r , AGGREGATE : R r×r × R r(|N (w)|+1) → R r , and NONLINEAR : R r → R r . Here by 'generalize' we mean there exists an instantiation of the learnable parameters {M 1,t } t∈[T ] and {M 2,t } t∈[T ] such that OptGNN is equivalent to equation 32.The crux of our proof is then to construct a message passing algorithm for the reformulated SDP Optimization 1 which is the subject of Appendix B.Our theoretical results lead to a simple practical recipe for solving CO problems with OptGNN. Consider a distribution over graphs D. OptGNN computes node embeddings V ∈ R r for minibatches of training graphs, which are then plugged into the Lagrangian, which is used as a loss function. Going back to the maxcut example, the loss in that case would be calculated asL(V ; G) = -(i,j)∈E 1 2 (1 -⟨v i , v j ⟩).The network is then trained in a completely unsupervised fashion by minimizing E G∼D [L(V ; G)] with a standard automatic differentiation package like Pytorch (Paszke et al., 2019) . At inference time, the neural network produces fractional embeddings V that we discretize with hyperplane rounding followed by a simple greedy heuristic. This enables fast inference while also helping ensure feasibility in the case of problems with constraints. For an example of the Lagrangian in the case of an optimization problem with additional constraints like Vertex Cover, see Appendix A. 
experiments: 
 In this section, we report experimental measurements of the performance of the OptGNN approach on two NP-complete combinatorial optimization problems, Maximum Cut and Minimum Vertex Cover.Datasets Our experiments span a variety of randomly generated and real-world datasets. Our randomly generated datasets contain graphs from several random graph models, in particular Erdős-Rényi (with p = 0.15), Barabási-Albert (with m = 4), Holme-Kim (with m = 4 and p = 0.25), and Watts-Strogatz (with k = 4 and p = 0.25). Our real-world datasets are ENZYMES, PROTEINS, MUTAG, IMDB-BINARY, COLLAB (which we will together call TU-small), and REDDIT-BINARY, REDDIT-MULTI-5K, and REDDIT-MULTI-12K (which we will call TU-REDDIT).We abbreviate the generated datasets using their initials and the range of vertex counts. For example, by ER (50,100) we denote Erdős-Rényi random graphs with a vertex count drawn uniformly at random from [50, 100] . In tables, we mark generated datasets with superscript a , TU-small with b , and TU-REDDIT with c .Baselines We compare the performance of our approach against classical and neural baselines. In terms of classical baselines, we run Gurobi with varying timeouts and include SDP results on smaller datasets. SDP scales extremely poorly with graph size so we omit the results for datasets with larger graphs. For minimum Vertex Cover, we include the classical baseline KaMIS, a maximum independent set solver. We also include a greedy baseline, which is the function one exchange (for Maximum Cut) or min weighted vertex cover (for minimum Vertex Cover) from networkx (Hagberg et al., 2008) . Our neural baselines include LwD (Ahn et al., 2020) and DGL-TREESEARCH (Li et al., 2018; Böther et al., 2022) .Validation and test splits For each dataset we hold out a validation and test slice for evaluation. In our generated graph experiments we set aside 1000 graphs each for validation and testing. Each step of training ran on randomly generated graphs. For TU-small, we used a train/validation/test split of 0.8/0.1/0.1. For TU-REDDIT, we set aside 100 graphs each for validation and testing.Scoring To measure a model's score on a graph, we first run the model on the graph to generate an SDP output, and then round this output to an integral solution using 1,000 random hyperplanes. We ran validation periodically during each training run and retained the model that achieved the highest validation score. Then for each model and dataset, we selected the hyperparameter setting that achieved the highest validation score, and we report the average score measured on the test slice. Please see subsection C.2 for further details on the hyperparameter ranges used.Table 1 presents the average integral cut value achieved 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. 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. Table 3 : Performance of various model architectures for selected datasets on Maximum Cut. Here, higher is better. GAT is the Graph Attention network (Veličković 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) .Our approach of training on the SDP objective generalizes to neural network architectures other than OptGNN. We trained several architectures besides OptGNN on a subset of our datasets for both maximum cut and minimum vertex cover. We present the comparison of their performance to OptGNN for maximum cut in Table 3 ; please see subsection C.4 for the analogous table for minimum vertex cover. On the datasets we used, OptGNN outperforms the other architectures we tested. We note that compared to OptGNN, many other models performed fairly well; for instance, GatedGCNN achieves average cut values within a few percent of OptGNN on nearly all the datasets (excluding COLLAB). An interesting question for future investigation is what architectures may perform better than OptGNN. 
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.1, and the design of neural SDP-based branch and bound solvers.Under 1 + x i 2 (11)EQUATION)EQUATIONTo deal with the constraint on the edges (1 -x i )(1 -x j ) = 0, we add a quadratic penalty to the objective with a penalty parameter ρ > 0 yieldingEQUATIONSubject to:EQUATIONAnalogously to Max Cut, we introduce a natural low rank vector formulation LiftVertexCover r (v)for vectors v = {v i } i∈[N ] in r dimensions. Minimize: LiftVertexCover r (v) := i∈[N ] 1 + ⟨v i , e 1 ⟩ 2 + ρ (i,j)∈E(1 -⟨v i , e 1 ⟩ -⟨v j , e 1 ⟩ + ⟨v i , v j ⟩) 2(16) Subject to:EQUATIONNow we can design a simple projected gradient descent scheme as follows. For iteration t in max iterations T , and for vector v i in v we perform the following update.EQUATIONEQUATIONWe can then define a OptGNN-VertexCover r (v) analogously with learnable matrices {M 1,t } t∈[T ] ∈ R r×r and {M 2,t } t∈[T ] ∈ R r×r which are each sets of T learnable matrices corresponding to T layers of neural network. Then for layer t in max iterations T , for v i in v, we haveEQUATIONWhich once again we see can be captured by the dynamicEQUATIONFor functions UPDATE : R 3r → R r and AGGREGATE : R r|N (i)| → R r and NONLINEAR : R r → R r . 
 
 Appendix: Our primary theoretical result is that a polynomial time message passing algorithm on an appropriately defined constraint graph computes the approximate optimum of Optimization 1 which is notable for being an SDP that achieves the Unique Games optimal integrality gap.Our proof roadmap is simple. First, we design an SDP relaxation Optimization 1 for Max-k-CSP that is provably equivalent to the SDP of Raghavendra (2008) and therefore inherits its complexity theoretic optimality. Finally, we design a message passing algorithm to approximately solve Optimization 1 in polynomial time to polynomial precision. Our message passing algorithm has the advantage of being formulated on an appropriately defined constraint graph. For a Max-k-CSP instance Λ with N variables, |P| predicates, over an alphabet of size q, it takes |P|q k space to represent the Max-CSP. Our message passing algorithm achieves an additive ϵ approximation in time poly( 1 ϵ , N, |P|q k ) which is then polynomial in the size of the CSP and inverse polynomial in the precision.Here we briefly reiterate the definition of Max-k-CSP. A Max-k-CSP instance Λ = (V, P, q) consists of a set of N variables V := {x i } i∈[N ] each taking values in an alphabet [q] and a set of predicates P := {P z } z⊂V where each predicate is a payoff function over k variables denoted z = {x i1 , x i2 , ..., x i k }. Here we refer to k as the arity of the GCSP, and we adopt the normalization that each predicate P z returns outputs in [0, 1]. We index each predicate P z by its domain z and we will use the notation S(P ) to denote the domain of a predicate P . The goal of Max-k-CSP is to maximize the payoff of the predicates.EQUATIONWhere X z denotes the assignment of variables {x i } i∈z .There is an SDP relaxation of equation 24 that is the "qualitatively most powerful assuming the Unique Games conjecture" Raghavendra (2008) . More specifically, the integrality gap of the SDP achieves the Unique Games optimal approximation ratio. Furthermore, there exists a rounding that achieves its integrality gap.SDP Reformulation: Next we will introduce the SDP formulation we adopt in this paper. For the sake of exposition and notational simplicity, we will work with binary Max-k-CSP's where q = {0, 1}. The extension to general q is straightforward and detailed in the appendix. TODOWe will adopt the standard pseudoexpectation and pseudodistribution formalism in describing our SDP. Let Ẽµ [X] be a matrix in dimension R (N +1) k/2 ×(N +1) k/2 of optimization variables defined as followsEQUATIONWhere we use ⊗ to denote tensor product. It is convenient to think of Ẽµ [X] as a matrix of variables denoting the up to k multilinear moments of a distribution µ over the variables V. A multilinear polynomial is a polynomial of the form X ϕ := i∈ϕ x i for some subset of the variables ϕ ⊆ V.We index the variables of the matrix Ẽµ [X] by the multilinear moment that it represents. Notice that this creates repeat copies as their are multiple entries representing the same monomial. This is dealt with by constraining the repeated copies to be equal with linear equality constraints.Specifically, let z be a subset of the CSP variables z ⊂ {x i } i∈[N ] of size k. Let X z denote the multilinear moment X z := i∈z x i . Then Ẽµ [X z ] denotes the SDP variable corresponding to the multilinear moment E µ [X z ]. Of course optimizing over the space of distributions µ over V is intractable, and so we opt for optimizing over the space of low degree pseudodistributions and their associated pseudoexpecation functionals. See Barak & Steurer (2014) for references therein.In particular, for any subset of variables X z := {x i1 , ..., x i k } ∈ V we let Ẽµ [X] z,d denote the matrix of the up to degree up to d multilinear moments of the variables in z.EQUATIONSubsequently, we describe a pseudoexpectation formulation of our SDP followed by a vector formulation.Multilinear Formulation: A predicate for a boolean Max-k-CSP P z (X z ) can be written as a multilinear polynomialEQUATIONFor some real valued weights w z,τ and w s which are simply the fourier coefficients of the function P z . Then the pseudoexpectation formulation of our SDP is as followsEQUATIONsubject to the following constraints 1. Unit: Ẽµ [1] = 1, Ẽµ [x 2 i ] = 1 for all x i ∈ V, and Ẽµ [ i∈s x 2 i j∈s ′ x j ] = Ẽµ [ j∈s ′ x j ] for all s, s ′ ⊆ S(P ) for every predicate P ∈ P such that 2s + s ′ ≤ k. In expectation, the squares of all multilinear polynomials are equal to 1.Positive Semidefinite: Ẽµ [X]| V,2 ⪰ 0 i.e the degree two pseudoexpectation is positive semidefinite. Ẽµ [X] z,k ⪰ 0 for all z = S(P ) for all P ∈ P. The moment matrix for the multilinear polynomials corresponding to every predicate is positive semidefinite.Equivalently we can view the SDP in terms of the vectors in the cholesky decomposition of Ẽµ [X]. We rewrite the above SDP accordingly. For this purpose it is useful to introduce the notationζ(A, B) := A ∪ B/A ∩ B.It is also useful to introduce the notation C(s) for the size of the set {g, g ′ ⊆ s : ζ(g, g ′ ) = s}. Lemma B.1. For Max-k-CSP instance Λ, The SDP of Optimization 1 is at least as tight as the SDP of Raghavendra (2008) .Proof. The SDP of Raghavendra ( 2008) is a based degree 2 SoS SDP augmented with k-local distributions for every predicate P ∈ P. By using the vectors of the cholesky decomposition and constraining them to be unit vectors we automatically capture degree 2 SoS. To capture k local distributions we simply enforce degree 2k SoS on the boolean hypercube for the domain of every predicate. This can be done with the standard vector formulation written in Optimization 1. See Barak & Steurer (2014) for background and references.Theorem B.1. Algorithm 2 computes in poly(1/ϵ, |P|, 2 k , log(δ -1 )) iterations a set of vectors v := {v s } for all s ⊆ S(P ) for all P ∈ P that satisfy the constraints of Optimization 1 to error ϵ and approximates the optimum of Optimization 1 to error ϵ with probability 1 -δ Pz∈P Ẽμ [P z (X z )] -OP T SDP (Λ) ≤ ϵwhere OP T SDP (Λ) is the optimum of Optimization 1.Algorithm 1 SDP Vector Formulation for Max-k-CSP 1: procedure SDP VECTOR FORMULATION(Λ = (V, P, {0, 1})) ▷ SDP Equivalent to UGC optimal Minimize:Pz⊂P Ẽµ [-P z (X z )] := Pz∈P s⊆z w s 1 |C(s)| g,g ′ ⊆s:ζ(g,g ′ )=s ⟨v g , v g ′ ⟩ (29) 2:▷ multilinear formulation of objective Subject to: v 0 = {v s } s⊆z:Pz∈P ← U nif orm(S n-1 ) ▷ Initialize vectors to uniform on the unit sphere return v t ▷ Returns the vectors corresponding to solution to Optimization 1 18: end procedure Proof. We begin by writing down the objective penalized by a quadratic on the constraints.∥v s ∥ 2 = 1 ∀s ⊆ S(P ) ∀P ∈ P (30) Ẽµ [X ζ(g,g ′ ) ] := ⟨v g , v g ′ ⟩ = ⟨v h , v h ′ ⟩ ∀ζ(g, g ′ ) = ζ(h, h ′ ) s.t g ∪ g ′ ⊆ S(P ) ∀P ∈ P (31) ▷ First constraintEQUATIONL ρ (v) := Pz∈P Ẽµ [P z (X z )] + ρ Pz∈P g,g ′ ,h,h ′ ⊆z:ζ(g,g ′ )=ζ(h,h ′ ) ⟨v g , v g ′ ⟩ -⟨v h , v h ′ ⟩ 2 + vs∈v (∥v s ∥ 2 -1) 2 (35)For any monomial X s = i∈s x i in P z (X z ) we writeẼµ [X s ] := 1 |C(s)| g,g ′ ⊆s:ζ(g,g ′ )=s ⟨v g , v g ′ ⟩ (36)Where C(s) is the size of the set {g, g ′ ⊆ s : ζ(g, g ′ ) = s}. In a small abuse of notation, we regard this as the definition of Ẽµ [X s ] but realizet that we're referring to the iterates of the algorithm before they've converged to a pseudoexpectation. Now recall equation 27, we can expand the polynomial P z (X z ) along its standard monomial basisEQUATION)where we have defined coefficients w s for every monomial in P z (X z ). Plugging equation 36 and equation 37 into equation 35 we obtain(35) = Pz∈P s⊆z w s 1 |C(s)| g,g ′ ⊆s:ζ(g,g ′ )=s ⟨v g , v g ′ ⟩ + ρ Pz∈P g,g ′ ,h,h ′ ⊆z:ζ(g,g ′ )=ζ(h,h ′ ) ⟨v g , v g ′ ⟩ -⟨v h , v h ′ ⟩ 2 + vs∈v (∥v s ∥ 2 -1) 2 (38)Taking the derivative with respect to any v w ∈ v we obtain ∂L ρ (v) ∂v w =Pz∈P:w⊆z s⊆z:w⊆sw s 1 |C(s)| w ′ ⊆s:ζ(w,w ′ )=s v w ′ + 2ρ Pz∈P:w⊆z w ′ ,h,h ′ ⊆s:ζ(w,w ′ )=ζ(h,h ′ ) ⟨v w , v w ′ ⟩ -⟨v h , v h ′ ⟩ v ′ w + (∥v w ∥ 2 -1)v w (39)The gradient update is then what is detailed in Algorithm 2v t+1 w = v t w -η ∂L ρ (v) ∂v w (40)Thus far we have established the form of the gradient. To prove the gradient iteration converges we reference the literature on convergence of perturbed gradient descent (Jin et al., 2017) . First we note that the SDP equation 29 has ℓ smooth gradient for ℓ ≤ poly(ρ, |P|, 2 k ) and has γ lipschitz Hessian for γ = poly(ρ, |P|, 2 k ) which we arrive at by bounding the size of every matrix involved in the objective and constraints of Optimization 1. Then by Theorem B.2 the iteration converges to an (ϵ ′ , γ 2 )-SOSP in no more than Õ( 1 ϵ ′2 ) iterations with probability 1 -δ. It remains to show that (ϵ ′ , γ 2 )-SOSP are approximately global optimum.Under review as a conference paper at ICLR 2024 Thus far we have worked with the vector version of the SDP which is overparameterized and nonconvex. For subsequent analysis we need to define the penalized loss which we denote Hρ ( Ẽ[X]) in terms of the SDP moment matrix Ẽ[X]. H ρ ( Ẽ[X]) := Pz∈P Ẽμ [P z (X z )] +ρ Pz∈P g,g ′ ,h,h ′ ⊆z:ζ(g,g ′ )=ζ(h,h ′ ) Ẽμ [X g,g ′ ]-Ẽμ [X h,h ′ ] 2 + Xs:s⊂S(P ),|s|≤k,∀P ∈P ( Ẽμ [X 2 s ]-1) 2 (41)Note that although by definition H ρ ( Ẽ[X]) = L ρ (v) , their gradients and hessians are distinct because L ρ (v) is overparameterized.For the SDP we are working a global optimum clearly exists which we denote Ẽμ [ X] with a cholesky decomposition ṽ. Let v be the set of vectors outputted by Algorithm 2 with associated pseudoexpectation Ẽμ [ X]. Then, we can boundL ρ (v) -L ρ (ṽ) = H ρ ( Ẽ[ X]) -H ρ ( Ẽ[ X]) ≤ ∇H ρ ( Ẽ[ X]), Ẽ[ X] -Ẽ[ X] (42)Here the first equality is by definition, and the inequality is by the convexity of H ρ . Moving on, we observe that∇ 2 L ρ (v) ⪰ -γ √ ϵ ′ implies λ min (∇H ρ ( Ẽ[ X])) ≥ -γ √ ϵ ′. This derivation can be found in multiple references such as Bhojanapalli et al. (2018) . We adapt the lines of their argument in lemma 3 most relevant to our analysis which we detail here for the sake of completeness.equation 42 ≤ -λ min (∇H ρ ( Ẽ[ X])) Tr( Ẽ[ X]) -∇H ρ ( Ẽ[ X]), Ẽ[ X] ≤ -λ min (∇H ρ ( Ẽ[ X])) Tr( Ẽ[ X]) + ∥∇H ρ ( Ẽ[ X])∥ F ∥ Ẽ[ X]∥ F ≤ γ √ ϵ ′ Tr( Ẽ[X]) + ϵ ′ ∥ṽ∥ F ≤ γ √ ϵ ′ |P|2 k + ϵ ′ |P|2 k ≤ ϵ (43)Here the first inequality follows by a standard inequality of frobenius inner product, the second inequality follows by Cauchy-Schwarz, the third inequality follows by the SOSP conditions on both the min eigenvalue of the hessian and the norm of the gradient, the final two inequalities follow from knowing the main diagonal of Ẽ[ X] is the identity and that every vector in ṽ is a unit vector up to inverse polynomial error. For this last point see the proof in Lemma B.2. Therefore if we set ϵ ′ = poly(ϵ, |P|, 2 k ) we arrive at any ϵ error. Therefore we have established our estimate v is approximates the global optimum of the quadratically penalized objective i.e H ρ ( Ẽ[ X]) -H ρ ( Ẽ[ X]) ≤ ϵ.To finish our proof, we have to bound the distance between the global optimum of the quadratically penalized objective H ρ ( Ẽ[ X]) and OPTSDP(Λ) the optimum of Optimization 1. This is established for ρ a sufficiently large poly(ϵ -1 , |P|, 2 k ) in Lemma B.2. This concludes our proof that the iterates of Algorithm 2 converge to the solution of the SDP Optimization 1.The following Lemma B.2 establishes that Lemma B.2. Let Λ be a Max-k-CSP instance, and let OPTSDP(Λ) be the optimum of Optimization 1. Let L ρ (v) be the quadratically penalized objectiveL ρ (v) := Pz∈P s⊆z w s 1 |C(s)| g,g ′ ⊆s:ζ(g,g ′ )=s ⟨v g , v g ′ ⟩ + ρ Pz∈P g,g ′ ,h,h ′ ⊆z:ζ(g,g ′ )=ζ(h,h ′ ) ⟨v g , v g ′ ⟩ -⟨v h , v h ′ ⟩ 2 + vs∈v (∥v s ∥ 2 -1) 2 (44)Let ṽ be the argmin of the unconstrained minimization ṽ := arg minv∈R |P| 2 (2 2k ) L ρ (v)Then we haveL ρ (ṽ) -OPTSDP(Λ) ≤ ϵ for ρ = poly( 1 ϵ , |P|, 2 k )Proof. We begin the analysis with the generic equality constrained semidefinite program of the form Minimize: ⟨C, X⟩ (45) Subject to:EQUATIONFor an objective matrix C and constraint matrices {A i } i∈F in some constraint set F. We will invoke specific properties of Optimization 1 to enable our analysis. First we define the penalized objective in this generic formH ρ (X) := ⟨C, X⟩ + ρ i∈F (⟨A i , X⟩ -b i ) 2Let X be the minimizer of the penalized problem.X := arg min X∈R d×d L ρ (X)Let X * be the minimizer of the constrained problem equation 61. Let τ i be the error X has in satisfying constraint ⟨A i , X⟩ = b i .τ i := |⟨A i , X⟩ -b i |We will show that τ i scales inversely with ρ. That is, τ i ≤ poly(|P|, 2 k , ρ -1 ).Notice that the quadratic penalty on the violated constraints must be smaller than the decrease in the objective for having violated the constraints. So long as the objective is not too sensitive 'robust' to perturbations in the constraint violations the quadratic penalty should overwhelm the decrease in the objective. To carry out this intuition, we begin with the fact that the constrained minimum is larger than the penalized minimum.EQUATIONRearranging LHS and RHS we obtainρ i∈F τ 2 i ≤ ⟨C, X -X * ⟩ (51)We know the RHS is upper boundedEQUATIONThe last line follows from the robustness theorem of Steurer (2010) lemma 3.4 that states for an SDP solution that violates the constraints by a small perturbation changes the objective by a small amount. Then taking Cauchy-Schwarz of the RHS we further bound byρ i∈F τ 2 i ≤ |F| i∈F τ 2 i poly(k, q)Rearranging left and right hand sides we obtain i∈F τ 2 i ≤ ρ -1 poly(k, q)|F| which implies ∥τ ∥ = poly(|P|, 2 k , ρ -1 ). Moving on, consider the dual feasibility conditionC = Q + i∈F λ i A i for some Q ⪰ 0. Then we have ⟨C, X * -X⟩ = ⟨Q, X * ⟩ -⟨Q, X⟩ + i∈F λ i ⟨A i , X * -X⟩By complementary slackness ⟨Q, X * ⟩ = 0 so we obtain= -⟨Q, X⟩ + i∈F λ i ⟨A i , X * -X⟩By PSD'ness of both Q and X we upper bound by≤ i∈F λ i ⟨A i , X * -X⟩ = i∈F λ i (b i -⟨A i , X⟩) ≤ i∈F λ 2 i ∥τ ∥Where in the first equality we used the fact that ⟨A i , X⟩ = b i , and the second inequality is Cauchy-Schwarz. Since we've already established that ∥τ ∥ ∝ ρ -1 we must simply bound the size of the dual variables λ i . To bound the size of λ i , we separate the constraints A i into the diagonal constraints {F i } i∈W and equality constraints {G i } i∈R where⟨F i , X⟩ = 1 ∀i ∈ W ⟨G i , X⟩ = 0 ∀i ∈ RThe dual takes on the following form for δ, η ∈ R Maximize:EQUATIONWhere we've split the dual variables {λ i } i∈F into two sets {δ i } i∈W and {η i } i∈R . Note that the δ i are polynomially bounded i.e |δ i | ≤ poly(|P|, 2 k ). Assume the contrary, if δ i > poly(|P|, 2 k ) then the objective is polynomially unbounded which contradicts dual objective being smaller than primal objective. If δ i < -poly(P, 2 k ) then the i ′ th diagonal coordinate of equation 54 is polynomially unbounded and then e i is a negative eigenvalue of equation 54 which is a contradiction of PSD'ness. Therefore, the δ i are polynomially bounded. To demonstrate the {η i } i∈R are polynomially bounded, note that because of linear independence of the constraints plus the minimum singular value being greater than a constant, there exists a setting of the η that is polynomially bounded such that the dual feasibility constraint is satisfied. Since the η do not appear in the objective, finding a setting that satisfies equation 54 suffices.Constraint matrix is well conditioned. The smallest singular value of {A i } i∈F is a constant. This is a technical observation about collections of vectors of the form {e 1 + e j } j∈[2,T ] where e i is the i ′ th standard basis vector. Any unit vector v satisfies ∥ j v j (e 1 + e j )∥ = ( j v j ) 2 + j v 2 j ≥ 1.Finally we show it's not hard to generalize our algorithm to alphabets of size [q] . Algorithm 3 SDP Vector Formulation for Max-k-CSP General Alphabet 1: procedure SDP VECTOR FORMULATION GENERAL ALPHABET(Λ = (V, P, q)) ▷ SDP Equivalent to UGC optimal Minimize:EQUATION▷ Pseudoexpectation formulation of objective Subject to: Ẽµ [(x 2 (i,a) -x (i,a) )(j,b)∈ϕx (j,b) ] = 0 ∀i ∈ V, ∀a ∈ [q], ∀ϕ ⊆ D(P ), ∀P ∈ P (56) Ẽµ [( a∈[q] x ia -1)EQUATION▷ First constraint corresponds to booleanity 3:▷ Second constraint corresponds to a variable taking on only one value in the alphabet 4:▷ Third constraint corresponds to a variable taking on only one value in the alphabet 5:▷ Fourth constraint corresponds to 6:▷ Fifth constraint correpsonds to the positivity of every degree two sum of squares of polynomials 7: end procedure Notation for General Alphabet. For any predicate P ∈ P, let D(P ) be the set of all variable assignment tuples indexed by a set of variables s ⊆ S(P ) and an assignment τ ∈ [q] |s| . Let x (i,a) denote an assignment of value a ∈ [q] to variable x i . Lemma B.3. There exists a message passing algorithm that computes in poly(1/ϵ, |P|, 2 k , log(δ -1 )) iterations a set of vectors v := {v (i,a) } for all (i, a) ∈ ϕ, for all ϕ ⊆ D(P ), for all P ∈ P that satisfy the constraints of Algorithm 3 to error ϵ and approximates the optimum of Algorithm 3 to error ϵ with probability 1 -δ Pz∈P Ẽμ [P z (X z )] -OP T SDP (Λ) ≤ ϵ where OP T SDP (Λ) is the optimum of Algorithm 3.Proof. The proof is entirely parallel to the proof of Theorem B.1. We can write Algorithm 3 entirely in terms of the vector of its cholesky decomposition where once again we take advantage of the fact that SoS degree 2kq distributions are actual distributions over subsets of kq variables over each predicate. Given the overparameterized vector formulation, we observe that once again we are faced with equality constraints that can be added to the objective with a quadratic penalty. Perturbed gradient descent induces a message passing algorithm over the constraint graph G Λ , and in no more than poly( 1 ϵ , |P |, q k ) iterations reaches an (ϵ, γ)-SOSP. The analysis of optimality goes along the same lines as Lemma B.2. For sufficiently large penalty ρ = poly( 1 ϵ , |P |, q k ) the error in satisfying the constraints is ϵ and the objective is robust to small perturbations in satisfying the constraint. That concludes our discussion of generalizing to general alphabets.An intriguing aspect of OptGNN is that the embeddings can be interpreted as the solution to a low rank SDP which leaves open the tantalizing possibility that the embeddings can be used to generate a dual certificate i.e a lower bound on a convex relaxation. First we define the primal problem Minimize: ⟨C, X⟩ (61) Subject to:⟨A i , X⟩ = b i ∀i ∈ [F] (62) X ⪰ 0 (63)Lemma B.4. Let OPT be the minimizer of the SDP equation 61. Then for any X ∈ R N ×N ⪰ 0 and any λ * ∈ R |F | , we define F λ * (X) to beF λ * ( X) := ⟨C, X⟩ + i∈F λ * i (⟨A i , X⟩ -b i )We require SDP to satisfy a bound on its trace T r(X) ≤ Y for some Y ∈ R + . Then the following is a lower bound on OPT.OP T ≥ F λ * ( X) -⟨∇F λ * ( X), X⟩ + λ min (∇F λ * ( X))YProof. Next we introduce lagrange multipliers λ ∈ R k and Q ⪰ 0 to form the lagrangianL(λ, Q, X) = ⟨C, X⟩ + i∈F λ i (⟨A i , X⟩ -b i ) -⟨Q, X⟩We lower bound the optimum of OPT defined to be the minimizer of equation 61EQUATIONWhere in the first inequality we replaced X ⪰ 0 with V V T which is a lower bound as every psd matrix admits a cholesky decomposition. In the second inequality we flipped the order of min and max, and in the final inequality we chose a specific set of dual variables λ * ∈ R |F | which lower bounds the maximization over dual variables. The key is to find a good setting for λ * .Next we establish that for any choice of λ * we can compute a lower bound on equation 65 as follows.Let F λ * (V V T ) be defined as the funciton in the RHS of equation 65.F λ * (V V T ) := ⟨C, X⟩ + i∈F λ * i (⟨A i , X⟩ -b i )Then equation 65 can be rewritten asOP T ≥ min V ∈R N ×N F λ * (V V T ) := ⟨C, X⟩ + i∈F λ * i (⟨A i , X⟩ -b i )Now let V * be the minimizer of equation 65 and let X * = V * (V * ) T . We have by convexity thatF λ * (X) -F λ * (X * ) ≤ ⟨∇F λ * (X), X -X * ⟩ = ⟨∇F λ * (X), X⟩ + ⟨-∇F λ * (X), X * ⟩ (66) ≤ ⟨∇F λ * (X), X⟩ -λ min (∇F λ * (X))Tr(X * ) (67) ≤ ⟨∇F λ * (X), X⟩ -λ min (∇F λ * (X))N(68) In the first inequality we apply the convexity of F λ * . In the second inequality we apply a standard inequality of frobenius inner product. In the last inequality we use the fact that Tr(X * ) = N . Rearranging we obtain for any X OP T ≥ F λ (X * ) ≥ F λ * (X) -⟨∇F λ * (X), X⟩ + λ min (∇F λ * (X))N (69) Therefore it suffices to upper bound the two terms above ⟨∇F λ * (X), X⟩ and λ min (∇F λ * (X)) which is an expression that holds for any X. Given the output embeddings Ṽ of OptGNN (or indeed any set of vectors Ṽ ) let X = Ṽ Ṽ T . Then we have concludedOP T ≥ F λ (X * ) ≥ F λ * ( X) -⟨∇F λ * ( X), X⟩ + λ min (∇F λ * ( X))N(70) as desired.Up to this point, every manipulation is formal proof. Subsequently we detail how to make an educated 'guess' of the dual variables λ * . Although any guess will produce a bound, it won't produce a tight bound. To be clear, solving for the optimal λ * would be the same as building an SDP solver which would bring us back into the expensive primal dual procedures that are involved in solving SDP's. We are designing quick and cheap ways to output a dual certificate that may be somewhat looser. Our scheme is simply to set λ * such that ∥∇F λ * ( X)∥ is minimized, ideally equal to zero. The intuition is that if ( X, λ * ) were a primal dual pair, then the lagrangian would have a derivative with respect to X evaluated at X would be equal to zero. Let H λ (V ) be defined as followsH λ * ( Ṽ ) := ⟨C, Ṽ Ṽ T ⟩ + i∈F λ * i (⟨A i , Ṽ Ṽ T ⟩ -b i )We know the gradient of H λ ( Ṽ )∇H λ ( Ṽ ) = 2(C + i∈F λ * i A i ) Ṽ = 2∇F λ ( Ṽ Ṽ T ) ṼTherefore it suffices to find a setting of λ * such that ∥∇F λ ( X) Ṽ ∥ is small, ideally zero. This would be a simple task, indeed a regression, if not for the unfortunate fact that OptGNN explicitly projects the vectors in Ṽ to be unit vectors. This creates numerical problems such that minimizing the norm of ∥∇F λ ( X) Ṽ ∥ does not produce a ∇F λ ( X) with a large minimum eigenvalue.To fix this issue, let R η,ρ (V ) denote the penalized lagrangian with quadratic penalties for constraints of the form ⟨A i , X⟩ = b i and linear penalty η i for constraints along the main diagonal of X of the form ⟨e i e T i , X⟩ = 1.R η,ρ (V ) := ⟨C, V V T ⟩ + i∈J ρ(⟨A i , V V T ⟩ -b i ) 2 + N i=1 η i (⟨e i e T i , V V T ⟩ -1)Taking the gradient of R η,ρ (V ) we obtain∇R η,ρ (V ) := 2CV + i∈J 2ρ(⟨A i , V V T ⟩ -b i )A i V + N i=1 2η i e i e T i VOur rule for setting dual variables δ i for i ∈ J isδ i := 2ρ(⟨A i , Ṽ Ṽ T ⟩ -b i )our rule for setting dual variables η j for j ∈ [N ] isη j := 1 2 ∥e T j (C + i∈F 2ρ(⟨A i , V V T ⟩ -b i )A i )V ∥Then our full set of dual variables λ * is simply the concatenation (δ, η). Writing out everything explicitly we obtain the following matrix for ∇F λ * ( Ṽ Ṽ T )∇F λ ( Ṽ Ṽ T ) = C + i∈F ρ(⟨A i , Ṽ Ṽ T ⟩ -b i )A i + j∈[N ] 1 2 ∥e T j (C + i∈F 2ρ(⟨A i , Ṽ Ṽ T ⟩ -b i )A i ) Ṽ ∥e i e T iPlugging this expression into Lemma B.4 the final bound we evaluate in our code is Note: The reason for splitting the set of dual variables is because the projection operator onto the unit ball is hard coded into the architecture of the lift network. Satisfying the constraint set via projection is different from the soft quadratic penalties on the remaining constraints and require separate handling.EQUATIONMax Cut Certificate For Max Cut our dual variables are particularly simple as there are no constraints ⟨A i , X⟩ = b i for b i ̸ = 0. The dual variables for Max Cut take on the form for all i ∈ [N ]λ * i = 1 2 ∥ j∈N (i) w ij v j ∥It's certainly possible to come up with tighter certification schemes which we leave to future work.Intuition: Near global optimality one step of the augmented method of lagrange multipliers ought to closely approximate the dual variables. After obtaining a guess for the penalized lagrange multipliers we estimate the lagrange multipliers for the norm constraint by approximating ∇R λ (V ) = 0.The alternative would have been to solve the linear system for all the lagrange multipliers at once but this runs into numerical issues and degeneracies explained below. We run out certification procedure which we name Opt-GNN-cert and compare it to the SDP certificate. Note, that mathematically we will always produce a larger (i.e inferior) dual certificate in comparison to the SDP because we are bounding the distance to the SDP optimum with error in the gradients and hessians of the output embeddings of OptGNN. Our advantage is in the speed of the procedure. Without having to go through a primal dual solver, the entire time of producing Opt-GNN-cert is in the time required to feedforward through Opt-GNN. In this case we train an Opt-GNN-MaxCut with 10 layers, on 1000 Erdos-Renyi graphs, with N = 100 nodes and edge density p = 0.1. We plot the Opt-GNN Max Cut value (an actual integer cut) on the x-axis and in the y-axis we plot the dual certificate value on the same graph where we compare the SDP certificate with the Opt-GNN-cert. See 2 for the N = 50 graphs and 3 for the N = 100 graphs.Note of course the dual certificate for any technique must be larger than the cut value outputted by Opt-GNN so the scatter plot must be above the x = y axis of the plot. We see as is mathematically necessary, the Opt-GNN-cert is not as tight as the SDP certificate but certainly competitive and more importantly it is arrived at dramatically faster. Without any attempt at optimizing the runtime, the Opt-GNN feedforward and certification takes no more than 0.02 seconds whereas the SDP takes 0.5 seconds on N = 100 node graphs.Theorem B.2 (perturbed-gd Jin et al. (2017) ). Let f be ℓ-smooth (that is, it's gradient is ℓ-Lipschitz) and have a γ-Lipschitz Hessian. There exists an absolute constant c max such that for any δ ∈ (0, 1), ϵ ≤ ℓ 2 γ , ∆ f ≥ f (X 0 ) -f * , and constant c ≤ c max , P GD(X 0 , ℓ, γ, ϵ, c, δ, ∆ f ) applied to the cost fucntion f outputs a (γ 2 , ϵ) SOSP with probability at least 1 -δ in 1.000 ± 0.002 IMDB-BIN b 1.000 ± 0.001 COLLAB b 0.999 ± 0.002 REDDIT-BIN c 1.000 ± 0.001 REDDIT-M-12K c 0.999 ± 0.002 REDDIT-M-5K c 0.999 ± 0.002O (f (X 0 ) -f * )Table 5 : Performance of OptGNN compared to Gurobi running under an 8 second time limit, expressed as a ratio. For each dataset, we take the ratio of the integral values achieved by OptGNN and Gurobi 8s on each of the graphs in the test slice. We present the average and standard deviation of these ratios. Here, higher is better. This table demonstrates that OptGNN achieves nearly the same performance, missing on average 1.1% of the cut value in the worst measured case.In Table 5 and Table 6 we supply the performance of OptGNN as a ratio against the integral value achieved by Gurobi running with a time limit of 8 seconds. These tables include the standard deviation in the ratio. We note that for Maximum Cut, OptGNN comes within 1.1% of the Gurobi 8s value, and for minimum Vertex Cover, OptGNN comes within 3.1%. 8 . 


Decision: This work introduces OptGNN, a novel graph neural network (GNN) architecture designed to tackle combinatorial optimization problems. By integrating semidefinite programming (SDP) and the Unique Games Conjecture (UGC), OptGNN can learn optimal approximation algorithms for Max Constraint Satisfaction Problems like Max-Cut, Min-Vertex-Cover, and Max-3-SAT. The authors demonstrate that polynomial-sized message-passing GNNs can replicate the performance of traditional SDP-based algorithms, producing high-quality approximate solutions. Empirical results show that OptGNN outperforms classical heuristics, solvers, and state-of-the-art neural models, making it a powerful tool for combinatorial optimization.

All the reviewers recognized the significance of this work and provided positive feedback. The paper is technically solid and merits presentation at NeurIPS.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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.
limitations: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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: 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.
limitations: limitations: Authors need to discuss the limitation of their work.
paper_summary: paper_summary: The papers propose graph neural architectures that can be used to capture optimal approximation algorithms for a large class of combinatorial optimization problems.
strength_weakness: strength_weakness: No significant weakness as such. 
Fig1. and Fig. 2 the visibility could be improved.
questions: questions: NA.
limitations: limitations: Yes, the authors has provided limitations section.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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?
limitations: 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.

Comments: title: Appreciate the authors' responses
minor remark
comment: I have read the authors response and I would like to keep my score.
Thank you for the detailed response. Please update the paper in the camera-ready version with these explanations. Your response meets my expectations, and I have increased my score to 7.
I believe my questions are well addressed by the response, and I am happy to increase my score to 7 accordingly.
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.