# Lost in the Shuffle: Testing Power in the Presence of Errorful Network Vertex Labels

arXiv: https://arxiv.org/abs/2208.08638 · HTML: https://mlsanity.com/paper/2208.08638/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 85 references that are in the map.
- First posted on arXiv 18 Aug 2022.

## Builds on (most cited first, 30 of 30)

- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys](https://mlsanity.com/paper/1506.03645/) (2015)
- [A statistical interpretation of spectral embedding: the generalised random dot product graph](https://mlsanity.com/paper/1709.05506/) (2017)
- [REGAL: Representation Learning-based Graph Alignment](https://mlsanity.com/paper/1802.06257/) (2018)
- [Inference for multiple heterogeneous networks with a common invariant subspace](https://mlsanity.com/paper/1906.10026/) (2019)
- [Seeded Graph Matching via Large Neighborhood Statistics](https://mlsanity.com/paper/1807.10262/) (2018)
- [Network cross-validation by edge sampling](https://mlsanity.com/paper/1612.04717/) (2016)
- [Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embedding](https://mlsanity.com/paper/1310.0532/) (2013)
- [Community Detection and Classification in Hierarchical Stochastic Blockmodels](https://mlsanity.com/paper/1503.02115/) (2015)
- [Hypothesis Testing For Network Data in Functional Neuroimaging](https://mlsanity.com/paper/1407.5525/) (2014)
- [A goodness-of-fit test for stochastic block models](https://mlsanity.com/paper/1412.4857/) (2014)
- [Hierarchical community detection by recursive partitioning](https://mlsanity.com/paper/1810.01509/) (2018)
- [Bootstrapping Networks with Latent Space Structure](https://mlsanity.com/paper/1907.10821/) (2019)
- [Nonparametric Bayes Modeling of Populations of Networks](https://mlsanity.com/paper/1406.7851/) (2014)
- [Spectral embedding of weighted graphs](https://mlsanity.com/paper/1910.05534/) (2019)
- [Spectral clustering on spherical coordinates under the degree-corrected stochastic blockmodel](https://mlsanity.com/paper/2011.04558/) (2020)
- [Vertex nomination schemes for membership prediction](https://mlsanity.com/paper/1312.2638/) (2013)
- [Information Recovery in Shuffled Graphs via Graph Matching](https://mlsanity.com/paper/1605.02315/) (2016)
- [Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching](https://mlsanity.com/paper/1311.6425/) (2013)
- [Bayesian Inference and Testing of Group Differences in Brain Networks](https://mlsanity.com/paper/1411.6506/) (2014)
- [Vertex nomination: The canonical sampling and the extended spectral nomination schemes](https://mlsanity.com/paper/1802.04960/) (2018)
- [Multiple Network Embedding for Anomaly Detection in Time Series of Graphs](https://mlsanity.com/paper/2008.10055/) (2020)
- [Vertex Nomination Via Seeded Graph Matching](https://mlsanity.com/paper/1705.00674/) (2017)
- [The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks](https://mlsanity.com/paper/2008.00163/) (2020)
- [Hypothesis Testing for Equality of Latent Positions in Random Graphs](https://mlsanity.com/paper/2105.10838/) (2021)
- [Hypothesis testing for populations of networks](https://mlsanity.com/paper/1911.03783/) (2019)
- [The Phantom Alignment Strength Conjecture: Practical use of graph matching alignment strength to indicate a meaningful graph match](https://mlsanity.com/paper/2103.00624/) (2021)
- [A central limit theorem for scaled eigenvectors of random dot product graphs](https://mlsanity.com/paper/1305.7388/) (2013)
- [Computing Scalable Multivariate Glocal Invariants of Large (Brain-) Graphs](https://mlsanity.com/paper/1312.4318/) (2013)

## Built on by (most cited first, 3 of 3)

- [Detection of Model-based Planted Pseudo-cliques in Random Dot Product Graphs by the Adjacency Spectral Embedding and the Graph Encoder Embedding](https://mlsanity.com/paper/2312.11054/) (2023)
- [Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)](https://mlsanity.com/paper/2506.02825/) (2025)
- [Matching and mixing: Matchability of graphs under Markovian error](https://mlsanity.com/paper/2601.20020/) (2026)

## Abstract (arXiv)

Two-sample network hypothesis testing is an important inference task with applications across diverse fields such as medicine, neuroscience, and sociology. Many of these testing methodologies operate under the implicit assumption that the vertex correspondence across networks is a priori known. This assumption is often untrue, and the power of the subsequent test can degrade when there are misaligned/label-shuffled vertices across networks. This power loss due to shuffling is theoretically explored in the context of random dot product and stochastic block model networks for a pair of hypothesis tests based on Frobenius norm differences between estimated edge probability matrices or between adjacency matrices. The loss in testing power is further reinforced by numerous simulations and experiments, both in the stochastic block model and in the random dot product graph model, where the power loss across multiple recently proposed tests in the literature is considered. Lastly, the impact that shuffling can have in real-data testing is demonstrated in a pair of examples from neuroscience and from social network analysis.