Measuring proximity on graphs with side information

Hanghang Tong, Huiming Qu, Hani Jamjoom

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings - 8th IEEE International Conference on Data Mining, ICDM 2008
Pages598-607
Number of pages10
DOIs
StatePublished - Dec 1 2008
Externally publishedYes
Event8th IEEE International Conference on Data Mining, ICDM 2008 - Pisa, Italy
Duration: Dec 15 2008Dec 19 2008

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
ISSN (Print)1550-4786

Other

Other8th IEEE International Conference on Data Mining, ICDM 2008
CountryItaly
CityPisa
Period12/15/0812/19/08

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Measuring proximity on graphs with side information'. Together they form a unique fingerprint.

  • Cite this

    Tong, H., Qu, H., & Jamjoom, H. (2008). Measuring proximity on graphs with side information. In Proceedings - 8th IEEE International Conference on Data Mining, ICDM 2008 (pp. 598-607). [4781155] (Proceedings - IEEE International Conference on Data Mining, ICDM). https://doi.org/10.1109/ICDM.2008.42