# Maximum a Posteriori Inference of Random Dot Product Graphs via Conic Programming

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

## Key facts

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

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

- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016)
- [A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion](https://mlsanity.com/paper/1309.6013/) (2013)
- [Limit theorems for eigenvectors of the normalized Laplacian for random graphs](https://mlsanity.com/paper/1607.08601/) (2016)
- [Joint Embedding of Graphs](https://mlsanity.com/paper/1703.03862/) (2017)
- [On the Burer-Monteiro method for general semidefinite programs](https://mlsanity.com/paper/1904.07147/) (2019)
- [Vertex Nomination, Consistent Estimation, and Adversarial Modification](https://mlsanity.com/paper/1905.01776/) (2019)
- [Dimensionality Reduction for Binary Data through the Projection of Natural Parameters](https://mlsanity.com/paper/1510.06112/) (2015)
- [Vertex nomination: The canonical sampling and the extended spectral nomination schemes](https://mlsanity.com/paper/1802.04960/) (2018)
- [Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks](https://mlsanity.com/paper/1812.10519/) (2018)
- [Simultaneous Dimensionality and Complexity Model Selection for Spectral Graph Clustering](https://mlsanity.com/paper/1904.02926/) (2019)
- [A Random Dot Product Model for Weighted Networks](https://mlsanity.com/paper/1611.02530/) (2016)
- [Robust Vertex Classification](https://mlsanity.com/paper/1311.5954/) (2013)

## Abstract (arXiv)

We present a convex cone program to infer the latent probability matrix of a random dot product graph (RDPG). The optimization problem maximizes the Bernoulli maximum likelihood function with an added nuclear norm regularization term. The dual problem has a particularly nice form, related to the well-known semidefinite program relaxation of the MaxCut problem. Using the primal-dual optimality conditions, we bound the entries and rank of the primal and dual solutions. Furthermore, we bound the optimal objective value and prove asymptotic consistency of the probability estimates of a slightly modified model under mild technical assumptions. Our experiments on synthetic RDPGs not only recover natural clusters, but also reveal the underlying low-dimensional geometry of the original data. We also demonstrate that the method recovers latent structure in the Karate Club Graph and synthetic U.S. Senate vote graphs and is scalable to graphs with up to a few hundred nodes.