Wasserstein Coupled Graph Learning for Cross-Modal Retrieval

Yun Wang, Tong Zhang, Xueya Zhang, Zhen Cui, Yuge Huang, Pengcheng Shen, Shaoxin Li, Jian Yang

Abstract

Cross-modal retrieval—the task of searching for data in one modality (e.g., images) using a query from another (e.g., text)—is fundamentally challenged by the "heterogeneity gap." This paper introduces Wasserstein Coupled Graph Learning (WCGL), a framework that bridges this gap by representing data as graphs and mapping them into a shared dictionary space. By utilizing the Wasserstein distance for structural comparison, WCGL achieves state-of-the-art performance across multiple benchmarks, demonstrating the power of relational structure in cross-modal alignment.

Introduction

Traditional cross-modal retrieval methods often treat images and sentences as "flat" feature vectors, effectively ignoring the rich internal structures and relationships between entities, such as a "person" "holding" a "surfboard." While graph-based methods have been proposed to capture these relationships, they often suffer from high computational complexity or poor alignment between disparate modalities. WCGL addresses these issues by combining Graph Convolutional Networks (GCNs) with an optimal transport-based embedding strategy, allowing for a robust and differentiable comparison of structural information.

The WCGL Framework

The WCGL architecture is built upon three core pillars designed to extract and align structural features:

  1. Graph Encoding: Input data is transformed into graphs where nodes represent objects or words and edges represent their relationships. These graphs are processed through GCNs to extract high-level structural features.
  2. Wasserstein Graph Embedding (WGE): The model maintains a Coupled Graph Dictionary—a set of learnable "template" graphs for both vision and text. The similarity between an input graph and these templates is calculated using the entropy-smoothed Wasserstein distance, solved via Sinkhorn iterations. This projects different modalities into a common "dictionary space."
  3. Discriminant Learning: To ensure semantic alignment, a Wasserstein Discriminant Loss (WD-loss) forces "counterpart" keys (e.g., the visual and textual templates for the same concept) to be close in the embedding space while pushing unrelated templates apart.
The WCGL architecture overview, showing the dual-path processing of vision and text through graph encoders and the coupled dictionary.

Experimental Evaluation

The model was evaluated on four major benchmarks: Flickr30K, MSCOCO, Real-world Scene Graph (RSG), and Moviegraphs. WCGL consistently outperformed existing state-of-the-art (SOTA) methods:

  • Flickr30K: Achieved a Recall@1 (R@1) of 74.8% for image-to-text retrieval, surpassing the previous best of 72.6%.
  • Moviegraphs: On this highly structural video-to-text dataset, WCGL reached an R@1 of 9.20%, a significant improvement over the previous SOTA (7.40%).

Performance is sensitive to architectural choices such as the number of layers in the graph encoder and the size of the coupled dictionary. Ablation studies confirmed that the shared template space provided by the dictionary is essential for effective cross-modal alignment.

Performance sensitivity analysis across different parameters: (a) number of graph encoder layers, (b) number of dictionary keys, and (c-d) loss weighting hyperparameters.

Key Insights

  • Structure as a Universal Language: By focusing on relationships rather than just isolated entities, the model finds a more stable bridge between vision and language.
  • Soft Matching via Optimal Transport: Using the Wasserstein distance allows for a "soft," differentiable alignment of nodes between graphs, making structural comparison compatible with end-to-end deep learning.
  • Dictionary Bottleneck: Comparing inputs to a small set of optimized "concepts" (the dictionary) filters out noise and focuses the model on core semantic meanings.

Limitations and Future Work

Despite its success, WCGL's performance is dependent on the quality of initial graph construction (e.g., object detection accuracy). Additionally, while Sinkhorn iterations make Wasserstein distance feasible, they still introduce more computational overhead than simple dot-product similarities. Future research will explore dynamic graph construction methods and further optimization of the dictionary scaling process.

Summary updated

Abstract

Graphs play an important role in cross-modal image-text understanding as they characterize the intrinsic structure which is robust and crucial for the measurement of crossmodal similarity. In this work, we propose a Wasserstein Coupled Graph Learning (WCGL) method to deal with the cross-modal retrieval task. First, graphs are constructed according to two input cross-modal samples separately, and passed through the corresponding graph encoders to extract robust features. Then, a Wasserstein coupled dictionary, containing multiple pairs of counterpart graph keys with each key corresponding to one modality, is constructed for further feature learning. Based on this dictionary, the input graphs can be transformed into the dictionary space to facilitate the similarity measurement through a Wasserstein Graph Embedding (WGE) process. The WGE could capture the graph correlation between the input and each corresponding key through optimal transport, and hence well characterize the inter-graph structural relationship. To further achieve discriminant graph learning, we specifically define a Wasserstein discriminant loss on the coupled graph keys to make the intra-class (counterpart) keys more compact and inter-class (non-counterpart) keys more dispersed, which further promotes the final cross-modal retrieval task. Experimental results demonstrate the effectiveness and state-of-the-art performance.
BibTeX
@inproceedings{wang2021wasserstein,
  author = {Yun Wang and Tong Zhang and Xueya Zhang and Zhen Cui and Yuge Huang and Pengcheng Shen and Shaoxin Li and Jian Yang},
  title = {{Wasserstein Coupled Graph Learning for Cross-Modal Retrieval}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2021},
  doi = {10.1109/iccv48922.2021.00183},
}
Figure