Accurate and Efficient MCMC for Latent Position Models

Zonghao Li and Aaron Smith · 2026

Read Accurate and Efficient MCMC for Latent Position Models by Zonghao Li and Aaron Smith (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-30134.txt.

Introduction

Zonghao Li and Aaron Smith offer two faster MCMC algorithms for latent position graph models. Fitting Bayesian versions is costly because one likelihood evaluation takes time quadratic in vertex count. Earlier algorithms approach edge-count time, the closest prior work reaching almost edge-count time with good performance. Their fast algorithm matches that time with stronger accuracy guarantees, while their faster algorithm reaches almost vertex-count time with improved guarantees. Both gains come from a cheap auxiliary data structure updated during runs, which may help other MCMC algorithms.

Catalog record

CREATORZonghao Li and Aaron Smith
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE79646
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.30134

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Accurate and Efficient MCMC for Latent Position Models Zonghao Li and Aaron Smith Abstract . Latent position models (LPMs) are a large and popular class of models for random graphs. However, fitting Bayesian LPMs is computationally challenging - computing the likelihood even once takes time that is quadratic in the number of vertices | V | |V| of the observed graph G = ( V , E ) G=(V,E) . Many previous papers have introduced approximate MCMC algorithms to speed this up, with the most similar to ours [ 25 ] presenting an algorithm that has amortized running time that can be reduced almost to O ⁡ ( | E | ) O(|E|) and good empirical performance on reasonable inference problems. The present paper offers two algorithms for solving the same problem: a “fast” algorithm with running time of the same almost- O ⁡ ( | E | ) O(|E|) order as [ 25 ] and much stronger accuracy guarantees, and a “faster” algorithm with an improved running time of almost O ⁡ ( | V | ) O(|V|) , and accuracy guarantees that are slightly improved compared to [ 25 ] (but not sufficient for all tasks). The main improvements come from the introduction of a simple auxiliary data structure that can be cheaply updated during an MCMC run; we suspect that the same “cheap sketch” may be useful for other MCMC algorithms. 1. Introduction Statistical network analysis has emerged as a prominent topic of interest across major fields of study including economics, biology, sociology, and finance (see e.g. textbooks [ 33 , 14 ] ), as well as specialized topics such as education research [ 31 ] and traffic prediction [ 6 ] . The first statistical network model was the famous (but very simple) Erdos-Renyi random graphs [ 7 ] . Almost immediately, statisticians started studying “geometric” models for networks, in which the nodes were assumed to have unknown “latent” positions that influenced edge formation [ 9 ] . The modern notion of latent position models (LPMs) was introduced by Hoff et al. [ 11 ] , and LPMs and their variants remain popular statistical models for networks (see the survey [ 15 ] for many variants and applications). Many variants of LPMs have been proposed (see e.g. [ 10 , 16 , 3 ] and the survey [ 15 ] ). In this paper, we focus on the following class of joint models on latent positions and generated graphs: Definition 1.1 . Fix a latent space \Omega , prior distribution \pi_{\Omega} on \Omega , a symmetric link function p\,:\,\Omega^{2}\to[0,1] satisfying p(x,y)=p(y,x) , and size n . The latent position model associated with the choices (\Omega,\pi_{\Omega},p,n) is a distribution on graphs G=(V,E) and latent positions Z_{1},\ldots,Z_{n}\in\Omega , given by setting V=[n] , sampling Z_{1},\ldots,Z_{n}\stackrel{{\scriptstyle iid}}{{\sim}}\pi_{\Omega} , and finally sampling the unordered edge set E_{und}\subseteq\{\{i,j\}:1\leq i<j\leq n\} conditional on Z_{1},\ldots,Z_{n} according to the distribution: P [E_und — Z_1,…,Z_n] = ∏_ 1≤i¡j≤n {i,j} ∈E p(Z_i,Z_j) ∏_ 1≤i¡j≤n {i,j} ∉E (1- p(Z_i,Z_j)). By a small abuse of notation, we will often call this the latent position model associated with link function p (hiding the dependence on the other choices). Unfortunately, it is difficult to fit models of the sort given in Definition 1.1 to large graphs using Markov chain Monte Carlo (MCMC). The first difficulty is that the evaluation of the likelihood ( ) takes O(|V|^{2}) computations, and this likelihood must typically be evaluated many times during an MCMC run. This quadratic complexity has seriously hurt the applicability of Bayesian methods to large datasets. Even this quadratic complexity is often optimistic, as simple Markov chains can mix more slowly for large |V| . Similar problems occur when fitting many Bayesian models to large datasets, and many solutions have been proposed. Our paper’s approach is in the category of “approximate” or “perturbed” MCMC: we find an MCMC algorithm that is fast, and has a stationary measure that is close but not equal to the posterior distribution associated with the model defined in Equation ( ). There are many ways to “perturb” nice models such as ( ). We review here caricatures of the most relevant approaches; see e.g. [ 26 ] for a recent survey. The most famous and general-purpose approach to perturbing a Markov chain is to use mini-batch algorithms such as stochastic gradient Langevin dynamics: at each step of the MCMC algorithm, you take a small random sample of the edges and use them to estimate ( ) (see e.g. [ 2 ] for an early survey of this approach). These methods are very fast and easy to implement, but they are also known to give poor approximations to the posterior in many cases [ 20 , 13 , 5 , 22 ] . Another approach, taken by [ 25 ] and others, is to chop up the state space \Omega and use a low-resolution proxy for the true likelihood ( ). This is close to the philosophy of the present paper, though unlike [ 25 ] we don’t literally partition \Omega . Our main differences come in the details: rather than constructing an explicit hard partition of the state space \Omega , we calculate moments associated with an adaptive, implicit and soft partition. These small-looking differences end up having a substantial impact on the asymptotic complexity or accuracy (or both) of our algorithms. 1.1. Asymptotics and Comparison to [ 25 ] Our paper presents two new algorithms, both based on finding computationally-tractable proxies for the likelihood ( ). We give here a short and informal discussion of the asymptotic running times and error bounds of these algorithms, deferring the technical details and main assumptions to Section 6 . We also compare these bounds to the state-of-the-art results of [ 25 ] , which takes a fairly similar approach and inspired this paper. We use two main quantities in comparing the algorithms. The first is what we call the “amortized cost per sweep.” All algorithms considered in this section involve a main loop that changes the embedding of a single node at a time. The “amortized cost per sweep” is roughly the number of basic computations required to move the latent embedding of every node . 1 1 1 Following standard practice in estimating the complexities of algorithms in computational statistics, we count the steps in our pseudocode descriptions of the algorithms, ignoring the details of e.g. how data is stored and retrieved. We also ignore the number of steps required for the chain to mix, which can depend quite strongly on the details of the hyperparameters. The second quantity is what we call the “total variation error” - this is just the total variation distance between the posterior distribution associated with the data and the stationary distribution of our MCMC algorithm. Both our algorithms, and the algorithm in [ 25 ] , come with a “size” parameter b that roughly indicates the resolution of the partition of \Omega . Our first algorithm, Algorithm 9 , also comes with an “order” parameter \kappa , indicating the size of the data structure to maintain. The standard Metropolis-within-Gibbs (MwG) algorithm has amortized cost of O(|V|^{2}) , and the stationary distribution is

Read the complete text