|
Abstract:
|
Detecting correlation between Euclidean vectors is one of the most classical and widely studied inference problems in multivariate statistics, while correlation testing for graphs is much less studied. Part of the difficulty lies in choosing an appropriate notion of correlation for graph-valued data. We are motivated by the problem of, given a pair of graphs on the same vertex set, determining whether or not the presence of an edge between any two chosen vertices in the first graph is correlated with the presence of an edge between the same vertices in the second graph. This notion of correlation appears in many real data applications, such as two networks on different social platforms and two knowledge graphs constructed using documents on the same topics but in different languages. We derive a necessary condition for the existence of a valid and consistent test procedure for the correlation testing problem and show that it exhibits a statistical vs. computational tradeoff. We consider a special case of the problem where the graphs are sampled from the graphon or latent space model and propose an asymptotically valid and consistent test procedure that also runs in polynomial time.
|
