{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T23:21:05Z","timestamp":1776122465846,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":50,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T00:00:00Z","timestamp":1623196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["652976"],"award-info":[{"award-number":["652976"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"EPSRC Centre for Doctoral Training in Pervasive Parallelism","award":["EP\/L01503X\/1"],"award-info":[{"award-number":["EP\/L01503X\/1"]}]},{"name":"NSFC","award":["62002236"],"award-info":[{"award-number":["62002236"]}]},{"name":"Royal Society Wolfson Research Merit Award","award":["WRM\/R1\/180014"],"award-info":[{"award-number":["WRM\/R1\/180014"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,9]]},"DOI":"10.1145\/3448016.3452797","type":"proceedings-article","created":{"date-parts":[[2021,6,18]],"date-time":"2021-06-18T17:22:30Z","timestamp":1624036950000},"page":"472-484","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Making Graphs Compact by Lossless Contraction"],"prefix":"10.1145","author":[{"given":"Wenfei","family":"Fan","sequence":"first","affiliation":[{"name":"University of Edinburgh, Shenzhen Institute of Computing Sciences, & Beihang University, Edinburgh, England UK"}]},{"given":"Yuanhao","family":"Li","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh , England UK"}]},{"given":"Muyang","family":"Liu","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, England UK"}]},{"given":"Can","family":"Lu","sequence":"additional","affiliation":[{"name":"Shenzhen Institute of Computing Sciences, Shenzhen, China"}]}],"member":"320","published-online":{"date-parts":[[2021,6,18]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"crossref","unstructured":"Takuya Akiba Yoichi Iwata and Yuichi Yoshida. 2013. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In SIGMOD .  Takuya Akiba Yoichi Iwata and Yuichi Yoshida. 2013. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In SIGMOD .","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_3_2_2_2_1","volume-title":"The diameter of the World Wide Web. CoRR","author":"Albert R\u00e9","year":"1999","unstructured":"R\u00e9 ka Albert , Hawoong Jeong , and Albert-L\u00e1 szl\u00f3 Barab\u00e1 si. 1999. The diameter of the World Wide Web. CoRR , Vol. cond-mat\/ 9907038 ( 1999 ). R\u00e9 ka Albert, Hawoong Jeong, and Albert-L\u00e1 szl\u00f3 Barab\u00e1 si. 1999. The diameter of the World Wide Web. CoRR , Vol. cond-mat\/9907038 (1999)."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Shikha Anirban Junhu Wang and Md Saiful Islam. 2019. Multi-level graph compression for fast reachability detection. In DASFAA .  Shikha Anirban Junhu Wang and Md Saiful Islam. 2019. Multi-level graph compression for fast reachability detection. In DASFAA .","DOI":"10.1007\/978-3-030-18579-4_14"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2992785"},{"key":"e_1_3_2_2_5_1","volume-title":"Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations. CoRR","author":"Besta Maciej","year":"2018","unstructured":"Maciej Besta and Torsten Hoefler . 2018. Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations. CoRR , Vol. abs\/ 1806 .01799 ( 2018 ). Maciej Besta and Torsten Hoefler. 2018. Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations. CoRR , Vol. abs\/1806.01799 (2018)."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300086"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"crossref","unstructured":"Fei Bi Lijun Chang Xuemin Lin Lu Qin and Wenjie Zhang. 2016. Efficient subgraph matching by postponing cartesian products. In SIGMOD.  Fei Bi Lijun Chang Xuemin Lin Lu Qin and Wenjie Zhang. 2016. Efficient subgraph matching by postponing cartesian products. In SIGMOD.","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"crossref","unstructured":"Paolo Boldi and Sebastiano Vigna. 2004. The WebGraph Framework I: Compression techniques. In WWW. 595--602.  Paolo Boldi and Sebastiano Vigna. 2004. The WebGraph Framework I: Compression techniques. In WWW. 595--602.","DOI":"10.1145\/988672.988752"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.53"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"crossref","unstructured":"James Cheng Silu Huang Huanhuan Wu and Ada Wai-Chee Fu. 2013. TF-Label: A topological-folding labeling scheme for reachability querying in a large graph. In SIGMOD .  James Cheng Silu Huang Huanhuan Wu and Ada Wai-Chee Fu. 2013. TF-Label: A topological-folding labeling scheme for reachability querying in a large graph. In SIGMOD .","DOI":"10.1145\/2463676.2465286"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_3_2_2_12_1","volume-title":"Trusses: Cohesive subgraphs for social network analysis. National security agency technical report","author":"Cohen Jonathan","year":"2008","unstructured":"Jonathan Cohen . 2008 . Trusses: Cohesive subgraphs for social network analysis. National security agency technical report , Vol. 16 (2008), 3--1. Jonathan Cohen. 2008. Trusses: Cohesive subgraphs for social network analysis. National security agency technical report , Vol. 16 (2008), 3--1."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"crossref","unstructured":"Sara Cohen. 2016. Data management for social networking. In SIGMOD .  Sara Cohen. 2016. Data management for social networking. In SIGMOD .","DOI":"10.1145\/2902251.2902306"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44816-0_11"},{"key":"e_1_3_2_2_16_1","volume-title":"mbox","author":"Dijkstra Edsger W","year":"1959","unstructured":"Edsger W Dijkstra mbox . 1959 . A note on two problems in connexion with graphs. Numerische mathematik , Vol. 1 , 1 (1959), 269--271. Edsger W Dijkstra et almbox. 1959. A note on two problems in connexion with graphs. Numerische mathematik , Vol. 1, 1 (1959), 269--271."},{"key":"e_1_3_2_2_17_1","volume-title":"Technology Conference on Performance Evaluation and Benchmarking. 25--40","author":"Dominguez-Sal David","year":"2010","unstructured":"David Dominguez-Sal , Norbert Martinez-Bazan , Victor Muntes-Mulero , Pere Baleta , and Josep Lluis Larriba-Pey . 2010 . A discussion on the design of graph database benchmarks . In Technology Conference on Performance Evaluation and Benchmarking. 25--40 . David Dominguez-Sal, Norbert Martinez-Bazan, Victor Muntes-Mulero, Pere Baleta, and Josep Lluis Larriba-Pey. 2010. A discussion on the design of graph database benchmarks. In Technology Conference on Performance Evaluation and Benchmarking. 25--40."},{"key":"e_1_3_2_2_18_1","volume-title":"StarIso: Graph Isomorphism Through Lossy Compression. In 2016 Data Compression Conference (DCC) .","author":"Fairey J.","unstructured":"J. Fairey and L. Holder . 2016 . StarIso: Graph Isomorphism Through Lossy Compression. In 2016 Data Compression Conference (DCC) . J. Fairey and L. Holder. 2016. StarIso: Graph Isomorphism Through Lossy Compression. In 2016 Data Compression Conference (DCC) ."},{"key":"e_1_3_2_2_19_1","unstructured":"Wenfei Fan Chunming Hu and Chao Tian. 2017. Incremental graph computations: Doable and undoable. In SIGMOD.  Wenfei Fan Chunming Hu and Chao Tian. 2017. Incremental graph computations: Doable and undoable. In SIGMOD."},{"key":"e_1_3_2_2_20_1","unstructured":"Wenfei Fan Jianzhong Li Xin Wang and Yinghui Wu. 2012. Query preserving graph compression. In SIGMOD .  Wenfei Fan Jianzhong Li Xin Wang and Yinghui Wu. 2012. Query preserving graph compression. In SIGMOD ."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Harold N Gabow Zvi Galil and Thomas H Spencer. 1984. Efficient implementation of graph algorithms using contraction. In FOCS .  Harold N Gabow Zvi Galil and Thomas H Spencer. 1984. Efficient implementation of graph algorithms using contraction. In FOCS .","DOI":"10.1109\/SFCS.1984.715935"},{"key":"e_1_3_2_2_22_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey Michael","unstructured":"Michael Garey and David Johnson . 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman and Company . Michael Garey and David Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness .W. H. Freeman and Company."},{"key":"e_1_3_2_2_23_1","volume-title":"Graph Theory and its applications","author":"Gross Jonathan","unstructured":"Jonathan Gross and Jay Yellen . 1998. Graph Theory and its applications . CRC Press . Jonathan Gross and Jay Yellen. 1998. Graph Theory and its applications .CRC Press."},{"key":"e_1_3_2_2_24_1","unstructured":"Wook-Shin Han Jinsoo Lee and Jeong-Hoon Lee. 2013. Turbo$_rm iso$: Towards ultrafast and robust subgraph isomorphism search in large graph databases. In SIGMOD.  Wook-Shin Han Jinsoo Lee and Jeong-Hoon Lee. 2013. Turbo$_rm iso$: Towards ultrafast and robust subgraph isomorphism search in large graph databases. In SIGMOD."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1198\/106186006X139162"},{"key":"e_1_3_2_2_26_1","unstructured":"Xiaocheng Hu Yufei Tao and Chin-Wan Chung. 2013. Massive graph triangulation. In SIGMOD .  Xiaocheng Hu Yufei Tao and Chin-Wan Chung. 2013. Massive graph triangulation. In SIGMOD ."},{"key":"e_1_3_2_2_27_1","unstructured":"Ruoming Jin Yang Xiang Ning Ruan and Haixun Wang. 2008. Efficiently answering reachability queries on very large directed graphs. In SIGMOD .  Ruoming Jin Yang Xiang Ning Ruan and Haixun Wang. 2008. Efficiently answering reachability queries on very large directed graphs. In SIGMOD ."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"crossref","unstructured":"Roozbeh Karimi David M Koppelman and Chris J Michael. 2019. GPU road network graph contraction and SSSP query. In ICS .  Roozbeh Karimi David M Koppelman and Chris J Michael. 2019. GPU road network graph contraction and SSSP query. In ICS .","DOI":"10.1145\/3330345.3330368"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"crossref","unstructured":"Walter Kropatsch. 1996. Building irregular pyramids by dual-graph contraction. In Vision Image and Signal Processing .  Walter Kropatsch. 1996. Building irregular pyramids by dual-graph contraction. In Vision Image and Signal Processing .","DOI":"10.1049\/ip-vis:19952115"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"crossref","unstructured":"Kristen LeFevre and Evimaria Terzi. 2010. GraSS: Graph structure summarization. In SDM .  Kristen LeFevre and Evimaria Terzi. 2010. GraSS: Graph structure summarization. In SDM .","DOI":"10.1137\/1.9781611972801.40"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"crossref","unstructured":"Jure Leskovec Jon M. Kleinberg and Christos Faloutsos. 2005. Graphs over time: Densification laws shrinking diameters and possible explanations. In SIGKDD .  Jure Leskovec Jon M. Kleinberg and Christos Faloutsos. 2005. Graphs over time: Densification laws shrinking diameters and possible explanations. In SIGKDD .","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_3_2_2_33_1","volume-title":"Mahoney","author":"Leskovec Jure","year":"2008","unstructured":"Jure Leskovec , Kevin J. Lang , Anirban Dasgupta , and Michael W . Mahoney . 2008 . Community Structure in Large Networks : Natural Cluster Sizes and the Absence of Large Well-Defined Clusters. CoRR , Vol. abs\/ 0810 .1355 (2008). Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, and Michael W. Mahoney. 2008. Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters. CoRR , Vol. abs\/0810.1355 (2008)."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"crossref","unstructured":"Yongjiang Liang and Peixiang Zhao. 2017. Similarity search in graph databases: A multi-layered indexing approach. In ICDE .  Yongjiang Liang and Peixiang Zhao. 2017. Similarity search in graph databases: A multi-layered indexing approach. In ICDE .","DOI":"10.1109\/ICDE.2017.129"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186727"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137660"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"crossref","unstructured":"Antonio Maccioni and Daniel J Abadi. 2016. Scalable pattern matching over compressed graphs via dedensification. In SIGKDD .  Antonio Maccioni and Daniel J Abadi. 2016. Scalable pattern matching over compressed graphs via dedensification. In SIGKDD .","DOI":"10.1145\/2939672.2939856"},{"key":"e_1_3_2_2_38_1","unstructured":"Julian McAuley and Jure Leskovec. 2012. Learning to Discover Social Circles in Ego Networks. In NIPS .  Julian McAuley and Jure Leskovec. 2012. Learning to Discover Social Circles in Ego Networks. In NIPS ."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"crossref","unstructured":"Han Myoungji Kim Hyunjoon Gu Geonmo Park Kunsoo and Han Wook-Shin. 2019. Efficient Subgraph Matching: Harmonizing Dynamic Programming Adaptive Matching Order and Failing Set Together. In SIGMOD.  Han Myoungji Kim Hyunjoon Gu Geonmo Park Kunsoo and Han Wook-Shin. 2019. Efficient Subgraph Matching: Harmonizing Dynamic Programming Adaptive Matching Order and Failing Set Together. In SIGMOD.","DOI":"10.1145\/3299869.3319880"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"crossref","unstructured":"Saket Navlakha Rajeev Rastogi and Nisheeth Shrivastava. 2008. Graph summarization with bounded error. In SIGMOD .  Saket Navlakha Rajeev Rastogi and Nisheeth Shrivastava. 2008. Graph summarization with bounded error. In SIGMOD .","DOI":"10.1145\/1376616.1376661"},{"key":"e_1_3_2_2_41_1","volume-title":"H-INDEX: Hash-Indexing for Parallel Triangle Counting on GPUs. In IEEE High Performance Extreme Computing Conference. 1--7.","author":"Pandey Santosh","year":"2019","unstructured":"Santosh Pandey , Xiaoye Sherry Li , Aydin Buluc , Jiejun Xu , and Hang Liu . 2019 . H-INDEX: Hash-Indexing for Parallel Triangle Counting on GPUs. In IEEE High Performance Extreme Computing Conference. 1--7. Santosh Pandey, Xiaoye Sherry Li, Aydin Buluc, Jiejun Xu, and Hang Liu. 2019. H-INDEX: Hash-Indexing for Parallel Triangle Counting on GPUs. In IEEE High Performance Extreme Computing Conference. 1--7."},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00079-8"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735493"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1108\/17440081011053104"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2006.107"},{"key":"e_1_3_2_2_46_1","volume-title":"Brian Gallagher, and Kevin Roundy.","author":"Soundarajan Sucheta","year":"2016","unstructured":"Sucheta Soundarajan , Acar Tamersoy , Elias B Khalil , Tina Eliassi-Rad , Duen Horng Chau , Brian Gallagher, and Kevin Roundy. 2016 . Generating graph snapshots from streaming edge data. In WWW . Sucheta Soundarajan, Acar Tamersoy, Elias B Khalil, Tina Eliassi-Rad, Duen Horng Chau, Brian Gallagher, and Kevin Roundy. 2016. Generating graph snapshots from streaming edge data. In WWW ."},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"crossref","unstructured":"Yuanyuan Tian Richard A Hankins and Jignesh M Patel. 2008. Efficient aggregation for graph summarization. In SIGMOD .  Yuanyuan Tian Richard A Hankins and Jignesh M Patel. 2008. Efficient aggregation for graph summarization. In SIGMOD .","DOI":"10.1145\/1376616.1376675"},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2515579"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"crossref","unstructured":"Jaewon Yang and Jure Leskovec. 2012. Defining and Evaluating Network Communities Based on Ground-Truth. In ICDM .  Jaewon Yang and Jure Leskovec. 2012. Defining and Evaluating Network Communities Based on Ground-Truth. In ICDM .","DOI":"10.1109\/ICDM.2012.138"},{"key":"e_1_3_2_2_50_1","first-page":"1","article-title":"GRAIL","volume":"3","author":"Yildirim Hilmi","year":"2010","unstructured":"Hilmi Yildirim , Vineet Chaoji , and Mohammed J. Zaki . 2010 . GRAIL : Scalable Reachability Index for Large Graphs. PVLDB , Vol. 3 , 1 -- 2 (2010), 276--284. Hilmi Yildirim, Vineet Chaoji, and Mohammed J. Zaki. 2010. GRAIL: Scalable Reachability Index for Large Graphs. PVLDB , Vol. 3, 1--2 (2010), 276--284.","journal-title":"Scalable Reachability Index for Large Graphs. PVLDB"}],"event":{"name":"SIGMOD\/PODS '21: International Conference on Management of Data","location":"Virtual Event China","acronym":"SIGMOD\/PODS '21","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 2021 International Conference on Management of Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448016.3452797","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448016.3452797","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:05Z","timestamp":1750195685000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448016.3452797"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,9]]},"references-count":50,"alternative-id":["10.1145\/3448016.3452797","10.1145\/3448016"],"URL":"https:\/\/doi.org\/10.1145\/3448016.3452797","relation":{},"subject":[],"published":{"date-parts":[[2021,6,9]]},"assertion":[{"value":"2021-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}