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

DOI10.1137/20M1389406MaRDI QIDQ6357733arXivFDO

Authors David X. Wu, David T. Palmer, Daryl Deford

Publication date 6 January 2021

Published in arXiv

Full work available at URL https://doi.org/10.1137/20M1389406

Mathematics Subject Classification ID

Positive matrices and their generalizations; cones of matrices (15B48) Bayesian inference (62F15) Numerical methods for low-rank matrix approximation; matrix compression (65F55) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

arXiv classification

cs.LGmath.OCstat.ML

Abstract: 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.

This page was built for publication: Maximum a Posteriori Inference of Random Dot Product Graphs via Conic Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6357733)