From tree matching to sparse graph alignment

Luca Ganassali, Laurent Massoulié
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1633-1665, 2020.

Abstract

In this paper we consider alignment of sparse graphs, for which we introduce the Neighborhood Tree Matching Algorithm (NTMA). For correlated Erdős-R{é}nyi random graphs, we prove that the algorithm returns – in polynomial time – a positive fraction of correctly matched vertices, and a vanishing fraction of mismatches. This result holds with average degree of the graphs in $O(1)$ and correlation parameter $s$ that can be bounded away from $1$, conditions under which random graph alignment is particularly challenging. As a byproduct of the analysis we introduce a matching metric between trees and characterize it for several models of correlated random trees. These results may be of independent interest, yielding for instance efficient tests for determining whether two random trees are correlated or independent.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-ganassali20a, title = {From tree matching to sparse graph alignment}, author = {Ganassali, Luca and Massouli\'e, Laurent}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {1633--1665}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/ganassali20a/ganassali20a.pdf}, url = {https://proceedings.mlr.press/v125/ganassali20a.html}, abstract = { In this paper we consider alignment of sparse graphs, for which we introduce the Neighborhood Tree Matching Algorithm (NTMA). For correlated Erdős-R{é}nyi random graphs, we prove that the algorithm returns – in polynomial time – a positive fraction of correctly matched vertices, and a vanishing fraction of mismatches. This result holds with average degree of the graphs in $O(1)$ and correlation parameter $s$ that can be bounded away from $1$, conditions under which random graph alignment is particularly challenging. As a byproduct of the analysis we introduce a matching metric between trees and characterize it for several models of correlated random trees. These results may be of independent interest, yielding for instance efficient tests for determining whether two random trees are correlated or independent.} }
Endnote
%0 Conference Paper %T From tree matching to sparse graph alignment %A Luca Ganassali %A Laurent Massoulié %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-ganassali20a %I PMLR %P 1633--1665 %U https://proceedings.mlr.press/v125/ganassali20a.html %V 125 %X In this paper we consider alignment of sparse graphs, for which we introduce the Neighborhood Tree Matching Algorithm (NTMA). For correlated Erdős-R{é}nyi random graphs, we prove that the algorithm returns – in polynomial time – a positive fraction of correctly matched vertices, and a vanishing fraction of mismatches. This result holds with average degree of the graphs in $O(1)$ and correlation parameter $s$ that can be bounded away from $1$, conditions under which random graph alignment is particularly challenging. As a byproduct of the analysis we introduce a matching metric between trees and characterize it for several models of correlated random trees. These results may be of independent interest, yielding for instance efficient tests for determining whether two random trees are correlated or independent.
APA
Ganassali, L. & Massoulié, L.. (2020). From tree matching to sparse graph alignment. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:1633-1665 Available from https://proceedings.mlr.press/v125/ganassali20a.html.

Related Material