Semantic Clustering of Russian Web Search Results: Possibilities and Problems

Andrey Kutuzov

TL;DR

This paper explores how to automatically group ambiguous Russian web search results into meaningful categories using graph-based word sense induction. By building co-occurrence graphs from large text corpora and applying algorithms like Hyperlex and Curvature, the author demonstrates a way to "understand" different query senses (e.g., distinguishing a singer from a magazine) without relying on pre-defined dictionaries.

What Problem Does This Paper Address?

Search engine queries are notoriously ambiguous. A user searching for "максим" (Maxim) might be looking for a popular pop singer, a men's magazine, an electronic library, or a common first name. While search engines try to provide a diverse set of results, these results are typically ranked by relevance rather than grouped by meaning.

The challenge is that search "snippets" (the short text previews) are often too sparse for traditional clustering. Two snippets about the same singer might not share a single common word other than the query itself. Conversely, snippets for different senses might share generic words like "author." This paper tackles the "vocabulary gap" by using external linguistic data to build a bridge between related terms, allowing for more robust semantic clustering.

Methods

The author follows a distributional semantics approach: the meaning of a word is defined by the company it keeps. The workflow consists of three main stages:

  1. Building a Global Co-occurrence Graph: The author creates a massive network where nodes are nouns (lemmas) and edges represent how often they appear near each other in a large corpus. The "strength" of these connections is measured using the Dice coefficient.
  2. Constructing a Query Graph ($G_q$): For a specific search query, a smaller graph is built using words found in the search results plus their "strong neighbors" from the global graph. This effectively "expands" the context of the sparse snippets.
  3. Graph Partitioning (Word Sense Induction): To find the distinct senses, the author compares two algorithms:
  4. Curvature: This identifies "bridge" words that have a low clustering coefficient (meaning they link disparate groups) and deletes them to break the graph into separate components.
  5. Hyperlex: This identifies "hubs" (highly connected nodes), generates a maximum spanning tree, and then splits that tree into subtrees rooted at those hubs.

Finally, individual search results are mapped to these induced senses based on the overlap of lemmas.

Datasets

The study utilized three primary Russian corpora to build the co-occurrence graphs:

  • Open Corpora (OC): 1 million tokens of various texts under free licenses.
  • Russian National Corpus (RNC): A 1-million-token disambiguated fragment.
  • Query Corpus (QC): 2 million tokens of random search queries from the Mail.ru search engine.
  • Mix Corpus: A combination of OC and RNC (approx. 0.8 million tokens after preprocessing).

For evaluation, the author used Analyzethis, a Russian search engine evaluation initiative that provides a "gold standard" for how many senses should exist for specific ambiguous queries.

Key Insights and Ideas

  • The "Small World" Property: The linguistic graphs naturally formed "small world" networks—dense clusters with short paths between any two nodes. This structure is what makes graph-based sense induction possible, as these clusters correspond to distinct word meanings.
  • Sparsity vs. Density: Interestingly, the larger Query Corpus (QC) performed worse than the smaller Mix Corpus. The author attributes this to the fact that search queries are naturally short and "less dense," leading to fewer edges and less reliable co-occurrence data compared to full natural language sentences.
  • "Uses" vs. "Senses": The author notes that these algorithms often find "typical environments" or "uses" rather than strict dictionary definitions. For example, it might separate "Hockey club" from "River" for the query "Amur." While a lexicographer might see these as related, for a search user, they represent distinct intents.

Key Results

The performance was measured by how closely the number of clusters generated by the algorithm matched the "gold standard" from Analyzethis:

  • Algorithm Performance: Hyperlex consistently outperformed Curvature. On the "Mix" corpus, Hyperlex had an average deviation of 49% from the gold standard, while Curvature deviated by 61%.
  • Corpus Performance: The "Mix" corpus (academic/literary texts) proved superior to the "Query" corpus across both algorithms.
  • Qualitative Success: The paper provides a visual example of the query "Amur," where the system successfully isolated four distinct clusters: the God of Love, the Movie, the Hockey Club, and the River.

Limitations and Future Work

The primary limitation acknowledged is the evaluation metric. Currently, the author only evaluates the number of clusters, not the content of those clusters, due to a lack of manually labeled Russian datasets for this specific task.

Future directions suggested by the author include:

  • Moving beyond single nouns to include compound phrases.
  • Experimenting with "second-order" co-occurrences (neighbors of neighbors) to further combat data sparsity.
  • Conducting full-scale human evaluations to judge the actual quality and usefulness of the resulting clusters for end-users.

Summary updated

BibTeX
@inproceedings{kutuzov2014semantic,
  author = {Andrey Kutuzov},
  title = {{Semantic Clustering of Russian Web Search Results: Possibilities and Problems}},
  booktitle = {Russir},
  year = {2014},
  doi = {10.1007/978-3-319-25485-2\_12},
}
Figure