Covariate-assisted graph matching

Data integration often requires aligning datasets without unique identifiers; for network data this is commonly addressed through graph matching. Despite the widespread availability of node and edge covariates in many applications, most existing methods rely solely on the structural similarity between the two graphs, limiting their flexibility and robustness to non-identifiable matches and structural noise. In this article, we study the seeded graph matching problem, where a partial alignment for a set of nodes (seeds) is known, in the presence of informative node and edge covariates. We propose two covariate-assisted methods: a global approach based on a quadratic assignment problem (QAP), and a scalable local approach that leverages the neighborhood of the seeds. Both methods are based on a flexible conditional modeling framework that enables covariate integration using predictive models ranging from generalized linear models to machine learning methods. We provide estimation error rates for the generalized linear model, and sufficient conditions for exact recovery of the true correspondences via the QAP. We further specialize these results to Erdős-Rényi model with covariates. The effectiveness in achieving improved performance by leveraging additional covariates is demonstrated through simulations and in an application to matching the statistics academic genealogy and the collaboration networks.