{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T22:05:51Z","timestamp":1780351551193,"version":"3.54.1"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T00:00:00Z","timestamp":1739145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,2,10]]},"abstract":"<jats:p>\n                    In many real-world applications (e.g., email networks, social networks, and phone call networks), the relationships between entities can be modeled as a temporal graph, in which each edge is associated with a timestamp representing the interaction time. As a fundamental task in temporal graph analysis, triangle counting has received much attention, and several triangle models have been developed, including \u03b4-temporal triangle, sliding-window triangle, and (\u03b4\n                    <jats:sub>1,3<\/jats:sub>\n                    , \u03b4\n                    <jats:sub>1,2<\/jats:sub>\n                    , \u03b4\n                    <jats:sub>2,3<\/jats:sub>\n                    )-temporal triangle. In particular, the \u03b4-temporal triangle, requiring the gap of timestamps of any two edges within it to be bounded by a threshold \u03b4, has been demonstrated effective in many real applications, such as cohesiveness analysis, transitivity, clustering coefficient, and graph classification. In this paper, we study fast algorithms for counting \u03b4-temporal triangles in a given query time window. We first propose an online algorithm, which enumerates all edges in the graph and for each edge, calculates how many \u03b4-temporal triangles end with the edge. We further develop an efficient index-based solution, which maps \u03b4-temporal triangles into points of the 2-dimensional space and further compactly organizes these points using hierarchical structures. Besides, we study the problem of binary \u03b4-temporal triangle counting by considering the existence of \u03b4-temporal triangle among three vertices. Experiments on large temporal graphs show that our online algorithm is up to 70\u00d7 faster than the state-of-the-art algorithm, and our index-based algorithm is up to 10\n                    <jats:sup>8<\/jats:sup>\n                    \u00d7 faster than the online algorithm.\n                  <\/jats:p>","DOI":"10.1145\/3709688","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T15:45:06Z","timestamp":1739288706000},"page":"1-27","source":"Crossref","is-referenced-by-count":3,"title":["Efficiently Counting Triangles in Large Temporal Graphs"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-0628-6122","authenticated-orcid":false,"given":"Yuyang","family":"Xia","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, Guangdong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5047-8593","authenticated-orcid":false,"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, Guangdong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1463-814X","authenticated-orcid":false,"given":"Wensheng","family":"Luo","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, Guangdong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,2,11]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1226"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401898"},{"key":"e_1_2_2_3_1","volume-title":"Science","volume":"353","author":"Benson Austin R","year":"2016","unstructured":"Austin R Benson, David F Gleich, and Jure Leskovec. 2016. Higher-order organization of complex networks. Science, Vol. 353, 6295 (2016), 163--166."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1186\/s40649-019-0068-z"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2022.3154319"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142388"},{"key":"e_1_2_2_8_1","volume-title":"Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs. arXiv preprint arXiv:2306.00893","author":"Cai Xinwei","year":"2023","unstructured":"Xinwei Cai, Xiangyu Ke, Kai Wang, Lu Chen, Tianming Zhang, Qing Liu, and Yunjun Gao. 2023. Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs. arXiv preprint arXiv:2306.00893 (2023)."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217026"},{"key":"e_1_2_2_10_1","volume-title":"Mining graphlet counts in online social networks. ACM Transactions on Knowledge Discovery from Data (TKDD)","author":"Chen Xiaowei","year":"2018","unstructured":"Xiaowei Chen and John CS Lui. 2018. Mining graphlet counts in online social networks. ACM Transactions on Knowledge Discovery from Data (TKDD), Vol. 12, 4 (2018), 1--38."},{"key":"e_1_2_2_11_1","series-title":"SIAM Journal on computing","volume-title":"Arboricity and subgraph listing algorithms","author":"Chiba Norishige","year":"1985","unstructured":"Norishige Chiba and Takao Nishizeki. 1985. Arboricity and subgraph listing algorithms. SIAM Journal on computing, Vol. 14, 1 (1985), 210--223."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020513"},{"key":"e_1_2_2_13_1","volume-title":"16th International Symposium on Experimental Algorithms (SEA","author":"da Fonseca Paulo GS","year":"2017","unstructured":"Paulo GS da Fonseca and Israel BF da Silva. 2017. Online construction of wavelet trees. In 16th International Symposium on Experimental Algorithms (SEA 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04245-8"},{"key":"e_1_2_2_15_1","volume-title":"Marc Van Kreveld, and Mark Overmars","author":"Berg Mark De","year":"2008","unstructured":"Mark De Berg, Otfried Cheong, Marc Van Kreveld, and Mark Overmars. 2008. Orthogonal range searching: Querying a database. Computational Geometry: Algorithms and Applications (2008), 95--120."},{"key":"e_1_2_2_16_1","volume-title":"Space-Query Tradeoffs in Range Subgraph Counting and Listing. arXiv preprint arXiv:2301.03390","author":"Deng Shiyuan","year":"2023","unstructured":"Shiyuan Deng, Shangqi Lu, and Yufei Tao. 2023. Space-Query Tradeoffs in Range Subgraph Counting and Listing. arXiv preprint arXiv:2301.03390 (2023)."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1054389"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2021.01.005"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742786"},{"key":"e_1_2_2_20_1","volume-title":"Laks VS Lakshmanan, and Xuemin Lin","author":"Fang Yixiang","year":"2019","unstructured":"Yixiang Fang, Kaiqiang Yu, Reynold Cheng, Laks VS Lakshmanan, and Xuemin Lin. 2019. Efficient algorithms for densest subgraph discovery. arXiv preprint arXiv:1906.00341 (2019)."},{"key":"e_1_2_2_21_1","volume-title":"A new data structure for cumulative frequency tables. Software: Practice and experience","author":"Fenwick Peter M","year":"1994","unstructured":"Peter M Fenwick. 1994. A new data structure for cumulative frequency tables. Software: Practice and experience, Vol. 24, 3 (1994), 327--336."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxad129"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339628"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452800"},{"key":"e_1_2_2_25_1","unstructured":"Roberto Grossi Ankur Gupta and Jeffrey Scott Vitter. 2003. High-order entropy-compressed text indexes. (2003)."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592799"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/3192424.3192486"},{"key":"e_1_2_2_28_1","volume-title":"Triangle counting and truss decomposition using FPGA. In 2018 IEEE high performance extreme computing conference (HPEC)","author":"Huang Sitao","unstructured":"Sitao Huang, Mohamed El-Hadedy, Cong Hao, Qin Li, Vikram S Mailthody, Ketan Date, Jinjun Xiong, Deming Chen, Rakesh Nagi, and Wen-mei Hwu. 2018. Triangle counting and truss decomposition using FPGA. In 2018 IEEE high performance extreme computing conference (HPEC). IEEE, 1--7."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3336191.3371839"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.2015.7421397"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-019-00630-6"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989418"},{"key":"e_1_2_2_34_1","volume-title":"Using triangles to improve community detection in directed networks. arXiv preprint arXiv:1404.5874","author":"Klymko Christine","year":"2014","unstructured":"Christine Klymko, David Gleich, and Tamara G Kolda. 2014. Using triangles to improve community detection in directed networks. arXiv preprint arXiv:1404.5874 (2014)."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2012.625260"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-27671-7_5"},{"key":"e_1_2_2_37_1","volume-title":"Temporal motifs. Temporal networks","author":"Kovanen Lauri","year":"2013","unstructured":"Lauri Kovanen, M\u00e1rton Karsai, Kimmo Kaski, J\u00e1nos Kert\u00e9sz, and Jari Saram\u00e4ki. 2013. Temporal motifs. Temporal networks (2013), 119--133."},{"key":"e_1_2_2_38_1","volume-title":"Proc. Int. Conf. on World Wide Web Companion. 1343--1350","author":"Kunegis J\u00e9r\u00f4me","year":"2013","unstructured":"J\u00e9r\u00f4me Kunegis. 2013. KONECT -- The Koblenz Network Collection. In Proc. Int. Conf. on World Wide Web Companion. 1343--1350."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00624-7"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00263763"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898361"},{"key":"e_1_2_2_42_1","volume-title":"Austin Benson, and Moses Charikar","author":"Liu Paul","year":"2018","unstructured":"Paul Liu, Austin Benson, and Moses Charikar. 2018. A sampling framework for counting temporal motifs. arXiv preprint arXiv:1810.00980 (2018)."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018731"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467374"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/SocialCom-PASSAT.2012.130"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/3192424.3192431"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220097"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.71.057101"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_2_2_51_1","volume-title":"Approximate triangle counting. arXiv preprint arXiv:0904.3761","author":"Tsourakakis Charalampos E","year":"2009","unstructured":"Charalampos E Tsourakakis, Mihail N Kolountzakis, and Gary L Miller. 2009. Approximate triangle counting. arXiv preprint arXiv:0904.3761 (2009)."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2024.123414"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-16-7566-9"},{"key":"e_1_2_2_54_1","volume-title":"A Clique-Querying Mining Framework for Discovering High Utility Co-Location Patterns without Generating Candidates. ACM Transactions on Knowledge Discovery from Data","author":"Wang Lizhen","year":"2023","unstructured":"Lizhen Wang, Vanha Tran, and Thanhcong Do. 2023. A Clique-Querying Mining Framework for Discovering High Utility Co-Location Patterns without Generating Candidates. ACM Transactions on Knowledge Discovery from Data, Vol. 18, 1 (2023), 1--42."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.134"},{"key":"e_1_2_2_56_1","unstructured":"Yuyang Xia Yixiang Fang and Wensheng Luo. 2024. Efficiently Counting Triangles in Large Temporal Graphs (Technical Report). https:\/\/github.com\/xqbf\/counting-triangles."},{"key":"e_1_2_2_57_1","volume-title":"T-gcn: A temporal graph convolutional network for traffic prediction","author":"Zhao Ling","year":"2019","unstructured":"Ling Zhao, Yujiao Song, Chao Zhang, Yu Liu, Pu Wang, Tao Lin, Min Deng, and Haifeng Li. 2019. T-gcn: A temporal graph convolutional network for traffic prediction. IEEE transactions on intelligent transportation systems, Vol. 21, 9 (2019), 3848--3858."},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00064"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3340964.3340987"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00100"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709688","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3709688","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:22:33Z","timestamp":1774981353000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709688"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,10]]},"references-count":60,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,10]]}},"alternative-id":["10.1145\/3709688"],"URL":"https:\/\/doi.org\/10.1145\/3709688","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,10]]}}}