Mining social networks for personalized email prioritization

ABSTRACT

Email is one of the most prevalent communication tools today, and solving the email overload problem is pressingly urgent. A good way to alleviate email overload is to automatically prioritize received messages according to the priorities of each user. However, research on statistical learning methods for fully personalized email prioritization (PEP) has been sparse due to privacy issues, since people are reluctant to share personal messages and importance judgments with the research community. It is therefore important to develop and evaluate PEP methods under the assumption that only limited training examples can be available, and that the system can only have the personal email data of each user during the training and testing of the model for that user. This paper presents the first study (to the best of our knowledge) under such an assumption. Specifically, we focus on analysis of personal social networks to capture user groups and to obtain rich features that represent the social roles from the viewpoint of a particular user. We also developed a novel semi-supervised (transductive) learning algorithm that propagates importance labels from training examples to test examples through message and user nodes in a personal email network. These methods together enable us to obtain an enriched vector representation of each new email message, which consists of both standard features of an email message (such as words in the title or body, sender and receiver IDs, etc.) and the induced social features from the sender and receivers of the message. Using the enriched vector representation as the input in SVM classifiers to predict the importance level for each test message, we obtained significant performance improvement over the baseline system (without induced social features) in our experiments on a multi-user data collection. We obtained significant performance improvement over the baseline system (without induced social features) in our experiments on a multi-user data collection: the relative error reduction in MAE was 31% in micro-averaging, and 14% in macro-averaging.

REFERENCES

• 1: CEAS 2005 - Second Conference on Email and Anti-Spam, July 21-22, 2005, Stanford University, California, USA, 2005.
• 2: P. Oscar Boykin , Vwani P. Roychowdhury, Leveraging Social Networks to Fight Spam, Computer, v.38 n.4, p.61-68, April 2005 [doi>10.1109/MC.2005.132]
• 3: 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
• 4: J. Cadiz, L. Dabbish, A. Gupta, and G. D. Venolia. Supporting email workflow. Technical Report MSR-TR-2001-88, Microsoft Research (MSR), Sept. 2001.
• 5: K. M. Carley, D. Columbus, M. DeReno, J. Reminga, and I. Moon. Ora user's guide 2007. Carnegie Mellon University, SCS ISRI, Technical Report, (07-115), 2007.
• 6: Laura A. Dabbish , Robert E. Kraut, Email overload at work: an analysis of factors associated with email strain, Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work, November 04-08, 2006, Banff, Alberta, Canada [doi>10.1145/1180875.1180941]
• 7: R. B. Einat Minkov and W. Cohen. Activity-centred search in email. In Proceedings of the 5th Conference on Email and Anti-Spam (CEAS). CEAS, 2008.
• 8: L. C. Freeman. The Development of Social Network Analysis: A Study in the Sociology of Science. Empirical Press, 2004.
• 9: Luiz H. Gomes , Fernando D. O. Castro , Virgílio A. F. Almeida , Jussara M. Almeida , Rodrigo B. Almeida , Luis M. A. Bettencourt, Improving spam detection based on structural similarity, Proceedings of the Steps to Reducing Unwanted Traffic on the Internet on Steps to Reducing Unwanted Traffic on the Internet Workshop, p.12-12, July 07, 2005, Cambridge, MA
• 10: T. Haveliwala, S. Kamvar, and G. Jeh. An analytical comparison of approaches to personalizing pagerank. Technical report, Stanford University, 2003.
• 11: E. Horvitz, A. Jacobs, and D. Hovel. Attention-sensitive alerting. In K. B. Laskey and H. Prade, editors, UAI '99: Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, Stockholm, Sweden, July 30-August 1,1999, pages 305--313. Morgan Kaufmann, 1999.
• 12: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 13: R. Likert. A technique for the measurement of attitudes. Archives of Psychology, 140:1--55, 1932.
• 14: K. B. Lisa Johansen, Michael Rowell and P. McDaniel. Email communities of interest. In Proceedings of the 4th Conference on Email and Anti-Spam (CEAS).CEAS, 2007.
• 15: S. Martin, B. Nelson, A. Sewani, K. Chen, and A. D. Joseph. Analyzing behavioral features for email classification. In CEAS {1}.
• 16: C. Neustaedter, A. J. B. Brush, M. A. Smith, and D. Fisher. The social network and relationship finder: Social sorting for email triage. In CEAS {1}.
• 17: M. E. J. Newman. Modularity and community structure in networks. 2006.
• 18: Joshua R. Tyler , Dennis M. Wilkinson , Bernardo A. Huberman, Email as spectroscopy: automated discovery of community structure within organizations, Communities and technologies, Kluwer, B.V., Deventer, The Netherlands, 2003
• 19: S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge, 1994.
• 20: Martin Wattenberg , Steven L. Rohall , Daniel Gruen , Bernard Kerr, E-mail research: targeting the enterprise, Human-Computer Interaction, v.20 n.1, p.139-162, June 2005 [doi>10.1207/s15327051hci2001&2_5]
• 21: Joshua Goodman , Gordon V. Cormack , David Heckerman, Spam and the ongoing battle for the inbox, Communications of the ACM, v.50 n.2, p.24-33, February 2007 [doi>10.1145/1216016.1216017]
• 22: Mona Mojdeh , Gordon V. Cormack, Semi-supervised spam filtering: does it work?, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390482]
• 23: B. Klimt and Y. Yang. The Enron Corpus: A New Dataset for Email Classification Research. ECML 2004.
• 24: R. Balasubramanyan, V. Carvalho and W. Cohen, CutOnce - Recipient Recommendation and Leak Detection in Action. In AAAI-2008, Workshop on Enhanced Messaging.
• 25: P.N. Bennett and J. Carbonell (2007). Combining Probability-Based Rankers for Action-Item Detection. In Proceedings of HLT-NAACL 2007.
• 26: A. McCallum, X. Wang and A. Corrada-Emmanuel. Topic and Role Discovery in Social Networks with Experiments on Enron and Academic Email. Journal of Artificial Intelligence Research (JAIR), 2007.
• 27: D. Alwin, and J. Krosnick, The reliability of survey attitude measurement: The influence of questions and respondent attributes, Sociological Methods Research, 1991, 20(139).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.m Miscellaneous

General Terms:
Algorithms, Experimentation, Human Factors, Languages, Security

Keywords:
email prioritization, social network, text mining