Spectral Clustering for Divide-and-Conquer Graph Matching

We present a bijective parallelizable seeded graph matching algorithm designed to match very large graphs. Our algorithm combines spectral graph embedding with existing state-of-the-art seeded graph matching procedures. We theoretically justify our approach by proving that modestly correlated, large stochastic block model random graphs are correctly matched utilizing very few seeds through our divide-and-conquer procedure. Lastly, we demonstrate the effectiveness of our approach in matching very large graphs in simulated and real data examples.