A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy

Kevin Bello, Chuyang Ke, Jean Honorio

Abstract

This paper investigates the theoretical mechanisms that allow the degree-4 Sum-of-Squares (SoS) hierarchy to outperform standard Semidefinite Programming (SDP) in graph inference tasks. By analyzing the dual optimization problem, the authors reveal that SoS constraints effectively construct higher-order graph representations—specifically Johnson and Kneser graphs—and optimize their edge weights to enhance algebraic connectivity. This work provides a bridge between abstract semidefinite hierarchies and concrete spectral graph theory, introducing a novel Cheeger-type bound for signed edge weights and demonstrating superior recovery performance in noisy environments.

Introduction

Graph inference is a fundamental problem in machine learning, underlying tasks such as community detection, image segmentation, and structured prediction. The goal is often exact recovery: perfectly reconstructing ground-truth labels from noisy observations of node relationships. Mathematically, this is formulated as a quadratic combinatorial optimization problem over a boolean hypercube, which is NP-hard. To solve it efficiently, researchers rely on convex relaxations. While Semidefinite Programming (SDP) is a common choice, it frequently fails on complex or noisy graph structures. The Sum-of-Squares (SoS) hierarchy provides a sequence of tighter relaxations, with degree-4 SoS showing significant empirical gains over SDP. However, the theoretical reasons for this improvement have historically been difficult to pinpoint.

Methodology: Higher-Order Graph Construction

The authors analyze the degree-4 SoS relaxation by examining its dual formulation. A key finding is that the degree-4 SoS optimization is equivalent to an optimization problem over a "level-2" graph. In this higher-order structure, the nodes represent pairs of nodes from the original graph.

Higher-order graph construction where nodes represent pairs of original nodes.

This construction links SoS constraints to classical algebraic graph theory, specifically Johnson Graphs (where nodes share one element) and Kneser Graphs (where nodes are disjoint). The condition for exact recovery is then framed as maintaining a positive "algebraic connectivity" (the second smallest eigenvalue of the Laplacian) in this higher-order graph.

Theoretical Insights: Reweighting and Connectivity

The core insight of the paper is the reweighting intuition. The degree-4 SoS hierarchy does not merely restrict the search space; it dynamically finds optimal edge weights for the associated Johnson and Kneser graphs. These weights allow the algorithm to "boost" the connectivity of the input graph, stabilizing the ground-truth solution against noise.

Furthermore, because SoS dual variables can be negative, the authors developed a novel Cheeger-type lower bound for graphs with signed edge weights. This theoretical contribution extends standard spectral graph theory, which typically assumes positive weights, and provides a rigorous tool for analyzing the stability of SoS solutions.

Empirical Results

To validate their theoretical framework, the authors conducted simulations comparing SDP and degree-4 SoS on structured prediction tasks. As edge noise increases, the probability of exact recovery for SDP drops precipitously. In contrast, degree-4 SoS maintains a significantly higher recovery rate, demonstrating its robustness.

Probability of exact recovery for SDP vs. SOS D4 as a function of edge noise.

In a specific 5-node "failure case" for SDP, the authors showed that the critical eigenvalue $\lambda_2$ was negative (-0.24), leading to recovery failure. By applying degree-4 SoS and utilizing the optimized Johnson/Kneser weights, the eigenvalue became positive (0.95), guaranteeing exact recovery.

Conclusion and Future Work

This research successfully demystifies the performance of the degree-4 SoS hierarchy by grounding it in graph-theoretic properties. While powerful, the $O(n^4)$ computational complexity of degree-4 SoS remains a barrier for large-scale applications. Future work will focus on improving scalability and exploring whether higher levels of the hierarchy (e.g., degree-6) offer similar structural insights through even higher-order graph representations.

Summary updated

BibTeX
@inproceedings{bello2022thorough,
  author = {Kevin Bello and Chuyang Ke and Jean Honorio},
  title = {{A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=TUVJ3T_Achf},
}
Figure