Methods, systems, and apparatus, including computer programs encoded on computer storage media, for providing video recommendations. For each video in a set of videos, a set of images included in the video are obtained. For each respective image in the set of images for a video, a set of one or more keywords that describe visual content depicted by the respective image is generated. Based at least on the sets of one or more keywords for at least some of the images, a set of keywords that describe the video is generated. The videos are assigned to groups based on the set of keywords generated for each video. A request is received for a video recommendation based on a first video. Data identifying a second video are provided as the video recommendation based on the second video being assigned to a same group as the first video.