article · arXiv (Cornell University) · 2026
Contextual Graph Matching with Correlated Gaussian Features
Mohammad Hassan Ahmad Yarandi, Luca Ganassali
Cited by 0Open access
Abstract
We investigate contextual graph matching in the Gaussian setting, where both edge weights and node features are correlated across two networks. We derive precise information-theoretic thresholds for exact recovery, and identify conditions under which almost exact recovery is possible or impossible, in terms of graph and feature correlation strengths, the number of nodes, and feature dimension. Interestingly, whereas an all-or-nothing phase transition is observed in the standard graph-matching scenario, the additional contextual information introduces a richer structure: thresholds for exact and almost exact recovery no longer coincide. Our results provide the first rigorous characterization of how structural and contextual information interact in graph matching, and establish a benchmark for designing efficient algorithms.
Cite this paper
Yarandi, M. H. A., & Ganassali, L. (2026). Contextual Graph Matching with Correlated Gaussian Features. arXiv (Cornell University).
Yarandi, Mohammad Hassan Ahmad, and Luca Ganassali. “Contextual Graph Matching with Correlated Gaussian Features.” arXiv (Cornell University), 2026.
Yarandi, Mohammad Hassan Ahmad, and Luca Ganassali. 2026. “Contextual Graph Matching with Correlated Gaussian Features.” arXiv (Cornell University).
Yarandi, M.H.A. and Ganassali, L. (2026) ‘Contextual Graph Matching with Correlated Gaussian Features’, arXiv (Cornell University).
@article{yarandi2026contextual,
title = {{Contextual Graph Matching with Correlated Gaussian Features}},
author = {Yarandi, Mohammad Hassan Ahmad and Ganassali, Luca},
journal = {arXiv (Cornell University)},
year = {2026}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.