Algorithmic detection of semantic similarity

ABSTRACT

Automatic extraction of semantic information from text and links in Web pages is key to improving the quality of search results. However, the assessment of automatic semantic measures is limited by the coverage of user studies, which do not scale with the size, heterogeneity, and growth of the Web. Here we propose to leverage human-generated metadata --- namely topical directories --- to measure semantic relationships among massive numbers of pairs of Web pages or topics. The Open Directory Project classifies millions of URLs in a topical ontology, providing a rich source from which semantic relationships between Web pages can be derived. While semantic similarity measures based on taxonomies (trees) are well studied, the design of well-founded similarity measures for objects stored in the nodes of arbitrary ontologies (graphs) is an open problem. This paper defines an information-theoretic measure of semantic similarity that exploits both the hierarchical and non-hierarchical structure of an ontology. An experimental study shows that this measure improves significantly on the traditional taxonomy-based approach. This novel measure allows us to address the general question of how text and link analyses can be combined to derive measures of relevance that are in good agreement with semantic similarity. Surprisingly, the traditional use of text similarity turns out to be ineffective for relevance ranking.

REFERENCES

• 1: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 2: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 3: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 4: Christopher Fox, Lexical analysis and stoplists, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 5: Prasanna Ganesan , Hector Garcia-Molina , Jennifer Widom, Exploiting hierarchical domain structure to compute similarity, ACM Transactions on Information Systems (TOIS), v.21 n.1, p.64-93, January 2003 [doi>10.1145/635484.635487]
• 6: Thomas R. Gruber, A translation approach to portable ontology specifications, Knowledge Acquisition, v.5 n.2, p.199-220, June 1993 [doi>10.1006/knac.1993.1008]
• 7: Taher H. Haveliwala , Aristides Gionis , Dan Klein , Piotr Indyk, Evaluating strategies for similarity search on the web, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511502]
• 8: Abraham Kandel, Fuzzy mathematical techniques with applications, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 9: M. Kessler. Bibliographic coupling between scientific papers. American Documentation, 14:10--25, 1963.
• 10: Jon Kleinberg , Eva Tardos, Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.14, October 17-18, 1999
• 11: Robert R. Korfhage, Information storage and retrieval, John Wiley & Sons, Inc., New York, NY, 1997
• 12: Dekang Lin, An Information-Theoretic Definition of Similarity, Proceedings of the Fifteenth International Conference on Machine Learning, p.296-304, July 24-27, 1998
• 13: Wangzhong Lu , Jeannette Janssen , Evangelos Milios , Nathalie Japkowicz, Node similarity in networked information spaces, Proceedings of the 2001 conference of the Centre for Advanced Studies on Collaborative research, p.11, November 05-07, 2001, Toronto, Ontario, Canada
• 14: Filippo Menczer, Combining link and content analysis to estimate semantic similarity, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA [doi>10.1145/1013367.1013521]
• 15: F. Menczer. Correlated topologies in citation networks and the web. European Physical Journal B, 38(2):211--221, 2004.
• 16: Filippo Menczer, Mapping the Semantics of Web Text and Links, IEEE Internet Computing, v.9 n.3, p.27-36, May 2005 [doi>10.1109/MIC.2005.59]
• 17: S. Polalck. Measures for the comparison of information retrieval systems. American Documentation, 19(4):387--397, 1968.
• 18: M. Porter. An algorithm for suffix stripping. Program, 14(3):130--137, 1980.
• 19: P. Resnik. Using information content to evaluate semantic similarity in a taxonomy. In IJCAI, pages 448--453, 1995.
• 20: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 21: H. Small. Co-Citation in the scientific literature: A new measure of the relationship between documents. Journal of the American Society for Information Science, 42:676--684, 1973.
• 22: A. Tversky. Features of similarity. Psychological Review, 84(4):327--352, 1977.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Experimentation, Measurement

Keywords:
Web mining, Web search, content and link similarity, ranking evaluation, semantic similarity