The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks

Abstract

Spectral inference on multiple networks is a rapidly-developing subfield of graph statistics. Recent work has demonstrated that joint, or simultaneous, spectral embedding of multiple independent networks can deliver more accurate estimation than individual spectral decompositions of those same networks. Such inference procedures typically rely heavily on independence assumptions across the multiple network realizations, and even in this case, little attention has been paid to the induced network correlation in such joint embeddings. Here, we present a generalized omnibus embedding methodology and provide a detailed analysis of this embedding across both independent and correlated networks, the latter of which significantly extends the reach of such procedures. We describe how this omnibus embedding can itself induce correlation, leading us to distinguish between inherent correlation -- the correlation that arises naturally in multisample network data -- and induced correlation, which is an artifice of the joint embedding methodology. We show that the generalized omnibus embedding procedure is flexible and robust, and prove both consistency and a central limit theorem for the embedded points. We examine how induced and inherent correlation can impact inference for network time series data, and we provide network analogues of classical questions such as the effective sample size for more generally correlated data. Further, we show how an appropriately calibrated generalized omnibus embedding can detect changes in real biological networks that previous embedding procedures could not discern, confirming that the effect of inherent and induced correlation can be subtle and transformative, with import in theory and practice.

arXiv comment44 pages, 13 figures

References in corpus (25)

• Point-Set Registration: Coherent Point Drift
• Network robustness and fragility: Percolation on random graphs
• struc2vec: Learning Node Representations from Structural Identity
• Matrix estimation by Universal Singular Value Thresholding
• Modeling homophily and stochastic equivalence in symmetric relational data
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges
• Locality statistics for anomaly detection in time series of graphs
• On a 'Two Truths' Phenomenon in Spectral Graph Clustering
• Joint Embedding of Graphs
• A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference
• A nonparametric two-sample hypothesis testing problem for random dot product graphs
• Seeded Graph Matching Via Joint Optimization of Fidelity and Commensurability
• Large-scale estimation of random graph models with local dependence
• Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral
• The Multiple Random Dot Product Graph Model
• Network Representation Using Graph Root Distributions
• Two-sample Test of Community Memberships of Weighted Stochastic Block Models
• Consistency of Spectral Clustering on Hierarchical Stochastic Block Models
• Efficient Estimation for Random Dot Product Graphs via a One-step Procedure
• Unseeded low-rank graph matching by transform-based unsupervised point registration
• Bias-Variance Tradeoffs in Joint Spectral Embeddings
• Multiple Network Embedding for Anomaly Detection in Time Series of Graphs
• Consistent detection and optimal localization of all detectable change points in piecewise stationary arbitrarily sparse network-sequences
• Consistent polynomial-time unseeded graph matching for Lipschitz graphons