# Spectral Clustering for Divide-and-Conquer Graph Matching

arXiv: https://arxiv.org/abs/1310.1297 · HTML: https://mlsanity.com/paper/1310.1297/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Oct 2013.

## Built on by (most cited first, 5 of 5)

- [Learning to Match Features with Seeded Graph Matching Network](https://mlsanity.com/paper/2108.08771/) (2021)
- [Graph Matching via Optimal Transport](https://mlsanity.com/paper/2111.05366/) (2021)
- [A computational transition for detecting correlated stochastic block models by low-degree polynomials](https://mlsanity.com/paper/2409.00966/) (2024)
- [Convex Joint Graph Matching and Clustering via Semidefinite Relaxations](https://mlsanity.com/paper/2110.11335/) (2021)
- [Detection of Model-based Planted Pseudo-cliques in Random Dot Product Graphs by the Adjacency Spectral Embedding and the Graph Encoder Embedding](https://mlsanity.com/paper/2312.11054/) (2023)

## Abstract (arXiv)

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.