Clustering query refinements by user intent

Eldar Sadikov, Jayant Madhavan, Lu Wang, Alon Y. HalevyWWW 2010 · DOI

TL;DR

This paper tackles the challenge of organizing related search queries (refinements) to better understand user intent. They propose a novel Markov model that combines document click data and session co-occurrence information, outperforming existing methods in a user study by providing more coherent and representative clusters.

What Problem Does This Paper Address?

When users search on engines like Google, they often see "related searches" or "refinements" that help them narrow down their information needs. However, search engines typically only display a handful of these, and choosing the right ones is crucial for a good user experience. The problem is that a single query can have many different underlying user intents (e.g., "mars" could mean the planet, the Roman god, or the candy bar). Existing methods for clustering these refinements often rely on either just document clicks or just session co-occurrences, leading to suboptimal groupings that don't fully capture the diverse intents. This paper aims to create clusters that better represent distinct user intents, improving the selection and placement of query suggestions.

Methods

The core of the proposed method is a graph-based approach that models user search behavior. This graph connects the original query, its refinements, and the documents clicked by users. The key innovation is treating this graph as an absorbing Markov model.

Here's a breakdown:

  • Graph Construction: Nodes represent the query, its refinements, and clicked documents. Edges represent transitions: query to refinement, refinement to clicked document, and refinement to other co-occurring refinements within sessions. Edge weights are derived from click frequencies and session co-occurrence frequencies.
  • Markov Model Interpretation: The graph is normalized into a transition probability matrix. The "absorbing states" are the clicked documents, meaning once a user reaches a document, they are considered to have satisfied their intent for that path. Refinement nodes are "transient states."
  • Absorption Distributions: The algorithm computes the "absorption distribution" for each refinement. This is essentially a vector representing the probability that a random walk starting from that refinement will end up in each of the absorbing document states. This vector captures the user's likely intent associated with that refinement.
  • Clustering: Refinements are clustered based on the similarity of their absorption distribution vectors. The paper uses complete-link clustering with cosine similarity for this step, which they found to be effective in avoiding issues like "chaining" (where a long chain of similar items can lead to unrelated items being grouped).
  • Off-Topic Drift Modeling: A novel addition is the inclusion of an "off-topic" absorbing state. This allows the model to account for users who might abandon their current search intent and switch to something unrelated, which is a common real-world behavior.

Datasets

The study used six months of anonymized search query logs from Google.com. They filtered queries to include those with at least 80 refinements and limited the number of refinements and clicked documents considered per query to 80 and 15, respectively, to manage dimensionality and focus on the most relevant information.

Key Insights and Ideas

  • Combining Data Sources is Key: The paper strongly suggests that combining document click data (which captures semantic similarity) with session co-occurrence data (which captures sequential user behavior) leads to richer and more accurate intent clustering than using either source alone.
  • Markov Models for User Intent: Framing user search behavior as an absorbing Markov model provides a principled way to quantify the "intent" associated with a query refinement through its absorption distribution.
  • Off-Topic Drift Matters: Explicitly modeling the possibility of users abandoning an intent and going "off-topic" significantly improves the robustness and accuracy of the clustering.
  • Complete-Link Clustering is Suitable: For this specific problem, complete-link clustering, despite its potential to be sensitive to outliers, proved effective in creating cohesive clusters by requiring all members of a cluster to be similar to each other.

Key Results

  • User Study Dominance: In a user study involving human evaluators, the proposed Markov model (MM) approach was rated significantly higher than document-click (DC) and session-query (SQ) based methods.
  • Reduced Under/Over-Clustering: MM resulted in fewer instances of queries being deemed under-clustered or over-clustered (only 25% combined) compared to DC (44%) and SQ (47%).
  • Better Cluster Groupings: MM was rated as the "best" cluster group for 54% of queries, significantly outperforming DC and SQ.
  • Improved Intent Tracking: The MM approach achieved a higher success rate (81.5%) in tracking user intent within sessions compared to SQ (75.5%) and DC (51.8%).

Limitations and Future Work

  • Ambiguous Queries: The paper acknowledges that detecting and handling ambiguous refinements (e.g., "jaguars" as a refinement for "jaguar") remains a challenge. They propose a heuristic to mitigate this by excluding them initially, but a more robust solution is needed.
  • Parameter Tuning: While the method is not overly sensitive to parameters like epsilon (document escape probability), further exploration of parameter selection for optimal cohesion-coverage trade-offs is suggested.
  • Leveraging Clusters: The paper suggests future work in developing better treatments for ambiguous queries and exploring how these clusters can be used to improve the overall search experience, beyond just query suggestion.

Summary updated

BibTeX
@inproceedings{sadikov2010clustering,
  author = {Eldar Sadikov and Jayant Madhavan and Lu Wang and Alon Y. Halevy},
  title = {{Clustering query refinements by user intent}},
  booktitle = {The Web Conference},
  year = {2010},
  doi = {10.1145/1772690.1772776},
}
Figure