On the Universality and Complexity of GNN for Solving Second-order Cone Programs
Authors: Ruizhe Li
Enming Liang
Minghua Chen
Venue: ICLR 2026 Poster (2026)
Keywords: graph neural network
second order cone programming
learning to optimize
Weisfeiler-Lehman test
sample complexity
Primary area: learning on graphs and other geometries & topologies
TL;DR: Graph neural networks can provably solve second-order cone programs.

Abstract: Graph Neural Networks (GNNs) have demonstrated both empirical efficiency and universal expressivity for solving constrained optimization problems such as linear and quadratic programming. However, extending this paradigm to more general convex problems with universality guarantees, particularly Second-Order Cone Programs (SOCPs), remains largely unexplored.
We address this challenge by proposing a novel graph representation that captures the inherent structure of conic constraints. We then establish a key universality theorem: *there exist GNNs that can provably approximate essential SOCP properties, including instance feasibility and optimal solutions*. We further derive the sample complexity for GNN generalization based on Rademacher complexity, filling an important gap for Weisfeiler-Lehman-based GNNs in learning-to-optimize paradigms.
Our results provide a rigorous foundation linking GNN expressivity and generalization power to conic optimization structure, opening new avenues for scalable, data-driven SOCP solvers. The approach extends naturally to $p$-order cone programming for any $p \geq 1$ while preserving universal expressivity and requiring no structural modifications to the GNN architecture. Numerical experiments on randomly generated SOCPs and real-world power grid problems demonstrate the effectiveness of our approach, achieving superior prediction accuracy with significantly fewer parameters than fully connected neural networks.

Published as a conference paper at ICLR 2026
ON THE UNIVERSALITY AND COMPLEXITY OF GNN SOLVING SECOND-ORDER CONE PROGRAMS
Ruizhe Li', Enming Liang**, Minghua Chen
*Department of Mathematics, Southern University of Science and Technology DDpaarmeett of Data Science, City University of Hong Kong School of Data Science, The Chinese University of Hong Kong, Shenzhen
ABSTRACT
Graph Neural Networks (GNNs) have demonstrated both empirical efficiency and universal expressivity for solving constrained optimization problems such as linear and quadratic programming. However, extending this paradigm to more general convex problems with universality guarantees, particularly Second-Orda Cone Programs (SOCPs), remains largely unexplored. We address this challenge by proposing novel graph representation that captures the inherent structure of conic constraints. We then establish a key universality theorem: there exist GNNs that can provably approxinate essential SOCP properties, such as instance feasibility and optimal solutions. We further derive the sample complexity for GNN generalization based on Rademacher complexity, filling an important gap for Weisfeiler-L wwweeiile--eehma--bbaeeee Lehman-based GNNs in provide a rigorous foundation linking GNN expressivity and generalization power conic optimization structure, opening new avenues for scalable, data-driven SOCP solvers. The approach extends naturally to p-order cone programming for any p 2 while preserving universal expressivity and requiring no structural modifications to the GNN architecture. Numerical experiments on randomly generated SOCPs and real-world power grid problems demonstrate the effectiveness of our approach, achieving superior prediction accuracy with significantly fewer parameters than fully connected neural networks.
paradigms. Our results
INTRODUCTION:
Second Order Cone Programming (SOCP) represents a fundamental class of convex optimization problems with numerous real-world applications (Lobo et al. 1998), including optimal power flow (Gan et al. 2014), trajectory planning (Liu et al. 2016), image restoration (Goldfarb & Yin 2005). signal processing (Shi et al. 2014), and network localization (Tseng) (007). However, traditional algorithms, such as primal-dus duua interior point methods, face computational limitations in large-scale applications, particularly in real-time scenarios where rapid response is crucial.
Recent advances in machine learning, such as the Searn-to-optimizz (L20) paradigm (Chen jtt al., 2022a [i & Malik 2016). have enabled solving optimization problems in real-time. Specifically, graph neural networks (GNNs) have been proven efficient in training by lever- aging the inherent graph structures of the prob- lem. For instance, lincar programs (LP) can be modeled as bipartite graphs with variable and constraint nodes (Chen al. 2022b), enabling efficient learning with a parameter sharing mech- Figure I: GNN expressivity for convex programs. anism over GPUs. Beyond empirical success, theoretical foundations, including universal approximation capabilities, have been established for
Convex Cone
p-order Cone (this work)
Second-Orde Cone (this work)
Convex Quadratic
Wu dl Cocrue di S02th
Linear
Witen es di Hioth NoA
GNN applications in (mixed-integer) LP (Chen al. 2022b 2023). quadratic programming (QP)
Chen et al. 2024b), and convex quadratically constraindd QP (Chen et al. 2024b Wu et al. 2024)
*Corresponding authors: Enming Liang (enming.cituu@gmmill waw.ityuuu@@mlllmmmmm.
Minghua Chen (minghua @ www.ccc.kccoo edu..en

---

Published as a conference paper at ICLR 2026
Despite these advances, extending GNNs more general convex programs like SOCP remains an open challenge. A key difficulty lies in the hybrid structure of second-order cone constraints, which involve both linear parts and non-linear norms. Effectively modeling the interplay between them and encoding constraints into graphs remains largely open. This paper proposes a novel GNN architecture with universal approximation capabilities for SOCPs, making the following contributions:
>> We propose a novel graph representation for SOCPs, which exploits linear relationships within the non-linear conic constraint and decomposes into separated nodes for efficient graph representations.
> Based on proposed graph representations, we design SOCP-GNNs, to predict the key properties of SOCPs, including instance feasibility and optimal solutions, with universal expressivity guarantees. Our GNN design and expressivity guarantees can be extended to p-order conic programming for p 2 1 without GNN structural modifications.
We further derive the sample complexity of the SOCP-GNNs for generalization. Such analysis is general and can also be extended to other Weisfeiler- Weisfeiler-Lchman-beee Lehsan- GNN approaches in the L20 community (Chen et al. 2022b 2023:
>>
Wu et al. 2024).
Our experiments demonstrate that the expressivity of designed GNNs, which use fewer parameters to achieve better prediction accuracy compared to fully connected NNs, in both the synthetic SOCP dataset and the real-world power grid optimization.
To the best of our knowledge, this is the first GNN design for SOCP with universal expressivity guarantees, and also the first work to analyze the generalization ability of Weisfeiler-Lehman--- GNNs designed in the L20 paradigm.
RELATED WORK
GNN Expressivity in L20 Paradigms: We review two primary paradigms for analyzing GNN expressivity for optimization problems: the Weisfeiler-Lehman (WL)-based and Algorithm- Algorithm-Unrooling bbued frameworks.
The WL-based framework models optimization problems as graphs, where nodes represent variables and constraints, with edges modeling their interactions. then links the GNN's expressive power with WL tests on graphs. Building on established foundations for (mixed-inte integer) linear programs (LP) (Chen al. 2022b 2023), researchers have extended this framework to more complex problems such as quadratic programs (QP) (Chen et al. (024b) and quadratically constrained QP (QCQP) (Wu et al. 2024). key challenge is representing non-linear constraints, as encoding complex interactions into nodes and edges is non-trivial. Recent work has addressed convex quadratic constraints through dynamic edge updates (Chen et al. 2024b) or augmented quadratic variable nodes (Wu et al, 2024). However, extending existing frameworks to represent general conic constraints like second-order cones remains an open question (see Appendix I.I for details).
The AU-based paradigm maps iterative steps of specialized algorithms (e.g., primal-dual methods) onto GNN layers. By aligning GNN layers with known algorithms for specific problems, such as LP Qian et al. 2024 Li et al. 2024a]] b. 2025a). QP (Qian & Morris 2025a Yang et al.) 2024a), and combinatorial problems (Yau et al. 2025 He & Vitercik, (202)). universality and parameter com- plexity can be naturally established through existing algorithmic convergence properties. However, representing more complex algorithmic steps involving non-linear operations (c.g.. factorization or projection) is non -on-taivial. Furthermore, the GNN's s expressivity is inherently limited by the underlying capability of the algorithm itself (see Appendix 1.1.2 for details).
Generalization of GNNs and L20: We briefly review several studies on the generalization ability of both GNNs and 1.20 paradigms (see Appendix A.2 for details).
To study the generalization capability of GNN and its variants, researchers have leveraged multiple ways, such as Vapnik-Cherronnnkke
dimension (Scarselli et al. [0188] Morris et al.) 2023 Franks let al. 2024 D I'Ivverno et al., 2025), Rademacher complexity (Garg et al. 2020; Pellizzoni et al.
2024), PAC-Bayes bound (Ju et al. 2023 Liao et al. 2020), and stochastic optimization (Tang & Liu 2023). However, these works cannot be directly applied to WL--based GNN frameworks under the L20 paradigm due to the continuous feature space of optimization problems and the difference
in GNN structures. The generalization performance of L20 or data-driven methods has also been studied from many perspectives, including VC dimension (and pseudo dimension) (Balcan al.
2

---

Published as a conference paper at ICLR 2026
2021b. loss landscape Yang al. 2023). and PAC-Bayes bound (Sucker & Ochs 2025 Stellato 2024). However, these works are not specifically designed for basea GNNs in L20 paradigms.
Sambharya
In this work, we extend the WL-based framework to optimization problems with second-order cone constraints, general class that encompasses L.,, QP, and convex QCQP, with extensive real-world applications. Our specialized GNN achieves universal expressivity capabilities while maintaining computational efficiency, establishing a foundational approach for extending GNNs to broader conic programming domains. Additionally, we provide the first generalization analysis for WL-based GNNs in the learning-to-optmmin to-optimize paradigm, establishing theoretical foundations for sample complexity when applying GNNs to solve optimization problems.
3 PROBLEM DEFINITION AND OPEN ISSUES
We consider general second-order cone programming (SOCP) (Alizadeh & Goldfarb 2003 as:
min SSSS
e TT
s.t. Fx S g, ||A,z + bill2 S of x + d, i [m]]
(1)
where decision variables are x R" and the problem parameters are e R", A R by R E R", di E R, F E Raxn g E RR, P", and r E R".
Open issue: While GNNs have successfully modeled linear and convex quadratic constraints with expressivity guarantees, handling more general second-order cone (SOC) constraints remains challenging. Additionally, the generalization capacity of GNNs for optimization problems remains largely unexplored. While previous work focused on expressivity, understanding how many training samples are needed for good performance over new instances is critical trustworthy applications.
METHODOLLOGY
We design the following layered graph representation to address the expressivity GNN for SOCP:
Graph Representation
Message Passing
Polyhedron condiralet
Second-Order Cone Program
(NN)
FiJ
Aua
Git
Esxsr
Varisble node by
1 bylls c dE
(b,)
(4,)
Minor conkc
Major contc constraint node
constraint node
The graph representation SOCPs and the message passing steps in GNN design. specific SOCP instance and its corresponding SOCP-graph are included in Fig. 6 Appendix B.4
Figure 2:
4.1 GRAPH REPRESENTATION OF SOCPs
As shown in Fig. 2gg22u the graph representation of an SOCP consists of four types of nodes, to represent decision variables (V1). polyhedron constraints (V2), minor conic constraints (Va), and major conic constraints (V.):
Vi = (e) denotes decision variables, where each node 2 is associated with a feature tuple (eg,y,,T)) representing the objective coefficient, variable lower and upper bounds.
V22 = { heE()) denotes polyhedron constraints equipped with feature (gx) for each node.
V3 = (ou { Fe denotes the minor conic constraint, where each node oa represents the i-th conic
tE(k.]
constraint's 1-th component, with feature (bx,)-
V4 {q: [e(m] denotes the i-th conic constraint with feature (d:)-
3

---

Published as a conference paper at ICLR 2026
Meanwhile, the SOCP graph includes four types of edges model the interactions between the decision variables and different constraint nodes:
Ejj Vi 1/2 denote the edges between the variable node Uj and the polyhedron constraint node Sk, with weight Fkj.
Gj,a E V1 x V33 denote the edge between variable node by and minor conic constraint node Oil with weight Ai,jj
Ejz E V1 x Va denote the edge between the variable node by and major conic constraint node qi. with weight Ci.j-
Est, E V/3 V4 denote the edge between node our and node ys with constant weight 1.
Remark 1 (Insights of Graph Design). For linear objectives and polyhedral constraints, our structure builds upon foundational works (Chen et al. 2022b). To deal with nonlinear second-order cone constraints, we exploit the linear relationships within the conic constraint, specifically, between A; and x, and between G and x. By representing the left-hand side and right-hand side as separate constraint nodes (V3 and V1), with linear interactions to decision nodes separately, and connecting V3 and Va via additional edges, we decompose the challenging nonlinear conic constraint into components amenable to efficient graph representations. Such decomposition and representation not limited to the second-order cone, and we provide more discussion after Theorem
Remark 2 (SOCP- + QCQF") One may note that SOC constraints, ||. + b/12 S c x + d. can be transformed into quadratic constraints by squaring both sides. potentially enabling the application of previous work on quadratic constraints (Wu et al. 2024 Chen et al., 2024b). However, this transformation introduces two significant challenges: (i) the resulting quadratic coefficient matrix A ALA - cc may not be positive semidefinite, rendering previous work theoretically inapplicable for such a non-convex QC; and (ii) the quadratic coefficient matrix A ec' may be dense, losing the potential sparse/low-rant rank structure of A and in the SOC constraint and making the graph representation and message passing inefficient.
Remark 3 (Convex QCQP + SOCP). Conversely, we may transform convex quadratic constraints < 0 into SOC constraints for more effective graph representation. For example, we can apply matrix decomposition Q LL" where L E R=xr, and reformulate the constraint as [[1 + x + d2: I'xx|] S c CT d2/2. Such a transformation is particularly efficient for low-rank matrices Q where <
of the form Qr + c
n. as it reduces the complexity of the graph representa- tion for original convex quadratic constraints, from quadratic node (Wu al. 2024) to minor conic constraint node via SOC graph representation. The convex quadratic objective in QCQP can also be converted to a linear objective by adding the epigraph constraint (Alizadeh & Goldfarb) (003). Thus, convex QCQP with variables and m quadratic constraints is equivalent to an SOCP with n + 1 variables and m + conic constraints (potentially low-rank). We further provide a quantitative comparison in the next section (Table 3)
4.2 MESSAGE PASSING IN SOCP-GNNS
Given the established graph representation of SOCPs, we propose message-passing (MP)-GNNs, consisting of an embedding layer, message-passing layers (each comprised of three sub-layers), and readout layer, detailed as follows:
Embedding Layer: For all nodes, the input features n,,, 10,s, 10:0, h:94 are initialized by embed- ding the node features into a hidden space Ao where hg the space dimension. Specifically,
he V. h =2()),) Vs V/2
0.0 + (h)), V vo V.
h0 21h))) V.
where of are learnable embedding functions for l = 1, 3, 4, and h" h², ht, h2 denotes the node features for E Vi, V2, o E Vs. E V4, respectively.
Message-Passinng Layer: As shown in Fig. 2 each message- message-passing layer consists of three sub- layers for updating the features of nodes with learnable functions ff gf For notation simplicity. Wij represents the weight of edge egj and (nn) (1,2,3, 3, 4) denotes the index of the node set for a node n.
Please refer Appendix
B.2 for detailed equivalent SOCP formulations.
4

---

Published as a conference paper at ICLR 2026
Updating for all constraint nodes (V1 V2 + V/3 + Vi): Vs V2 and Vn V3 U V4, update the embedding
h -gi (nree E eEV
hrm of hht Σ
WemnFro)-1(h""))
vEVi
Updating between major and minor conic constraint nodes (V3 + Vi and V4 Va): Vy E Va and Vo E V3, we update embedding as:
t - g4
h.. Σ
Won (angf((hee) 11t1o + h.o Σ
Wy (i
oEV3
4EV/
Vi): Vo E V1, we update the embedding as: Updating for variable nodes (V2 + V/3 + V4
h gô
h
Σ V
Wa fo
Wo Wo
Wy Sg
VeV3
The readout layer leverages a learnable function fout to map the node embedding T output by the T-th (i.e., last) y in desired output space IR", where is the output dimension. For example:
Readout layer:
passing layer for v E V12 U V2 U V33 Va, to readout
-Graph-level scalar output (e.g., predicting SOCP feasibility with a = 1):
y Soun (h, I2, Ia. I4)
Node-level vector output (e.g., predicting SOCP optimal solutions with n):
fout (1 (TTT.,, 11, 13.11)
where 7, ==Evv TT, I2 = E.evs TT, Is = =ooEVs hTi, 14 Egeev hTa
As mentioned in Remarks 2 and our SOCP-GNN also efficiently handles con- vex QCQPs by reformulating them into SOCP. Based on the GNN architecture de- scribed above, we analyze both the node and message passing complexity compared to previous works on convex QCQP (Wu al.) 2024 Chen et al.] 2024b). Our SOCP-GNI achieves the same order node and message passing complexity state-of-the-art GNNs designed specifically
Num. of Nodes
MP Complexity
Wi et al.
2024
O(n + m)
On + +mn") ((mn
et
2024b
O (mm)
Ours
On E
O(n Σ rs)
Figure 3: Complexity comparison of GNNs for vex QCQP with n variables, m quadratic constraints, and quadratic coefficient matrix ranks r; S n, = O...., where = indicate the quadratic matrix from objective.
for QCQP with general parameter coefficients. practice, the coefficient matrices may exhibit sparse or low-rank structure, resulting in different empirical performance: (i) When the quadratic coefficients Q; are sparse, previous GNNs benefit from reduced connections and message passing. After reformulating to SOCP via decomposition Q LiLl the resulting graph may lose this sparsity. However, structured sparse matrices (e.g.. banded or block diagonal (Davis) (2066] Golub) & Van Loan 2013)), sparsity is preserved in the COCP-graphh and our SOCP-GNN inherits the computational benefits. (ii) When the quadratic matrices exhibit low-rank structure, SOCP-GNN becomes more efficient with reduced graph size and message passing complexity.
Therefore, SOCP-GNN not only extends theoretical applicability to the broader class of SOCP beyond convex QCQPs, but also maintains competitive computational complexity when restricted to the convex QCQP subclass. See detailed discussion in Appendix B.5
UNIVERSALITY OF SOCP-GNN
With the established graph representation and corresponding GNN, we formally prove the universality of the GNN for predicting key properties of SOCPs, like the instance feasibility and optimal solutions.
5

---

