Abstract: Search engine has become an essential way for satisfying users’ daily information needs, however, formulating a proper query for search is difficult for users. To alleviate users’ search burden, query recommendation has been proposed and considered as a prominent ingredient of modern search engines. Traditional recommendation approaches have paid great attention to recommend relevant queries, which attempt to find alternative queries with close search intent to the original query. However, the ultimate goal of query recommendation is to assist users to accomplish their search task successfully, while not just find relevant queries in spite of they can sometimes produce useful search results. To better match user search objective in the real world, a more straight way of query recommendation is to recommend users high utility query, i.e., queries that can better satisfy users’ information needs. In this paper, we propose a two-step utility query recommendation method based on absorbing random walk, which can infer query’s utility by simultaneously modeling both users’ reformulation behaviors and click behaviors. Extensively experiments are conducted on a real query log, and the results show that this method significantly outperforms five baseline methods under the evaluation metric query relevant ratio (QRR) and mean relevant document (MRD).