Improving graph-walk-based similarity with reranking: Case studies for personal information management Authors: Einat Minkov, William W. Cohen Keywords: graph walk, learning, semistructured data, PIM
Abstract:
Relational or semistructured data is naturally represented by a graph, where nodes denote entities and directed typed edges represent the relations between them. Such graphs are heterogeneous, describing 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 high-level information such as the paths traversed in the walk. High performance, together with practical runtimes, suggest that the described framework is a useful search system in the PIM domain, as well as in other semistructured domains. (emphasis in original)
OK, so I lied. The title of the post isn’t the title of the article. Sue me. 😉
Although, on the other hand you will find that for the authors, relatedness and similarity are used interchangeably (footnote 4), which I found to be rather odd.
My point being that creation of a topic map can be viewed as a process of refinement.
Based on some measure of similarity, you can decide that enough information has been identified or gathered together about a subject and simply stop.
There may well be additional information that could be refined out of a graph about a subject but there is no rule that compels you do to so.