Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdős-Rényi Graphs

Graph alignment in two correlated random graphs refers to the task of identifying the correspondence between vertex sets of the graphs. Recent results have characterized the exact information-theoretic threshold for graph alignment in correlated Erdös-Rényi graphs. However, very little is known about the existence of efficient algorithms to achieve graph alignment without seeds. In this work we identify a region in which a straightforward O(n11/5 log n)-time canonical labeling algorithm, initially introduced in the context of graph isomorphism, succeeds in aligning correlated Erdos-Rényi graphs. The algorithm has two steps. In the first step, all vertices are labeled by their degrees and a trivial minimum distance alignment (i.e., sorting vertices according to their degrees) matches a fixed number of highest degree vertices in the two graphs. Having identified this subset of vertices, the remaining vertices are matched using a alignment algorithm for bipartite graphs. Finally, we show that the implementation of a variant of this algorithm allows for the efficient alignment of large graphs under limited noise.

Published in:
Proceedings of ACM SIGMETRICS 2019, 3, 2, 36:1-36:25
Presented at:
Joint International Conference on Measurement and Modeling of Computer Systems - SIGMETRICS '19, Phoenix, AZ, USA, June, 2019
Jun 01 2019
Association for Computing Machinery (ACM)
Other identifiers:

Note: The status of this file is: Anyone

 Record created 2020-02-20, last modified 2020-04-20

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)