A method for expanding a query to include additional terms associated through visual content is provided. A bipartite graph is constructed based on a database of visual content and associated textual content. One partition of the bipartite graph contains visual content and the other partition of the bipartite graph contains textual content. Weighted edges between nodes in the two partitions represent associations between the visual content and textual content in the database. Random walks on the bipartite graph are performed to derive probabilistic association scores between textual content that are indirectly associated with each other through visual content. The query is expanded to include additional terms whose equivalent textual content is highly associated with the query's equivalent textual content.