# Matching and mixing: Matchability of graphs under Markovian error

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 88 references that are in the map.
- First posted on arXiv 27 Jan 2026.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [A Review of Stochastic Block Models and Extensions for Graph Clustering](https://mlsanity.com/paper/1903.00114/) (2019)
- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [REGAL: Representation Learning-based Graph Alignment](https://mlsanity.com/paper/1802.06257/) (2018)
- [Exact alignment recovery for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1711.06783/) (2017)
- [Hierarchical Block Structures and High-resolution Model Selection in Large Networks](https://mlsanity.com/paper/1310.4377/) (2013)
- [Improved Achievability and Converse Bounds for ErdHos-R'enyi Graph Matching](https://mlsanity.com/paper/1602.01042/) (2016)
- [Graph Matching: Relax at Your Own Risk](https://mlsanity.com/paper/1405.3133/) (2014)
- [Seeded Graph Matching via Large Neighborhood Statistics](https://mlsanity.com/paper/1807.10262/) (2018)
- [Testing correlation of unlabeled random graphs](https://mlsanity.com/paper/2008.10097/) (2020)
- [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)
- [Hierarchical community detection by recursive partitioning](https://mlsanity.com/paper/1810.01509/) (2018)
- [KerGM: Kernelized Graph Matching](https://mlsanity.com/paper/1911.11120/) (2019)
- [Network classification with applications to brain connectomics](https://mlsanity.com/paper/1701.08140/) (2017)
- [Joint Embedding of Graphs](https://mlsanity.com/paper/1703.03862/) (2017)
- [Information Recovery in Shuffled Graphs via Graph Matching](https://mlsanity.com/paper/1605.02315/) (2016)
- [Recovering shared structure from multiple networks with unknown edge distributions](https://mlsanity.com/paper/1906.07265/) (2019)
- [Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks](https://mlsanity.com/paper/1812.10519/) (2018)
- [Seeded Graph Matching Via Joint Optimization of Fidelity and Commensurability](https://mlsanity.com/paper/1401.3813/) (2014)
- [Hypothesis Testing for Equality of Latent Positions in Random Graphs](https://mlsanity.com/paper/2105.10838/) (2021)
- [Linear Programming Heuristics for the Graph Isomorphism Problem](https://mlsanity.com/paper/1611.00711/) (2016)
- [Lost in the Shuffle: Testing Power in the Presence of Errorful Network Vertex Labels](https://mlsanity.com/paper/2208.08638/) (2022)
- [Planar Graph Perfect Matching is in NC](https://mlsanity.com/paper/1709.07822/) (2017)
- [Fastest Mixing Reversible Markov Chain: Clique Lifted Graphs and Subgraphs](https://mlsanity.com/paper/2501.02421/) (2025)

## Abstract (arXiv)

We consider the problem of graph matching for a sequence of graphs generated under a time-dependent Markov chain noise model. Our edgelighter error model, a variant of the classical lamplighter random walk, iteratively corrupts the graph G0 with edge-dependent noise, creating a sequence of noisy graph copies (Gt). Much of the graph matching literature is focused on anonymization thresholds in edge-independent noise settings, and we establish novel anonymization thresholds in this edge-dependent noise setting when matching G0 and Gt. Moreover, we also compare this anonymization threshold with the mixing properties of the Markov chain noise model. We show that when G0 is drawn from an ErdHos-R'enyi model, the graph matching anonymization threshold and the mixing time of the edgelighter walk are both of order Theta(n2log n). We further demonstrate that for more structured model for G0 (e.g., the Stochastic Block Model), graph matching anonymization can occur in O(nαlog n) time for some α<2, indicating that anonymization can occur before the Markov chain noise model globally mixes. Through extensive simulations, we verify our theoretical bounds in the settings of ErdHos-R'enyi random graphs and stochastic block model random graphs, and explore our findings on real-world datasets derived from a Facebook friendship network and a European research institution email communication network.