Graph Learning for Exploratory Query Suggestions in an Instant Search System

October 25, 2023 Published by Enrico Palumbo, Andreas Damianou, Francesco Fabbri, Hugues Bouchard, Mounia Lalmas

Graph Learning for Exploratory Query Suggestions in an Instant Search System

Spotify’s search system plays a vital role in helping users explore the catalog and discover new content. Exploratory searches such as “new funk soul releases” or “guitar solos to learn” provide an opportunity for users to find their next favorite song and for the platform to surface under-served content [1]. Query suggestion services such as Related Searches help users formulate effective queries and are extremely useful in exploratory search, where the discovery process often requires several iterations of query formulation. For example, imagine that the user is looking for music to stream during a yoga session. The user initially types a generic ‘yoga’ query, but after seeing the query suggestions, the user opts for ‘vinyasa’ and finally refines the intent with ‘vinyasa flow’. 

Related Searches help users navigate the catalog by recommending related queries that facilitate the exploration process, leading to discovery and more effective searches.

Graph Learning for Query Suggestions

To facilitate exploratory searches through query suggestions, we developed a graph learning approach. Graphs are ideal structures for modeling connections and associations, and they can easily encompass heterogeneous data such as queries, items, topics, musical genres. Graph learning methods learn patterns in these structures and encode them into vectors that can effectively be used for recommendation via nearest neighbor search. In this work, we use node2vec [2] to learn the graph structure and the vectorial representations.

Graph Learning algorithms (e.g. node2vec) learn patterns in graph structures and encode them in a vector space. Then, query recommendations can be obtained by finding the nearest neighbors to the user query.

We observed in offline experiments that the graph learning solution node2vec produces accurate query suggestions (+22% with respect to the best baseline, i.e. a transformer model based on semantic similarity), while keeping a high level of diversity, which is critical to allow users to inspect different exploration paths.

Hence, we ran an A/B test experiment with this model on millions of users where the node2vec model was added as a new source of query suggestions. The results showed that this model leads to significant improvements in coverage (+1.42%), and number of clicks on query suggestions (+1.21%), without affecting the overall latency of the system. We observe an especially marked increase for clicks on exploratory queries (+9.37%), proving our hypothesis that the graph learning solution can help exploration through search.


Graphs can connect heterogeneous data (e.g. queries, songs, artists, podcasts, topics, musical genres), facilitating associations that support exploratory searches. Graph Learning allows one to easily create graph-based recommender systems by mapping graph patterns into a vector space. We developed a query suggestion model based on graph learning and prove that it helps exploratory searches in a large-scale online experiment. We believe that these results prove the potential of graph-based methods for search and many other core products at Spotify and elsewhere.

For more information, please refer to our paper:

Graph Learning for Exploratory Query Suggestions in an Instant Search System
Enrico Palumbo, Andreas Damianou, Alice Wang, Alva Liu, Ghazal Fazelnia, Francesco Fabbri, Rui Ferreira, Fabrizio Silvestri, Hugues Bouchard, Claudia Hauff, Mounia Lalmas, Ben Carterette, Praveen Chandar, David Nyhan


[1] Tomasi, Federico, et al. “Query Understanding for Surfacing Under-served Music Content.” CIKM 2020. 
[2]: Grover, Aditya, and Leskovec, Jure. “node2vec: Scalable feature learning for networks.” Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 2016.