Labeling Samples in a Similarity Graph

Particular embodiments of a social-networking system maintain one or more data stores storing a social graph comprising user nodes, concept nodes, and edges connecting the nodes. Particular embodiments may determine a confidence score with respect to a user node and a concept node, wherein the confidence score is based at least in part on affinity scores associated with the edges along a sequence of nodes between the user node and the concept node in the social graph. The confidence score may be based on an overall probability that a random walk starting at the user node will end at the concept node. This overall probability may be determined by calculating, for each edge in the random walk, the probability of taking that edge during the random walk, based on the affinity score associated with that edge.