# Stars: Tera-Scale Graph Building for Clustering and Graph Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 46 references that are in the map.
- First posted on arXiv 5 Dec 2022.

## Builds on (most cited first, 13 of 13)

- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [Optimal Data-Dependent Hashing for Approximate Near Neighbors](https://mlsanity.com/paper/1501.01062/) (2015)
- [Quantization based Fast Inner Product Search](https://mlsanity.com/paper/1509.01469/) (2015)
- [Grale: Designing Networks for Graph Learning](https://mlsanity.com/paper/2007.12002/) (2020)
- [Hierarchical Clustering via Spreading Metrics](https://mlsanity.com/paper/1610.09269/) (2016)
- [Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time](https://mlsanity.com/paper/2106.05610/) (2021)
- [Graph Spanners: A Tutorial Review](https://mlsanity.com/paper/1909.03152/) (2019)
- [Massively Parallel and Dynamic Algorithms for Minimum Size Clustering](https://mlsanity.com/paper/2106.02685/) (2021)
- [Maximally Consistent Sampling and the Jaccard Index of Probability Distributions](https://mlsanity.com/paper/1809.04052/) (2018)
- [The Anchors Hierachy: Using the triangle inequality to survive high dimensional data](https://mlsanity.com/paper/1301.3877/) (2013)
- [Practical Data-Dependent Metric Compression with Provable Guarantees](https://mlsanity.com/paper/1711.01520/) (2017)
- [Massively Parallel Computation via Remote Memory Access](https://mlsanity.com/paper/1905.07533/) (2019)

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

- [UGSL: A Unified Framework for Benchmarking Graph Structure Learning](https://mlsanity.com/paper/2308.10737/) (2023)

## Abstract (arXiv)

A fundamental procedure in the analysis of massive datasets is the construction of similarity graphs. Such graphs play a key role for many downstream tasks, including clustering, classification, graph learning, and nearest neighbor search. For these tasks, it is critical to build graphs which are sparse yet still representative of the underlying data. The benefits of sparsity are twofold: firstly, constructing dense graphs is infeasible in practice for large datasets, and secondly, the runtime of downstream tasks is directly influenced by the sparsity of the similarity graph. In this work, we present textitStars: a highly scalable method for building extremely sparse graphs via two-hop spanners, which are graphs where similar points are connected by a path of length at most two. Stars can construct two-hop spanners with significantly fewer similarity comparisons, which are a major bottleneck for learning based models where comparisons are expensive to evaluate. Theoretically, we demonstrate that Stars builds a graph in nearly-linear time, where approximate nearest neighbors are contained within two-hop neighborhoods. In practice, we have deployed Stars for multiple data sets allowing for graph building at the textitTera-Scale, i.e., for graphs with tens of trillions of edges. We evaluate the performance of Stars for clustering and graph learning, and demonstrate 10~1000-fold improvements in pairwise similarity comparisons compared to different baselines, and 2~10-fold improvement in running time without quality loss.