An Incremental Reseeding Strategy for Clustering
In this work we propose a simple and easily parallelizable algorithm for multiway graph partitioning. The algorithm alternates between three basic components: diffusing seed vertices over the graph, thresholding the diffused seeds, and then randomly reseeding the thresholded clusters. We demonstrate experimentally that the proper combination of these ingredients leads to an algorithm that achieves state-of-the-art performance in terms of cluster purity on standard benchmarks datasets. Moreover, the algorithm runs an order of magnitude faster than the other algorithms that achieve comparable results in terms of accuracy. We also describe a coarsen, cluster and refine approach similar to GRACLUS and METIS that removes an additional order of magnitude from the runtime of our algorithm while still maintaining competitive accuracy.
Code (0)
등록된 구현이 없습니다.
Tasks
Clusteringgraph partitioningSimilar Papers 제목 키워드 기반
Unsupervised vehicle recognition using incremental reseeding of acoustic signatures
Vehicle recognition and classification have broad applications, ranging from traffic flow management to military target identification. We demonstrate an unsupervised method for automated identification of moving vehicle…
ClusteringDimensionality ReductionGeneral ClassificationManagementAdaptive Markov State Model estimation using short reseeding trajectories
In the last decade, advances in molecular dynamics (MD) and Markov State Model (MSM) methodologies have made possible accurate and efficient estimation of kinetic rates and reactive pathways for complex biomolecular dyna…
Protein FoldingIncremental Clustering: The Case for Extra Clusters
The explosion in the amount of data available for analysis often necessitates a transition from batch to incremental clustering methods, which process one element at a time and typically store only a small subset of the …
ClusteringIncremental Minimax Optimization based Fuzzy Clustering for Large Multi-view Data
Incremental clustering approaches have been proposed for handling large data when given data set is too large to be stored. The key idea of these approaches is to find representatives to represent each cluster in each da…
ClusteringToward Efficient and Incremental Spectral Clustering via Parametric Spectral Clustering
Spectral clustering is a popular method for effectively clustering nonlinearly separable data. However, computational limitations, memory requirements, and the inability to perform incremental learning challenge its wide…
ClusteringComputational EfficiencyIncremental Learning