Abstract
This paper investigates the automatic categorization of ambiguous Russian web search results using graph-based word sense induction. By constructing co-occurrence graphs from large-scale text corpora and applying algorithms such as Hyperlex and Curvature, the study demonstrates a method for identifying distinct query senses—such as distinguishing between a river, a sports club, and a mythological figure—without the need for pre-defined dictionaries. The research highlights the effectiveness of distributional semantics in bridging the "vocabulary gap" inherent in sparse search snippets.
Introduction
Search engine queries are frequently ambiguous. A search for "максим" (Maxim) could refer to a pop singer, a men's magazine, or a common first name. While modern search engines aim for diversity in results, they typically rank by relevance rather than grouping by semantic meaning.
Traditional clustering often fails because search snippets are too sparse; two results about the same entity might not share any words besides the query itself. This paper addresses this challenge by using external linguistic data to build a bridge between related terms, enabling more robust semantic clustering through graph-based expansion.
Methodology
The approach is rooted in distributional semantics, where a word's meaning is defined by its context. The process involves three stages:
- Global Co-occurrence Graph: A massive network is built where nodes represent nouns and edges represent co-occurrence frequency in a large corpus, weighted by the Dice coefficient.
- Query Graph Construction: For a specific query, a sub-graph is created using words from search results and their strong neighbors from the global graph, expanding the context of sparse snippets.
- Graph Partitioning: Two algorithms are compared for sense induction: Curvature, which identifies and removes "bridge" words with low clustering coefficients, and Hyperlex, which identifies highly connected "hubs" to generate a maximum spanning tree.
Data Analysis
The study utilized several Russian corpora, including the Open Corpora (OC), the Russian National Corpus (RNC), and a Query Corpus (QC) from Mail.ru.
As shown in Table 1, the linguistic graphs exhibit "small world" properties, characterized by high clustering coefficients and short average path lengths. Interestingly, the larger Query Corpus (QC) proved less effective than the smaller "Mix" corpus. The data reveals that QC is significantly sparser, with an average degree of only 6.8 compared to 24.7 for the Mix corpus, explaining the lower reliability of its co-occurrence data.
Key Insights
- Small World Property: The natural formation of dense clusters with short paths between nodes is what makes graph-based sense induction possible, as these clusters correspond to distinct word meanings.
- Functional Uses vs. Semantic Senses: The algorithms often identify "typical environments" or practical uses rather than strict dictionary definitions. For a search user, separating "Hockey club" from "River" is more useful than a purely lexicographical distinction.
Results
Performance was evaluated against the Analyzethis gold standard for Russian search queries. Hyperlex consistently outperformed Curvature, showing a lower average deviation from the expected number of clusters.
Qualitatively, the system successfully isolated four distinct clusters for the query "Amur": the God of Love, the Movie, the Hockey Club, and the River. Figure 1 illustrates how these disparate senses form separate regions within the expanded query graph, with nodes like "хоккей" (hockey) and "река" (river) anchoring their respective clusters.
Conclusion
While the current evaluation is limited to the number of clusters rather than their content, the results demonstrate the potential of graph-based methods for search result diversification. Future work will focus on including compound phrases, exploring second-order co-occurrences, and conducting human evaluations to assess the practical utility of the clusters for end-users.
Summary updated