Accepted at ICTIR ’16: International Conference on the Theory of Information Retrieval [1].

Abstract. We present a framework for discovering sets of web queries having similar latent needs, called search tasks, from user queries stored in a search engine log. Our solution is made of two components: a Query Similarity Learning (QSL) module and a Graph-based Query Clustering (GQC) module. The former is devoted to learning a query similarity function from a ground truth of manually-labeled search tasks. The latter represents each user search log as a graph whose nodes are queries, and uses the learned similarity function to weight edges between query pairs. Finally, search tasks are detected by clustering those queries in the graph which are connected by the strongest links, in fact by detecting the strongest connected components of the graph. To discriminate between “strong” and “weak” links also the GQC module entails a learning phase whose goal is to estimate the best threshold for pruning the edges of the graph. We discuss how the GSL module can be effectively implemented using Learning to Rank (L2R) techniques. Experiments on a real-world search engine log show that query similarity functions learned using L2R lead to better performing GQC implementations when compared to similarity functions induced by other state-of-the-art machine learning solutions, such as logistic regression and decision trees.