Matching and mixing: Matchability of graphs under Markovian error

Zhirui Li, Keith D. Levin, Zhiang Zhao, Vince Lyzinski · 2026

Read Matching and mixing: Matchability of graphs under Markovian error by Zhirui Li, Keith D. Levin, Zhiang Zhao, Vince Lyzinski (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-20020.txt.

Introduction

Zhirui Li, Keith D. Levin, Zhiang Zhao, and Vince Lyzinski study matching graphs that change over time. Graph matching pairs up the nodes of two graphs that describe the same objects. Noise corrupts real graphs, so matches must survive errors. The authors consider a sequence of graphs produced by a time-dependent Markov chain noise process.

Their edgelighter model corrupts a base graph step by step, flipping edges with edge-dependent rules. It is a variant of the classical lamplighter random walk. The question is matchability: when can the true pairing still be recovered from the noisy copies? Network de-anonymisation and image alignment both hinge on such guarantees. The work gives the time-varying case a proper theory.

Catalog record

CREATORZhirui Li, Keith D. Levin, Zhiang Zhao, Vince Lyzinski
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE97 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-20020

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Matching and mixing: Matchability of graphs under Markovian error Zhirui Li, Keith D. Levin, Zhiang Zhao, Vince Lyzinski Abstract 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 G 0 G_{0} with edge-dependent noise, creating a sequence of noisy graph copies ( G t ) (G_{t}) . 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 G 0 G_{0} and G t G_{t} . Moreover, we also compare this anonymization threshold with the mixing properties of the Markov chain noise model. We show that when G 0 G_{0} is drawn from an Erdős–Rényi model, the graph matching anonymization threshold and the mixing time of the edgelighter walk are both of order Θ ⁡ ( n 2 ​ log ⁡ n ) \Theta(n^{2}\log n) . We further demonstrate that for more structured model for G 0 G_{0} (e.g., the Stochastic Block Model), graph matching anonymization can occur in O ⁡ ( n α ​ log ⁡ n ) O(n^{\alpha}\log n) time for some α < 2 \alpha<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 Erdős–Rényi 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. 1 Introduction Networks are used across the sciences to describe complex real-world relationships. Examples include studies of social networks, where nodes represent users and edges denote friendships or follower-following relations 53 . Co-authorship networks 30 and email exchange networks 41 have proven to be helpful in identifying leading research scientists, prominent organizations, and potential academic fraud. In neuroscience, networks derived from functional MRI scans 82 ; 69 have seen applications in analyzing connectivity patterns 28 ; 54 , and studying brain-related diseases 81 ; 77 . Large knowledge graphs have become increasingly useful for representing the conceptual relations between entities 91 . Statistical network inference on collections of graphs often assumes that the observed graphs are noisy copies generated from some shared latent structures 83 ; 44 ; 60 ; 6 ; 45 . From these observations, numerous tasks such as classification, hypothesis testing, and more can be pursued 78 ; 62 ; 74 ; 23 ; 33 ; 16 ; 75 ; 22 . A crucial assumption of most of these methods is that the vertices are a priori aligned across networks before inference is pursued. In situations where this is not the case, inference can degrade when vertex labels are shuffled or noisily observed 65 . In these cases, graph matching methods are often deployed to attempt to recover the true node labeling across graphs and enable the application of subsequent inference methods 39 ; 86 ; 4 ; 32 ; 6 . Stated simply, the goal of graph matching is to find the best possible alignment between the vertices of two (or more) graphs in order to minimize a measure of edgewise structural discrepancy. For detailed discussions on the graph matching problem, including its applications, approximation methods, extensions, and variants, refer to the surveys 63 ; 87 ; 19 . Recently, there have been numerous papers in the literature dedicated to algorithmic graph matching 79 ; 90 ; 34 ; 76 ; 27 ; 89 and the information theoretic limits of matching theory 88 ; 49 ; 20 ; 21 ; 85 . Nearly all of the aforementioned theoretical graph matching developments rely on the assumption of independent edge-level noise. However, in real applications such as protein-protein interaction networks 71 , epidemiological networks 57 , error propagation in neural networks 46 , and temporal networks 8 , it is more realistic to consider time- or node-dependent noise. To address this issue, our focus in the present work concerns the matchability of graphs with spatially- or temporally-dependent edge-noise processes. 1.1 Notation For any n\in\mathbb{Z}^{+} , we write [n]=\{1,2,\dots,n\} . For x\in\mathbb{R} , we write \lfloor x\rfloor for the floor function of x , i.e., the element n\in\mathbb{Z} such that n\leq x and n+1>x and denote the ceiling function analogously by \lceil\cdot\rceil . For a set S , we write \binom{S}{j} to denote the collection of all size- j subsets of S ; we also write \{0,1\}^{\binom{S}{j}} to denote the set of length |\binom{S}{j}| binary sequences indexed by \binom{S}{j} . We use \|\cdot\|_{F} to denote the matrix Frobenius norm. We use the standard notations for asymptotics. In particular, for two functions f,g:\mathbb{Z}^{+}\rightarrow\mathbb{R}^{+} , we write f(n)=o(g(n)) or f\ll g , if \lim_{n\rightarrow\infty}f(n)/g(n)=0 ; we write f(n)=\omega(g(n)) or f\gg g if g(n)=o(f(n)) ; we write f(n)=O(g(n)) or f\lesssim g if \exists C>0 and n_{0} such that \forall n\geq n_{0} , f(n)\leq Cg(n) ; we write f(n)=\Omega(g(n)) or f\gtrsim g if g(n)=O(f(n)) ; we write f(n)=\Theta(g(n)) if f(n)=O(g(n)) and g(n)=O(f(n)) . 1.2 The Graph Matching Problem The formulation of the graph matching problem we consider herein is defined as follows. Definition 1 . Consider two graphs G_{1}=(V_{1},E_{1}) and G_{2}=(V_{2},E_{2}) with corresponding adjacency matrices A and B , respectively. When |V_{1}|=|V_{2}|=n , the Graph Matching Problem (GMP) seeks to find \argmin_{P\in\Pi_{n}}\|A-PBP^{T}\|_{F}=\argmax_{P\in\Pi_{n}}\operatorname{Tr}\!\left(APBP^{T}\right), (1) where \Pi_{n} denotes the set of all n -by- n permutation matrices. The goal of the GMP is to find the best possible alignment of the vertices (as encoded by a permutation of the vertex labels) between the two graphs, so as to minimize a measure (here the \ell_{2} norm of binary edge-difference vectors) of the edgewise structural differences. In the general setting where the two graphs are allowed to be weighted, directed and to exhibit self-loops, the above formulation is equivalent to the NP-hard quadratic assignment problem 51 ; 80 . That said, there are efficient graph matching algorithms for special classes of graphs (e.g., planar graphs) 66 ; 5 . When discussing the GMP in what follows, we will refer to a graph and its adjacency matrix interchangeably, due to the one-to-one correspondence between weighted graphs and square matrices. The GMP has a long and rich history. Initial research focused on finding graph isomorphisms, solutions for which the objective function in Equation ( 1 ) equals zero 9 ; 61 ; 73 . The stringent nature of exact matching, however, limits the applicability of the graph isomorphism problem in real-world scenarios where noise or distortion of graph structures might be present. In response, more general formulations of the graph matching problem aim not to drive the objective to zero, but rather to minimize it, allowing for the possibility that two graphs, while not precisely isomorphic, may still exhibit meaningful structural similarity; see 19 for more extensive background. In the graph isomorphism setting, there is a notion of a true alignment (i.e., the isomorphism) that is not necessarily present in the general GMP. To remedy this, we consider the pair of networks G_{1} and G_{2} as having a true, latent (i.e., a priori unknown) node-level alignment across their vertex sets. This

Read the complete text