{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T18:07:37Z","timestamp":1759514857000,"version":"3.44.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,2]]},"abstract":"<jats:p>Bipartite graphs are ubiquitous in many domains, e.g., e-commerce platforms, social networks, and academia, by modeling interactions between distinct entity sets. Within these graphs, the butterfly motif, a complete 2\u00d72 biclique, represents the simplest yet significant subgraph structure, crucial for analyzing complex network patterns. Counting the butterflies offers significant benefits across various applications, including community analysis and recommender systems. Additionally, the temporal dimension of bipartite graphs, where edges activate within specific time frames, introduces the concept of historical butterfly counting, i.e., counting butterflies within a given time interval. This temporal analysis sheds light on the dynamics and evolution of network interactions, offering new insights into their mechanisms. Despite its importance, no existing algorithm can efficiently solve the historical butterfly counting task. To address this, we design two novel indices whose memory footprints are dependent on #butterflies and #wedges, respectively. Combining these indices, we propose a graph structure-aware indexing approach that significantly reduces memory usage while preserving exceptional query speed. To further reduce the index size and boost the query efficiency, we design an index compression strategy, enabling the fast, high-quality, and unbiased approximation of historical butterfly counts. We theoretically prove that our approach is particularly advantageous on power-law graphs, a common characteristic of real-world bipartite graphs, by surpassing traditional complexity barriers for general graphs. Extensive experiments reveal that our query algorithms outperform existing methods by up to five magnitudes, effectively balancing speed with manageable memory requirements.<\/jats:p>","DOI":"10.14778\/3725688.3725693","type":"journal-article","created":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T14:19:21Z","timestamp":1756477161000},"page":"1607-1620","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Historical Butterfly Counting in Large Temporal Bipartite Networks via Graph Structure-Aware Index"],"prefix":"10.14778","volume":"18","author":[{"given":"Qiuyang","family":"Mang","sequence":"first","affiliation":[{"name":"CUHK-Shenzhen"}]},{"given":"Jingbang","family":"Chen","sequence":"additional","affiliation":[{"name":"University of Waterloo"}]},{"given":"Hangrui","family":"Zhou","sequence":"additional","affiliation":[{"name":"Tsinghua University"}]},{"given":"Yu","family":"Gao","sequence":"additional","affiliation":[{"name":"Independent"}]},{"given":"Yingli","family":"Zhou","sequence":"additional","affiliation":[{"name":"CUHK-Shenzhen"}]},{"given":"Qingyu","family":"Shi","sequence":"additional","affiliation":[{"name":"Independent"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}]},{"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"CUHK-Shenzhen"}]},{"given":"Chenhao","family":"Ma","sequence":"additional","affiliation":[{"name":"CUHK-Shenzhen"}]}],"member":"320","published-online":{"date-parts":[[2025,8,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335326"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/comnet\/cnx001"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1186\/s40649-019-0068-z"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1306\u20131325","author":"Brach Pawe\u0142","year":"2016","unstructured":"Pawe\u0142 Brach, Marek Cygan, Jakub \u0141\u0105cki, and Piotr Sankowski. 2016. Algorithmic complexity of power law networks. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1306\u20131325."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3636218.3636223"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217026"},{"key":"e_1_2_1_7_1","unstructured":"Kaiyu Chen Dong Wen Wenjie Zhang Ying Zhang Xiaoyang Wang and Xuemin Lin. [n. d.]. Querying Structural Diversity in Streaming Graphs. ([n. d.])."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3467861.3467873"},{"key":"e_1_2_1_9_1","series-title":"SIAM Journal on computing 14, 1","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 14, 1 (1985), 210\u2013223."},{"key":"e_1_2_1_10_1","volume-title":"Space-Query Tradeoffs in Range Subgraph Counting and Listing. In 26th International Conference on Database Theory (ICDT","author":"Deng Shiyuan","year":"2023","unstructured":"Shiyuan Deng, Shangqi Lu, and Yufei Tao. 2023. Space-Query Tradeoffs in Range Subgraph Counting and Listing. In 26th International Conference on Database Theory (ICDT 2023). Schloss-Dagstuhl-Leibniz Zentrum f\u00fcr Informatik."},{"key":"e_1_2_1_11_1","volume-title":"Madhav V Marathe, Aravind Srinivasan, Zoltan Toroczkai, and Nan Wang.","author":"Eubank Stephen","year":"2004","unstructured":"Stephen Eubank, Hasan Guclu, VS Anil Kumar, Madhav V Marathe, Aravind Srinivasan, Zoltan Toroczkai, and Nan Wang. 2004. Modelling disease outbreaks in realistic urban social networks. Nature 429, 6988 (2004), 180\u2013184."},{"key":"e_1_2_1_12_1","volume-title":"Madhav V Marathe, Aravind Srinivasan, Zoltan Toroczkai, and Nan Wang.","author":"Eubank Stephen","year":"2004","unstructured":"Stephen Eubank, Hasan Guclu, VS Anil Kumar, Madhav V Marathe, Aravind Srinivasan, Zoltan Toroczkai, and Nan Wang. 2004. Modelling disease outbreaks in realistic urban social networks. Nature 429, 6988 (2004), 180\u2013184."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_2_1_14_1","volume-title":"Conditional Lower Bounds for Space\/Time Tradeoffs","author":"Goldstein Isaac","unstructured":"Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. 2017. Conditional Lower Bounds for Space\/Time Tradeoffs. In Algorithms and Data Structures, Faith Ellen, Antonina Kolokolova, and J\u00f6rg-R\u00fcdiger Sack (Eds.). Springer International Publishing, Cham, 421\u2013436."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ISAAC.2019.7"},{"key":"e_1_2_1_16_1","volume-title":"Bipartite graphs as models of complex networks. Physica A: Statistical Mechanics and its Applications 371, 2","author":"Guillaume Jean-Loup","year":"2006","unstructured":"Jean-Loup Guillaume and Matthieu Latapy. 2006. Bipartite graphs as models of complex networks. Physica A: Statistical Mechanics and its Applications 371, 2 (2006), 795\u2013813."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737791"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397271.3401063"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052569"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487678"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2011\/11\/P11005"},{"key":"e_1_2_1_22_1","volume-title":"Main-memory triangle computations for very large (sparse (power-law)) graphs. Theoretical computer science 407, 1\u20133","author":"Latapy Matthieu","year":"2008","unstructured":"Matthieu Latapy. 2008. Main-memory triangle computations for very large (sparse (power-law)) graphs. Theoretical computer science 407, 1\u20133 (2008), 458\u2013473."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2021.3062987"},{"key":"e_1_2_1_24_1","volume-title":"MLG Workshop@ KDD.","author":"Li Yuchen","year":"2018","unstructured":"Yuchen Li, Zhengzhi Lou, Yu Shi, and Jiawei Han. 2018. Temporal motifs in heterogeneous information networks. In MLG Workshop@ KDD."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00100"},{"key":"e_1_2_1_26_1","volume-title":"Cycles and clustering in bipartite networks. Physical review E 72, 5","author":"Lind Pedro G","year":"2005","unstructured":"Pedro G Lind, Marta C Gonzalez, and Hans J Herrmann. 2005. Cycles and clustering in bipartite networks. Physical review E 72, 5 (2005), 056127."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313522"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3289600.3290988"},{"key":"e_1_2_1_29_1","first-page":"945","article-title":"Temporal network motifs: Models, limitations, evaluation","volume":"35","author":"Liu Penghang","year":"2021","unstructured":"Penghang Liu, Valerio Guarrasi, and Ahmet Erdem Sar\u0131y\u00fcce. 2021. Temporal network motifs: Models, limitations, evaluation. IEEE Transactions on Knowledge and Data Engineering 35, 1 (2021), 945\u2013957.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the Ninth International Conference on Complex Networks and Their Applications COMPLEX NETWORKS","author":"Locicero Giorgio","year":"2021","unstructured":"Giorgio Locicero, Giovanni Micale, Alfredo Pulvirenti, and Alfredo Ferro. 2021. TemporalRI: a subgraph isomorphism algorithm for temporal networks. In Complex Networks & Their Applications IX: Volume 2, Proceedings of the Ninth International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2020. Springer, 675\u2013687."},{"key":"e_1_2_1_31_1","volume-title":"Network motifs: simple building blocks of complex networks. Science 298, 5594","author":"Milo Ron","year":"2002","unstructured":"Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002. Network motifs: simple building blocks of complex networks. Science 298, 5594 (2002), 824\u2013827."},{"key":"e_1_2_1_32_1","volume-title":"Triadic closure in two-mode networks: Redefining the global and local clustering coefficients. Social networks 35, 2","author":"Opsahl Tore","year":"2013","unstructured":"Tore Opsahl. 2013. Triadic closure in two-mode networks: Redefining the global and local clustering coefficients. Social networks 35, 2 (2013), 159\u2013167."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018731"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 1319\u20131328","author":"Pashanasangi Noujan","year":"2021","unstructured":"Noujan Pashanasangi and C Seshadhri. 2021. Faster and generalized temporal triangle counting, via degeneracy ordering. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 1319\u20131328."},{"key":"e_1_2_1_35_1","volume-title":"Bipartite graphs in systems biology and medicine: a survey of methods and applications. GigaScience 7, 4","author":"Pavlopoulos Georgios A","year":"2018","unstructured":"Georgios A Pavlopoulos, Panagiota I Kontou, Athanasia Pavlopoulou, Costas Bouyioukos, Evripides Markou, and Pantelis G Bagos. 2018. Bipartite graphs in systems biology and medicine: a survey of methods and applications. GigaScience 7, 4 (2018), giy014."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 2013 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining. 1451\u20131452","author":"Redmond Ursula","year":"2013","unstructured":"Ursula Redmond and P\u00e1draig Cunningham. 2013. Temporal subgraph isomorphism. In Proceedings of the 2013 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining. 1451\u20131452."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220097"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357983"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 1568\u20131577","author":"Sarpe Ilie","year":"2021","unstructured":"Ilie Sarpe and Fabio Vandin. 2021. OdeN: simultaneous approximation of multiple motif counts in large temporal networks. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 1568\u20131577."},{"key":"e_1_2_1_40_1","volume-title":"sGrapp: Butterfly approximation in streaming graphs. ACM Transactions on Knowledge Discovery from Data (TKDD) 16, 4","author":"Sheshbolouki Aida","year":"2022","unstructured":"Aida Sheshbolouki and M Tamer \u00d6zsu. 2022. sGrapp: Butterfly approximation in streaming graphs. ACM Transactions on Knowledge Discovery from Data (TKDD) 16, 4 (2022), 1\u201343."},{"key":"e_1_2_1_41_1","volume-title":"Massive Graph Analytics","author":"Shi Jessica","unstructured":"Jessica Shi and Julian Shun. 2022. Parallel algorithms for butterfly computations. In Massive Graph Analytics. Chapman and Hall\/CRC, 287\u2013330."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.98.022307"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148170.1148257"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.Congress.2014.13"},{"key":"e_1_2_1_45_1","volume-title":"Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks. PVLDB","author":"Wang Kai","year":"2019","unstructured":"Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, and Ying Zhang. 2019. Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks. PVLDB (2019)."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00063"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00746-0"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588714"},{"key":"e_1_2_1_49_1","volume-title":"Span-reachability querying in large temporal graphs. The VLDB Journal","author":"Wen Dong","year":"2022","unstructured":"Dong Wen, Bohua Yang, Ying Zhang, Lu Qin, Dawei Cheng, and Wenjie Zhang. 2022. Span-reachability querying in large temporal graphs. The VLDB Journal (2022), 1\u201319."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3494523"},{"key":"e_1_2_1_51_1","volume-title":"GPU-based butterfly counting. The VLDB Journal","author":"Xia Yifei","year":"2024","unstructured":"Yifei Xia, Feng Zhang, Qingyu Xu, Mingde Zhang, Zhiming Yao, Lv Lu, Xiaoyong Du, Dong Deng, Bingsheng He, and Siqi Ma. 2024. GPU-based butterfly counting. The VLDB Journal (2024), 1\u201325."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589315"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447702"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476260"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626753"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489502"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-32049-6_14"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3725688.3725693","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T14:22:14Z","timestamp":1756477334000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3725688.3725693"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2]]},"references-count":57,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["10.14778\/3725688.3725693"],"URL":"https:\/\/doi.org\/10.14778\/3725688.3725693","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,2]]},"assertion":[{"value":"2025-08-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}