# Large-Scale Graph Building in Dynamic Environments: Low Latency and High Quality

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 34 references that are in the map.
- First posted on arXiv 14 Jul 2025.

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

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Machine Learning on Graphs: A Model and Comprehensive Taxonomy](https://mlsanity.com/paper/2005.03675/) (2020)
- [SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2111.08566/) (2021)
- [Grale: Designing Networks for Graph Learning](https://mlsanity.com/paper/2007.12002/) (2020)
- [A Quest for Structure: Jointly Learning the Graph Structure and Semi-Supervised Classification](https://mlsanity.com/paper/1909.12385/) (2019)
- [SOAR: Improved Indexing for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2404.00774/) (2024)
- [Large Scale Distributed Semi-Supervised Learning Using Streaming Approximation](https://mlsanity.com/paper/1512.01752/) (2015)
- [Fast k-Nearest Neighbour Search via Dynamic Continuous Indexing](https://mlsanity.com/paper/1512.00442/) (2015)

## Abstract (arXiv)

Learning and constructing large-scale graphs has attracted attention in recent decades, resulting in a rich literature that introduced various systems, tools, and algorithms. Grale is one of such tools that is designed for offline environments and is deployed in more than 50 different industrial settings at Google. Grale is widely applicable because of its ability to efficiently learn and construct a graph on datasets with multiple types of features. However, it is often the case that applications require the underlying data to evolve continuously and rapidly and the updated graph needs to be available with low latency. Such setting make the use of Grale prohibitive. While there are Approximate Nearest Neighbor (ANN) systems that handle dynamic updates with low latency, they are mostly limited to similarities over a single embedding. In this work, we introduce a system that inherits the advantages and the quality of Grale, and maintains a graph construction in a dynamic setting with tens of milliseconds of latency per request. We call the system Dynamic Grale Using ScaNN (Dynamic GUS). Our system has a wide range of applications with over 10 deployments at Google. One of the applications is in Android Security and Privacy, where Dynamic Grale Using ScaNN enables capturing harmful applications 4 times faster, before they can reach users.