The DOI matches its Crossref record; 26 of the 26 references it cites were found in a registry or an index.
Fast Random Walk with Restart and Its Applications
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 150x speed up with 90%+ quality preservation.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
(1999) · Cited by 12,854
Indexing by latent semantic analysis
Deerwester, S., Dumais, S. T., Furnas, G. W., Landauer, T. K., & Harshman, R. (1990) · Journal of the American Society for Information Science · doi:10.1002/(sici)1097-4571(199009)41:6<391::aid-asi1>3.0.co;2-9 · Cited by 12,751
Gaussian Processes for Machine Learning
Rasmussen, C. E., & Williams, C. K. I. (2005) · doi:10.7551/mitpress/3206.001.0001 · Cited by 11,705
Goodall, C. (1988) · Technometrics · doi:10.1080/00401706.1988.10488412 · Cited by 8,675
On Spectral Clustering: Analysis and an algorithm
Ng, A. Y., Jordan, M. I., & Weiss, Y. (2001) · Cited by 8,159
Learning with Local and Global Consistency
Zhou, D., Bousquet, O., Lal, T. N., Weston, J., & Schölkopf, B. (2003) · MPG.PuRe (Max Planck Society) · Cited by 3,864
SimRank: a measure of structural-context similarity
Jeh, G., & Widom, J. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/775047.775126 · Cited by 1,925
Haveliwala, T. H. (2002) · Proceedings of the 11th international conference on World Wide Web · doi:10.1145/511446.511513 · Cited by 1,567
Scaling personalized web search
Jeh, G., & Widom, J. (2003) · Proceedings of the twelfth international conference on World Wide Web - WWW '03 · doi:10.1145/775152.775191 · Cited by 1,195
Cited by
Link prediction in complex networks: A survey
Lü, L., & Zhou, T. (2011) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2010.11.027 · Cited by 2,819
Rajaraman, A., & Ullman, J. D. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9781139058452 · Cited by 2,262
PathSim: meta path-based top-K similarity search in heterogeneous information networks
Sun, Y., Han, J., Yan, X., Yu, P. S., & Wu, T. (2011) · Proceedings of the VLDB Endowment · doi:10.14778/3402707.3402736 · Cited by 1,870
Exploiting geographical influence for collaborative point-of-interest recommendation
Ye, M., Yin, P., Lee, W.-C., & Lee, D.-L. (2011) · Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval · doi:10.1145/2009916.2009962 · Cited by 1,111
Lü, L., Medo, M., Yeung, C. H., Zhang, Y.-C., Zhang, Z.-K., & Zhou, T. (2012) · Physics Reports · doi:10.1016/j.physrep.2012.02.006 · Cited by 995
Supervised random walks: predicting and recommending links in social networks
Backstrom, L., & Leskovec, J. (2011) · Proceedings of the fourth ACM international conference on Web search and data mining · doi:10.1145/1935826.1935914 · Cited by 982
Luo, Y., Zhao, X., Zhou, J., Yang, J., Zhang, Y., Kuang, W., Peng, J., Chen, L., & Zeng, J. (2017) · Nature Communications · doi:10.1038/s41467-017-00680-8 · Cited by 916
Graph clustering based on structural/attribute similarities
Zhou, Y., Cheng, H., & Yu, J. X. (2009) · Proceedings of the VLDB Endowment · doi:10.14778/1687627.1687709 · Cited by 863
Shi, Y., Larson, M., & Hanjalic, A. (2014) · ACM Computing Surveys · doi:10.1145/2556270 · Cited by 806
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
Qiu, J., Chen, Q., Dong, Y., Zhang, J., Yang, H., Ding, M., Wang, K., & Tang, J. (2020) · Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining · doi:10.1145/3394486.3403168 · Cited by 777
Entity Linking meets Word Sense Disambiguation: a Unified Approach
Moro, A., Raganato, A., & Navigli, R. (2014) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00179 · Cited by 743
A Survey of Link Prediction in Complex Networks
Martínez, V., Berzal, F., & Cubero, J.-C. (2017) · ACM Computing Surveys · doi:10.1145/3012704 · Cited by 695
Modeling Relation Paths for Representation Learning of Knowledge Bases
Lin, Y., Liu, Z., Luan, H., Sun, M., Rao, S., & Liu, S. (2015) · Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing · doi:10.18653/v1/d15-1082 · Cited by 657
Gleich, D. F. (2015) · SIAM Review · doi:10.1137/140976649 · Cited by 646
On social networks and collaborative recommendation
Konstas, I., Stathopoulos, V., & Jose, J. M. (2009) · Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/1571941.1571977 · Cited by 604
Managing and Mining Graph Data
(2010) · Advances in Database Systems · doi:10.1007/978-1-4419-6045-0 · Cited by 594
Clustering and community detection in directed networks: A survey
Malliaros, F. D., & Vazirgiannis, M. (2013) · Physics Reports · doi:10.1016/j.physrep.2013.08.002 · Cited by 591
DeepInf: Social Influence Prediction with Deep Learning
Qiu, J., Tang, J., Ma, H., Dong, Y., Wang, K., & Tang, J. (2018) · Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining · doi:10.1145/3219819.3220077 · Cited by 587
Link prediction techniques, applications, and performance: A survey
Kumar, A., Singh, S. S., Singh, K., & Biswas, B. (2020) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2020.124289 · Cited by 516
Location recommendation for location-based social networks
Ye, M., Yin, P., & Lee, W.-C. (2010) · Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems · doi:10.1145/1869790.1869861 · Cited by 505
Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning
Liu, Y., Li, Z., Pan, S., Gong, C., Zhou, C., & Karypis, G. (2022) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2021.3068344 · Cited by 492
HeteSim: A General Framework for Relevance Measure in Heterogeneous Networks
Shi, C., Kong, X., Huang, Y., S. Yu, P., & Wu, B. (2014) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2013.2297920 · Cited by 350
A model-based approach to attributed graph clustering
Xu, Z., Ke, Y., Wang, Y., Cheng, H., & Cheng, J. (2012) · Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2213836.2213894 · Cited by 332
Heterogeneous Network Representation Learning: A Unified Framework With Survey and Benchmark
Yang, C., Xiao, Y., Zhang, Y., Sun, Y., & Han, J. (2022) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2020.3045924 · Cited by 324
Word Sense Disambiguation: A Unified Evaluation Framework and Empirical Comparison
Raganato, A., Camacho-Collados, J., & Navigli, R. (2017) · Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers · doi:10.18653/v1/e17-1010 · Cited by 316
Community detection in node-attributed social networks: A survey
Chunaev, P. (2020) · Computer Science Review · doi:10.1016/j.cosrev.2020.100286 · Cited by 300
Random Walks: A Review of Algorithms and Applications
Xia, F., Liu, J., Nie, H., Fu, Y., Wan, L., & Kong, X. (2020) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2019.2952908 · Cited by 295
Fast shortest path distance estimation in large networks
Potamias, M., Bonchi, F., Castillo, C., & Gionis, A. (2009) · Proceedings of the 18th ACM conference on Information and knowledge management · doi:10.1145/1645953.1646063 · Cited by 291
Exploring social influence for recommendation: a generative model approach
Ye, M., Liu, X., & Lee, W.-C. (2012) · Proceedings of the 35th international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/2348283.2348373 · Cited by 288
Wu, Q., Zhang, H., Gao, X., He, P., Weng, P., Gao, H., & Chen, G. (2019) · The World Wide Web Conference · doi:10.1145/3308558.3313442 · Cited by 271
Compact integration of multi-network topology for functional analysis of genes
Cho, H., Berger, B., & Peng, J. (2016) · Cell Systems · doi:10.1016/j.cels.2016.10.017 · Cited by 241
Robust guided image filtering using Nonconvex potentials
Ham, B., Cho, M., & Ponce, J. (2018) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2017.2669034 · Cited by 219
A Random Walk around the City: New Venue Recommendation in Location-Based Social Networks
Noulas, A., Scellato, S., Lathia, N., & Mascolo, C. (2012) · 2012 International Conference on Privacy, Security, Risk and Trust and 2012 International Confernece on Social Computing · doi:10.1109/socialcom-passat.2012.70 · Cited by 184
Himmelstein, D. S., & Baranzini, S. E. (2015) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1004259 · Cited by 172
Gotcha! Network-based fraud detection for social security fraud
Van Vlasselaer, V., Eliassi-Rad, T., Akoglu, L., Snoeck, M., & Baesens, B. (2017) · Management Science · doi:10.1287/mnsc.2016.2489 · Cited by 164
Semi-Supervised Classification of Network Data Using Very Few Labels
Lin, F., & Cohen, W. W. (2010) · 2010 International Conference on Advances in Social Networks Analysis and Mining · doi:10.1109/asonam.2010.19 · Cited by 96
Li, Z. (., Fang, X., & Sheng, O. R. L. (2018) · ACM Transactions on Management Information Systems · doi:10.1145/3131782 · Cited by 65
Temporal subgraph contrastive learning for anomaly detection on dynamic attributed graphs
Yu, Y., Li, X., Shao, M., Sun, Y., & Wang, W. (2025) · Applied Intelligence · doi:10.1007/s10489-025-06402-8 · Cited by 2
Metadata
- Authors
- Tong, H., Faloutsos, C., & Pan, J.-Y.
- Venue
- Sixth International Conference on Data Mining (ICDM'06)
- Publisher
- IEEE
- Published
- 2006-12
- Pages
- 613-622
- ISSN
- 1550-4786 (ISSN-L)
- OpenAlex
- W2133299088
- Cited by
- 1,184
- References
- 26
- FWCI
- 12.44
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.