1. A computing device with a processor and memory for training a document ranking component, comprising: a training data store that contains training data including representations of documents and, for each query of a plurality of queries, a labeling of some of the documents with relevance of the documents to the query; a graph component that creates a graph of the documents with the documents represented as nodes being connected by edges representing similarity between documents including a build graph component that builds a graph in which nodes representing similar documents are connected via edges, such that each node has an edge to a number of other nodes that are most similar to it; and a generate weights component that generates weights for the edges based on similarity of the documents represented by the connected nodes, each document being represented by a feature vector in a feature space, the similarity between two documents being calculated based on a metric derived from the feature vectors representing the two documents; and a propagate relevance component that propagates relevance of the labeled documents to the unlabeled documents based on similarity between documents as indicated by the weights generated for the edges; a training component that trains a document ranking component to rank relevance of documents to queries based on the propagated relevance of the documents of the training data; and a search component that, after the document ranking component is trained, receives a query, identifies documents relating to the query, and ranks the identified documents using the document ranking component that was trained based on the propagated relevance of the documents of the training data wherein the components comprise computer-executable instructions stored in memory for execution by the processor.