Efficient processing node proximity via random walk with restart

Bingqing Lv, Weiren Yu, Liping Wang, Julie A. McCann

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

Abstract

Graph is a useful tool to model complicated data structures. One important task in graph analysis is assessing node proximity based on graph topology. Recently, Random Walk with Restart (RWR) tends to pop up as a promising measure of node proximity, due to its proliferative applications in e.g. recommender systems, and image segmentation. However, the best-known algorithm for computing RWR resorts to a large LU matrix factorization on an entire graph, which is cost-inhibitive. In this paper, we propose hybrid techniques to efficiently compute RWR. First, a novel divide-and-conquer paradigm is designed, aiming to convert the large LU decomposition into small triangular matrix operations recursively on several partitioned subgraphs. Then, on every subgraph, a “sparse accelerator” is devised to further reduce the time of RWR without any sacrifice in accuracy. Our experimental results on real and synthetic datasets show that our approach outperforms the baseline algorithms by at least one constant factor without loss of exactness.
Original languageEnglish
Title of host publicationWeb Technologies and Applications
Subtitle of host publication16th Asia-Pacific Web Conference, APWeb 2014, Changsha, China, September 5-7, 2014. Proceedings
EditorsLei Chen, Yan Jia, Timos Sellis, Guanfeng Liu
Place of PublicationCham (CH)
PublisherSpringer
Pages542-549
Number of pages8
ISBN (Electronic)978-3-319-11116-2
ISBN (Print)978-3-319-11115-5
Publication statusPublished - 2014
Event16th Asia-Pacific Web Conference - Changsha, China
Duration: 5 Sep 20147 Sep 2014

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume8709
ISSN (Print)0302-9743

Conference

Conference16th Asia-Pacific Web Conference
Abbreviated titleAPWeb 2014
CountryChina
CityChangsha
Period5/09/147/09/14

Fingerprint

Recommender systems
Processing
Factorization
Image segmentation
Particle accelerators
Data structures
Topology
Decomposition
Costs

Cite this

Lv, B., Yu, W., Wang, L., & McCann, J. A. (2014). Efficient processing node proximity via random walk with restart. In L. Chen, Y. Jia, T. Sellis, & G. Liu (Eds.), Web Technologies and Applications: 16th Asia-Pacific Web Conference, APWeb 2014, Changsha, China, September 5-7, 2014. Proceedings (pp. 542-549). (Lecture Notes in Computer Science; Vol. 8709). Cham (CH): Springer.
Lv, Bingqing ; Yu, Weiren ; Wang, Liping ; McCann, Julie A. / Efficient processing node proximity via random walk with restart. Web Technologies and Applications: 16th Asia-Pacific Web Conference, APWeb 2014, Changsha, China, September 5-7, 2014. Proceedings. editor / Lei Chen ; Yan Jia ; Timos Sellis ; Guanfeng Liu. Cham (CH) : Springer, 2014. pp. 542-549 (Lecture Notes in Computer Science).
@inproceedings{81fc14bee0e944959ca1b4a84e8596a1,
title = "Efficient processing node proximity via random walk with restart",
abstract = "Graph is a useful tool to model complicated data structures. One important task in graph analysis is assessing node proximity based on graph topology. Recently, Random Walk with Restart (RWR) tends to pop up as a promising measure of node proximity, due to its proliferative applications in e.g. recommender systems, and image segmentation. However, the best-known algorithm for computing RWR resorts to a large LU matrix factorization on an entire graph, which is cost-inhibitive. In this paper, we propose hybrid techniques to efficiently compute RWR. First, a novel divide-and-conquer paradigm is designed, aiming to convert the large LU decomposition into small triangular matrix operations recursively on several partitioned subgraphs. Then, on every subgraph, a “sparse accelerator” is devised to further reduce the time of RWR without any sacrifice in accuracy. Our experimental results on real and synthetic datasets show that our approach outperforms the baseline algorithms by at least one constant factor without loss of exactness.",
author = "Bingqing Lv and Weiren Yu and Liping Wang and McCann, {Julie A.}",
year = "2014",
language = "English",
isbn = "978-3-319-11115-5",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "542--549",
editor = "Lei Chen and Yan Jia and Timos Sellis and Guanfeng Liu",
booktitle = "Web Technologies and Applications",
address = "Germany",

}

