{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T02:18:22Z","timestamp":1773886702037,"version":"3.50.1"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>\n            Given an input graph\n            <jats:italic>G<\/jats:italic>\n            and a node\n            <jats:italic>v<\/jats:italic>\n            \u2208\n            <jats:italic>G<\/jats:italic>\n            , homogeneous network embedding (HNE) maps the graph structure in the vicinity of\n            <jats:italic>v<\/jats:italic>\n            to a compact, fixed-dimensional feature vector. This paper focuses on HNE for massive graphs,\n            <jats:italic>e.g.<\/jats:italic>\n            , with billions of edges. On this scale, most existing approaches fail, as they incur either prohibitively high costs, or severely compromised result utility.\n          <\/jats:p>\n          <jats:p>\n            Our proposed solution, called Node-Reweighted PageRank (NRP), is based on a classic idea of deriving embedding vectors from pairwise personalized PageRank (PPR) values. Our contributions are twofold: first, we design a simple and efficient baseline HNE method based on PPR that is capable of handling billion-edge graphs on commodity hardware; second and more importantly, we identify an inherent drawback of vanilla PPR, and address it in our main proposal NRP. Specifically, PPR was designed for a very different purpose,\n            <jats:italic>i.e.<\/jats:italic>\n            , ranking nodes in\n            <jats:italic>G<\/jats:italic>\n            based on their\n            <jats:italic>relative<\/jats:italic>\n            importance from a source node's perspective. In contrast, HNE aims to build node embeddings considering the\n            <jats:italic>whole<\/jats:italic>\n            graph. Consequently, node embeddings derived directly from PPR are of suboptimal utility.\n          <\/jats:p>\n          <jats:p>\n            The proposed NRP approach overcomes the above deficiency through an effective and efficient node reweighting algorithm, which augments PPR values with node degree information, and iteratively adjusts embedding vectors accordingly. Overall, NRP takes\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) time and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            ) space to compute all node embeddings for a graph with\n            <jats:italic>m<\/jats:italic>\n            edges and\n            <jats:italic>n<\/jats:italic>\n            nodes. Our extensive experiments that compare NRP against 18 existing solutions over 7 real graphs demonstrate that NRP achieves higher result utility than all the solutions for link prediction, graph reconstruction and node classification, while being up to orders of magnitude faster. In particular, on a billion-edge Twitter graph, NRP terminates within 4 hours, using a single CPU core.\n          <\/jats:p>","DOI":"10.14778\/3377369.3377376","type":"journal-article","created":{"date-parts":[[2020,2,19]],"date-time":"2020-02-19T18:58:53Z","timestamp":1582138733000},"page":"670-683","source":"Crossref","is-referenced-by-count":59,"title":["Homogeneous network embedding for massive graphs via reweighted personalized PageRank"],"prefix":"10.14778","volume":"13","author":[{"given":"Renchi","family":"Yang","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore"}]},{"given":"Jieming","family":"Shi","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}]},{"given":"Xiaokui","family":"Xiao","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}]},{"given":"Yin","family":"Yang","sequence":"additional","affiliation":[{"name":"Hamad Bin Khalifa University, Qatar"}]},{"given":"Sourav S.","family":"Bhowmick","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2020,2,19]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"9180","volume-title":"NeurIPS","author":"Abu-El-Haija S.","year":"2018","unstructured":"S. Abu-El-Haija , B. Perozzi , R. Al-Rfou , and A. A. Alemi . Watch your step: Learning node embeddings via graph attention . In NeurIPS , pages 9180 -- 9190 , 2018 . S. Abu-El-Haija, B. Perozzi, R. Al-Rfou, and A. A. Alemi. Watch your step: Learning node embeddings via graph attention. In NeurIPS, pages 9180--9190, 2018."},{"key":"e_1_2_1_2_1","first-page":"37","volume-title":"WWW","author":"Ahmed A.","year":"2013","unstructured":"A. Ahmed , N. Shervashidze , S. Narayanamurthy , V. Josifovski , and A. J. Smola . Distributed large-scale natural graph factorization . In WWW , pages 37 -- 48 , 2013 . A. Ahmed, N. Shervashidze, S. Narayanamurthy, V. Josifovski, and A. J. Smola. Distributed large-scale natural graph factorization. In WWW, pages 37--48, 2013."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1935826.1935914"},{"key":"e_1_2_1_4_1","volume-title":"Fifth International AAAI Conference on Weblogs and Social Media","author":"Brzozowski M. J.","year":"2011","unstructured":"M. J. Brzozowski and D. M. Romero . Who should i follow? recommending people in directed social networks . In Fifth International AAAI Conference on Weblogs and Social Media , 2011 . M. J. Brzozowski and D. M. Romero. Who should i follow? recommending people in directed social networks. In Fifth International AAAI Conference on Weblogs and Social Media, 2011."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2807452"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806512"},{"key":"e_1_2_1_7_1","volume-title":"AAAI","author":"Cao S.","year":"2016","unstructured":"S. Cao , W. Lu , and Q. Xu . Deep neural networks for learning graph representations . In AAAI , 2016 . S. Cao, W. Lu, and Q. Xu. Deep neural networks for learning graph representations. In AAAI, 2016."},{"key":"e_1_2_1_8_1","volume-title":"AAAI","author":"Chen H.","year":"2018","unstructured":"H. Chen , B. Perozzi , Y. Hu , and S. Skiena . HARP: hierarchical representation learning for networks . In AAAI , 2018 . H. Chen, B. Perozzi, Y. Hu, and S. Skiena. HARP: hierarchical representation learning for networks. In AAAI, 2018."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00059"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488620"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2849727"},{"key":"e_1_2_1_12_1","volume-title":"AAAI","author":"Dai Q.","year":"2018","unstructured":"Q. Dai , Q. Li , J. Tang , and D. Wang . Adversarial network embedding . In AAAI , 2018 . Q. Dai, Q. Li, J. Tang, and D. Wang. Adversarial network embedding. In AAAI, 2018."},{"key":"e_1_2_1_13_1","first-page":"329","volume-title":"WWW","author":"Dai Q.","year":"2019","unstructured":"Q. Dai , X. Shen , L. Zhang , Q. Li , and D. Wang . Adversarial training methods for network embedding . In WWW , pages 329 -- 339 , 2019 . Q. Dai, X. Shen, L. Zhang, Q. Li, and D. Wang. Adversarial training methods for network embedding. In WWW, pages 329--339, 2019."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220025"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220041"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_1_17_1","first-page":"359","volume-title":"WWW","author":"Gu Y.","year":"2018","unstructured":"Y. Gu , Y. Sun , Y. Li , and Y. Yang . Rare: Social rank regulated large-scale network embedding . In WWW , pages 359 -- 368 , 2018 . Y. Gu, Y. Sun, Y. Li, and Y. Yang. Rare: Social rank regulated large-scale network embedding. In WWW, pages 359--368, 2018."},{"key":"e_1_2_1_18_1","first-page":"359","volume-title":"WWW","author":"Gu Y.","year":"2018","unstructured":"Y. Gu , Y. Sun , Y. Li , and Y. Yang . Rare: Social rank regulated large-scale network embedding . In WWW , pages 359 -- 368 , 2018 . Y. Gu, Y. Sun, Y. Li, and Y. Yang. Rare: Social rank regulated large-scale network embedding. In WWW, pages 359--368, 2018."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"e_1_2_1_20_1","first-page":"271","volume-title":"WWW","author":"Jeh G.","year":"2003","unstructured":"G. Jeh and J. Widom . Scaling personalized web search . In WWW , pages 271 -- 279 , 2003 . G. Jeh and J. Widom. Scaling personalized web search. In WWW, pages 271--279, 2003."},{"key":"e_1_2_1_21_1","unstructured":"Kaggle 2012. https:\/\/www.kaggle.com\/c7kddcup2012-track1.  Kaggle 2012. https:\/\/www.kaggle.com\/c7kddcup2012-track1."},{"key":"e_1_2_1_22_1","volume-title":"NeurIPS Workshop","author":"Kipf T. N.","year":"2016","unstructured":"T. N. Kipf and M. Welling . Variational graph auto-encoders . NeurIPS Workshop , 2016 . T. N. Kipf and M. Welling. Variational graph auto-encoders. NeurIPS Workshop, 2016."},{"key":"e_1_2_1_23_1","volume-title":"ICLR","author":"Kipf T. N.","year":"2017","unstructured":"T. N. Kipf and M. Welling . Semi-supervised classification with graph convolutional networks . In ICLR , 2017 . T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017."},{"key":"e_1_2_1_24_1","first-page":"591","volume-title":"WWW","author":"Kwak H.","year":"2010","unstructured":"H. Kwak , C. Lee , H. Park , and S. Moon . What is twitter, a social network or a news media ? In WWW , pages 591 -- 600 , 2010 . H. Kwak, C. Lee, H. Park, and S. Moon. What is twitter, a social network or a news media? In WWW, pages 591--600, 2010."},{"key":"e_1_2_1_25_1","first-page":"5257","volume-title":"NeurIPS","author":"Lai Y.-A.","year":"2017","unstructured":"Y.-A. Lai , C.-C. Hsu , W. Chen , M.-Y. Yeh , and S.-D. Lin . Prune : Preserving proximity and global ranking for network embedding . In NeurIPS , pages 5257 -- 5266 , 2017 . Y.-A. Lai, C.-C. Hsu, W. Chen, M.-Y. Yeh, and S.-D. Lin. Prune: Preserving proximity and global ranking for network embedding. In NeurIPS, pages 5257--5266, 2017."},{"key":"e_1_2_1_26_1","volume-title":"SysML","author":"Lerer A.","year":"2019","unstructured":"A. Lerer , L. Wu , J. Shen , T. Lacroix , L. Wehrstedt , A. Bose , and A. Peysakhovich . Pytorch-biggraph: A large-scale graph embedding system . In SysML , 2019 . A. Lerer, L. Wu, J. Shen, T. Lacroix, L. Wehrstedt, A. Bose, and A. Peysakhovich. Pytorch-biggraph: A large-scale graph embedding system. In SysML, 2019."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3289600.3291029"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220062"},{"key":"e_1_2_1_29_1","first-page":"1396","volume-title":"NeurIPS","author":"Musco C.","year":"2015","unstructured":"C. Musco and C. Musco . Randomized block krylov methods for stronger and faster approximate singular value decomposition . In NeurIPS , pages 1396 -- 1404 , 2015 . C. Musco and C. Musco. Randomized block krylov methods for stronger and faster approximate singular value decomposition. In NeurIPS, pages 1396--1404, 2015."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939751"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110025.3110086"},{"key":"e_1_2_1_33_1","first-page":"1509","volume-title":"WWW","author":"Qiu J.","year":"2019","unstructured":"J. Qiu , Y. Dong , H. Ma , J. Li , C. Wang , K. Wang , and J. Tang . Netsmf: Large-scale network embedding as sparse matrix factorization . In WWW , pages 1509 -- 1520 , 2019 . J. Qiu, Y. Dong, H. Ma, J. Li, C. Wang, K. Wang, and J. Tang. Netsmf: Large-scale network embedding as sparse matrix factorization. In WWW, pages 1509--1520, 2019."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159706"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1038\/nmeth.2340"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098061"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.37"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3357377.3357379"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741093"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-010-0210-x"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/P18-1024"},{"key":"e_1_2_1_42_1","first-page":"539","volume-title":"WWW","author":"Tsitsulin A.","year":"2018","unstructured":"A. Tsitsulin , D. Mottin , P. Karras , and E. M\u00fcller . Verse: Versatile graph embeddings from similarity measures . In WWW , pages 539 -- 548 , 2018 . A. Tsitsulin, D. Mottin, P. Karras, and E. M\u00fcller. Verse: Versatile graph embeddings from similarity measures. In WWW, pages 539--548, 2018."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220068"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939753"},{"key":"e_1_2_1_45_1","volume-title":"AAAI","author":"Wang H.","year":"2018","unstructured":"H. Wang , J. Wang , J. Wang , M. Zhao , W. Zhang , F. Zhang , X. Xing , and M. Guo . Graphgan: Graph representation learning with generative adversarial nets . In AAAI , 2018 . H. Wang, J. Wang, J. Wang, M. Zhao, W. Zhang, F. Zhang, X. Xing, and M. Guo. Graphgan: Graph representation learning with generative adversarial nets. In AAAI, 2018."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219869"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/390"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00576-7"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021936"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360902"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098072"},{"key":"e_1_2_1_52_1","volume-title":"AAAI","author":"Wang X.","year":"2017","unstructured":"X. Wang , P. Cui , J. Wang , J. Pei , W. Zhu , and S. Yang . Community preserving network embedding . In AAAI , 2017 . X. Wang, P. Cui, J. Wang, J. Pei, W. Zhu, and S. Yang. Community preserving network embedding. In AAAI, 2017."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196920"},{"key":"e_1_2_1_54_1","volume-title":"Mathematical Programming","author":"Wright S. J.","year":"2015","unstructured":"S. J. Wright . Coordinate descent algorithms . Mathematical Programming , 2015 . S. J. Wright. Coordinate descent algorithms. Mathematical Programming, 2015."},{"key":"e_1_2_1_55_1","volume-title":"Starspace: Embed all the things! In AAAI","author":"Wu L. Y.","year":"2018","unstructured":"L. Y. Wu , A. Fisch , S. Chopra , K. Adams , A. Bordes , and J. Weston . Starspace: Embed all the things! In AAAI , 2018 . L. Y. Wu, A. Fisch, S. Chopra, K. Adams, A. Bordes, and J. Weston. Starspace: Embed all the things! In AAAI, 2018."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/544"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_2_1_58_1","volume-title":"Homogeneous network embedding for massive graphs via personalized pagerank. arXiv preprint","author":"Yang R.","year":"2019","unstructured":"R. Yang , J. Shi , X. Xiao , S. S. Bhowmick , and Y. Yang . Homogeneous network embedding for massive graphs via personalized pagerank. arXiv preprint , 2019 . R. Yang, J. Shi, X. Xiao, S. S. Bhowmick, and Y. Yang. Homogeneous network embedding for massive graphs via personalized pagerank. arXiv preprint, 2019."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330860"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220000"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2018.2850013"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/594"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00094"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219969"},{"key":"e_1_2_1_65_1","volume-title":"AAAI","author":"Zhou C.","year":"2017","unstructured":"C. Zhou , Y. Liu , X. Liu , Z. Liu , and J. Gao . Scalable graph embedding for asymmetric proximity . In AAAI , 2017 . C. Zhou, Y. Liu, X. Liu, Z. Liu, and J. Gao. Scalable graph embedding for asymmetric proximity. In AAAI, 2017."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220052"},{"key":"e_1_2_1_67_1","first-page":"2494","volume-title":"WWW","author":"Zhu Z.","year":"2019","unstructured":"Z. Zhu , S. Xu , M. Qu , and J. Tang . Graphvite: A high-performance cpu-gpu hybrid system for node embedding . In WWW , pages 2494 -- 2504 , 2019 . Z. Zhu, S. Xu, M. Qu, and J. Tang. Graphvite: A high-performance cpu-gpu hybrid system for node embedding. In WWW, pages 2494--2504, 2019."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3377369.3377376","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:33:06Z","timestamp":1672219986000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3377369.3377376"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":67,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.14778\/3377369.3377376"],"URL":"https:\/\/doi.org\/10.14778\/3377369.3377376","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}