Attributed Network Alignment: Statistical Limits and Efficient Algorithm

This paper studies the problem of recovering a hidden vertex correspondence between two correlated graphs when both edge weights and node features are observed. While most existing work on graph alignment relies primarily on edge information, many real-world applications provide informative node features in addition to graph topology. To capture this setting, we introduce the featured correlated Gaussian Wigner model, where two graphs are coupled through an unknown vertex permutation, and the node features are correlated under the same permutation. We characterize the optimal information-theoretic thresholds for exact recovery and partial recovery of the latent mapping. On the algorithmic side, we propose QPAlign, an efficient method based on a quadratic programming relaxation, and demonstrate its strong empirical performance on both synthetic and real datasets. Moreover, we also derive theoretical guarantees for the proposed procedure, supporting its reliability and providing convergence guarantees.

Graph alignment aims to match corresponding entities across two networks, such as papers in bibliographic databases, users on social platforms, or genes in biological networks. In real applications, networks often provide both connection patterns and node-level information, such as names, profiles, or annotations. This paper studies how these two sources of information can be combined for reliable alignment. We show that network structure and node features can complement each other: even when either source alone is insufficient, using them together may make accurate matching possible. We also propose an efficient algorithm, QPAlign, and experiments on synthetic and real datasets show that it effectively balances these two types of information.