# Attributed Network Alignment: Statistical Limits and Efficient Algorithm

arXiv: https://arxiv.org/abs/2604.04365 · HTML: https://mlsanity.com/paper/2604.04365/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 94 references that are in the map.
- First posted on arXiv 6 Apr 2026.

## Builds on (most cited first, 8 of 8)

- [Exact alignment recovery for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1711.06783/) (2017)
- [A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation](https://mlsanity.com/paper/2306.00266/) (2023)
- [The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime](https://mlsanity.com/paper/2402.15095/) (2024)
- [Aligning Multiple Inhomogeneous Random Graphs: Fundamental Limits of Exact Recovery](https://mlsanity.com/paper/2405.12293/) (2024)
- [Gaussian Database Alignment and Gaussian Planted Matching](https://mlsanity.com/paper/2307.02459/) (2023)
- [Consistent polynomial-time unseeded graph matching for Lipschitz graphons](https://mlsanity.com/paper/1807.11027/) (2018)
- [Independence testing for inhomogeneous random graphs](https://mlsanity.com/paper/2304.09132/) (2023)
- [Information-Theoretic Thresholds for Planted Dense Cycles](https://mlsanity.com/paper/2402.00305/) (2024)

## Built on by (most cited first, 1 of 1)

- [Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Tests](https://mlsanity.com/paper/2607.09087/) (2026)

## Abstract (arXiv)

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 algorithm 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.