Search papers, labs, and topics across Lattice.
This paper investigates the ability of GNNs to act as surrogates for solving linear Semidefinite Programs (SDPs). It demonstrates that standard GNN architectures are insufficient for recovering optimal SDP solutions, but a more expressive architecture, capable of emulating first-order solver updates, can effectively learn to predict SDP solutions. Empirically, this enhanced GNN achieves lower prediction error and objective gaps, and warm-starting a first-order solver with its predictions yields up to 80% speedups.
Standard GNNs can't cut it for solving linear SDPs, but a carefully designed architecture that mimics first-order solver updates can learn to predict solutions and dramatically accelerate convergence.
Semidefinite programs (SDPs) are a powerful framework for convex optimization and for constructing strong relaxations of hard combinatorial problems. However, solving large SDPs can be computationally expensive, motivating the use of machine learning models as fast computational surrogates. Graph neural networks (GNNs) are a natural candidate in this setting due to their sparsity-awareness and ability to model variable-constraint interactions. In this work, we study what expressive power is sufficient to recover optimal SDP solutions. We first prove negative results showing that standard GNN architectures fail on recovering linear SDP solutions. We then identify a more expressive architecture that captures the key structure of SDPs and can, in particular, emulate the updates of a standard first-order solver. Empirically, on both synthetic and \textsc{SdpLib} benchmarks of various classes of SDPs, this more expressive architecture achieves consistently lower prediction error and objective gap than theoretically weaker baselines. Finally, using the learned high-quality predictions to warm-start the first-order solver yields practical speedups of up to 80%.
