Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.23305 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914417854119936 |
|---|---|
| author | Yarandi, Mohammad Hassan Ahmad Ganassali, Luca |
| author_facet | Yarandi, Mohammad Hassan Ahmad Ganassali, Luca |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_23305 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Contextual Graph Matching with Correlated Gaussian Features Yarandi, Mohammad Hassan Ahmad Ganassali, Luca Machine Learning 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. |
| title | Contextual Graph Matching with Correlated Gaussian Features |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2603.23305 |