  Testing for independence between graphs is a problem that arises naturally in
social network analysis and neuroscience. In this paper, we address
independence testing for inhomogeneous Erd\H{o}s-R\'{e}nyi random graphs on the
same vertex set. We first formulate a notion of pairwise correlations between
the edges of these graphs and derive a necessary condition for their
detectability. We next show that the problem can exhibit a statistical vs.
computational tradeoff, i.e., there are regimes for which the correlations are
statistically detectable but may require algorithms whose running time is
exponential in n, the number of vertices. Finally, we consider a special case
of correlation testing when the graphs are sampled from a latent space model
(graphon) and propose an asymptotically valid and consistent test procedure
that also runs in time polynomial in n.
