Are Graph Neural Networks Optimal Approximation Algorithms?
Authors: Morris Yau
Nikolaos Karalias
Eric Hanqing Lu
Jessica Xu
Stefanie Jegelka
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Combinatorial Optimization
Graph Neural Networks
Unsupervised Learning
Primary area: graph_neural_networks
TL;DR: We show that graph neural networks can efficiently implement a message passing algorithm that is optimal (under plausible assumptions) for a broad class of combinatorial problems and demonstrate that this leads to empirically powerful architectures.

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.

Are Graph Neural Networks Optimal Approximation Algorithms?
Morris Yau MIT CSAIL
Nikolaos Karalias MIT CSAIL stalence@mit.edd edu
Eric Lu Harvard University
morrisydmit.edd
ericlu010g harvard. edu
Jessica Xu
Stefanie Jegelka
Independent researcher formerly at MIT jessica, peng. xu@gmail... com
TUM* and MIT stef joffeemii eemit. edu
Abstract
In this work we design graph neural network architectures that capture optimal approximation algorithms for large class of combinatorial optimization prob- lems, using powerful algorithmic tools from semidefinite programming (SDP). Concretely, we prove that polynomial-sized message-passing GNN's can learn the most powerful polynomial time algorithms for Max Constraint Satisfaction Prob- lems 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 Max-Cut, Min Vern-Vertxx-CCe -oover, 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
Introduction
Combinatorial Optimization (CO) is the class of problems that optimize functions subject to con- straints 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, /mith et al. 2004 Du al. 2017) has engendered a long history of study rooted in the following simple insight. In practice CO instances are endowed with domain domain-specifer structure that can be exploited by special- ized algorithms (Hespe et al. 2020 Walteros & Buchanan, 2019; Ganesh Vardi (020). 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 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 this line of research forego optimality and focus parametrizing heuristics eLi al. 2018 Khalil et al.) 2017 Yoleu & Póczos 2019 Chen & Tian
2019) or by employing specialized models (Zhang al. [2023] Nazari et al. 2018 Toenshoff et al. 2019
Xu et al.) 2021 Min et al.) (022) and task-specific loss functions (Amizadeh et al. 2018
"CIT. MCML, MDSI
TEBC and CSAIL
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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. Striking the right balance between efficiency and optimality is quite challenging, which leads us to the central question of this paper:
Karalias & Loukas| 2020 Wang et al. 2022 Karalias et al. 2022 Sun et al.
Are there neural architectures for efficient combinatorial optimization that can learn to adapt to data distribution over instances yet capture algorithms with optimal worst-case approximation guarantees?
To answer this question, we build on the extensive literature approxi- mation algorithms and semidefinite programming (SDP) which has led to breakthrough results for NP-hard combinatorial problems, such as the Goemans- 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). For several problems, it is known that the Unique Games Con- jecture (UGC) is true, then the approx- imation guarantees obtained through SDP relaxations are indeed the best that can be achieved (Raghavendral 2008 Barak & Steurer (0114). The key insight of our work is that poly- nomial time message-passiing rithm (see Definition (i) approximates the solution of an SDP with the opti- mal integrality gap for the class of Maximum Constraint Satisfaction Problems (Max-CSP), assuming the UGC. This algorithm can be naturally parameterized to build graph neural network, which we call OptGNN.
0c,iv]
00,40
Miera ous haney
Traning:
QUEWN
Bo-nlC, G)]
CytC O)
Infernnce
QHEW
Figure 1: Schematic representation of OptGNN. During train- ing, OptGNN produces node embeddings using message passing updates on the graph G. These embeddings are used to compute the penalized objective (v G). OptGNN is trained by minimizing the average loss over the training set. At inference time, the fractional solutions (embeddings) for an input graph G produced by OptGNN are rounded us- ing randomized rounding.
algo-
Our contributions can be summarized as follows:
We construct polynomial- -imem message passing algorithm (see Definition G for solving the SDP of Raghavendra (2008) for the broad class of maximum constraint satisfaction problems (including Max-Cur Cut, Max-SAT, etc.), that is optimal barring the possibility of significant breakthroughs in the field of approximation algorithms.
We construct graph neural network architecture which we call OptGNN, to capture this bassaae-passing algorithm. We show that OptGNN is PAC-learnable with polynomial sample complexity.
We describe how to generate optimality certificates from the learned representations of OpIGNN i.e., provable bounds on the optimal solution.
Empirically, OpiGNN is simple to implement (see pseudocode in Appendix 5) and we show that achieves competitive results on landmark CO problems and several datasets against classical heuristics, solvers and state-of-tt ofte--f-theearrr art neural baselines Furthermore, provide out-of- nutoof-distribution (OOD) evaluations and ablation studies for OpIGNN that further validate our parametrized message- passing approach.
Coode is available

---

2 Background and Related Work
Optimal Approximation Algorithmss Proving that an algorithm achieves the best approximation guarantee for NP-hard problems is an enormous scientific challenge as it requires ruling out that better algorithms exist (i.e., hardness result). The Unique Games Conjecture (UGC) (Khot (002) is striking development in the theory of approximation algorithms because it addresses this obstacle. If true, it implies approximation hardness results for a large number of hard combinatorial problems that match the approximation guarantees of the best-known algorithms (Raghavendra & Steurer 2009b to as Raghavendra et al. 2012). For that reason, those algorithms are also sometimes referred More importantly, the UGC implies that for all Max-CSPs there is a general
UGC-optimal algorithm based on semidefinite programming (Raghavendra) 2008). For a complete exposition on the topic of UGC and approximation algorithms, we refer the reader to Barak & Steurer (2014).
Neural approximation algorithms and their limitations. There has been important progress in characterizing the combinatorial capabilities of modern deep learning architectures, including bounds on the approximation guarantees achievable by GNNs on bounded degree graphs (Sato et al., 2019. 2021) and conditional impossibility results for solving classic combinatorial problems such as Max- Dax-Independent-SS and Min- Min-Spanning-TTee
(Loukas 2019). It has been shown that GNN can implement a distributed local algorithm that straightforwwrdly obtains a a2-apppoximttion for Max- SAT (Liu et al. (021). which is also achievable through simple randomized algorithm (Johnson 1973). Recent work proves there are barriers to the approximation power of GNNs for combinatorial problems including Max-Cut and Min-Vertex- Vertex-Cover (Gamarnik 2023) for constant depth GNNs. Other approaches to obtaining approximation guarantees propose avoiding the dependence of the model on the size of the instance with weriid-and-conquse strategy; the problem is subdivided into
smaller problems which are then solved with a neural network (McCarty et al.) 2021 Kahng et al., 2023).
Convex Relaxations and Machine Learning. Convex relaxations are crucial in the design of approximation algorithms. In this work, we show how SDP-based approximation algorithms can be incorporated into the architecture of neural networks. We draw inspiration from the algorithms that are used for solving low-rank SDPs (Burer & Monteiro [003 Wang al. [0177: [Wang& & Kolter 2019 Boumal et al. 2020). Beyond approximation algorithms, there is work on designing diffcrentiable Max-SAT solvers via SDPs facilitate symbolic reasoning in neural architectures (Wang al. 2019). This approach uses a fixed algorithm for solving a novel SDP relaxation for Max-SÄT, and aims to learn the structure of the SAT instance. In case, the instance is given, but algorithm is learnable, and we seek to predict the solution. SDPs have found numerous applications in machine learning including neural network verification (Brown et al. 2022), differentiable learning with discrete functions (Karalias et al., 2022), kernel methods (Rudi et al. 2020 Jethava et al. (0133) and quantum information tasks (Kriváchy et al. 202I). Convex relaxation are also instrumental in integer programming where branch-and-boum
tree search is guaranteed to terminate with optimal integral solutions Mixed Integer Linear Programs (MILP). Proposals for incorporating neural networks into the MILP pipeline include providing "warm start" (Benidis et al. (203)) to the solver, learning
branching heuristics (Gasse et al. 2019 Nair et al.) 2020 Gupta al.) [020 Paulus et al. 2022). and
learning cutting plane protocols (Paulus et al. [2022) A recent line of work studies the capabilities of
neural networks to solve linear programs (Chen et al. 2022, Qian et al. 2023). It is shown that GNNs
can represent LP solvers, which may in turn explain the success of learning branching heuristics QQia et al. 2023).
similar line of work, neural nets are used to learn branching heuristics for CDCL SAT vors (Selsam & Björner 2019 Kurin et al. 2020 Wang et al.) 2021). Finally, convex optimization has also found applications (Numeroso et al. 2023 in the neural algorithmic reasoning
paradigm (Veličković al.) 2022) where neural networks trained to solve problems by learning to
emulate discrete algorithms in higher dimensional spaces.
Learning frameworks for CO. A common approach to neural CO is to use supervision either in the
form of execution traces of expert algorithms or labeled solutions (Li et al. 20188] Selsam et al. 2018
Prates et al. 2019: Vinyals et al. 2015 Doshi et al., 2019 2020 Gasse et al. 2019 Ibarz et al. 2022
Georgiev et al. 2023). Obtaining labels for combinatorial problems can be computationally costly which has led to the development of neural network pipelines that can be trained without access to
labels or partial solutions. This includes approaches based on Reinforcement Learning (Ahn et al.
2020 Böther et al. 2022, Barrett al. 2020 2022
Bello et al. 2016 Khalil et al. 2017 Yolcu &

---

Póczos 2019
Chen & Tian 2019), and other self supervised methods (Brusca et al., 2023; Karalias
al. 2022] Karalias & Loukas 2020 Tönshoff et al. 2022; Schuetz al., 2022a b Amizadeh et
2019; Dai et al. 2020] Sun et al. 2022 Wang et al. 2022 Amizadeh et al., 2018 Gaile et al. (022).
Our work falls into the latter category since only problem instance sufficient for training and
supervision signals are not required. For a complete overview of the field, we refer the reader to the
relevant survey papers (Cappart et al. 2023 Bengio et al. 2021).
Optimal Approximation Algorithms with Neural Networks
We begin by showing that solving the Max-Cur problem using vector (low-rank SDP) relaxation and simple projected gradient descent scheme amounts to executing a message-passing algorithm on the input graph. We then generalize this insight to the entire class of Max-CSPs. We reformulate the UGC-optimal SDP for Max-CSP in SDP Our main Theorem 3.1 exhibits a message passing algorithm (Algorithm T for solving T We then capture Algorithm I via a message passing GNN with learnable weights (see Definition G for definition of Message Passing GNN). Thus, by construction OpiGNN captures algorithms with UGC-optimal approximation guarantees for Max- CSP. Furthermore, we prove that OptGNN is efficiently PAC-learnable (see Lemma 3.1) as step towards explaining its empirical performance.
3.1 Solving Combinatorial Optimization Problems with Message Passing
In the Max-Cut problem, we are given a graph G = (V, E) with N vertices and edges E. The goal is to divide the vertices into two sets that maximize the number of edges going between them. This corresponds to the quadratic integer program
Σ (LE)
(1-1,2,) subject to: of =1 Vi [N).
max 21 22
The global optimum of the integer program the Max-Cut. Noting that discrete variables are not amenable to the tools of continuous optimization, a standard technique is to 'lift' the quadratic integer problem: replace the integer variables z; with vectors v, E R"' and constrain e; to on the unit sphere
min PE.
1 2 (EJ))E
Σ
(wi, ()))
U2)) subject to: ||0||| =1 Vi E [N] E...".
(1)
This nonconvex relaxation of the problem admits an efficient algorithm Burer & Monteiro 2003).
Furthermore, all local minima are approximately global minima (Ge al. 2016) and variations of
stochastic gradient descent converge to its optimum (Bhojanapalli et al. 2011 Jin et al. 2017) under variety of smoothness and compactness assumptions. Specifically, for large enough (Boumal et al. 2020: O' O'Carroll et al. 2022), simple algorithms such as block coordinate descent (Erdogdu al. 2019) can find an approximate global optimum of the objective. Projected gradient descent is natural approach for solving the minimization problem in equation] I
In iteration t (for T iterations),
update vector v; as
of (1 JEE(())) 05).
NORMALIZE
(2)
where NORMALIZE enforces unit Fuclidean norm, 1) R is adjustable step size, and N(i) the neighborhood of node i. The gradient updates to the vectors are local, each vector is updated by aggregating information from its neighboring vectors (i.e., it is message-passing algorithm).
OptGNN for Max-Cut. Our main contribution 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 2 Let M1, M2,, ..., My E Brx2r be set of T learnable matrices corresponding to T layers of neural network. Then for layer and embedding u, we define
a GNN update
(Mr. (EEsENO 1)
of
++1
NORMALIZE
(3)

---

More generally, we can write the dynamics of+1 := MORMALIZE(M,AAGGiJ, f feN())) where AGG is function of the node embedding and its neighboring embeddings. We will present message passing algorithm[ [ that generalizes the dynamics of to the entire class of Max-CSPs (see example derivations in Appendix [A and Appendix [B), which provably converges in polynomial iterations for reformulation of the canonical SDP relaxation of Raghavendra (2008) (see S Parametrizing this general message-passing algorithm will lead to the definition of OpiGNN (see Definition 3.3
3.2 Message Passing for Max-CSPs
Given 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 A = (V. P.
consists of set of N variables V := {ar J JE[N] each taking values in an alphabet [g] and a set of predicates P
=Cy where each predicate is a payoff function over variables X; { Lig. ..., ). Here we refer to k as the arity of the Max-k-CSP. We adopt the normalization that each predicate P= returns outputs in [0, 1]. We index each predicate Pz by its domain 2. The goal of Max-k-CSP is to maximize the payoff of the predicates.
max OPT(A) (D1 (N)
E P.((2), P.EP
|P]
where we normalize by the number of constraints so that the total payoff is in [0, 1]. Therefore we can unanbiguously define e-approximate assignment an assignment achieving a payoff of OPT c.
Since our result depends on a message-passingg algorithm, we will need to define an appropriate graph structure over which messages will be propagated. To that end, will leverage the constraint graph of the CSP instance: Given a Max-k-CSP instance A = (V, P..) .. a constraint graph GA = (V. E) is comprised of vertices V {vo.<)
} for every subset of variables & C = for every predicate Pa E P and every assignment& Ç E [q] |=| the variables in z. The edges E are between any pair of vectors Vo.cc and Vor,s" ."' such that the variables in & and ø' appear in a predicate together. For instance, for SAT clause (x) x2) A æ1 A 23 there are four nodes U1, V12 03 and vi with a complete graph between {U1, V12, } and e3 an isolated node.
Let SDP(A) be the optimal value of the SDP 1 on instance A. The approximation ratio for the OPT(A)
Max-k-CSP problem achieved by the SDP is min k CSP SDP(A) where the minimization taken over all instances A with arity k. There is no polynomial time algorithm that can achieve a larger approximation ratio assuming the truth of the UGC Raghavendra (2008). We construct our message passing algorithm as follows. First we introduce the definition of the vector form SDP and its associated quadratically penalized Lagrangian.
Definition (Quadratically Penalized Lagrangian). Any standard form SDP A can be expressed as the following vector form SDP for some matrix V = [01. U2...., uN] E R NNN
min X
(C,V
subject to: (A,,VTV) = by Vi E
(5)
VERMXN
For any SDP in vector form we define the p quadratically penalized Lagrangian to be ((Ar, V'V, - -.)².
Cx(V) = (C) + P Σ
(6)
IEF
We show that gradient descent on this Lagrangian (V) for the Max-CSP SDP takes the form of a message-passing algorithm the constraint graph that can provably converge to approximate global optimum for the SDP (see algorithm DT. We see that gradient descent on L, takes the form of simultaneous message passing update on the constraint graph. See equation 60 algorithm 3 for analytic form of the Max- Max-CSP message passing update. See appendix A and I Boo analytic form of Lii-Veetex--owee and Max-3-SAT message passing updates. Our main theorem is then following.
Theorem 3.1. [Iformaa]] Given a Max-k-CSP instance A represented in space & = O(PPlg*), there a message passing Algorithm 3 on constraint gruph G with a per iteration update time of (($) that computes in D(e-1h1) iterations an e-appreximate solution (solution satisfies constraints to error achieving objective value within of optimum) to SDP For the formal theorem and proof Theorem C.1
5

---

3.3 OpiGNN for Max-CSP
Next we define OptGNN for Max-CSP. See and B for OptGNN for Vertex Cover and 3-SAT.
Definition (OpIGNN for Max-CSP). Let A be Max-CSS instance on constraint graph GA with N nodes. Let U be an input matrix of dimension r x N for N nodes with embedding dimension r. Let
Lp be the penalized lagrangian loss defined in equation 6 associated with the Max-CSP instance A.
Let M be the OpiGNN weights which are set of matrices M == MM,,,MM... ..., Mr) E 1 Let
LAYERM, M. : RRXN
+ RrxN be the function M. (U) = ((GG((U) where
AGG TX 2 is the aggregation function AGG(U) == [U, VL,D() We define
OpiGNN (MAA) RRXN + R to be the function
OpIGNN (M,A)(U) (U) = Cp o LAYERM, O... o cLAYER (U).
The per iteration update time of OpIGNN is O where w is the matrix multiplication exponent. We update the parameters of OpIGNN by inputting the output of the final layer LAYERM, into the Lagrangian Cp and backpropagate its derivatives. We emphasize the data is the instance A and not the collection of vectors U which can be chosen entirely at random. The form of the gradient V C. is a message passing algorithm over the nodes of the constraint graph GA. Therefore, OptGNN is a message passing GNN over GA (see Definition G). This point is of practical importance it is what informs out implementation of the OptGNN architecture. We then arrive at the following corollary.
Corollary (Informal). Given a Max k-CSP instance A represented in space = O(IPla)), there is an OptGNN (a,.A) with T = (()=1(1) layers, and embeddings of dimension & such that there is an instantiation of learnable parameters M = {Mr}er( that outputs set of vectors V satisfying the constraints of SDP and approximating its optimum to error e. See formal statement 2
Moving on from our result on representing approximation algorithms, we ask whether OptGNN is learnable. That is to say, does OpiGNN approximate the value of [DP when given a polynomial amount of data? We provide a perturbation analysis to establish the polynomial sample complexity of PAC-learning OptGNN. The key idea is to bound the smoothness of the polynomial circuit AGG used in the OptGNN layer which is a cubic polynomial analogous to linear attention. We state the informal version below. For the formal version see Lemma
Lemma 3.1 (PAC learning). Let be a dataset of Max-k-CSP instances over an alphabet of size [g] with each instance represented in space o. Here the dataset D == A1, A2. .... Ap....rp ~ D is drawn i.i.d from distribution over instances D. Let M be a set of parameters M = MM, M..... Mr} in
parameter space O Then for T = Oc)= for I = O(c $66 1og"((--7)) ()- let M be the empirical loss minimizing weights for arbitrary choice of initial embeddings U in a bounded norm ball. Then we have that OptGNN is (T, e, 5) -PCC learnable. That is to say the empirical loss minimizer EMP(() within from the distributional loss with probability greater than Ō:
Pr
EMP Q)
EE-D [OPIGNN (M (M))( Se 2 1-
We note that this style of perturbation analysis is akin to the VC theory on neural networks adapted to our unsupervised setting. Although it's insufficient explain the empirical success of backprop, we believe our analysis sheds light on how architectures that capture gradient iterations can successfully generalize.
OptGNN in practice. Figure I summarizes the OpiGNN pipeline for solving CO problems. OptGNN
computes node embeddings V E 1 as per equation 7 which feeds into the loss L.. For pseudocode, please refer to the appendix (Max-Cut: algorithm 4 and general SDPs: algorithm (5). We use Adam (Kingma & Ba (2144) to update the parameter matrices M. Given a training distribution D. the network is trained in a completely unsupervised fashion by minimizing EG~D[[(v G'] with standard automatic differentiation package like Py (Paszke et al. 2019). A practical benefit of our approach is that users do not need to reimplement the network to handle each new problem. Users need only implement the appropriate loss, and our implementation uses automatic differentiation to compute the messages in the forward pass. At inference time, the output embeddings must be rounded to discrete solution. To do this, we select random hyperplane vector y E R", and for each node with embedding vector uy we calculate its discrete assignment x; E (11,1] 1} as x; = sign(v, y). We use multiple hyperplanes and pick the best resulting solution.

---

Obtaining neural certificates. We construct dual certificates of optimal- ity from the output embeddings of OpiGNN. The certificates provide a bound on the optimal solution of the SDP. The key idea is to estimate the dual variables of SDP [ Since we use a quadratic penalty for con- straints, the natural dual estimate is one step of the augmented method of Lagrange multipliers on the SDP solu- tion which can be obtained straightfor- wardly from the primal problem vari- ables V. We then analytically bound the error in satisfying the KKT condi- tions of SDP [ See [C. for deriva- tions and extended discussion, and Figure 3 for an experimental demon- stration.
SDP 1 SDP for Max-k-CSP (Equivalent to UGC-optimal)
SDP Vector Formulation A = (V,P, (0, Multilinear formulation of objective.
min Σ
Wx
Σ
Ug))
C(s)
9: oggCn((lls")==
subject to: ||ual1 =1 Vs S VP EP
(Ug, [gy) = Uw)
v((g.9') = ((', s.t
g S(P)), P
(10)
Notation: For a Max-CSP instance A. there a canoni- cal boolean polynomial representing the objective denoted P(21,.....N) = Ep. where Ps is the canonical polynomial associated to the predicate over the variables z. Con- versely, for each predicate variables in the domain of P. We write out the polynomial P: with coefficients {w=)ac= as follows P3 = E.c, We lhe zi.
E P we let S(P) denote the
Adaptation to Data vs. Theoreti- cal Result. The theory result con- cerns worst case optimality where the embedding dimension is large as
We introduce the set notation ((A, B) = A B/A B and
use C(s) to denote the size the set {g. g C s: C(. g¹) = s).
N. In practice we deploy OptGNN with varying choices of the embed- ding dimension to obtain the best per- formance. For low dimensional em- beddings, the corresponding low rank SDP objective is NP-hard to optimize. As such, training OptGNN is like training any other GNN for CO in that the weights adapt to the data. This is highlighted in our experiments where OptGNN generally outperforms SDP solvers.
Algorithm 1 Message Passing for Max-CSP (informal).
Input: Max-CSP Instance A with constraint graph GA v <- Uniform(S"-))
(Initialization on the unit sphere)
for f = 1, 1,2, .......77 T do
for v E v' [message passing on the constraint graph) do
aVol'',e" Ouf
oft
c- ro -7
Σ
end for end for
Output: vector solution v' for SDP
Notation: (V) can be written as the sum of functions
4 Experiments
across pairs edges in the constraint graph GA i. (V)
Σiey Ee,e'EEi)) (,(e,e)) where E() is the set of edges in- volving vertex and denotes the vector embeddings of its two corresponding vertices. For analytic form of the messages see algorithm 3
First, we provide comprehensive experimental evaluation of the Opt- GNN pipeline on several problems and datasets and compare it against heuristics, solvers, and neural baselines. We then describe a model ablation study, an out-of- distribution performance (OOD) study, and an experiment with our neural certification scheme. We empirically test the performance of OptGNN on NP-Hard combinatorial optimization problems: Maximum Cut, Minimum Vertex Cover, and Maximum 3-SAT. We obtain results for several datasets and compare against greedy algorithms, local search, state-of-the-an MIP solver (Gurobi), and various neural basclines. For Max-3-SAT and Min- Vertex- we adopt the quadratically penalized Lagrangian loss of their respective SDP relaxations. For details of the setup see Appendix D
experiments. We evaluated OpIGNN on forced RB instances, which are hard vertex cover instances from the RB random CSP model that contain hidden optimal solutions (Xu al. (007). We use two distributions specified in prior work (Wang & Li 2023). RB200 and RB500. The results are in Figure 2b which also includes the performance of several neural and classical baselines as reported in (Wang & Li| 2023 Brusea et al. 2023). OpiGNN consistently outperforms state-of-the-art unsupervised baselines on this task and able to match the performance of Gurobi with 0.5s time limit.
Min-Vertex-Cun
Max-3-SAT experiment and ablation. The purpose of this experiment is twofold: to demonstrate the
7

---

Table 1: Performance of OptGNN, Greedy, and Gurobi 0.1s, 1s, and 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 OpiGNN.
Dataset
OpiGNN
Greedy
Gurobi 0.1s
Gurobi 1.0s
BA* (400,500)
2197.99 (66)
1255.22
2208. 11
2208.11
ER* (400,500)
16387.46 (225)
8622.34
16476.72
16491.60
HK* (400,500)
2159.90 (61)
1230.98
2169.46
2169.46
WC (400,500)
1166.47 (78)
690.19
1173.45
1175.97
ENZYMES
81.37 (14)
48.53
81.45
81.45
COLLAB
2622.41 (22)
1345.70
2624.32
2624.57
REDDIT-M-I2K'
568.00 (89)
358.40
567.71
568.91
REDDIT-M-5K
786.09 (133)
495.02
785.44
787.48
Table 2: Average number of unsatisfied clauses for Max-3-SAT on random instances with N 100 variables and clause ratios 4.00, 4.15, 4.30. Standard deviation of the ratio over the test set is reported in superscript. In parentheses, we report the average time per instance on the test set in seconds.
Dataset
r 4.00
r 4.15
T= 4.30
FrdōsGNN
5,46*191
(0.01)
6.14 (0.01)
6.79#2.05 (0.01)
Walksat (100 restarts)
0.14 (0.12)
0.36 (0.25)
0.68 (0.40)
Walksat restart)
0.94 (0.01)
1.46 (0.01)
1.97
(0.01)
Survey Propagation
+ (0.001)
3.87
(0.001)
3.94
#099 (0.001)
OptGNN
4.46 (0.01)
5,15 (0.01)
5,84 (0.01)
Autograd SDP
6,85#2335
(6.80)
7.52
(6.75)
8.32#2.00 (6.77)
Low-Rank SDP (Wang& & Kolter 2019
12.38=1006 (0.66)
13.32
(0.67)
14.27 (0.69)
viability of OptGNN the Max-3-SAT problem and examine the role of overparameterization in OPIGNN. We generate 3-SAT formulae on the fly with 100 variables and a random number of clauses in the [400, 430) interval, and train OptGNN for 100,000 iterations. We then test instances with 100 variables and ( (400, 415, 430) clauses. The results are Table 2| We compare with ATT a classic local search algorithm for SAT, a low-rank SDP solver (Wang al. 2019), Survey Propagation (Braunstein et al. (2005). and ErdosGNN Karalias & Loukas (2020). a neural baseline trained in the same way. We also compare with simple baseline reported as "Autograd" that directly employs gradient descent on the penalized Lagrangian using the autograd functionality of Pytorch. For details see D.2 OptGNN is able outperform ErdōsGNN consistently and improves significantly over Autograd, which supports the overparameterized message passing of OptGNN. OpiGNN performs better than the low-rank SDP solver, though does not beat WalkSAT//Srvey Prop. It is worth noting that the performance of OptGNN could likely be further improved without significant computational cost by applying a local search post-processing step to its solutions but we did not pursue this further in order to emphasize the simplicity of our approach.
Max-Cut experiments. Table presents a comparison between OptGNN, greedy algorithm, and Gurobi for Max-Cut. OpIGNN clearly outperforms greedy on all datasets and is competitive with Gurobi when Gurobi is restricted to similar runtime. For results on more datasets see ceelsubsettion D.3 Following the experimental setup of ANYCSP Tönshoff Tonshoof et al. (2022). we also tested OptGNN on the GSET benchmark instances (Benlic & Hao (013)) We trained an OptGNN for 20k iterations on generated Erdós-Remp graphs In.p for n E [400, 500) and p 0.15. |Figure 2a shows the results. We have included an additional low-rank SDP baseline to the results, while the rest of the baselines are reproduced as they appear in the original ANYCSP paper. These include state-of-the-an neural baselines, the Goemans- Williamson algorithm, and a greedy heuristic. We can see that OptGNN outperforms the SDP algorithms and the greedy algorithm, while also being competitive with the
8

---

= 800
OptoNN
1-0000
N 2000 shown
= 3000 (NA shown as 0)
ANYCSP
ECORD
ECO-DON
SDP
Greedy
100
200
500
600
700
800
Mean deviation from known optimal (number edges; lower better)
(a) Comparison GSET Max-Cut instances against of art neural baselines. Numbers reported the (over the graphs the test set) deviations from the best-known Max-Cut values, reported in Benlic & Hao (2013).
RE200
OptGNN
Gurobi (56)
Gurobi (1s)
Gurobi (0.5 5s)
Greedy MVC
RUN-CSP
Mcta.GN
ErdösGNN
CMP
1.00
1.02
1.04
1.06
1.08
1.10
1.12
1.14
Approximation (values closer better)
(b) Average approximation ratio and standard deviation over the test set for vertex covers on forced RB instances. A ratio of 1.000 represents finding the minimum vertex cover.
Figure Results for Max-Cur and Minimum Vertex Cover.
neural baselines. However, OptGNN does not manage to outperform ANYCSP, which to the best of knowledge achieves the current offte-of-thearr results for neural networks.
Out distribution generalization. We OpIGNN's ability perform on data distributions (for the same optimization problem) that it's not trained on. The results can be seen in table and subsection D.6 The results show that the model is capable of performing well even on datasets has not been trained on.

---

Model ablation. We train modern GNN archi- tectures from the literature with the same loss function and compare them against OpiGNN. Please see Appendix D.4 for more details and results on multiple datasets for two different problems, Overall, OpIGNN is the best perform- ing model on both problems across all datasets.
Certificato Quality: SDP vs. Opt Bapt-GNNi-o cort N-160
Opt-CAN-cert SDPicert
680
640
Experimental demonstration of neural cer- tificates. Next, we provide a simple experi- mental 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. fig- ure shows an example. For 100 node graphs with 1000 edges certificates deviate from the SDP certificate by about 20 nodes but are dra- matically faster to produce. The runtime is dom- OptGNN which the SDP solve time which 0.5 seconds on evxpy. Sce[C.T]orr extensive discussion and additional results.
380
500
Opt-GNN
Figure 3: Experimental comparison of SDP versus OptGNN Dual Certificates on random graphs of 100 nodes for the Max Cut problem. Our OptGNN certificates track closely with the SDP certificates while taking considerably less time to generate.
inated by the feedforward is 0.02 seconds
5
Conclusion
We presented OptGNN, GNN that can capture provably optimal message passing algorithms for 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,
observed that the OpIGNN architecture achieves strong performance on wide range of datasets and on multiple problems. OptGNN opens up several directions for future exploration, such as the design of powerful rounding procedures that can secure approximation guarantees, the construction of neural certificates that improve upon the ones we described in Appendix C.T. and design of neural SDP-based branch and bound solvers.
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: PS00PT_217999) Stefanie Jegelka and Nikolaos Karalias acknowledge support from NSF AI Institute TILOS (NSF CCF-21 12665.. Stefanie Jegelka acknowledges support from NSF award 21 2134108.
10

---

References
Sungsoo Ahn, Younggyo Sco, and Jinwoo Shin. Learning what to defer for maximum independent sets. In International Conference on Machine Learning, pp. 134-144. PMLR, 2020.
Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. Learning to solve circuit-sat: An unsupervised differentiable approach. 2018.
Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. Pdp: A general neural framework for learning constraint satisfaction solvers, 2019.
Boaz Barak and David Steurer. Sum-of-squares proofs and the quest toward optimal algorithms. arXiv preprint arXiv: 1404.223, 2014.
Thomas Barrett, William Clements, Jakob Foerster, and Alex Lvovsky. Exploratory combinatorial optimization with reinforcement learning. In Proceedings of the AAAI conference artificial intelligence, volume 34, pp. 3243-3250, 2020.
Thomas D Barrett, Christopher WF Parsonson, and Alexandre Laterre. Learning to solve combi- natorial graph partitioning problems via efficient exploration. arXiv preprint arXiv:2205.41005, 2022.
Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint 1rXiv:1611.0994 2016.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' hohorizon. European Journal of Operational Research, 290(2):405-4211 2021.
Konstantinos Benidis, Ugo Rosolia, Syama Rangapuram, George Iosifidis, and Georgios Paschos. Solving recurrent mips with semi-supervised graph neural networks. arXiv preprint arXiv:2302.11992, 2023.
Una Benlic and Jin-Kao Hao. Breakout local search for the max-cutproblem. Engineering Applica- fions of Artificial Intelligence, 26(3): 162-1173, 2013.
Srinadh Bhojanapalli, Nicolas Boumal, Prateek Jain, and Praneeth Netrapalli. Smoothed analysis for low-rank solutions semidefinite programs in quadratic penalty form, 2018
Maximilian Böther, Otto Kißig, Martin Taraz, Sarel Cohen, Karen Seidel, and Tobias Friedrich. What's wrong with deep learning in tree search for combinatorial optimization. arXiv preprint arXiv:2201.10494 2022.
Nicolas Boumal, Vladislav Voroninski, and Afonso Bandeira. Deterministic guarantees for burer- monteiro factorizations of smooth semidefinite programs. Communications on Pure and Applied Mathematics, 73())581-6088 2020.
Alfredo Braunstein, Mare Mézard, and Riccardo Zecchina. Survey propagation: An algorithm for satisfiability, Random Structures & Algorithmss 27(2):201-226, 2005.
Robin A Brown, Edward Schmerling, Navid Azizan, and Marco Pavone. A unified view of sdp-based neural network verification through completely positive programming. International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2022.
Lorenzo Brusca, Lars CPM Quaedvlieg, Stratis Skoulakis, Grigorios G Chrysos, and Volkan Cevher. Maximum independent set: Self-training through dynamic programming. In Advances in neural information processing systems (NeurIPS), 2023.
Samuel Burer and Renato Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming, Series B, 95:329-357, 02 2003. doi: 10.10077//00077-002-32---2
Quentin Cappart, Emmanuel Goutierre, David Bergman, and Louis-Martin Rousseau. Improving optimization bounds using machine learning: decision diagrams meet deep reinforcement learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 1443-1451, 2019.
11

---

Quentin Cappart, Didier Chételat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Velickovic. Combinatorial optimization and reasoning with graph neural networks. J. Mach. Learn. Res., 24:130-1, 2023.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. In Advances Neural Information Processing Systems, pp. 6278-6777888 02788,6692928 2019.
Ziang Chen, Jialin Liu, Xinshang Wang, Jianfeng Lu, and Wotao Yin. On representing linear programs by graph neural networks. arXiv preprint arXiv:2209. /2288, 2022.
Hanjun Dai, Xinshi Chen, Yu Li, Xin Gao, and Le Song. A framework for differentiable discovery of graph algorithms. 2020.
Jiaoman Du, Xiang Li, Lean Yu, Ralescu Dan, and Jiandong Zhou, Multi-depot vehicle routing problem for hazardous materials transportation: A fuzzy bilevel programming. Information sciences, 399:201-2188 2017.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.0090 2020.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. arXiv preprint arXiv:2110.07875, 2021.
Murat A. Erdogdu, Asuman Ozdaglar, Pablo A. Parrilo, and Nuri Denizcan Vanli. Convergence rate of block-coordinate maximization burer-montein method for solving large sdps, 2019.
Eliza Gaile, Andis Draguns, Emils Ozolinš, and Kärlis Freivalds. Unsupervised training for neural tsp solver. In International Conference on Learning and Intelligent Optimization, pp. 334
Springer, 2022.
David Gamarnik. Barriers for the performance of graph neural networks (gnn) in discrete random structures. Proceedings of the National Academy of Sciences, 120(40):e2314092120 2023.
Vijay Ganesh and Moshe Y Vardi. On the unreasonable effectiveness of sat solvers. Beyond the Worst-Case Analysis of Algorithms, pp. 547-566, 2020.
Eleanor Gardiner, Peter Willett, and Peter Artymiuk. Graph-theoretic techniques for macro- molecular docking. Journal of Chemicul Information and Computer Sciences, 40(2):273-279, 2000.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combina- torial optimization with graph convolutional neural networks, arXiv preprint 2019.
Rong Ge, Jason D. Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. CORR, abs/ /ts/16605.02222 2016. URL http:://rxxii..orr/// httg:/bs/1100
wwtp:///ow.aaba.ooooooooo 0tee//60500770 07272
Dobrik Georgiev, Danilo Numeroso, Davide Bacciu, and Pietro Liò. Neural algorithmic reasoning for combinatorial optimisation. arXiv preprint arXiv:2306. 06064, 2023.
Michel Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6): 1115-1145, 1995.
Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1:169-197, 1981.
Prateek Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigonda, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. Advances in neural information processing systems, 33: 18087-18097, 2020.
Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. Exploring network structure, dynamics, and function using networkx. Gaël Varoquaux, Travis Vaught, and Jarrod Millman (eds.), Proceedings of the 7th Python in Science Conference, pp. 11 - 15, Pasadena, CA USA, 2008.
12

---

Demian Hespe, Sebastian Lamm, Christian Schulz, and Darren Strash. Wegotyoueovered: The winning solver from the pace 2019 challenge, vertex cover track. In 2020 Proceedings of the SIAM Workshop Combinatorial Scientific Computing, pp. 1-11. SIAM, 2020.
Borja Ibarz, Vitaly Kurin, George Papamakarios, Kyriacos Nikiforou, Mehdi Bennani, Róbert Csordás, Andrew Joseph Dudzik, Matko Bošnjak, Alex Vitvitskyi, Yulia Rubanova, et al. A generalist neural algorithmic learner. In Learning on Graphs Conference, pp. 2-1, PMLR, 2022.
Vinay Jethava, Anders Martinsson, Chiranjib Bhattacharyya, and Devdatt Dubhashi. Lovász 0 function, svms and finding dense subgraphs. The Journal of Machine Learning Research, 14(1): 3495-3536, 2013.
Chi Jin, Rong Ge, Pranceth Netrapalli, Sham M. Kakade, and Michael I. Jordan. How to escape saddle points efficiently, 2017.
David S Johnson. Approximation algorithms for combinatorial problems. In Proceedings of the fifth anmual ACM symposium Theory of computing, pp. 38-49, 1973.
Chaitanya Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.012: 2019.
Chaitanya K Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning tsp requires rethinking generalization. arXiv preprint S4Ki::0006.005544 2020.
Andrew В Kahng, Robert R Nerem, Yusu Wang, and Chien-Y Yi Yang. Nn-steiner: A mixed neural-algorihmmic approach for the rectilinear steiner minimum tree problem. arXiv preprint arXiv:2312.10589 2023.
Nikolaos Karalias. Probabilistic methods for neural combinatorial optimization. Technical report, EPPL, 2023.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. arXiv preprint arXiv:2006. 10643, 2020.
Nikolaos Karalias, Joshua Robinson, Andreas Loukas, and Stefanic Jegelka. Neural set function
extensions: Learning with discrete functions in high dimensions. Advances in Neural Information Processing Systems, 15:1533115 2022.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, pp. 6348 6358, 2017.
Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM symposium Theory of computing, pp. 767-775, 2002.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXiv:1412.6980 2014.
Tamás Kriváchy, Yu Cai, Joseph Bowles, Daniel Cavalcanti, and Nicolas Brunner. High-speed batch processing of semidefinite programs with feedforward neural networks. New Journal of Physics, 23(10):103034, 2021.
Vitaly Kurin, Saad Godil, Shimon Whiteson, and Bryan Catanzaro. Can q-learning with graph networks learn generalizable branching heuristic for sat solver? Advances in Neural Information Processing Systems, 33:9608 13:9608-9621. 2020.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint arXiv: 1.05993, 2015.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Advances in Neural Information Processing Systems, pp- 539-548, 2018.
13

---

Minghao Liu, Fuqi Jia, Pei Huang, Fan Zhang, Yuchen Sun, Shaowei Cai, Feifei Ma, and Jian Zhang. Can graph neural networks learn solve maxsat problem? arXiv preprint arXiv:2111.07568. 2021.
Andreas Loukas. What graph neural networks cannot learn: depth vs width, 2019.
László Lovász. On the shannon capacity of graph. IEEE Transactions on Information theory, 25(1):
1-7, 1979.
Evan McCarty, Qi Zhao, Anastasios Sidiropoulos, and Yusu Wang. Nn-baker: A neural-network infused algorithmic framework for optimization problems on geometric intersection graphs. Ad- vances in Neural Information Processing Systems, 34:23023 2021.
Yimeng Min, Frederik Wenkel, Michael Perlmutter, and Guy Wolf. Can hybrid geometric scattering networks help solve the maximum clique problem? Advances in Neural Information Processing Systems, 35:22713-22772 2022.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference artificial intelligence, volume 33, pp. 4602-4609, 2019.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012. 2020.
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, pp. 9839 9849, 2018.
Danilo Numeroso, Davide Bacciu, and Petar Veličković. Dual algorithmic reasoning. arXiv preprint arXiv:2302.04446, 2023.
Liam O'Carroll, Vaidehi Srinivas, and Aravindan Vijayaraghavan. The burer-monteiro sdp method can fail even above the barvinok- -ataki bound. Advances in Neural Information Processing Systems, 35:31254-31266 2022.
Augustin Parjadis, Quentin Cappart, Louis-Martin Rousseau, and David Bergman. Improving branch- and-bound using decision diagrams and reinforcement learning. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 18th International Conference, CPAIOR 2021, Vienna, Austria, July 5-8, 2021, Proceedings 18, pp. 446-455. Springer. 2021.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
Max B Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, and Chris Maddison. Learning to cut by looking ahead: Cutting plane selection via imitation learning. In International conference on machine learning, pp. 17584-17600. PMLR, 2022.
Marcelo Prates, Pedro HC Avelar, Henrique Lemos, Luis C Lamb, and Moshe Y Vardi. Learning to solve np-complete problems: graph neural network for decision tsp. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp- 4731 4731-4738, 2019.
Chendi Qian, Didier Chételat, and Christopher Morris. Exploring the power of graph neural networks in solving linear optimization problems. arXiv preprint arXiv:2310. 10603, 2023.
Prasad Raghavendra. Optimal algorithms and inapproximability results for every csp? In Proceedings of the fortieth annual ACM symposium on Theory of computing, pp. 245-254, 2008.
Prasad Raghavendra and David Steurer. How to round any esp. 2009 50th Annual IEFF Symposium on Foundations of Computer Science, pp. 586-594, 2009a. doi: 10. 10L.//0CS./00099 74.
14

---

Prasad Raghavendra and David Steurer. Towards computing the grothendieck constant. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 525-534. SIAM, 2009b.
Prasad Raghavendra, David Steurer, and Madhur Tulsiani. Reductions between expansion problems. In 2012 IEEE 27th Conference on Computational Complexity, pp. 64-73. IEEE, 2012.
Alessandro Rudi, Ulysse Marteau-Ferey, and Francis Bach. Finding global minima via kernel approximations. arXiv preprint arXiv:2012.11978, 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems, 2019.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM international conference on data mining (SDM), pp. 333-341. SIAM, 2021.
Martin JA Schuetz, J Kyle Brubaker, and Helmut G Katzgraber. Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4):367-377, 2022a.
Martin JA Schuetz, J Kyle Brubaker, Zhihuai Zhu, and Helmut G Katzgraber. Graph coloring with physics-inspired graph neural networks. Physical Review Research, 4(4):043131, 2022b.
Daniel Selsam and Nikolaj Bjømnrr Guiding herf--peroommnnce sat solvers with unsat-core predictions. In Theory and Applications of Satisfiability Testing-SAT 2019; 22nd International Conference, SAT 2019, Lisbon, Portugal, July 9-12, 2019, Proceedings 22, pp. 336-353 Springer, 2019.
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L. Dill. Learning a sat solver from single-bit supervision, 2018.
Alexander Smith, Andreas Veneris, and Anastasios Viglas. Design diagnosis using boolean satisfia- bility.. In ASP-DAC 2004: Asia and South Pacifie Design Automation Conference 2004 (IEEE Cat. No. 04EX753), pp. 218-223. IEEE, 2004.
Haoran Sun, Etash K Guha, and Hanjun Dai. Annealed training for combinatorial optimization on graphs. arXiv preprint arXiv:2207. 11542, 2022.
Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Run-csp: Unsupervised learn- ing of message passing networks for binary constraint satisfaction problems. arXiv preprint arXiv:1909.08887 2019.
Jan Tönshoff, Berke Kisin, Jakob Lindner, and Martin Grohe. One model, any esp: Graph neural net- works as fast global search heuristics for constraint satisfaction. arXiv preprint arXiv:2208.10227, 2022.
Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. International Conference on Learning Representations.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Petar Veličković, Adrià Puigdomènech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, and Charles Blundell. The clrs algorithmic reasoning benchmark. In International Conference on Machine Learning, pp. 22084-22 102. PMLR, 2022.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, pp. 2692-2700, 2015.
Jose L Walteros and Austin Buchanan. Why is maximum clique often easy in practice. Oper. Res, 2019.
Haoyu Wang and Pan Li. Unsupervised learning for combinatorial optimization needs meta-learning International Conference Learning Representations, 2023,
15

---

Haoyu Peter Wang, Nan Wu, Hang Yang, Cong Hao, and Pan Li. Unsupervised learning for combinatorial optimization with principled objective relaxation. In Advances in Neural Information Processing Systems, 2022.
Po-Wei Wang and J Zico Kolter. Low-rank semidefinite programming for the max2sat problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1641-1649, 2019.
Po- Wei Wang, Priya Donti, Bryan Wilder, and Zico Kolter. Satnet: Bridging deep learning and logical reasoning using differentiable satisfiability solver. In International Conference Machine Learning, pp. 6545-6554, PMLR, 2019.
Wenxi Wang, Yang Hu, Mohit Tiwari, Sarfraz Khurshid, Kenneth McMillan, and Risto Miikkulainen. Neurocomb: Improving sat solving with graph neural networks. arXiv preprint arXiv:2110.14033, 2021.
Yiming Wang, Austin Buchanan, and Sergiy Butenko, On imposing connectivity constraints in integer programs. Mathematical Programming, 166(1-2):241-27) 2017.
Ke Xu, Frédéric Boussemart, Fred Hemery, and Christophe Lecoutre. Random constraint satisfaction: Easy generation of hard (satisfiable) instances. Artificial intelligence, 171(8-9):514-544 2007.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural
networks? In International Conference on Learning Representations, 2019. URL https:// openreview peet/forummiddiiee
Yunqiu Xu, Meng Fang, Ling Chen, Gangyan Xu, Yali Du, and Chengqi Zhang. Reinforcement learning with multiple relational attention for solving vehicle routing problems. IEEE Transactions on Cybernetics, 52(10):1107-111220 2021.
Emre Yolcu and Barnabás Póczos. Learning local search heuristics for boolean satisfiability. Advances in Neural Information Processing Systems, 32, 2019.
Mohammed Javeed Zaki, Srinivasan Parthasarathy, Mitsunori Ogihara, Wei Li, et al. New algorithms for fast discovery of association rules. In KDD, volume 97, pp. 283-286, 1997.
Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: Solving graph combinatorial optimization problems with gflownets. arXiv preprint 1005 2023.
16

---

A
Min- Vertex-Cover OptGNN
Min Min-Vertex-Cover can be written as the following integer program
+ 3z
Minimize:
(11)
<E[N] 2
Subject to: - (1-r;) - =;)== =0 v(i.J) E
(12)
2
Vi E [N]
(13)
To deal with the constraint on the edges (1 x1)(1 - 3z) 0, we add quadratic penalty to the
objective with a penalty parameter 0 yielding
Minimize:
Σ
Ti
+ P Σ
(1 - 52 - 2j + x,0;)
(14)
1E(N]
(i,))E
Subject to:
=;=1
[
(15)
Analogously to Max-Cut, we adopt natural low rank vector formulation for vectors = {vi) dimensions.
1 (wi, no)
Minimize:
+P
Σ (1 -
(mi, up) (1z, vo) + (Us. 15))²
(16)
2
NE
(L,))E
Subject to:
||0||| U E
RR
Vi
[N]
(17)
Now we can design a simple projected gradient descent scheme as follows. For iteration è in max iterations and vector v; we perform the following update.
0.+1 of niup 2p
Σ (1 JEN()
(ut, vp) (of, un) + (1,, (1), tf))
(18)
0
1+1
(19)
|
We then define OptGNN (M.G) analogously with learnable matrices M {M he E R Rx22 which are each sets of T learnable matrices corresponding T layers of neural network. Let the message from node to node v; be
MESSAGE(u, + w.] = 2p(1 (0f, up) - (0j, vo) + (w%, (- of))
Let the aggregation function AGG be defined as
AGG((v))ee(o) = E EjEN() MESSAGE(1; vs]
Then for layer in max iterations T, for is in v, we have
0/+1 M (AGG(u!))
(20)
0
(21)
1
This approach can be straightforwardly adopted to compute the maximum clique and the maximum independent set.
17

---

B Max-3-SAT OpIGNN
Our formulation for Max 3-SAT directly translates the OpiGNN architecture from Definition 3.3 Let A be a 3-SAT instance with a set clauses P over a set of binary litcrals V = {21, 22, .... N E {-1,1): Here -1 corresponds to assigning the literal to False whilst 1 corresponds to True. Each clause P. E P can be specified by three literals (2y, 2.j. 2k) and a set of three 'tokens' (Ti, Tj. Tk) E
{-1,1] which correspond to whether the variable æis Jij 2y are negated in the clause. For instance the clause (z1 - V Øz) is translated into three literals (21, 22, 223) and tokens (1, 11)
The 3-SAT problem on instance is equivalent maximizing the following polynomial
1 (1 + 7,24)(1 ry + T..%))
Σ
(1
(22)
8
Subject to the constraint 21, .... IN f1. -13. Now we'r re reading to define the OptGNN for 3-SAT
Objective: First we define the set of vector embeddings. For every literal I; we associate an embedding oy E IR., For every pair of literals that appear in clause (r)) we associate variable Vi E Rr. Finally we associate a vector Uy to represent 1. Then the unconstrained objective SAT is defined as
(
SAT(A)
Σ
TTy Ker, vya) (1y, vns + (eu, vis)]
1
(Niiitt 72 MP)EP
1 1 ((ei, e5) + (Uig, voll -001--TTh TiT [eii un) + (ven, vo)l - T Kuy, vn) + (esk, upil
1
TT vi)) Tz (1z, Up) - Th (en, up} + +7)
(23)
Constraints:
The constraints are then as follows. For every clause involving variables (20,, Tj 25.) we impose the following constraints on 0i, Ui, Uk, Uij, Uak Uja and vig. Note that these constraints exactly the ones listed in algorithm 2 which we organize here for convenience. The naming convention is the degree of the polynomial on the left to the degree of the polynomial on the right.
1. pair-to-pair
(et, 23) (Wij, U1)
(24)
(0), Uk) = (WER. Up)
(25)
(0z, 2k) (uykk Un)
(26)
2. triplets-to-triplet
(vig, vk) (WERs U1) (uyks vz)
(27)
3. triplet-to-single
(wr, Uzy)
(1z, Up)
(28)
(uy, May) (wt, Up)
(29)
(Uy, Uya) (UR, Up)
(30)
(Kk, Myk) = (17, Up)
(31)
(w), viR) (vK, Up)
(32)
(Uk. UsA)
= (e), Up)
(33)
(34)
4. quad-to-pair
(Degs Uzb) (u,, U&)
(35)
(mej, v2a) (Uj, UR)
(36)
(Die. U.R.) (N6, 1i)
(37)
(38)
18

---

5. unit norm
w
||,y||
||wx|||
||
||
|oya|l
||00||
(39)
Then for completeness we write out the full penalized objective. We perform this exercise in such great detail to inform the reader of how this could be set up for other Max-CSP's. Definition (OptGNN for 3-SAT). Let A be a 3-SAT instance. Let Lp be defined as
LV( =
Σ
ThT (or, Uzx) + (15, G.)) + (vx, wiy)l
1 (00, vy) (vgg. [o)] TTTA 1
[10g, Uk) + (ver, - Ty T 1 Kuy, vn) (0yk
(141 vo) (15, 06) - -Tx 010 + +7)
+ [((((s 0z) (0))) 2b))² + ((r,, un) (Usk: u0)) + ((0), (1ysr 00) ?²
+ P [[(us. Uk) - (vik. 13))3 + ((ors, 0z) - (usRs 01))² + (LUzk, Us) (Vig, oz)) )
+ [(wag U22))
(us, ox)) + ((ey, vix) - (oy,, 2x))² + ((Uak) Usk) - (us, 13)) + ((15, wty) - (U), vo))² + ((ug.Uzk (oR, (0)) + ((Uk, U)k)))))))))))))))))))) 00))2
pl((e, (1y, v0)) (0))
+ ((ri, vxx) vp)) + ((VR, Uzx) - (ws, vo))
+o [(]|eel - 1)² + (1|0) 1)² (l|vall 1)² + (1 1)² +11vax - 1)² (11oaall - 1)² (llvell 1)
(40)
Then taking the gradient of C gives us the precise form of the message passing. We list the forms of the messages from adjacent nodes in the constraint graph GA.
Message: Pair Singles for Single in Pair. This is the message MESSAGE(e;, - U/l for each pair node Usy to a single v; node.
MESSAGE(0. + v/] |[c P: 24 E c))2p((v,, (iy) - (uy, og)) (41)
Message: Pair to Singles for Single not in Pair. each pair node Viy to single 2g node.
This is the message MESSAGE(uv + uk] for
MESSAGE by + Uk]
Σ CEP Eec
1 ThTgTH 2/5
8
+ 2p [(UK, viy) - (vi, vyae) + ((U5, Uzk) (Ox, m())) w.y)) (
(42)
Message: Single to Pair for Single in Pair. This is the message MESSAGE(U; 0iyl for each single node v; to pair Uk
MESSAGE[u; Biyl He E P 24 c))2p((u,, vg)) (uz, up))u;
(43)
Message: Single Pair for Single not in Pair. each pair node U/y to single eg node.
This is the message MESSAGE(11 -> ck] for
MESSAGE Dy + unl
Σ
TTT 3 Uu
(44)
8
CE CEPi(a,. Ec
+2p (((kk viy) - (v,. (xx))ox + (luk) vz)) (0,,, 2ra)) y01)
(45)
19

