Matching and mixing: Matchability of graphs under Markovian error

• URL: http://arxiv.org/abs/2601.20020v1
• Date: Tue, 27 Jan 2026 19:53:56 GMT
• Title: Matching and mixing: Matchability of graphs under Markovian error
• Authors: Zhirui Li, Keith D. Levin, Zhiang Zhao, Vince Lyzinski,
• Abstract summary: We show that anonymization can occur before the Markov chain noise model globally mixes.<n>We explore our findings on real-world datasets derived from a Facebook friendship network and a European research institution email communication network.
• Score: 1.2559534897613556
• License: http://creativecommons.org/licenses/by/4.0/
• 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$ with edge-dependent noise, creating a sequence of noisy graph copies $(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$ and $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$ 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)$. We further demonstrate that for more structured model for $G_0$ (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 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.

Related papers

• DREAM: Dual-Standard Semantic Homogeneity with Dynamic Optimization for Graph Learning with Label Noise [53.55187452152358]
  This paper proposes a novel method, Dual-Standard Semantic Homogeneity with Dynamic Optimization (DREAM) for reliable, relation-informed optimization on graphs with label noise.<n>Specifically, we design a relation-informed dynamic optimization framework that iteratively reevaluates the reliability of each labeled node in the graph.
  arXiv  Detail & Related papers  (2026-01-24T12:54:18Z)
• Sparse Training of Discrete Diffusion Models for Graph Generation [45.103518022696996]
  We introduce SparseDiff, a novel diffusion model based on the observation that almost all large graphs are sparse. By selecting a subset of edges, SparseDiff effectively leverages sparse graph representations both during the noising process and within the denoising network. Our model demonstrates state-of-the-art performance across multiple metrics on both small and large datasets.
  arXiv  Detail & Related papers  (2023-11-03T16:50:26Z)
• Graph Mixup with Soft Alignments [49.61520432554505]
  We study graph data augmentation by mixup, which has been used successfully on images. We propose S-Mixup, a simple yet effective mixup method for graph classification by soft alignments.
  arXiv  Detail & Related papers  (2023-06-11T22:04:28Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
  We consider the problem of modelling high-dimensional distributions and generating new examples of data with complex relational feature structure coherent with a graph skeleton. The model we propose tackles the problem of generating the data features constrained by the specific graph structure of each data point by splitting the task into two phases. In the first it models the distribution of features associated with the nodes of the given graph, in the second it complements the edge features conditionally on the node features.
  arXiv  Detail & Related papers  (2022-12-01T11:49:07Z)
• DiGress: Discrete Denoising diffusion for graph generation [79.13904438217592]
  DiGress is a discrete denoising diffusion model for generating graphs with categorical node and edge attributes. It achieves state-of-the-art performance on molecular and non-molecular datasets, with up to 3x validity improvement. It is also the first model to scale to the large GuacaMol dataset containing 1.3M drug-like molecules.
  arXiv  Detail & Related papers  (2022-09-29T12:55:03Z)
• Node Copying: A Random Graph Model for Effective Graph Sampling [35.957719744856696]
  We introduce the node copying model for constructing a distribution over graphs. We show the usefulness of the copying model in three tasks. We employ our proposed model to mitigate the effect of adversarial attacks on the graph topology.
  arXiv  Detail & Related papers  (2022-08-04T04:04:49Z)
• Causal Inference Despite Limited Global Confounding via Mixture Models [4.721845865189578]
  A finite $k$-mixture of such models is graphically represented by a larger graph. We give the first algorithm to learn mixtures of non-empty DAGs.
  arXiv  Detail & Related papers  (2021-12-22T01:04:50Z)
• Neighborhood Random Walk Graph Sampling for Regularized Bayesian Graph Convolutional Neural Networks [0.6236890292833384]
  In this paper, we propose a novel algorithm called Bayesian Graph Convolutional Network using Neighborhood Random Walk Sampling (BGCN-NRWS) BGCN-NRWS uses a Markov Chain Monte Carlo (MCMC) based graph sampling algorithm utilizing graph structure, reduces overfitting by using a variational inference layer, and yields consistently competitive classification results compared to the state-of-the-art in semi-supervised node classification.
  arXiv  Detail & Related papers  (2021-12-14T20:58:27Z)
• Label-Wise Message Passing Graph Neural Network on Heterophilic Graphs [20.470934944907608]
  We investigate a novel framework that performs well on graphs with either homophily or heterophily. In label-wise message-passing, neighbors with similar pseudo labels will be aggregated together. We also propose a bi-level optimization method to automatically select the model for graphs with homophily/heterophily.
  arXiv  Detail & Related papers  (2021-10-15T14:49:45Z)
• Order Matters: Probabilistic Modeling of Node Sequence for Graph Generation [18.03898476141173]
  A graph generative model defines a distribution over graphs. We derive the exact joint probability over the graph and the node ordering of the sequential process. We train graph generative models by maximizing this bound, without using the ad-hoc node orderings of previous methods.
  arXiv  Detail & Related papers  (2021-06-11T06:37:52Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  A learning agent repeatedly chooses from a set of $K$ actions after being presented with a $d$-dimensional context vector. The agent incurs and observes the loss of the chosen action, but also observes the losses of its neighboring actions in the observation structures. Two efficient algorithms are developed based on textttEXP3.
  arXiv  Detail & Related papers  (2020-12-10T15:40:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.