Graph alignment in sparse inhomogeneous models via self-overlap

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.

Disclosure

“t (I(π (up to oP (n) vertices). and, by (120), (125) V≥t (I(π b)) = B (up to oP (n) vertices). This concludes the proof. Acknowledgments. The author used large language model tools for brainstorming, drafting, generating figures, and proofreading. The author takes full responsibility for all mathematical content and any errors. The author would like to thank Laurent Massoulié for his helpful comments on earl”

PDF page 30

Classification

Drafting limited passages

Multiplier

5

Verified

2026-08-23T18:55:09.141404Z

Structural counts