---

Message: Single to Single single 0j node.
This is the message MESSAGE(1; U3 + Uzyl for each single node to
MESSAGE|e; + uy]
Σ
TiTT 2 (115552
(46)
+2p ((ess 03) - (Viy, u) + ((Uik: U5a)) - (Us, z())) (-)))
(47)
Message: Pair to Pair Uikk node.
This is the message MESSAGE(Us rya] for each pair node viy a pair
MESSAGE(e;, - U5al = [c E P: Zz TR Th Ec) Uz2) (us, vx) )eyy
(48)
Then the OptGNN (M,C.) is defined with the following functions UPDATE, AGGREGATE, and NONLINEAR. For any node v, the OpiGNN update is
AGGREGATE((x<
MESSAGE - 'cEN(e)
Σ
(49)
UPDATE(U) M (1 AGGGEGATEE (F (FC
(50)
NONLINEAR(()-
(51)
|
Finally, note that many of the signs in the forms of messages could have been chosen differently ie (ex, 03) - (Vay. un) produces different gradients from (Vsy. Uo) (v,, UT). We leave small choices like this to the reader.
C Optimality of Message Passing for Max-CSP
Our primary theoretical result is that a polynomial time message passing algorithm on appropriately defined constraint graph computes the approximate optimum of 2DP2 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 SDP 2 for Max-k-CSP that provably equivalent the SDP of [Raghavendra (2008) and therefore inherits its complexity theoretic optimality. Finally, we design message passing algorithm to approximately solve SDP in polynomial time polynomial precision. Our message passing algorithm has the advantage of being formulated on an appropriately defined constraint graph. For a Max-k-CSP instance A with N variables, IP) predicates, over alphabet of size q, it takes |P|q* space to represent the Max-CSP. To declutter notation, we let & be the size of the Max-CSP which is equal to |P|g* Our message passing algorithm achieves an additive approximation in time poly(E -1 4 log(ō")) 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, Max-k-CSP instance A (VV,P,.) con- sists of a set of N variables V == {z; bei]e[]]] each taking values in an alphabet [g] and a set of predicates P == {Pz) (Pzzzv where each predicate is a payoff function over k variables denoted 2 {xi, Tin .... T.s Here we refer to k as the arity of the Max-k-CSP, and we adopt the normal- ization that each predicate P. returns outputs in [0, 1]. We index each predicate P. by its domain and we will use the notation S(P) to denote the domain of predicate P. The goal of Max-k-CSP is to maximize the payoff of the predicates.
max NN
Σ P((x))
(52)
El
IP]
PLEP
Where X, denotes the assignment of variables {x:hee.
There is an SDP relaxation of equation 52 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 rounding that achieves its integrality gap.
20

---

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 2 [0, }.. The extension to general is straightforward and detailed in the appendix.
We will adopt the standard pseudoexpectation and pseudodistribution formalism in describing SDP. Let [x[[x] be a matrix in dimension ((++1) ((N+1)"2**(+++) (N+1)**² optimization variables defined as follows
E [x] == Ep,(1, Z1, T2,,.,, (1 (1,,,),) )d/2))
(53)
Where to denote tensor product. It is convenient to think of [x] matrix of variables denoting the up to multilinear moments of a distribution μ over the variables V. A multilinear polynomial is polynomial of the form X Ilie 3; for some subset of the variables Φ C V. We index the variables of the matrix Ej [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.
(ar))E[N] of size k. Let X2 denote the multilinear moment X= := Ili Tj- Then [x,] denotes the SDP variable corresponding to the multilinear moment Ey, [X,]. Of course optimizing over the space of distributions μ over V is intractable, and opt for optimizing over the space of low degree pseudodistributions and their associated pseudoexpecation functionals. See Barak & Steurer (2014) for references therein.
Specifically, let be subset of the CSP variables
In particular, for any subset of variables X, { Tig. } E V we let [x,.[x]] denote the matrix of the up to degree up to multilinear moments of the variables 2.
E x = E,, ((,, Ity. Fi. )04/2 ((1, Tty The )84/2)
(54)
We refer to above matrix as a degree pseudoexpectation funcitonal over X₃, Subsequently, we describe pseudoexpectation formulation of our SDP followed by vector formulation.
Multilinear Formulation: predicate for boolean Max-k-CSP P=(X,) can be written
multilinear polynomial
Px())) =
Σ
W2.7 II
Σ
V,X,
(55)
2
Z.E3
For some real valued weights Wz.r and y, which are simply the fourier coefficients of the function Pg. Then the pseudoexpectation formulation of our SDP is as follows
max E, [x]
Σ [x.))
(56)
PP|
PLEP
subject the following constraints
1. Unit:
1, 1,, for all x; E V. and IT of Ilees xz] = II jes xy] for all s, C S(P) for every predicate
such that 2s ss S In expectation, the
squares of all multilinear polynomials are equal to 1.
2. Positive Semidefinite:
[x v.2 Z 0 i. the degree two pseudoexpectation is positive semidefinite. E,, [x] 2.24 2 for all z S(P) for all P. The moment matrix for the multilinear polynomials corresponding to every predicate is positive semidefinite.
Equivalently we can view the SDP terms of vectors the cholesky decomposition of E,, [x]. We rewrite the above SDP accordingly. For this purpose it is useful to introduce the notation C(A, B) == AU B/Ar A B. also useful to introduce the notation C(s) for the size of the set (g.g' C ((g.9') = s).
21

---

SDP 2 SDP for Max-k-CSP (Equivalent to UGC-optimal)
SDP Vector Formulation A = (V,P: (0, 13). Multilinear formulation of objective.
min
(X,))= = ΣΣ
w [c(s)]
Σ
(ig Ugg))
(57)
P
PCC
subject to: || =1 A8 V VP
VP E
(58)
E,, Ex((x(( = (gg:0g)) = (Uh, Une) vC(9.9) = h(h,h) sa و S((P), e (59)
First constraint is the square of multilinear polynomials are unit. Second constraint are degree 2k SoS constraints for products of multilinear polynomials.
Lemma C.I. For Max-k-CSP instance A, The SDP of SDP 2 is at least as tight as the SDP of Raghavendra 20088.
Proof. The SDP of Raghavendra (0088) is a degree 2 SoS SDP augmented with k-local distributions P. By using the vectors of the cholesky decomposition and constraining them to be unit vectors we automatically capture degree 2 SoS. To capture & local distributions we simply enforce degree SoS on the boolean hypercube for the domain of every predicate. This can be done with the standard vector formulation written in SDP2 See Barak & Steurer (2014) for background and references.
for every predicate
Moving forward, the goal of Algorithm is to minimize the loss (v(v) which is function of the Max-CSP instance A.
Cv(v) = [P]
Σ P.EP
Us c(s)]
Σ
Ug))
9.9 Ce sit Cln.d )=8
+ P Σ
Σ
(1eg) (gr) (wn, owl)
P.EP
9.d A.'' ((9.99 ((th,h))((hhhh))
Σ
(11val1 2 - 1)2 1)²
(60)
12 EV
The loss Cp has gradient of the form
Σ
Σ
Σ
Us ((s)
Vwn
P
P.EP StwCAsstuE C
cC
W Co
stt ((w,w))==
2p
Σ
Σ
((ow, Uwr) (ehs vw))
P.EP STWS
+ [[|vw 1 1)
(61)
Noticing that the form of the gradient depends only the vectors in the neighborhood of the constraint graph GA we arrive at our message passing algorithm. The key to our proof is bounding the number of iterations required optimize equation 60 to sufficient accuracy to be approximate global optimum of 2
iterations a set of vectors v == (6.) for all C for all P e P that satisfy the constraints of SDP error and approximates the
Theorem C.1. Algorithm computes O(e -1p log
22

---

Algorithm 3 Message Passing for Max-CSP
1: Inputs: Max-CSP instance A
2: $ log(6-1)
3: 77, W. t- n
[Initialize step size, noise threshold, and noise
variance)
4: v = (V + + Uniform((*"))
[Initialize vectors to uniform on the unit sphere) }
5: for E ( -ooco/l-oog0-11110
log(ō-1)) do
6: for u v² [Iterate over vectors and update each vector with neighboring vectors in constraint
graph) do
7:
? PPl
Σ
Σ
Us
[C())
Σ
(62)
P.EP 5.1 w
a5e
We C
+ 2p
Σ
E
(fr elorr - (th, w/()) (1 - 1)ue
P.EP
w W',
1o st st st((w,/")=<((NN)) ((((,N))
8:
if 1 +++ - will S 3 then
9:
aT)
10:
else
11:
12: end if
ot-1 v
(
14: end for
end for
16:
return v
Output: vectors corresponding solution SDP 2
optimum of 2o ervor with probability 1
Σ
Se
where SDP(A) is the optimum SDP
Proof. We begin by writing down the objective penalized by a quadratic on the constraints.
Cv(
Σ
(x.))
P
P.EP
+
Σ PLEP
Σ
((og) (vn, unr)))
Σ
(11vall - 1)2
(63)
9.9' Ji.h' Cz stt C(g.9')) ((fssn")<(hhh))) <(h,N')
Ev
For any monomial X, = -Iles x; in Pz (X.)) we write
E, [X,] = C(s)
Σ
(Eg. Dgr
(64)
9.9 Co stt C(a.a =
Where C(s) is the size of the set (g.g' S C - s}. =}. In a small abuse of notation, we regard this as the definition of [X,] but realize that we're referring to the iterates of the algorithm before they've 'e converged to a pseudoexpectation, Now recall equation 55 we can expand the polynomial P. (X,) along its standard monomial basis
23

---

Px(X,)= = Σ
=(xx)==ux Vs
(65)
where we have defined coefficients y/s for every monomial in Px())). Plugging equation equation 65 into equation 63 we obtain
64 and
Lp(v) = IPl
ΣΣ
Σ 9.9 C
(Ug Vgg))
(((S)
P.EP =
st Clo.9 )=
+ P Σ
Σ
((rgs 0gr)
(wh, vn.))
P.EP
9.9 A,
sA 199' (((,b))
Σ (10,11 1)²
(66)
EV
Taking the derivative with respect to any Uhe E v we obtain
Σ
Σ
Σ
IP|
Us
[C(s]
P.EP eCo stw st
w S
st <(w,,w)))
2p
Σ
Σ
((Vers Unoi) (whb (2)))ol
P.EP
of ALA'Cs (LC((. (((b,,)
ST
+ +[lvwl1 211uwl1-11)a 1)0e
-
(67)
The gradient update is then what is detailed in Algorithm
(C,(v)
0 1 1) Fo.
(68)
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) which we rewrite Theorem F.1 First we note that the SDP
has has smooth gradient for E S poly(p. and has lipschitz Hessian for poly(p, B) which we arrive at in Lemma E.2 and Lemma F.1 The
proofs of Lemma E.2 and Lemma our proof.
F. are technically involved and form the core hurdle in arriving at
Then by Theorem F.1 the iteration converges an (E', (2)SOSS Definition F.1 no more than Ö iterations with probability 1 8. Now that we've established that the basic gradient iteration converges to approximate SOSP, we need to then prove that the approximate SOSP are approximate global optimum. We achieve this by using the result of (Bhojanapalii et al. (2018) lemma which we restate in Lemma C for convenience.
The subsequent presentation adapts the proof of Lemma C.2
setting. To show that (e',
SOSP are approximately global optimum, we have to work with the original SDP loss as opposed to the nonconvex vector loss. For subsequent analysis we need to define the penalized loss which denote H.p ([E[x]) in terms of the SDP moment matrix [[x]
H, (E[x)) =
1
Σ
[x.)(
P
P.CP
+
Σ
Σ
(E (B(l(((n))))+
Σ
[L 1)2
(69)
PP.PP
9:9 A.C'Z
X, SLOCS(P)
C( ((Ch)")
IISAPPEP

---

Here we use the notation (x and Ep. PeplXxroa c(n,ar)) to denote (Ug, u/y) and (w), 2%) respectively. Note that although by definition Hpp (E(x) = Cp(v). their gradients and hessians are distinct because (v(()) is overparameterized. This is the key point. It is straightforward to argue that SOSP of a convex optimization are approximately global, but we are trying to make this argument for SOSP of the overparameterrzze loss C,(v).
Let the global optimum of SDP 2 be denoted [,[[]] with cholesky decomposition V. Let v be the set of vectors outputted by Algorithm 3 with associated pseudoexpectation F [x]. Then, we can bound
- (v) -,,,
(E(x) (VH, E[ E[x])
(70)
Here the first equality is by definition, and the inequality is by the convexity of H.. Moving on, we use the fact that the min eigenvalue of the hessian of overparameterized loss (V) 2 -yve' implies the min eigenvalue of the gradient of the convex loss Amio (VH, (EEx)) fact is invoked in [Bhojanppalli et al. (2018) lemma which we adapt to our setting in Lemma
-VVE. This
Subsequently, adapt the lines of their argument in Lemma C.2 most relevant to our analysis which we detail here for the sake of completeness.
70
Amin
VH, (E(xI) (B((()) (VH, [
S Amii (E(x)) Th ( +
[
S SIVE ( 2ve c S
(71)
Here the first inequality follows by a standard inequality of frobenius inner product, the second inequality follows by Cauchy-Schwand 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 E[{] is the identity and that every vector in v is unit vector up inverse polynomial error poly(p- 2* For this last point the proof in Lemma E Therefore if we set é' poly(e, we arrive at any error. Therefore we have established our estimate è is approximates the global optimum of the quadratically penalized objective i.e (E(x)) - H,p (É[x)) I e. To finish our proof, we have to bound the distance between the global optimum of the quadratically penalized objective H. (I]) and SDP(A) the optimum of SDP This is established for sufficiently large poly(E 2*) in Lemma E.1 This concludes our proof that the iterates of Algorithm converge to the solution of SDP
the third incquality follows by the ( > conditions
In our proof above, the bound on approximate SOSP being approximate global optimum is built on the result of Bhojanapalli et al. (2018) which we rephrase for our setting below.
Lemma C.2. (Bhojanapalli et al. 2018) lemma 3 rephrased] Let (.).) be defined as in equation 63
and let (-) be defined as in equation 69 Let E x be an (e. 7)SSOSP (-).,, then
Amin (VH,(E())) 2 -Yve
Furthermore, the global optimum X obeys the optimality gap
HV - H, & (VCT)(X) + + "lUll
The following Lemma 1 establishes that for sufficiently large penalty parameter p poly(e- -1,2% 2 the optimum of the penalized problem and the exact solution to SDP close. Lemma C.3. Let A be Max-k-CSP instance, and let SDP(A) be the optimum of SDP be the quadratically penalized objective
Let Lv(v)
Cv(v)== [P]
ΣΣ Y P.EP =C
Σ 9.9'S
(og
Σ P.EP
Σ
un!)
C(s)
9:9" ,,, Clg.9' ((g.g')=((hhh1
((9.9))=
Σ
(110a1
1)2
(72)
25

---

Let be the argmin of the unconstrained minimization
8 arg min Cp(v)
(
Then have
- S
for p poly(c-1,
Proof.
We begin the analysis with the generic equality constrained semidefinite program the form
Minimize:
(C,
(73)
Subject to:
(A,, X) = ViEF
(74)
X > 0
(75)
E Raxd
(76)
For an objective matrix C' and constraint matrices {Aiher in some constraint set F. We will invoke specific properties of to enable our analysis. First we define the penalized objective this generic form
Hp(x) = (C, + Σ X) 6,)²
Let X be the minimizer of the penalized problem.
X
arg min (x( XeRdxa
Let X* be the minimizer of the constrained problem equation 87
Let T; be the error X has in
satisfying constraint (A, X)= by-
= I X) -49
We will show that T; scales inversely with p. That is, T, S. poly(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 i.e 'robust' to perturbations the constraint violations the quadratic penalty should overwhelm the decrease in the objective. To carry this intuition, we begin with the fact that the constrained minimum is larger than the penalized minimum.
Ha((*) - Hxp(X) <
(77)
Applying the definitions of (X*(X) and (X) obtain
(C,x)) (1C, x) + 23)
(78)
EEF
Rearranging LHS and RHS and dividing by |F] obtain
(C, (C,
(79)
TET
We upper bound the RHS using the robustness theorem of Raghavendra & Steurer (2009) restated in the appendix Theorem F.2 which states that an SDP solution that violates the constraints by a small perturbation changes the objective by a small amount. Thus we obtain.
1/2
RHS <
Σ iEF
T.
poly(k)
(80)
F
Therefore combining equation
79 with equation 80 we obtain
1/2
Σ
(A)y(A)
26

---

Taking Cauchy-Schward on the RHS we obtain
1/4
Σ
+
poly(k)
F
Noticing that [F E, T?
appears in both LHS and RHS we rearrange to obtain
poly(k)
Se
F
p²/3
have the average squared error of the constraints is upper bounded by Then via Markov's no more than ve fraction of the constraints can be violated by more than squared error Ve. We label these grossly' violated constraints. The clauses involved in these grossly violated constraints contributes no more than poly(k) V the objective. On the other hand, the constraints that are violated by no more than squared error vc contributed no more than poly (k)) to the objective which follows from the robustness theorem Theorem Taken together we conclude that
Where for poly(k)
<3/4
(p(T) SDP(A) Se
For = poly(k,, as desired.
Finally we show it's not hard to generalize our algorithm alphabets of size [g].
Notation for General Alphabet. For any predicate P E P, let D(P) be the set of all variable assignment tuples indexed by set of variables S S(P) and assignment [g]lsl Let (i.o) denote assignment of value [q] to variable 2;.
SDP 3 SDP Vector Formulation for Max-k-CSP General Alphabet (Equivalent UGC optimal)
SDP Vector Formulation General Alphabet A (V, P.g). Pseudoexpectation formulation of the objective.
min 21.22
Ex(-P:(X,)] P.CP
Σ
(81)
subject to: Eu((a - x(taa)
II (1.))+
.6,و =0 V, (g) vo CPP))
(82)
E. Σ
II [(,,i) =0 E V, 94 (PP))
(83)
aE[s]
(J)))
II fomi =0 WEE, Va # (0). vo 44 C(P), VP VPEP
(1,))&
(84)
B[SoS2ng (Xx)) 20 D(P),
(85)
E[SoSy(x)] 2 0.
(86)
First constraint corresponds to booleanity of each value in the alphabet. Second constraint corresponds to variable taking only value in the alphabet.
Third constraint corresponds to a variable taking on only one value in the alphabet. Fourth constraint corresponds to local distribution the variables in each predicate.
Fifth constraint corresponds to the positivity of every degree two sum of squares of polynomials.
Lemma C.4. There exists message passing algorithm that computes poly(e-1, -1
iterations set of vectors := {((r,) for all (i, ø. for all & D(P), for all P. that satisly
27

---

the constraints of Algorithm with probability 1-6
B to error and approximates the optimum of Algorithm 3 to error
Σ
ExIP.(X.) SDP(A)) Se
P.EP
where SDP(A) is the optimum of Algorithm
Proof. The proof entirely parallel the proof of Theorem C.1 We can write Algorithm Bentirely 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 kg variables over each predicate. Given the overparameterized vector formulation, we observe that once again we are faced with equality constraints that can added to the objective with a quadratic penalty. Perturbed gradient descent induces message passing algorithm over the constraint graph Ga. and in more than poly(E (b) iterations reaches an (c, ()SSSP. The analysis of optimality goes along the same lines as Lemma constraints is and the objective is robust to small perturbations in satisfying the constraint. That concludes our discussion of generalizing to general alphabets.
For sufficiently large penalty / = poly(e -1 .g)) the error in satisfying the
C.1 Neural Certification Scheme
An intriguing aspect of OptGNN is that the embeddings can be interpreted as the solution a low rank SDP which leaves open the possibility that the embeddings can be used to generate a dual certificate i.e lower bound convex relaxation. First, we define the primal problem
Minimize:
(C,X)
(87)
Subject to: (A,. X) = b,
ViE [
(88)
x x 0
(89)
Lemma C.5. Let OPT be the minimizer of the SDP equation any X E RlFl, we define Fx- (X) to be
87
Then for any X E NxN 2 0 and
Fx (= +
Σ 1 (A,, - bz)
NEF
We require SDP to satisfy bound on its trace Tr(X)= < for some y E RR Then the following is a lower bound on OPT.
OPT Fx-(X) - (VFx- (X), + Amin (VF) y
Proof. Next we introduce lagrange multipliers À E IR* and 2 0 form the lagrangian
C(A, Q x) (C, x) + Σ As ((A,, X) b,) (Q. X)
iEF
We lower bound the optimum of OPT defined be the minimizer of equation 87
OPT min max C(A,Q,X) XE0
min (OX(CVVV)) VERNXN
Σ
X ((Ar, VVT) b.) (90)
X
SEF
min (C, Σ Xe ((Ar, VVT) - b.) (91)
VERNXN
iEF
min (C + Σ Xi ((A,, bi). VERNXN
(92)
Where in the first inequality replaced X with VVT which is lower bound every psd matrix admits a cholesky decomposition. the second inequality we flipped the order min and max, and in the final inequality we chose a specific set of dual variables X E [R which lower bounds the maximization over dual variables. The key is to find good setting for X*.
28

---

Next we establish that for any choice of X we can compute lower bound on inequality 92 as follows. Let Fx- (VVT) be defined the funciton in the RHS of 92
Fx- FV-(VV)) (C,
Σ iEF
M ((), b.)
Then equation can can be rewritten as
OPT
min VERNXN
(3-(VV))== Σ X ((A;,)) - -b:)
iEF
Now let V* be the minimizer of equation 92 and let X = (*(V))². We have by convexity that
(x) - Fx-(X*) (VFx X x*) = (V)x- + (- VEx- (X),
(93)
(X), Amann (VFx-(X) Tr(X")
(94)
S (x) Amin (V (X))N
(95)
In the first inequality we apply the convexity of Fxt. 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
OPT 2 Fx(x) 2 (x) (VFx (X), X) + Amin (VFx (X)) N
(96)
Therefore it suffices upper bound the terms above (VFx-(X), X) and Amia ( (VFx- (X)) which an expression that holds for any X. Given the output embeddings V of OpIGNN (or indeed any set of vectors V) let X- VVT. Then we have concluded
OPT 2 Fx 2 Fx- (X) (VFx Amin (VFx-(X))N
(97)
as desired.
Up to this point, every manipulation is formal proof. Subsequently we detail how to estimate the dual variables X" Although any estimate will produce bound, it won't produce tight bound. To be clear, solving for the optimal X would be the same as building an SDP solver which would bring us back into the expensive primal dual procedures that are involved solving SDP's. We are designing quick and cheap ways to output dual certificate that may be somewhat looser. Our scheme is simply to set X such that ||V (X)ll 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 (V) be defined as follows
Xx (V) == (C, (C, + Σ>; (AA, -b.)
IEF
We know the gradient of (v)
VHA(V)= = C+ Σ AAA C+
V V -VP
Therefore it suffices to find setting of X* such that (XF((XVVII is small, ideally zero. This would be a simple task, indeed a regression, if not for the unfortunate fact that OpiGNN explicitly projects the vectors in V to be unit vectors. This creates numerical problems such that minimizing the norm of (X))) does not produce a (X)) with large minimum eigenvalue.
To fix this issue, let (V) denote the penalized lagrangian with quadratic penalties for constraints of the form (Ai, X) = be and linear penalty π) for constraints along the main diagonal of X of the form (ezef. X)= 1.
N
Ryp((V = (C,VVT)+ + EP(AA, - b,)2 + Σ
milles VVT) - 1)
NET
29

---

Taking the gradient of (V) we obtain
V (V) = 2CV + 1
220((A, - b.)AVVV +
2nee V
SEJ
Our rule for setting dual variables ó, for i E J is
6 : 2p (Ai, VVT) bs)
our rule for setting dual variables fi for j E [N] is
n
oj
C+ E
20((A,, -VT) b,) v
IEF
Then full set of dual variables X is simply the concatenation (6, Writing everything explicitly we obtain the following matrix for V (VVV2)
VFX((VV) = C+ Σ
P(A,,
6,)4, +
Σ JE[N]
cf
C+ (VT) v xeef
C+
iEF
Plugging this expression into Lemma C.5 the final bound we evaluate in our code is
OPT (C, + Σ
(A, VVT) b:)²
iEF
| C+ E o(A,, VVT) b,)Ai+ Σ
C+
Σ
2p((A,, b.)4
-b))4) V eee, vpr
2
FEF
JE[N]
EEF
(C+ C+E - 4.) JE[N]
+ +Amin
Σ
2
E
T
C+ Σ
2p((A,, VV4) 1 bi) v eeee N
iEF
SEF
(98)
Which is entirely computed in terms of V the output embeddings of OpIGNN. The resulting plot is as follows.
Quality: vs. Opt-GNN-ccert N=
200
SDp cart
150
180
180
100
140
130
140
150
100
1700
350
130
Oct GMN
Figure 4: N=50 p=0.1 SDP OptGNN Dual Certificate
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.
Note:
30

---

Max-Cut Certificate For Max-Cu- our dual variables are particularly simple as there are no constraints (A,,)) b, for # O. The dual variables for Max-Cut take on the form for all [N]
1 2
x;
Σ JENO
It's certainly possible to come up with tighter certification schemes which we leave future work.
Near global optimality one step of the augmented method of lagrange multipliers ought to closely approximate the dual variables. After obtaining a estimate for the penalized lagrange multipliers we estimate the lagrange multipliers for the norm constraint by approximating v VRx(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.
Intuition:
Certificate Experiment: We run our certification procedure which we name OptGNN-cert and compare 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 primal dual solver, the entire time of producing OptGNN-cert is in the time required feedforward through OptGNN. In this case we train an OpGGNN-Max-Cut with 10 layers, on 1000 Erdos-Reny graphs, with N = 100 nodes and edge density p = 0.1. We plot the OpiGNN 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 OpIGNN-cert. See for the N = 50 graphs and m for the N 100 graphs.
Note of course the dual certificate for any technique must be larger than the cut value outputted by OpIGNN so the scatter plot must be above the y axis of the plot. We see as is mathematically necessary, the OptGNN-cert is not as tight as the SDP certificate but certainly competitive and more importantly arrived at dramatically faster. Without any runtime optimizations, the OptGNN feedforward and certification takes no more than 0.02 seconds whereas the SDP takes 0.5 seconds on N 100 node graphs.
D Experiment details
In this section give further details our experimental setup.
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 = 15), Barabási-Albert (with m 4), Holme-Kim (with m and p = 0.25), Watts-Strogaat (with h = 4 and 0.25), and forced RB (with two sets of parameters, RB200 and RB500). Our real-world datasets are ENZYMES, PROTEINS, MUTAG, -IDB-B. COLLAB (which we will together call TU-small), and REDDIT-BINARY REDDIT-MULTI-SK and REDDIT-MULTI- (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ény. random graphs with vertex count drawn uniformly at random from [50, 100]. In tables, we mark generated datasets with superscript ", TU-small with h. and TU-REDDIT with S.
For Figure 2b we display results for forced RB instances drawn from two different distributions. For RB200, we select N uniformly in [6, 15] and K uniformly in [12, 21]. For RB500, we select N uniformly in [20, 34] and K uniformly in [10, 29].
random 3-SAT instances are generated by drawing three random variables for each clause and negating each variable with p = 0.5. We trained on instances with 100 variables and clause count drawn uniformly from the interval [400, 430), and tested on instances with 100 variables and 400, 415, and 430 clauses respectively.
In Table 2
Baselines. We compare the performance of our approach against known classical algorithms. In terms of classical baselines, we run Gurobi with varying timeouts and include SDP results on smaller datasets.
31

---

Parameter
ER. BA, WS, HK
RB200
RB500
3-SAT
TU-small
TU-REDDIT
Gradient steps
20,000
200,000
100,000
100,000
100,000
100,000
Validation freq
1,000
2,000
2,000
2,000
1,000
2,000
Batch size
16
32
32
32
16
16
Ranks
4, 8, 16, 32
32, 64
32, 64
32, 64
4, 8. 16, 32
4, 8. 16, 32
Layer counts
8, 16
16
16
16
8, 16
8, 16
Positional encodings
RW
none
LE, RW
RW
Run count
8
2
2
16
8
Figure 5: Hyperparameter range explored for each group of datasets. For each NN architecture, when training on dataset, we explored every listed hyperparameter combination in the corresponding column.
We also include a greedy baseline, which is the function one_exchange (for Max-Cut) or min_weighhod_rrrrtssscooov (for Min- Vertex-Cover) from networkx (Hagberg et al., 2008).
Validation and test splits. For each dataset we hold out a validation and test slice for evaluation. In our generated graph experiments we 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/fe split of 0.8/0.1/0.. 1/0.1. For TU-REDDIT, we set aside 100 graphs each for validation and testing.
Scoring. To measure a model's 's score on a graph, we first run the model on the graph with a random initial vector assignment generate SDP output, and then round this output to integral solution using 1,000 random hyperplanes. For the graph, we retain the best score achieved by any hyperplane.
We ran validation periodically during each training and retained the model that achieved the highest validation score. Then for each model and dataset, we selected the hy hyperparameter setting that achieved the highest validation score, and report the average score measured on the test slice. Please seell D for further details on the hyperparameter ranges used.
In Figure 2b and Figure 2a at test time, we use 100 random initial vector assignments instead of just and retain the best score achieved by any hyperplane on any random initial vector assignment. We use random initial vector assignment for validation in other cases.
Hardware. Our training runs used 20 cores of Intel Xeon Gold 6248 (for data loading and random graph generation) and NVIDIA Tesla V 100 GPU. Our Gurobi runs use 8 threads on a Intel Xcon Platinum 8260. Our KaMIS runs use an Intel Core 19-13900H. Our LwD and DGL runs use an Intel Core 19-13900H and an RTX 4060.
range of hyperparameters. See Figure 5 for the hyperparameter listing. For all training runs, we used the Adam optimizer Kingma & Ba (2014) with learning rate of 0.001. We used Laplacian eigenvector Dwivedi et al. (2020) (LE) random walk Dwivedi et al. (202T) (RW) positional encoding with dimensionality of half the rank, except for rank 32 where used 8 dimensions. For Max-3-SAT, we set the penalty term p 0.003.
Hyperparameters. We each experiment
D.1 Max-Cut
Low-rank SDP We have included an additional baseline that solves low-rank SDP using coordinate descent (Wang & Kolter 2019) to the Max-Cut benchmark that originally appears in Any-CSP (Tönshoff et al. (2022). We have used the publicly available implementation provided by the authors. For each instance, the rank is automatically selected by the package to be [V2N].
D.2 Max-3-SAT
ErdösGNN. The ErdōsGNN baseline accepts as input clause-variable bipartite graph of the SAT formula and the node degrees as input attributes. Each variable z; is set TRUE with probability p:- A graph neural network (GatedGCNN) is trained until convergence (~500 iterations) with randomly generated formulae with clause to variable ratiot in the range [4, 4.3). The neural network trained to produce output probabilities p; by minimizing the expected number of unsatisfied clauses. The exact closed form of the expectation can be found in (Karalias) 2023). At inference time, the probabilities rounded to binary assignments using the method of conditional expectation.
32

---

Survey propagation. We report the results of survey propagation Braumstein et al. 2005 Typically. algorithms like survey propagation are accompanied by local search algorithm like WalkSAT. Here we report the results obtained by the algorithm without running any local search on its output.
Low-rank SDP. This is identical to the baseline that used for Max-3-SAT (see Max-Cut section above).
WalkSAT. We use publicly available python implementation of WalkSAT and we set the max number variable flips to 4unumber of variables, for total of 400 flips on the instances we tested.
Autograd. The autograd comparison measures the performance of autograd on the same loss as OpIGNN. Starting with some initial node embeddings for the instance, the Lagrangian is computed for the problem and the node embeddings are updated by minimizing the Lagrangian using Adam. This process is run for several iterations. After is concluded, the vectors are rounded with hyperplane rounding, yielding binary assignment for the variables of the formula.
Autograd parameters. We use the Adam optimizer with learning rate 0.1 for 1000 epochs with penalty 0.01 and round with 10,000 hyperplanes, which is 10 times as many as that used by OpIGNN.
D.3
Additional Results
D.3.1
Comparisons with Gurobi and Greedy
Table 4 and Table 3
contain comparisons on additional datasets with Gurobi and Greedy.
Dataset
OpIGNN
Greedy
Gurobi 0.
Gurobi 1.0s
Gurobi 8.0s
BA* (50,100)
42.88 (27)
51.92
42.82
42.82
42.82
BA* (100,200)
83.43 (25)
101.42
83.19
83.19
83.19
BA (400,500)
248.74 (27)
302.53
256.33
246.49
246.46
ERx (50,100)
55.25 (21)
68.85
55,06
54.67
$4.67
ER (100,200)
126.52 (18)
143.51
127.83
123.47
122.76
ER (400,500)
420.70 (41)
442.84
423.07
423.07
415.52
HK' (50,100)
43.06 (25)
51.38
42.98
42.98
42.98
HK* (100,200)
84.38 (25)
100.87
84.07
84.07
84.07
HK (400,500)
249.26 (27)
298.98
247.90
247.57
247.57
WC' (50,100)
46.38 (26)
72.55
45.74
45.74
45.74
WC (100,200)
91.28 (21)
143.70
89,80
89,80
89.80
WC (400,500)
274.21 (31)
434.52
269.58
269.39
269.39
MUTAG
7.79 (18)
12.84
7.74
7.74
7.74
ENZYMES
20,00 (24)
27.35
20.00
20,00
20.00
PROTEINS'
25.29 (18)
33.93
24.96
24.96
24.96
IMDB-BIN"
16.78 (18)
17.24
16.76
16.76
16.76
COLLAB"
67,50 (23)
71.74
67.47
67.46
67.46
REDDIT-BINE
82.85 (38)
117.16
82.81
82.81
82.81
REDDIT-M- 12K"
81.55 (25)
115.72
81.57
81,52
81.52
REDDIT-M-SK"
107.36 (33)
153.24
108.73
107.32
107.32
Table 3: Performance of OpIGNN, Greedy, and Gurobi 1s,s, 1s, and 8s on Min- Vertex 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.
D.3.2
Ratio tables
In Figure 6 and Figure 7 we supply the performance of OpIGNN as a ratio against the integral value achieved by Gurobi running with 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 Min-Vertex-Cover. OptGNN comes within 3.1%.
33

---

Dataset
OpiGNN
Greedy
Gurobi 0.1s
Gurobi 1.0s
Gurobi
8.0s
BA (50,100)
351.49 (18)
200.10
351.87
352.12
352.12
BA" (100,200)
717.19 (20)
407.98
719.41
719.72
720.17
BA" (400,500)
2197.99 (66)
1255.22
2208.11
2208.11
2212.49
ER 150,100)
528.95 (18)
298.55
529.93
530.03
530.16
ER (100,200)
1995.05 (24)
1097.26
2002.88
2002.88
2002.93
ER (400,500)
16387.46 (225)
8622.33
16476.72
16491.60
16495.31
HK" (50,100)
345.74 (18)
196.23
346.18
346.42
346.42
HKº (100,200)
709.39 (23)
402.54
711.68
712.26
712.88
(400,500)
2159.90 (61)
1230.98
2169.46
2169.46
2173.88
WC" (50,100)
198.29 (18)
116.65
198.74
198.74
198.74
WC (100,200)
389.83 (24)
229.43
390.96
392.07
392.07
WC (400,500)
1166.47 (78)
690.19
1173.45
1175.97
1179.86
MUTAG?
27.95 (9)
16.95
27.95
27.95
27.95
ENZYMES
81.37 (14)
48.53
81.45
81,45
81.45
PROTEINS'
102.15 (12)
60.74
102.28
102.36
102.36
IMDB-BIN BIN"
97.47 (11)
51.85
97.50
97.50
97.50
COLLAB"
2622.41 (22)
1345.70
2624.32
2624.57
2624.62
REDDIT-BIN
693.33 (186)
439.79
693.02
694.10
694.14
REDDIT-M-12K
568.00 (89)
358.40
567.71
568.91
568.94
REDDIT-M-5K'
786.09 (133)
495.02
785.44
787.48
787.92
Table 4: Performance of OptGNN, Greedy, and Gurobi 0.1s, 1s, and 8s on Maximum Cut. For each approach and dataset, 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 OpIGNN.
Dataset
OptGNN
Dataset
OptGNN
BA* (50,
0.998 0.002
WC (100,200)
0.995 0.003
BA* (100,200)
0.996 0.003
WC (400,500)
0.989 + 0.003
BA (400,500)
0.993 = 0.003
MUTAG*
1.000 0.000
ERa (50,100)
0.998 0.002
ENZYMES²
0.999 = 0.003
ERa (100,200)
0.996 = 0.002
PROTEINS*
1.000 + 0,002
ERa (400,500)
0.993 = 0.001
IMDB-BING
1.000 0.001
HK (50,100)
0.998 = 0.002
COLLAB*
0.999 0.002
HKº (100,200)
0.995 0.003
REDDIT-BIN
1.000 0.001
HK* (400,500)
0.994 0.003
1EDDIT-M-12K*
0.999 + 0.002
WC² 150)
0.998 = 0.003
REDDIT-M-5K-
0.999 0.002
Figure 6: Performance of OpIGNN on Max-Cut compared Gurobi running under an second time limit, expressed ratio. For each dataset, 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. of the cut value the worst measured case.
34

---

Dataset
OptGNN
Dataset
OpiGNN
BA* (50,100)
1,001 + 0.005
WC (100,200)
L016 0.013
BA (100,200)
1.003 + 0.005
WC (400,500)
1.018 0.007
BA (400,500)
1.008 + 0.011
MUTAG
1.009 = 0.027
ER (50,100)
1.010 0.015
ENZYMES"
1.000 0.000
ER (100,200)
1.031 = 0.012
PROTEINS'
1.010 = 0.021
ERS (400,500)
1.013 = 0.006
IMDB IMDB-BIN
L.02 0.016
HK* (50,100)
1.002 + 0.007
COLLAB
1.001 = 0.003
HK* (100,200)
1,004 + 0.013
REDDIT-BINE
1.000 0.002
HK* (400,500)
1.007 + 0.011
REDDIT-M-I2K
1.000 + 0.001
WC² (50.100)
1.014 = 0.016
REDDIT-M-SK
1.000 + 0.001
Figure 7: Performance of OpIGNN on Min- Seee-eeeexx-veee compared to Gurobi running under an second time limit, expressed ratio. For each dataset, we take the ratio of the integral values achieved by OpIGNN and Gurobi 8s on each of the graphs in the test slice. We present the average and standard deviation of these ratios. Here, lower is better. This table demonstrates that OptGNN achieves nearly the same performance, producing a cover on average 3.1% larger than Gurobi 8s in the worst measured case.
D.4 Model ablation study
Here we provide the evaluations of several models that were trained on the same loss as OptGNN. We see that OptGNN consistently achieves the best performance among different neural architectures. 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 few percent of OptGNN on nearly all the datasets (excluding COLLAB). This points the overall viability of training using an SDP relaxation for the loss function.
Dalusel
GAT
GCNN
GIN
GatedGCNN
OpGGNN
ER" (50,100)
525.92 (25)
500.94 (17)
498.82 (14)
$26.78 (14)
$28.95 (18)
ER' (100,200)
1979.45 (20)
1890. 10 (26)
1893.23 (23)
1978.78 (21)
1995,05 (24)
ER" (400,500)
16317.69 (208)
15692.12 (233)
15818.42 (212)
16188.85 (210)
(225)
MUTAG*
27.84 (19)
27.11 (12)
21.16 (13)
27.95 (14)
27.95 (9)
ENZYMES
80.73 (17)
74.03 (12)
73.85 (16)
81.35 (9)
$1.37 (14)
PROTEINS
100.94 (14)
92.01 (19)
92.62. (17)
(10)
102.15 (12)
BIN
(18)
(21)
(10)
97.11
COLLAB"
2611.83 (22)
2109.81 (21)
2430.20 (23)
(18)
2622.41 (22)
Table 5: Performance of various model architectures for selected datasets 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).
Table 6 presents the performance of alternative neural network architectures on Min-Vertex-Com Vertex-Cover.
Dataset
GAT
GCNN
GIN
GatedGCNN
OPIGNN
ER' (50,100)
58.78 (20)
64.42 (23)
64.18 (20)
56.17
55.25 (21)
ER' (100,200)
129.47 (20)
141.94 (17)
140.06 (20)
130.32 (20)
126.52 (18)
ER (400,500)
443.93 (43)
444.12 (33)
442. (31)
440.90 (28)
420.70 (41)
MUTAG
7.79 (19)
8.11 (16)
7.95 (20)
1.79 (.7)
7.79 (18)
ENZYMES
21.93 (24)
25.42 (18)
25.80 (28)
20.28 (14)
20,00 (24)
PROTEINS
(23)
31.07 (19)
(21)
25.25 (19)
25. (18)
IMDB-BIN'
17.62
19.22 (19)
19.03
16.79 (15)
16.78 (18)
COLLAB"
68.23
73.32 (17)
73.82 (26)
72.92 (13)
67.50
Table 6: Performance of various model architectures compared to OptGNN for selected datasets on
Min- Vervex-Cover. Here, lower is better.
35

---

SLE BIGAN
(a) On TU-small datasets.
ThiS Putroalere
with
-100
(b) On generated datascts.
Figure 8: Trends in model performance Min- Vertex-Cover with respect the number of layers, hidden size, and positional encoding the models.
D.5 Effects of hyperparameters on performance
Figure and
Figure
present overall trends in model performance across hyperparameters.
36

---

(a) On TU-small datasets,
ryperprrmeter pertoc mereer mEcuILE
10--
(b) On generated datascts.
Figure 9: Trends in model performance on Max-Cut with respect to the number of layers, hidden size, and positional encoding of the models.
D.6 Out of distribution testing
OpIGNN trained one dataset performed quite well other datasets without any finetuning, suggesting that the model can generalize to examples outside its training distribution. For each dataset in our collection, we train model and then test the trained model on subset of datasets in the collection. The results are shown in Table It is apparent from the results that the model performance generalizes well to different datasets. Interestingly, we frequently observe that model reaches its peak performance on a given test dataset even when trained on different one. This suggests that the model indeed capturing elements more general process instead just overfitting the training data.
37

---

Train Dataset
MUTAG
ENZYMES
PROTEINS
IMDB-BIN
COLLAB
BA 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
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
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
WC (50,100)
7.89
20.13
25.46
17.38
70.14
WC (000,200)
7.79
20.30
25.45
17.91
71.16
WC (400,500)
8.05
20.48
25.79
17.12
70.16
MUTAG ENZYMES
7.74
20.83
26.76
16.92
70.09
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
Table 7: Models for Vertex-Cooveeeeeee 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.
D.7 Pseudocode for OptGNN training and inference
In algorithm 4 present pseudocode for OptGNN in the Max-Cut case and in algorithm 5 pseu- docode for the forward pass of general SDP.
Algorithm OpiGNN pseudocode for Max-Cut forward pass
Require: graph
1: v (V), 02 .... UN (random initial feature vectors and/or positional encodings)
2: for = 1, 1,2, 3. ...... do
3: for i E v do
4:
of 1-1 of + > )jEN(i) of
2/+1
5: 8111 + Linear(
10
6: end for
7: end for
Algorithm 5 OpiGNN pseudocode for implementing general SDP forward pass
Require: graph G
1: v {U1, ....... UN (random initial feature vectors and/or positional encodings)
2: for 1,2, ...... do
3: for ui E v do
4:
1-1 + of + Autograd G))
5:
86-1 + Linear
10
6: end for
7: end for
38

---

E
Generalization Analysis
In this section produce generalization bound for OpiGNN. First restate result that penalized loss approximates the optimum SDP2 Our amalysis follows from a standard perturbation argument where the key is bound the lipschitzness of the OptGNN aggregation function. Here we will have to be more precise with the exact polynomial dependence of the lipschitzness of the gradient V pp and the smoothness of the hessian V p.-
Notation: For the convenience of the proofs in this section, with slight abuse of notation, we will define loss functions (V) that take matrix arguments V instead of collections vectors v where V is simply the vectors in concatenated row by row. We will also refer to rows of V by indexing them with set notation v; E V where v; denotes the i'th row of V. Furthermore, let every vector be bounded in norm by some absolute constant B.
We begin by recomputing precisely the number of iterations required for algorithm approximate the global optimum of 2 Note that this was done in the proof of Theorem C.1 but we do it here with explicit polynomial dependence.
Lemma E.1 (gradient descent lemma restated). Algorithm 3 computes in O 1og"(6-1)
iterations a set of vectors v := {ú,} for all C S(P) for all P E P that satisfy the constraints of SDP 2 to average error and approximates the optimum of SDP error with probability 1
Σ P.PP
ExP.((X)) - SDP(A)) Se
where SDP(A) the optimum of SDP
Proof. To apply the gradient descent lemma of Jin et al. (2017) Theorem F.1 we need bound on the lipschitzness of the gradient and the smoothness of the hessian of the loss equation 72 By the lipschitz gradient Lemma E.2 we have that the loss is ;= poly( B)p lipschitz, and by the smooth hessian Lemma F.T have the loss is y = poly(B)p smooth. Then we have by Theorem F. that perturbed gradient descent in
(f(Xo) - l 52
deA e02
log*
iterations can achieve a ("2,,")- SOSP. In our setting ((x)) - < because the loss normalized
between [0, 1]. Our desired accuracy e' is poly(B-1, , ) - poly(B-1 p where
take poly(2*, ) as in Lemma E.1 For these settings we achieve an approximation in Ó log (8-1) iterations.
Next move prove the lipschitzness of the Max-CSP gradient. This is important for two reasons. First we need it to bound the number of iterations required in the proof of Lemma E.1 Secondly, the lipschitzness of the hessian will be the key quantity
Lemma E.2 (Lipschitz Gradient Lemma Max-CSP). For a Max-CSP instance A, Let (v) be the normalized loss defined in equation 72
Then the gradient satisfies
VV, < VI
Proof. We begin with the form of the Max-CSP gradient.
OC,(V)
(V)
VC,(V)- vC
Σ
(99)
Iin.
No..
WE
F
39

---

Where recall
0Cp(v)
1
Σ
Σ
Σ
Vo [(()]
Dw!
vw
Pl
P.EP "Ez
W'
StwCastuCe
2p
Σ
Σ
(foWr Veri) - (un, Uw ) v'w
on .'A' st at ((w,w")=((ia)) >(((),))
PEP
+ (1/vw/ll 1)
(100)
We break the gradient (V) up into three terms T2(V,, and Tz(V) such that (V) = (V (VV) (L)) Where (v)) (2(V) (ar (s(V) le are defined as follows
[V( = [P|
Σ
Σ
Ve
C(s)
(101)
P.EP c
sa ((10,
2p T2(V) ~ [P]
Σ
Σ
(1ows Uwi) (wn, 120)
(102)
P.EP
x. WI
((w,w')==(hh.)
2p (112m0112 - 1)2
TV [P]
(103)
Such that by triangle inequality we have
- VV) - V.,( s (
- =|
Ta(1) T|(V) - Ta(
((a)))((()))
(104)
Where the three terms in equation 104 are follows.
(VVV T/00// PI
Σ
Us
[C(s)
(wwr Burr
(105)
P.EP cC St
w C sA((w,,")==
(E(V)-T((D)))
(106)
2p
Σ
Σ
Σ
[H vwr) - (uhy vw:)) ((ire Bur) (6n, bn)) 8%
PP]
WEF
P.EP
starg st ((m,,')=((hh.)
(107)
(T(()) - 1
2p
Σ
[[[[1100111 - 1)u 01/0mr112 1)0m 11
(108)
[P||
WEF
We bound the terms one by one. First we bound term 1.
40

---

Term 1:
- Pl
Σ WEF
Σ P.EP StwC:stwCe
Σ
Σ
(wwr - Bid))
(109)
IC(s)]
=C2
We will need to define some matrices so that we can write the above expression as the frobenius inner product of matrices. First define GA to be the adjacency matrix of the constraint graph. In particular we denote the (w, w') entry of GA as G wew defined as follows.
GAle,or = {1. 1, there exists P. E s.t ((w, (())
0, otherwise
Furthermore, we define My (s)) to be a matrix comprised of set of coefficients ys/ Us/[C(s)] cor- responding to every edge the consraint graph GA- The (w, w') entry of M My./C(s) is denoted My./C(s) wa and defined as follows.
My. (C(s low = [v//(((s), if there exists Pg E E S.t w/) =
10
otherwise
Then rewriting equation
T09
(V - Ti()
Σ WEF
MV
(110)
F IP|
Pi V | Mv.rcto)
(111)
By Cauchy-Schweee Schwarz we obtain
Ti()) - -i()
- P
|r o My. || v-
(112)
Next we move on to bound term 2.
Term 2:
Ta(V) TaMMI11-
(113)
2p I
Σ F
Σ
Σ
bo (wn, vn))o()) (fowr Der 1o0 - (6n, 2n.)
P.EP
o M'N' sa (1(,,)")=((hh))
stw
(114)
Let the vector d Uw Var and let the scalar 8m,,nn (Bery Unnt) - (Bar Buo)). Then we have by plugging definitions that
((ew, Ye' (Bw, )(m) = ((ww) Vor - (((vwr Uwr) + Sw (1/o + 8w.)))
(115)
Substituting equation
TI5 into equation 114 in the square root obtain
2p
Σ
Σ
Σ
- Wwas Une Dww Sm, + oe San
(116)
P
WEF
PLEP L
Cs
41

---

Applying triangle inequality we obtain
16p PPI
Σ wEF
Σ
Σ
(Wars Vnn Dour
+ WEF
+
Σ P.EP n S² W
Σ
Σ
Σ
Σ
ow Our
P.EP n Cs sut u
WEF
P.EP w
Ca
(117)
Let Mor) IR! IRIP12 x|P|2* be the matrix whose w, entry is (Bw, d'u)) Let Ms the matrix whose w, w entry is ow, Let @ denote the entrywise product two matrices.
16p
/ CA |P]
M (o (V -V- + +||0x o Mo (V (V- -11l + C P Mo (V-
1
(118)
Applying Cauchy-Schwarz we obtain
16p P V IG @ M Mo 11 (v- 1) + +I o II 1/ 111
Gx
Ms
|
2
(VV- 1//
(119)
We apply entrywise upper bound (Var U S B which can be done because we' re taking a frobenius norm so the sign of each entry does not matter. Likewise we apply crude entrywise upper bound of 6 I B again because the sign of each entry does not matter in the frobenius norm (for each row this is euclidean norm).
16B*p |PP)
V |IGNNI//
V-
-11 + IIGA v v--l
+ 1IGAl?? |
(120)
Using the fact that ||Gx|p S 2th VIPI
2* Ba p
V -V-v|l 52 V |/F
(121)
p
Therefore have established
Tv(V)- -
S²"B²' v 811
(122)
Finally we move on to bound term 3.
Term 3:
-5(0)-((()11 =
2p
Σ WEJ
|| (11umol1 1) - (11 1)0m 11²
(123)
iP]V
2p PP
/ - 11 10 + Eu Vw
(124)
Applying triangle inequality obtain
2p
|uwll 2 Uww - -110ml Em 2
2p
110
vull?
(125)
P
[P]
WEX
WE
Using the fact that Σwer
1ww - umnll -uull
11V V1
P
2p
|||| 11 Uw - -11 1| 0m
1
+
|p]
2p
1|V - V1IF
(126)
WE
42

---

Let de.. := nn - Vw
then substituting the definition we obtain
2p
Σ
New
/| vi - l/ + Sv.,.l 11 (Uwr + dow))
12]
22
2p
I1 1/l
(127)
V
(Pl
WEF
expanding the expression in the square root obtain
2p =
Σ
2/
Nv. - l1ōe. Ve || 11 8e. 2(w )ow)ou. - 110 dvw
|']
Pl
WEF
(128)
2p
+
IV
V
[P]
(129)
By triangle inequality we upper bound by
2p
2 8ew vwll
Pl
WEF
2p
|2]
110m
112 Une
IP]
V
2p
2
||
8ew
[P]
+
2p
Σ
2
112
PP]
WEF
2p
2
11óm.. 112 80m
PP
WEF
2p + [P]
VV
V11F (130)
For the first term consider by Cauchy-Schwarr
|| 2(w )v..) Cwr
Yur 112 = 4/ 8._ )² ||w < 4B*
1 11?
Consider the second term which we upper bound via the norm bound on ||v < B
|6_.. 11? ow
| 2| B²
Consider the third term which we upper bound via the norm bound on || S B
||ol 11 8 I = u| [|6. B² 11: 1|²
Consider the fourth term which we upper bound via Cauchy- Schwarz
2(v do 112 = 4(Uw, do 116._ 1| < 4B² 11
Consider the fifth term. We apply crude upper bound of || 1| B2
|| 18cz 212 8e
11.....1" 118... 112 B² 18 1|
Therefore conclude
20 p IP
2p |p]
130
<
Σ
15
+
VV Vl
(131)
WEF
20B2 p
||V
v/
+
2p
IV
VI
(132)
P
F
P
43

---

So we conclude our bound on term 3
Ts(V) - T 20B2 v V/1
(133)
as desired. Putting our bounds for terms 1, and into equation 104 we obtain
VV, v SO | ll
(134)
as desired.
Lemma E.3 (Max-CSP gradient perturbation analysis). For any set of matrices M
(M,, M2, Mr} E _garxr perturbation U = (U,,U2,.., UT} E _ that satisfies [1 1.1 I for all i E [T. Let M + U denote the elementwise addition of M and U as such M+U == [M1 U1, +U2 Mr+ tUT). Then for matrix V E g satisfying |V S vd
we define the aggregation function AGG IR IRTXN + 2 as such
V AGG(V) vC
(135)
Furthermore, let LAYERM, (V) denote
LAYERM, (V) = M(GGG(())
Finally, let OpIGNN Ad RRNN be defined as OptGNN M (V) Lp LAYERM,
LAYER LAYER (V)
Here we feed the output of the final layer LAYERT to the loss function L RRRN + R. Then
|OptGNN Mr (V) OONGOOIGNMMMO M+ S ((BBT ,T)
Proof. We begin by analyzing how much the gradient perturbs the input to single layer. First we apply the definition of LAYER and AGG to obtain
|LAERR (V) - (V)IlF
(136)
< (M UVV - MVII + ((M VC,(M
(137)
[UV + [VVC+(+((+(MMM)) - VV,(MVV)
(138)
< |V]1,
-V,,))l
(139)
3/2 |IVC, + (ML))((+))
- -V))) (VC
(140)
Here the first inequality follows by triangle inequality. The second inequality follows by Cauchy- Schwarz. Finally the frobenius norm of is er the frobenius norm V Then applying the lipschitzness of the gradient Lemma
E.2 we obtain.
S 3/2 + +OB3p) [I +UV MVII, = O(B?))
(141)
I 3/2 3/2 pBBPp) [ |
[V
(142)
5 3/2 +O(B [V
(143)
O(B p)er3/2
(144)
To conclude, we' ve established that
|LAYER Mr (V) - M (V)l
3/2r
(145)
Next we upper bound the lipschitzness of the LAYER function by the frobenius norm of || S ((r) multiplied by the lipschitzness of VL, which is O(B2p), p). Taken together we find the the lipschitzness of LAYER is upper bounded by O(B²p pr).
Note that OptGNN is comprised of T layers of LAYER functions followed by the evaluation of the loss L. The T layers contribute a geometric series of enrors with the dominant term being O pr2pr)T) O(e(B2 "T) The smaller order terms contribute no more than an additional multiplicative factor of 7 leading emrr of (Te((B² 2T) At any rate, the dominant
44

---

term is the exponential dependence on the number of layers. Finally, OpIGNN's final layer is the evaluation of the loss pp. The lipschitzness of the loss Cp can be computed as follows. For any pair of matrices V and V both R we have
p2 [P] ||
- -v, S
(146)
where we used the fact that the loss is dominated by its quadratic penalty term times the square of the violations where each row in V can be counted in up to 2 constraints normalized by the number of predicates [P]. Putting this together applying the LAYER function over T layers we obtain
OpiGNN M+G (V) OpiGNN m (V)ll & O p 2T 2T))
(147)
At this point we restate some elementary theorems in the study of PAC learning adapted for the unsupervised learning setting.
Lemma E,4 (Agnostic PAC Icarnability (folklore)). Let 21, 22, ... ~ D be data drawn from distribution D. Let H be any finite hypothesis class comprised of functions E where the range of h in bounded in [0, 1). Let h
be the empirical loss minimizer
arg min NEW
h(xz)
N
SE[N]
Let ō be the failure probability and let be the approximation error. Then say i (N, e, PA-P learnable if
Pril N
Σ - 2 8
iE[N]
Furthermore, is (N) learnable long
N = o [log [H]
log(1 (1/))
2
The proof is standard epsilon net union bound argument which the familiar reader should feel free to skip.
Proof. For any fixed hypothesis h the difference between the distributional loss between [0, and the empirical loss can be bounded by Hoeffding.
Pr
E Be>D[h(x)]
Σ h(x)) > exp(-NNe)
KE[N]
Let h H be the empirical risk minimizer within the hypothesis class on data (x1, T2, .., .N What is the probability that the empirical risk deviates from the distributional risk by greater than c? ie we wish to upper bound the quantity
Pr [EWD(((E))
Σ M(x;) > 6 XE[N]
N
Of course the biggest caveat is that h depends on F1.-.,, UN and thus Hoeffding does not apply. Therefore we upper bound by the probability over draws I .., UN ~ D that there exists ANY hypothesis in H that deviates from its distributional risk by more than E.
E E [h(x)]]
1 N
Σ VEINI
Pr 1E EE
U hEW
[ELDD/(()]
Σ M(x,) >
(E[N]
(148)
This follows because the event that deviates substantially from its distributional loss one of the elements of the union the right hand side.
45

---

1 h(xx))
Σ
> o
_
U NEW
1 N
Σ NE[N]
h(x,) > >c]
N
NE[N]
Then we have via union bound that
Pr RyomnyyD
BEWD [m()]]
Σ
> >
Pr
[U
(ENDD(((())
Σ h(x;) > []
N
N
iE[M]
DEW
iE[N]
Pr 2g
E BooD(h(>))
Σ h(x;) >
KE[N]
exp(
(2 = |H| exp(-c2N) (149)
NEW
where the last line follows by Hoeffding, In particular if we want the failure probability to be 5 then
[H| (exp(=22 <
(150)
which implies
H
N
Suffices for the ' H deviate from its empirical risk by less than 6.
Finally putting our perturbation analysis Lemma E.3 together with the agnostic PAC learnability Lemma E.4
Lemma E.5. Let A1, A2,..., Ap D be Max-CSP instances drawn from a distribution over instances D with no more than [P] predicates. Let M be set of parameters M = {M, Mr} parameter space e Then for I = O(2*), for I' = O 66 log' 1og"((-1))) (8-1)), let M be the empirical loss minimizer
M arg min MED I
Σ
kE[T
Then we have that OpiGNN is 8)- learnable
OPIGNN (MM.A.) EAND [OPIGNN nZ SE[T]
Pr
Se 2 -
Proof. The result follows directly from the agnostic PAC learning Lemma E.4 and the perturbation analysis Lemma E.3 We have that for net of interval size fer suffices for an approximation.
The cardinality of the net is then ,22 /ec per parameter raised the power of the number of param- eters required for OpIGNN to represent an approximate solution to SDP(A) Each LAYER is comprised of matrix M, of dimension r 2r for r &. By Lemma E.I we need a total of T = O($4<=1log") 1og"(611)) layers to represent optimal solution with probability 1 5. Then the total number of parameters in the network O (6- desired.
46

---

F
Hessian Lemmas
This section is prove the hessian V²G, Lp is smooth. This is relevant for bounding the number of iterations required for algorithm 3
Lemma F.1 (Smooth Hessian Lemma). For a Max-CSP instance A, Let Cy(v) be the normalized Then the hessian satisfies
loss defined in equation 72
v2 Cv)Il & 8BpIIV - Vlrr-
In particular for poly(k, 1 we have that the hessian is poly B, k,, smooth.
Proof. Next we verify this for the Max-CSP hessian. The form of its hessian is far more complex. To simplify matters first consider the hessian of polynomials of the form T T(us, Vj Uks vs) ((v,, uz) (Uk, u2))²
0
T
205a
for a, b E [r]
Ovia Pukb
Te trz
T
Ukb.
for a, b E [r]
T
22sa Veb,
for a b E
Teja dejad
Te Ove T 22ha Ukb:
for a, E [r]
Seio Buga T = 20ya Vib.
for a, b E [r]
V2T (1), Uk.
T = 2 Ukb.
for a, b E [r]
av Bva
J T
Ujai
for E [r]
ōe T
for a E [r]
ia
T
for E [r]
T
for E [r] otherwise
3e
0.
We can decompose the Hessian as sum of 10 matrices corresponding to the cases enumerated above.
V'T(v) = V + V'T(()lann + V²T(v)l(g)) + V²T(v)
+ +V*T(v)l(s) + (VT(()
T(v)lu + V²T(v) VVT(v)lle (151)
Then compute
[v² (vT(v)
[VT(()) += T()
(V=T((V)le ((.)) V
V'T(W))
|V- (V)))) V2T(+) F //2 (K.0) - (+)ooll
[V²T(v))
- V'T(lllasslee
+ +|V2TT(V))(
(1V"T V*T(Wllelle- (152)
Noticing that the first four terms have the same upper bound, terms 5 and 6 have the same upper bound, and terms through 10 share the same upper bound obtain
[VVT(v)) -
(VV (+)a)ll V2T(() (l)lll
2 V
+ -
- VVT(+))
(153)
Now consider the first term
[V2((>)) V2T(D) = 4( Σ
(UjaVes 02)
(154)
a.bE(r]
47

---

Let 6y 8g uy b and 8: 6z vg. We expand equation 154 to obtain
2/|0, 0,07 FF 21| (v, 6,)(vz 5
= 2211yug - (2rn) + 0,0g + o50 + II?
= + 0,0 66,0
+ where we apply Cauchy-Schwarz as needed. The second term is bounded similarly. The last term can be bounded
< <16([16]111|ss1] + |||1||]]]]++ 1 1= = ( ||x+111),
|V2T(v) - V $2
22
Σ
ja
DE(r]
Upper bounding Vja + 0ūaa S 2B which applies for all a E [r] we obtain
=2 Σ (oja - (2 + 0ja)² s 2
B Σ (Uja - 0za)2 s 2 |10 1 B².
[Eir]
aE/rl
Putting the terms together obtain the following bound for
[V²T(v)) (iT(v)|l
1613² (110,112 1102112) + (110,1 P ((xx (116:11 + (|62l13) + (116.11 ||ōe|l²)
+ (116, 12 |1,,1 + (116 1| + || 112)
+ (116, 112 ||, 11 + || || 13)] (155)
Now can perform the analysis for the hessian of the entire Max-CSP loss
(v(v)=
ΣΣ3. e
y
Σ
(Ugg
[
C(s)
P.EP
9. C
C(a.9')
+
Σ PLEP <(g.g') (((,h'')
Σ
((Vg) Ngr) - (un, vw.))
A.N''
+
Σ 1110,112 1)2
(156)
3.Ev
We break the loss into three terms
wi(v:== := P
Ya C(s)
1
Σ
(og, (gr)
P.EP
S
stt C(a.0 )m
Wb((): = 0
Σ
Σ
(Vyg) (on, kw)))
P
P.EP
9.9' Ar,'C <la.9' (((ha)
Wa(v)= P
Σ
(1|o,11 1)2
0,EV
48

---

such that (p(v) = Wi(v) + W2(v) + Ws(v). We break the hessian apart into three terms
| ( (
+ ( (I
W-)lll (157)
The first term is zero as its the hessian of a quadratic which is constant. The difference is then zero. We bound the second term as follows.
V2 (2
P P
Σ P.EP
E
(V"Toor V (.
9.9 9.9' Clo.9 )(9.)))((hhN))
P
Σ PLEP
E
64Ba (115g1 16 112 || + ||6 11)..
P
h.N's <(g.9') ((th))
Noticing that each 0g be involved in more than |P] sums by being variables in every single predicate.
8Bp |P]
8Bp
VIPIIV
VIB
V
V/FF-
P
Now we move on to bound W/
[Pa3(v) - WW
Σ
(11ua11 - 1)2
-1)
PsEV
pB M |P]
pB |P|
Σ
| 0g 12
|
VIle.
Putting all three terms together we obtain the smoothness the hessian dominated by W2-
8Bp /
Bp
8Bp
[ (0C((0)
+
D
Vlr
V
Vllr.
p
vIP
F.1 Miscellaneous Lemmas
Theorem F.1 (perturbed-eg gd Jim et al. (017)). b. Let f be t-smooth (that is, it's gradient is (-Lipschitz) and have y-Lipschitz Hessian. There exists absolute constant Cmaz such that for any ö e (0, 1),1), < & y A 2 f(xo) f*, and constant S Cmax, PGD(Xu, B.n.C.C, 8, Aς) applied the cost function f outputs (y²,e) E) SOSP with probability at least 1 - 8 in
(f(Xo) - f
log"
22
228
iterations.
Definition. [(7,,c- -e-ccn order stationary point] A (y, c) second order stationary point of function is point x satisfying
V [+)( Se
Xmain V f()()) -C.
Theorem F22 (Robustness Theorem 4.6 Raghavendra & Steurer 2009a) rephrased) Let v be set of vectors satisfying the constraints of SDP 2 to additive error with objective OBJ(y), then
SDP(A) 2 OBJ(v) Vkpoly(kqq.
Corollary 2. Given Max-k-CSP instance A, there is an OPIGNNMAAVV with T O 1og(8-1)) layers, O(Φ) dimensional embeddings, with learnable parameters M (M,,.. Mr} that outputs set vectors V satisfying the constraints of SDP and approximating its objective, SDP(A), to error with probability å over random noise injections.
49

---

Proof. The proof is by inspecting the definition of OptGNN in the context of Theorem 3.1
Corollary 3. The OptGNN of Corollary 2 which by construction is equivalent Algorithm outputs set of embeddings v such that the rounding Raghaavvena & Steurer (2009) outputs an integral assignment V with Max-k-CSP objective OBJ(V) satistying OBJ(V) 2 (SDP((A)
e) in time exp(exp(poly) ()) which approximately dominates the Unique Games optimal approximation ratio.
Proof. The proof follows from the robustness theorem of [Raghavendra & Steurer (009a) which states that any solution the SDP that satisfies the constraints approximately does not change the objective substantially Theorem F2
G
Definitions
In this section we introduce precise definitions for message passing, message passing GNN, and SDP's. First we begin with the SDP.
Definition (Standard Form SDP). An SDP instance A is comprised of objective matrix C and constraint matrices {Ai]iEz and constants {ie over a constraint set J.
NxN
Minimize:
(C,X)
(158)
Subject to: (A,, X) b Vi [F]
(159)
X O.
(160)
For any standard form SDP, there an equivalent vector form SDP with an identical optimum.
Definition (Vector Form SDP). Any standard form SDP A is equivalent to the following vector form SDP.
Minimize:
(C, (C,VVV)
(161)
Subject to:
(A,, VVV) = be Vi [F]
(162)
V == [11, (2, 02, UN] E RNN
(163)
For the SDP's corresponding to CSP's, there is natural graph upon which the CSP instance is defined. Next we define what it means for a message passing algorithm on graph solve a SDP.
Definition (Message Passing). A T' iteration message passing algorithm denoted MP is uniform circuit family that takes as input a graph G = (V, E') and initial embeddings U = {u,] he(N]] E R and outputs MP(G,U") E x The evaluation of MP involves the use of uniform circuit family defined for each iteration UPDATE = [UPDATE,);ET? At iteration E [T'. for each node i V, the function UPDATE, +1) + I'' takes the embeddings of nodes and its neighbors at iteration é - 1, denoted (u] 8- DjeN(ouur E I", and outputs embedding uf E RT.
We additionally require some mild restrictions the UPDATE function to be polynomially smooth in its inputs and computable in polynomial time. That is for any ||]|| < B the B norm ball we have
UPDATE, (U - -U") < B,l(B,N))[C U'|. and the UPDATE, circuit is polynomial time computable (f))
(164)
We impose some mild restrictions on the form the message passing algorithm to capture algorithms that could reasonably be executed by a Mcssage Passing GNN. In practice the UPDATE circuit for OptGNN a smooth cubic polynomial similar to linear attention and therefore of practical value. Next define Message Passing GNN.
Definition (Message Passing GNN). A layer Message Passing GNN is a uniform circuit family that takes as input a graph G = E), a set of parameters == {M² M2 ..., M12 }. and initial embeddings 1r { JEV R and outputs GNN(G, M. ) T The GNN circuit is
evaluated as follows. For each node i E V, each layer & E [7], there a uniform circuit family
AGG, RIM* x (+))
R" that takes as input set of parameters A e M and set of
50

---

embeddings of node and its neighbors at layer & denoted fuf HENN(OUS and outputs an embedding un. This update equation is represented as follows
== AGG UY) = UPD(u (
(165)
For some functions UPD and MSG parameterized by M To capture meaningful models of GNNs, we require (M, Ui to be polynomially lipschitz and computable in polynomial time. That is, for weights M and M' and for inputs Ü and U" all in the B norm ball, we require
|AGG(M, Ū) AGG(M', U'II s poly(B, N) (I 1AM-MM'
+ M'II (I'--M'I++ +101 1(-')))
(166)
and we require AGG(M, Ū) to be computable in poly( time.
In practice the AGG circuit for OptGNN is a smooth cubic polynomial similar linear attention and therefore of practical value. In almost the same way, we define message passing algorithm see Definition G
Definition (Output of GNN solves SDP). We say GNN e-approximately solves SDP with
optimum OPT its output embeddings U = { heNN approximately optimize the vector form SDP objective SDP( (eN])) OPT and approximately satisfy the vector form constraints (A,, VTV) - bul <
51

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset used"). In general, answering "[No] or "[NA]" is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can be found.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Main claims are message passing GNN for Max-CSP Theorem C. Corollary OptGNN experiments for Max Cut, Vertex-Cover, 3-SAT (Figure 2b Table Table neural certification experiment [egeimment(Fiuuee>
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We compare our results against broad variety of neural and classical baselines AWalkSAT, Survey Propagation, Gurobi, CVXPY, SDP's, etc.), perform extensive ablations host of datasets Tables 5,6 and Figures 5-9 and situate our theory within the existing literature on approximation algorithms with SDP's (see references intro). Computational efficiency of OptGNN and message passing algorithm are stated adjacent to their definitions.
52

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
Main theorem informally stated Theorem 3.1 is restated formally in body of
paper as Theorem C with accompanying proof. Main PAC learning result stated paper
3.1 and restated in appendix and proven as E.5 Certification proof is provided in C.I
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The paper provides a thorough description of the experimental details (see Appendix (D), as well pseudocode for the proposed method (see Algorithm 5)
Guidelines:
53

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Link the code along with instructions is provided in the main text.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
soseeeesuuumssssooooooooy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https CodeeSumiiii www.iisssoooooiii
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
54

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes, the experimental setup is thoroughly described in the Appendix D and in the main experiments section of the paper.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report enror bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The paper reports standard deviations for several experiments (e.g., Figure 3b, Table 2, Figure 6, Figure 7). In cases such as Figure 3a where the setup is identical to previous published work, the deviations not available because they were not provided in the original paper.
Guidelines:
The answer NA that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The resource that were used are detailed in Appendix D Execution time is also discussed there but also explicitly provided tables 1,2.3,4.
Guidelines:
55

---

The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: After reviewing the code of Ethics, the authors find that the paper does not violate it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper provides a general theoretical result about graph neural network architectures and experimental backup for its claims on general benchmark instances. There are no immediate societal implications aspects of neural networks such as their combinatorial rrolleg-solving (which is the case here) can open up avenues for their misuse. However, believe that those consequences are rather indirect and beyond the scope of our paper.
this line of work. On the other hand, improving
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologics that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
56

---

11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The released models and the data used do not have a high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The paper provides appropriate citations for packages and data that have been used and their licenses are properly respected.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
Yes we provide a detailed description of the code that being provided with the submission.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
57

---

The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not include any such experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjeets
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper has no such research or experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
58


Reviews:
[{"review_id": "rBDympd1wS", "reviewer": "Reviewer_WeYu", "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.", "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?\n2. 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?\n3. Can you also point out some future directions for this research? Both application and theoretical wise are good.", "limitations": "Yes.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The paper is theoretically solid. It builds on well-established concepts in approximation algorithms and semidefinite programming, providing a strong theoretical basis for its claims. \n2. The development of OptGNN, a graph neural network that can capture optimal message-passing algorithms for combinatorial optimization problems, seems to be a significant innovation. This architecture leverages message-passing updates use SDP relaxations to prove its high-quality approximate solutions.\n3. The paper includes a variety of evaluations, such as out-of-distribution tests and ablation studies, which help validate the practical utility and robustness of OptGNN.", "weaknesses": "1. Although OptGNN shows strong performance on several benchmarks, it does not outperform all state-of-the-art methods. This indicates room for improvement in the model’s optimization and training processes.\n2. 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.\n3. The writing needs to be improved, there are multiple typos and inconsist notations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for all their detailed comments and review of our work! To address the\nconcerns in order. \n1. For a graph $G$ with vertices $V$ and edges $E$, for embedding dimension $d$, and depth $L$, the total runtime of OptGNN is $O(L d^\\omega |V| + Ld|E|)$ where $\\omega$ is the matrix multiplication constant $2.37$.  That is, the computational cost scales linearly in the size of the graph just as it does with message passing neural networks.  In practice, the max cut GSET instances serve as a scalability test.  \nThe GSET dataset is comprised of graphs with up to tens of thousands of nodes, whereas the OptGNN training set was comprised of graphs with up to 500 nodes.  We observe the model maintains strong performance for instances that are up to 3000 nodes and subsequently tapers off when the number of nodes substantially exceeds 3000. \n2. The OptGNN construction can be performed for any polynomial optimization subject to polynomial constraints (polynomial system solving).  Any polynomial system, of which MaxCSP is a prominent example, admits a vector form SDP relaxation corresponding to the degree-2 Lasserre hierarchy relaxation. A prominent example of a problem that does not have a well known formulation as a polynomial optimization is the traveling salesman problem.  \n3. Promising avenues of research include constructing tighter bounds on optimality for the outputs of neural architectures/OptGNN.  Tighter bounds directly translate to superior performance for branch and bound tree searches that require a certificate of optimality for termination.  This would be a promising avenue for empirical investigation.     \n4. Weaknesses: Indeed, further empirical work is required to achieve state of the art across a wide variety of benchmarks.  With respect to the UGC, although its truth is yet undetermined, another way to think about it is from the perspective of algorithms.  OptGNN captures the algorithms with the best approximation ratios for Max CSP that are known in the literature.\n\nWe once again thank the reviewer for their questions and time in reviewing our work, and hope our response addresses their concerns!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZFl4wufBX3", "reviewer": "Reviewer_zqcP", "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.", "questions": "1. Could you clarify how the proposed approach scales with increasingly large problem instances, particularly regarding computational complexity and performance stability?\n2. What are the generalization capabilities over problem scale of the proposed approach?\n3. What are the limitations of OptGNN? please explain in the text.", "limitations": "Authors need to discuss the limitation of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper explores integrating semidefinite programming into GNNs under the Unique Games Conjecture to optimally approximate combinatorial optimization problems. It introduces the OptGNN, a model designed to utilize polynomial-time message-passing algorithms and low-rank SDP relaxations to effectively solve problems such as Max-Cut and Max-3-SAT. The paper establishes OptGNN's potential through PAC learning arguments and empirical validation against traditional solvers and neural baselines. The paper is well-structured and mathematically sound.", "weaknesses": "- The paper lacks a comprehensive analysis of how well OptGNN scales with increasing graph sizes and complexity.\n- Although the out-of-distribution generalization of OptGNN has been tested, an analysis of its generalization over problem size is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the detailed feedback. We appreciate their positive comments on the soundness and the structure of the paper!\n\nTo address the weaknesses:\n\n>The paper lacks a comprehensive analysis of how well OptGNN scales with increasing graph sizes and complexity.\n\nThe cost of OptGNN scales linearly with the size of the graph (number of nodes/edges) as it is a message passing GNN. Empirically, we show that OptGNN runs on graphs of several thousands of nodes (GSET and 3-SAT experiments) without scalability issues. \n\n>Although the out-of-distribution generalization of OptGNN has been tested, an analysis of its generalization over problem size is missing.\n\nOur Max-Cut GSET results act also as both size and OOD generalization tests since the training was done on ER graphs of 500 nodes with a fixed edge density, and the testing was done on the GSET instances which can have tens of thousands of nodes and are not from the same ER distribution. The model performs competitively on up to an order of magnitude larger graphs than the ones it was trained on.\n\n>Could you clarify how the proposed approach scales with increasingly large problem instances, particularly regarding computational complexity and performance stability?\n\nPlease see answers above and our response to reviewer WeYu.\n\n>What are the generalization capabilities over problem scale of the proposed approach?\n\nIt is not quite clear what is meant by this question. Is this is about generalization to other problems, e.g., training on Max-Cut and testing on Vertex Cover? If that is what is meant by the reviewer,  OptGNN in that case will typically not be able to transfer its performance to different problems without further training. It is certainly an interesting question to explore whether pre-training on certain problems and fine-tuning on others can impact performance in a positive way.\n\n>What are the limitations of OptGNN? please explain in the text.\n\nThank you for pointing this out! We will make sure to discuss limitations and scaling in more detail in the paper.  Briefly, the main two limitations are that the applicability of our theoretical result only covers CSPs and not all CO problems.  Empirically, there is also the issue of \"rounding\" a convex relaxation to a integral solution, which is typically undertaken by a branch and bound tree search (i.e for producing a valid tour in the TSP). Tackling this issue is an important avenue for future work and would require non-trivial additions to our framework.  Please also see our response to reviewer Ubhy for the same question.\n\n\nAgain, we thank the reviewer for their comments. If this answer has addressed your concerns please consider raising your score. In any case, we will gladly respond to any further questions!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uBl7Da0gx3", "reviewer": "Reviewer_857L", "summary": "The papers propose graph neural architectures that can be used to capture optimal approximation algorithms for a large class of combinatorial optimization problems.", "questions": "NA.", "limitations": "Yes, the authors has provided limitations section.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper for the most part is well written with clear motivation.\n- The contributions made in the paper are manifold across various optimization problems like Max-cut, Min-vertex cover etc. and have shown commendable performance.\n- The paper also showcases a good theoretical basis.", "weaknesses": "No significant weakness as such. \nFig1. and Fig. 2 the visibility could be improved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and for appreciating both the empirical and theoretical elements of the paper's contributions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "buXcXHUyII", "reviewer": "Reviewer_Ubhy", "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.", "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": "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.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The logic of the paper in writing/presentation are absolutely easy to read and understand, and the project in design are reasonable.\n2. The proposal is presented with theoretical guarantees, i.e. the bounds of the optimal solutions are shown.\n3. The proposed framework OptGNN is easy to implement and the empirical studies are consistent and demonstrate the effectiveness of the proposal.\n4. The discussion of related work is extensive and satisfactory.", "weaknesses": "1. Take the example of Max-Cut problem as an example, how to show the optimization problem are the same in equation (2) and the message-passing diagram shown in equation (3)? Same for other optimization problems discussed in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. We are glad that the reviewer finds that the paper is well-presented and explained and that they value both the empirical and theoretical aspects of this work!\n\nNext, we address the weaknesses/questions in order:\n\n>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.\n\n\n Let's take the Max-Cut problem as an example (equation 1). To update the embedding $v_i$ corresponding to node $i$ we take the gradient of the Lagrangian $\\frac{\\partial{\\mathcal{L}(\\mathbf{v})}}{\\partial v_i}$.  The update will be as follows:\n$$ v_i' = v_i - \\eta \\frac{\\partial{\\mathcal{L}(\\mathbf{v})}}{\\partial v_i}.$$\nFor the Max-Cut problem, we can enforce the constraint by normalizing the embeddings. So we just need derivatives with respect to the objective from equation 1. It is hopefully easy to see that computing  $\\frac{\\partial{\\mathcal{L}(\\mathbf{v})}}{\\partial v_i}$  of the objective in equation 1 leads to the expression in the parenthesis in equation 2. The normalization for equation 2 enforces the constraint in equation 1. The central observation is that this kind of approach to minimizing the Lagrangian using gradient steps will lead to message-passing steps on the constraint graph for constraint satisfaction problems. In equation 3 we show a simple way to parameterize this message passing by adding learnable matrices.\n\nFor the question:\n>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?\n\nThe ratio is the clauses-to-variables ratio. This means that the higher the ratio the more constrained the instance will be, which will typically make it harder or potentially impossible to solve. More specifically, it is known that there is a phase transition point at a ratio of 4.26. Formulae with higher ratios than that become increasingly more likely to be unsatisfiable.  Formulae with ratios at this phase transition point are typically considered to be hard.\n\n>Limitations:\nBased 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.\n\n The main limitation of this work has to do with its applicability to different combinatorial optimization problems. The theoretical connection to optimal approximability results only holds for Max-CSPs. Of course, our method can be applied to essentially any SDP/polynomial optimization problem in practice. The main practical challenge in that case is enforcing the feasibility of the solutions. For example, consider the Travelling Salesperson Problem (TSP). In that case, our model requires a way of enforcing that the solutions produced by the model are valid tours. That would have to be solved with a post-processing step. Covering such cases is no trivial task and would require additional arguments and empirical work to be done in a clean and mathematically coherent way. We believe this is certainly a promising avenue for future work.\n\nAgain, we thank the reviewer for the comments and we will make sure to include an extensive discussion of the limitations in the final version of the paper. We would also like to encourage the reviewer to have a look at our responses to the other reviewers as well, in case that helps further clarify some of their concerns. We hope our response addresses the concerns of the reviewer! If the reviewer finds our answers satisfactory, we would be grateful if they could further increase their score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (spotlight)