The task of relevance search is to find relevant items to some given queries, which can be viewed either as an information retrieval problem or as a semi-supervised learning problem. In order to combine both of their advantages, we develop a new relevance search method using label diffusion on bipartite graphs. And we propose a heat diffusion-based algorithm, namely bipartite label diffusion (BLD). Our method yields encouraging experimental results on a number of relevance search problems.