Hanghang Tong, Huiming Qu and Hani Jamjoom
IEEE International Conference on Data Mining (ICDM)
Pisa, Italy, December 2008
Abstract. This paper studies how to incorporate side information (such
as users’ feedback) in measuring node proximity on
large graphs. Our method (ProSIN) is motivated by
the well-studied random walk with restart (RWR).
The basic idea behind ProSIN is to leverage side
information to refine the graph structure so that the
random walk is biased towards/away from some specific
zones on the graph. Our case studies demonstrate
that ProSIN is well-suited in a variety of
applications, including neighborhood search,
center-piece subgraphs, and image caption. Given
the potential computational complexity of ProSIN, we
also propose a fast algorithm (Fast-ProSIN) that
exploits the smoothness of the graph structures
with/without side information. Our experimental
evaluation shows that Fast-ProSIN achieves
significant speedups (up to 49x) over straightforward
implementations.
Bibtex.
@inproceedings{jamjoom-ICDM-08,
author = {Hanghang and Tong and Huiming and Qu and Hani and Jamjoom},
title = {{Measuring Proximity on Graphs with Side Information}},
booktitle = {IEEE International Conference on Data Mining (ICDM)},
address = {Pisa, Italy},
month = {December},
year = {2008}
}