Testing Dependency of Weighted Random Graphs

Consider the following decision problem. We observe two weighted random graphs that are either generated independently at random or are edge-dependent due to some latent vertex correspondence or permutation. For this basic problem, two natural questions arise: the detection problem, which concerns whether the graphs exhibit dependence, and the recovery problem, which concerns identifying the latent correspondence between vertices. Here, we address the former question, specifically, we aim to understand under what conditions, in terms of the number of vertices and the generative distributions, one can distinguish between the two hypotheses and detect whether these graphs are dependent or not, say, with high probability? The fundamental question above was first introduced and analyzed in [1], where for Gaussian-weighted and dense Erdős-Rényi random graphs on n vertices, sharp informationtheoretic thresholds were developed, revealing the exact barrier at which the asymptotic optimal detection error probability undergoes a phase transition from zero to one as n approaches infinity. For sparse Erdős-Rényi random graphs this threshold was initially determined within a constant factor in the same paper.