The rapid growth of the number of videos on the Internet provides enormous potential for users to find content of interest to them. Video search, such as Google, Youtube, Bing, is a popular way to help users to find desired videos. However, it is still very challenging to discover new video contents for users. In this paper, we address the problem of providing personalized video suggestions for users. Rather than only exploring the user-video graph that is formulated using the click-through information, we also investigate other two useful graphs, the user-query graph indicating if a user ever issues a query, and the query-video graph indicating if a video appears in the search result of a query. The two graphs act as a bridge to connect users and videos, and have a large potential to improve the recommendation as the queries issued by a user essentially imply his interest. As a result, we reach a tripartite graph over (user, video, query). We develop an iterative propagation scheme over the tripartite graph to compute the preference information of each user. Experimental results on a dataset of 2,893 users, 23,630 queries and 55,114 videos collected during Feb. 2011 demonstrate that the proposed method outperforms existing state-of-the-art approaches, co-views and random walks on the user-video bipartite graph.