{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T17:17:06Z","timestamp":1780766226825,"version":"3.54.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:p>Butterfly counting is an important and costly operation for large bipartite graphs. GPUs are popular parallel heterogeneous devices and can bring significant performance improvement for data science applications. Unfortunately, no work enables efficient butterfly counting on GPU currently. To fill this gap, we propose a GPU-based butterfly counting, called G-BFC. G-BFC addresses three main technical challenges. First, butterfly counting involves massive serial operations, which leads to severe synchronization overheads and performance degradation. We unlock the serial region and utilize the shared memory on GPU to efficiently handle it. Second, butterfly counting on GPU faces the workload imbalance problem. We develop a novel adaptive strategy to balance the workload among threads for efficiency. Third, butterfly counting in parallel suffers from the traversal of the huge amount of two-hop paths, also called wedges, in bipartite graphs. We develop a novel preprocessing strategy, which can effectively reduce the number of wedges to be traversed. Experiments show that G-BFC brings significant performance benefits. On eleven real datasets, G-BFC achieves 19.8X performance speedup over the state-of-the-art solution.<\/jats:p>","DOI":"10.14778\/3551793.3551806","type":"journal-article","created":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T22:25:03Z","timestamp":1664490303000},"page":"2450-2462","source":"Crossref","is-referenced-by-count":16,"title":["Efficient load-balanced butterfly counting on GPU"],"prefix":"10.14778","volume":"15","author":[{"given":"Qingyu","family":"Xu","sequence":"first","affiliation":[{"name":"Renmin University of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Feng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Renmin University of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhiming","family":"Yao","sequence":"additional","affiliation":[{"name":"Renmin University of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lv","family":"Lu","sequence":"additional","affiliation":[{"name":"Renmin University of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaoyong","family":"Du","sequence":"additional","affiliation":[{"name":"Renmin University of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dong","family":"Deng","sequence":"additional","affiliation":[{"name":"Rutgers University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bingsheng","family":"He","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,9,29]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2021. https:\/\/www.taobao.com\/about\/intro.php  2021. https:\/\/www.taobao.com\/about\/intro.php"},{"key":"e_1_2_1_2_1","unstructured":"2021. https:\/\/ssc.io\/trackingthetrackers\/  2021. https:\/\/ssc.io\/trackingthetrackers\/"},{"key":"e_1_2_1_3_1","unstructured":"2021. http:\/\/konect.cc  2021. http:\/\/konect.cc"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1093\/comnet\/cnx001"},{"key":"e_1_2_1_5_1","volume-title":"2015 IEEE International Parallel and Distributed Processing Symposium Workshop. IEEE, 804--811","author":"Azad A.","unstructured":"A. Azad , A. Buluc , and J. Gilbert . 2015. Parallel triangle counting and enumeration using matrix algebra . In 2015 IEEE International Parallel and Distributed Processing Symposium Workshop. IEEE, 804--811 . A. Azad, A. Buluc, and J. Gilbert. 2015. Parallel triangle counting and enumeration using matrix algebra. In 2015 IEEE International Parallel and Distributed Processing Symposium Workshop. IEEE, 804--811."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488400"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2735405"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2004-00020-6"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.271"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389137"},{"key":"e_1_2_1_11_1","volume-title":"Trusses: Cohesive subgraphs for social network analysis. National security agency technical report 16, 3.1","author":"Cohen Jonathan","year":"2008","unstructured":"Jonathan Cohen . 2008 . Trusses: Cohesive subgraphs for social network analysis. National security agency technical report 16, 3.1 (2008). Jonathan Cohen. 2008. Trusses: Cohesive subgraphs for social network analysis. National security agency technical report 16, 3.1 (2008)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.inffus.2018.08.002"},{"key":"e_1_2_1_13_1","volume-title":"Fast and adaptive list intersections on the GPU. In 2018 IEEE High Performance extreme Computing Conference (HPEC)","author":"Fox James","unstructured":"James Fox , Oded Green , Kasimir Gabert , Xiaojing An , and David A Bader . 2018. Fast and adaptive list intersections on the GPU. In 2018 IEEE High Performance extreme Computing Conference (HPEC) . IEEE , 1--7. James Fox, Oded Green, Kasimir Gabert, Xiaojing An, and David A Bader. 2018. Fast and adaptive list intersections on the GPU. In 2018 IEEE High Performance extreme Computing Conference (HPEC). IEEE, 1--7."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083676"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.68"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 4th Workshop on Irregular Applications: Architectures and Algorithms. 1--8.","author":"Green O.","unstructured":"O. Green , P. Yalamanchili , and L. M. Munguia . 2014. Fast triangle counting on the GPU . In Proceedings of the 4th Workshop on Irregular Applications: Architectures and Algorithms. 1--8. O. Green, P. Yalamanchili, and L. M. Munguia. 2014. Fast triangle counting on the GPU. In Proceedings of the 4th Workshop on Irregular Applications: Architectures and Algorithms. 1--8."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452815"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2018.00017"},{"key":"e_1_2_1_19_1","volume-title":"Link prediction based on graph topology: The predictive value of generalized clustering coefficient. Available at SSRN 1634014","author":"Huang Zan","year":"2010","unstructured":"Zan Huang . 2010. Link prediction based on graph topology: The predictive value of generalized clustering coefficient. Available at SSRN 1634014 ( 2010 ). Zan Huang. 2010. Link prediction based on graph topology: The predictive value of generalized clustering coefficient. Available at SSRN 1634014 (2010)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052636"},{"key":"e_1_2_1_21_1","volume-title":"NextDoor: GPU-Based Graph Sampling for Graph Machine Learning. arXiv preprint arXiv:2009.06693","author":"Jangda Abhinav","year":"2020","unstructured":"Abhinav Jangda , Sandeep Polisetty , Arjun Guha , and Marco Serafini . 2020. NextDoor: GPU-Based Graph Sampling for Graph Machine Learning. arXiv preprint arXiv:2009.06693 ( 2020 ). Abhinav Jangda, Sandeep Polisetty, Arjun Guha, and Marco Serafini. 2020. NextDoor: GPU-Based Graph Sampling for Graph Machine Learning. arXiv preprint arXiv:2009.06693 (2020)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850471"},{"key":"e_1_2_1_23_1","volume-title":"Multiplicative attribute graph model of real-world networks. Internet mathematics 8, 1--2","author":"Kim Myunghwan","year":"2012","unstructured":"Myunghwan Kim and Jure Leskovec . 2012. Multiplicative attribute graph model of real-world networks. Internet mathematics 8, 1--2 ( 2012 ), 113--160. Myunghwan Kim and Jure Leskovec. 2012. Multiplicative attribute graph model of real-world networks. Internet mathematics 8, 1--2 (2012), 113--160."},{"key":"e_1_2_1_24_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. 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_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCGrid.2011.13"},{"key":"e_1_2_1_26_1","volume-title":"Maximum biclique search at billion scale. PVLDB","author":"Lyu Bingqing","year":"2020","unstructured":"Bingqing Lyu , Lu Qin , Xuemin Lin , Ying Zhang , Zhengping Qian , and Jingren Zhou . 2020. Maximum biclique search at billion scale. PVLDB ( 2020 ). Bingqing Lyu, Lu Qin, Xuemin Lin, Ying Zhang, Zhengping Qian, and Jingren Zhou. 2020. Maximum biclique search at billion scale. PVLDB (2020)."},{"key":"e_1_2_1_27_1","first-page":"45","article-title":"Introducing the graph 500","volume":"19","author":"Murphy Richard C","year":"2010","unstructured":"Richard C Murphy , Kyle B Wheeler , Brian W Barrett , and James A Ang . 2010 . Introducing the graph 500 . Cray Users Group (CUG) 19 (2010), 45 -- 74 . Richard C Murphy, Kyle B Wheeler, Brian W Barrett, and James A Ang. 2010. Introducing the graph 500. Cray Users Group (CUG) 19 (2010), 45--74.","journal-title":"Cray Users Group (CUG)"},{"key":"e_1_2_1_28_1","series-title":"SIAM review 45, 2","volume-title":"The structure and function of complex networks","author":"Newman Mark EJ","year":"2003","unstructured":"Mark EJ Newman . 2003. The structure and function of complex networks . SIAM review 45, 2 ( 2003 ), 167--256. Mark EJ Newman. 2003. The structure and function of complex networks. SIAM review 45, 2 (2003), 167--256."},{"key":"e_1_2_1_29_1","volume-title":"Broken ties: Interlocking directorates and intercorporate coordination. Administrative Science Quarterly","author":"Palmer Donald","year":"1983","unstructured":"Donald Palmer . 1983. Broken ties: Interlocking directorates and intercorporate coordination. Administrative Science Quarterly ( 1983 ), 40--55. Donald Palmer. 1983. Broken ties: Interlocking directorates and intercorporate coordination. Administrative Science Quarterly (1983), 40--55."},{"key":"e_1_2_1_30_1","volume-title":"Exploring Data Analytics without Decompression on Embedded GPU Systems","author":"Pan Zaifeng","year":"2021","unstructured":"Zaifeng Pan , Feng Zhang , Yanliang Zhou , Jidong Zhai , Xipeng Shen , Onur Mutlu , and Xiaoyong Du. 2021. Exploring Data Analytics without Decompression on Embedded GPU Systems . IEEE Transactions on Parallel and Distributed Systems ( 2021 ). Zaifeng Pan, Feng Zhang, Yanliang Zhou, Jidong Zhai, Xipeng Shen, Onur Mutlu, and Xiaoyong Du. 2021. Exploring Data Analytics without Decompression on Embedded GPU Systems. IEEE Transactions on Parallel and Distributed Systems (2021)."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2019.8916492"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052597"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398454"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:CMOT.0000032580.12184.c0"},{"key":"e_1_2_1_35_1","volume-title":"Ahmet Erdem Sariyuce, and Srikanta Tirthapura","author":"Sanei-Mehri Seyed-Vahid","year":"2018","unstructured":"Seyed-Vahid Sanei-Mehri , Ahmet Erdem Sariyuce, and Srikanta Tirthapura . 2018 . Butterfly Counting in Bipartite Networks. In ACM SIGKDD. 2150--2159. Seyed-Vahid Sanei-Mehri, Ahmet Erdem Sariyuce, and Srikanta Tirthapura. 2018. Butterfly Counting in Bipartite Networks. In ACM SIGKDD. 2150--2159."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining. 504--512","author":"Sariyuce A. E.","unstructured":"A. E. Sariyuce and A. Pinar . 2018. Peeling bipartite networks for dense subgraph discovery . In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining. 504--512 . A. E. Sariyuce and A. Pinar. 2018. Peeling bipartite networks for dense subgraph discovery. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining. 504--512."},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"SheshboloukiAida and Z. Tamer. 2022. sGrapp: Butterfly Approximation in Streaming Graphs. ACM Transactions on Knowledge Discovery from Data (TKDD) 16 4 (2022) 1--43.  SheshboloukiAida and Z. Tamer. 2022. sGrapp: Butterfly Approximation in Streaming Graphs. ACM Transactions on Knowledge Discovery from Data (TKDD) 16 4 (2022) 1--43.","DOI":"10.1145\/3495011"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976021.2"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC41405.2020.00104"},{"key":"e_1_2_1_40_1","volume-title":"A survey of collaborative filtering techniques. Advances in artificial intelligence 2009","author":"Su Xiaoyuan","year":"2009","unstructured":"Xiaoyuan Su and Taghi M Khoshgoftaar . 2009. A survey of collaborative filtering techniques. Advances in artificial intelligence 2009 ( 2009 ). Xiaoyuan Su and Taghi M Khoshgoftaar. 2009. A survey of collaborative filtering techniques. Advances in artificial intelligence 2009 (2009)."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2013.6799136"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.Congress.2014.13"},{"key":"e_1_2_1_43_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 ). 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_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851145"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2017.8091043"},{"key":"e_1_2_1_46_1","volume-title":"Efficient pagerank and spmv computation on amd GPUs","author":"Wu Tianji","unstructured":"Tianji Wu , Bo Wang , Yi Shan , Feng Yan , Yu Wang , and Ningyi Xu. 2010. Efficient pagerank and spmv computation on amd GPUs . In ICPP. IEEE , 81--89. Tianji Wu, Bo Wang, Yi Shan, Feng Yan, Yu Wang, and Ningyi Xu. 2010. Efficient pagerank and spmv computation on amd GPUs. In ICPP. IEEE, 81--89."},{"key":"e_1_2_1_47_1","volume-title":"Jidong Zhai, and Xiaoyong Du.","author":"Zhang Feng","year":"2021","unstructured":"Feng Zhang , Zheng Chen , Chenyang Zhang , Amelie Chi Zhou , Jidong Zhai, and Xiaoyong Du. 2021 . An efficient parallel secure machine learning framework on GPUs. IEEE Transactions on Parallel and Distributed Systems ( 2021). Feng Zhang, Zheng Chen, Chenyang Zhang, Amelie Chi Zhou, Jidong Zhai, and Xiaoyong Du. 2021. An efficient parallel secure machine learning framework on GPUs. IEEE Transactions on Parallel and Distributed Systems (2021)."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00148"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2586074"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236203"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3093234"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00636-3"},{"key":"e_1_2_1_53_1","volume-title":"Clustering coefficient and community structure of bipartite networks. Physica A: Statistical Mechanics and its Applications 387, 27","author":"Zhang Peng","year":"2008","unstructured":"Peng Zhang , Jinliang Wang , Xiaojia Li , Menghui Li , Zengru Di , and Ying Fan . 2008. Clustering coefficient and community structure of bipartite networks. Physica A: Statistical Mechanics and its Applications 387, 27 ( 2008 ), 6869--6875. Peng Zhang, Jinliang Wang, Xiaojia Li, Menghui Li, Zengru Di, and Ying Fan. 2008. Clustering coefficient and community structure of bipartite networks. Physica A: Statistical Mechanics and its Applications 387, 27 (2008), 6869--6875."},{"key":"e_1_2_1_54_1","volume-title":"Fast rectangle counting on massive networks","author":"Zhu Rong","unstructured":"Rong Zhu , Zhaonian Zou , and Jianzhong Li. 2018. Fast rectangle counting on massive networks . In ICDM. IEEE , 847--856. Rong Zhu, Zhaonian Zou, and Jianzhong Li. 2018. Fast rectangle counting on massive networks. In ICDM. IEEE, 847--856."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3551793.3551806","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:26:08Z","timestamp":1672223168000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3551793.3551806"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":54,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["10.14778\/3551793.3551806"],"URL":"https:\/\/doi.org\/10.14778\/3551793.3551806","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,7]]}}}