# Covariate-assisted graph matching

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 81 references that are in the map.
- First posted on arXiv 12 Dec 2025.

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

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [ranger: A Fast Implementation of Random Forests for High Dimensional Data in C++ and R](https://mlsanity.com/paper/1508.04409/) (2015)
- [Multilayer Networks](https://mlsanity.com/paper/1309.7233/) (2013)
- [Efficient random graph matching via degree profiles](https://mlsanity.com/paper/1811.07821/) (2018)
- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [Community Detection in Networks with Node Attributes](https://mlsanity.com/paper/1401.7267/) (2014)
- [Exact alignment recovery for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1711.06783/) (2017)
- [Structure and inference in annotated networks](https://mlsanity.com/paper/1507.04001/) (2015)
- [Improved Achievability and Converse Bounds for ErdHos-R'enyi Graph Matching](https://mlsanity.com/paper/1602.01042/) (2016)
- [Covariate-assisted spectral clustering](https://mlsanity.com/paper/1411.2158/) (2014)
- [Graph Matching: Relax at Your Own Risk](https://mlsanity.com/paper/1405.3133/) (2014)
- [Seeded Graph Matching via Large Neighborhood Statistics](https://mlsanity.com/paper/1807.10262/) (2018)
- [Random graph matching at Otter's threshold via counting chandeliers](https://mlsanity.com/paper/2209.12313/) (2022)
- [Seeded graph matching for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1304.7844/) (2013)
- [Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model](https://mlsanity.com/paper/1907.08880/) (2019)
- [Optimal De-Anonymization in Random Graphs with Community Structure](https://mlsanity.com/paper/1602.01409/) (2016)
- [Information Recovery in Shuffled Graphs via Graph Matching](https://mlsanity.com/paper/1605.02315/) (2016)
- [Pairwise Covariates-adjusted Block Model for Community Detection](https://mlsanity.com/paper/1807.03469/) (2018)
- [Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks](https://mlsanity.com/paper/1812.10519/) (2018)
- [Testing and Modeling Dependencies Between a Network and Nodal Attributes](https://mlsanity.com/paper/1306.4708/) (2013)
- [Deep Adversarial Network Alignment](https://mlsanity.com/paper/1902.10307/) (2019)
- [Graph matching between bipartite and unipartite networks: to collapse, or not to collapse, that is the question](https://mlsanity.com/paper/2002.01648/) (2020)
- [Generalized linear models with low rank effects for network data](https://mlsanity.com/paper/1705.06772/) (2017)
- [A Spike-and-Slab Prior for Dimension Selection in Generalized Linear Network Eigenmodels](https://mlsanity.com/paper/2309.11654/) (2023)
- [Learning Joint and Individual Structure in Network Data with Covariates](https://mlsanity.com/paper/2406.08776/) (2024)
- [Matching Community Structure Across Online Social Networks](https://mlsanity.com/paper/1608.01373/) (2016)
- [Testing for Association in Multi-View Network Data](https://mlsanity.com/paper/1909.11640/) (2019)
- [Vertex Nomination in Richly Attributed Networks](https://mlsanity.com/paper/2005.02151/) (2020)
- [Inference for Network Regression Models with Community Structure](https://mlsanity.com/paper/2106.04271/) (2021)
- [Statistical Network Analysis: Past, Present, and Future](https://mlsanity.com/paper/2311.00122/) (2023)

## Abstract (arXiv)

Data integration is essential across diverse domains, from historical records to biomedical research, facilitating joint statistical inference. A crucial initial step in this process involves merging multiple data sources based on matching individual records, often in the absence of unique identifiers. When the datasets are networks, this problem is typically addressed through graph matching methodologies. For such cases, auxiliary features or covariates associated with nodes or edges can be instrumental in achieving improved accuracy. However, most existing graph matching techniques do not incorporate this information, limiting their performance against non-identifiable and erroneous matches. To overcome these limitations, we propose two novel covariate-assisted seeded graph matching methods, where a partial alignment for a set of nodes, called seeds, is known. The first one solves a quadratic assignment problem (QAP) over the whole graph, while the second one only leverages the local neighborhood structure of seed nodes for computational scalability. Both methods are grounded in a conditional modeling framework, where elements of one graph's adjacency matrix are modeled using a generalized linear model (GLM), given the other graph and the available covariates. We establish theoretical guarantees for model estimation error and exact recovery of the solution of the QAP. The effectiveness of our methods is demonstrated through numerical experiments and in an application to matching the statistics academic genealogy and the collaboration networks. By leveraging additional covariates, we achieve improved alignment accuracy. Our work highlights the power of integrating covariate information in the classical graph matching setup, offering a practical and improved framework for combining network data with wide-ranging applications.