16. The system of claim 10 wherein the transformation mechanism is further configured to output a query reformulation graph having nodes representing queries and nodes representing reformulated queries, with each edge between a query node and reformulated query node having a weight that indicates how many times that reformulated query was clicked on following that query, wherein the weight has zero noise, a negative noise or a positive noise added thereto.
17. The system of claim 16 wherein the transformation mechanism is further configured to limit the reformulated queries to those that are returned as the top reformulated queries for each query with respect to a search performed with that query.