Multi-Hop Correlation Preserving Hashing for Efficient Hamming Space Retrieval

Hamming space retrieval, allowing for retrieval within a fixed Hamming radius rather than scanning all instances linearly, has gained widespread attention for retrieving nearest neighbors at a fixed computational cost. Current models have focused only on shared-label correlations as the label-wise semantics while ignoring the potential multi-hop constraints, which are the unique constraints in Hamming space retrieval under multi-label conditions. Instances with multi-dimensional labels form a multi-hop correlation graph rather than several clusters in a single-label scenario. So there are potential distance constraints between dissimilar instances connected through multi-hop correlations. Existing models blindly expanding the dissimilar instances will break the multi-hop correlations and finally disrupt the hashing consistency of the shared-label instances. This paper first defines the multi-hop correlations to address these challenges with the multi-hop preserving strategy for dissimilar instances to help the Hamming distance converge to the expected range. Meanwhile, we introduce a Wasserstein-1-distance-based loss to reduce information loss while encoding compactly. We evaluate our proposed model on three commonly used datasets with extensive experiments to demonstrate that our model achieves significant improvements over existing methods.