A0832
Title: Matching and mixing: Matchability of graphs under Markovian error
Authors: Zhirui Li - University of Maryland College Park (United States) [presenting]
Keith Levin - University of Wisconsin (United States)
Zhiang Zhao - Xiangze International Holdings Inc (United States)
Vince Lyzinski - University of Maryland, College Park (United States)
Abstract: Theoretical results on the matchability of graphs are presented under dependent Markovian noise. The theories are built upon a lamplighter-like model, which, unlike most existing work in the graph-matching literature, does not assume the independence of noise on the edges. By comparing the Markovian mechanism of the lamplighter walk and the ability to de-anonymize (i.e., match) the noisy network, it is shown that under classical homogeneous Erdos-Renyi models, the anonymization time and the mixing time of the random walk are both of order $O(n^2\text{polylog}(n))$. It is further demonstrated that for more structured models (e.g., the stochastic block model), anonymization can occur in $O(n^\alpha\text{polylog}(n))$ time for $\alpha<2$, indicating that matching fails before the Markovian noise globally mixes. These established time bounds are demonstrated using both simulated graph models in the settings of Erdos-Renyi and SBM graphs, as well as real-world datasets such as the Facebook friendship network and the European research institution email communication network.