Lv, B, Yu, W, Wang, L & McCann, JA 2014, Efficient processing node proximity via random walk with restart. in L Chen, Y Jia, T Sellis & G Liu (eds), Web Technologies and Applications: 16th Asia-Pacific Web Conference, APWeb 2014, Changsha, China, September 5-7, 2014. Proceedings. Lecture Notes in Computer Science, vol. 8709, Springer, Cham (CH), pp. 542-549, 16th Asia-Pacific Web Conference, Changsha, China, 5/09/14.

Efficient processing node proximity via random walk with restart. / Lv, Bingqing; Yu, Weiren; Wang, Liping; McCann, Julie A.

Web Technologies and Applications: 16th Asia-Pacific Web Conference, APWeb 2014, Changsha, China, September 5-7, 2014. Proceedings. ed. / Lei Chen; Yan Jia; Timos Sellis; Guanfeng Liu. Cham (CH) : Springer, 2014. p. 542-549 (Lecture Notes in Computer Science; Vol. 8709).

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

TY - GEN

T1 - Efficient processing node proximity via random walk with restart

AU - Lv, Bingqing

AU - Yu, Weiren

AU - Wang, Liping

AU - McCann, Julie A.

PY - 2014

Y1 - 2014

N2 - Graph is a useful tool to model complicated data structures. One important task in graph analysis is assessing node proximity based on graph topology. Recently, Random Walk with Restart (RWR) tends to pop up as a promising measure of node proximity, due to its proliferative applications in e.g. recommender systems, and image segmentation. However, the best-known algorithm for computing RWR resorts to a large LU matrix factorization on an entire graph, which is cost-inhibitive. In this paper, we propose hybrid techniques to efficiently compute RWR. First, a novel divide-and-conquer paradigm is designed, aiming to convert the large LU decomposition into small triangular matrix operations recursively on several partitioned subgraphs. Then, on every subgraph, a “sparse accelerator” is devised to further reduce the time of RWR without any sacrifice in accuracy. Our experimental results on real and synthetic datasets show that our approach outperforms the baseline algorithms by at least one constant factor without loss of exactness.

AB - Graph is a useful tool to model complicated data structures. One important task in graph analysis is assessing node proximity based on graph topology. Recently, Random Walk with Restart (RWR) tends to pop up as a promising measure of node proximity, due to its proliferative applications in e.g. recommender systems, and image segmentation. However, the best-known algorithm for computing RWR resorts to a large LU matrix factorization on an entire graph, which is cost-inhibitive. In this paper, we propose hybrid techniques to efficiently compute RWR. First, a novel divide-and-conquer paradigm is designed, aiming to convert the large LU decomposition into small triangular matrix operations recursively on several partitioned subgraphs. Then, on every subgraph, a “sparse accelerator” is devised to further reduce the time of RWR without any sacrifice in accuracy. Our experimental results on real and synthetic datasets show that our approach outperforms the baseline algorithms by at least one constant factor without loss of exactness.

M3 - Conference contribution

SN - 978-3-319-11115-5

T3 - Lecture Notes in Computer Science

SP - 542

EP - 549

BT - Web Technologies and Applications

A2 - Chen, Lei

A2 - Jia, Yan

A2 - Sellis, Timos

A2 - Liu, Guanfeng

PB - Springer

CY - Cham (CH)

ER -

Lv B, Yu W, Wang L, McCann JA. Efficient processing node proximity via random walk with restart. In Chen L, Jia Y, Sellis T, Liu G, editors, Web Technologies and Applications: 16th Asia-Pacific Web Conference, APWeb 2014, Changsha, China, September 5-7, 2014. Proceedings. Cham (CH): Springer. 2014. p. 542-549. (Lecture Notes in Computer Science).