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

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},
    Booktitle = {The 23rd Conference on Uncertainty in Artificial Intelligence(UAI)},
    Author = { Purnamrita Sarkar, Andrew W. Moore },
    Title = {A Tractable Approach to Finding Closest Truncated-commute-time Neighbors in Large Graphs}
}