{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T06:27:39Z","timestamp":1778048859132,"version":"3.51.4"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Hong Kong RGC GRF Grant","award":["No. 14217322"],"award-info":[{"award-number":["No. 14217322"]}]},{"name":"Hong Kong RGC ECS Grant","award":["No. 24203419"],"award-info":[{"award-number":["No. 24203419"]}]},{"name":"Hong Kong RGC CRF Grant","award":["No. C4158-20G"],"award-info":[{"award-number":["No. C4158-20G"]}]},{"name":"Hong Kong ITC ITF grant","award":["No. MRP\/071\/20X"],"award-info":[{"award-number":["No. MRP\/071\/20X"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["No. U1936205, U2241212, 62276066"],"award-info":[{"award-number":["No. U1936205, U2241212, 62276066"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"crossref","award":["2020AAA0107600"],"award-info":[{"award-number":["2020AAA0107600"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>Subset embedding is the task to learn low-dimensional representations for a subset of nodes according to the graph topology. It has applications when we focus on a subset of users, e.g., young adults, and aim to make better recommendations for these target users. In real-world scenarios, graphs are dynamically changing. Thus, it is more desirable to dynamically maintain the subset embeddings to reflect graph updates. The state-of-the-art methods, e.g., DynPPE, still adopt a hashing-based method, while hashing-based solutions are shown to be less effective than matrix factorization (MF)-based methods in existing studies. At the same time, MF-based methods in the literature are too expensive to update the embedding when the graph changes, making them inapplicable on dynamic graphs.<\/jats:p>\n          <jats:p>Motivated by this, we present Tree-SVD, an efficient and effective MF-based method for dynamic subset embedding. If we simply maintain the whole proximity matrix, then we need to re-do the MF, e.g., truncated Singular Value Decomposition (SVD), on the whole matrix after graph updates, which is prohibitive. To tackle this issue, our main idea is to do hierarchical SVD (HSVD) on the proximity matrix of the given subset, which vertically divides the proximity matrix into multiple sub-matrices, and then repeatedly do SVD on sub-matrices and merge the intermediate results to obtain the final embedding. We first present Tree-SVD, which combines a sparse randomized SVD with an HSVD. Our theoretical analysis shows that our Tree-SVD gains the efficiency of sparse randomized SVD and the flexibility of the HSVD with theoretical guarantees. To further reduce update costs, we present a lazy-update strategy. In this strategy, we only update sub-matrices that changes remarkably in terms of the Frobenius norm. We present theoretical analysis to show the guarantees with our lazy-update strategy. Extensive experiments show the efficiency and effectiveness of Tree-SVD on node classification and link prediction tasks.<\/jats:p>","DOI":"10.1145\/3588950","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T17:42:05Z","timestamp":1685468525000},"page":"1-26","source":"Crossref","is-referenced-by-count":12,"title":["Efficient Tree-SVD for Subset Node Embedding over Large Dynamic Graphs"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2865-1767","authenticated-orcid":false,"given":"Xinyu","family":"Du","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5203-5916","authenticated-orcid":false,"given":"Xingyi","family":"Zhang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1892-6971","authenticated-orcid":false,"given":"Sibo","family":"Wang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2671-7483","authenticated-orcid":false,"given":"Zengfeng","family":"Huang","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2023. Technical report and source code. https:\/\/github.com\/DoThingYo\/Tree-Embedding."},{"key":"e_1_2_2_2_1","doi-asserted-by":"crossref","unstructured":"Reid Andersen Fan Chung and Kevin Lang. 2006. Local Graph Partitioning using PageRank Vectors. In FOCS. 475--486.","DOI":"10.1109\/FOCS.2006.44"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2020.3032189"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3019134"},{"key":"e_1_2_2_5_1","doi-asserted-by":"crossref","unstructured":"Lun Du Yun Wang Guojie Song Zhicong Lu and Junshan Wang. 2018. Dynamic Network Embedding : An Extended Approach for Skip-gram based Network Embedding. In IJCAI. 2086--2092.","DOI":"10.24963\/ijcai.2018\/288"},{"key":"e_1_2_2_6_1","unstructured":"Xu Feng Yuyang Xie Mingye Song Wenjian Yu and Jie Tang. 2018. Fast Randomized PCA for Sparse Data. In ACML. 710--725."},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"Aditya Grover and Jure Leskovec. 2016. Node2vec: Scalable Feature Learning for Networks. In SIGKDD. 855--864.","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_2_8_1","doi-asserted-by":"crossref","unstructured":"Xingzhi Guo Baojian Zhou and Steven Skiena. 2021. Subset Node Representation Learning over Large Dynamic Graphs. In SIGKDD. 516--526.","DOI":"10.1145\/3447548.3467393"},{"key":"e_1_2_2_9_1","unstructured":"Will Hamilton Zhitao Ying and Jure Leskovec. 2017. Inductive representation learning on large graphs. In NeurIPS."},{"key":"e_1_2_2_10_1","doi-asserted-by":"crossref","unstructured":"Xiangnan He Kuan Deng Xiang Wang Yan Li YongDong Zhang and Meng Wang. 2020. LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation. In SIGIR. 639--648.","DOI":"10.1145\/3397271.3401063"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1997.9.8.1735"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461554"},{"key":"e_1_2_2_13_1","volume-title":"Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme. PACMMOD 1, 1","author":"Hou Guanhao","year":"2023","unstructured":"Guanhao Hou, Qintian Guo, Fangyuan Zhang, Sibo Wang, and Zhewei Wei. 2023. Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme. PACMMOD 1, 1 (2023), 25:1--25:26."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1058467"},{"key":"e_1_2_2_15_1","first-page":"1","article-title":"Representation Learning for Dynamic Graphs: A Survey","volume":"21","author":"Kazemi Seyed Mehran","year":"2020","unstructured":"Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. 2020. Representation Learning for Dynamic Graphs: A Survey. JMLR 21, 70 (2020), 1--73.","journal-title":"JMLR"},{"key":"e_1_2_2_16_1","volume-title":"Kipf and Max Welling","author":"Thomas","year":"2017","unstructured":"Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In ICLR."},{"key":"e_1_2_2_17_1","doi-asserted-by":"crossref","unstructured":"Haewoon Kwak Changhyun Lee Hosung Park and Sue Moon. 2010. What is Twitter a Social Network or a News Media?. In WWW. 591--600.","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_2_18_1","volume-title":"Efficient algorithms for personalized pagerank","author":"Lofgren Peter","unstructured":"Peter Lofgren. 2015. Efficient algorithms for personalized pagerank. Stanford University."},{"key":"e_1_2_2_19_1","doi-asserted-by":"crossref","unstructured":"Yao Ma Ziyi Guo Zhaocun Ren Jiliang Tang and Dawei Yin. 2020. Streaming Graph Neural Networks. In SIGIR. 719--728.","DOI":"10.1145\/3397271.3401092"},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","unstructured":"Sedigheh Mahdavi Shima Khoshraftar and Aijun An. 2018. dynnode2vec: Scalable Dynamic Network Embedding. In ICBD. 3762--3765.","DOI":"10.1109\/BigData.2018.8621910"},{"key":"e_1_2_2_21_1","volume-title":"Dynamic graph convolutional networks. Pattern Recognition 97","author":"Manessi Franco","year":"2020","unstructured":"Franco Manessi, Alessandro Rozza, and Mario Manzo. 2020. Dynamic graph convolutional networks. Pattern Recognition 97 (2020)."},{"key":"e_1_2_2_22_1","unstructured":"Tomas Mikolov Ilya Sutskever Kai Chen Greg Corrado and Jeffrey Dean. 2013. Distributed Representations of Words and Phrases and their Compositionality. In NeurIPS. 3111--3119."},{"key":"e_1_2_2_23_1","volume-title":"Ryan A. Rossi, Nesreen K. Ahmed, Eunyee Koh, and Sungchul Kim.","author":"Nguyen Giang Hoang","year":"2018","unstructured":"Giang Hoang Nguyen, John Boaz Lee, Ryan A. Rossi, Nesreen K. Ahmed, Eunyee Koh, and Sungchul Kim. 2018. Continuous-Time Dynamic Network Embeddings. In WWW Companion. 969--976."},{"key":"e_1_2_2_24_1","doi-asserted-by":"crossref","unstructured":"Naoto Ohsaka Takanori Maehara and Ken-ichi Kawarabayashi. 2015. Efficient PageRank Tracking in Evolving Networks. 875--884.","DOI":"10.1145\/2783258.2783297"},{"key":"e_1_2_2_25_1","doi-asserted-by":"crossref","unstructured":"Mingdong Ou Peng Cui Jian Pei Ziwei Zhang and Wenwu Zhu. 2016. Asymmetric Transitivity Preserving Graph Embedding. In SIGKDD. 1105--1114.","DOI":"10.1145\/2939672.2939751"},{"key":"e_1_2_2_26_1","unstructured":"Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1999. The PageRank citation ranking: bringing order to the web. (1999)."},{"key":"e_1_2_2_27_1","doi-asserted-by":"crossref","unstructured":"Bryan Perozzi Rami Al-Rfou and Steven Skiena. 2014. DeepWalk: Online Learning of Social Representations. In SIGKDD. 701--710.","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_2_2_28_1","doi-asserted-by":"crossref","unstructured":"Jiezhong Qiu Yuxiao Dong Hao Ma Jian Li Chi Wang Kuansan Wang and Jie Tang. 2019. NetSMF: Large-Scale Network Embedding As Sparse Matrix Factorization. In WWW. 1509--1520.","DOI":"10.1145\/3308558.3313446"},{"key":"e_1_2_2_29_1","doi-asserted-by":"crossref","unstructured":"Jiezhong Qiu Yuxiao Dong Hao Ma Jian Li Kuansan Wang and Jie Tang. 2018. Network Embedding as Matrix Factorization: Unifying DeepWalk LINE PTE and Node2vec. In WSDM. 459--467.","DOI":"10.1145\/3159652.3159706"},{"key":"e_1_2_2_30_1","unstructured":"Mingyue Tang Pan Li and Carl Yang. 2022. Graph Auto-Encoder via Neighborhood Wasserstein Reconstruction. In ICLR."},{"key":"e_1_2_2_31_1","unstructured":"Rakshit Trivedi Mehrdad Farajtabar Prasenjeet Biswal and Hongyuan Zha. 2019. DyRep: Learning Representations over Dynamic Graphs. In ICLR."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447713"},{"key":"e_1_2_2_33_1","doi-asserted-by":"crossref","unstructured":"Hanzhi Wang Zhewei Wei Junhao Gan Sibo Wang and Zengfeng Huang. 2020. Personalized pagerank to a target node revisited. In SIGKDD. 657--667.","DOI":"10.1145\/3394486.3403108"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021936"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360902"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098072"},{"key":"e_1_2_2_37_1","doi-asserted-by":"crossref","unstructured":"Zhewei Wei Xiaodong He Xiaokui Xiao Sibo Wang Shuo Shang and Ji-Rong Wen. 2018. Topppr: top-k personalized pagerank queries with precision guarantees on large graphs. In SIGMOD. 441--456.","DOI":"10.1145\/3183713.3196920"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377376"},{"key":"e_1_2_2_39_1","doi-asserted-by":"crossref","unstructured":"Yuan Yin and Zhewei Wei. 2019. Scalable graph embeddings via sparse transpose proximities. In SIGKDD. 1429--1437.","DOI":"10.1145\/3292500.3330860"},{"key":"e_1_2_2_40_1","doi-asserted-by":"crossref","unstructured":"Wenchao Yu Wei Cheng Charu C Aggarwal Haifeng Chen and Wei Wang. 2017. Link Prediction with Spatial and Temporal Consistency in Dynamic Networks. In IJCAI. 3343--3349.","DOI":"10.24963\/ijcai.2017\/467"},{"key":"e_1_2_2_41_1","doi-asserted-by":"crossref","unstructured":"Hongyang Zhang Peter Lofgren and Ashish Goel. 2016. Approximate personalized pagerank on dynamic graphs. In SIGKDD. 1315--1324.","DOI":"10.1145\/2939672.2939804"},{"key":"e_1_2_2_42_1","doi-asserted-by":"crossref","unstructured":"Xingyi Zhang Kun Xie Sibo Wang and Zengfeng Huang. 2021. Learning Based Proximity Matrix Factorization for Node Embedding. In SIGKDD. 2243--2253.","DOI":"10.1145\/3447548.3467296"},{"key":"e_1_2_2_43_1","doi-asserted-by":"crossref","unstructured":"Ziwei Zhang Peng Cui Haoyang Li Xiao Wang and Wenwu Zhu. 2018. Billion-scale network embedding with iterative random projection. In ICDM. 787--796.","DOI":"10.1109\/ICDM.2018.00094"},{"key":"e_1_2_2_44_1","volume-title":"TIMERS: Error-Bounded SVD Restart on Dynamic Networks. In AAAI. 224--231.","author":"Zhang Ziwei","year":"2018","unstructured":"Ziwei Zhang, Peng Cui, Jian Pei, Xiao Wang, and Wenwu Zhu. 2018. TIMERS: Error-Bounded SVD Restart on Dynamic Networks. In AAAI. 224--231."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588950","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588950","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:38Z","timestamp":1750178858000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588950"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588950"],"URL":"https:\/\/doi.org\/10.1145\/3588950","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}