Nonparametric two-sample hypothesis testing for low-rank random graphs of differing sizes

Abstract

Given two networks of differing sizes, it is of interest to test whether the two networks belong to the same distribution. We formalize the notion of "equality of distribution" under the framework of the generalized random dot product graph, which considers as special cases a number of popular network models with low-rank expectations. We then propose a nonparametric two-sample test statistic to conduct this test, assuming only that the networks have independent edges generated from low-rank probability matrices. 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, and our results are demonstrated in numerical simulations.

References in corpus (19)

• Modularity and community structure in networks
• A new graph-based two-sample test for multivariate and object data
• Convergence and Concentration of Empirical Measures under Wasserstein Distance in Unbounded Functional Spaces
• On a 'Two Truths' Phenomenon in Spectral Graph Clustering
• Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances
• Towards Optimal Transport with Global Invariances
• A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference
• Two-Sample Tests for Large Random Graphs Using Network Statistics
• Bootstrapping Networks with Latent Space Structure
• The multilayer random dot product graph
• Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral
• Two-sample Test of Community Memberships of Weighted Stochastic Block Models
• Unseeded low-rank graph matching by transform-based unsupervised point registration
• On Two Distinct Sources of Nonidentifiability in Latent Position Random Graph Models
• On the Theoretical Properties of the Network Jackknife
• Bias-Variance Tradeoffs in Joint Spectral Embeddings
• Persistent Homology of Graph Embeddings
• Manifold structure in graph embeddings
• Numerical tolerance for spectral decompositions of random matrices

Cited by in corpus (3)

• Entrywise Estimation of Singular Vectors of Low-Rank Matrices with Heteroskedasticity and Dependence
• Graphon based Clustering and Testing of Networks: Algorithms and Theory
• Valid Two-Sample Graph Testing via Optimal Transport Procrustes and Multiscale Graph Correlation with Applications in Connectomics