Systems and methods for bipartite graph reinforcement modeling to annotate web images are described. In one aspect the systems and methods implement bipartite graph reinforcement modeling operations to identify a set of annotations that are relevant to a Web image. The systems and methods annotate the Web image with the identified annotations. The systems and methods then index the annotated Web image. Responsive to receiving an image search query from a user, wherein the image search query comprises information relevant to at least a subset of the identified annotations, the image search engine service presents the annotated Web image to the user.