Bias-Variance Tradeoffs in Joint Spectral Embeddings

Abstract

Joint spectral embeddings facilitate analysis of multiple network data by simultaneously mapping vertices in each network to points in Euclidean space where statistical inference is then performed. In this work, we consider one such joint embedding technique, the omnibus embedding of arXiv:1705.09355 , which has been successfully used for community detection, anomaly detection, and hypothesis testing tasks. To date the theoretical properties of this method have only been established under the strong assumption that the networks are conditionally i.i.d. random dot product graphs. Herein, we take a first step in characterizing the theoretical properties of the omnibus embedding in the presence of heterogeneous network data. Under a latent position model, we show the omnibus embedding implicitly regularizes its latent position estimates which induces a finite-sample bias-variance tradeoff for latent position estimation. We establish an explicit bias expression, derive a uniform concentration bound on the residual, and prove a central limit theorem characterizing the distributional properties of these estimates. These explicit bias and variance expressions enable us to state sufficient conditions for exact recovery in community detection tasks and develop a pivotal test statistic to determine whether two graphs share the same set of latent positions; demonstrating that accurate inference is achievable despite the estimator's inconsistency. These results are demonstrated in several experimental settings where statistical procedures utilizing the omnibus embedding are competitive, and oftentimes preferable, to comparable embedding techniques. These observations accentuate the viability of the omnibus embedding for multiple graph inference beyond the homogeneous network setting.

arXiv comment45 pages, 7 figures

References in corpus (21)

• The complex network of global cargo ship movements
• Structural measures for multiplex networks
• Emergence of network features from multiplexity
• Statistical Mechanics of Multiplex Ensembles: Entropy and Overlap
• Measuring and modelling correlations in multiplex networks
• Multilayer motif analysis of brain networks
• The new challenges of multiplex networks: measures and models
• How women organize social networks different from men
• Structure of Triadic Relations in Multiplex Networks
• Multiplex lexical networks reveal patterns in early word acquisition in children
• Statistical inference on random dot product graphs: a survey
• Node and layer eigenvector centralities for multiplex networks
• Angles between subspaces and their tangents
• Multilayer weighted social network model
• Inference for multiple heterogeneous networks with a common invariant subspace
• A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference
• A random effects stochastic block model for joint community detection in multiple networks with applications to neuroimaging
• The Multiple Random Dot Product Graph Model
• "You Know Because I Know": a Multidimensional Network Approach to Human Resources Problem
• Hierarchical Stochastic Block Model for Community Detection in Multiplex Networks
• A simple multiforce layout for multiplex networks

Cited by in corpus (3)

• Nonparametric two-sample hypothesis testing for low-rank random graphs of differing sizes
• Multiple Network Embedding for Anomaly Detection in Time Series of Graphs
• The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks