Query clustering using click-through graph

ABSTRACT

In this paper we describe a problem of discovering query clusters from a click-through graph of web search logs. The graph consists of a set of web search queries, a set of pages selected for the queries, and a set of directed edges that connects a query node and a page node clicked by a user for the query. The proposed method extracts all maximal bipartite cliques (bicliques) from a click-through graph and compute an equivalence set of queries (i.e., a query cluster) from the maximal bicliques. A cluster of queries is formed from the queries in a biclique. We present a scalable algorithm that enumerates all maximal bicliques from the click-through graph. We have conducted experiments on Yahoo web search queries and the result is promising.

REFERENCES

• 1: J. J. Carrasco, D. C. Fain, K. J. Lang, and L. Zhukov. Clustering of bipartite advertiser-keywork grdaph. Workshop on Large Scale Clustering, ICDM 2003.
• 2: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Proceedings of the eighth international conference on World Wide Web, p.1481-1493, May 1999, Toronto, Canada
• 3: K. Makino, and T. Uno, New algorithms for enumerating all maximal cliques, The 9th Scandinavian Workshop on Algorithm Theory, 2004.
• 4: Etsuji Tomita , Akira Tanaka , Haruhisa Takahashi, The worst-case time complexity for generating all maximal cliques and computational experiments, Theoretical Computer Science, v.363 n.1, p.28-42, 25 October 2006 [doi>10.1016/j.tcs.2006.06.015]
• 5: Query clustering using user logs, ACM Transactions on Information Systems (TOIS), v.20 n.1, p.59-81, January 2002 [doi>10.1145/503104.503108]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Experimentation

Keywords:
biclique, click-through graph, equivalence set, maximal bipartite clique, query clustring, query intent