Graph Matching with Partially-Correct Seeds
share
The graph matching problem aims to find the latent vertex correspondence between two edge-correlated graphs and has many practical applications. In this work, we study a version of the seeded graph matching problem, which assumes that a set of seeds, i.e., pre-mapped vertex-pairs, is given in advance. Specifically, consider two correlated graphs whose edges are sampled independently with probability s from a parent graph 𝒢(n,p). Furthermore, a mapping between the vertices of the two graphs is provided as seeds, of which an unknown β fraction is correct. This problem was first studied in <cit.> where an algorithm is proposed and shown to perfectly recover the correct vertex mapping with high probability if β≥max{8/3p,16logn/nps^2}. We improve their condition to β≥max{30√(log n/n(1-p)^2s^2),45logn/np(1-p)^2s^2). However, when p=O( √(log n/ns^2)), our improved condition still requires that β must increase inversely proportional to np. In order to improve the matching performance for sparse graphs, we propose a new algorithm that uses "witnesses" in the 2-hop neighborhood, instead of only 1-hop neighborhood as in <cit.>. We show that when np^2≤1/135log n, our new algorithm can achieve perfect recovery with high probability if β≥max{900√(np^3(1-s)log n/s),600√(log n/ns^4), 1200log n/n^2p^2s^4} and nps^2≥ 128log n. Numerical experiments on both synthetic and real graphs corroborate our theoretical findings and show that our 2-hop algorithm significantly outperforms the 1-hop algorithm when the graphs are relatively sparse.
READ FULL TEXT