Discrete Graph Hashing

Wei Liu, Cun Mu, Sanjiv Kumar, Shih-Fu Chang

Introduction

Discrete Graph Hashing (DGH) tackles a notorious performance drop-off seen in unsupervised hashing as code lengths increase. By ditching the standard practice of "relaxing" binary constraints into continuous values, DGH optimizes hash codes directly in the discrete space. This approach achieves superior accuracy and nearly 100% search success rates on million-scale datasets, effectively solving the "long code" problem.

The "Relaxation Trap" in Compact Hashing

In the world of "Big Data," finding the nearest neighbor to a query—such as locating similar images in a database of millions—is computationally expensive. Compact Hashing addresses this by compressing high-dimensional data into short binary strings (hash codes). If two items are similar, their hash codes should have a small Hamming distance.

However, most unsupervised learning methods (like Spectral Hashing) face a major mathematical hurdle. Because optimizing discrete binary bits is NP-hard, researchers typically treat the bits as continuous numbers during training and then round them back to 0 or 1 at the end. As the desired hash code gets longer (e.g., moving from 32 to 128 bits), the errors introduced by this rounding step amplify. This "relaxation trap" causes search performance to plummet just when longer codes should theoretically provide better precision.

The Discrete Graph Hashing (DGH) Approach

The authors introduce DGH to avoid the relaxation trap entirely by working directly with discrete constraints. The framework relies on several key innovations:

  1. Anchor Graphs for Scalability: To handle massive datasets (up to 1 million points), DGH uses "anchors"—a small set of representative points—to approximate the neighborhood structure of the entire dataset. This reduces computational complexity from quadratic to linear.
  2. Discrete Optimization: Instead of relaxing the problem, the authors formulate an objective function that preserves the graph structure while strictly enforcing binary constraints.
  3. Alternating Maximization: The optimization is solved using a two-step iterative process:
  4. B-Subproblem: Updates the binary codes using a novel Signed Gradient Method (SGM).
  5. Y-Subproblem: Solves for a continuous auxiliary matrix using a closed-form solution via Singular Value Decomposition (SVD).
  6. Asymmetric Hashing: DGH learns the best possible codes for the training data directly and then induces a separate hash function to map new, unseen queries into that same code space.

Experimental Results

The authors evaluated DGH on four diverse, large-scale benchmarks: CIFAR-10, SUN397, YouTube Faces, and Tiny-1M (a massive subset of the 80 Million Tiny Images dataset). DGH consistently outperformed state-of-the-art unsupervised methods like Iterative Quantization (ITQ) and Spectral Hashing (SH).

Long Code Superiority and Success Rate

The core insight of the paper is that the poor performance of previous graph-based hashing wasn't due to the graph model itself, but the "relaxation + rounding" procedure. By staying in the discrete space, DGH maintains high recall even for long codes.

While other methods saw performance plateaus or severe dips as codes reached 128 bits, DGH's accuracy continued to climb. On the YouTube Faces and Tiny-1M datasets, DGH achieved a hash lookup success rate of nearly 100% for longer codes, whereas competitors often struggled to find any neighbors within a small Hamming radius.

Hash lookup success rates across four datasets

Efficiency and Precision

Despite the complex discrete optimization, DGH's training time remains highly practical. The authors proposed two initialization strategies (DGH-I and DGH-R), with DGH-R using an optimized rotation to provide a better starting point.

As shown in the performance tables, for 1 million samples (Tiny-1M), DGH-R takes about 45 minutes (~2793 seconds) to train. This is significantly faster than distance-preservation methods like BRE, which took over 2 hours (~8419 seconds) for the same task, all while DGH delivers superior mean precision.

Mean Precision and Training Time on YouTube Faces and Tiny-1M

Limitations and Future Work

While highly effective, the DGH framework has a few limitations:

  • Local Optima: Because the underlying problem is NP-hard, the alternating maximization algorithm is guaranteed to converge, but only to a local optimum. The suggested initializations (like DGH-R) work well in practice, but there is no theoretical guarantee of reaching the global best.
  • Asymmetry: The fact that training samples and queries are encoded differently (asymmetric hashing) is a strength for accuracy but adds a layer of complexity to the system architecture compared to simple, symmetric linear projections.
  • Hyperparameters: The model's performance depends on tuning the penalty parameter $\rho$ and the number of anchors $m$, which may require adjustment when applied to new datasets.

Summary updated

Abstract

Hashing has emerged as a popular technique for fast nearest neighbor search in gigantic databases. In particular, learning based hashing has received considerable attention due to its appealing storage and search efficiency. However, the performance of most unsupervised learning based hashing methods deteriorates rapidly as the hash code length increases. We argue that the degraded performance is due to inferior optimization procedures used to achieve discrete binary codes. This paper presents a graph-based unsupervised hashing model to preserve the neighborhood structure of massive data in a discrete code space. We cast the graph hashing problem into a discrete optimization framework which directly learns the binary codes. A tractable alternating maximization algorithm is then proposed to explicitly deal with the discrete constraints, yielding high-quality codes to well capture the local neighborhoods. Extensive experiments performed on four large datasets with up to one million samples show that our discrete optimization based graph hashing method obtains superior search accuracy over state-of-the-art unsupervised hashing methods, especially for longer codes.
BibTeX
@inproceedings{liu2014discrete,
  author = {Wei Liu and Cun Mu and Sanjiv Kumar and Shih-Fu Chang},
  title = {{Discrete Graph Hashing}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure