NDLI: Random walk with restart: fast solutions and applications

Content Provider	Springer Nature Link
Author	Tong, Hanghang Faloutsos, Christos Pan, Jia Yu
Copyright Year	2007
Abstract	How closely related are two nodes in a graph? How to compute this score quickly, on huge, disk-resident, real graphs? Random walk with restart (RWR) provides a good relevance score between two nodes in a weighted graph, and it has been successfully used in numerous settings, like automatic captioning of images, generalizations to the “connection subgraphs”, personalized PageRank, and many more. However, the straightforward implementations of RWR do not scale for large graphs, requiring either quadratic space and cubic pre-computation time, or slow response time on queries. We propose fast solutions to this problem. The heart of our approach is to exploit two important properties shared by many real graphs: (a) linear correlations and (b) block-wise, community-like structure. We exploit the linearity by using low-rank matrix approximation, and the community structure by graph partitioning, followed by the Sherman–Morrison lemma for matrix inversion. Experimental results on the Corel image and the DBLP dabasets demonstrate that our proposed methods achieve significant savings over the straightforward implementations: they can save several orders of magnitude in pre-computation and storage cost, and they achieve up to 150 × speed up with 90%+ quality preservation.
Starting Page	327
Ending Page	346
Page Count	20
File Format	PDF
ISSN	02191377
Journal	Knowledge and Information Systems
Volume Number	14
Issue Number	3
e-ISSN	02193116
Language	English
Publisher	Springer-Verlag
Publisher Date	2007-07-04
Publisher Place	London
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Relevance score Random walk with restart Graph Mining Business Information Systems Information Systems and Communication Service
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence Information Systems Human-Computer Interaction Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Exploring heterogeneous information networks and random walk with restart for academic search

TagClus: a random walk-based method for tag clustering

Modeling and exploiting tag relevance for Web service mining

An efficient graph-mining method for complicated and noisy data with real-world applications

Boosting for graph classification with universum

Attributed graph mining in the presence of automorphism

Graph mining for discovering infrastructure patterns in configuration management databases

Random-data perturbation techniques and privacy-preserving data mining

PEGASUS: mining peta-scale graphs

Random walk with restart: fast solutions and applications

Similar Documents

Exploring heterogeneous information networks and random walk with restart for academic search

TagClus: a random walk-based method for tag clustering

Modeling and exploiting tag relevance for Web service mining

An efficient graph-mining method for complicated and noisy data with real-world applications

Boosting for graph classification with universum

Attributed graph mining in the presence of automorphism

Graph mining for discovering infrastructure patterns in configuration management databases

Random-data perturbation techniques and privacy-preserving data mining

PEGASUS: mining peta-scale graphs

Random walk with restart: fast solutions and applications