Contextual Graph Matching with Correlated Gaussian Features
This work provides foundational insights for researchers in network analysis and machine learning by rigorously characterizing how structural and contextual information interact in graph matching, establishing a benchmark for algorithm design.
The paper tackles the problem of contextual graph matching with correlated Gaussian features, deriving precise information-theoretic thresholds for exact and almost exact recovery based on graph and feature correlations, node count, and feature dimension, and reveals that contextual information introduces a richer phase transition structure compared to standard graph matching.
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.