A Tractable Approach to Finding Closest Truncated-commute-time Neighbors in Large Graphs
Purnamrita Sarkar, Andrew Moore
Recently there has been much interest in graph-based learning, with applications in collaborative filtering for recommender net- works, link prediction for social networks and fraud detection. These networks can consist of millions of entities, and so it is very im- portant to develop highly efficient 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 intro- duce 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.
PDF Link: /papers/07/p335-sarkar.pdf
AUTHOR = "Purnamrita Sarkar
and Andrew Moore",
TITLE = "A Tractable Approach to Finding Closest Truncated-commute-time Neighbors in Large Graphs",
BOOKTITLE = "Proceedings of the Twenty-Third Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-07)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2007",
PAGES = "335--343"