Spectral Clustering for Divide-and-Conquer Graph Matching
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.
Code (1)
Tasks
ClusteringGraph EmbeddingGraph MatchingStochastic Block ModelSimilar Papers 제목 키워드 기반
Divide-and-conquer based Large-Scale Spectral Clustering
Spectral clustering is one of the most popular clustering methods. However, how to balance the efficiency and effectiveness of the large-scale spectral clustering with limited computing resources has not been properly so…
ClusteringImage/Document ClusteringTwo provably consistent divide and conquer clustering algorithms for large networks
In this article, we advance divide-and-conquer strategies for solving the community detection problem in networks. We propose two algorithms which perform clustering on a number of small subgraphs and finally patches the…
ClusteringCommunity DetectionVocal Bursts Valence Prediction$DC^2$: A Divide-and-conquer Algorithm for Large-scale Kernel Learning with Application to Clustering
Divide-and-conquer is a general strategy to deal with large scale problems. It is typically applied to generate ensemble instances, which potentially limits the problem size it can handle. Additionally, the data are ofte…
ClusteringHyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering
Hypergraphs allow modeling problems with multi-way high-order relationships. However, the computational cost of most existing hypergraph-based algorithms can be heavily dependent upon the input hypergraph sizes. To addre…
Clusteringhypergraph partitioningHierarchical Manifold Clustering on Diffusion Maps for Connectomics (MIT 18.S096 final project)
In this paper, we introduce a novel algorithm for segmentation of imperfect boundary probability maps (BPM) in connectomics. Our algorithm can be a considered as an extension of spectral clustering. Instead of clustering…
ClusteringSegmentation