  We present a parallelized bijective graph matching algorithm that leverages
seeds and is designed to match very large graphs. Our algorithm combines
spectral graph embedding with existing state-of-the-art seeded graph matching
procedures. We 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. We also demonstrate the
effectiveness of our approach in matching very large graphs in simulated and
real data examples, showing up to a factor of 8 improvement in runtime with
minimal sacrifice in accuracy.
