Scaling Semidefinite Relaxations for Large Graphs

This direction is merged into another direction: semidefinite programming scalability (computational scalability of semidefinite programming). Its last version stays readable and citable here.

Version 1 of 1122 papers127 conceptsfrozen 2026-10-04

Graph problems are notoriously difficult because they are discrete. If you want to partition a network into two communities, you are essentially making a series of binary choices: node $i$ is either in Group A or Group B. This leads to a combinatorial explosion that makes problems like Max-Cut or the Stochastic Block Model (SBM) NP-hard in their raw form.

To bypass this, researchers use Semidefinite Programming (SDP) relaxations. Instead of forcing a hard "yes/no" choice, we "relax" the problem into a continuous space where nodes are represented by vectors on a high-dimensional sphere. This transformation turns a jagged, impossible landscape into a smooth, convex one that we can solve with global optimality.

However, this elegance comes at a steep price. While SDPs are technically solvable in polynomial time, their computational cost is often $O(n^3)$ or worse. In an era of billion-node social networks, this creates a massive "scalability wall."

The Intuition of Lifting and Smoothing

Why bother with SDPs if they are so slow? The answer lies in their robustness.

Simple spectral methods—which look at the eigenvectors of a graph's adjacency matrix—are fast but fragile. As Andrea Montanari and Subhabrata Sen demonstrate in Semidefinite Programs on Sparse Random Graphs, spectral methods are easily distracted by "hubs" (nodes with unusually high degrees). These hubs create "spikes" in the spectrum that mask the true community structure.

SDPs act as a mathematical "smoothing" agent. By lifting the problem into a higher-dimensional matrix space, the optimization naturally de-emphasizes these local irregularities. This allows SDPs to reach the information-theoretic limit for community detection—the Kesten-Stigum threshold—even when the graph is sparse or noisy. Yury Makarychev further shows in Learning Communities in the Presence of Errors that this framework is uniquely capable of resisting adversarial noise, where an attacker intentionally adds or removes edges to mislead the algorithm.

The Scalability Wall

The central tension in recent research is that the very thing that makes SDPs powerful—the large matrix of relationships between all pairs of nodes—makes them impractical for large datasets.

In Theoretical Bounds on the Network Community Profile from Low-rank Semi-definite Programming, Yufan Huang and David F. Gleich point out that even "efficient" low-rank SDP solvers can take days to process a network with just a few hundred thousand nodes. For web-scale graphs, traditional interior-point solvers are essentially non-starters.

This has led to a search for "first-order" methods—algorithms that use only gradients rather than complex second-order derivatives. Shiau Hong Lim explores this in Labeled Graph Clustering via Projected Gradient Descent, showing that non-convex approaches like Projected Gradient Descent can sometimes achieve the same rigorous recovery guarantees as SDPs but with orders-of-magnitude faster runtimes.

Bridging Global and Local

A fascinating discovery in this field is that we might not always need to solve the full, global SDP to get its benefits.

Zhou Fan and Fan Zhou proved in How Well Do Local Algorithms Solve Semidefinite Programs? that for certain random graph models, simple local heuristics can approximate the results of complex SDP relaxations surprisingly well. This suggests that the "global" wisdom of an SDP is often encoded in the local structure of the graph, waiting to be extracted by faster, more scalable algorithms.

Similarly, the Locale algorithm attempts to bridge this gap by replacing the greedy "local moves" of popular methods like Louvain with a localized semidefinite relaxation. By focusing on the low-cardinality (sparsity) of the solution, they achieve the robustness of a global optimizer without the $O(n^3)$ overhead.

Why It Matters: Beyond Simple Clustering

This research isn't just about finding groups in a social network. The principles of convex relaxation are being applied to:

  1. Causal Inference: Davide Viviano and colleagues use these techniques in Causal clustering: design of cluster experiments under network interference to design A/B tests that are robust to "spillovers" (when one person's treatment affects their neighbor).
  2. Privacy: David Steurer and others use Sum-of-Squares (a higher-order form of SDP) to estimate graph properties while maintaining strict differential privacy, as seen in Private Edge Density Estimation for Random Graphs.
  3. Structured Prediction: Kevin Bello and Jean Honorio show in Exact inference in structured prediction that SDPs can turn NP-hard inference tasks into solvable polynomial problems for a wide class of graphs.

The future of this field lies in narrowing the gap between the theoretical optimality of the semidefinite relaxation and the practical necessity of linear-time algorithms. Whether through low-rank approximations, local smoothing, or neural-network-guided optimization, the goal remains the same: capturing the global structural truth of a network without getting lost in its massive scale.

Papers in this version

Showing 60 of 122 papers.

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_scaling_semidefinite_relaxations_for_lar_0f388853,
  title = {Scaling Semidefinite Relaxations for Large Graphs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-semidefinite-relaxations-for-large-graphs/rdr_0f388853c6434004adb9b5bd8d2bd7b6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_scaling_semidefinite_relaxations_for_lar_0f388853_v1,
  title = {Scaling Semidefinite Relaxations for Large Graphs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-semidefinite-relaxations-for-large-graphs/rdr_0f388853c6434004adb9b5bd8d2bd7b6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}