LA Probability Forum

I will discuss a random geometric graph model, where connections between vertices depend on the distances between latent d-dimensional feature vectors. We are especially interested in the high-dimensional case when d is large. Upon observing a graph, our aim is to recover these latent feature vectors (i.e., embedding). We have identified a phase transition phenomenon: when d is significantly larger than nH(p) (with a polylogarithmic term), embedding becomes feasible with high probability using a spectral algorithm. H here represents the entropy function. Conversely, when d is considerably smaller than nH(p), embedding becomes information theoretically impossible. In our proof of the impossibility result, we design a dynamics and show that it can find two distant embeddings that produce the same graph. This is based on joint works with Eric Ma and Tselil Schramm.