In this paper, we study the problem of testing for edge dependence between two weighted random graphs observed up to vertex relabeling. We formulate it as a binary hypothesis testing problem: under the null hypothesis, the two observed graphs are statistically independent, whereas under the alternative, the edges of one graph are correlated with the edges of a randomly vertex-permuted version of the other graph. For general edge-weight distributions, we establish thresholds at which optimal testing is information-theoretically impossible and possible, in terms of the number of vertices and the underlying weight distributions. Finally, we exhibit a statistical– computational gap for this problem and provide evidence that it is fundamental, using the low-degree polynomial framework.

In this paper, we investigate the problem of deciding whether two random databases$\textsf {X}\in {\mathcal { X}} ^{n\times d}$and$\textsf {Y}\in {\mathcal { Y}} ^{n\times d}$are statistically dependent or not. This is formulated as a hypothesis testing problem, where under the null hypothesis, these two databases are statistically independent, while under the alternative, there exists an unknown row permutation$\sigma $, such that$\textsf {X}$and$\textsf {Y}^{\sigma } $, a permuted version of$\textsf {Y}$, are statistically dependent with some known joint distribution, but have the same marginal distributions as the null. We characterize the thresholds at which optimal testing is information-theoretically impossible and possible, as a function of n, d, and some spectral properties of the generative distributions of the datasets. For example, we prove that if a certain function of the eigenvalues of the likelihood function and d, is below a certain threshold, as$d\to \infty $, then weak detection (performing slightly better than random guessing) is statistically impossible, no matter what the value of n is. This mimics the performance of an efficient test that thresholds a centered version of the log-likelihood function of the observed matrices. We also analyze the case where d is fixed, for which we derive strong (vanishing error) and weak detection lower and upper bounds.