Timothy L.H. Wee

To understand how hidden information can be extracted from statistical networks, planted models in random graphs have been the focus of intensive study in recent years. In this work, we consider the detection of a planted matching, i.e., an independent edge set, hidden in an Erdős–Rényi random graph, which is formulated as a hypothesis testing problem. We identify the critical regime for this testing problem and prove that the log-likelihood ratio is asymptotically normal. Via analyses of computationally efficient edge or wedge count test statistics that attain the optimal limits of detection, our results also reveal the absence of a statistical-to-computational gap. Our main technical tool is the cluster expansion from statistical physics, which allows us to prove a precise, non-asymptotic characterization of the log-likelihood ratio. Our analyses rely on a careful reorganization and cancellation of terms that occur in the difference between monomer-dimer log partition functions on the complete and Erdős–Rényi graphs. This combinatorial and statistical physics approach represents a significant departure from the more established methods such as orthogonal decompositions, and positions the cluster expansion as a viable technique in the study of log-likelihood ratios for planted models in general.

Motivated by applications to group synchronization and quadratic assignment on random data, we study a general problem of Bayesian inference of an unknown “signal” belonging to a high-dimensional compact group, given noisy pairwise observations of a featurization of this signal. We establish a quantitative comparison between the signal-observation mutual information in any such problem with that in a simpler model with linear observations, using interpolation methods. For group synchronization, our result proves a replica formula for the asymptotic mutual information and Bayes-optimal mean-squared-error. Via analyses of this replica formula, we show that the conjectural phase transition threshold for computationally-efficient weak recovery of the signal is determined by a classification of the real-irreducible components of the observed group representation(s), and we fully characterize the information-theoretic limits of estimation in the example of angular/phase synchronization over \mathbbSO(2)/\mathbbU(1). For quadratic assignment, we study observations given by a kernel matrix of pairwise similarities and a randomly permutated and noisy counterpart, and we show in a bounded signal-to-noise regime that the asymptotic mutual information coincides with that in a Bayesian spiked model with i.i.d. signal prior.

Define the overlap of a random vector to be its inner product with an independent copy. A random vector whose Euclidean norm and overlap concentrates is shown to have random low-dimensional projections that are approximately random Gaussians. Conversely, asymptotically random Gaussian projections imply these hypotheses. This extends and unites several existing results in geometric functional analysis and spin glasses. Applications include a large-system characterization of the joint law of cavity fields in the Sherrington-Kirkpatrick model.