Research map / Graph learning / Graph algorithms and clustering
Stars: Tera-Scale Graph Building for Clustering and Learning
CJ Carey, Jonathan Halcrow, Rajesh Jayaram, Vahab Mirrokni, Warren Schudy, Peilin Zhong
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Stars star-graph construction instead of all-pairs comparisons within LSH buckets | LSH graph building · All evaluated datasets | pairwise similarity comparisons: at least a ∼10-fold improvement | Improved |
| Use LSH+Stars instead of non-Stars LSH | Amazon2m graph building · Amazon2m | total running time: 10× faster | Improved |
| Use Stars-based graph building with neural-network similarity rather than non-Stars graph building | Amazon2m · Amazon2m | VMeasure clustering quality | No clear effect |
| Use LSH+Stars instead of LSH | Graph building · Random10B | total running time: 100× | Improved |
| Use SortingLSH+Stars instead of SortingLSH | Graph building · Random10B | total running time: 10× | Improved |
| Use Stars instead of non-Stars LSH or SortingLSH | Graph building · Random10B | pairwise similarity comparisons: more than 95% | Improved |
| Reduce the number of Stars leaders to 1 (ablation) | Stars · Wikipedia, Amazon2m, MNIST | pairwise similarity comparisons: ∼ 100-fold improvement | Improved |
| Reduce the number of Stars leaders to 5 (ablation) | Stars · Wikipedia, Amazon2m, MNIST | pairwise similarity comparisons: ∼ 100-fold improvement | Improved |
| Use neural-network learned similarity instead of the cosine/Jaccard mixture | Amazon2m graph building and clustering · Amazon2m | VMeasure clustering quality | Improved |
| Use neural-network learned similarity instead of the cosine/Jaccard mixture | Amazon2m graph building · Amazon2m | total running time: 5×∼ 10× slower | Hurt |
Closest papers by meaning
- Non-Graph Data Clustering via $\mathcal {O}(n)$ Bipartite Graph Convolution (TPAMI 2022 · similarity 0.88)
- No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasets (ICML 2025 · similarity 0.86)
- DGCLUSTER: A Neural Framework for Attributed Graph Clustering via Modularity Maximization (AAAI 2024 · similarity 0.86)
- THESAURUS: Contrastive Graph Clustering by Swapping Fused Gromov-Wasserstein Couplings (AAAI 2025 · similarity 0.86)
- Graph Sparsification via Mixture of Graphs (ICLR 2025 · similarity 0.86)
- Local Graph Clustering with Noisy Labels (ICLR 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
