Methods, systems, and apparatus, including computer programs encoded on computer storage media, for clustering query refinements. One method includes building a representation of a graph for a first query, wherein the graph has a node for the first query, a node for each of a plurality of refinements for the first query, and a node for each document in the document sets of the refinements, and wherein the graph has edges from the first query node to each of the refinement nodes, edges from the first query to each document in the respective document set of the first query, edges from each refinement to each document in the respective document set of the refinement, and edges from each refinement to each co-occurring query of the refinement. The method further includes clustering the refinements into refinement clusters by partitioning the refinement nodes in the graph into proper subsets.