Source-linked AI summary
Graph Optimal Transport for Cross-Domain Alignment
Liqun Chen, Zhe Gan, Yu Cheng, Linjie Li, Lawrence Carin, Jingjing Liu
TL;DR
Cross-domain alignment lacks explicit training signals because paired entities are available without ground-truth relations, limiting the supervision of attention-based approaches. GOT formulates alignment as graph matching with Wasserstein and Gromov-Wasserstein distances and uses the resulting distance as a regularizer. Experiments report consistent performance enhancement over strong baselines across five diverse tasks, while the method's node-matching and edge-matching components have distinct limitations.
Problem
Cross-domain alignment is weakly supervised: paired entity spaces are given, but ground-truth relations and an explicit alignment objective are absent.
Method
GOT dynamically represents entities as graphs, formulates alignment as graph matching, and combines Wasserstein distance for nodes with Gromov-Wasserstein distance for edges as a regularizer.
Results
GOT provides consistent performance enhancement over strong baselines across image-text retrieval, visual question answering, image captioning, machine translation, and text summarization.
Takeaways & Limitations
The framework is presented as a generic cross-domain alignment method applicable to a wide range of tasks, with alignment enforcement serving as an effective training regularizer.
Takeaways & Limitations
Wasserstein distance cannot capture edge similarity, whereas Gromov-Wasserstein distance cannot be directly applied to graph alignment without addressing its matching limitations.
Abstract
from arXiv · showhide
Cross-domain alignment between two sets of entities (e.g., objects in an image, words in a sentence) is fundamental to both computer vision and natural language processing. Existing methods mainly focus on designing advanced attention mechanisms to simulate soft alignment, with no training signals to explicitly encourage alignment. The learned attention matrices are also dense and lacks interpretability. We propose Graph Optimal Transport (GOT), a principled framework that germinates from recent advances in Optimal Transport (OT). In GOT, cross-domain alignment is formulated as a graph matching problem, by representing entities into a dynamically-constructed graph. Two types of OT distances are considered: (i) Wasserstein distance (WD) for node (entity) matching; and (ii) Gromov-Wasserstein distance (GWD) for edge (structure) matching. Both WD and GWD can be incorporated into existing neural network models, effectively acting as a drop-in regularizer. The inferred transport plan also yields sparse and self-normalized alignment, enhancing the interpretability of the learned model. Experiments show consistent outperformance of GOT over baselines across a wide range of tasks, including image-text retrieval, visual question answering, image captioning, machine translation, and text summarization.
1. Introduction
Cross-domain alignment is central to tasks spanning vision and language, yet weak supervision leaves entity relations unspecified and attention-based methods lack an explicit alignment objective. GOT addresses this by framing alignment as graph matching with Optimal Transport distances and serving as a regularizer across diverse tasks.
- Motivation: Cross-domain alignment associates related entities across domains and supports image-text retrieval, visual question answering, and machine translation.Models must identify entities, represent intra- and cross-domain relations, and measure alignment quality.
- Motivation: Weak supervision provides paired entity spaces but no ground-truth relations, while prior methods mainly use attention mechanisms to simulate soft alignment.The training objective therefore lacks an explicit signal encouraging cross-domain alignment.
- Graph Optimal Transport: GOT represents entities as dynamically updated graphs and formulates cross-domain alignment as a graph matching problem.Each entity is represented by a feature vector, and graph edges are constructed from thresholded within-domain similarities.
- Graph Optimal Transport: Wasserstein distance matches graph nodes, while Gromov-Wasserstein distance captures edge structure, allowing GOT to model both entity and relational information.Combining the two distances supports graph matching using node and edge information.
- Empirical Scope: GOT is compatible with existing neural networks as a drop-in regularizer and improves performance consistently over strong baselines across five cross-domain tasks.The evaluated tasks are image-text retrieval, visual question answering, image captioning, machine translation, and text summarization.
2. Graph Optimal Transport Framework
The GOT framework formulates cross-domain alignment as dynamic graph matching and regularizes neural models with optimal-transport distances. Wasserstein distance matches nodes, while Gromov-Wasserstein distance matches within-domain structure through a shared transport plan.
- Problem formulation: Cross-domain alignment is added as an explicit regularization objective alongside the task supervision loss.The regularizer is weighted by a hyper-parameter α and is optimized through gradient back-propagation.
- Dynamic graph construction: Entities are represented as feature-vector nodes in dynamically constructed graphs whose edges connect pairs exceeding a thresholded cosine-similarity cost.The graphs evolve as model parameters update, making alignment a graph matching problem.
- Graph matching via OT distances: Optimal Transport learns a self-normalized and potentially sparse transport plan, supporting more interpretable cross-domain alignment.The exact solution has at most 2r − 1 non-zero elements, where r = max(n, m).
- Graph matching via OT distances: Wasserstein distance measures cross-domain node discrepancies, whereas Gromov-Wasserstein distance compares within-domain pairwise relations for edge matching.WD directly compares node samples across domains; GWD compares distances between node pairs and their counterparts.
- Graph matching via OT distances: GOT combines node and structural costs through a unified objective and uses one transport plan to match nodes and edges simultaneously.The shared plan is reported as better and faster than using two separate transport plans because it is solved only once.
3. Related Work
Prior work applies optimal-transport distances, graph neural networks, and graph matching to learning tasks, while GOT provides algorithms for combining these components.
- Optimal Transport: Optimal Transport has been applied to vision, language, generative modeling, and vision-language pre-training, while Gromov-Wasserstein distance supports distributional metric matching and unsupervised machine translation.
- GOT Distance: Algorithm 3 computes GOT distance by forming intra- and cross-domain similarities, optionally updating a unified loss, and returning Dgot.
- Optimal Transport: Linear-programming OT solvers are nondifferentiable, motivating differentiable approximations such as WGAN’s restricted dual formulation and the Sinkhorn algorithm.
- Graph Neural Network: Graph neural networks evolved from recurrent graph models to scalable normalized graph convolutions and graph attention networks using learned weights and masked neighborhood aggregation.
- Graph Matching: Graph matching networks use masked intra-graph attention, cross-graph soft attention, and task-specific losses, with adjacency matrices obtained directly from data in that setting.
4. Experiments
Experiments evaluate GOT across vision-and-language and text-generation tasks, showing performance gains, interpretable alignments, and modest computational overhead. Ablations indicate that combining node- and edge-level matching is most effective, while shared transport plans improve both performance and training efficiency.
- Experimental scope: GOT is evaluated on image-text retrieval, visual question answering, image captioning, machine translation, and abstractive summarization.The experiments use diverse vision-and-language and text-generation benchmarks.
- Vision-and-Language Tasks: Both WD and GWD improve SCAN on image-text retrieval, while combining them achieves the best performance.WD provides a larger standalone margin than GWD, suggesting that GWD alone is less effective for graph alignment.
- Vision-and-Language Tasks: GOT produces a sparser and less noisy transport plan than SCAN’s attention matrix, making image-text alignments more interpretable.The visualization uses image regions on the horizontal axis and word tokens on the vertical axis; “sidewalk” and “skateboard” align well with corresponding regions.
- Vision-and-Language Tasks: GOT improves BAN on VQA, and BAN-4 with GOT reaches 66.10 accuracy versus 66.00 for BAN-8 without GOT.The improvement is more significant for smaller models, while gains remain measurable for complex architectures.
- Text Generation Tasks: 107.9−106.3 = 81.25% relative performance boost from WD to GOT on CIDEr for image captioning.The additional GWD is attributed to modeling implicit intra-domain relationships in images and captions.
- Text Generation Tasks: Combining WD and GWD achieves the best machine-translation performance, whereas GWD alone lowers test BLEU and WD alone improves Transformer sequence-to-sequence learning.GWD complements WD by capturing graph information that node matching may miss, while GWD alone ignores node representations.
- Text Generation Tasks: Both GWD and WD improve abstractive summarization, whose learned source-output transport plan is sparse and interpretable.The output words “more” and “investment” align well with the source sentence.
- Ablation study: A shared transport plan outperforms an unshared plan and saves training time because the Sinkhorn algorithm runs only once.For image-text retrieval, SCAN training takes 6hr 34min versus 6hr 57min for SCAN+GOT.
5. Conclusions
Graph Optimal Transport provides a principled framework for cross-domain alignment using Wasserstein and Gromov-Wasserstein distances. Experiments support its use as a generic alignment regularizer across diverse cross-domain tasks.
- GOT captures both intra-domain and cross-domain relations through Wasserstein and Gromov-Wasserstein distances.
- Enforcing alignment serves as an effective regularizer for model training.
- Extensive experiments show that GOT applies generically across a wide range of cross-domain tasks.