2024-06-30-huang24b.md

title	section	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs	Original Papers	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	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	huang24b	0	Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs	2494	2518	2494-2518	2494	false	Huang, Dong and Song, Xianwen and Yang, Pengkun	given family Dong Huang given family Xianwen Song given family Pengkun Yang	2024-06-30		Proceedings of Thirty Seventh Conference on Learning Theory	247	inproceedings	date-parts 2024 6 30	https://proceedings.mlr.press/v247/huang24b/huang24b.pdf