Graph alignment in sparse inhomogeneous models via self-overlap
arXiv:2607.14948
The paper introduces a framework to determine when graph alignment can be successfully performed in sparse, heterogeneous random graphs, using a new measure called self-overlap to establish sharp feasibility thresholds.
Abstract
We develop a general framework for understanding when graph alignment is information-theoretically feasible in sparse inhomogeneous random graph models, by studying the set of vertices on which the underlying matching can be recovered. Our main theorem gives a general lower bound on this set by leveraging the balanced load function introduced by Hajek (1990). The corresponding obstruction is captured by a new graph parameter, the self-overlap, which measures the extent to which a graph can imitate itself under a non-trivial relabelling. We then show that this criterion is sharp in a broad class of sparse inhomogeneous models, recovering known ErdÅs--Rényi phenomena and yielding sharp thresholds for Chung--Lu graphs and stochastic block models.
31 pages, 1 figure