Measuring proximity on graphs with side information

Hanghang Tong; Huiming Qu; Hani Jamjoom

doi:10.1109/ICDM.2008.42

Measuring proximity on graphs with side information

Hanghang Tong, Huiming Qu, Hani Jamjoom

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings - 8th IEEE International Conference on Data Mining, ICDM 2008
Pages	598-607
Number of pages	10
DOIs	https://doi.org/10.1109/ICDM.2008.42
State	Published - 2008
Externally published	Yes
Event	8th IEEE International Conference on Data Mining, ICDM 2008 - Pisa, Italy Duration: Dec 15 2008 → Dec 19 2008

Publication series

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

Other

Other	8th IEEE International Conference on Data Mining, ICDM 2008
Country/Territory	Italy
City	Pisa
Period	12/15/08 → 12/19/08

ASJC Scopus subject areas

General Engineering

Online availability

10.1109/ICDM.2008.42

Library availability

Discover UIUC Full Text

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., 4781155, Proceedings - IEEE International Conference on Data Mining, ICDM, pp. 598-607, 8th IEEE International Conference on Data Mining, ICDM 2008, Pisa, Italy, 12/15/08. https://doi.org/10.1109/ICDM.2008.42

@inproceedings{3965d455a23c46c5970cba2457e26936,

title = "Measuring proximity on graphs with side information",

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.",

author = "Hanghang Tong and Huiming Qu and Hani Jamjoom",

year = "2008",

doi = "10.1109/ICDM.2008.42",

language = "English (US)",

isbn = "9780769535029",

series = "Proceedings - IEEE International Conference on Data Mining, ICDM",

pages = "598--607",

booktitle = "Proceedings - 8th IEEE International Conference on Data Mining, ICDM 2008",

}

TY - GEN

T1 - Measuring proximity on graphs with side information

AU - Tong, Hanghang

AU - Qu, Huiming

AU - Jamjoom, Hani

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=67049167774&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67049167774&partnerID=8YFLogxK

U2 - 10.1109/ICDM.2008.42

DO - 10.1109/ICDM.2008.42

M3 - Conference contribution

AN - SCOPUS:67049167774

SN - 9780769535029

T3 - Proceedings - IEEE International Conference on Data Mining, ICDM

SP - 598

EP - 607

BT - Proceedings - 8th IEEE International Conference on Data Mining, ICDM 2008

T2 - 8th IEEE International Conference on Data Mining, ICDM 2008

Y2 - 15 December 2008 through 19 December 2008

ER -

Measuring proximity on graphs with side information

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this