Quantifying Network Similarity using Graph Cumulants

How might one test the hypothesis that networks were sampled from the same distribution? Here, we compare two statistical tests that use <PRE_TAG><PRE_TAG>subgraph counts</POST_TAG></POST_TAG> to address this question. The first uses the <PRE_TAG>empirical subgraph densities</POST_TAG> themselves as estimates of those of the <PRE_TAG>underlying distribution</POST_TAG>. The second test uses a new approach that converts these subgraph densities into estimates of the <PRE_TAG><PRE_TAG><PRE_TAG><PRE_TAG>graph cumulants</POST_TAG></POST_TAG></POST_TAG></POST_TAG> of the distribution (without any increase in computational complexity). We demonstrate -- via theory, <PRE_TAG>simulation</POST_TAG>, and application to <PRE_TAG>real data</POST_TAG> -- the superior <PRE_TAG>statistical power</POST_TAG> of using graph cumulants. In summary, when analyzing data using <PRE_TAG>subgraph/motif densities</POST_TAG>, we suggest using the corresponding <PRE_TAG><PRE_TAG><PRE_TAG><PRE_TAG>graph cumulants</POST_TAG></POST_TAG></POST_TAG></POST_TAG> instead.