This paper studies the problem of recovering hidden vertex correspondences between two correlated random graphs. We introduce the partially correlated Erdős-Rényi model and the partially correlated Gaussian Wigner model, where a pair of induced subgraphs is correlated. We investigate the information-theoretic thresholds for recovering these latent correlated subgraphs and their hidden vertex correspondences. For the partially correlated Erdős-Rényi model, we establish the optimal rate for partial recovery: above this threshold, a positive fraction of vertices can be correctly matched, while below it, matching any positive fraction is impossible. We also determine the optimal rate for exact recovery. In the partially correlated Gaussian Wigner model, the optimal rates for partial and exact recovery coincide. To prove the achievability results, we introduce correlated functional digraphs to partition the edges and bound error probabilities using lower-order cumulant generating functions. Our impossibility results rely on a generalized Fano’s inequality and the recovery thresholds for correlated Erdős-Rényi graphs.

This paper studies the problem of recovering the hidden vertex correspondence between two correlated random graphs. We propose the partially correlated Erdős-Rényi graphs model, wherein a pair of induced subgraphs with a certain number are correlated. We investigate the information-theoretic thresholds for recovering the latent correlated subgraphs and the hidden vertex correspondence. We prove that there exists an optimal rate for partial recovery for the number of correlated nodes, above which one can correctly match a fraction of vertices and below which correctly matching any positive fraction is impossible, and we also derive an optimal rate for exact recovery. In the proof of possibility results, we propose correlated functional digraphs, which categorize the edges of the intersection graph into two cases of components, and bound the error probability by lower-order cumulant generating functions. The proof of impossibility results build upon the generalized Fano’s inequality and the recovery thresholds settled in correlated Erdős-Rényi graphs model