Introduction
In large-scale information retrieval, document hashing is a critical technique for achieving speed and memory efficiency. By compressing documents into short binary strings, similarity can be calculated using rapid bitwise operations. However, a persistent challenge is ensuring these hash codes accurately reflect both the semantic content of a document and its relationship to other documents in a corpus.
Historically, unsupervised hashing methods have diverged into two main approaches: semantic-focused generative models (like Variational Autoencoders) and neighborhood-focused graph-based models. While the former excels at capturing internal text nuances, they often treat documents as independent entities. Conversely, graph-based models preserve structural relationships but may overlook fine-grained semantic details. This paper introduces SNUH (Semantics-Neighborhood Unified Hashing), a framework presented at ACL 2021 that unifies these perspectives within a single generative model.
The SNUH Framework
SNUH addresses the limitations of previous hybrid methods, which often relied on heuristic "neighbor-preserving" penalties. Instead, SNUH incorporates neighborhood information directly into the model's prior distribution.
Graph-Driven Generative Modeling
The core innovation is a graph-induced prior. Rather than drawing latent codes from independent Gaussian distributions, SNUH uses a multivariate Gaussian where the covariance is defined by a document similarity graph. This ensures that the model is inherently aware of document relationships before processing the text.
Overcoming Computational Complexity
Modeling correlations across millions of documents typically leads to intractable $O(N^3)$ matrix inversions. SNUH bypasses this computational bottleneck through a tree-structured approximation. By approximating the document graph using a set of spanning trees, the authors prove that the training objective—the Evidence Lower Bound (ELBO)—can be decomposed into terms involving only individual documents or pairs. This allows for efficient training comparable to models that assume document independence.
Methodology
The SNUH architecture employs a correlated encoder strategy. It utilizes two encoders: one for individual document features and another that examines pairs of documents to refine their latent representations based on their graph-defined relationships. This dual-stream approach ensures that the resulting hash codes are informed by both local semantics and global context.
Experimental Evaluation
The framework was evaluated on three benchmark datasets: Reuters25178, TMC (air traffic reports), and 20Newsgroups (NG20).
Performance and Efficiency
SNUH consistently outperformed state-of-the-art (SOTA) methods such as AMMI and CorrSH across various bit lengths. For instance, on the 20Newsgroups dataset, SNUH achieved an average precision of 0.6731 at 128 bits, a significant improvement over the previous SOTA of 0.6359.
Crucially, this performance gain does not come at the cost of scalability. On the Reuters dataset, SNUH's training time per epoch (~3.79s) remained competitive with much simpler models like VDSH (~2.04s), demonstrating the effectiveness of the tree-structured approximation.
The Impact of Multiple Spanning Trees
A key insight from the study is that using a mixture of multiple spanning trees significantly enhances retrieval accuracy. Different trees capture different paths of similarity, providing a more robust representation of the underlying graph structure.
Conclusion
SNUH represents a principled step forward in document hashing by unifying semantic and neighborhood information. By leveraging graph-driven priors and efficient tree-structured approximations, it achieves state-of-the-art retrieval performance while maintaining the scalability required for real-world applications. Future work may explore more sophisticated graph construction methods and the application of this framework to other correlated data modalities.
Summary updated