Improving Graph-Walk Based Similarity with Reranking: Case Studies for Personal Information Management

Relational or semi-structured data is naturally represented by a graph, where nodes denote entities and directed typed edges represent the relations between them. Such graphs are heterogeneous in the sense that they describe different types of objects and links. We represent personal information as a graph that includes messages, terms, persons, dates and other object types, and relations like sent-to and has-term. Given the graph, we apply finite random graph walks to induce a measure of entity similarity, which can be viewed as a tool for performing search in the graph. Experiments conducted using personal email collections derived from the Enron corpus and other corpora show how the different tasks of alias finding, threading and person name disambiguation can be all addressed as search queries in this framework, where the graph-walk based similarity metric is preferable to alternative approaches, and further improvements are achieved with learning. While researchers have suggested to tune edge weight parameters to optimize the graph walk performance per task, we apply reranking to improve the graph walk results, using features that describe highlevel information such as the paths traversed in the walk. High performance, together with practical run times, suggest that the described framework is a useful search system in the PIM domain, as well as in other semi-structured domains.