1. A method implemented by data processing apparatus, the method comprising: obtaining a search query; selecting one or more candidate refinement queries, wherein selecting one or more candidate refinement queries comprises: selecting one or more terms from training data as candidate refinement queries, wherein a respective right context of each of the selected terms in the training data includes at least one word in a right context of the search query, and wherein a respective left context of each of the selected terms in the training data includes at least one word in a left context of the search query; determining one or more categories for the search query; determining one or more categories for each of the candidate refinement queries; determining a respective first score for each of the candidate refinement queries, wherein determining the respective first score for the candidate refinement query comprises adjusting the respective first score for the candidate refinement query based on a number of categories shared between the candidate refinement query and the search query; and identifying as query refinements for the search query one or more of the candidate refinement queries based on the first scores.