Spectral Clustering for Divide-and-Conquer Graph Matching

Author name not available (Why is that?)

Publication date: 4 October 2013

Abstract: 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.

Has companion code repository: https://github.com/lichen11/LSGMcode

This page was built for publication: Spectral Clustering for Divide-and-Conquer Graph Matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6245356)