# Practice with Graph-based ANN Algorithms on Sparse Data: Chi-square Two-tower model, HNSW, Sign Cauchy Projections

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 48 references that are in the map.
- First posted on arXiv 13 Jun 2023.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Text and Code Embeddings by Contrastive Pre-Training](https://mlsanity.com/paper/2201.10005/) (2022)
- [DeCLUTR: Deep Contrastive Learning for Unsupervised Textual Representations](https://mlsanity.com/paper/2006.03659/) (2020)
- [Pre-training Tasks for Embedding-based Large-scale Retrieval](https://mlsanity.com/paper/2002.03932/) (2020)
- [General Multi-label Image Classification with Transformers](https://mlsanity.com/paper/2011.14027/) (2020)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [Deep Fragment Embeddings for Bidirectional Image Sentence Mapping](https://mlsanity.com/paper/1406.5679/) (2014)
- [Learning Tree-based Deep Model for Recommender Systems](https://mlsanity.com/paper/1801.02294/) (2018)
- [Hierarchical Bilinear Pooling for Fine-Grained Visual Recognition](https://mlsanity.com/paper/1807.09915/) (2018)
- [Joint Optimization of Tree-based Index and Deep Model for Recommender Systems](https://mlsanity.com/paper/1902.07565/) (2019)
- [Learning Optimal Tree Models Under Beam Search](https://mlsanity.com/paper/2006.15408/) (2020)
- [Deep Retrieval: Learning A Retrievable Structure for Large-Scale Recommendations](https://mlsanity.com/paper/2007.07203/) (2020)
- [Learning and Evaluating Sparse Interpretable Sentence Embeddings](https://mlsanity.com/paper/1809.08621/) (2018)
- [Proximity Graph Maintenance for Fast Online Nearest Neighbor Search](https://mlsanity.com/paper/2206.10839/) (2022)

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

- [CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs](https://mlsanity.com/paper/2308.15136/) (2023)
- [Experimental comparison of graph-based approximate nearest neighbor search algorithms on edge devices](https://mlsanity.com/paper/2411.14006/) (2024)

## Abstract (arXiv)

Sparse data are common. The traditional ``handcrafted'' features are often sparse. Embedding vectors from trained models can also be very sparse, for example, embeddings trained via the ``ReLu'' activation function. In this paper, we report our exploration of efficient search in sparse data with graph-based ANN algorithms (e.g., HNSW, or SONG which is the GPU version of HNSW), which are popular in industrial practice, e.g., search and ads (advertising). We experiment with the proprietary ads targeting application, as well as benchmark public datasets. For ads targeting, we train embeddings with the standard ``cosine two-tower'' model and we also develop the ``chi-square two-tower'' model. Both models produce (highly) sparse embeddings when they are integrated with the ``ReLu'' activation function. In EBR (embedding-based retrieval) applications, after we the embeddings are trained, the next crucial task is the approximate near neighbor (ANN) search for serving. While there are many ANN algorithms we can choose from, in this study, we focus on the graph-based ANN algorithm (e.g., HNSW-type). Sparse embeddings should help improve the efficiency of EBR. One benefit is the reduced memory cost for the embeddings. The other obvious benefit is the reduced computational time for evaluating similarities, because, for graph-based ANN algorithms such as HNSW, computing similarities is often the dominating cost. In addition to the effort on leveraging data sparsity for storage and computation, we also integrate ``sign cauchy random projections'' (SignCRP) to hash vectors to bits, to further reduce the memory cost and speed up the ANN search. In NIPS'13, SignCRP was proposed to hash the chi-square similarity, which is a well-adopted nonlinear kernel in NLP and computer vision. Therefore, the chi-square two-tower model, SignCRP, and HNSW are now tightly integrated.