A metadata augmentation system determines similarities between digital objects, such as digital videos, that may or may not have metadata associated with them. Based on the determined similarities, the metadata augmentation system augments metadata of objects, such as augmenting metadata of objects lacking a sufficient amount of metadata with metadata from other objects having a sufficient amount of metadata.In one embodiment, the similarities are used to determine training sets for training of classifiers that output degrees of more specific similarities between the corresponding video and an arbitrary second video. These classifiers are then applied to add metadata from one video to another based on a degree of similarity between the videos, regardless of their respective locations within the object similarity graph.