Testing Correlation in Graphs by Counting Bounded Degree Motifs

Dong Huang, Pengkun Yang

We investigate the problem of detecting correlation between two Erdős-Rényi graphs $G(n,p)$, formulated as a hypothesis testing problem: under the null hypothesis, the two graphs a…