Phase transitions for detecting latent geometry in random graphs

Random graphs with latent geometric structure are popular models of social and biological networks, with applications ranging from network user profiling to circuit design. These graphs are also of purely theoretical interest within computer science, probability and statistics. A fundamental initial question regarding these models is: when are these random graphs affected by their latent geometry and when are they indistinguishable from simpler models without latent structure, such as the Erdos-Renyi graph G(n, p)? We address this question for two of the most well-studied models of random graphs with latent geometry-the random intersection and random geometric graph. Our results are as follows: (a) The random intersection graph is defined by sampling n random sets S-1, S-2, ... , S-n by including each element of a set of size d in each S-i independently with probability d, and including the edge {i, j} if S-i n S-j not equal circle divide. We prove that the random intersection graph converges in total variation to an Erdos-Renyi graph if d = (omega) over tilde (n(3)), and does not if d = o(n(3)), for both dense and sparse edge densities p. This resolves an open problem in Fill et al. (Random Struct Algorithms 16(2):156-176, 2000), Rybarczyk (Random Struct Algorithms 38(1-2):205-234, 2011) and Kim et al. (Random Struct Algorithms 52(4):662-679, 2018). The same result was obtained simultaneously and independently by Bubeck et al. (When random intersection graphs lose geometry. Manuscript, 2019). (b) We strengthen the preceding argument to show that the matrix of random intersection sizes vertical bar S-i n S-j vertical bar converges in total variation to a symmetric matrix with independent Poisson entries. This yields the first total variation convergence result for tau-random intersection graphs, where the edge {i, j} is included if vertical bar S-i n S-j vertical bar >= tau. More precisely, our results imply that, if p is bounded away from 1, then the t-random intersection graph with edge density p converges to G(n, p) if d = omega(tau(3)n(3)). (c) The random geometric graph on Sd-1 is defined by sampling X-1, X-2, ... , X-n uniformly at random from Sd-1 and including the edge {i, j} if parallel to X-i - X-j parallel to(2) <= tau. A result of Bubeck et al. (Random Struct Algorithms 49:503-532, 2016) showed that this model converges to G(n, p) in total variation, where p is chosen so that the models have matching edge densities, as long as d = omega(n(3)). It was conjectured in Bubeck et al. (2016) that this threshold decreases drastically for p small. We make the first progress towards this conjecture by showing convergence if d = (omega) over tilde (min{pn(3), p(2)n(7/2)}). Our proofs are a hybrid of combinatorial arguments, direct couplings and applications of information inequalities. Previous upper bounds on the total variation distance between random graphs with latent geometry and G(n, p) have typically not been both combinatorial and information-theoretic, while this interplay is essential to the sharpness of our bounds.