{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:21:37Z","timestamp":1768108897362,"version":"3.49.0"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:p>\n            Graph embedding aims at mapping each node to a low-dimensional vector, beneficial for various applications like pattern matching, retrieval augmented generation and recommendation. In this paper, we study the large-scale temporal graph embedding problem. Different from simple graphs, each edge has a timestamp in temporal graphs, which requires the embeddings to encode the temporal biases. Factorizing similarity matrix is a common approach for generating simple graph embeddings where similarity can be well characterized by some conventional metrics like personalized PageRank. However, how to construct a similarity that can encode interactions with temporal biases is a critical problem for large scale temporal graphs. To address this, we introduce the concept of temporal-based bipartite graph (TBG) and develop the temporal preferential attachment similarity (TPASim) that reflects concurrent node activity over time. Directly factorizing the TPASim matrix, which contains nearly\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            non-zeros, is not feasible for large graphs with\n            <jats:italic>n<\/jats:italic>\n            nodes. Instead, we present LTGE, which constructs and factorizes a temporal matrix with at most 2\n            <jats:italic>m<\/jats:italic>\n            non-zeros, where\n            <jats:italic>m<\/jats:italic>\n            is the number of edges. Our theoretical analysis shows that LTGE achieves the same embeddings as factorizing the TPASim matrix but significantly reduces complexity by a factor of\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \/\n            <jats:italic>m.<\/jats:italic>\n            On the other hand, when graphs evolve over time, to avoid recomputing, we further propose LTGEInc that utilizes a novel incremental singular value decomposition (SVD) algorithm with provable guarantee for updating the embeddings. Extensive experiments on several datasets with up to 17 million nodes and 1.3 billion edges demonstrate that LTGE outperforms the state of the art significantly and is orders of magnitude faster than the baselines specially designed for temporal graphs. For embeddings update, LTGEInc retains the performance with small computational overhead.\n          <\/jats:p>","DOI":"10.14778\/3717755.3717756","type":"journal-article","created":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T15:51:49Z","timestamp":1747756309000},"page":"929-942","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Graph Embedding Generation and Update for Large-Scale Temporal Graph"],"prefix":"10.14778","volume":"18","author":[{"given":"Yifan","family":"Song","sequence":"first","affiliation":[{"name":"HKUST(GZ)"}]},{"given":"Xiaolong","family":"Chen","sequence":"additional","affiliation":[{"name":"HKUST(GZ)"}]},{"given":"Wenqing","family":"Lin","sequence":"additional","affiliation":[{"name":"Tencent"}]},{"given":"Jia","family":"Li","sequence":"additional","affiliation":[{"name":"HKUST(GZ) &amp; HKUST"}]},{"given":"Chen","family":"Zhang","sequence":"additional","affiliation":[{"name":"Zhejiang CreateLink Technology"}]},{"given":"Yan","family":"Zhou","sequence":"additional","affiliation":[{"name":"Zhejiang CreateLink Technology"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"HKUST(GZ) &amp; HKUST"}]},{"given":"Jing","family":"Tang","sequence":"additional","affiliation":[{"name":"HKUST(GZ) &amp; HKUST"}]}],"member":"320","published-online":{"date-parts":[[2025,5,20]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Watch your step: Learning node embeddings via graph attention. Advances in neural information processingsystems 31","author":"Abu-El-Haija Sami","year":"2018","unstructured":"Sami Abu-El-Haija, Bryan Perozzi, Rami Al-Rfou, and Alexander A Alemi. 2018. Watch your step: Learning node embeddings via graph attention. Advances in neural information processingsystems 31 (2018)."},{"key":"e_1_2_1_2_1","volume-title":"Emergence of scaling in random networks. science 286, 5439","author":"Barab\u00e1si Albert-L\u00e1szl\u00f3","year":"1999","unstructured":"Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert. 1999. Emergence of scaling in random networks. science 286, 5439 (1999), 509\u2013512."},{"key":"e_1_2_1_3_1","volume-title":"Laplacian eigenmaps and spectral techniques for embedding and clustering. Advances in neural information processing systems 14","author":"Belkin Mikhail","year":"2001","unstructured":"Mikhail Belkin and Partha Niyogi. 2001. Laplacian eigenmaps and spectral techniques for embedding and clustering. Advances in neural information processing systems 14 (2001)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584053"},{"key":"e_1_2_1_5_1","volume-title":"Learning on attribute-missing graphs","author":"Chen Xu","year":"2020","unstructured":"Xu Chen, Siheng Chen, Jiangchao Yao, Huangjie Zheng, Ya Zhang, and Ivor W Tsang. 2020. Learning on attribute-missing graphs. IEEE transactions on pattern analysis and machine intelligence 44, 2 (2020), 740\u2013757."},{"key":"e_1_2_1_6_1","volume-title":"Link Recommendation to Augment Influence Diffusion with Provable Guarantees. arXiv preprint arXiv:2402.19189","author":"Chen Xiaolong","year":"2024","unstructured":"Xiaolong Chen, Yifan Song, and Jing Tang. 2024. Link Recommendation to Augment Influence Diffusion with Provable Guarantees. arXiv preprint arXiv:2402.19189 (2024)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2023\/395"},{"key":"e_1_2_1_8_1","volume-title":"International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=rJeW1yHYwH","unstructured":"da Xu, chuanwei ruan, evren korpeoglu, sushant kumar, and kannan achan. 2020. Inductive representation learning on temporal graphs. In International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=rJeW1yHYwH"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313445"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3580305.3599250"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654965"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/288"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588950"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02288367"},{"key":"e_1_2_1_15_1","volume-title":"SPECTRAL STATISTICS OF ERD\u0150S\u2014R\u00c9NYI GRAPHS I: LOCAL SEMICIRCLE LAW. The Annals of Probability","author":"Erd\u0151s L\u00e1szl\u00f3","year":"2013","unstructured":"L\u00e1szl\u00f3 Erd\u0151s, Antti Knowles, Horng-Tzer Yau, and Jun Yin. 2013. SPECTRAL STATISTICS OF ERD\u0150S\u2014R\u00c9NYI GRAPHS I: LOCAL SEMICIRCLE LAW. The Annals of Probability (2013), 2279\u20132375."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00198"},{"key":"e_1_2_1_17_1","volume-title":"Matrix computations","author":"Golub Gene H","unstructured":"Gene H Golub and Charles F Van Loan. 2013. Matrix computations. JHU press."},{"key":"e_1_2_1_18_1","volume-title":"DynGEM: Deep Embedding Method for Dynamic Graphs. (May","author":"Goyal Palash","year":"2018","unstructured":"Palash Goyal, Nitin Kamra, Xinran He, and Yan Liu. 2018. DynGEM: Deep Embedding Method for Dynamic Graphs. (May 2018)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_1_20_1","series-title":"SIAM review 53, 2","volume-title":"Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions","author":"Halko Nathan","year":"2011","unstructured":"Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. 2011. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review 53, 2 (2011), 217\u2013288."},{"key":"e_1_2_1_21_1","volume-title":"The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis) 5, 4","author":"Maxwell Harper F","year":"2015","unstructured":"F Maxwell Harper and Joseph A Konstan. 2015. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis) 5, 4 (2015), 1\u201319."},{"key":"e_1_2_1_22_1","volume-title":"Chang No Yoon, and Seung Kee Han.","author":"Holme Petter","year":"2002","unstructured":"Petter Holme, Beom Jun Kim, Chang No Yoon, and Seung Kee Han. 2002. Attack vulnerability of complex networks. Physical review E 65, 5 (2002), 056109."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/tkde.2020.3046511"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00101"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1058467"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775126"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775191"},{"key":"e_1_2_1_28_1","first-page":"19874","article-title":"Neural temporal walks: Motifaware representation learning on continuous-time dynamic graphs","volume":"35","author":"Jin Ming","year":"2022","unstructured":"Ming Jin, Yuan-Fang Li, and Shirui Pan. 2022. Neural temporal walks: Motifaware representation learning on continuous-time dynamic graphs. Advances in Neural Information Processing Systems 35 (2022), 19874\u201319886.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2009.263"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3167132.3167276"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159729"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2016.0033"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1609\/icwsm.v4i1.14013"},{"key":"e_1_2_1_34_1","volume-title":"Neural word embedding as implicit matrix factorization. Advances in neural information processing systems 27","author":"Levy Omer","year":"2014","unstructured":"Omer Levy and Yoav Goldberg. 2014. Neural word embedding as implicit matrix factorization. Advances in neural information processing systems 27 (2014)."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583150"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308560.3316585"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308560.3316585"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3289600.3291029"},{"key":"e_1_2_1_39_1","volume-title":"Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781","author":"Mikolov Tomas","year":"2013","unstructured":"Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781 (2013)."},{"key":"e_1_2_1_40_1","volume-title":"Randomized block krylov methods for stronger and faster approximate singular value decomposition. Advances in neural information processing systems 28","author":"Musco Cameron","year":"2015","unstructured":"Cameron Musco and Christopher Musco. 2015. Randomized block krylov methods for stronger and faster approximate singular value decomposition. Advances in neural information processing systems 28 (2015)."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3184558.3191526"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/1543767.1543769"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018731"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457329"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313446"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159706"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517887"},{"key":"e_1_2_1_49_1","unstructured":"Emanuele Rossi Ben Chamberlain Fabrizio Frasca Davide Eynard Federico Monti and Michael Bronstein. 2020. Temporal Graph Networks for Deep Learning on Dynamic Graphs. arXiv:2006.10637 [cs.LG]"},{"key":"e_1_2_1_50_1","volume-title":"Nonlinear dimensionality reduction by locally linear embedding. science 290, 5500","author":"Roweis Sam T","year":"2000","unstructured":"Sam T Roweis and Lawrence K Saul. 2000. Nonlinear dimensionality reduction by locally linear embedding. science 290, 5500 (2000), 2323\u20132326."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.2246"},{"key":"e_1_2_1_52_1","volume-title":"International Conference on Machine Learning. PMLR, 32728\u201332748","author":"Su Junwei","year":"2023","unstructured":"Junwei Su, Difan Zou, Zijun Zhang, and Chuan Wu. 2023. Towards robust graph incremental learning on evolving graphs. In International Conference on Machine Learning. PMLR, 32728\u201332748."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741093"},{"key":"e_1_2_1_54_1","unstructured":"Lloyd N Trefethen and David Bau. 2022. Numerical linear algebra. SIAM."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939753"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219869"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457564"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517838"},{"key":"e_1_2_1_59_1","volume-title":"Homogeneous network embedding for massive graphs via reweighted personalized pagerank. arXiv preprint arXiv:1906.06826","author":"Yang Renchi","year":"2019","unstructured":"Renchi Yang, Jieming Shi, Xiaokui Xiao, Yin Yang, and Sourav S Bhowmick. 2019. Homogeneous network embedding for massive graphs via reweighted personalized pagerank. arXiv preprint arXiv:1906.06826 (2019)."},{"key":"e_1_2_1_60_1","volume-title":"Scaling attributed network embedding to massive graphs. arXiv preprint arXiv:2009.00826","author":"Yang Renchi","year":"2020","unstructured":"Renchi Yang, Jieming Shi, Xiaokui Xiao, Yin Yang, Juncheng Liu, and Sourav S Bhowmick. 2020. Scaling attributed network embedding to massive graphs. arXiv preprint arXiv:2009.00826 (2020)."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.047102"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219890"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827597329266"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.017101"},{"key":"e_1_2_1_65_1","first-page":"4278","article-title":"Prone: Fast and scalable network representation learning","volume":"19","author":"Zhang Jie","year":"2019","unstructured":"Jie Zhang, Yuxiao Dong, Yan Wang, Jie Tang, and Ming Ding. 2019. Prone: Fast and scalable network representation learning.. In IJCAI, Vol. 19. 4278\u20134284.","journal-title":"IJCAI"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457325"},{"key":"e_1_2_1_67_1","unstructured":"Yuyu Zhang Liang Pang Lei Shi and Bin Wang. 2015. Large Scale Purchase Prediction with Historical User Actions on B2C Online Retail Platform. arXiv:1408.6515 [cs.LG]"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3265271"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2788565"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.11.016"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3717755.3717756","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T16:18:23Z","timestamp":1747757903000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3717755.3717756"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12]]},"references-count":70,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["10.14778\/3717755.3717756"],"URL":"https:\/\/doi.org\/10.14778\/3717755.3717756","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,12]]},"assertion":[{"value":"2025-05-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}