A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference

Abstract

Performing statistical analyses on collections of graphs is of import to many disciplines, but principled, scalable methods for multi-sample graph inference are few. Here we describe an "omnibus" embedding in which multiple graphs on the same vertex set are jointly embedded into a single space with a distinct representation for each graph. We prove a central limit theorem for this embedding and demonstrate how it streamlines graph comparison, obviating the need for pairwise subspace alignments. The omnibus embedding achieves near-optimal inference accuracy when graphs arise from a common distribution and yet retains discriminatory power as a test procedure for the comparison of different graphs. Moreover, this joint embedding and the accompanying central limit theorem are important for answering multiscale graph inference questions, such as the identification of specific subgraphs or vertices responsible for similarity or difference across networks. We illustrate this with a pair of analyses of connectome data derived from dMRI and fMRI scans of human subjects. In particular, we show that this embedding allows the identification of specific brain regions associated with population-level differences. Finally, we sketch how the omnibus embedding can be used to address pressing open problems, both theoretical and practical, in multisample graph inference.

References in corpus (2)

• Stochastic blockmodels and community structure in networks
• Graph limits and exchangeable random graphs

Cited by in corpus (20)

• Statistical inference on random dot product graphs: a survey
• Bootstrapping Networks with Latent Space Structure
• The multilayer random dot product graph
• Change point localization in dependent dynamic nonparametric random dot product graphs
• Link prediction in dynamic networks using random dot product graphs
• Spectral embedding for dynamic networks with stability guarantees
• Hierarchical Stochastic Block Model for Community Detection in Multiplex Networks
• Nonparametric two-sample hypothesis testing for low-rank random graphs of differing sizes
• The Phantom Alignment Strength Conjecture: Practical use of graph matching alignment strength to indicate a meaningful graph match
• On Two Distinct Sources of Nonidentifiability in Latent Position Random Graph Models
• The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks
• Bias-Variance Tradeoffs in Joint Spectral Embeddings
• Optimal Bayesian Estimation for Random Dot Product Graphs
• Consistent polynomial-time unseeded graph matching for Lipschitz graphons
• Tractable Graph Matching via Soft Seeding
• Community Detection in Weighted Multilayer Networks with Ambient Noise
• Latent Space Model for Higher-order Networks and Generalized Tensor Decomposition
• Limit theorems for out-of-sample extensions of the adjacency and Laplacian spectral embeddings
• Central Limit Theorems for Classical Multidimensional Scaling
• Workgroup Mapping: Visual Analysis of Collaboration Culture