{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T12:48:05Z","timestamp":1751460485399,"version":"3.41.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T00:00:00Z","timestamp":1716249600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61877035, 62141216, 62002350"],"award-info":[{"award-number":["61877035, 62141216, 62002350"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004739","name":"Youth Innovation Promotion Association CAS","doi-asserted-by":"crossref","award":["2023120"],"award-info":[{"award-number":["2023120"]}],"id":[{"id":"10.13039\/501100004739","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science Foundation CRII Award","award":["2000722"],"award-info":[{"award-number":["2000722"]}]},{"name":"NSF","award":["2212370"],"award-info":[{"award-number":["2212370"]}]},{"name":"CAREER Award","award":["2046102"],"award-info":[{"award-number":["2046102"]}]},{"name":"SOAR fellowship, University of Sydney Faculty Startup funding, Australia Research Council (ARC) Discovery Project","award":["DP210101984"],"award-info":[{"award-number":["DP210101984"]}]},{"name":"Ant Group through Ant Research Intern Program"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>Many real-world networks are characterized by being temporal and dynamic, wherein the temporal information signifies the changes in connections, such as the addition or removal of links between nodes. Employing random walks on these temporal networks is a crucial technique for understanding the structural evolution of such graphs over time. However, existing state-of-the-art sampling methods are designed for traditional static graphs, and as such, they struggle to efficiently handle the dynamic aspects of temporal networks. This deficiency can be attributed to several challenges, including increased sampling complexity, extensive index space, limited programmability, and a lack of scalability.<\/jats:p>\n          <jats:p>\n            In this article, we introduce\n            <jats:italic>TEA+<\/jats:italic>\n            , a robust, fast, and scalable engine for conducting random walks on temporal graphs. Central to\n            <jats:italic>TEA+<\/jats:italic>\n            is an innovative hybrid sampling method that amalgamates two Monte Carlo sampling techniques. This fusion significantly diminishes space complexity while maintaining a fast sampling speed. Additionally,\n            <jats:italic>TEA+<\/jats:italic>\n            integrates a range of optimizations that significantly enhance sampling efficiency. This is further supported by an effective graph updating strategy, skilled in managing dynamic graph modifications and adeptly handling the insertion and deletion of both edges and vertices. For ease of implementation, we propose a temporal-centric programming model, designed to simplify the development of various random walk algorithms on temporal graphs. To ensure optimal performance across storage constraints,\n            <jats:italic>TEA+<\/jats:italic>\n            features a degree-aware hybrid storage architecture, capable of adeptly scaling in different memory environments. Experimental results showcase the prowess of\n            <jats:italic>TEA+<\/jats:italic>\n            , as it attains up to three orders of magnitude speedups compared to current random walk engines on extensive temporal graphs.\n          <\/jats:p>","DOI":"10.1145\/3652604","type":"journal-article","created":{"date-parts":[[2024,3,14]],"date-time":"2024-03-14T12:23:19Z","timestamp":1710418999000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["<i>TEA+<\/i>\n            : A Novel Temporal Graph Random Walk Engine with Hybrid Storage Architecture"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3154-3580","authenticated-orcid":false,"given":"Chengying","family":"Huan","sequence":"first","affiliation":[{"name":"Institute of Software Chinese Academy of Sciences, Beijing, China and Rutgers University, New Brunswick, USA, and Tsinghua University, Beijing, China, and Tsinghua University, Beijing China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3440-9675","authenticated-orcid":false,"given":"Yongchao","family":"Liu","sequence":"additional","affiliation":[{"name":"Ant Group, Hangzhou, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6597-6520","authenticated-orcid":false,"given":"Heng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Institute of Software Chinese Academy of Sciences, Beijing China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8402-1436","authenticated-orcid":false,"given":"Shuaiwen","family":"Song","sequence":"additional","affiliation":[{"name":"Sydney University, Sydney Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3528-6868","authenticated-orcid":false,"given":"Santosh","family":"Pandey","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, United States"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2626-7865","authenticated-orcid":false,"given":"Shiyang","family":"Chen","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, United States"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-8742-0996","authenticated-orcid":false,"given":"Xiangfei","family":"Fang","sequence":"additional","affiliation":[{"name":"Institute of Software Chinese Academy of Sciences, Beijing China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-8799-5225","authenticated-orcid":false,"given":"Yue","family":"Jin","sequence":"additional","affiliation":[{"name":"Ant Group, Hangzhou, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7580-0131","authenticated-orcid":false,"given":"Baptiste","family":"Lepers","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Neuch\u00e2tel, Neuchatel, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1823-0459","authenticated-orcid":false,"given":"Yanjun","family":"Wu","sequence":"additional","affiliation":[{"name":"Institute of Software, Chinese Academy of Sciences, Beijing China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6323-7388","authenticated-orcid":false,"given":"Hang","family":"Liu","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, United States"}]}],"member":"320","published-online":{"date-parts":[[2024,5,21]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"Yahoo Webscope. n.d. Home Page. Retrieved March 19 2024 from http:\/\/webscope.sandbox.yahoo.com"},{"key":"e_1_3_1_3_2","unstructured":"Web Data Commons. n.d. The 2012 Common Crawl Graph. Retrieved March 19 2024 from http:\/\/webdatacommons.org"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3575693.3575713"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-019-08746-5"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168846"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330925"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3102254.3102279"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2849727"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129104"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132953"},{"key":"e_1_3_1_13_2","first-page":"17","volume-title":"Proceedings of OSDI","author":"Gonzalez Joseph E.","year":"2012","unstructured":"Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012. PowerGraph: Distributed graph-parallel computation on natural graphs. In Proceedings of OSDI. 17\u201330."},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_3_1_15_2","first-page":"1024","volume-title":"Proceedings of NIPS","author":"Hamilton William L.","year":"2017","unstructured":"William L. Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Proceedings of NIPS. 1024\u20131034."},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2012.03.001"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3552326.3567491"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00101"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775126"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447786.3456226"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330895"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2507157.2507173"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623756"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11691"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816696"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_3_1_28_2","volume-title":"Inverse Transform Sampling","author":"Miller Frederic P.","year":"2010","unstructured":"Frederic P. Miller, Agnes F. Vandome, and John McBrewster (Eds.). 2010. Inverse Transform Sampling. VDM Publishing."},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3184558.3191526"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC41405.2020.00060"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl301"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380562"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882950"},{"key":"e_1_3_1_35_2","article-title":"Graph embedding with rich information through bipartite heterogeneous network","volume":"1710","author":"Sun Guolei","year":"2017","unstructured":"Guolei Sun and Xiangliang Zhang. 2017. Graph embedding with rich information through bipartite heterogeneous network. CoRR abs\/1710.06879 (2017).","journal-title":"CoRR"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476257"},{"key":"e_1_3_1_37_2","series-title":"National Bureau of Standards Applied Mathematics Series","first-page":"36","volume-title":"Monte Carlo Method","author":"Neumann John von","year":"1951","unstructured":"John von Neumann. 1951. Various techniques used in connection with random digits. In Monte Carlo Method. National Bureau of Standards Applied Mathematics Series, Vol. 12. National Bureau of Standards, 36\u201338."},{"key":"e_1_3_1_38_2","first-page":"559","volume-title":"Proceedings of ATC","author":"Wang Rui","year":"2020","unstructured":"Rui Wang, Yongkun Li, Hong Xie, Yinlong Xu, and John C. S. Lui. 2020. GraphWalker: An I\/O-efficient and resource-friendly graph analytic system for fast and scalable random walks. In Proceedings of ATC. 559\u2013571."},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3582016.3582025"},{"key":"e_1_3_1_40_2","volume-title":"Proceedings of ICLR","author":"Wang Yanbang","year":"2021","unstructured":"Yanbang Wang, Yen-Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. 2021. Inductive representation learning in temporal networks via causal anonymous walks. In Proceedings of ICLR."},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732945"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3477132.3483575"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359634"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219890"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220024"},{"key":"e_1_3_1_46_2","volume-title":"Proceedings of ICLR","author":"Zeng Hanqing","year":"2020","unstructured":"Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. 2020. GraphSAINT: Graph sampling based inductive learning method. In Proceedings of ICLR."},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/634"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/613"},{"key":"e_1_3_1_49_2","article-title":"Efficient graph computation for Node2Vec","volume":"1805","author":"Zhou Dongyan","year":"2018","unstructured":"Dongyan Zhou, Songjie Niu, and Shimin Chen. 2018. Efficient graph computation for Node2Vec. CoRR abs\/1805.00280 (2018).","journal-title":"CoRR"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352127"},{"key":"e_1_3_1_51_2","first-page":"301","volume-title":"Proceedings of OSDI","author":"Zhu Xiaowei","year":"2016","unstructured":"Xiaowei Zhu, Wenguang Chen, Weimin Zheng, and Xiaosong Ma. 2016. Gemini: A computation-centric distributed graph processing system. In Proceedings of OSDI. 301\u2013316."},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220054"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3652604","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3652604","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:30Z","timestamp":1750291410000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3652604"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,21]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3652604"],"URL":"https:\/\/doi.org\/10.1145\/3652604","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2024,5,21]]},"assertion":[{"value":"2023-07-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-05-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}