Learning to rank typed graph walks: local and global approaches

ABSTRACT

We consider the setting of lazy random graph walks over directed graphs, where entities are represented as nodes and typed edges represent the relations between them. This framework has been used in a variety of problems to derive an extended measure of entity similarity. In this paper we contrast two different approaches for applying supervised learning in this framework to improve graph walk performance: a gradient descent algorithm that tunes the transition probabilities of the graph, and a reranking approach that uses features describing global properties of the traversed paths. An empirical evaluation on a set of tasks from the domain of personal information management and multiple corpora show that reranking performance is usually superior to the local gradient descent algorithm, and that the methods often yield best results when combined.

REFERENCES

• 1: Alekh Agarwal , Soumen Chakrabarti , Sunny Aggarwal, Learning to rank networked entities, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150409]
• 2: Andrey Balmin , Vagelis Hristidis , Yannis Papakonstantinou, Objectrank: authority-based keyword search in databases, Proceedings of the Thirtieth international conference on Very large data bases, p.564-575, August 31-September 03, 2004, Toronto, Canada
• 3: M. Barthelemy, E. Chow, and T. Eliassi-Rad. Knowledge representation issues in semantic graphs for relationship detection. In AAAI Spring Symposium, 2005.
• 4: Helmut Berger , Michael Dittenbach , Dieter Merkl, An adaptive information retrieval system based on associative networks, Proceedings of the first Asian-Pacific conference on Conceptual modelling, p.27-36, January 23, 2004, Dunedin, New Zealand
• 5: Arvind Hulgeri , Charuta Nakhe, Keyword Searching and Browsing in Databases using BANKS, Proceedings of the 18th International Conference on Data Engineering, p.431, February 26-March 01, 2002
• 6: Soumen Chakrabarti , Jeetendra Mirchandani , Arnab Nandi, SPIN: searching personal information networks, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076186]
• 7: Huan Chang , David Cohn , Andrew McCallum, Learning to Create Customized Authority Lists, Proceedings of the Seventeenth International Conference on Machine Learning, p.127-134, June 29-July 02, 2000
• 8: W. W. Cohen and E. Minkov. A graph-search framework for associating gene identifiers with documents. BMC Bioinformatics, 7(440), 2006.
• 9: W. W. Cohen, P. Ravikumar, and S. Fienberg. A comparison of string distance metrics for name-matching tasks. In IIWEB, 2003.
• 10: W. W. Cohen, R. E. Schapire, and Y. Singer. Learning to order things. Journal of Artificial Intelligence Research (JAIR), 10:243--270, 1999.
• 11: Michael Collins, Ranking algorithms for named-entity extraction: boosting and the voted perceptron, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania [doi>10.3115/1073083.1073165]
• 12: Michael Collins , Terry Koo, Discriminative Reranking for Natural Language Parsing, Computational Linguistics, v.31 n.1, p.25-70, March 2005 [doi>10.1162/0891201053630273]
• 13: Kevyn Collins-Thompson , Jamie Callan, Query expansion using random walk models, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099727]
• 14: M. Diligenti, M. Gori, and M. Maggini. Learning web page scores by error back-propagation. In IJCAI, 2005.
• 15: Christos Faloutsos , Kevin S. McCurley , Andrew Tomkins, Fast discovery of connection subgraphs, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014068]
• 16: T. Hughes and D. Ramage. Lexical semantic relatedness with random graph walks. In EMNLP, 2007.
• 17: Glen Jeh , Jennifer Widom, SimRank: a measure of structural-context similarity, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775126]
• 18: B. Klimt and Y. Yang. The enron corpus: A new dataset for email classification research. In ECML, 2004.
• 19: E. Minkov and W. W. Cohen. An email and meeting assistant using graph walks. In CEAS, 2006.
• 20: Einat Minkov , William W. Cohen , Andrew Y. Ng, Contextual search and name disambiguation in email using graphs, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148179]
• 21: J. Neville and D. Jensen. Data mining in social networks. In National Academy of Sciences Symposium on Dynamic Social Network Analysis, 2002.
• 22: Zaiqing Nie , Yuanzhi Zhang , Ji-Rong Wen , Wei-Ying Ma, Object-level ranking: bringing order to Web objects, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060828]
• 23: L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. In Technical Report, Computer Science department, Stanford University, 1998.
• 24: G. Salton , C. Buckley, On the use of spreading activation methods in automatic information, Proceedings of the 11th annual international ACM SIGIR conference on Research and development in information retrieval, p.147-160, May 1988, Grenoble, France [doi>10.1145/62437.62447]
• 25: Robert E. Schapire , Yoram Singer, Improved Boosting Algorithms Using Confidence-rated Predictions, Machine Learning, v.37 n.3, p.297-336, Dec. 1999 [doi>10.1023/A:1007614523901]
• 26: Kristina Toutanova , Christopher D. Manning , Andrew Y. Ng, Learning random walk models for inducing word dependency distributions, Proceedings of the twenty-first international conference on Machine learning, p.103, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015442]
• 27: Wensi Xi , Edward A. Fox , Weiguo Fan , Benyu Zhang , Zheng Chen , Jun Yan , Dong Zhuang, SimFusion: measuring similarity using unified relationship matrix, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076059]
• 28: B. Zhao, P. Sen, and L. Getoor. Entity and relationship labeling in affiliation networks. In ICML Workshop on Statistical Network Analysis, 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models; Search process

General Terms:
Algorithms, Experimentation

Keywords:
entity relation graphs, learning, personal information management