Random Graph Matching with Improved Noise Robustness
share
Graph matching, also known as network alignment, refers to finding a bijection between the vertex sets of two given graphs so as to maximally align their edges. This fundamental computational problem arises frequently in multiple fields such as computer vision and biology. Recently, there has been a plethora of work studying efficient algorithms for graph matching under probabilistic models. In this work, we propose a new algorithm for graph matching and show that, for two Erdős-Rényi graphs with edge correlation 1-α, our algorithm recovers the underlying matching with high probability when α≤ 1 / (loglog n)^C, where n is the number of vertices in each graph and C denotes a positive universal constant. This improves the condition α≤ 1 / (log n)^C achieved in previous work.
READ FULL TEXT