Nonparametric Two-Sample Hypothesis Testing for Random Graphs with Negative and Repeated Eigenvalues

• Activity Number: 201 - Nonparametric Statistics Student Paper Competition Presentations
• Type: Topic-Contributed
• Date/Time: Tuesday, August 10, 2021 : 1:30 PM to 3:20 PM
• Sponsor: Section on Nonparametric Statistics
• Author(s): Joshua Agterberg* and Minh Tang and Carey E Priebe
• Companies: Johns Hopkins University and North Carolina State University and Johns Hopkins University
• Keywords: Networks; Nonparametric Statistics; Hypothesis Testing; Kernel Methods; Random Graphs; Two-Sample Testing

Abstract

We propose a nonparametric two-sample test statistic for low-rank, conditionally independent edge random graphs whose edge probability matrices have negative eigenvalues and arbitrarily close eigenvalues. Our proposed test statistic involves using the maximum mean discrepancy applied to suitably rotated rows of a graph embedding, where the rotation is estimated using optimal transport. We show that our test statistic, appropriately scaled, is consistent for sufficiently dense graphs, and we study its convergence under different sparsity regimes. In addition, we provide empirical evidence suggesting that our novel alignment procedure can perform better than the naïve alignment in practice, where the naïve alignment assumes an eigengap.