Contextual search and name disambiguation in email using graphs

ABSTRACT

Similarity measures for text have historically been an important tool for solving information retrieval problems. In many interesting settings, however, documents are often closely connected to other documents, as well as other non-textual objects: for instance, email messages are connected to other messages via header information. In this paper we consider extended similarity metrics for documents and other objects embedded in graphs, facilitated via a lazy graph walk. We provide a detailed instantiation of this framework for email data, where content, social networks and a timeline are integrated in a structural graph. The suggested framework is evaluated for two email-related problems: disambiguating names in email documents, and threading. We show that reranking schemes based on the graph-walk similarity measures often outperform baseline methods, and that further improvements can be obtained by use of appropriate learning methods.

REFERENCES

• 1: Manu Aery , Sharma Chakravarthy, eMailSift: Email Classification Based on Structure and Content, Proceedings of the Fifth IEEE International Conference on Data Mining, p.18-25, November 27-30, 2005 [doi>10.1109/ICDM.2005.58]
• 2: A. Balmin, V. Hristidis, and Y. Papakonstantinou. ObjectRank: Authority-based keyword search in databases. In VLDB, 2004.
• 3: Ron Bekkerman , Ran El-Yaniv , Andrew McCallum, Multi-way distributional clustering via pairwise interactions, Proceedings of the 22nd international conference on Machine learning, p.41-48, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102357]
• 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: Vitor R. Carvalho , William W. Cohen, On the collective classification of email "speech acts", 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.1076094]
• 6: William W. Cohen, Data integration using similarity joins and a word-based information representation language, ACM Transactions on Information Systems (TOIS), v.18 n.3, p.288-321, July 2000 [doi>10.1145/352595.352598]
• 7: W. W. Cohen, P. Ravikumar, and S. Fienberg. A comparison of string distance metrics for name-matching tasks. In IIWEB, 2003.
• 8: W. W. Cohen, R. E. Schapire, and Y. Singer. Learning to order things. Journal of Artificial Intelligence Research (JAIR), 10:243--270, 1999.
• 9: 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]
• 10: M. Collins and T. Koo. Discriminative reranking for natural language parsing. Computational Linguistics, 31(1):25--69, 2005.
• 11: 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]
• 12: W. Bruce Croft , John Lafferty, Language Modeling for Information Retrieval, Kluwer Academic Publishers, Norwell, MA, 2003
• 13: C. P. Diehl, L. Getoor, and G. Namata. Name reference resolution in organizational email archives. In SIAM, 2006.
• 14: M. Diligenti, M. Gori, and M. Maggini. Learning web page scores by error back-propagation. In IJCAI, 2005.
• 15: S. Haykin. Neural Networks. Macmillan College Publishing Company, 1994.
• 16: Marti A. Hearst, TextTiling: segmenting text into multi-paragraph subtopic passages, Computational Linguistics, v.23 n.1, p.33-64, March 1997
• 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: D. Kalashnikov, S. Mehrotra, and Z. Chen. Exploiting relationship for domain independent data cleaning. In SIAM, 2005.
• 19: B. Klimt and Y. Yang. The enron corpus: A new dataset for email classification research. In ECML, 2004.
• 20: Oren Kurland , Lillian Lee, PageRank without hyperlinks: structural re-ranking using links induced by language models, 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.1076087]
• 21: David D. Lewis , Kimberly A. Knowles, Threading electronic mail: a preliminary study, Information Processing and Management: an International Journal, v.33 n.2, p.209-217, March 1997 [doi>10.1016/S0306-4573(96)00063-5]
• 22: Bradley Malin , Edoardo Airoldi , Kathleen M. Carley, A Network Analysis Model for Disambiguation of Names in Lists, Computational & Mathematical Organization Theory, v.11 n.2, p.119-139, July 2005 [doi>10.1007/s10588-005-3940-3]
• 23: E. Minkov, R. C. Wang, and W. W. Cohen. Extracting personal names from emails: Applying named entity recognition to informal text. In HLT-EMNLP, 2005.
• 24: 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]
• 25: 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.
• 26: 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]
• 27: G. Salton and C. Buckley. Global text matching for information retrieval. Science, 253:1012--1015, 1991.
• 28: Gerard Salton , Amit Singhal , Mandar Mitra , Chris Buckley, Automatic text structuring and summarization, Information Processing and Management: an International Journal, v.33 n.2, p.193-207, March 1997 [doi>10.1016/S0306-4573(96)00062-3]
• 29: 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]
• 30: 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]
• 31: 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]
• 32: Yiming Yang , Christopher G. Chute, An example-based mapping method for text categorization and retrieval, ACM Transactions on Information Systems (TOIS), v.12 n.3, p.252-277, July 1994 [doi>10.1145/183422.183424]
• 33: D. Zhou, B. Scholkopf, and T. Hofmann. Semi-supervised learning on directed graphs. In NIPS, 2005.
• 34: X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In ICML, 2003.

INDEX TERMS

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

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

General Terms:
Algorithms, Experimentation

Keywords:
email, graph-based retrieval, name disambiguation, threading