1. A method at least partially implemented by a computing device, the method comprising: determining, using bipartite graph reinforcement modeling, a set of annotations relevant to a Web image, wherein determining the set of annotations comprises: generating initial candidate annotations for the Web image; ranking relevancy of the initial candidate annotations to the Web image using a first ranking algorithm, the first ranking algorithm comprising obtaining a first initial candidate annotation ranking and a second initial candidate annotation ranking for each initial candidate annotation and fusing the first initial candidate annotation ranking and the second initial candidate annotation ranking using a weighted linear combination scheme; identifying, using the initial candidate annotations, extending candidate annotations by submitting each word and corresponding image associated with the initial candidate annotations as a respective query to an image search engine to receive search results and clustering the search results in view of the initial candidate annotations to obtain cluster names, the extending candidate annotations comprising the cluster names; ranking relevancy of the extending candidate annotations using a second ranking algorithm that is different than the first ranking algorithm by determining an average similarity between images in a cluster and the Web image and weighting the average similarity with textual information associated with the cluster name, the cluster corresponding to the cluster name; identifying, at least partially in view of relevancy rankings of the initial candidate annotations and the extending candidate annotations, relationships between two disjoint sets of vertices in a bipartite graph, a first set of the two disjoint sets of vertices representing the initial candidate annotations, a second set of the two disjoint sets of vertices representing the extending candidate annotations; re-ranking the initial candidate annotations and the extending candidate annotations based on the relationships between the two disjoint sets of vertices in the bipartite graph; annotating the Web image based on the re-ranked initial candidate annotations and the extending candidate annotations; and providing the Web image to an indexing service for indexing and presentation of relevant search results to a user search query, the relevant search results being based on at least a subset of the annotations.