# Space-Time Correspondence as a Contrastive Random Walk

arXiv: https://arxiv.org/abs/2006.14613 · HTML: https://mlsanity.com/paper/2006.14613/

## Key facts

- Cited by 239 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2020.

## Built on by (most cited first, 30 of 239)

- [Emerging Properties in Self-Supervised Vision Transformers](https://mlsanity.com/paper/2104.14294/) (2021)
- [Objaverse: A Universe of Annotated 3D Objects](https://mlsanity.com/paper/2212.08051/) (2022)
- [R3M: A Universal Visual Representation for Robot Manipulation](https://mlsanity.com/paper/2203.12601/) (2022)
- [Putting NeRF on a Diet: Semantically Consistent Few-Shot View Synthesis](https://mlsanity.com/paper/2104.00677/) (2021)
- [Emergent Correspondence from Image Diffusion](https://mlsanity.com/paper/2306.03881/) (2023)
- [Perception Encoder: The best visual embeddings are not at the output of the network](https://mlsanity.com/paper/2504.13181/) (2025)
- [PointOdyssey: A Large-Scale Synthetic Dataset for Long-Term Point Tracking](https://mlsanity.com/paper/2307.15055/) (2023)
- [TAP-Vid: A Benchmark for Tracking Any Point in a Video](https://mlsanity.com/paper/2211.03726/) (2022)
- [Conditional Object-Centric Learning from Video](https://mlsanity.com/paper/2111.12594/) (2021)
- [Masked Visual Pre-training for Motor Control](https://mlsanity.com/paper/2203.06173/) (2022)
- [MOSE: A New Dataset for Video Object Segmentation in Complex Scenes](https://mlsanity.com/paper/2302.01872/) (2023)
- [Keeping Your Eye on the Ball: Trajectory Attention in Video Transformers](https://mlsanity.com/paper/2106.05392/) (2021)
- [Self-Supervised Pretraining of 3D Features on any Point-Cloud](https://mlsanity.com/paper/2101.02691/) (2021)
- [Particle Video Revisited: Tracking Through Occlusions Using Point Trajectories](https://mlsanity.com/paper/2204.04153/) (2022)
- [A Survey on Self-supervised Learning: Algorithms, Applications, and Future Trends](https://mlsanity.com/paper/2301.05712/) (2023)
- [Tracking Everything Everywhere All at Once](https://mlsanity.com/paper/2306.05422/) (2023)
- [Unsupervised Semantic Segmentation by Contrasting Object Mask Proposals](https://mlsanity.com/paper/2102.06191/) (2021)
- [Motion Prompting: Controlling Video Generation with Motion Trajectories](https://mlsanity.com/paper/2412.02700/) (2024)
- [Recurrent Video Restoration Transformer with Guided Deformable Attention](https://mlsanity.com/paper/2206.02146/) (2022)
- [SAVi++: Towards End-to-End Object-Centric Learning from Real-World Videos](https://mlsanity.com/paper/2206.07764/) (2022)
- [Efficient Visual Pretraining with Contrastive Detection](https://mlsanity.com/paper/2103.10957/) (2021)
- [Towards Long-Form Video Understanding](https://mlsanity.com/paper/2106.11310/) (2021)
- [Layered Neural Atlases for Consistent Video Editing](https://mlsanity.com/paper/2109.11418/) (2021)
- [A Survey on Deep Learning Technique for Video Segmentation](https://mlsanity.com/paper/2107.01153/) (2021)
- [CoTracker3: Simpler and Better Point Tracking by Pseudo-Labelling Real Videos](https://mlsanity.com/paper/2410.11831/) (2024)
- [How to represent part-whole hierarchies in a neural network](https://mlsanity.com/paper/2102.12627/) (2021)
- [BootsTAP: Bootstrapped Training for Tracking-Any-Point](https://mlsanity.com/paper/2402.00847/) (2024)
- [V-JEPA 2.1: Unlocking Dense Features in Video Self-Supervised Learning](https://mlsanity.com/paper/2603.14482/) (2026)
- [CoDeF: Content Deformation Fields for Temporally Consistent Video Processing](https://mlsanity.com/paper/2308.07926/) (2023)
- [SiT: Self-supervised vIsion Transformer](https://mlsanity.com/paper/2104.03602/) (2021)

## Abstract (arXiv)

This paper proposes a simple self-supervised approach for learning a representation for visual correspondence from raw video. We cast correspondence as prediction of links in a space-time graph constructed from video. In this graph, the nodes are patches sampled from each frame, and nodes adjacent in time can share a directed edge. We learn a representation in which pairwise similarity defines transition probability of a random walk, so that long-range correspondence is computed as a walk along the graph. We optimize the representation to place high probability along paths of similarity. Targets for learning are formed without supervision, by cycle-consistency: the objective is to maximize the likelihood of returning to the initial node when walking along a graph constructed from a palindrome of frames. Thus, a single path-level constraint implicitly supervises chains of intermediate comparisons. When used as a similarity metric without adaptation, the learned representation outperforms the self-supervised state-of-the-art on label propagation tasks involving objects, semantic parts, and pose. Moreover, we demonstrate that a technique we call edge dropout, as well as self-supervised adaptation at test-time, further improve transfer for object-centric correspondence.