RREH: Reconstruction Relations Embedded Hashing for Semi-paired Cross-Modal Retrieval

Jianzong Wang, Haoxiang Shi, Kaiyi Luo, Xulong Zhang, Ning Cheng, Jing Xiao

Abstract

Cross-modal retrieval is essential for managing large-scale multi-modal data, such as searching for images using text queries. While hashing facilitates efficient retrieval by mapping data into binary strings, most existing methods assume a fully paired dataset. In real-world scenarios, datasets are often "semi-paired," containing a small fraction of linked data alongside vast amounts of unpaired samples. This paper presents Reconstruction Relations Embedded Hashing (RREH), an unsupervised framework that leverages high-order data relationships through anchor-based linear reconstruction. By avoiding the $O(n^2)$ complexity of traditional Laplacian-based methods, RREH provides a scalable and accurate solution for semi-paired retrieval tasks.

Introduction

The explosion of multi-modal data has made cross-modal retrieval—the ability to search across different data types like images and text—a critical research area. Hashing has emerged as a dominant technique to ensure these searches remain fast at scale. By transforming high-dimensional features into short binary codes, computers can perform similarity searches using extremely fast bitwise XOR operations.

However, a significant gap exists between academic assumptions and real-world data. Most hashing models require "perfectly paired" training data, where every image is strictly linked to a corresponding text description. In practice, datasets are typically semi-paired: while a few thousand pairs might be manually labeled, millions of other images and texts remain unpaired. Previous attempts to utilize this unpaired data often relied on Laplacian matrices to preserve data structures, but these methods suffer from $O(n^2)$ time complexity, making them computationally prohibitive for large-scale applications.

The RREH Framework

Reconstruction Relations Embedded Hashing (RREH) is designed to bridge the gap between paired and unpaired data without the computational penalty of graph-based methods. The framework is built on three core pillars: efficiency, high-order relationship modeling, and robust optimization.

1. Anchor-Based Linear Reconstruction

Instead of calculating pairwise similarities between every data point in the set—which leads to the $O(n^2)$ bottleneck—RREH utilizes a small set of "anchors" selected from the paired data. The model assumes that any unpaired data point can be represented as a linear reconstruction of these anchors. This approach captures high-order relationships (how a point relates to a group of representative samples) rather than simple one-to-one similarities, and it reduces the computational complexity significantly.

2. Shared Latent Subspace Learning

RREH operates on the principle that different modalities share a common underlying concept space. For paired data, the model forces the image and text representations to align directly in this latent space. For unpaired data, the model embeds the previously learned reconstruction relationships into this same subspace. This allows the unpaired data to "find its place" relative to the anchors, effectively using the paired data as a bridge to align the entire dataset.

3. Kernel Mapping and Discrete Optimization

To handle the non-linear complexities of high-dimensional data, RREH employs a kernel trick to map original features into a more expressive space before learning the hash functions. Furthermore, because learning binary codes is a non-convex problem (due to the discrete nature of bits), the authors utilize an alternating optimization algorithm. This process iteratively updates the hash functions, latent representations, and binary codes, ensuring efficient convergence.

Experimental Evaluation

The effectiveness of RREH was tested on two standard benchmarks:

  • MIRFlickr: 25,000 image-text pairs categorized into 24 classes.
  • NUS-WIDE: A large-scale dataset of approximately 270,000 images and associated tags.

To simulate the semi-paired challenge, the researchers used only 10% (and in some tests, 5%) of the available pairs during training. This forced the model to rely on its ability to extract meaningful information from the remaining 90-95% of unpaired data.

Key Results

RREH consistently outperformed state-of-the-art unsupervised baselines, including DUMCH, SPDH, and UAPMH, across various bit lengths (16, 32, and 64 bits). On the NUS-WIDE dataset, RREH demonstrated superior accuracy in both "Image query Text" and "Text query Image" tasks. For instance, in text-to-image retrieval at 64 bits, RREH achieved a Mean Average Precision (MAP) of 0.5719, notably higher than the next best method, DUMCH (0.5529).

Ablation studies further confirmed that the reconstruction component is vital; when the reconstruction term was removed, performance dropped significantly, particularly in scenarios with very low pairing ratios (5%).

Discussion and Conclusion

The primary contribution of RREH is the demonstration that high-order relationships, captured via linear reconstruction, are more effective and scalable than traditional pairwise similarity graphs. By reducing the computational burden, RREH makes unsupervised cross-modal hashing viable for massive, real-world datasets.

Despite its strengths, the model is sensitive to the hyperparameter $\theta$, which balances the binarization process. If $\theta$ is too high, the model may converge on binary codes too quickly, potentially sacrificing the quality of the continuous latent representation. Future research could investigate automated hyperparameter tuning or adapt the RREH framework for online/streaming environments where data is updated continuously.

Summary updated

BibTeX
@inproceedings{wang2024rreh,
  author = {Jianzong Wang and Haoxiang Shi and Kaiyi Luo and Xulong Zhang and Ning Cheng and Jing Xiao},
  title = {{RREH: Reconstruction Relations Embedded Hashing for Semi-paired Cross-Modal Retrieval}},
  booktitle = {ICIC (LNAI 5)},
  year = {2024},
  url = {https://openreview.net/forum?id=pikT849cCH},
}
Figure