Spectral Clustering for Divide-and-Conquer Graph Matching
This provides a scalable solution for graph matching in large-scale applications, though it appears incremental as it builds on existing seeded matching methods.
The paper tackles the problem of matching very large graphs by developing a parallelized bijective graph matching algorithm that combines spectral graph embedding with existing seeded matching procedures. The approach achieves up to 8x faster runtime with minimal accuracy loss in simulated and real data examples.
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.