1. A computer-implemented method comprising: receiving, at a computer system, user information associated with users of a social network and associated with media accessed by the users; generating, by the computer system, a graph that links first representations of the users and second representations of the media based on relationships derived from the user information, wherein the first representations and the second representations comprise nodes in the graph that are linked by edges; selecting one or more advertising labels that are descriptive of one or more advertisements; iteratively propagating values for the one or more advertising labels among the first representations of the users and the second representations of the media using the graph that links the first representations and the second representations; and identifying an advertisement to provide in association with a particular representation based, at least in part, on magnitudes of one or more advertising label values for the particular representation that were determined by the iterative propagation, wherein the magnitudes of the one or more advertising label values indicate how likely a user is to select one or more corresponding advertisements, wherein the particular representation comprises a representation of a particular video, and wherein the advertisement is selected for presentation in a document that includes the particular video.