Published as a conference paper at ICLR 2026
5.1 BASIC DEFINITIONS
Definition 5.1 (Spaces of SOCP-Graphs). Let SOCP for all SOCPs with variables, m conic constraints with dimension :1...., km. and b polyhedron constraints.
gt..m.......... denote the set of graph representations
Definition 5.2 (Spaces of SOCP-GNNs). Let ww..m.k.....mm &m (I8a) be the set of message passing SOCP
gg.m.......... to target output in R Each GNNs proposed in Sec. 4.2 that map the input graph in SOCP
GNN is parameterized by continuous embedding functions S. l2 [4]. continuous hidden functions in the message passing layers si. [6] and fig [8). and the continuous readout function, fout-
Definition 5.3 (Target mappings P. Let Gsocp be graph representation of SOCP problem. We define the following target mappings.
Feasibility mapping: ieas (GsocP) 1 the SOCP is feasible and Preas (9soCP) otherwise.
Optimal solution mapping: (950CP) = x², where x" is the optimal solution of the SOCF
5.2 SEPARATION POWER OF THE SOCP WEISPEILER-LEMMAN TEST
To investigate the relationship between target properties and SOCP-GNNs, we first analyze the separation power of SOCP-GNNs. The separation power of traditional GNNs is closely related the Weisfeiler-Lehme
(WL) test (Weisfeiler & Leman 1968). classical algorithm to identify whether two given graphs are isomorphic. To apply the WL test on SOCP-graphs, we design a modified WL test, called the SOCP-W WL test, in Algorithm | Below, we provide the main theoretical result about the separation power of the SOCP-WI test.
Theorem 1. Let I, I (with given sizes m. km,...,km.bb encoded by G, G E @soe two SOCP instances. If the G and G cannot be distinguished by the SOCP- WL test, then: For any target mapping 4 -SoCP gi..m......om
gr.m.......km... be
R.. ( (G) always holds up to permutations.
The detailed proof can be found in Appendix C By Theorem
that: any two instances
which the SOCP-WL test cannol separate share the same larget property we want (up to permutations). Hence, demonstrating SOCP-GNI is equivalent to SOCP-WI. guarantees its sufficient separation power, as shown in Appendix
5.3 UNIVERSAL APPROXIMATION SOCP-GNNS
Beyond separation power, expressive power (i.e., approximation capability) ) is also critical. Here, provide the main theoretical results to validate the SOCP-GNN's universal expressivity for SOCP ie., there always exists SOCP-GNN that can universally approximate target mappings in Def. 3.3 within given error tolerance:
Theorem 2. For any Borel regular probability measure P on the space of SOCPs GD.mm ki.....m....
any larget mapping 9 gn..m.k......ia Rea defined in Def. 5.3 and any 8,e 0, there exists
F E SOCP
mmm. km. (I2.) such that:
((([)((SOOC)) (G 8) <e.
The detailed proof is provided in Appendix expressivity of the proposed SOCP-GNNs. The high-level proof structure follows established foundations for LP in (Chen et al.) 2022b). However, previous graph design and expressivity proof not directly be extended the challenging non-linear SOC constraints. To this end, we leverage the equivariance, convexity, and separabiliry of the Eg norm in SOC, and then establish the expressive power proposed CDCP-GNNs, We further extend the universal expressivity of the proposed GNN to p-order cone programming in Appendix C.6, since the core lemmas in our proof are also satisfied for the Ep norm.
C This Theorem formally establishes the universal
"For target mappings, please refer Def. B.1 Theorem also holds for these target mappines.
"Since SOCP may admit multiple optimum, we choose the one with minimum la norm (Chen et al. 2022h *Please refer to those definitions in Definition C.2 and C.3

---

Published as a conference paper at ICLR 2026
6 GENERALIZATION ABILITY OF SOCP-GNNS
Beyond expressivity, the generalization capability of GNNs, i.e., how many samples are needed for training achieve good performance on unseen instances, is critical for real-world trustworthy applications. While previous foundational works have focused on expressivity (Chen et al. 2002b 2024b), the generalization ability of GNNs designed for optimization remains largely unexplored. Addressing this gap, our work takes an initial step towards formally analyzing the generalization properties of these models.
with bounded parameters (e, {A,]]² (be 1= (c )m :==: {d, )d P. P.g, I,), and denote N as the problem size, i.e., the total dimension of all parameters. Without loss of generality, it is sufficient to consider the problem parameters lic in ball B, = { |||=]122 S ri with some positive radius 7j.
We consider subclass of SOCP problems denoted as X C Ssocr I
F ((R") said to be Lipschitz with respect to the input domain X' if and only if 3L > 0 such that for each output component fi, [f(()) - fx(2)) S -| - x'll holds for all x, x' E X. And denotes the Lipschitz constant of f.
Definition 6.1 (Lipschitz GNN). A SOCP-GNN f E SUCP
We also assume the GNN is Lipschitz (Def. 6.1 and denote all the FOCP-GNNY whose Lipschitz constant is no more than L with respect to the input domain B,, S RN by AL.N. We remark that this Lipschitz assumption is widely adopted in related works on the sample complexity/generalllello
ability of graph neural networks (Pellizzoni et al. 2024 Garg et al. 2020 Tang & Liu 2023 Huang et al. 2024a). The Lipschitz condition holds in general if both the input domain and the parameter space are bounded, while the GNNs are differentiable with respect to the inputs and parameters. We then present the main theorem for the generalization capability of our GNN:
Theorem 3 (Generalization Bound for SOCP-GNNs). Consider the hypothesis class AI. of SOCP- GNNs with outputs in y and input SOCP instances X with parameters in Br. Let D be the uniform distribution over X. Assume the loss function é: y x y + R is bounded by p and q-Lisschitz with respect to the first parameter when the second parameter is fixed. For a training set S of m samples drawn i...d. from D, let ht arg Ai, LD (h the population risk minimizer and hg = arg minke (h) be the empirical risk minimizer. Then with probability at least - 8:
LD(hs) LD") S Crank B(m, N, L, 22pp222ggg0 2log(1/8))
where the complexity term is B(m, N, L,r) = inf 1e + S. C(v) do], with C(v) =
min((2Zx,) 1))" log 22r + 2). The lusk-dependent constant are defined as: Crast 4q for graph-level predictions with outputs in [-r,r); and Canck 422ng for node-level predictions with oufputs in [-r,r]"_ Here, n denotes the number of decision variables.
- (ALn)te)N
The conditions in Theorem are satisfied by many common loss functions, including margin loss and MSE loss under mild regularity conditions. Theorem 3 provides the first sample complexity analysis for WL-test based GNNs, particularly SOCP-GNN establishing solid theoretical foundation for task-specific sample complexity research. As demonstrated in Theorem 3 sample complexity deteriorates as GNN complexity or problem dimension increases (i.e., as L or N grows larger). This relationship is directly evident from the
The detailed proof can be found in Appendix D.3
proofs in Theorems 13 and 14
Remark 4. We also analyze the VC dimension and pseudo dimension of SOCP- with scalar outputs in Appendices [DI [nd respectively, for SOCPs whose parameters can be encoded into discrete labels (e.g., problems where all coefficients are binary-valued,. However, these theoretical results reveal practical limitations: for continuous problem parameters typical in real-world SOCPs, the resulting VC and pseudo dimensions are often infinite. This necessitates more powerful analytical tools capable of handling continuous feature spaces, such as Theorem 3 Under the same assumptions as Theorem 3 our theoretical framework extends directly to other distributions over different SOCP problems and other WI.-based approaches in L.20 paradigms, since the application of Tonelli's theorem, Jensen's 's inequality, and contraction lemmas all remain valid as proven in Appendix D33
$ 'Here, the population(true) risk is defined as T.p (h) Rg-D (1((x))) v(z))) and the empirical risk for training set is defined as Eerg ((h()))p(()) where y(x) is the true label of SOCP instance x, c.g. objective value.
[8]
7

---

Published as a conference paper at ICLR 2026
7 NUMERICAL EXPERIMENTS
In this section, we demonstrate the efficiency of the proposed SOCP-GNN on both synthetic SOCP instances and real-world power grid optimization problems.
To validate the empirical advantages of SrCP-Graphs (Sec. we employ a fully-connected neural network (FCNN) one baseline, where the FCNN receives the same problem parameters as input in vectorized form. This comparison isolates the benefits of the graph structure inherent in SOCP-GNT relative to a standard neural network approach. To validate the designed message- passing mechanisms (Sec. (4.2). we compare our SOCP-GNN with vanilla Message Passing Neural Network (MPNN) Gilmer al. 2017) and Graph Isomorphism Network (GIN) (Xu al., 2019). We note that no existing graph representation has been specifically designed for SOCP problems with non-linear constraints. Therefore, we compare all of those GNN-based baselines to the same graph structure proposed in this work. Notably, vanilla MPNN and GIN perform message passing based on the adjacency relationships, whereas our approach incorporates well-designed constraint-to- variable and variable-to-consttaii message passing. While SOCP instances can be reformulated as QCQP, previous QCQP- GNN (Wu et al., 2024 Chen et al. 2024b) do not provide publicly available implementations, and more importantly, they lack theoretical universal approximation guarantees for SOCP instances since the associated quadratic constraints are not necessarily positive semidefinite. Consequently, focus our experimental comparison on vanilla MPNN, GIN and FCNN baselines.
7.1 SYNTHETIC SOCP INSTANCE
For dataset generation, we randomly sample coefficient matrices and constraint parameters following the CVXPY example code structure and parameter settings (Chen et al., 2024b). Each instance is solved in CVXPY to obtain ground truth solutions, forming our training dataset. We then train SOCP-GNN using regular supervised learning procedures for optimal solution predictions. We also test the feasibility classification in Appendix
4(b) and 4(c) we compare the solution relative error Of our SOCP-GNN against the FCNN, Vanilla MPNN, and GIN baselines across three different problem scales over 100 training epochs. COCP-GNN demonstrates superior performance across all scales, achieving substantially lower error on both training and validation sets. For the large-scale 500-dim SOCP with input dimension 452, 400, our GNN achieves better prediction accuracy while using only 0. 35Mb parameters compared 11 1Mb for the FCNN baseline (shown in Fig. [(C) 300x reduction in model complexity. This demonstrates SOCP-GNN's parameter efficiency and its ability to effectively learn target mappings in SOCPs by leveraging the natural sparse graph structure of these problems. All graph-based neural networks outperform FCNN significantly on synthetic datasets, further validating the effectiveness of our graph representation. Notably, SOCP-GNI substantially surpasses other GNN baselines, demonstrating the advantage of SOCP-GNN three-sublayer message passing mechanism over methods relying solely on adjacency relationships.
As shown in Fig. 4(a)
7.2 SoC- BASED OPTIMAL POWER FLOW
Optimal power flow (OPF) is the fundamental problem in power systems optimization, determining the most economical operating point while satisfying all constraints. The second-order cone (SoC) relaxation transforms the non-convex AC power flow equations into tractable convex conic forms (see formulations in Appendix E). This relaxation is exact for radial networks and provides near-optimal solutions for meshed transmission systems (Gan et al. 2014 Madani et al. 2014), making it preferred for real-time operations
We evaluate SOCP- GNN on IEEE test systems ranging from 118 to 500-bus power grids (Babaeine jadsarookolace et al. 2019). For each grid, we generate problem instances by randomly varying load
'The solution relative crror (Chen et al. 2024b) between prediction and ground truth x² as m 1-
|a-2"18
"We note that GNN-based methods have been directly applied to non-convex AC-OPF problems using the physical graph structure of power grids (Yang et al. 2024h Owerko al. 2020 Varbella et al. 2024). However, we do not compare with these methods directly because: (1) the SOC relaxation provides lower bound the original OCF problem, making direct performance comparison unfair, and (2) our focus is on demonstrating
GNN universality for convex SOC-relaxed problems. Nevertheless, extending our theoretical framework to establish universality guarantees for non-convex AC-OPF remains important direction for future work with significant practical value.
8

---

Published as a conference paper at ICLR 2026
FCNN
GIN
MPNN
SOCP-GNN
Sallion Sallinn Rulevve Bri
Solilon Ralldiva Error
10"
22"
90
Epocc
Training Eooch
Trathing Epoch
(a) 50-dim SOCP
(b) 100-dim SOCP
500-dim SOCP
Soluton Relatve Ennor
Soldion Relefiv Erie
10"
Sokutinn Roiaivee
R0"
10"
10"
10
Training Eboch
Traning Epoch
Training Epoco
(d) 118-bus grid
(c) 200-bus grid
(f) 500-bus grid
Figure 4: (a)-(c): Performance comparison in predicting solutions of synthetic SOCP instances. The SOCP size are (50, 10, 10), (100, 50, 50), and (500, 100, 100), respectively. (d)-(f): Performance comparison in predicting solutions of SoC-OPF. The SOCP size are (596, 854, 555), (764, 1288, 732), and (2182, 3454, 2181), respectively. Here, we denote the size of an SOCP instance by tuple (n, b, m). where n represents the number of decision variables, b denotes number of polyhedral constraints, and m indicates the number of second-order cone constraints. The total input parameters for an SOCP (n, b, m) are of dimension O(n (b m)).
demands and generator costs, and introducing random line outages (i.e., loss of line connection) to simulate realistic operational scenarios. We compare against CVXPY with MOSEK solver CPU) and learning- based approaches, including various GNNs and FCNN (on both CPU and GPU for fair comparison). Results in across all problem scales with significantly fewer parameters than the FCNN baseline in real-world scenarios. For real-world OPF problems with sparse structures, SOCP-GNT performs better than on randomly generated instances in both prediction errors and inference time (shown in Fig. 5(a) and Fig. 5(b),, highlighting the potential for real-world applications. Consistent with the results obtained from the synthetic dataset, experiments of our graph representation and the benefits of our three-layer message passing mechanism.
[(e) and 4(f) show that SOCP- COCP-GNN achieves lower errors
real-world OPF problems further demonstrate the effectiveness
7.3 EMPIRICAL STUDY ON SAMPLE/MODEL COMPLEXITY AND SIZE GENERALIZATION
In this section, we investigate the performance of SOCP-GNNs under different model sizes and training samples. The detailed experiment settings can be found in Appendix F.4 As shown in Fig. 5(a) 5(d) SOCP-GNNs are both scalable and fast at solving SOCPs with superior accuracy. Since the learnable functions are applied feature-wise. independent of the number of nodes and edges, the memory cost of SOCP-GNNS remains constant across different problem sizes. We then analyze the sensitivity of SOCP-GNN to different hidden sizes and training samples as shown in Fig. 5(e) Both training and validation losses decrease hidden layer size number of training samples increases, demonstrating the model's capacity to benefit from additional parameters and data while validating Theorem 3.
To further validate the Lipschitz assumption in Theorem 3 we use projected optimization method (Gouk et al. 2020) to control the Lipschitz coefficient of SOCP-GNN. The results be found in Appendix F.3 From the result, we can see that: the generalization gap decreases as the model becomes less complex (i.e. decrease the Lipschitz constant I. of SOCP-GNN) the train

---

Published as a conference paper at ICLR 2026
CVXPY
FCNN (GPL)
GIN (GPU)
MPNN (GPU)
SOCP -NN (GPU)
FONN (CPU) *...... GIN (CPU)
MPNN (CPU)
SOCP-GNN (CPU)
Mosil Shae 0181
Mabil Skyy (M8)
10
020
1900
206
120
230
330
430
600
102
257
350
400
500
Vars
Nam. df
(a) SOCP solving time (b) SoC-OPF solving time (c) Model size SOCP (d) Model size in SoC-OPF
Bidden Stze
1idder Layer Sia
Ax13
1:33
8:222
6013
9421
6412
6.44
Train Lone
Dmmention Tramnng
Vastasoon
6011
40.
1331
842
0.0
-42
160
4:00
4.4
1250
2500
5000
Numbe of Bamplea
Number of Samples
Dimmssiona Teating Iradtercaa
(e) SOCP-GNN training loss (Left) and validation loss (Right) under Training and Testing of SOCP. different hidden-layer embedding sizes and number of training samples. GNN on different problem sizes.
Figure 5: (a)-(d): inference time and model size comparison between GNN and FCNN in SOCP and SoC-OPF problems. (e): sensitivity analysis of GNN on mudden-layer embedding sizes and number of training samples. (f): generalization ability analysis of GNN on SOCP problems of different sizes.
increases. This enhances the tradeoff between the expressive power and generalization ability of SOCP-GNNs, as indicated in Theorem 3
We also investigate the size generalization capability from small to large-scale problems, with results
shown in Fig. 5(f) Models trained on larger training samples perform well on smaller testing instances, while those trained on small samples generalize less effectively to larger SOCP instances. This observation motivates further research to theoretically characterize the size generalization ability of GNN training (Huang et al.) 2024b).
CONCLUSIONS, LIMITATIONS, AND FUTURE WORKS
This paper introduces a novel graph representation for SOCP, a fundamental class of convex optimiza- tion problems covering LP, QP, and convex QCQP. We design novel GNN architecture that exploits inherent SOC structure for predicting key properties, including fcasibility and optimal solutions, with established universal expressivity guarantees. Our framework extends p-order cone programming. broadening GNN applicability a subclass of conic and polynomial optimization. We establish the first general framework for analyzing the generalization capability of SOCP- or other WL-based GNNs, bridging an important research gap. Comprehensive experiments validate both our theoretical predictions and practical performance.
While our work establishes universality and sample complexity guarantees, several important limi- tations suggest promising future directions. The parameter complexity of GNNs for optimization problems remains a significant challenge shared by prior WL-test-based frameworks. One promising avenue involves combining algorithm-unrollin approaches with the WL--hased framework develop unified theoretical analysis of GNNs for optimization. Another important direction is extending the GNN paradigm beyond convex settings to handle semidefinite programs and general polynomial optimization problems. Such extensions would require developing new graph representations and theoretical frameworks capable of capturing the more complex thermore, exploring metrics beyond the naive & norm for the SOCP parameter space is crucial. An optimization-pront property-aware distance could significantly lower the covering number by better fitting the problem's intrinsic structure, directly yielding tighter generalization bound.
relations. Fur-
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENT
This work is supported in part by a General Research Fund from Research Grants Council, Hong Kong (Project No. 11200223), a Collaborative Research Fund from Research Grants Council, Hong Kong (Project No. C1049-24G), an InnoHK initiative, The Government of the HKSAR, Laboratory for AI-Powered Financial Technologies, a Shenzhen- Hong Kong-Macce Macau Science & Technology Project (Category C, Project No. SGDX202205301 10000000001000266000 and Start-up Research Grant from The Chinese University of Hong Kong. Shenzhen (Project No. UDF01004086) The authors would also like to thank the anonymous reviewers for their helpful comments. This work has previously been presented at the NeurIPS 2025 ScaleOPT workshop
(Li et al. 2025b).
LLM USAGE
Large Language Models (LLMs) were used to aid in the writing and polishing of the manuscript.
REFERENCES
Farid Alizadeh and Donald Goldfarb. Second-order cone programming. Mathematical programming. 95(1):3-51, 2003.
Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural networks. arXiv preprint arXiv:2006. 15646, 2020.
Sogol Babaeinejadsarrooollee Adam Birchfield, Richard D Christie, Carleton Coffrin, Christopher DeMarco, Ruisheng Diao, Michael Ferris, Stephane Fliscounakis, Scott Greene, Renke Huang, et al. The power grid library for benchmarking ac optimal power flow algorithms. arXiv preprini 1rX8::1908.007888 2019.
Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data sufficient to learn high-performing algorithms? generalization guarantees for data-driven algorithm design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 919-932, 2021.
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch: Generalization guarantees and limits of data-independent discretization. Journal of the ACM, 71 (2):1-73, 2024.
Qian Chen, Tianjian Zhang, Linxin Yang, Qingyu Han, Akang Wang, Ruoyu Sun, Xiaodong Luo, and Tsung-Hui Chang. Symilo: A symmetry-aware learning framework for integer linear optimization. Advances in Neural Information Processing Systems, 37:24411-24432 2024a.
Qian Chen, Lei Li, Qian Li, Jianghua Wu, Akang Wang, Ruoyu Sun, Xiaodong Luo, Tsung- Hui Chang, and Qingjiang Shi. When gnns meet symmetry ilps: an orbit-based feature augmentation approach. arXiv preprint 2xXi:22501.1421, 2025.
Tianlong Chen, Xiaohan Chen, Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang, and Wotao Yin. Learning to optimize: A primer and benchmark. Journal of Machine Learning Research, 23(18)):1-59 2022a.
Ziang Chen, Jialin Liu, Xinshang Wang, Jianfeng Lu, and Wotao Yin. On representing linear programs by graph neural networks. arXiv preprint arXiv:2209. 12288, 2022b.
Ziang Chen, Jialin Liu, Xinshang Wang. Jianfeng Lu, and Wotao Yin. On representing mixed-intege linear programs by graph neural networks, 2023.
Ziang Chen, Xiaohan Chen, Jialin Liu, Xinshang Wang, and Wotao Yin. Expressive power of graph neural networks for (mixed-integer) quadratic programs. arXiv preprint 0rXiv:2400.055388 2024b.
Ziang Chen, Jialin Liu, Xiaohan Chen, Xinshang Wang, and Wotao Yin. Rethinking the capacity of graph neural networks for branching strategy. arXiv preprint arXiv:2402.07099 2024c.
11

---

Published as a conference paper at ICLR 2026
Timothy A Davis. Direct methods for sparse linear systems. SIAM, 2006.
Giuseppe Alessio D' I'Inveoo, Monica Bianchini, and Franco Scarselli. Ve dimension of graph neural
networks with pfaffian activation functiions. Neural Networks, 182:106924, 2025. ISSN 0893 6080. doi: /tt.i//ncc/aartccccaa/////////// com/ hamm/ccience/eaee
106924. URL httpt::///// /wwp://wwww/..... www..cci. www.w..ww.........cccwwwww encedi rect
Adam N Elmachtoub and Paul Grigas. Smart "predict, then optimize". Management Science, 68(1):
9-26, 2022.
Billy Franks, Christopher Morris, Ameya Velingker, and Floris Geerts. Weisfeiler-leman at the margin: When more expressivity matters. arXiv preprint arXiv:2402.07568, 2024.
Lingwen Gan, Na Li, Ufuk Topcu, and Steven H Low. Exact convex relaxation of optimal power flow in radial networks. IFEE transactions on automatic control, 60(1):72-8772011 2014.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. International conference on machine learning, pp. 3419-3430. PMLR, 2020.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combina- torial optimization with graph convolutional neural networks, 2019.
Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In International conference machine learning, pp- 1263-1272. Pmir, 2017.
Donald Goldfarb and Wotao Yin. Second-order cone programming methods for total variation-based image restoration. SIAM Journal on Scientific Computing, 27(2):622-645, 2005.
Gene H Golub and Charles F Van Loan. Matrix computations. JHU press, 2013.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE international joint conference on neural networks, 2005., volume pp. 729-734. IEEE, 2005.
Henry Gouk, Eibe Frank, Bernhard Plahringer, and Michael J. Cree, Regularisation neural networks by enforcing lipschitz continuity, 2020. URL http:tss//a.xii.oo/////////////s 1804. 04368
Yuhang Guo, Zicheng Su, Hai Yang, Enming Liang, Chen Zhong, and Wanjing Ma. A smart predict-then-optimize framework for vehicle rebalancing problem. Transportation Research Part B: Methodological, 103411, 2026.
Yu He and Ellen Vitercik. Primal-dual neural algorithmic reasoning, 2025.
Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanie Jegelka, and Pan Li On the stability of expressive positional encodings for graphs, 2024a.
Zheng Huang, Qihui Yang. Dawei Zhou, and Yujun Yan. Enhancing size generalization in graph neural networks through disentangled representation learning. In Proceedings of the 41st International Conference on Machine Learning, pp. 20365-20388 2024b.
Haotian Ju, Dongyue Li, Aneesh Sharma, and Hongyang Zhang. Generalization in graph neural networks: Improved pac-bayesian bounds on graph diffusion. In International conference artificial intelligence and statistics, pp. 6314-6341. PMLR, 2023.
Bingheng Li, Linxin Yang, Yupeng Chen, Senmiao Wang, Qian Chen, Haitao Mao, Yao Ma, Akang Wang, Tian Ding, Jiliang Tang, et al. Pdhg-unrolledd learning-to-optiiien to-optimize method for large-scale linear programming. arXiv preprint arXiv:2406.01990 2024a.
Ke Li and Jitendra Malik. Learning to optimize, 2016. URL ptttps://arxiv.. baog/abb/// 1500
01885
12

---

Published as a conference paper at ICLR 2026
Qian Li, Tian Ding, Linxin Yang, Minghui Ouyang, Qingjiang Shi, and Ruoyu Sun. On the power of small-size graph neural networks for linear programming. In The Thirty-eighth Anmual Conference on Neural Information Processing Systems, 2024b.
Qian Li. Minghui Ouyang, Tian Ding, Yuyi Wang, Qingjiang Shi, and Ruoyu Sun. Towards explaining the power of constant-depth graph neural networks for linear programming. In The Thirleenth International Conference on Learning Representations, 2025a.
Ruizhe Li, Enming Liang, and Minghua Chen. On the expressivity of gnn for solving second order cone programming. In NeurlPS Workshop on GPU-Accelerated and Scalable Optimization, 2025b.
Xinpeng Li, Enming Liang, and Minghua Chen. Gauge flow matching for efficient constrained generative modeling over general convex set. ICLR 2025 Workshop on Deep Generative Model in Machine Learning: Theory, Principle and Efficacy, 2025c.
Xinpeng Li, Enming Liang, and Minghua Chen. Gauge flow matching: Efficient constrained genera- tive modeling over general convex set and beyond. In The Fourteenth International Conference on Learning Representations. ICLR, 2026.
Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. T2t: From distribution learning in training to gradient search in testing for combinatorial optimization. Advances in Neural Information Processing Systems, 36:50020-50040, 2023.
Enming Liang and Minghua Chen. Generative learning for solving non-convex problem with multi- valued input-solution mapping. In 12th International Conference on Learning Representations (ICLR 2024). ICLR, 2024.
Enming Liang and Minghua Chen. Efficient bisection projection to ensure neural-network solution feasibility for optimization over general set. In Proceedings of the Forty-second International Conference on Machine Learning. PMLR, 2025.
Enming Liang, Minghua Chen, and Steven H Low. Low complexity homeomorphic projection to ensure netral-network solution feasibility for optimization over (non-) convex set. Proceedings of the 40th International Conference on Machine Learning. PMLR, 2023.
Enming Liang, Minghua Chen, and Steven H Low. Homeomorphic projection to ensure neural- network solution feasibility for constrained optimization. Journal of Machine Learning Rexearch, 25(329):1-55, 2024.
Renjie Liao, Raquel Urtasun, and Richard S. Zemel. A pac-bayesian approach generalization bounds for graph neural networks. CoRR, abs/2012.07690, 2020.
Jialin Liu, Lisang Ding, Stanley Osher, and Wotao Yin. Implicit models: Expressive power scales with test-time compute. arXiv preprint arXiv:2510.03638, 2025.
Xinfu Liu, Zuojun Shen, and Ping Lu. Entry trajectory optimization by second-order cone program- ming. Journal of Guidance, Control, and Dynamics, 39(2):227-241, 20166.
Miguel Sousa Lobo, Lieven Vandenberghe, Stephen Boyd, and Hervé Lebret. Applications of second-orde cone programming. Linear algebra and its applications, (84(1-3):193-23)) 1998.
Ramtin Madani, Somayeh Sojoudi, and Javad Lavaei. Convex relaxation for optimal power flow problem: Mesh networks. IEEE Transactions on Power Systems, 3091)1199-211, 2014.
Jayanta Mandi, James Kotary, Senne Berden, Maxime Mulamba, Victor Bucarey, Tias Guns, and Ferdinando Fioretto. Decision-Focusee learning: Foundations, state of the art, benchmark and future opportunities. Journal of Artificial Intelligence Research, 80:1623-1701. 2024.
Ian Horrocks Matthew Morris, Bernardo Cuenca Grau. Orbit-equivariant graph neural networks. In 2024 The International Conference on Learning Represeettations((ILRR)) pp. 7056-7062. ICLR, 2024.
Andreas Maurer. A vector-contraation inequality for rademacher complexities. In International Conference Algorithmic Learning Theory, pp. 3-17. Springer, 2016.
13

---

Published as a conference paper at ICLR 2026
Christopher Morris, Floris Geerts, Jan Tönshoff, and Martin Grohe. WI meet In International conference on machine learning, Pp. 25275 25302. PMLR, 2023.
Damian Owerko, Fernando Gama, and Alejandro Ribeiro. Optimal power flow using graph neural networks. ICASSP 2020-2020 JEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5930-5934. IEEE, 2020.
Xiang Pan, Tianyu Zhao, Minghua Chen, and Shengyu Zhang. Deepopf: deep neural network approach for securty-constrringg de optimal power flow. IEEE Transactions on Power Systems, 36(3):725-11355, 2020.
Xiang Pan, Minghua Chen, Tianyu Zhao, and Steven H Low. Deepopf: A feasibility-opmmized deep neural network approach for ac optimal power flow problems. IEEE Systems Journal, 17(1): 673-683, 2022.
Paolo Pellizzoni, Till Hendrik Schulz, Dexiong Chen, and Karsten Borgwardt. On the expressivity and sample complexity of node-individualized graph neural networks. Advances in Neural Information Processing Systems, 17:120221-1202511 2024.
Chendi Qian and Christopher Morris. Towards graph neural networks for provably solving convex optimization problems. arXiv preprint 2502:2250..02446, 2025a.
Chendi Qian and Christopher Morris. Principled data augmentation for learning to solve quadratic programming problems. arXiv preprini arXiv:2506.0172 2025b.
Chendi Qian, Didier Chételat, and Christopher Morris.
Exploring the power of graph neural networks in solving linear optimization problems. In International conference on artificial intelligence and statistics, pp. 1432-1440. PMLR, 2024.
Rajiv Sambharya and Bartolomeo Stellato. Data-driven performance guarantees for classical and learned optimizers, 2024.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008
Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The vapnik-chervonenkk dimension of graph and recursive neural networks. Neural Networks, 108:248 251,2018
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Mohamed Shamseldein. A hybrid gnn-Ise method for fast, robust, and physically-coonsiseet ac power flow. Electric Power Systems Research, 252: 12380, 2026.
Qingjiang Shi, Weiqiang Xu, Tsung- Chang, Yongchao Wang, and Enbin Song. Joint beamforming and power splitting for miso interference channel with swipt: An socp relaxation and decentralized algorithm. IEEE Transactions on Signal Processing, (2(23):6194-6200 2014.
Michael Sucker and Peter Ochs. A generalization result for convergence in coaming-to-optimine 2025.
Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. Advances in neural information processing systems, 0013770667331. 2023.
Huayi Tang and Yong Liu. Towards understanding generalization of graph neural networks. In Proceedings of the 40th International Conference on Machine Learning. PMLR, 2023.
Paul Tseng. Second-order cone programming relaxation of sensor network localization. SIAM
Journal on Optimization, 18( 1):116-118 2007.
Anna Varbella, Damien Briens, Blazhe Gjorgiev, Giuseppe Alessio D D'Invero,, and Giovanni Sansavini. Physics-informed gnn for non-linear constrained optimization: Pinco a solver for the ac-optimal power flow, 2024. (tLL:httpss//aaxiiirrr//a//////
04818
14

---

Published as a conference paper at ICLR 2026
Martin J. Wainwright. High-Dimmessinn Staristics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
B. Ju. Weisfeiler and A. A. Leman. A reduction of a graph to a canonical form and an algebra arising during this reduction. Meuchno--Tkkmicheeee
Informatsiya, Seriya 2, (9):19-21, 1968.
Chenyang Wu, Qian Chen, Akang Wang, Tian Ding, Ruoyu Sun, Wenguo Yang, and Qingjiang Shi. On representing convex quadratically constrained quadratic programs via graph neural networks. arXiv preprint arXiv:2411.13800 2024.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019. URL https
//openreview. net/ hatp://ueeee.ntttffoorrmeee/eege
Jiaqi Yang, Enming Liang. Zicheng Su, Zhichao Zou, Peng Zhen, Jiecheng Guo, Wanjing Ma, and
Kun An. Dff: Decision-focused fine-tuning for smarter predict-then-optime with limited data. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 26868-26877 2025.
Junjie Yang, Tianlong Chen, Mingkang Zhu, Fengxiang He, Dacheng Tao, Yingbin Liang, and Zhangyang Wang. Learning to generalize provably in learning to optimize. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, pp. 9807-9825, PMLR. 2023.
Linxin Yang, Bingheng Li, Tian Ding, Jianghua Wu, Akang Wang, Yuyi Wang. Jiliang Tang, Ruoyu Sun, and Xiaodong Luo. An efficient unsupervised framework for quadratic programs via deep unrolling, 2024a.
Mei Yang, Gao Qiu, Junyong Liu, Youbo Liu, Tingjian Liu, Zhiyuan Tang, Lijie Ding, Yue Shui. and Kai Liu. hopollgy-transfervn physics-guided graph neural network for real-time optimal power 2024b.
flow. IEEE Transactions on Industrial Informatics, 2009);
Morris Yau, Nikolaos Karalias, Eric Lu, Jessica Xu, and Stefanie Jegelka. Are graph neural networks optimal approximation algorithms? Advances in Neural Information Processing Systems, 37: 73124-73181, 2025.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small relu networks are powerful memorizers: tight analysis of memorization capacity. Advances in neural information processing systems, 32, 2019.
15

---

Contents
Discussion of Related Work
17
A.1
GNNs for Constrained Optimization
17
A.2
Generalization Analysis of GNNs and 1.20 paradigms
19
Preliminary and Basic Concepts
19
B.1
Basic concepts of SOCPs
................................
19
B.2
Equivalent Formulations of SOCP
20
B.3
Target Mappings for SOCP
21
B. 4
An Example for SOCP graphs
21
B.5
Complexity Comparison with SOTA Works:
22
Proof of Main Theorem
22
SOCP WL-test
22
C.2
The connection between the WL-indistingguihhabit and target property
22
The measurable property of target mapping
28
C.4
Relation between SOCP-GNN's separation power and SOCP- PL test's separation
power
32
C.5
Main theorem's proof
34
C.6
Extension to p-order cone programming
35
Proof of theorem 3
36
D.I
VC-dimension based approaches for binary classification
36
D.2
Pseudo-dimension based approaches for real-valued scalar prediction
36
D.3
Rademacher complexity based approaches
37
SOCP-based Formulation for OPF
47
Experiment Settings and Supplementary Results
48
F.1
Data generation
48
F2
Implementations and training settings for predicting the optimal solution and feasibility
49
F3
Results for predicting optimal solutions and feasibility
50
F44
Empirical study sample/model complexity and size generalization
50
F5
Empirical study on the Lipschitz regularization
50
16

---

Published as a conference paper at ICLR 2026
A DISCUSSION OF RELATED WORK
Machine learning has been increasingly integrated with optimization problems to enable efficient Decision-making Several paradigms have emerged for this integration, each addressing different aspects of the optimization process but sharing common architectural challenges. Learning optimize trains models to iteratively refine solutions or to learn update rules that accelerate convergence (Li & Malik 2016 Chen et al. 2022a). Decision-focused learning leverages downstream optimization
tasks to refine upstream prediction models (Elmachtoub & Grigas] 2022 Mandi et al. 2024: Yang
al. 2025 Guo et al.) 2026). End-to-end learning trains neural networks to directly predict solutions
to constrained optimization problems, serving either as warm starts for solvers or as approximate
optima (Owerko al. 2020 Pan et al.) 2020 2022 Liang al. 2023 2024 Liang & Chen 2025).
Generative modeling approaches learn solution distributions for hard optimization problems Sun &
Yang 2023 Liang & Chen 2024 Li al. 2023
2025c 2026).
While these paradigms differ in their formulations, they share critical challenge: selecting an appropriate neural network architecture for the predictor or iterative component is essential for algorithmic performance.
A.1
GNNS FOR CONSTRAINED OPTIMIZATION
Among various neural architectures, Graph Neural Networks (GNNs) have demonstrated particular effectiveness for problems with inherent graph structures, leveraging the natural correspondence
between problem formulations and graph representations (Chen et al. 2022b Wu et al. 2024 Chen
ct al. 2023 Varbella et al.) 2024) Shamseldein 2026 Liu et al.
2025
To understand the fundamental capabilities of GNNs in optimization contexts, research has examined their expressivity (Chen et al.) 2022b 2024c). generalization properties (Balcan et al., 2021| 2024). and symmetry preservation (Chen et al. 2202at) Matthew Morris 2024 Chen et al. 2025 Qian &
Morris 2025b). The analysis of GNN expressive power in optimization is primarily guided by two complementary theoretical paradigms: the Peiiseiler-Lehmar -Wasedest-baseed framework, which characterizes what optimization properties GNNs can theoretically distinguish, and the Algorithm- Unrolling (AU)-based framework, which establishes connections between classical optimization algorithms and GNN architectures through direct algorithmic simulation.
A.1.1 WL-BASED FRAMEWORKS
This section reviews optimization problems where GNNs have been proven to achieve universal approximation capabilities through theoretical frameworks based on Wcisfeiler-Leman (WL) tests.
Linear Programming (LP) (Chen et al. 2022b): It establishes foundational theoretical framework for analyzing GNN expressivity in solving LPs through WL-tests. Building upon the bipartite graph representation introduced by (Gasse et al. 2019), they demonstrate formal connection between GNN expressivity and WL-tests on graph structures. Their key theoretical contribution proves that GNNs achieve universality over the parameter space of LPs. Specifically, they show the existence of pressage-passing GNNs capable of reliably approximating fundamental LP properties, including feasibility, optimal objective value, and optimal solutions.
Mixed-Integer Linear Programming (MILP) (Chen et al. 2023): : The extension to MILP presents significant theoretical challenges not encountered in the continuous LP setting. The fundamental limitation arises from the discrete nature of integer variables, where GNN expressivity remains constrained by the discriminative power of WL-tests. A critical issue emerges: two MILP instances that are indistinguishable under WL-ttssts may exhibit fundamentally different properties regarding feasibility and optimal solutions. To address these challenges, the authors identify a restricted class of MILPs satisfying the "unfoldable" property, for which universality guarantees can be established. Additionally, they demonstrate that augmenting the graph representation with random node features enables GNNs to achieve universality the complete class of MILP problems, effectively circumventing the limitations imposed by deterministic WL-tests.
Linearly Constrained Quadratic Programming (LCQP) (Chen et al., 2024b): While modeling linear constraints through a bipartite graph is relatively straightforward, extending graph-bascd ap- proaches to handle quadratic objective functions presents challenges. It addresses this by introducing
17

---

Published as a conference paper at ICLR 2026
self-connections within variable nodes capture quadratic interactions in the objective function. Their framework extends a broader class of mixed-intege LCQP problems satisfying the MP-tractable property, establishing universality results for GNNs specific computational tasks within this class.
The authors further extend their approach to convex quadratically constrained quadratic programming (QCQP) through dynamic edge update mechanisms, detailed in their supplementary materials, demonstrating the framework's 's adaptability to more complex constraint structures.
Convex Quadratically Constrained Quadratic Programming (QCQP) (Wu et al. 2024): It pro- vides a comprehensive treatment of convex QCQPs, addressing the significant complexity introduced by multiple convex quadratic constraints. The key innovation lies in their sophisticated design of edge weights and specialized GNN architecture, which together ensure that the resulting message- message-passing framework achieves universality for the complete class of convex QCQP problems. This represents significant advancement in handling optimization problems with complex constraint structures through GNNs.
A.1.2 AU-BASED FRAMEWORKS
Algorithm unrolling represents fundamental approach in learning-based optimization, enhancing interpretability by directly simulating classical algorithmic procedures through neural network archi- tectures. This section reviews successful applications of GNNs in unrolling established optimization algorithms.
Interior Point Method The unrolling of Interior Point Methods (IPM) establishes direct and interpretable correspondence between classical optimization algorithms and GNNs. (Qian et al. 2024) first provides theoretical foundations demonstrating that standard IPM iterations for LPs can be precisely simulated through sequences of GNN message- message-passing operations. This framework was extended to the broader class of LCQPs (Qian & Morris, 2025a), maintaining the fundamental correspondence between algorithmic steps and neural computations.
Primal-Dual Hybrid Gradient: The unrolling of Primal-Dual Hybrid Gradient (PDHG) algorithms provides scalable framework for accelerating first-order optimization methods through learning- based approaches. (Li et al., 2024a) introduces PDHG-Net for large-scale LPs, demonstrating be approximated using polynomial-sizer neural networks. This foundational work establishes both theoretical guarantees and practical scalability for the unrolled PDHG framework. The extension QP represents another advancement (Yang al., (022a)), which introduces an innovative unsupervised training methodology that directly incorporates Karush-Kuhn- Tucker (KKT) optimality conditions into the loss function.
that optimal LP solutions
Specialized Algorithms for Structured Problems: For optimization problems with specialized structures, researchers have developed tailored algorithmic approaches that leverage problem-specific properties for effective GNN unrolling.
For covering and packing LPs, (Li et al. 2024b) design variants of the -habbucc-KKaadkaar al- gorithm, successfully umrolling these through careful exploitation of activation function properties. Specifically, they utilize ELU and sigmoid activation functions to simulate exponential operations and Heaviside step functions, respectively, enabling reproduction of the classical algorithm's behavior within the GNN framework.
In the context of sparse binary LPs, (Li et al. 2025a) proposes constant-round distributed algorithm that applies to almost all sparse binary LP instances. This algorithm naturally aligns with constant- depth, constant- GNN architectures, providing theoretical justification for the empirical success of shallow networks in this domain.
demonstrates that polynomial-sized GNNs can effectively learn powerful approx- imation algorithms for Maximum Constraint Satisfaction Problems (Max-CSP). Their approach leverages the equivalence between projected gradient descent on low-rank vector formulations of relaxed semidefinite programs and local message- paassingganngggggg operations inherent in GNN architectures.
(Yau al. 2025)
Additionally, (He & Vitercik 2025) aligns GNN architectures with primal-dual algorithmic reasoning for minimum hitting set problems, achieving empirical success in generalization across problem sizes and distri--iitiiition scenarios.
18

---

Published as a conference paper at ICLR 2026
A.2 GENERALIZATION ANALYSIS OF GNNS AND L2O PARADIGMS
Generalization of GNNs: Graph Neural Networks (GNNs) Gori al. 2005 Scarselli al. 2008) are state-of-the oftth-f-t architectures proposed for graph learning. They leverage neighborhood information to capture the structured properties of a graph. To ensure effective learning, several approaches have been introduced to study their sample complexity, which is defined as the number of data required to generalize well to unseen data from the same underlying distribution. (Scarselli) iet al. 2018) connects the VC dimension to network parameters. activation functions (like piecewise polynomial activation functions), and graph size. Furthermore, (D (D'Inverno al.
2025 derives upper
bounds for the VC dimension of Graph Neural Networks using more general Pfaffian activation functions (like sigmoid and tanh). relating generalization capacity to network hyperparameters and the number of colors determined by the Weisfeiler-Lehmen test. (Morris et al. 2023) then tightly link generalization ability to GNN expressivity via Weisfeiler--emmnn WT.) test. Further, (Franks) et al.) 2024) uses margin theory show that greater expressivity only improves generalization if also increases the margin between classes. Based on Rademacher complexity, (Garg et al. (2200) gives the first data-dependent generalization bounds for GNNs using Rademacher complexity, which are significantly tighter than previous VC-dimension-bast
guarantees. For node individualization
schemes emerging these days, (Pellizzoni al. (2224) uses both VC dimension and Rademacher complexity to give the generalization bound via WL-test and covering number bounds. Moreover, several researches (Ju et al. 2023 Liao et al., 2020 Tang & Liu 2023) give the generalization bound from other perspectives, like the Pay-Bsyes bound and stochastic optimization.
Generalization of L20 paradigms: There are two main parts of researches in the study of general- ization ability of L20 paradigms: optimizer generalization, i.e., the performance gap between trained optimizees (tasks) and unseen optimizees, and optimizee generalization, i.e., the performance gap between training data and unseen test data of the same underlying optimizees (Yang et al. (023)). We only review the optimzee generalization part and the data-driven method generalization studies below.
(Balcan et al. 2021) first proposes unified sample complexity framework for the algorithm parameter configuration based pseudo-dimension. (Yang al. 2023) shows that local entropy measures loss landscape flatness, similar to the Hessian. then uses both metrics as regularizers to meta-train optimizers that provably learn to find generalizable models. (Sucker & Ochs 2025) combines PAC- Bayesian generalization theory with variational analysis to show that a learned algorithm' 's trajectory will converge to critical point with high probability unseen problems. (Sambharya & Stellato 2024) develops a general data-driven framework using PAC-Bayes theory to provide probabilistic performance guarantees for both classical and learned optimizers over fixed number of iterations.
B PRELIMINARY AND BASIC CONCEPTS
B. BASIC CONCEPTS OF SOCPs
For problem I we denote all the feasible solution by:
Xreasible := f E IR" Fx < I x < || bill2 S of x di, vi E [m]]
(3)
If Xreasible is not empty, problem D is said to be feasible; otherwise, it is said to be infeasible. A feasible SOCP is bounded and only if the objective function is bounded from below in Xteasible- ie., 3a R such that
ct 2 a, Vx E Xisasible
Otherwise, the SOCP instance is unbounded.
For a feasible and bounded SOCP, its optimal value is defined as: inf (eTx,Va Vx E Meeaatble) Moreover, x² is said to be an optimal solution if it's feasible and
of xx S e xx Vx E Xtonsible
Unlike convex QCQP, an SOCP instance may not admit an optimal solution even when it's feasible and bounded (see corollary 4h. Moreover, an SOCP instance can also have multiple solutions.
19

---

Published as a conference paper at ICLR 2026
B.2 EQUIVALENT FORMULATIONS OF SOCP
Consider a second-order cone (SOC) constraint of the form | + bll2 < c² + where A E R has rank r I min(k: n). Let the singular value decomposition of A be A = UEV", where U E R has orthonormal columns, Σ E Rexr is diagonal with positive entries, and V E Raxr has orthonormal columns.
Dimension Reduction of SOC Constraints:
Since U has orthonormal columns, we have U I and UUT is the orthogonal projection onto the column space of A. We can decompose the vector b as
b = by + br, where b = U
b1 = (1x -U0000
(4)
where by lies in the column space of A and b is orthogonal to it.
Define A' = EV E R and D' = U by E R'. Then:
UEVT = UA
(5)
and
U-+b-UA'+UUU U40-
b1
(6)
Since U has orthonormal columns and bj is orthogonal to the column space of U, we have:
|| + bl|2 (A bT) b_1l2 = =1 + UTh
1b1ll2
This reformulation reduces the constraint to at most + 1 rows, which is beneficial when k >> r. Reformulation of SOCP to QCQP: A SOC constraint || - bll2 S of x + d can be equivalently written as the quadratic constraint (may be non-convex) by squaring both sides as:
(Az + b)2 (Ar + b) s (c x d)²
TT ATA Az + 2b Az + ||b1l2 - x cc x 2dc + d
provided that cTa x + 2 O. Rearranging terms yields:
x² aAA cc 2(6 - + (1bb1 -
d²) 0
(8)
This transformation is valid only when the right-hand side of the original SOC constraint is non- negative, which must be enforced as an additional linear constraint e d 2
Reformulation of Convex QCQP to SOCP: Conversely, we may transform convex quadratic constraints of the form x Qx CT + d 0 into SOC constraints. Since Q S is positive semidefinite, we can apply matrix decomposition Q = LL" where L E Raxr with r = rank(Q). This decomposition can be obtained through Cholesky factorization when Q positive definite, or through eigenvalue decomposition in the general case.
The quadratic constraint then be reformulated as:
x xTQr + + x: LL T x +c d
|| T x
Using the rotated second-order cone representation, we can reformulate the constraint as:
1tc 1tc"atd xtd
1 1- cT
2
L x
This fonmulation is valid when 1 1-cT T x a-dd 2 0, which ensures that the right- hand side is non-negative. The constraint e x + d < 0 from the original quadratic form is automatically satisfied when the SOC constraint holds.
20

---

Published as a conference paper at ICLR 2026
For the convex quadratic objective function min, x vtQx + cJx d, reformulate it using epigraph variable T:
min 2,7
T
s.t. I Qe
Using the matrix decomposition Q LL
this becomes:
min
1-740 a4d
+ T c x
d
S.t.
2
B.3 TARGET MAPPINGS FOR SOCP
Then, propose all target mappings.
Definition B.1 (Target mappings). Let Gsoce be graph representation of a SOCP problem. We define the following target mappings.
the SOCP problem feasible and Feasibility mapping: We define Peeas
(tcasGSooc)) 0 otherwise.
Boundedness mapping:
For feasible SOCP problem, define Phound 1 if the SOCP problem is bounded and Dounnd (GsocP) = 0 otherwise.
For a feasible and bounded SOCP problem, we set Pape to be optimal objective value.
Optimal value mapping:
Attainability Mapping: For a feasible and bounded SOCP problem, its optimal value (infimum) is finite, but this value not necessarily attained by a feasible point. Therefore, we introduce mapping (9socP) which equals if an optimal solution exists, and 0 otherwise.
Solution
Optimal solution mapping: For an SOCP problem that admits a solution, its optimal solution might not be unique. Therefore, define the optimal solution mapping to be T (9soc)) x², where x" is the solution with the smallest l2 norm of the corresponding SOCP
B.4 AN EXAMPLE FOR SOCP GRAPHS
F is an example of a toy SOCP and its corresponding graph representation:
Polyhadron constraint node
min 1x, +2
3
Veriable node
Variable node 2
s.t. 55
(1. 1.
(2, 1,11
1 15 1,2
9
6 + +7 -
(11)
Minor conic constraint
1
Major conic constraint mode
Figure 6: toy SOCP instance with graph representation
21

---

Published as a conference paper at ICLR 2026
B.5 COMPLEXITY COMPARISON WITH SOTA WORKS:
Complexity for representing convex QCQP: We discuss further about what we mentioned in remark
3
For convex QCQP instance with m quadratic constraints and n variables, where the i-th constraint matrix has rank r; S our graph representation requires + m + 2 + "i=orr + 1) nodes while the architecture in (Wu et al. 2024 requires + m fn(n + 1) nodes and architecture in (Chen et al., 2024b) requires mn + 71 TT "nodes" that need to be updated dynamically. It's noteworthy that our graph representation only uses sparse connections between these nodes via using minor conic nodes as a sparse intermediate information passing layer between variables and conic constraints. As result, our SOCP-GNN requires only (n(( >== r:]] messages per iteration. This is in sharp contrast to the architecture by (Wu et al. (024), which models each quadratic term explicitly and thus incurs much higher per-iteration cost of O(n +mn? And result in (Chen et al. 2024b)
m
use ((mn²) messages each iteration.
Reducing the Node Complexity of SOCP-GNNs: One may note that for SOC constraints ||Ar
bll2 < c x + with A E k of a large >> n, the GNN need k minor conic constraint nodes to represent it. However, shown in Appendix B.1 we can reduce the complexity O(n) by reformulating it into another equivalent SOC constraint with corresponding A' R& xn of k' S 1. This reformulation makes SOCP-GNN more scalable for the large and structured problems real-world applications.
C PROOF OF MAIN THEOREM
C.I SOCP WL-TEST
The separation power of traditional GNNs is closely related to the Weisfeiler-Lehman (WL) test, classical algorithm to identify whether two given graphs are isomorphic. To apply the WL test on SOCP-graphs, we design modified WL test in Algorithm
We denote Algorithm I by WLsocp(.) and we assume that there is no collision of Hash functions and
their linear combination in the following proof (Chen et al. 2024b Wu al. 2024). We say that two SOCP -oCp-s G, G can be distinguished by Algorithm if and only if there exist positive integer and injective hash functions mentioned above such that the output multisets of G, G are different.
C.2 THE CONNECTION BETWEEN THE WL-INDISTINGUISHAABLIT AND TARGET PROPERTY
Here, we analyze the WL. test's convergence and corresponding stable properties to lead to the core lemma
Lemma 1. Assume all hash functions satisfy conditions in Appendix C.1 and we terminate the SOCP WL-test when the number of distinct colors no longer changes in an teration. Then the SOCP WL-test terminates in finite iterations.
Proof. Here, notice that the SOCP WL-test satisfies the following two properties:
If two nodes v, w have different colors in one (sub)iteration, then they will always have different colors in the following (sub)itcrations.
If after full iteration, the nodes' color doesn't 't change under some one-to-one color mapping, then for all iterations after this iteration, the algorithm will always return the same result.
These two facts have shown that, after one iteration, the color collections either get strictly finer or remain unchanged for all following iterations. Since the number of nodes is finite, the algorithm terminates in finite iterations.
And now, study the convergence properties of the SOCP-WI. test
22

---

Published as a conference paper at ICLR 2026
Algorithm The WL test for SOCP-Graphs (denoted by WLsocP)
1: Require: A graph instance G = (V, E) with node sets V1, V2, Va, V4, initial node features h", h², h² ht, and an iteration limit >> 0.
2: Initialize initial colors for all nodes:
3: Co." HA (h"), vo E Vi
4: C <- HASHo, (h*),
vs E V/
5: C + o
Yo E V/3
6: C + HASHo, (h9),
Vq E V4
7: for | to I. do
8: Update colors for polyhedron constraint nodes (V2);
9: Cl. + HASH Ct-1,,, Evev, WA..HHA
10:
Update colors for minor conic constraint nodes (V3):
Cl-100 + HASH Ch-1.0 Evev, (ASH
11:
Update colors for major conic constraint nodes (V4):
13:
C'-1,9 - HASH Cl-1. Evev, (ASH( (.1)
14:
Update colors for major conic constraint nodes (V4):
Cla HASH Cl-1, 11-1,,,,ev, Eoev, HASHHHHHCC
16:
Update colors for minor conic constraint nodes (V²):
17:
Cle + HASH (1-1,0 .Egv,, Wo,7 Ho.HHASS
Update colors for variable nodes (Vi):
19:
O HASH
C"-1,,, ,M, M2, M3) where:
M1
Σ SEV
w we H.,HHHSS(CC.))
M2 Σ
Wh, Wro HHAH(CHHH))
OEV
M3 Σ
Wh., HASH(C
GEV4
end for
21: Return The multisets of final colors: ((CL.)) Deen, ((Ch:))sevs
((Cho) Hoevs B
Given the SOCP graph G, assume the SOCP WL-test stabilizes after T 2 O iterations. The sum of weights from certain node of one color to all nodes of another color only depends on the color of the given node. Specifically, the sum (taking W1 for variable nodes and W2 for polyhederon constraint nodes as an example) is:
Lemma 2.
S(W2, W1;G)= =
Ws.
CF."=W; W1
and is well-defined for all s, such that C W
Similarly, for any color of variables Wi. color of polyhedron constraints Wz, color of minor conic constraints W3 and color of major conic constraints Wa. the following sums are well-defined:
S(W,, W1;G)=
Σ
Wo,v:
IT
W3
CT.=WWi
S(W4, Wg; ==
goo
CT. W4
CTio=Wa
S(W,, G2;G)= =
Σ
Wyss:
C... W
Chi==W2
S(W,, W): =
Wo,o1
ITe W1
CTo=Wa
23

---

Published as a conference paper at ICLR 2026
S(W1, W+: =
E
Wogg CT. = Wi
CRR=WW,
S(W1, W1;G) =
Σ
Wgr
C W4
CTN=WW
Proof. Let v1; be two nodes with color Wi = CT = CT,,, Since the SOCP WL-test has stabilized, the node pairs won't be finer, i.e.
Σ Wor HASH (CT.) = Σ Waz HA.H(CT..))
Rearranging according to W2 C. we get:
Σ Σ
W W. HASH(W2)) =
Σ
E
Woy HASH(W2).
WA CT.==W2
W2 CT.==W2
Assuming that the hash function is Iillision-free and maps different colors into different linearly independent vectors, we conclude that:
Wpis
CTM=W2
CTM==W2
ie., S(W,, W2; G) = Ecn.-ws Wa,er Other proofs are similar.
CT. W is well-defined.
An immediate conclusion is listed following.
Corollary all the SOCP WL-test cannot separate the two instances: I, (with given sizes n, m. "t,,k,,..,,, encoded by G, G E @soer g...m.k............. then: All the sum lemma 3 well defined for G and G and equal each other respectively.
Meanwhile, we define: Wi to be the collection of nodes with node type and color j. By summing the cross terms and rearranging the sum, we have:
S(W1j. W2 G)| = S(W2,, Way: W2x
S(W1, W3: G)[ = S(War. W1ys G) Wal
S(W1y. Wani G) W1yl = S(W 1m. Wiy G)
Now, we begin to prove the following lemma.
Lemma 3. I, Í (with given sizes n., m, ki,..., kmm b, encoded by G, G E Sooe gi..mkk....un two SOCP instances. If the following holds:
The SOCP WL-test cannot separate the two instances;
x is feasible solution of
Then there exists feasible solution â for Ý whose objective and Ez-norm are controlled by x, such that:
è à $ e
| la ||/||2
24

---

Published as a conference paper at ICLR 2026
Proof. The key to this proof is to take the average among the nodes in the same node pair. Formally, we define 2, = Wiyl (cnw=w,, Fvr) for all v, such that: CT,'" Wi;
By the Cauchy-Schwarz inequality, we have:
Σ
a 2 Wisll |1yl
Σ
Tor)]
CT Wis
CT W1,
Summing over all possible Wi,, we get: ||ا|| S ||0||
Meanwhile, notice that: for all v', such that: CT Wiy, their corresponding ev' ber, Por and évr, Lot, for are the same, respectively. Hence, we have:
Σ
Σ
Ep
CT.Y =W,
Ey E for
for all possible variable node v and color W1j. Summing over Wi, yields:
EewIy' Eévrão
Further, consider the edge properties brought by the above lemma, we get:
For the 1-th and t-th polyhedron constraint both with color W2., L E 21, .b (Here, we assume in both G and G. 1-th and t-th polyhedron constraint are both with color W2 respectively) the following inequality holds:
Fijez S St,
Σ
EEX
Fi S 9t.
12
LeW Wi; #EW15
Exchange the order of the sum, we get:
ΣΣ Σ
Finto S 9t.
W2n
W1, vEW,, Ie
Notice that:
ΣΣ Σ
FiN
EE Σ
Finntto
W2
[W2s
W1, 1EW IeWa
Wi, vEW LeWa
|Wad Σ E
Σ Fi
Wiy LEW2
Σ Σ
W1y DEW1,
Thus, Ew,, Evew., Fl, S 9t = 9. = ğl. which shows that the polyhedron constraint is satisfied.
Similarly, for the u-th and r-th (major) conic constraints both with color W Wam: we have:
After proper rearranging of nodes Oue, and Ors,, where Su 1, 2, ..., kui Sr 1, 2, ... ky the color of Ous,, and Oys.. where s, = 1,2, ..., ky S, = 1, 2, ..., hy, are the same regarding the order, i.e. on TToo.. Vi ..... kn (Notice that :ki, kz).
25

---

Published as a conference paper at ICLR 2026
du=dy.
For any node Ohi and Ojk E V3 with the same stable color, either h the color of node lh and Qj are the same.
Now let's prove the conic part. For the u-th and r-th major conic constraint node both with color Wam in both G and G and the minor conic node jı corresponds to r-th major conic constraint node in both G and G we have:
Right constraint:
Σ
T. + du
Wam Caim=Wam
=
Σ
Σ
Σ Cuo + dr
Waml
Wey DEW1;
Σ
Σ
Cuv + dr
Wam
Wis DEW1, CT.M=Wam
Waml Σ
Σ
S(W15, Wm:: G)zz) + dr
W1y NEW1;
Σ
Σ
S(W1,, Wam; G)āx) - d
Wam
W1y DEW1,
W Wigls(W1, W G)²,) + dr
Waml
W1s
Wam 5(( W15; G) d
Wmml
W1.
S(Wam am. W1,; + + Σ Σ W1; vEW1,
( + + = d,
W1
Left Constraint: Recall: two nodes in V/ has the same stable color W3 if their corresponding major conic constraint node's 's stable color is the same. So for each stable color W3: in V3, the corresponding major conic node's stable colors are all the same, denoted by Wam- And each major conic node
[Way] minor nodes with stable color Wa. And use denotes minor conic node have [ corresponds to node u
1
Σ
Σ
W&ml
(Aw + bu);
WAm WTw==W... sm jEWanjeeu
Wad
=(br),, + [Wadl Cr."=W am jEW
Σ
Σ
(Aux)))
= =(br),, + [Wad
Σ
Σ
Σ
Σ (Au)
CT."=W J Wa Win vEWin
=bb))) [Wall
Σ
Σ
E
E
(Au)goto
Win oi CT -W==WWar om JEWaIjEu
= =(b)))
IW Σ Σ
S(WIn, Was G)I,
vEWiA
=(br), |Wad
Σ
Σ
S(WI,, Wa; G)
W VE
26

---

Published as a conference paper at ICLR 2026
(br),.
Win SWWin War &)
[W't
Win
(br)
WSWWS WiA: G)
WWs st
WIn
(br)s. Σ
S(Wa,, WIA: &)
W1n.
=(br)..
Σ
Σ
(Ar)svv
W1a 1EWin
(br)s, (A, (b, A,
Conic feasibility for i
For the u-th conic constraint with stable color W anm its corresponds minor conic node j with color Wa., without loss of generality, we assume (Au + bu) 's first N
(W'r rows' corresponding to [Wam
all the minor conic nodes with color W3 for such and j. Thus, we have:
IWal
Waml
Σ
I[b A,t)
Σ C7 Wam
Σ
(Aue + bu)sllē
44m
Waml
WWal
(Aux + bu)s
WAm
CT.*=Waa
Hence, summing over all possible Wa for fixed W4m, we have:
| + A Σ Σ
I1 A, S
E
(Aux bw)ll
Wam CT.=
Wa WinniEWW
This yields that:
||b, + A,t S [Waal
E
(Aux +b)l22
Σ
I1(Aue + bullle
WWml
C7iM=Wam
C
Σ
of + d,, = +
Waml
Caam=
Since r is arbitrarily chosen from Wam- the conic feasibility holds obviously.
Corollary 2. If two SOCP instances I, I with their graph representations are indistinguishable by the SOCP-WL test, then the two problems share the same feasibility.
Proof. Let æ be a feasible solution for I, then by lemma there exists a feasible solution à for Ż.
Corollary 3. If two SOCP instances I, ī with their graph representations are indistinguishable by the SOCP- WL test, then the two problems share the same boundness.
Proof.
If one instance infeasible, by corollary the other instance is infeasible as well,
i.e., they are not bounded.
If one instance is not bounded from below, denoted by Z. Since we always find feasible solution of ī which has smaller objective value than any fixed feasible solution of I by Lemma 3 the conclusion is obvious.
27

---

Published as a conference paper at ICLR 2026
Corollary 4. If two SOCP instances I with their graph representations are indistinguishabble by the SOCP-W-- WL test, then the two problems share the same optimal objective value.
only need consider the case when both instances are feasible and Proof. By corollary bounded.
Notice that the feasibility with boundness may lead to the existence of an optimal solution for SOCP problems, for example:
min 22,
21 s.t. [1(2, 21 - x2)ll2 S 21 + 02 x1 2 0, x2
So, we prove by "infimum" argument, and p the optimal value of I and Ê respectively. Then for any >>> 0, there exists feasible solution I, s.t. e² S + c. By lemma 4, there exists feasible solution é of i, such that < v & S e ppe.. Let 0 yields p S p. Similarly, we have: I 2/ p. which finishes the proof.
Corollary 5. If two SOCP instances I, I with their graph representations are indistinguishable by the SOCP-W WLC test and one of these instances admits an optimal solution, then the other instance has an optimal solution well.
Proof. See the proof corollary
Corollary 6. If two SOCP instances I, 1 with their graph representations are indistinguishable by the SOCP-WL test, then the two problems share the same optimal solution with the smallest Euclidean norm if one instance admits optimal solution up to permulation.
Proof. Without loss of generality, we assume that for each variable j. its corresponding stable color in I, I after the SOCP-WL test the same, and Z has an optimal solution æ with the smallest Euclidean norm. By using lemma solution for I again with
3 twice, we can construct a feasible solution á for and construct a feasible
T and |
||
||ā1|2
Hence, R. Recall the proof of the lemma the variables in å with the same stable color after SOCP-WL test already have the same value, so averaging them again won't 't change it anymore, i.c. f = å. Hence, x = f = By corollary 4. ft is an optimal solution of
Now, if there exists an optimal solution of with ||v||2 < | = ||æ|||,, by similar proof above, we can get: y is also an optimal solution of I, which contradicts the fact that: æ is the optimal solution of with the smallest Euclidean norm. Hence, an optimal solution of 2 with the smallest Euclidean norm
C.3 THE MEASURABLE PROPERTY OF TARGET MAPPING
Definition C.1. For an SOCP instance G:
minimize eTar
subject
|| + bill2 S S. [ di, m.
Fx <
4 S I; S i- 1, 1,..,,
(c)m Its parameter is defined as (e, {A (m)) (d.) form the parameter space P
F,g,l,r), and all the parameter
Notice that: For an SOCP instance, there exists a bijective mapping I mn.m. + P with SOCP
I(G) = (c, (m [b,) fm (d. mm 2, for any SOCP instance G parametrized by (e, {m (b -- {d, )m F, g. r)). And we equip both G gn.mm.k......... and P with the standard Fuclidean topology and product topology in its feature space. Then I is homeomorphism.
28

---

Published as a conference paper at ICLR 2026
Remark:
If we prove that Ptarget P + R is measurable, then Ptarget o1 PSOCP "... Rm.b R measurable as well.
Theorem 4. For any Borel regular measure μ defined P, Deeas P - {0, 1] is me-aasauralle.
Proof. Below, we use measurable to denote je-measuable for simplicity.
To prove that feas is measurable, suffices to show that the preimage of {1}, denoted Preas = {P P Peems (P) = 13, is measurable set.
First, we define feasibility violation function Vieas
P R - 1220 Let (w)+ max(0, y).
Veeas (P, = Σ (11 b,ll2 - (cT + +d)) + Σ ((Fx), - 9;) + Σ ((lx - mx)+ + (Ix - -k)+)
j=1
This function Viens .)) is continuous with respect both Pand x. as it sum and composition of continuous functions (norms, linear maps, max function). Furthermore, Vieus ( (P, x) 0 if and only I is feasible point for the problem instance P.
A problem P is feasible if and only if there exists an r IR" such that Views (P.r) 0. This is equivalent to the condition 3R E N s.t. infzeR=neR 2P)
We can now express the set of feasible problems Preas by restricting the infimum to countable dense set. Let BR the closed ball of radius centered at the origin. By continuity of Vieas in æ, we have:
Preas =
U
PEP
inf BE
Vieas (P,x) =
REN+
1
U
n
BR, s.l. S.L.Vers (P,x)
REN+ KEN+
So, Pteas can be written as:
UUU {PED Vieas (P,x) <
1 k
Picas
REN+ KEN+ ZEBAUQ"
For any fixed x E Q", the function P Views (P,x) is continuous. Thus, for each tuple (R, k x), the set (P Vieas (P,x) < 1/k} is a Borel set. Since Preas is formed by countable unions and intersections of measurable sets, it itself a measurable (Borel) set. Therefore, Piens is measurable function.
Theorem 5. For any Borel regular measure μ defined on P. Pbownd P P (0,1} is u--masrrable
Proof. Below, we use measurable to denote μ μ-measurable for simplicity.
Let Preas 4 1 (1), which is measurable set. We only need to show that the set Poad {P Pieus & (P) = 1} is measurable.
A problem P Preas is bounded if and only if there exists M Z such that for all feasible solutions
x of P. e" 2 M. This can be stated as:
Phod
U {P E Preas MEZ
Vx 12" s.t. Vieas (P,x) = + e z M}
= U
P leas
inf
Tx
=ER", N. (Px)==
Mez
Let's define the boundness violation function:
inf Vidal (P,x) FERt s. Viea (P.))=0)
o frx
Now, have:
Poss
U (PE Preas Viaul (P,x) (x) 2 M) MEZ
29

---

Published as a conference paper at ICLR 2026
So it suffices to prove (x) is measurable and only need to show that: for any M IR, the sublevel set {P E Pleas (P) < M } is a measurable set.
The condition Vodd (P) < M is equivalent the existence of feasible point such that e M. This can be expressed as:
(P E Pieas (P) < M]
U k
P leus 3z RR s.t. e 2 M and feasible
Let us define an auxiliary violation function Vidd P x R x R + Ryo:
Vodu viol 2, = max ((e 2- M)+, Viens PP ())
This function is continuous in (P, 2, M). The condition Viad.vial P, M') 0 holds if and only if a feasible point and its objective value satisfies eT S M'
Thus, similar to the proof of feasibility, the condition Voau (P)
< M is equivalent to:
U KEN+ REN+
k: =
PE Preas
inf BER"OBR
Vidd,viol
P, P. M
By continuity of Vodd viol in
restrict the infimum to the countable dense set Q":
U U KEN REN+
UUE
(pE
PE Pleas
inf =EQenBR
Voda viol (P, 2. =
For any fixed z e , N+ and M' E R, the function P ++ Vidi (P, 2, .M) is continuous, hence measurable. The infimum of countable collection of such measurable functions is also measurable. Therefore, the set (P infzeq" Vidia M²) = 0} measurable for any fixed M'.
Since the sublevel set {P E Press Viaa(P) < M) is countable union of such measurable sets, it is measurable. This holds for all M R, Vida is measurable function.
Theorem 6. For any Borel regular measure μ defined on P, Parj P RR. is pasis-mmmanne measuraab...
Proof. Below, we use measurable to denote =-measurable simplicity.
To prove that obbj is measurable, we only need to show that for any & E R. the sublevel set {P P (P) < Φ} is measurable.
Let us define objective violation function Vobi P x R" x R + Rzoi
Vaij (P, 6) max ((e" +)+, Viens LensP.. (P,x))
This function is continuous in (P,x, Φ). Votgl (P, x, 0 if and only if is feasible point and its objective value satisfies ef < db
The condition oonj(P) (P) < Φ is equivalent to the existence of feasible point x such that eT x < Φ. This can be expressed as:
(P E P 2ati (P) < o)
U (PE s.t. eTa s σ h KEN+
and æ is feasible)
Similar to the previous proof, this is equivalent to:
U
U
PEPI
inf ZER
Voti
P.x, 1 k 0
KEN REN+
U
U kENt REN+
PEP
Vobi P,x, xeQ
inf
1 To) of
For any fixed E Q", the function P (P, 0') is continuous, hence measurable. The infimum a countable collection of measurable functions measurable. Hence, the set {P infreg= Vat x,  0} measurable for any fixed d. Since the sublevel set {P ong < Φ} is countable union such measurable sets, is measurable. This holds for all IR, so & Pat is measurable function.
n
30

---

Published as a conference paper at ICLR 2026
Theorem 7. For any Borel regular measure μu defined P, Panain {0, is memmasurable..
Proof. Below,
measurable to denote me-measurable for simplicity.
Let Pin = [6) (RR, which a measurable set. We only need to show that the set Poot = {P E Pmn Pattain (P) = } is measurable.
problem P Pin attains its optimal solution if and only if there exists point R" such that is feasible and its objective value is equal to the optimal value, Ponj(P). (P). This can be stated as:
Paol= {P E Piin 3x E Rd s.t. Vieas (P,x) and e (P))
Let's define the optimality violation function:
V (P. 2) max ((e Poty (P))+, Views (P,x))
Notice that:
For a fixed x, the function P + Vastul (P,x) is measurable because it is "composition" of continuous functions and the measurable function Patj-
For a fixed P. the function x Viotu x)) continuous.
A SOCP instance P attains its solution if and only if there exists R E N+, s.t. the infimum of V P, x) over x E Br is zero, i.e.
Pstl = U
P
Pin
V (P, = BB
inf
REN
Following the same logic used for Preas, write:
Punl U
{
PE
inf #ERenBR
Vinia (inu((,
REN+
U
n
P
inf oe B
Vasta (P, <
1
NeNt KEN
For any fixed v, P + Vaotu (P,x) is measurable. The infimum a countable of measurable functions is measurable. Therefore, the set
P Pun inf
Vastu (P, Vaot((P,2) zEBrnQ"
<
k
a measurable subset of Prin Since Psol is formed by countable unions and intersections of measurable sets, it is measurable. Thus, a is measurable function.
Theorem 8. For any Borel regular measure μ defined P, P Rd y--masurabll.
Proof. Below, measurable to denote me-meauurale for simplicity.
For any P E Psot = attaann o (1), o sotu well-defined. And suffices to prove that:(Paall): is
measurable for any E [ni], i.c. for any ø E the set: {P Poot (Rootu)s < Φ) is measurable.
Notice that: the followings are equivalent for P E Psoti
Pe (P Pool
( (osal)); < <}).
There exists x E R" with x; < d. such that Violu(P, = and Viotu > O, Va Biell x44 Φb
There exists R E Q+ E N., and x Bn with 2; = 6-1/r, such that Vantu x)) =
and Vana (P,z') > 0. Val E Br. 1 2 d.
31

---

Published as a conference paper at ICLR 2026
There exists R E Q+ and N+, such that for all r' N4, 3z E Bg n Q" I, I 1/r.
s.t. Vo x) < 1/rr and that 3," E N4, s.t, Viouu (P,x') 2 1/7", Va' E BR 0 Q" x 2
Hence, we can rewrite {P E Pool (Dsotu)i < o) as:
(NNERL UsERiOen {P E Poot Viola (P.z) < 71
U REQ+ rENt
0 (UNEEN, AW'BBnQu 220 e soo at Valu (P,x')
which is measurable.
C.4 RELATION BETWEEN SOCP-GNN'S SEPARATION POWER AND SOCP-WI TEST'S SEPARATION POWER
Remark 5.
Thanks to the universality of MLPs, it's noteworthy that we assume all learnable functions in SOCP-GNN are continuous in the following proof without loss of generality, since they always parametrized by MI.s..
Theorem 9, SOCP-GNN has the same separation power the SOCP-WI, test.
Proof. We only need to show: For any SOCP instance I and f, encoded by G, G, respectively, the following holds:
For graph-level output, two instances can't be separated by F
mn (R), i.e.
F(G) F(G), VF E SOCP
ki.............. (R)
if and only if the two instances can't 't be separated by the SOCP-WL test either.
For node-level output, the two instances can't be separated by Fumm kw......................... Am. (R. i.e., (TR"),
F(G) F()), vF E SOCP
Fummk........ ....kk.....k..b (R")
if and only the two instances can't 't be separated by the SOCP-WL test either, with CTiy CT. hold for all E [n]. i.c. the variables are reindexed according to the SOCP-WL test for both instances.
We first prove that SOCP-GNN can simulate the SOCP WL-test for any fixed SOCP instance. This can be proved by showing that: For any special SOCP-WY test and given graph G, there exists an SOCP-GNN that simulate arbitrary iterations of this test given the same input for G under the one-hot encoding.
Let F denote the set of all the initial features for all nodes in G. Then select g 1, 2, 3. 4 to map these features F to their one-hot encoding respectively by theorem 3.2 of (Yun et al. (019). So for any initial round in the SOCP-WL test, there exists an SOCP-GNN that can simulate
Assume now, we already have: we get an SOCP-GNN which can simulate the first t rounds of a special SOCP-WL test, that: h1.. is just the one-hot encoding of Ct. for all nodes For the first refinement round for the polyhedron constraint node we choose ff as an identity mapping, so that: if (Ct.e, L.EV, Wo, HO,HH.AS(CC and (Orie, Evev, W W...H.ASH(CC.)) are different, then (1,.0, E.Ev,, Wa.nJ((hh.)) and (14.', Evev, W (.r.o.((hh..)) are different. Then, by The- orem 3.2 of Yun et al. 2019), there exists 4-layered MLP gf) with ReLU activation can map these inputs: h Ever, (i(t)))))))) to their corresponding output in SOCP-WL test's one-hot encoding.
Similarly, we can prove that: there exists (-) and (.), such that the corresponding SOCP- GNN can simulate the t+1 round of the SOCP-WL test for G. By mathematical induction, for any possible output of for SOCP-W WL test, there exists SOCP-GNNs can output the corresponding one-hot encoding of the stable color, respectively. Consider the two possible outputs:
32

---

Published as a conference paper at ICLR 2026
Graph-level scalar output. In this set
= fout (I1, 12, 13, 11)
Node-level vector output. In this case, only consider the output associated with the variable nodes V1, given by
Yi Sou (hi::t, Jı, 12, 13, 14) [n]
where, 11 = 41=
EvEv, TT.", 12 E.ev, hT (TT..15 - -oovs nT' and 1 E hT
two instances I and Í can't be separated by any SOCP-GNNs but can be separated by some SOCP-WL test W. By applying the results discussed above to the disjoint union of these two instances' corresponding graphs, we get: R is just one-hot encoding of C respectively. Then we conclude that their output multisets under W the same, which causes contradiction. Hence, if two instances Z and i can't be separated by any SOCP-GNNs, then they can't be separated by any SOCP-WL test W as well. Similarly, we have:
For any node n', n" in SOCP instance I, Í respectively, if h = ii.." AF E F.mmm. Ni..... A (R) holds for any N, then n', n²" have the same stable color for any possible SOCP-WL test.
Now, assume two instances and 7 can't be separated by any SOCP-WL test. Now, show that:
F..mm -²'==" = h/ = polyhedron constraint s, s and F
(R),
SOCP
while a similar result can be derived for other sublayer-iterations using the same method.
When the conclusion holds obviously.
When f 2 1, assume the conclusion for all nodes holds for t - 1, then we have: Ch-1, Ever, W. HASH((()..) =(Cr-uo Erev, w., (ASH(("
Hence, we have:
Ct-l++= (1-1,8' M-1, 11-1,8
For any color Wi, the collection of colors the th iteration for varaible nodes, Evew,, Wa,e Evew,; u. This can be shown by assuming Hash function maps different colors to linearly independent vectors.
For any color Wii1 Evewi; Wav/i W (11-210) = Evewn wf (h--11 ( (By induc- tive assumption for node at iteration
Ew., Evew,, We (1' Ew., Evew,, ue foreft11p dt (
Therefore, h = Red which finishes the proof.
immediate corollary is:
Corollary 7. For any node n, n' in SOCP instance I, respectively, Cta Cann holds for all ki..k holds
possible SOCP-WL test and any & E N if and only if h hi'n', VF E SOCP for any t N.
By the proof of lemma 3 you can see that:
Corollary 8. For any node n, n' in SOCP instance I, respectively, Cl. = ò holds for all possible SOCP-WL test and any t if and only h ht.'' VF SOCP ki.m.k (R) holds for any E N. Under such assumption, ( (Dsatution (I)) = ( sotutioon (I)) if n, ni' are variable nodes.
33

---

Published as a conference paper at ICLR 2026
C.5 MAIN THEOREM'S SS PROOF
Consider the following theorems, which play an important role in real analysis:
Let f be Borel regular measure R and let I - IRm be p-measurable. Then for any j-measurable X C R with ((X) < oo and any > 0, there exists a compact set E C X with μ(X \ E) e, such that flg is continuous.
Lusin theorem:
By this fundamental but important theorem, we get 0, 3 compact X C SOCP (OSC .i.... X) < e, such that Ptarget|x x is continuous holds for any Starget mentioned in
.i........... with G km
Definition
Moreover, using similar tricks in (Chen et al. 2022b), we can assume that: X remains the same under the action of the permutation group S,, without loss of generality.
Generalized Stone- Weierstrass
(Theoremm 22 of (Azizian & Lelarge 2020 Let X be compact topology space and let G be a finite group that acts continuously on X and R. Define the collection of all equivariant continuous functions from X to R" as follows:
CE(X,R") = (F e C(X,R") F(g + x) = g * F(x), Vo E G,
Consider any FC C. CE(X,R") and any 4 Cg(X, Suppose the following conditions hold:
(i) Fís subalgebra of C(X, and E F.
(ii) For any x, I E X, if f(z) = f(x') holds for any f E C(X,)) with f1 E F, then for any F F. there exists g G such that F(x)= g F(x').
(iii) For any x, x' E XX, F(x) = F(z') holds for any F E F, then F(x) (xx).
(iv) For any x E X, it holds that (0)) = b(x)s V(j.j" E ((x,, where
((x 211.2...., F(x); F()),, WF FF
Then for any > 0, there exists F F such that
sup []((() - F(x)l <E
zeX
Now we leverage the theorems listed above give a proof of the main theorem. And we let the group G to be permutation group Sn. Since our SOCP-GNNs are permutation-cquivarian. they are obviously G equivariant continuous functions. (The following refers n)
Property (i): Fm.m.. km.. (R.........((() (R²) is subalgebra of Cæ(X, R*) and J.m.m. km . (R.))
SOCP
Proof. If suffices to prove this by using similar channel expansion techniques mentioned in (Chen ct al. 2022b).
Property (ii): For any x, x' E X, if f(x) f(x') holds for any f E C(X, with f1
Fn.m.. 8 Bma ( (IR"), then for any F E Fsoer ki.. (RR), there exists E G such that F(x)
g*
Proof. First notice that: J..m.
(R) E C(X,R) with f1 E Jn.mm
(R2), Vf
T.m.n.. ki ki...kk.. (IR). Then applying theorem and corollary is enough.
Property (iii) and (iv):
For any x X,ifF(()) = F(z') holds for any F E ((x").
Fa b then ((z)- SOCP
For any
X, it holds that ((x), (xx) v(i.j') J(x), where
J(z) = {{1,2, "1.,,,...aa? F(x), = F(x),, VF E Fn.mk ..... A (R²))
34

---

Published as a conference paper at ICLR 2026
Proof. Applying theorems in Appendix C.2 theorem and corollary 8 enough.
Applying the generalized Moone-Wieerstrass theorem gives us Theorem immediately.
C.6 EXTENSION тO P-ORDER CONE PROGRAMMING
general p-order cone programming can be stated as:
minimize subject to
Fx 9, I5r5r,
(10)
|A + bille s af + iE [m]]
where decision variables E IR", de E R. F E 1 g E R², 1 E ([-JUUR)) and r E ((+o)UR)) Here, we only consider the case: p E too..
R and the problem parameters
IR", A, R b; E R
Here, we formally define some concepts that are helpful to the extension of p-order cone programming. Definition C.2. function f R" + E is said to be separable f(x) can be expressed as sum f(x) = شÿー (2z)), where each function ʃa only depends on the scalar zj. (This definition is stricter than traditional "block separable".)
Definition C.3. A function f: R" + lR is said to be equivalent (w.r.t. permutation group S,) if for any rearranging (2))) (()) of 21,2, ,n) and any RP, f21,, ,.n) [( (o(2)> (o())
For p E [1. Ho0), we have: ||=13 = E |x which is separable and equivalent according to Definition C.2 and
Situation 1:Use p as fixed parameter: We don't need to make any modifications to our archi- tectures. As for the proof the universality, we just need to change ||.1|2 to ||-IIp for p 2 1 in our proof of lemma 3 and other theorems in Appendix C since our proof only uses the convexity, permutation -nnvaraannn property, continuous property, and separability of the le norm, which holds for the 4p norm well when p [L. +oo). As for +oo, lemma can be directly validated by noticing that:
1(6, + A,.)),1
1
Σ
Waml [Ws
(Ane + bw)sl
[aaml
CT: am Ee
W4m
(Ayx + bw)ss
Wam CT.==Wam JE JeWarjeu
W3'
WAm Aml
Σ Σ
(cu.2 + du)=
Σ CTM=-Wam Wam
(caxt + du)
Wan am CT. Wm JEW
[am
< 6 f + d,
where the notions follow the settings in lemma 3 Since the above equation holds for all jı, we can see that: lemma 3 still holds. Since || oloo continuous, the measurability holds as well.
Situation 2:Use chitectures and proofs, while we only consider p E [1, +ox) since ||>||p is continuous p when p E (o).
continuous parameter: Here, need little modification on our ar-
For the graph representation. we only need to augment our variable features from (e,, r:) to (ei, r.,)). And the GNN and related WL test don't 't need any modification. As for the proof, it suffices to notice that:
To prove lemma we just need to observe that: two instances I and 7 can't 't be distin- guished by the WL test, then their corresponding p must be the same. Then what remains is just the situation one's proof mentioned above. Other related results hold as well, like the equivalence of the WL. test and GNN in separation power.
35

---

Published as a conference paper at ICLR 2026
As for the measurability, we just need to repeat what do in Appendix C33 while taking p as a parameter in the new parameter space.
Situation 3:Mix order conic programming: Here, similar to situation 2, we need to augment features for minor constraint nodes. For the constraint |A,z + billp I c x + de, we reset the minor conic node j's feature to be ((4:),, p) Then we can prove Lemma 3 by noticing that: two major conic constraints have the same color and only their corresponding are the same. The measurability holds as well, similar to situation 1.
D PROOF OF THEOREM 3
D.1 VC-DIMENSION BASED APPROACHES FOR BINARY CLASSIHICATION
Definition D.1 (Growth function). For binary classification, the growth function of hypothesis class A over the domain X' is defined as:
Ta(n) = sup | x x where Aox ((a(z)), (x22), ... aaxx)) {0, 13"h e
Definition D.2 (VC-dimension). The Vapnik- Chenik-Chervoneniis dimension, VC-dimension, of AA is the largest integer n such (hat:Tu(n)= = 2". If (n) = 2" for all possible n, then A's VC dimension +00.
Below, we use (C(A to denote the VC dimension of the hypothesis class A for simplicity.
Definition D.3 (WL equivalence relation). We define the equivalence relation in SSCCP. as: two graphs G1 and G2 are equivalent if and only if they can't be distinguished by all possible SOCP-WL tests. Given a space of graphs G C SSoP gn..n.k......i
gn.............
let g/wr. denotes collections of the
equivalence class of G under such equivalence relation.
Theorem 10 (VC dimension of Fn.mk. .m.....m... (RR over 9). For hypothesis class Fn.m. ki....
km. (RR) Fn.mm, k...m.k.....mmbbb. (TR) do binary classification in the follow- pmmm.k M1.......... . (R)) maps to if (x) 2 0.5. Otherwise, it maps x to
VC (FSPP SOCP
k..... (R)) = 19//w// wL. Here, FSOCP
ing way: any function f E SOCP
(R) < 19/wr//- We prove by contradiction, if VC "i...mmmk.......... (R)) > 19/wzl, then there exists two graphs G2, G2 E G which can't be
Proof. First, we show that: VC (B)
distinguished by SOCP-WI. test but have different output under some f E Foomphi p...m..........h (i....ncc (TR) This
contradicts with thcorem g
Now, show that: VC (R)) GG/w//. Let u G//wl. Take representative elements G1, G2. G., of 9/WL respectively. Consider u +00 first, from theorem g we know that there exists POCP-GNN that simulate the SOCP-WL test for U,t,, G,. Hence, G,'s output (I, I2, Iz. I2) must be different respectively under this GNN after enough iterations. By theorem 3.1 of YYun al. 2019), we can output all possible results for G; respectively by using ki............
3-layer ReLU-like FNN as the output layer. Hence, SOCP
19/wz| when
" < +00, which indicates VC(JF. -t. (R)) = |9/ ///- In case where u = - we have:
SOCP
VC FCC,,mm km..kk (R) too well. Similar the proof when +o0,
that:
vn E N. T Taa.m km.. (B) (n) = 2", which finishes the proof.
D.2 PSEUDO-DIMENSION BASED APPROACHES FOR REAL-VALUED SCALAR PREDICTION
Definition D.4. Let g be a family of real-valued functions g X' - R. We say that a set of points (I), ,2, X is pseudo-shattered by if there exists vector of thresholds (or targets)
HHere, use p 1 encode +00 into feature.
36

---

Published as a conference paper at ICLR 2026
(21, 22, ..... 2N) R such that for any binary vector b (b1, b2 ..... ...., 11,%
there is a function g E G satisfying:
(l......, sign(g(æ;) 21) =
The pseudo-dimension of G, denoted as (g) the size of the largest set that can be pseudo- shattered by G. If arbitrarily large sets can be pseudo-shattered, the pseudo-dimension is infinite.
common result in learning theory shows that: For any family of functions H. mapping from a domain }' to bounded interval [0, HI,, the following generalization guarantee holds: For any E (0, 1), with probability least over the draw set D. of N samples drawn i.i.d. from an arbitrary distribution D over V, the following bound holds uniformly for all h E H:
1
Pdim H) + In (1)
Σ h(v) E [h(v)] N
0
H
N
Now, we begin to give the pseudo-dimension of SOCP-GNNs for real-valued scalar prediction (e.g. predicting the objective value).
Theorem 11 (pseudo-dimension of Fn.mm...... ....m.........
(R) over 9). For hypothesis class
Fn.ukkk b.....m.bbb. (RR), Pdim( (dim(FFocr kt..m..................... (R)) = l9/wrl
SOCP
SOCP
Proof. Similar to the proof above, we prove this theorem from two sides.
Otherwise, First, we show that: Pdim Jt..m...........pppp (R)) S. 19/wl/-
Pdim Faim kn. bo (IR) > 19/wzl, then there exists two graphs G1, G2 E G which can't
be distinguished by SOCP-WI, test but have different output under some f E Soo Fu.m.kk.....m.. (RR).
This contradicts with theorem / (Assume there exist 21, 22 such that: for any binary vector
b (b1, b2) 1+11-13 there function g E SOCP ki ki....m..b( satisfying:
Vi E (1.2), sign(g(G.) - -x;) =b:
Without loss of generality, we assume 21 2 22. Then there is a function g E FOCC that g(G) > 21 22 ((G2)..
Fn.mm Aim (R) such
Now, we show that: Pdim F pt....i............ elements G1, G2. G. of 9/ WL respectively. Consider u < too first, from theorem 9 we know that there exists a SOCP-GN output (7,, I2, Iz, [a) must be different respectively under this GNN after enough iterations. By theorem 3.1 of (Yun al. 2019). we can output all possible results for G; respectively by using
RR) 2 19/wel Let a [g/wL/- Take representative
SOCP
that can simulate the SOCP-WL test for Li= G,. Hence, G,'s
a 3-layer ReLU-like FNN as the output layer. Hence, Pdim (S k_..m.k.....k...
(R)) 2 |9/ wwl when < +00, which indicates Pdim(F F kn..kk (R)) [G/wr.| In case where +o0,
have: Pdim(Fn..m.ii ki............. elements of G/w G/WL can be pseudo-shattered.
(R)) +00 well, since any finite set composed of the representative
D.3 RADEMACHER COMPLEXITY BASED APPROACHES
Before we start, let's recall some basic concepts first.
Definition D.5. For a SOCP problem X N to be its parameter (c, (A, (b, Jm fci Je 1 when equipped with product topology over these Euclidean spaces for predicting boundedness, solution attainability, optimal value, optimal solution. And we define its problem size to be the dimension of its constraints' parameter (f {b (m (d, ym F.g. F.g.L. rr'sss dimension when equipped with product topology over these Euclidean space for predicting feasibility.
SSoP
on..m.A......... we define its size dimension
We make the task-specialized definitions above since predicting feasibility has nothing to do with the objective function, while other tasks are all closely related to the objective function. Here, focus on the following set of problems and hypotheses:
Problem class: The problem class X' solving satisfies the following properties:
37

---

Published as a conference paper at ICLR 2026
The problem size is N.
Its valid parameters lie in the bounded ball B, = f |æ||| S ri).
Note that we can always transform a problem class whose valid parameters are bounded into a new problem class whose valid parameters lie in the bounded ball by scaling. Moreover, real-world large-scale problems always have spansity. So it's reasonable to assume that the & norm of the valid parameters of the problems is bounded.
Hypothesis class: Here, we consider a subclass of SOCP-GNNs AL,N such that each a E AL,N satisfying the following property:
Graph-level Output Lipschitz property: a is L-Lipshitz w.r.t the input problem parame- ters Br,
Node-level Output Lipschitz property: For each variable [n]], we have: a's i-th output is I--Lipshtz w.r.t. the input problem parameters in B,, as well.
We remark that this kind of assumption is widely accepted by researchers in the sample complex- ity/generalization ability of graph neural networks (Pellizzoni et al.) [024] Garg et al. 2020 Tang &
Liu 2023). Now, we introduce some concepts which helpful to our theory.
Definition D.6 (Rademacher Complexity of a set). Given set C R the Rademacher complexity of A is defined as follows:
1 Rod( A) -
Egg
sup aE
0
m
, where 01, 02...., Om are independent random variables drawn from the Rademacher distribution, ie.,
Pr(o, = -1) = Pr(o, = -1) = 1/2 for i 1,2,..., m, and (a1,..., am) E A. The expectation E, taken over the random variables (o1....,mm)
Definition D.7 (pseudo metric space). A pseudometric space an ordered pair (X, d) where X is a set and d is function d X x X E, called pseudometric, satisfying the following conditions for all v, = E X:
1. d(x, 3) 2 (Non-ncgativity)
2. d(x, .) (Identity of self)
3. d(x, y) = d(y, .x) (Symmetry)
4. d(r, =) < d(x y) + d(y, =) (Triangle inequality)
Unlike a metric space, a pseudometric space allows d(z,, y) for distinct points x + y. Definition D.8 (Covering number). Let (X, d) be pseudometric space and let S be subset of X. For a given e > 0, an e-covering for is a set of points (a1,..., xx) S X such that for every point E S. there exists some x; in the for which d(s, x;2) The e-covering number of S, denoted by Cov(S, d, c), is the minimum size of e-coverings for S. Formally:
Cov(S, d, min {IPI P X is an e-covering]
Definition D.9 (Packing number). Let (X, d) be pseudometric space. For a given >> 0, an e-packing of is subset C X in which the distance between any two distinct points strictly greater than e, i.e., d(x. y) > for all x, E P with x # y. The e-packing number of X, denoted by Pack(X K, d, <), the maximum possible cardinality of such a set. Formally, defined as the supremum over the sizes of all possible e-packings:
Pack(X, d, c) = max {|P] PC X is an c-packing].
Now, Ict's define the pscudo metric over AI,N for both graph-level output and node-level output. Pseudo metric for graph-level scalar output: Given training set x {#1,"". (mm) we define
||a
lxx
(a(m:) for a E AL,N with output dimension pseudo norm. And define
V13
38

---

Published as a conference paper at ICLR 2026
||a blpp,
the pseudo metric Ar. with scalar output, denoted by
I1-llpxx
m
Pseudo metric for node-level vector output: Given a training set x {01,-" J. define 2. (a(r))
3mm
||a||p
for E AL,N with output dimension pseudo norm. And Di= [(a(m)))) (b(x,))) as the pseudo metric on AL.N with vector men
611 xx output, denoted by 1-lppx
define ||a
Without loss of generality, we assume our loss function Lipshitz continuous with coefficient q.
Lemma 4 (Contraction lemma, (Shalev-Shwartz & Ben- David 2014)'s Lemma 26.9). For each i [m]] lel Φ; IR + R be p-Lipschitz, function, namely for all or, E R we have [0x(a)) (0: (3) S
pla- 3). For Ie let ((a) denote the vector ( (ai ((i)).... .., &m (0m)). Let Φ A {Φ(a) AJ. Then,
Rad Φ A) S pRad(()) (A).
For the node-Ievel scalar output, we have: Lemma 5 (Contraction lemma for node-level output, (Maurer 2016)) Let X be any set, (f1.-.., (In) ) E X", let F be a class of functions f X' E2 and let hs la - have Lips- chitz norm L. Then
E sup
Σ Eorhi(((a))) & VV2LE sup Σ ounfk(zi), SEF
SEF
where ouk is independent doubly indexed Rademacher sequence and Sx((2)) is the k-th component of (xx)) And We use lg to denote the Hilbert space of square summable sequences of real numbers.
By setting the after M-th coordinate x E RM to O, we can see that any finite dimensional Euclidean space special class of (2 space.
Now, Let 2; denote (I;; ys), where v; is the i-th socp instance and y: E is the label of z4. We denote the loss function ((2) = ((a(x). y), which is q-Lipshitz w.r.t a(x) for all possible y. Let (z2) denote the vector (á(21)..... @b (m Let & o A = {Ø(Z) z E A). Then, we have:
Rad(o ( (22,,..., 14 = (a(x:), v1), Vi E [m] for E AL.N)) S q oL. zm)))
Meanwhile, Let 2; denote (z,, y:). where x; the i-th soep instance and y: E R" is the label of x; and we denote the loss function x(2) = ((a(x), v), which is q-Lipshitz w.r.t a(x) E RR" for all possible y. by lemma 5 we get:
Rad(o ((),),,(((,..,, 2m) 2, = (a(x:), (.) Vi [m] for a E AL,N)) S 22n (od(AL..o((E)).... zm)})
where RLd(AA ( {m)) Es supaEAL.N ETh o;a(x:) for graph-level scalar output E. supacAL, Em Σj= (a)(a())))) for node-level
and Rad(AL, {II1, Lm]] vector output.
mn
So, we only need to focus on Rod(AL,N That's just (AL,)) we defined following.
for fixed training sample (æ1,--- Rm).
Lemma 6 (Dudley Entropy Integral for scalar output, chapter 5.3.3 of (Winwwiiht, 2019)). Let AL,N
be the hypothesis class of SOCP-GNN; with scalar output as defined above. Let S {21, Im be a fixed set of SOCP problem instances. The empirical Rademacher complexity of AL.N on S is defined as
1 m
m
Rs(AL.N)
Es
sup dEAL
Σ
G,((x;)
where o; are independent Rademacher random variables. Let 112.s be the empirical L2 pseudo
metric on AL,N, given by ||a||2,s / Em alx;)² 2 for a E AL,N- Assume that for some Cs > 0,
39

---

Published as a conference paper at ICLR 2026
we have Su ||l|2.5 I Cs. Then.
12 vm
Us/2
Rs(ALN)) inf cE(0,Cs/2]
4e
Vlog Cov(AL.N, |I 112.s, v) do
where Cov(AL, d, c) is the e-covering number of the set AL,N with respect to the pseudometric d.
Proof. We start by constructing a sequence of coverings for the hypothesis class AI.N at progres- sively finer scales. Define E, = Cs/2' for j = 1, ..,,, For each j. let A, be a minimal E, cover of N with respect to the || |2.. pseudometrie, so that its size is [Aj] = Cov(AL, || 112.s, e2).
For any function E AL.N. we can define sequence of approximations TT(a) E A, such that a| (a) l1a.s Ej and set (a)a) O. For any integer K 2 0, any function AL,N can be decomposed into:
K
a = (a - (a)) + (
j=1
By the sub-additivity of the supremum, the empirical Rademacher complexity Rs(AL,N) = SuP Ei o,a(x;) can be bounded by:
L Eg m
m
K +
m
(s(.)) & m
Eg sup REAL.
Σ (((a(x:)=xxaa)
E
sup dEAL
Σ i=1
-
m
j=1
The first term, representing the residual error, can be bounded using the Cauchy-Schward inequality. For any E AL.N. have Σ (a(x)) xx (x,)) I -mlaa (a)llisiss -mlla Tx Tx(a)ll2,s & mex- Thus, the residual term is bounded by éK-
For the second terms, consider each term for O..... K. Let d,(a) = TT((a) I difference function belongs to the set Dj- = {c - c E Aj.c' E Aj-1l. whose size is at most | By the triangle inequality, the norm of any such difference is bounded by:
(a). This
||d, = (a= - T)-1(a))le.) l2.s $ || - all2.s + ||a T)-1(a)ll2.5 S + E = 3e,. We apply Massart's 's Lemma the Rademacher complexity of the finite set Dy:
F
sup dEAL 1=1
Σ
(a))((
< sup dED,
d(r,)² v 2 2log D2l
sup .EAi.,
Since the covering number is non-increasing with scale, |Ay-1 S |Ayl. which gives log [Dyl s 2 log [Ay). Therefore, the bound on the j-th term of the Rademacher complexity is:
Eg
sup nEAL.
Σ (a)((a) < (3e,) log |Ayl
6e, vm
log Cov(AL.N,))) ll2.s, e)).
Summing these bounds from j to K, and noting that e; = 2(E, - Ef41), we obtain sum that approximates an integral:
K
12 K
6e, / log Cov(AL. w.w.NNII-llllse... (l),s,e))= =
( ((+1) log Cov(AL,N l12.s.e)
Vm
j=1
12
Cov(L.N lla,s, v) do.
Vm
Jex+1
Combining all parts, have for any chosen refinement level K:
12
Cs/2
Rs(AL.N) s 2ek+1
Log 112.s. v) do.
Vm
Jex+1
40

---

Published as a conference paper at ICLR 2026
Since this holds for any K, replace the cutoff scale ex+1 with an arbitrary 1 ex41ll Taking the infimum over all such yields the tightest bound:
(As,N)
inf ce(o.Cs/2]
4e
12 V
Csl2
Vlog Cov(Ar, Il 112,8, v) du
Lemma (Dudley Entropy Integral for vector output), Let AL,N the hypothesis class of SOCP- GNNs defined above. Let S ..1.....Im. be fixed set of m SOCP problem instances. The empirical Rademacher complexity of AL.N with output dimension n on S is defined as
Th a
Rs(AL))) E.
sup AEAL.
ΣΣ o.((a(x:))
mn
where osj independent Rademacher random variables. Let 11. 112,5 be the empirical L2 pseu- dometric AL,N, given by ||a||2,s v mn E " (a(x:))3 for AL, Assume that for some Cs > O, we have SuPEEAL.N ||a||2,s S Cs. Then,
12
Cs/2
Rs(AL,N) S inf cE(0,Ca/2]
4e
log Cov( ll2,s, v) du
Vmn
where Cov(AL,,, d, 6) is the e-covering number of the set AL,N with respect the pseudometric d.
Proof. Similarly, we define e Cs/22 for ........ K For each k, let A& be minimal ex-cover of AL,N with respect to the || |2.s pscudometric, so that its size is [AA = Cov(AL.N, (2).
For any function E AL.N, we can define a sequence of approximations (a) E AA such that || (a) 1|2.s S eg and set ma(a) O. For any integer K 0, any function AL.N can be decomposed into:
K
a = (a (a-T<(a)) (a)) + ((m((a) -
(Tx(())-T-((a))) Tk))
By the sub-additivity of the supremum, the empirical Rademacher complexity Rs(AL,)
E. suPoEAL.N mn
E Σラ= (,(((()))) can be bounded by:
m
Rs(Ar. S E,
sup dEAL,
mn
m
E,
sup
- -x-1(()(;;)]
mi
aEAL. i=1 j=1
(iy(((z))))))))))))))))))))))) For any AL,N have E 1) mnlla (x(a)]l2,s S mnek. Thus, the residual term is bounded by ek.
ne (a))))) -mnlla n (a)llas s
For the second terms, we consider each term for k = O...., K. Let da(a) =x(a)= - (a) This difference function belongs to the set Dy {c
Au, c' Ax-1), whose size at most [ By the triangle inequality, the norm of any such difference is bounded by:
(ad (() (a-1(a) S (a)x(a) all2.s + ||a = S e + ch-1 = 3Ep- We apply Massart's 's Lemma to the Rademacher complexity of the finite set Dy:
E
sup aeAL,,
as (d& (a)(
<
sup deD,
Σ
(d(x:))3 22logg Da
i=l j=1
2=
41

---

Published as a conference paper at ICLR 2026
sup (Vmnild<<()l2a) log(IAA ||
aEAL,
Since the covering number is non-increasing with scale, | < 2 log [Ag]. Therefore, the bound on the k-th term of the Rademacher complexity is:
[Ax which gives log DD 5
1 E, sup .EAL.N 1=
6
(ty(d((a((a))) S
(3ex) 4log Au
log Cov(AL, II ll2.s, ea).
Vmn
Summing these bounds from & K, and noting that c₁ 2(ck ck+1), obtain sum that approximates an integral:
K
GER
12
log Cov(L,, -I.l1l111. Ill,s,
(ek cat1) /log loggl/oooooo Cov(AA, Il 1la,s, ea)
mn
mm
12
log CogCovAA,,N |l -1..,,l..1,,, dv.
mm
ce++1
Combining all parts, we have for any chosen refinement level K:
12
Caff
Rs(AL,N) S 22 +
log Cov 11,,s v) do.
ex-1
Since this holds for any K, we can replace the cutoff scale ex+1 with an arbitrary e E 1 .eK+1]- Taking the infimum over all such yields the tightest bound:
12
Cal2
(A
inf eE(0,Cs/2]
4e
V Vlog Cov lla.ss o)
do du
Vm
By the above lemma, it suffices to study the bound of Cov(AL,N, || ll2,s, v) now. And we will consider two different situations here, i.e., the output dimension 1 and n, respectively.
space, (Pellizzoni al. 2024) Lemma 2). Let AL.N C (f S + R.} be the hypothesis class of SOCP-GNNs whose output dimension is I, where S {II,.... {I be fixed set of m problem instances. We assume the function outputs lie in the interval [-r,r]. For any > 0, the logarithm of the e-covering number of 1|2.s, bounded by:
Lemma 8 (Estimation for covering number bounds in
this class with respect to the empirical L2 pseudometric,
E +2)
log Cor(AA., (la.s,e) S Cov(S, l| 1l2, 2L log
Proof. Take 5, to be the minimal
2T -overing of S. Consider function class O = {s : S. -
{5 + ke : k = - 1), ..,, 0, [2 For each S, let π (x) S, be one of the closet point of
x in S, satisfying: [π) æ1I2 S DT Ler O = ( S + R f(x) = f(T(2)) for some f E O}. So. suffices to prove that: O is e-covering of AL,N
Then |0| |0| = (21=] + 2) (s.
under || 112.s-
For any f E AL,N take g O such that (g(x) f()) $ for all a e S.. Then have:
1 m
|l g122,8
Σ - -(()))(())13)
[1())) f((()() -((()) (o(=())) ((x)
m
L + + =
2L
ZES
Taking square root of both sides, get the proof.
42

---

Published as a conference paper at ICLR 2026
Lemma 9. Let AL.N C (f R") be the hypothesis class of SOCP-GNNs whose outpur dimension is n, where S= (21....... Im be a fixed set of m problem instances. We assume that each component of the function output lies in the interval [-r,r]. For any >> 0, the logarithm of the e-covering number of this class with respect to the empirical Iz2 pseudometric, || 112,s, is bounded
by:
log Cov( Cov(AA.,,11I ll2.s.e) & nCov(S. 112. 2 log +2)
Proof. Take S, to be the minimal covering of S. Consider function class O = [ Sz ( + ke k = - + 1), (e.),,,,,00000. O, (,) ( For each x E S, let π (x) E S, be one of the closest point of
R f(x) ((((1) for some f E O}. Then |0| = [0] = [2 + 2)nCov( (ll So, it suffices to prove that: O is a e-covering of AL.N
in S2 satisfying: [x 21l2 गे. Let (s
under || 112.5-
For any f E AL,N, take E O such that [g(x); f(x)11 S 1 for all x E S. and i E [n]. Then we have:
Il - 9
1f(x), - -(())/)
mn
ZES i=1
Σ lI(())) - [(T(x))) (f(T()))) ((*())) +o(T(())) s(x)(133)
mmn
FES
T.
2 + +0]3)
mn
2L
BES
Taking square root of both sides, we get the proof.
So, what remains is to discuss the covering number bounds of S in its valid parameter space Br, Lemma 10 (Estimation for covering number bounds in socp-parameter space). For any 0 and the uniform distribution P over the valid parameter space By, we have:
(12,,)) S 2 Prite (1 miin((_),,1))
Ega (Cov(S, (C1.(8.11-112.ee)
Proof. Notice that:
Cou(S,11 (12,c) c) I Pack(S, || 112, s Pack(Br. (22,c)
Here, the first inequality holds since any maximum 6-packing is a e-covering as well. Let P be the maximum e-packing of B,; and let P = {z1, .IPii. Then, we have: U!Al B(r,, 5) c (00, 5), where B(r;, 5) {ar E N || ælla S { are mutually disjoint. Hence, if let aN denote the volume of the bounded ball in N. we get: S ax (2
Consider the collection of balls B (B(x,, e) i E [[[[]] For any ball b and m socp instances 81, 8m which are sampled i.idd. from the uniform distribution on B,,, we have:
P(s: & b, Vi [ml) 2 min(( min((_)) 1))
For any possible realization of = ........ ................................ sm }. we take all balls b E B, which contain some points in S to form new of balls, denoted by C. Then O's center forms e-covering of S.
43

---

Published as a conference paper at ICLR 2026
(Here, notice that: Br C UbgBb). Let I1,,.., I| denote the indicator variables for the event: E y E S, s.l. E ((zi,e) respectively. Then, we have:
IPI
Es-3nm (Cov(S, (122,))- - BS
I S
||([1 (1 min([_)) m)
2r C N (1-min(( (ain((_),,)))) 11)
Before we get our result finally, an important lemma is needed.
Theorem (Theorem 26.5 of (Shalev- -Shwarzz & Ben-David 2014) 4); Algorithmic Foundations of (Shalev-Shwartz
Learning). Assume that for all and h E H we have that [8(h, 2) S c. Then,
1. With probability of at least 1 5, for all h E H.
2 21n (2/6)
- < 2 E SmmD
Rad(f Ho H0
In particular, this holds for (S).
2. With probability of at least 5, for all E H.
2ln(4/5)
(h) Ls(h) S 2Rad(E Ho S) + scy
m
In particular, this holds for (SM.
3. For any h², with probability of least 8.
2nn(8/
LD(ERMH(S)) LD(h") S 2Rod(l S) + 5
m
4. For any h², with probability of at least 1 8.
2 2lo((1/))
- LD(ERMx(S))
S ADs:=Dm(Raddl o H. S')] + 201
Here, denotes the sample point, S and S' denotes the truining set of size H denotes the hypothesis class, denotes the loss function, h- denote the hypothesis H with the smallest generalization error and (RM denotes the hypothesis in H with the smallest empirical error on S.
Before we go further, we need a further lemma to apply Tonelli's is theorem in the following proof. Lemma 11. The function (S, v) Cov(S, v) is measurable w.r.. the standard lebesgue measure, where (B,,)m v E R Here, R+ denotes all non-negative real numbers.
Proof. Here, if suffices to prove that: for any E N, the set {(S,v) +(S,0) v) S n) is measurable. Let S (81, sm.) ). X (x1,-.. ,T,,, we define h(S, X) maxxe[m] minje(s] ||s; 12112. which is continuous in S, X. By Berge's 's theorem of maximum, g(S) inf i... M(S, X) is continuous S. Hence (S)
continuous. Notice that:
{S, v) (S, v) < <n) = ((S,v) ((S) - <
Hence, this set is measurable, which indicates that Cov -
v) is measurable w.n.. (S, v).
It's time to get our integral sample complexity result.
44

---

Published as a conference paper at ICLR 2026
Theorem 13 (estimation risk for graph level output). For graph-level prediction tasks, let AL.N be the hypothesis class of SOCP-GNNs defined above for a graph-level prediction lask on the set X of SOCP instances whose valid parameters lie in BrG with outputs in [-r, r| and loss functions that are q-Lipshitz and bounded by Then, for any training set S of m samples which are i..d. sampled from the uniform distribution D over X, let h" denote the hypothesis in AL,N with the smallest generalization error and ERMA,, x (S) denotes the hypothesis in AL,N with the smallest empirical
error S. have: with probability of at least 1 6.
2 log(116)
Lo(ERMAI,, (8)) -D(h') S Dm [Rad(L AL.N 8')] + 2pV
vm A (1 min(( ),, 1)) log
12
(2/
4g inf cE(0.r/2]
[de
du]
2Lr
2 (og(
+ 2pv
m
Proof. By theorem above, it suffices to notice that:
nn RRad( o AL.N o S')]
S 1m A o S') (lemma
4
I gm inf
4e +
12
Viog Cov(AA... |l lla,s,, v) dv
(lemma 6
-E(0.r/2)
vm
12
/T/2
5 inf [|
Bgg-Dm(
dE +
log Cov(A,, |l- lla,s u) du
Vm
12 Bigi pm
5 inf *E(0,r/2]
[ee +
Cov Ila.s 2)) do]
vm
12
2r +2) dul (lemma X
5g inf [c(U.r/2]
[4e +
Bsr
Cov(s', 21 2 log
vm
12
122
2r +22
5 inf
[e +
Br Cov(5",11 I1. 112, 21
log
(Tonelli'sss Theorem)
=2(0,r/2
vm
12
2r +
59 inf
[e +
BSnnDm(Covis (Cov(S', .1 lla, 21 log
(Jensen Inequality)
cElu.r/2!
vml
12
12
ALr; to u min((
2r +2)
5g inf =E(0,r/2]
[ee +
)N, 1)) log log
(lemmaa 10
vm
2L.
Here, /Cov(S', 11- |12, 27. log 2r + +2 is measurable since it's the square root of the multiplication of two valued positive measurable functions. Since it's positive, we can exchange the order of integration by Tonelli's theorem.
Theorem 14 (estimation risk for node level output). For node-level prediction tasks, let AL,N be
the hypothesis class of SOCP-GNN: defined above for a node-level prediction task on the set of
SOCP instances whose valid parameters lie in BrG, with outputs in [-r,r]" and loss functions that are L-pisshitz and bounded by p. Then, for any training set S of m samples which are iidd sampled from the uniform distribution D over X, let h denote the hypothesis in AL,N with the smallest generalization error and A1, (S) denotes the hypothesis in AL,N with the smallest empirical error S, have: with probability of at least 1 6.
2 log(1/8)
LE,E - LD(h") ) S Dm Rod(E AL.N o S')) + 2p/
m
< 2/2gg inf [4e + 12 /2
/
ALri AL + - (1 min(( 11 MM, m)) log
2r +2) del
+E(0.r/2)
/m
2T.5
45

---

Published as a conference paper at ICLR 2026
1lg(11/8)
+ 2p1
m
Proof. By theorem above, it suffices to notice that:
DD
[Rad(l AL.N S
VingBg--Do AL, 5")] (lemma
12
< B2ngBg-nm
inf <E(Urr/2]
4e +
log Cov(AA,, |I l1,,5 v)
(lemma
v Vmn
12
S </2ng inf cE(U.r/4]
E Bm Dm
+
log Cov(AN,, I1 112.s. v) do
Vmn
$ </2ng inf xE(U.n/2]
[e +
12
Es ~
log Cov(L,,
112,11 w)] de]
Vmn
$ <22ng inf cE(U.r/2]
[e +
12
E. pm
CnooCCCs lla,
log
2r + v
duj (lemma
Vmn
2T.
S </2gg
inf -E(0.r/2)
[4c +
12
12
Eswnmly wy nnCo(sss 112.
log
2r
+ +2
dej (Tonelli's Theorem)
Vmn
2L
S <v2ng
inf
Me +
12
/2/
nEg:NDm (FFrsmm(CCv((" 1 21
log
2r +2
dul (Jensen Inequality)
cE (e(0.r/2)
Vmn
S <22gg
inf ,E(0.r/2)
Me +
12
ALri t (N - (1 min((
)N, 1))mm) log
(2r
2r dul (lemma I0
+2)
vm
21m
46

---

Published as a conference paper at ICLR 2026
E SOCP-BASED FORMULATION FOR OPF
Decision Variables
Wi E
R
voltage magnitude squared at bus
(11)
Cijy Siy IR
cosine and sine terms for line (i,j)
(12)
P9.s. Qg.t E
real and reactive power generation at bus
(13)
P.j. Q.j R
real and reactive power flows line (i,j)
(14)
where:
Cjj w cos (0: 02)
(15)
8ij w.wy sin(0; - 0,)
(16)
Objective Function min Eveg Pg.
Second-Order Cone Constraints For each line (i, E &, the rotated second-orde cone
constraint:
22 + 22 S w;10j
(17)
can be directly reformulated the following standard second-order cone constraint:
20gj
28:j
S w7 + wy
(18)
[00, Wij
2
Power Flow Equations Real power flow from bus to bus j:
P.j Wi DiCCij 82j
(19)
Reactive power flow from bus i to bus j::
Qzy - w w. + biyCaj Say
(20)
where gsy and biy are the conductance and susceptance line (i, j).
Nodal Power Balance For each bus i E N:
Pg Pa.s =
Σ
Pij + gaw;
(21)
jEN(
Q9 Qa,
Σ
Qi
by
(22)
JEN(()
where ((t)) is the set of buses connected to bus i, and Júi by are shunt elements.
Voltage Magnitude Limits
(V (Vmin>² ) & we - (Vmaxx²
ViEN
(23)
Generation Limits
9 pmin < Pg.s
pmax gi
Vi WEG
(24)
Qmin S Qg S Qmax
Vieg g
(25)
Line Flow Limits
((P,)Qi))) < Smax V(i.)) E 3
(26)
47

---

Published as a conference paper at ICLR 2026
F EXPERIMENT SETTINGS AND SUPPLEMENTARY RESULTS
F.1 DATA GENERATION
F.1.1 GENERATION OF FEASIBLE SOCP INSTANCES
Following the SOCP generating scheme in CVXPY we use the following steps to generate feasible and random SOCP instances, which admit at least an optimal solution.
Generate secret point H. E R by sampling from standard normal distribution, i.e., (O, I). Then generate the objective coefficient e ~ (O, 0.25I).
(II) Impose lower bounds and upper bounds on variables S I₁ S r for the problem. Here and 3g | 0.1,r r = Is + A - 0.1, where A; are sampled i.i.d. from (0, 0.25I)
denotes component-wise absolute value.
IIII) Generate F
R whose nonzero entries sampled iid. from (O 0.01) and components are nonzero with probability 0.5. The vector g is subsequently sampled by
g FI, As| 0.1, where A3 ~ 0.25)...
(IV) For each conic constraint, randomly sample the cone dimension (the number of rows of A, b,) in [1.7] with equal probability. Then, generate A,, C₁ b, whose nonzero entries are sampled i.i.d. from (0, 0.0025). Each component of the coefficient matrix AG, Ca is nonzero with probability 0.5. Then, generate d; ||A,T, + 6;ll2 e, I. + e, where c~ U(0.5, 1).
Step (II) ensures that the generated SOCP instances always have optimal solution. Furthermore, the coefficients are intentionally sampled from distributions with different variances, introducing varying numerical scales create more challenging instances.
F.1.2 GENERATION OF (POSSIBLE) INFEASIBLE SOCP INSTANCES
We use the following steps to generate a (possible) infeasible SOCP instance with pre-determined probability h E [0, 1].
(I Sample a feasible SOCP instance by methods in Appendix F.I.1
(II) Execute step III-IV with probability h and execute step V-VI with probability 1 h.
(III) Sample a random integer p in [3, 20) and scale coefficient a ~ 20, 1). Then repeat step
IV for times
(IV) Randomly choose type of constraint to break with equal probability. If the polyhedral constraint is chosen, we randomly choose one component of with equal probability, denoted by Ji, and then replace 9i by (Fx.); 5 3. If the conic constraint is chosen, we randomly choose one with equal probability and then replace its corresponding d, by |A,z,
bill2 C, x. 8 3. Here 8 ~ ((,
(V) Sample a random integer p in [3, 20] and scale coefficient a U(00 1). Then repeat step VI for times
(VI) Randomly choose type of constraint to enhance with equal probability. If the polyhedral constraint is chosen, we randomly choose one component of g with equal probability, denoted by Ji, and then replace gi by y; + 8. If the conic constraint is chosen, we randomly choose one with equal probability and then replace its corresponding de by d, + Here 8 ~ u(0,a). a).
F.1.3 GENERATION OF OPF-SOCP INSTANCES
We the following steps generate feasible SOCP instances that admit an optimal solution (Here, initial problem settings are the same as Appendix
1I Read the reference problem in the IEEE test systems (Babaeinnjaasarrookllee et al. 2019 which has the pre-determined number of buses.
48

---

Published as a conference paper at ICLR 2026
(II) Randomly remove one branch from the grid topology while making sure the resulting graph is still connected.
(III) Apply multiplicative perturbations to the base real and reactive power demands, Pa. and Qd.i. each bus i, and to the linear generator cost coefficients, C,. Each perturbation factor is drawn Lid. from a uniform distribution [0,9, 1.1].
(IV) Check if the problem has an optimal solution. If yes, then return the problem. Otherwise, repeat steps I-IV again.
F.1.4 DATA GENERATION FOR PREDICTING OPTIMAL SOLUTIONS
We randomly generate 5000 feasible SOCP instances by methods in Appendix F.1.1 of size (50,10,10), (100,50,50), and (500, 100. 100) respectively. Each instance solved in CVXPY to obtain a ground truth solution as the label. Then, we divide these instances into training. validation, and test data classes by the ratio 8 1
To further validate our theorem on real-world situations, we use methods in section F.1.3 randomly generate 1000 samples based on IEEE test systems. Then, we divide these instances into training, validation, and test data classes by the ratio 8: 11:11
F.1.5 DATA GENERATION FOR PREDICTING THE FEASIBILITY:
We randomly generate 5000 infeasible SOCP instances with probability h 0.5 by methods in Appendix F.1.2 of size (50,10,10), (100,50,50) and (500,100, 100,) respectively. We use CVXPY to detect the feasibility of these instances as well. Then, we divide these instances into training class and validation class by the same ratio.
F.2 IMPLEMENTATIONS AND TRAINING SETTINGS FOR PREDICTING THE OPTIMAL SOLUTION AND FEASIBILITY
For predicting the optimal solution, our SOCP-GNN is implemented with four geessage-psssing layers. The learnable functions, denoted by g.. 9/.- fi,- and fou (where 1 E (1,..., 4]. le {1, (1....,6), 6), and 1N (1....,8)), ,8),, are all parameterized by neural networks. Specifically, of, and of, are simple linear layers, while Jf, and fau are constructed with single hidden layer containing 64 neurons. For comparison, our baseline FCNN is implemented with four hidden layers with residual connections, each containing 64 neurons. The other GNNs are implemented based on the basic message- message-passing method with the same embedding layer as SOCP-GNN, i.e. ha Update(h"** Aggregate( (f , In' E H)) Here h is the feature of node n at the 1-th message passing process, Gyn is the edge weight connecting node n and its neighbor n', and ((n) denotes the neighborhood of node n. In the vanilla MPNN, we first concatenate Con' and ha' to form [can', h² .1. This vector is processed by MLP with two hidden layers (64 neurons each) to generate a message vector matching the dimension of h. We then compute the mean of these messages over the neighborhood of n, denoted as hn Finally, a distinct MLP with an identical architecture maps the concatenation [h= h to the updated feature h,, For the Graph Isomorphism Network (GIN), we employ the same MLP architecture as the vanilla MPNN to map hmd + [W(m)) to the updated feature h,+++ Vanilla MPNNs and GINs both have five message passing layers. We use normalized MSE loss (Section as the loss function.
For predicting the feasibility, our SOCP-GNN follows a similar structure to the one solution prediction. Since the binary classification is simpler than the solution regression, set the hidden layer with 16 neurons. For comparison, our baseline FCNN is implemented with three hidden layers, each containing 16 neurons. We use binary cross-entropy loss as the loss function.
All MLPs mentioned above use ReLU as the activation function. We use AdamW to optimize our learnalee parameters for both FCNNs and GNNs with maximum learning rate of 5 x 10-4 and batch size of 40, All experiments were conducted on an NVIDIA H200 GPU, with the exception of the inference time evaluation.
We denote an SOCP instance by tuple (n, b, m). where represents the number of decision variables, b denotes the number of polyhedral constraints, and indicates the number of second-order cone constraints.
49

---

Published as a conference paper at ICLR 2026
F.3
RESULTS FOR PREDICTING OPTIMAL SOLUTIONS AND FEASIBILITY
GNN Train Loss
GNN Val. Loss
FCNN Train Loss
FCNN Val. Loss
Focsibiity Lo55
Fecelallty
Training Epoch
Training Epoch
Training Epoch
(a) Small SOCP: (50, 10, 10)
(b) Mcdium SOCP (100, 50, 50)
(c) Large SOCP (500, 100, 100)
Figure 7: Comparison between the proposed GNN and FCNN for feasibility classification for random SOCP instances. The GNN uses approximately 0.0IM parameters across three scales, while the FCNN uses approximately 0.07M, O. 7M, and 7M parameters for all three problem scales, respectively.
As shown in Figures 4 and 7 the proposed SOCP-GNN surpasses the baseline FCNNs in both optimal solution prediction and feasibility classification tasks in both synthetic and real-world SOCP instances. Across all problem scales-small, medium, and large-the GNN achieves substantially lower relative MSE and binary cross-entropy loss compared the FCNN baseline. This superior performance is particularly evident in its parameter efficiency: on large-scale problems, the GNN, with only approximately O. 35Mb parameters, outperforms the FCNN, which requires 11 OMb parameters for the solution prediction task, representing nearly 300-fold reduction in model complexity. We also observe similar trends in the feasibility classification tasks.
This dramatic improvement in both performance and efficiency validates the effectiveness of exploit- ing the inherent sparse geometric structure of optimization problems through graph representations and message passing. These results confirm the potential of our approach as scalable, data-driven framework for solving complex optimization problems.
Remark Since we have already proved that target mappings are measurable, follows that: FCNNs can provably approximate these target mappings within any given error tolerance. Hence, it's reasonable to use FCNNs as a baseline for comparison.
F.4 EMPIRICAL STUDY ON SAMPLE/MODEI. COMPLEXITY AND SIZE GENERAL ALIZATION
As shown in Fig ((c) randomly generate 625, 1250, 2500, and 5000 synthetic training samples of size (50, 10, 10) and divide these instances into training, validation, and test data classes by the ratio 8: 1 respectively. We use four SOCP-GNNs with the hidden layer sizes 32, 64, 128, and 256, respectively. Then, we train these four models on the four different datasets, respectively, and then measure their training and validation losses. When the hidden layer size or the number of training samples increases, both the training loss and validation loss decrease. This demonstrates that: with a sufficient number of training samples, the SOCP-GNN can achieve near-zero approximation error and generalize effectively to unseen instances.
Moreover, we randomly generate 6000 synthetic training samples of size (10.5.5), 10), (40,20 20,20, 480,40,40) and (160,80,8) 80) respectively. Then we divide these samples into training and test data classes by the ratio 5 1. Then, we train the SOCP-GNN model with hidden layer size 64 on these datasets, respectively. Finally, each trained model was evaluated on all five test sets to measure its cross-size generalization performance, reported as test loss. The results are summarized Fig 5( It's observed that: models trained on larger problem instances demonstrate superior generalization capabilities, particularly when tested on smaller, unseen problem sizes. Mcanwhile, models trained entirely on smaller datasets also have the surprising ability to generalize to unseen larger datasets. This has validated the good size generalization probability of SOCP-GNNs, which motivates future research efficient training of SOCP- leveraging this size generalization ability.
F.5 EMPIRICAL STUDY ON THE LIPSCHITZ REGULARIZATION
To show how the Lipschitz assumption can be controlled in the experimental setting, we use projection- based methods to train our SOCP-GNN (Gouk et al. 2020). The method operates follows: for
50

---

Published as a conference paper at ICLR 2026
predefined constants À and 1, project each weight matrix W onto an norm ball after each standard optimizer update. Specifically, at the end of every epoch, the weights are updated via the assignment:
W
W
1, 1
max
To validate this approach, we conducted an experiment on the IEEE 1 118-bus dataset. The number of samples and the dividing rules are the same as above, The results are summarized in Table [ In the table, pl lambda0. 5 refers to configuration with p = and À = 0.5. The generalization gap measured by the difference between train loss and true loss, approximating the difference between empirical risk and true risk. The Lipschitz coefficient 7. is measured by randomly picking
10000 pairs of instances x, in dataset and then take the supremum of [f(x)) fiv) experiment for 3 times and take the average.
We repeat the 2-
Table Training and test results for different configurations.
Config
Train Loss
Test Loss
Gen Gap
Lip-L
baseline
0.004885
0.005076
0.000191
0.5186
p1 _aambda00
0.008184
0.008208
0.000024
0.4011
pl.aabd
0.006707
0.006905
0.000199
0.4782
The experimental results indicate that selecting smaller radius for the norm ball leads to lower Lipschitz constant for the model. This suggests that the Lipschitz constant can be effectively controlled by constraining the norm of the weight matrices.
51


Reviews:
[{"review_id": "xzegwHqq5N", "reviewer": "Reviewer_5AzP", "summary": "This ICLR submission proposes a graph representation and Graph Neural Network (GNN) architecture, termed SOCP-GNN, for solving Second-Order Cone Programs (SOCPs). The graph representation has variable, polyhedral, minor conic, and major conic nodes, enabling message-passing GNNs to predict key properties like feasibility and optimal solutions. They prove universal approximation capabilities using Weisfeiler-Lehman-based expressivity and derive sample complexity bounds via Rademacher complexity for generalization. The approach generalizes to p-order cone programs and demonstrates empirical superiority on synthetic SOCPs and real-world power grid problems, using fewer parameters than fully connected networks.", "questions": "Is it possible to add quadratic terms in the objective function, as in (Wu et al., 2024; Chen et al., 2024b)?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is in general well written, and the main results are easy to follow.\n\n2. The paper provides the generalization analysis beyond WL-test-based GNN analysis, deriving sample complexity bounds via Rademacher complexity.", "weaknesses": "The WL-test-based universal approximation analysis is not completely new; it uses ideas from (Chen et al., 2022b), as the authors explicitly noted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "gZcMF7V4rk", "reviewer": "Reviewer_wvA8", "summary": "The present manuscript addresses the solution of Second-Order Cone Programs (SOCPs) by means of Graph Neural Networks, specifically designed to process the variables-constraints graph arising from such problems, with a lightweight implementation that is competitive in terms of computational complexity.\nThe authors provide universal approximation results and generalization bounds for the proposed model, and evaluate their model against  traditional SOCP solvers.", "questions": "- I would suggest the authors to revise the literature over generalization results for GNNs, as suggested above;\n- I would suggest the authors make explicit connections between the experimental validation and the theoretical results;\n- Lastly, I would strongly encourage the authors to insert a (possibly) fair comparison with deep learning-based OPF solvers.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The literature review is accurate and broad, and the related work is addressed (almost) properly. \nThe theoretical results are meaningful and derived with deep rigorousness (the Appendix has been checked). \nAll the needed mathematical concepts are clearly introduced and explained, and intuitive readings of the theoretical results are provided. \nThe experimental evaluation on synthetic data is well set and well conducted.", "weaknesses": "Major concerns:\n- The literature review on VC dimension for GNNs is not complete, please check [1];\n- at line 306, a Lipschitz assumption on GNN is stated; although, as noted by the authors, this is frequent in theoretical analysis of generalization capabilities of GNNs, I don't think that such property has been properly addressed when switching to the experimental framework;\n- a similar concern arises about connecting the generalization bound with the experiments, i.e.  there are not connections between Theorem 2 and the experiments in Section 7;\n- lastly, even if this paper is a proof of concept, the authors propose a benchmarking over AC-OPF solvers; in this case, I think that a comparison with actual deep learning OPF solvers is needed.\n\nMinor concerns:\n- line 104, \"specially\" -> \"specifically\"\n- line 128, \"representations\" -> \"representation\"\n- line 1845-1847: \"Lipshitz\" -> \"Lipschitz\"\n\n[1] D’Inverno, G. A., Bianchini, M., & Scarselli, F. (2025). VC dimension of Graph Neural Networks with Pfaffian activation functions. Neural Networks, 182, 106924.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "aeSTEN3GXv", "reviewer": "Reviewer_tMNV", "summary": "The author proposed a novel graph representation for SOCPs, that is a major class of convex optimization problems. Based on this representation, the author proposed a GNN structure called SOCP-GNN, that is simple enough to be effective. Additionally, the author analyzed the representation power and generalization capability of SOCP-GNN. Finally, the author provided the results a series of experiments to validate the proposed framework.", "questions": "- In the comparison of node complexity and MP complexity, the ranks of the cone constraints are denoted by $k_{i} $instead of $r_{i}$. $r_{i}$ is used to denote the rank of quadratic constraints, but here we are not discussing quadratic constraints.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- The new graph representation extends to SOCP problems, which is more general than previously considered LP, QP, and QCQPs. And on the representation, the proposed structure is simple enough, while having enough representation power to express the inherent structure of SOCP instances.\n- The author provides a framework for analyzing the generalization capability of SOCP-GNN or other structures with representation power guarantee established by WL-test and relevant tool(i.e. Lusin's theorem and Generalized Stone-Weierstrass Theorem).", "weaknesses": "- The previous representation on QCQPs **benefits from sparsity** to get better MP complexity and the SOCP-GNN(when applied on equivalent reformulated QCQPs) benefits from **the constraints being low-rank**. The author claimed that the proposed structure is less complex when used on equivalent reformulated convex QCQPs, but there is no argument about relation between sparsity of the original QCQP instance and the complexity of the reformulated instance.\n- SOCPs do not cover **general** QCQPs, since only convex QCQPs can be directly reformulated to equivalent SOCPs, and SOCPs reformulated to special non-convex QCQPs (since the special combination of non-convex quadratic constraints and linear constraint makes it **implicitly convex** to be solved in polynomial time). So there is not too much improvement with respect to general non-convex QCQPs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "MiCejo4CFm", "reviewer": "Reviewer_c5JN", "summary": "This paper proposed a way to encode SOCP problems with graphs, which is an important extension of LP, QP, QCQP problems. The authors designed a message passing scheme on top. Besides, the separation power of WL on such graphs as well as generalization bounds are established. The empirical results also exhibited the sigfinicance of the work.", "questions": "- What are the hardwares for comparing solving time of SOCP-GNN and MOSEK solver? It seems that the GNN has constant solving time with the growth of the instance size, so I guess it is on GPU. Did you also run MOSEK on GPU? If not that is not fare comparison.\n- It is mentioned in the appendix that extending the work to more general $p$ cone only requires encoding $p$ parameter in the graph. It is plausible in the perspective of WL test, but does it hurt the generalization performance? For example, will there be such a family of problems, where different $p$ leads to the same solution?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The problem is well motivated. SOCP is an important extension of LP, QCQP, and this work is an important milestone towards more general convex cones. \n- The paper is well written and easy to read. \n- The design of the graph encoding for SOCP problems make a lot of sense, and faithfully encode all the information of an SOCP problem.\n- The theoretical results are well established.", "weaknesses": "- I think the separation power of WL on SOCP is also an important point and should be mentioned in the main paper as well. \n- The notations of graph nodes are a bit confusing, they are inconsistent in section 4.1 and figure 2. \n- I understand there might be lack of baselines, but FCNN baseline is a bit too trivial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)