Abstract
Given a graph G with n nodes, and two nodes \(u,v\in G\), the CoSimRank value s(u, v) quantifies the similarity between u and v based on graph topology. Compared to SimRank, CoSimRank is shown to be more accurate and effective in many real-world applications including synonym expansion, lexicon extraction, and entity relatedness in knowledge graphs. The computation of all pairwise CoSimRanks in G is highly expensive and challenging. Existing solutions all focus on devising approximate algorithms for the computation of all pairwise CoSimRanks. To attain a desired absolute accuracy guarantee \(\epsilon \), the state-of-the-art approximate algorithm for computing all pairwise CoSimRanks requires \(O(n^3\log _2(\ln (\frac{1}{\epsilon })))\) time, which is prohibitively expensive even \(\epsilon \) is large. In this paper, we propose \(\mathtt {RPCS}\), a fast randomized algorithm for computing all pairwise CoSimRank values. The basic idea of \(\mathtt {RPCS}\) is to approximate the \(n\times n\) matrix multiplications in CoSimRank computation via random projection. Theoretically, \(\mathtt {RPCS}\) runs in \(O(\frac{n^2\ln (n)}{\epsilon ^2}\ln (\frac{1}{\epsilon }))\) time and meanwhile ensures an absolute error of at most \(\epsilon \) in each CoSimRank value in G with a high probability. Extensive experiments using six real graphs demonstrate that \(\mathtt {RPCS}\) is more than up to orders of magnitude faster than the state of the art. In particular, on a million-edge Twitter graph, \(\mathtt {RPCS}\) answers the \(\epsilon \)-approximate (\(\epsilon =0.1\)) all pairwise CoSimRank query within 4 h, using a single commodity server, while existing solutions fail to terminate within a day.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
References
Achlioptas, D.: Database-friendly random projections: johnson-lindenstrauss with binary coins. J. Comput. Syst. Sci., pp. 671–687 (2003)
Chen, L.: Johnson-lindenstrauss transformation and random projection (2015)
Dhulipala, L., Shi, J., Tseng, T., Blelloch, G.E., Shun, J.: The graph based benchmark suite (gbbs). In: Proceedings of the Joint International Workshop on Graph Data Management Experiences and Systems and Network Data Analytics, pp. 1–8 (2020)
Haveliwala, T.H.: Topic-sensitive pagerank: a context-sensitive ranking algorithm for web search. IEEE Trans. Knowl. Data Eng., pp. 784–796 (2003)
Hou, G., Chen, X., Wang, S., Wei, Z.: Massively parallel algorithms for personalized pagerank. Proc. VLDB Endow. 14(9), 1668–1680 (2021)
Munich, L.P.: For information of the university cistern (2013). cistern.cis.lmu.de
Jeh, G., Widom, J.: Simrank: a measure of structural-context similarity. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 538–543 (2002)
Jeh, G., Widom, J.: Scaling personalized web search. In: Proceedings of the International Conference on World Wide Web, pp. 271–279 (2003)
Johnson, W.B., Lindenstrauss, J.: Extensions of lipschitz mappings into a hilbert space. Contemp. Math. 26(189–206), 1 (1984)
Kaban, A.: Improved bounds on the dot product under random projection and random sign projection. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 487–496 (2015)
Leskovec, J., Krevl, A.: SNAP Datasets: stanford large network dataset collection (2013). snap.stanford.edu/data
Levitin, A.: Introduction to the design and analysis of algorithms. Pearson, Boston (2012)
Liao, X., Wu, Y., Cao, X.: Second-order cosimrank for similarity measures in social networks. In: IEEE International Conference on Communications, pp. 1–6 (2019)
Lin, W.: Distributed algorithms for fully personalized pagerank on large graphs. In: Proceedings of the International Conference on World Wide Web, pp. 1084–1094 (2019)
Matoušek, J.: On variants of the johnson-lindenstrauss lemma. Random Structures and Algorithms, pp. 142–156 (2008)
McAuley, J.J., Leskovec, J.: Learning to discover social circles in ego networks. In: Advances in Neural Information Processing Systems, pp. 548–56 (2012)
Page, L., Brin, S., Motwani, R., Winograd, T.: The pagerank citation ranking: bringing order to the web. Tech. Rep., Stanford InfoLab (1999)
Ponza, M., Ferragina, P., Chakrabarti, S.: A two-stage framework for computing entity relatedness in wikipedia. In: Proceedings of the ACM International Conference on Information and Knowledge Management, pp. 1867–1876 (2017)
Rothe, S., Schütze, H.: Cosimrank: A flexible and efficient graph-theoretic similarity measure. In: Proceedings of the Annual Meeting of the Association for Computational Linguistics, pp. 1392–1402 (2014)
Shi, J., Jin, T., Yang, R., Xiao, X., Yang, Y.: Realtime index-free single source simrank processing on web-scale graphs. Proc. VLDB Endow. 13(7), 966–980 (2020)
Shi, J., Yang, R., Jin, T., Xiao, X., Yang, Y.: Realtime top-k personalized pagerank over large graphs on gpus. Proc. VLDB Endow., pp. 15–28 (2019)
Tian, B., Xiao, X.: Sling: A near-optimal index structure for simrank. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 1859–1874 (2016)
Venkatasubramanian, S., Wang, Q.: The johnson-lindenstrauss transform: an empirical study. In: Proceedings of the Thirteenth Workshop on Algorithm Engineering and Experiments, pp. 164–173 (2011)
Wang, H., Wei, Z., Yuan, Y., Du, X., Wen, J.R.: Exact single-source simrank computation on large graphs. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 653–663 (2020)
Wang, S., et al.: Efficient algorithms for approximate single-source personalized pagerank queries. ACM Trans. Database Syst., pp. 1–37 (2019)
Wang, S., Yang, R., Xiao, X., Wei, Z., Yang, Y.: Fora: simple and effective approximate single-source personalized pagerank. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 505–514 (2017)
Wang, Y., et al.: Disk: a distributed framework for single-source simrank with accuracy guarantee. Proc. VLDB Endow. 14(3), 351–363 (2020)
Wei, Z., et al.: Prsim: Sublinear time simrank computation on large power-law graphs. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. pp. 1042–1059 (2019)
Wu, H., Gan, J., Wei, Z., Zhang, R.: Unifying the global and local approaches: an efficient power iteration with forward push. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 1996–2008 (2021)
Yang, R., Shi, J., Xiao, X., Yang, Y., Bhowmick, S.S.: Homogeneous network embedding for massive graphs via reweighted personalized pagerank. Proc. VLDB Endow. 13(5), 670–683 (2020)
Yu, W., McCann, J.: Co-simmate: Quick retrieving all pairwise co-simrank scores. In: Proceedings of the Annual Meeting of the Association for Computational Linguistics. pp. 327–333 (2015)
Yu, W., Wang, F.: Fast exact cosimrank search on evolving and static graphs. In: Proceedings of the International Conference on World Wide Web, pp. 599–608 (2018)
Zeng, W., Tang, J., Zhao, X.: Measuring entity relatedness via entity and text joint embedding. Neural Process. Lett., pp. 1861–1875 (2019)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Yang, R., Xiao, X. (2021). Fast Approximate All Pairwise CoSimRanks via Random Projection. In: Zhang, W., Zou, L., Maamar, Z., Chen, L. (eds) Web Information Systems Engineering – WISE 2021. WISE 2021. Lecture Notes in Computer Science(), vol 13080. Springer, Cham. https://doi.org/10.1007/978-3-030-90888-1_34
Download citation
DOI: https://doi.org/10.1007/978-3-030-90888-1_34
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-90887-4
Online ISBN: 978-3-030-90888-1
eBook Packages: Computer ScienceComputer Science (R0)