Deep Graph Online Hashing for Multi-Label Image Retrieval

Yuan Cao, Xiangru Chen, Zifan Liu, Wenzhe Jia, Fanlei Meng, Jie GuiAAAI 2025 · DOI

Abstract: Online hashing is essential for efficient image retrieval in dynamic environments where data arrives in continuous streams. Current online hashing methods often rely on shallow architectures or fail to capture complex multi-label semantic relationships, leading to suboptimal retrieval performance and catastrophic forgetting. We present Deep Graph Online Hashing (DGOH), the first framework to integrate deep inductive Graph Neural Networks (GNNs) into the online hashing paradigm. DGOH utilizes a bilayer GNN architecture to model both image features and label correlations dynamically. By learning label-wise weights and implementing a strategic "dissimilar sampling" approach for knowledge retention, DGOH achieves state-of-the-art performance on benchmark datasets while remaining computationally feasible for real-time updates.

Introduction

The explosion of visual data in the modern era necessitates efficient retrieval mechanisms. Hashing transforms high-dimensional images into compact binary codes, enabling fast similarity searches. While offline hashing is well-established for static datasets, real-world applications like social media monitoring or live surveillance require online hashing—the ability to update hash functions incrementally as new data arrives.

Existing online hashing research faces three primary challenges:

  1. Model Depth: Most online methods use shallow linear models because updating deep neural networks typically takes too long for streaming scenarios.
  2. Static Similarity: Current methods often treat all labels as equally important, failing to capture the nuanced semantic relationships inherent in multi-label data.
  3. Catastrophic Forgetting: As models learn from new data batches, they tend to lose information learned from previous data.

The DGOH Framework

DGOH addresses these challenges through a novel bilayer architecture consisting of two interconnected inductive GNNs: the Feature Network and the Label Network.

Bilayer Architecture

  • Feature Network: This network utilizes a Vision GNN backbone to extract image features, which are then mapped into a graph. Because it employs inductive GNNs, it can generate hash codes for new, unseen images by aggregating information from their local neighborhood in the feature space without requiring a full system retrain.
  • Label Network: This component serves as the semantic core. It uses Word2Vec embeddings to construct a label graph and dynamically learns label-wise weights ($\omega$). This allows the model to realize that sharing a rare, specific label is a much stronger signal of similarity than sharing a common, broad label.
The DGOH framework architecture, featuring the Feature and Label Networks.

Dynamic Similarity and Knowledge Retention

Instead of a simple binary similarity score, DGOH calculates a fine-grained Dynamic Affinity Matrix using the learned label weights. This matrix evolves with each new batch of data. To combat catastrophic forgetting, the authors implement a Knowledge Retaining Strategy. Rather than random sampling, the model specifically selects historical examples that are dissimilar to the incoming data, ensuring the model maintains a diverse internal representation of the entire dataset over time.

Experimental Evaluation

The authors evaluated DGOH on two standard multi-label benchmarks: MIRFlickr (25,000 images) and MSCOCO (approximately 122,218 images). To simulate real-world streaming, data was processed in online batches of 50 images.

Key Results

DGOH consistently outperformed eight state-of-the-art baselines, including OKH, BSODH, and FOH. Key findings include:

  • Superior Accuracy: DGOH achieved Mean Average Precision (mAP) gains of up to 11.6% on MIRFlickr and 13.3% on MSCOCO.
  • Practical Efficiency: Despite its deep architecture, DGOH updates in seconds. While slightly slower than the fastest shallow models (which operate in milliseconds), it remains highly practical for real-time applications where accuracy is the priority.
  • Ablation Insights: Removing the label network or the dissimilar sampling strategy led to significant performance drops, confirming that multi-label mining and strategic memory retention are the primary drivers of the accuracy boost.
Precision-Recall curves comparing DGOH against state-of-the-art methods on MIRFlickr and MS-COCO datasets.

Conclusion

Presented at AAAI-25, DGOH represents a significant advancement in online hashing by successfully leveraging deep inductive GNNs. By moving beyond shallow models and static similarity metrics, it provides a robust solution for multi-label image retrieval in streaming contexts. Future research will focus on further optimizing graph maintenance for million-scale databases and exploring unsupervised adaptations of the framework.

Summary updated

BibTeX
@inproceedings{cao2025deep,
  author = {Yuan Cao and Xiangru Chen and Zifan Liu and Wenzhe Jia and Fanlei Meng and Jie Gui},
  title = {{Deep Graph Online Hashing for Multi-Label Image Retrieval}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i2.32191},
}
Figure