A Tractable Approach to Finding Closest Truncated-commute-time Neighbors in Large Graphs (2007)

Purnamrita Sarkar, Andrew W. Moore

Abstract

Recently there has been much interest in graph-based learning, with applications in
collaborative fltering for recommender networks, link prediction for social networks and
fraud detection. These networks can consist of millions of entities, and so it is very important
to develop highly effcient techniques. We are especially interested in accelerating random walk approaches to compute some
very interesting proximity measures of these kinds of graphs. These measures have been
shown to do well empirically (Liben-Nowell & Kleinberg, 2003; Brand, 2005). We introduce a
truncated variation on a well-known measure, namely commute times arising from
random walks on graphs. We present a very novel algorithm to compute all interesting
pairs of approximate nearest neighbors in truncated commute times, without comput-
ing it between all pairs. We show results on both simulated and real graphs of size up to
100,000 entities, which indicate near-linear scaling in computation time.

Full text

Download (application/pdf, 217.9 kB)

Approximate BibTeX Entry

@inproceedings{sarkar_moore_uai07,
    Year = {2007},
    Title = {A Tractable Approach to Finding Closest Truncated-commute-time Neighbors in Large Graphs}
}