Abstract
Hashing is essential for approximate nearest neighbor (ANN) search in large-scale applications due to its efficiency. Graph hashing, which preserves neighborhood similarity, is highly effective but suffers from $O(n^2)$ complexity. This paper introduces Scalable Graph Hashing (SGH), a method that uses feature transformation to approximate the similarity graph in linear time. Experiments on million-scale datasets demonstrate that SGH achieves superior accuracy and scalability compared to existing methods.
Introduction
Approximate Nearest Neighbor (ANN) search is a fundamental task in modern information retrieval. Hashing techniques address this by mapping high-dimensional data into compact binary codes, enabling rapid searches in Hamming space. Graph hashing methods are particularly effective because they explicitly model the similarity structure of the data. However, the computational cost of building a full similarity matrix—$O(n^2)$—is prohibitive for datasets with millions of points. While anchor-based methods attempt to mitigate this, they often sacrifice accuracy or introduce new bottlenecks.
Methodology: Scalable Graph Hashing (SGH)
The SGH framework addresses the scalability bottleneck through two core innovations: feature transformation and sequential bit-wise learning.
Feature Transformation
To avoid the $O(n^2)$ cost of computing a Gaussian similarity kernel $S_{ij} = \exp(-\|x_i - x_j\|^2 / \sigma^2)$, SGH employs a feature transformation trick. By decomposing the similarity function, the algorithm approximates the kernel using the dot product of transformed features $P(x)$ and $Q(x)$.
As shown in Figure 1, the transformation relies on approximating the exponential term. This allows the similarity graph to be handled through matrix multiplications with $O(n)$ complexity, making it feasible for million-scale datasets.
Sequential Bit-Wise Learning
Rather than solving a complex NP-hard problem to learn all hash bits simultaneously, SGH adopts a sequential approach. It learns one bit at a time by solving a generalized eigenvalue problem. After each bit is determined, the algorithm calculates the residual error and trains the subsequent bit to minimize this error, ensuring that each bit contributes unique information and reducing redundancy.
Experimental Evaluation
SGH was evaluated on two large-scale benchmarks:
- TINY-1M: 1 million images (384D GIST features).
- MIRFLICKR-1M: 1 million images (512D features). In both cases, 5,000 queries were used against a retrieval set of 995,000 points.
Performance Results
SGH consistently outperforms state-of-the-art unsupervised hashing methods, including Iterative Quantization (ITQ) and Anchor Graph Hashing (AGH).
As illustrated in Figure 3, SGH (indicated by the red star line) maintains the highest precision across various numbers of returned samples for both 64-bit and 128-bit codes. For instance, on TINY-1M with 128-bit codes, SGH achieved a Top-1000 precision of 0.6737, significantly outperforming ITQ (0.4986).
Scalability and Efficiency
Beyond accuracy, SGH demonstrates remarkable efficiency. On the TINY-1M dataset, SGH requires only 52 seconds to train 64-bit codes. Competing graph-based methods like AGH and DGH often require over 1,400 seconds just for the initial anchor graph construction, highlighting SGH's practical advantage for big data applications.
Conclusion
Scalable Graph Hashing (SGH) successfully bridges the gap between the high accuracy of graph-based hashing and the requirements of large-scale retrieval. By leveraging feature transformation to achieve linear complexity and sequential learning to optimize code quality, SGH provides a robust solution for million-scale ANN search. Future work may explore extending this feature transformation approach to supervised hashing or optimizing kernel basis selection.
Summary updated