Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for training an image embedding model. In one aspect, a method comprises: obtaining training data comprising a plurality of training examples, wherein each training example comprises: an image pair comprising a first image and a second image; and selection data indicating one or more of: (i) a co-click rate of the image pair, and (ii) a similar-image click rate of the image pair; and using the training data to train an image embedding model having a plurality of image embedding model parameters.