#mail mining

By Liane Lewin-Eytan and Yoelle Maarek

The mail experience has not evolved much in the last few decades as compared to other communication channels. At the same time, personal communications have exploded  with the advent and growth of numerous new communication and social networking apps. This might lead you to believe mail is on its way to a slow death. We beg to differ.

As messaging, video chatting, and other social networking methods have reached adolescence, mail has entered its mid-life (without the crisis) while its traffic has significantly changed and evolved. A new type of mail traffic has emerged with the rise of online transactions, including online purchases, financial transactions, travel plans, event notifications, and many others. As a result, the Web mail domain has become dominated by what we call “machine-generated” messages; that is, emails that are generated (usually by companies) via scripts rather than by humans. Following this essential observation, it makes sense that you might want to be able to distinguish traffic generated by machines from that generated by humans. The use cases are numerous: from being able to provide views gathering similar types of messages (personal, travel, purchases, etc.) as surfaced recently in Yahoo Mail (see Figure 1) and Gmail, to being able to provide a user experience tailored to the type of email you are looking at (e.g., you wouldn’t want to provide a “reply” option to a “noreply@” machine-generated address).

Figure 1: Yahoo Mail “Smart Views” – here users can explore emails that are automatically categorized by topic

At Yahoo Research, we have developed a new classifying technology that distinguishes between human- and machine-generated mail. This “Human/Machine” classifier is based on a wide range of features, such as:

sender and traffic characteristics – a machine can generate large traffic bursts sent to a large number of recipients, while a human cannot

semantic attributes – various keywords repeating in machine-generated traffic of all types

structural attributes – messages generated by machines typically have complex HTML structures, while those composed by human are rather flat

Our classifier now achieves a performance of 90% precision and 90% recall for both categories. This means that 90% of the messages actually composed by human beings are indeed classified as “human,” and out of those classified as “human,” we are correct in 90% of the cases. The same goes for machines.

Given the high degree of accuracy with which we can distinguish between the two types of email traffic, we felt confident launching people-only notifications in Yahoo Mail across all platforms. This new feature (see Figure 2) allows you to get “people-only” notifications. In other words, you can turn on the option to receive a notification only when a person emails you, or you can turn it off and receive a notification for any new incoming message.

Figure 2: “People only” notifications settings enabled

While our users have said they enjoy the "people only" feature, what really excites us on the Yahoo Mail Mining team in Haifa, is the opportunity presented by machine-generated emails. We know that machines account for 90% of all mail traffic [4]. These machine-generated messages, whether they are purchase receipts, flight reservations, or something else, contain loads of personal information. So in many ways, the mailbox serves as a personal data store. Unpacking that data in a meaningful way presents an incredible opportunity to advance the mail experience for our users.

Machine-Generated Mail Mining

This line of research, based on the difference between human- and machine-generated mail traffic, was initiated when we investigated better means of mail classification [4][6] and has served different use cases in recent years [3][5], including mail anonymization [2]. Today, it mainly serves automatic mail extraction [1]. With mail extraction, what we attempt to achieve is an automated way of extracting the “personalized” (and thus more meaningful to the user) parts of messages created by automated scripts; more specifically, those parts that are either of high interest to you (the items you purchased, their date of delivery, the details of your trip, etc.), or those that have a business value (e.g., the advertisements we surface). Anonymization techniques that we developed precisely for machine-generated traffic (see Figure 3) allow us to preserve a user’s privacy [2] and adhere to formal PII terms of service.

Figure 3: Anonymized mail sample showing extraction fields

Mail extraction is a process composed of two main phases: clustering the messages and extracting the data. Why do we cluster before extracting? Because if clustered correctly, a single extraction rule can be applied over an entire cluster, and therefore needs to be defined only once per cluster.

Clustering

