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

arXiv: https://arxiv.org/abs/2102.08019 · HTML: https://mlsanity.com/paper/2102.08019/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 40 references that are in the map.
- First posted on arXiv 16 Feb 2021.

## Builds on (most cited first, 16 of 16)

- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [SPONGE: A generalized eigenproblem for clustering signed networks](https://mlsanity.com/paper/1904.08575/) (2019)
- [On semidefinite relaxations for the block model](https://mlsanity.com/paper/1406.5647/) (2014)
- [Sum-of-squares proofs and the quest toward optimal algorithms](https://mlsanity.com/paper/1404.5236/) (2014)
- [Sum-of-squares lower bounds for planted clique](https://mlsanity.com/paper/1503.06447/) (2015)
- [Clustering Signed Networks with the Geometric Mean of Laplacians](https://mlsanity.com/paper/1701.00757/) (2017)
- [Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4](https://mlsanity.com/paper/1911.01411/) (2019)
- [Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity](https://mlsanity.com/paper/1607.01151/) (2016)
- [On spectral partitioning of signed graphs](https://mlsanity.com/paper/1701.01394/) (2017)
- [Exact inference in structured prediction](https://mlsanity.com/paper/1906.00451/) (2019)
- [On the Definiteness of the Weighted Laplacian and its Connection to Effective Resistance](https://mlsanity.com/paper/1408.2187/) (2014)
- [Cheeger constants, structural balance, and spectral clustering analysis for signed graphs](https://mlsanity.com/paper/1411.3530/) (2014)
- [Inference in Graphical Models via Semidefinite Programming Hierarchies](https://mlsanity.com/paper/1709.06525/) (2017)
- [The Geometry of SDP-Exactness in Quadratic Optimization](https://mlsanity.com/paper/1804.01796/) (2018)
- [Fairness constraints can help exact inference in structured prediction](https://mlsanity.com/paper/2007.00218/) (2020)
- [A Gramian Description of the Degree 4 Generalized Elliptope](https://mlsanity.com/paper/1812.11583/) (2018)

## Abstract (arXiv)

Performing inference in graphs is a common task within several machine learning problems, e.g., image segmentation, community detection, among others. For a given undirected connected graph, we tackle the statistical problem of exactly recovering an unknown ground-truth binary labeling of the nodes from a single corrupted observation of each edge. Such problem can be formulated as a quadratic combinatorial optimization problem over the boolean hypercube, where it has been shown before that one can (with high probability and in polynomial time) exactly recover the ground-truth labeling of graphs that have an isoperimetric number that grows with respect to the number of nodes (e.g., complete graphs, regular expanders). In this work, we apply a powerful hierarchy of relaxations, known as the sum-of-squares (SoS) hierarchy, to the combinatorial problem. Motivated by empirical evidence on the improvement in exact recoverability, we center our attention on the degree-4 SoS relaxation and set out to understand the origin of such improvement from a graph theoretical perspective. We show that the solution of the dual of the relaxed problem is related to finding edge weights of the Johnson and Kneser graphs, where the weights fulfill the SoS constraints and intuitively allow the input graph to increase its algebraic connectivity. Finally, as byproduct of our analysis, we derive a novel Cheeger-type lower bound for the algebraic connectivity of graphs with signed edge weights.