On the Expressive Power of GNNs to Solve Linear SDPs

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

Many important decision-making problems, such as finding cuts in graphs, coloring graphs, or solving control problems, can be written as semidefinite programs (SDP), a powerful type of optimization problem. However, solving large semidefinite programs with traditional optimization software can be very slow, which limits their use in practice. This paper studies whether graph neural networks (GNN) can learn to predict the solutions of these problems much faster. We show that standard GNNs are not expressive enough, because they treat the entries of the solution matrix too independently and miss important matrix structure. We then identify a more expressive GNN design that captures the symmetries and interactions needed for SDPs. Theoretically, we prove that this architecture is powerful enough to emulate the steps of a standard optimization algorithm for these problems. Experimentally, it predicts higher-quality solutions than weaker GNNs on both synthetic benchmarks and real-world instances. Its predictions can also be used to warm-start a classical solver, reducing solving time by up to about 80%. Overall, this work provides a principled way to design machine learning models that can accelerate an important class of optimization problems.