Clustering mail messages is performed horizontally, exploiting the similarities of machine-generated messages sent en masse with (usually) complex HTML structures. Using the recurrent characteristics of these messages, clusters are created, optimally matching the scripts generating the messages. Previous clustering techniques relied only on the message header [5] and mainly looked for similarities in the messages’ subjects. Today, the state-of-the-art clustering techniques rely on the body of messages (i.e., their structures) [1][2]. These techniques detect similarities in the HTML structure of the messages and allow for flexible matching, including some small differences in the structure. More flexible clustering results in fewer clusters and ease processes that require some maintenance or human intervention.

Figure 4: Cluster of Amazon purchase confirmations

Figure 5: A chart representing the distribution of clusters between different categories

Figure 6: Level of structural flexibility that can be allowed, while still guaranteeing high extraction quality (flexibility represented by edit distance)

Extractions

Once the clusters have been created, and we have guaranteed that all messages within a cluster are similar with regard to structure, we can move on to our next phase: mail extraction. Currently at Yahoo, some manual work is involved in defining extraction rules for interpreting some pieces of messages and for validating parts of the process. Extraction rules are defined per cluster and are applied online for each message entering the system after identifying the cluster to which it belongs.

The fact that mail extraction requires some interpretability during intermediate phases of its cycle is a bottleneck, which prevents scalability and coverage of the long tail. A fully-automated method for creating extraction rules that cover all machine-generated traffic is in the advance stages of development. Our process is based on the similarity of messages guaranteed by the cluster, which is a crucial attribute used for identifying and annotating the pieces of information we want to extract. Figure 7 below is an example of a rule created automatically. It is defined over an Xpath [7], where an Xpath is simply a pointer to a specific location in the message. This rule defines the fields of interest to be extracted from this location and provides their full annotations.

Figure 7: An extraction rule

As we continue to develop our machine-generated mail mining techniques, we hope to broaden our approach and share this research in an effort to encourage others to do the same. As a domain that has significantly changed its nature in recent years, mail deserves a reexamination of its scientific foundation and more attention within the research community.

Acknowledgements:

This multiple-year work has been published at several top conferences in the last few years and we are grateful to all our co-authors who not only invested so much effort in this research, but also published about it: Nir Ailon, Noa Avigdor-Elgrabli, Marc Cwalinski, Dotan DiCastro, Iftah Gamzu, Ira Grabovitch-Zuyev, Mihajlo Grbovic, Guy Halawi, Yehuda Koren, Zohar Karnin, Edo Liberty, Roman Sandler, David Wajc, Ran Wolff, and Eyal Zohar.

A huge thanks to the entire Yahoo Mail engineering and product team. The list of our friends and colleagues there is too long to be fully listed here but this couldn't have happened without their extraordinary support and partnership.

References:

[1] Noa Avigdor-Elgrabli, Mark Cwalinskiy, Dotan Di Castro, Iftah Gamzu, Irena Grabovitch-Zuyev, Liane Lewin-Eytan, Yoelle Maarek. Structural Clustering of Machine-Generated Mail. CIKM 2016.

[2] Dotan Di Castro, Liane Lewin-Eytan, Yoelle Maarek, Ran Wolff and Eyal Zohar, Enforcing k-anonymity in Web mail auditing. WSDM'2016, San Francisco, CA, Feb 2016.

[3] Iftah Gamzu, Zohar Shay Karnin, Yoelle Maarek and David Wajc. You Will Get Mail! Predicting the Arrival of Future Email. TempWeb 2105, Florence Italy, May 2015.

[4] Mihajlo Grbovic, Guy Halawi, Zohar Karnin and Yoelle Maarek. How many folders do you really need? Classifying email into a handful of categories. CIKM’2014, Shanghai, China, Nov 2014.

[5] Nir Ailon, Zohar Karnin, Edo Liberty and Yoelle Maarek. Threading Machine Generated Email. WSDM 2013.

[6] Y. Koren, E. Liberty, Y. Maarek, and R. Sandler. Automatically tagging email by leveraging other users' folders. KDD, 2011.