Abstract: Shulong Tan, Zhixin Zhou, Zhaozhuo Xu, Ping Li. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP).
2019.
Introduction
In modern artificial intelligence, entities such as words, users, and products are frequently represented as dense vectors in high-dimensional spaces. Finding the most similar item to a query vector typically involves Maximum Inner Product Search (MIPS). However, the inner product is a non-metric measure; unlike Euclidean distance, it does not satisfy the triangle inequality.
Most existing Approximate Nearest Neighbor Search (ANNS) tools are optimized for metric spaces. When applied to MIPS, these tools often suffer from efficiency bottlenecks or require complex mathematical transformations that limit performance. Researchers from Baidu have addressed this by developing the Inner Product Delaunay Graph (IPDG), a graph-based search method designed specifically for the unique geometry of inner products.
Methods
The IPDG approach introduces two primary innovations to optimize graph-based retrieval for non-metric spaces:
1. Inner Product-Specific Edge Selection
Traditional graph methods like HNSW add edges to maintain graph diversity based on distance. In contrast, IPDG employs a pruning rule tailored for MIPS: an edge to a candidate point $b$ is only retained if $b$ is not "hidden" by a superior point $a$. Specifically, if $b^T b \leq a^T b$, point $b$ is considered dispensable and the edge is discarded. This logic results in a sparser graph that prioritizes "extreme points" on the dataset's convex hull.
2. Two-Round Construction
To ensure high graph quality regardless of point insertion order, the authors implement a two-round construction process. This allows the graph to refine its structure and globally discover the most effective extreme points, preventing early-inserted points from degrading the final search efficiency.
Key Insights: The Power of Extreme Points
A fundamental observation of this work is that for inner product search, only points residing on the convex hull (the outer boundary of the point cloud) can ever be the top-1 result for a query. Traditional metric-based methods often waste computational resources navigating through "internal" points that are mathematically incapable of being the optimal match.
By pruning edges that do not lead toward the convex hull, IPDG creates an efficient "highway" system. This sparsity directly translates to search speed without sacrificing accuracy.
Evaluation and Results
The authors evaluated IPDG across six datasets representing NLP (e.g., fastText, GloVe) and Recommendation Systems (e.g., Amazon Movie, Netflix).
- Superior Efficiency: IPDG consistently outperformed state-of-the-art methods like HNSW-Wrapper and ip-NSW in "Recall vs. Time" benchmarks.
- Reduced Computational Overhead: On the
fastTextFrdataset, IPDG achieved 95% recall while examining only 0.07% of the total data, compared to 0.3% for the previous best method. - Robustness: IPDG maintained high performance across varying dimensions, proving more stable than baselines that struggled with high-dimensional word embeddings.
- Graph Quality: Analysis confirmed that IPDG graphs have significantly fewer nodes with incoming edges, validating the strategy of ignoring non-extreme points.
Conclusion and Future Work
IPDG demonstrates that tailoring graph structures to the specific mathematical properties of the similarity measure—rather than forcing metric assumptions—yields significant performance gains. While currently optimized for top-1 retrieval, future research may extend these principles to top-$n$ search and hardware-accelerated (GPU) implementations for billion-scale datasets.
Summary updated