Optimal Network Pairwise Comparison

We are interested in the problem of two-sample network hypothesis testing: given two networks with the same set of nodes, we wish to test whether the underlying Bernoulli probability matrices of the two networks are the same or not. We propose Interlacing Balance Measure (IBM) as a new two-sample testing approach. We consider the <i>Degree-Corrected Mixed-Membership (DCMM)</i> model for undirected networks, where we allow severe degree heterogeneity, mixed-memberships, flexible sparsity levels, and weak signals. In such a broad setting, how to find a test that has a tractable limiting null and optimal testing performances is a challenging problem. We show that IBM is such a test: in a broad DCMM setting with only mild regularity conditions, IBM has N(0,1) as the limiting null and achieves the optimal phase transition. While the above is for undirected networks, IBM is a unified approach and is directly implementable for directed networks. For a broad directed-DCMM (extension of DCMM for directed networks) setting, we show that IBM has N(0,1/2) as the limiting null and continues to achieve the optimal phase transition. We have also applied IBM to the Enron email network and a gene co-expression network, with interesting results.

我们关注双样本网络假设检验问题：给定两个共享同一节点集合的网络，我们需要检验这两个网络的底层伯努利（Bernoulli）概率矩阵是否一致。我们提出交错平衡测度（Interlacing Balance Measure，IBM）作为一种新型双样本检验方法。我们针对无向网络考虑度校正混合成员模型（Degree-Corrected Mixed-Membership，DCMM），该模型允许存在显著的度异质性、混合成员结构、灵活的稀疏性水平以及弱信号。在如此宽泛的模型设定下，如何找到一种具有易处理的极限零分布且具备最优检验性能的检验方法，是一项极具挑战性的问题。我们证明IBM正是符合该要求的检验方法：在仅需温和正则性条件的宽泛DCMM设定下，IBM的极限零分布服从标准正态分布N(0,1)，且可实现最优相变。尽管上述结论针对无向网络，但IBM是一种统一的检验框架，可直接应用于有向网络。针对宽泛的有向DCMM（针对有向网络的DCMM扩展）设定，我们证明IBM的极限零分布服从N(0,1/2)，且同样可实现最优相变。我们还将IBM应用于安然（Enron）邮件网络与基因共表达网络，并获得了颇具意义的研究结果。