  Existing video-language studies mainly focus on learning short video clips,
leaving long-term temporal dependencies rarely explored due to over-high
computational cost of modeling long videos. To address this issue, one feasible
solution is learning the correspondence between video clips and captions, which
however inevitably encounters the multi-granularity noisy correspondence (MNC)
problem. To be specific, MNC refers to the clip-caption misalignment
(coarse-grained) and frame-word misalignment (fine-grained), hindering temporal
learning and video understanding. In this paper, we propose NOise Robust
Temporal Optimal traNsport (Norton) that addresses MNC in a unified optimal
transport (OT) framework. In brief, Norton employs video-paragraph and
clip-caption contrastive losses to capture long-term dependencies based on OT.
To address coarse-grained misalignment in video-paragraph contrast, Norton
filters out the irrelevant clips and captions through an alignable prompt
bucket and realigns asynchronous clip-caption pairs based on transport
distance. To address the fine-grained misalignment, Norton incorporates a
soft-maximum operator to identify crucial words and key frames. Additionally,
Norton exploits the potential faulty negative samples in clip-caption contrast
by rectifying the alignment target with OT assignment to ensure precise
temporal modeling. Extensive experiments on video retrieval, videoQA, and
action segmentation verify the effectiveness of our method. Code is available
at https://lin-yijie.github.io/projects/Norton.
