Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs

Dong Huang, Xianwen Song, Pengkun Yang
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2494-2518, 2024.

Abstract

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

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-huang24b, title = {Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs}, author = {Huang, Dong and Song, Xianwen and Yang, Pengkun}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {2494--2518}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/huang24b/huang24b.pdf}, url = {https://proceedings.mlr.press/v247/huang24b.html}, abstract = {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} }
Endnote
%0 Conference Paper %T Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs %A Dong Huang %A Xianwen Song %A Pengkun Yang %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-huang24b %I PMLR %P 2494--2518 %U https://proceedings.mlr.press/v247/huang24b.html %V 247 %X 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
APA
Huang, D., Song, X. & Yang, P.. (2024). Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:2494-2518 Available from https://proceedings.mlr.press/v247/huang24b.html.

Related Material