Web Page Clustering Using Heuristic Search in the Web Graph

Ron Bekkerman, Shlomo Zilberstein, James Allan

Abstract

Effective representation of Web search results remains an open problem in the Information Retrieval community. For ambiguous queries, a traditional approach is to organize search results into groups (clusters), one for each meaning of the query. These groups are usually constructed according to the topical similarity of the retrieved documents, but it is possible for documents to be totally dissimilar and still correspond to the same meaning of the query. To overcome this problem, we exploit the thematic locality of the Web—relevant Web pages are often located close to each other in the Web graph of hyperlinks. We estimate the level of relevance between each pair of retrieved pages by the length of a path between them. The path is constructed using multi-agent beam search: each agent starts with one Web page and attempts to meet as many other agents as possible with some bounded resources. We test the system on two types of queries: ambiguous English words and people names. The Web appears to be tightly connected; about 70% of the agents meet with each other after only three iterations of exhaustive breadth-first search. However, when heuristics are applied, the search becomes more focused and the obtained results are substantially more accurate. Combined with a content-driven Web page clustering technique, our heuristic search system significantly improves the clustering results.

Introduction

When users search for ambiguous terms like "Jaguar," they may be looking for information on the car, the animal, or the operating system. Traditional clustering methods rely on topical similarity, comparing the vocabulary of different pages. However, this approach often fails when pages have low context (e.g., image galleries) or use divergent terminology (e.g., an academic homepage vs. a personal blog).

This research proposes leveraging the "thematic locality" of the Web. By treating the Web as a graph of hyperlinks, we can identify related pages based on their proximity in the graph, even if they share little common text.

The core of the proposed method is a multi-agent search framework. Each search result is assigned an "agent" that explores the web graph starting from that page. If two agents meet at a common node within a limited number of hops, their starting pages are considered related and clustered together.

The authors introduce two primary algorithms:

  1. Sequential Heuristic Search (SHS): Agents explore the graph and cluster pages based on shared nodes found within a fixed search depth.
  2. Incremental Heuristic Search (IHS): An improved version that starts with "core clusters" and incrementally adds new pages, reducing semantic drift as clusters expand.

The Role of Heuristics

Because the Web is a "small world," exhaustive search quickly leads to the "Adobe/Google problem," where unrelated pages connect via massive hub sites. To maintain precision, the search must be focused.

Comparison between exhaustive breadth-first search (left) and focused heuristic search (right).

Key heuristics include:

  • High-Degree Node Elimination: Pruning nodes with extremely high in-degrees (e.g., google.com).
  • Person Name Heuristic: Using Named Entity Recognition (NER) to identify shared specific names.
  • Anchor Text Heuristic: Prioritizing links whose anchor text suggests a relevant connection.

Experimental Results

The system was evaluated on two datasets: a Web Appearance Disambiguation Dataset (1,085 pages for 12 ambiguous names) and a Jaguar Dataset (100 hits for the query "jaguar").

The experiments confirmed that while the Web is highly connected—70% of agents meet within three iterations of exhaustive search—heuristics are essential for accuracy.

Precision-recall curves for the Web appearance disambiguation dataset, showing the impact of different heuristics.

As shown in the precision-recall curves, adding heuristics like high-degree node elimination and name matching significantly improves performance. For the person disambiguation task, a hybrid model combining topical and topological signals achieved an F-measure of 83.9%, outperforming the pure topical baseline of 78.4%. On the Jaguar dataset, the hybrid approach reached a 77.1% F-measure.

Conclusion

By exploiting the link structure of the Web, heuristic search provides a powerful tool for disambiguating search results. While graph traversal is computationally intensive, the use of pre-indexed link structures makes this approach a viable complement to traditional text-based clustering, particularly for finding "hidden" connections between semantically related but linguistically diverse pages.

Summary updated

Abstract

Effective representation of Web search results remains an open problem in the Information Retrieval community. For ambiguous queries, a traditional approach is to organize search results into groups (clusters), one for each meaning of the query. These groups are usually constructed according to the topical similarity of the retrieved documents, but it is possible for documents to be totally dissimilar and still correspond to the same meaning of the query. To overcome this problem, we exploit the thematic locality of the Web--relevant Web pages are often located close to each other in the Web graph of hyperlinks. We estimate the level of relevance between each pair of retrieved pages by the length of a path between them. The path is constructed using multi-agent beam search: each agent starts with one Web page and attempts to meet as many other agents as possible with some bounded resources. We test the system on two types of queries: ambiguous English words and people names. The Web appears to be tightly connected; about 70% of the agents meet with each other after only three iterations of exhaustive breadth-first search. However, when heuristics are applied, the search becomes more focused and the obtained results are substantially more accurate. Combined with a content-driven Web page clustering technique, our heuristic search system significantly improves the clustering results.
BibTeX
@inproceedings{bekkerman2007web,
  author = {Ron Bekkerman and Shlomo Zilberstein and James Allan},
  title = {{Web Page Clustering Using Heuristic Search in the Web Graph}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
  url = {https://openreview.net/forum?id=HJZ2JHfubB},
}
Figure