mlsanityData to 14 Oct 2026

Matching and mixing: Matchability of graphs under Markovian error

arXiv 2601.20020 ↗First posted 27 Jan 2026math.ST math.PR stat.COcited by 0

Not on the map. Why?

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.

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

26 of 88 references.

References · 26

  1. 2017Community Detection and Stochastic Block Modelscited by 319
  2. 2017Statistical inference on random dot product graphs: a surveycited by 70
  3. 2019A Review of Stochastic Block Models and Extensions for Graph Clusteringcited by 46
  4. 2021Settling the Sharp Reconstruction Thresholds of Random Graph Matchingcited by 45
  5. 2018REGAL: Representation Learning-based Graph Alignmentcited by 40
  6. 2017Exact alignment recovery for correlated ErdHos-R'enyi graphscited by 38
  7. 2013Hierarchical Block Structures and High-resolution Model Selection in Large Networkscited by 37
  8. 2016Improved Achievability and Converse Bounds for ErdHos-R'enyi Graph Matchingcited by 30
  9. 2014Graph Matching: Relax at Your Own Riskcited by 27
  10. 2018Seeded Graph Matching via Large Neighborhood Statisticscited by 27
  11. 2020Testing correlation of unlabeled random graphscited by 26
  12. 2015Community Detection and Classification in Hierarchical Stochastic Blockmodelscited by 23
14 more
  1. 2014Hypothesis Testing For Network Data in Functional Neuroimagingcited by 20
  2. 2018Hierarchical community detection by recursive partitioningcited by 16
  3. 2019KerGM: Kernelized Graph Matchingcited by 13
  4. 2017Network classification with applications to brain connectomicscited by 12
  5. 2017Joint Embedding of Graphscited by 12
  6. 2016Information Recovery in Shuffled Graphs via Graph Matchingcited by 8
  7. 2019Recovering shared structure from multiple networks with unknown edge distributionscited by 8
  8. 2018Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networkscited by 6
  9. 2014Seeded Graph Matching Via Joint Optimization of Fidelity and Commensurabilitycited by 5
  10. 2021Hypothesis Testing for Equality of Latent Positions in Random Graphscited by 5
  11. 2016Linear Programming Heuristics for the Graph Isomorphism Problemcited by 3
  12. 2022Lost in the Shuffle: Testing Power in the Presence of Errorful Network Vertex Labelscited by 3
  13. 2017Planar Graph Perfect Matching is in NCcited by 1
  14. 2025Fastest Mixing Reversible Markov Chain: Clique Lifted Graphs and Subgraphscited by 1

Built on by

Not cited yet.