ICM 2026 Invited Section Lecture – Laurent Massoulie
Computational Thresholds in High-Dimensional Statistics: The Case of Graph Alignment Graph alignment is an instance of the NP-hard quadratic assignment problem. It consists, given the adjacency matrices A1, A2 in Rn×n of two graphs, in finding a permutation matrix Π that minimizes the Frobenius norm ∥ΠA1 −A2Π∥F . In this talk we consider the problem from the perspective of high-dimensional statistics: we aim to estimate an unknown permutation π∗ in the symmetric group Sn from the observation of two correlated random adjacency matrices A1, A2. Uploaded 06-10-26 We establish the following computational thresholds. We first consider the case where A1, A2 are the adjacency matrices of two correlated Erd\H{o}s-Rényi random graphs G(n, p) in the sparse regime with average degree λ := np = O(1) and edge correlation parameter s ∈ (0, 1). We identify a critical threshold s∗ (λ) for s above which a message-passing, local algorithm succeeds at alignment –that is, recovers a fraction Ω(1) of the entries of π∗, and below which no local algorithm succeeds. This result crucially depends on an associated model of correlated random trees. We then consider the case where A1, A2 are two correlated Gaussian Wigner matrices with correlation parameter expressed as s = 1/ √ 1 + σ2 where σ is the “noise” parameter. In this setting we consider a fast spectral algorithm based on the leading eigenvectors of the matrices A1, A2, and identify the critical scaling for noise parameter σ at which the fraction of entries of π∗ correctly recovered goes from 1 − o(1) to o(1). We next consider the convex relaxation approach which obtains the doubly stochastic matrix X that minimizes ∥XA1 − A2X∥F . We obtain upper and lower bounds on the critical noise parameter σ at which a simple postprocessing of X correctly recovers a fraction 1 − o(1) of entries of π∗ . We finally identify promising future directions on i) computational thresholds for spectral methods and convex relaxation methods of practical interest, and ii) impossibility results for broad classes of algorithms, notably low degree polynomial algorithms and local search algorithms. Learn more about your ad choices. Visit megaphone.fm/adchoices
