Cluster-and-Conquer: When Randomness Meets Graph Locality

2020-10-22 · George Giakkoupis, Anne-Marie Kermarrec, Olivier Ruas, François Taïani

K-Nearest-Neighbors (KNN) graphs are central to many emblematic data mining and machine-learning applications. Some of the most efficient KNN graph algorithms are incremental and local: they start from a random graph, which they incrementally improve by traversing neighbors-of-neighbors links. Paradoxically, this random start is also one of the key weaknesses of these algorithms: nodes are initially connected to dissimilar neighbors, that lie far away according to the similarity metric. As a result, incremental algorithms must first laboriously explore spurious potential neighbors before they can identify similar nodes, and start converging. In this paper, we remove this drawback with Cluster-and-Conquer (C 2 for short). Cluster-and-Conquer boosts the starting configuration of greedy algorithms thanks to a novel lightweight clustering mechanism, dubbed FastRandomHash. FastRandomHash leverages random-ness and recursion to pre-cluster similar nodes at a very low cost. Our extensive evaluation on real datasets shows that Cluster-and-Conquer significantly outperforms existing approaches, including LSH, yielding speed-ups of up to x4.42 while incurring only a negligible loss in terms of KNN quality.

📄 PDF Abstract BibTeX arXiv:2010.11497

Code (0)

등록된 구현이 없습니다.

Tasks

Clustering

Graph-Based Parallel Large Scale Structure from Motion

2019-12-23 · Yu Chen, Shuhan Shen, Yisong Chen, Guoping Wang

While Structure from Motion (SfM) achieves great success in 3D reconstruction, it still meets challenges on large scale scenes. In this work, large scale SfM is deemed as a graph problem, and we tackle it in a divide-and…

3D Reconstruction Clustering

Two provably consistent divide and conquer clustering algorithms for large networks

2017-08-18 · Soumendu Sundar Mukherjee, Purnamrita Sarkar, Peter J. Bickel

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…

Clustering Community Detection Vocal Bursts Valence Prediction

Rethinking Graph Auto-Encoder Models for Attributed Graph Clustering

2021-07-19 · Nairouz Mrabah, Mohamed Bouguessa, Mohamed Fawzi Touati, Riadh Ksantini

Most recent graph clustering methods have resorted to Graph Auto-Encoders (GAEs) to perform joint clustering and embedding learning. However, two critical issues have been overlooked. First, the accumulative error, infli…

Clustering Graph Clustering Node Clustering

Divide-and-conquer based Large-Scale Spectral Clustering

2021-04-30 · Hongmin Li, Xiucai Ye, Akira Imakura, Tetsuya Sakurai

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…

Clustering Image/Document Clustering

Cluster Catch Digraphs with the Nearest Neighbor Distance

2025-01-09 · Rui Shi, Nedret Billor, Elvan Ceyhan

We introduce a new method for clustering based on Cluster Catch Digraphs (CCDs). The new method addresses the limitations of RK-CCDs by employing a new variant of spatial randomness test that employs the nearest neighbor…