# Information Recovery in Shuffled Graphs via Graph Matching

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 May 2016.

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

- [Exact Community Recovery in Correlated Stochastic Block Models](https://mlsanity.com/paper/2203.15736/) (2022)
- [Lost in the Shuffle: Testing Power in the Presence of Errorful Network Vertex Labels](https://mlsanity.com/paper/2208.08638/) (2022)
- [Clustered Graph Matching for Label Recovery and Graph Classification](https://mlsanity.com/paper/2205.03486/) (2022)
- [Gotta match 'em all: Solution diversification in graph matching matched filters](https://mlsanity.com/paper/2308.13451/) (2023)
- [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)
- [Covariate-assisted graph matching](https://mlsanity.com/paper/2512.11761/) (2025)
- [Matching and mixing: Matchability of graphs under Markovian error](https://mlsanity.com/paper/2601.20020/) (2026)

## Abstract (arXiv)

While many multiple graph inference methodologies operate under the implicit assumption that an explicit vertex correspondence is known across the vertex sets of the graphs, in practice these correspondences may only be partially or errorfully known. Herein, we provide an information theoretic foundation for understanding the practical impact that errorfully observed vertex correspondences can have on subsequent inference, and the capacity of graph matching methods to recover the lost vertex alignment and inferential performance. Working in the correlated stochastic blockmodel setting, we establish a duality between the loss of mutual information due to an errorfully observed vertex correspondence and the ability of graph matching algorithms to recover the true correspondence across graphs. In the process, we establish a phase transition for graph matchability in terms of the correlation across graphs, and we conjecture the analogous phase transition for the relative information loss due to shuffling vertex labels. We demonstrate the practical effect that graph shuffling---and matching---can have on subsequent inference, with examples from two sample graph hypothesis testing and joint spectral graph clustering.