{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T01:39:44Z","timestamp":1784597984309,"version":"3.55.0"},"reference-count":78,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,11]]},"abstract":"<jats:p>Graph sparsification is a technique that approximates a given graph by a sparse graph with a subset of vertices and\/or edges. The goal of an effective sparsification algorithm is to maintain specific graph properties relevant to the downstream task while minimizing the graph's size. Graph algorithms often suffer from long execution time due to the irregularity and the large real-world graph size. Graph sparsification can be applied to greatly reduce the run time of graph algorithms by substituting the full graph with a much smaller sparsified graph, without significantly degrading the output quality. However, the interaction between numerous sparsifiers and graph properties is not widely explored, and the potential of graph sparsification is not fully understood.<\/jats:p>\n          <jats:p>In this work, we cover 16 widely-used graph metrics, 12 representative graph sparsification algorithms, and 14 real-world input graphs spanning various categories, exhibiting diverse characteristics, sizes, and densities. We developed a framework to extensively assess the performance of these sparsification algorithms against graph metrics, and provide insights to the results. Our study shows that there is no one sparsifier that performs the best in preserving all graph properties, e.g. sparsifiers that preserve distance-related graph properties (eccentricity) struggle to perform well on Graph Neural Networks (GNN). This paper presents a comprehensive experimental study evaluating the performance of sparsification algorithms in preserving essential graph metrics. The insights inform future research in incorporating matching graph sparsification to graph algorithms to maximize benefits while minimizing quality degradation. Furthermore, we provide a framework to facilitate the future evaluation of evolving sparsification algorithms, graph metrics, and ever-growing graph data.<\/jats:p>","DOI":"10.14778\/3632093.3632106","type":"journal-article","created":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T11:26:31Z","timestamp":1705749991000},"page":"427-440","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Demystifying Graph Sparsification Algorithms in Graph Properties Preservation"],"prefix":"10.14778","volume":"17","author":[{"given":"Yuhan","family":"Chen","sequence":"first","affiliation":[{"name":"University of Michigan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haojie","family":"Ye","sequence":"additional","affiliation":[{"name":"University of Michigan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanketh","family":"Vedula","sequence":"additional","affiliation":[{"name":"Technion"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alex","family":"Bronstein","sequence":"additional","affiliation":[{"name":"Technion"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ronald","family":"Dreslinski","sequence":"additional","affiliation":[{"name":"University of Michigan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Trevor","family":"Mudge","sequence":"additional","affiliation":[{"name":"University of Michigan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nishil","family":"Talati","sequence":"additional","affiliation":[{"name":"University of Michigan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,1,20]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2022. Spanning Tree. https:\/\/en.wikipedia.org\/wiki\/Spanning_tree (last accessed date: 11\/15\/2023)."},{"key":"e_1_2_1_2_1","unstructured":"2022. Tree (graph theory). https:\/\/en.wikipedia.org\/wiki\/Tree_(graph_theory) (last accessed date: 11\/15\/2023)."},{"key":"e_1_2_1_3_1","unstructured":"2023. Clustering coefficient. https:\/\/en.wikipedia.org\/wiki\/Clustering_coefficient (last accessed date: 11\/15\/2023)."},{"key":"e_1_2_1_4_1","unstructured":"2023. Connected graph. https:\/\/mathworld.wolfram.com\/ConnectedGraph.html (last accessed date: 11\/15\/2023)."},{"key":"e_1_2_1_5_1","unstructured":"2023. Cut (graph theory). https:\/\/en.wikipedia.org\/wiki\/Cut_(graph_theory) (last accessed date: 11\/15\/2023)."},{"key":"e_1_2_1_6_1","unstructured":"2023. Eigenvector centrality. https:\/\/en.wikipedia.org\/wiki\/Eigenvector_centrality (last accessed date: 11\/15\/2023)."},{"key":"e_1_2_1_7_1","volume-title":"Orlin","author":"Ahuja Ravindra K.","year":"1993","unstructured":"Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc., USA."},{"key":"e_1_2_1_8_1","volume-title":"SWAT 90, John R","author":"Alth\u00f6fer Ingo","unstructured":"Ingo Alth\u00f6fer, Gautam Das, David Dobkin, and Deborah Joseph. 1990. Generating sparse spanners for weighted graphs. In SWAT 90, John R. Gilbert and Rolf Karlsson (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 26--37."},{"key":"e_1_2_1_9_1","volume-title":"Advances in Neural Information Processing Systems","author":"Belkin Mikhail","year":"2001","unstructured":"Mikhail Belkin and Partha Niyogi. 2001. Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering. In Advances in Neural Information Processing Systems, T. Dietterich, S. Becker, and Z. Ghahramani (Eds.), Vol. 14. MIT Press. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2001\/file\/f106b7f99d2cb30c3db1c3cc0fde9ccb-Paper.pdf"},{"key":"e_1_2_1_10_1","unstructured":"Elisabetta Bergamini Michele Borassi Pierluigi Crescenzi Andrea Marino and Henning Meyerhenke. 2017. Computing top-k Closeness Centrality Faster in Unweighted Graphs. arXiv:1704.01077 [cs.DS]"},{"key":"e_1_2_1_11_1","volume-title":"On a Measure of Divergence between Two Multinomial Populations","author":"Bhattacharyya A.","year":"1933","unstructured":"A. Bhattacharyya. 1946. On a Measure of Divergence between Two Multinomial Populations. Sankhy\u0101: The Indian Journal of Statistics (1933--1960) 7, 4 (1946), 401--406. http:\/\/www.jstor.org\/stable\/25047882"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/p10008"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1057\/s41289-018-0072-1"},{"key":"e_1_2_1_14_1","volume-title":"Graph Theory with Applications","author":"Bondy J. A.","unstructured":"J. A. Bondy and U. S. R. Murty. 1976. Graph Theory with Applications. Elsevier, New York."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_16_1","volume-title":"Structural Holes: The Social Structure of Competition","author":"RONALD S.","year":"1992","unstructured":"RONALD S. BURT. 1992. Structural Holes: The Social Structure of Competition. http:\/\/www.jstor.org\/stable\/j.ctv1kz4h78."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 26th Design, Automation, and Test in Europe (DATE) conference (DATE","author":"Chen Yuhan","year":"2023","unstructured":"Yuhan Chen, Alireza Khadem, Xin He, Nishil Talati, Tanvir Ahmed Khan, and Trevor Mudge. 2023. PEDAL: A Power Efficient GCN Accelerator with Multiple DAtafLows. In Proceedings of the 26th Design, Automation, and Test in Europe (DATE) conference (DATE 2023)."},{"key":"e_1_2_1_18_1","volume-title":"REWIRE: An Optimization-based Framework for Data Center Network Design.","author":"Curtis Andrew R.","year":"2011","unstructured":"Andrew R. Curtis, Tommy Carpenter, and S. Keshav. 2011. REWIRE: An Optimization-based Framework for Data Center Network Design. (2011)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","unstructured":"Micha\u00ebl Defferrard Xavier Bresson and Pierre Vandergheynst. 2016. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. (2016). 10.48550\/ARXIV.1606.09375","DOI":"10.48550\/ARXIV.1606.09375"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","unstructured":"Andac Demir Toshiaki Koike-Akino Ye Wang Masaki Haruna and Deniz Erdogmus. 2021. EEG-GNN: Graph Neural Networks for Classification of Electroencephalogram (EEG) Signals. In 2021 43rd Annual International Conference of the IEEE Engineering in Medicine & Biology Society (EMBC). 1061--1067. 10.1109\/EMBC46164.2021.9630194","DOI":"10.1109\/EMBC46164.2021.9630194"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1030194.1015483"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/3001460.3001507"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2005.10.010"},{"key":"e_1_2_1_26_1","volume-title":"Fast Graph Representation Learning with PyTorch Geometric. CoRR abs\/1903.02428","author":"Fey Matthias","year":"2019","unstructured":"Matthias Fey and Jan Eric Lenssen. 2019. Fast Graph Representation Learning with PyTorch Geometric. CoRR abs\/1903.02428 (2019). arXiv:1903.02428"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.21136\/CMJ.1973.101168"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1142\/s0129065717500137"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_2_1_30_1","volume-title":"The Development of Social Network Analysis. (01","author":"Freeman Linton","year":"2004","unstructured":"Linton Freeman. 2004. The Development of Social Network Analysis. (01 2004)."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2791204.2791213"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1093\/molbev\/msi072"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Michael Hamann Gerd Lindner Henning Meyerhenke Christian L. Staudt and Dorothea Wagner. 2016. Structure-Preserving Sparsification Methods for Social Networks. arXiv:1601.00286 [cs.SI]","DOI":"10.1007\/s13278-016-0332-2"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/3294771.3294869"},{"key":"e_1_2_1_35_1","volume-title":"Open Graph Benchmark: Datasets for Machine Learning on Graphs. arXiv preprint arXiv:2005.00687","author":"Hu Weihua","year":"2020","unstructured":"Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open Graph Benchmark: Datasets for Machine Learning on Graphs. arXiv preprint arXiv:2005.00687 (2020)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1038\/35036627"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289026"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.1609.02907"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Joseph B. Kruskal. 1956. On the shortest spanning subtree of a graph and the traveling salesman problem.","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1217299.1217301","article-title":"Graph evolution: Densification and shrinking diameters","volume":"1","author":"Leskovec Jure","year":"2006","unstructured":"Jure Leskovec, Jon M. Kleinberg, and Christos Faloutsos. 2006. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data 1 (2006), 2.","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"e_1_2_1_41_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357951"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289146"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btg177"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/505659.505663"},{"key":"e_1_2_1_47_1","unstructured":"Vijini Mallawaarachchi. 2020. Evaluating clustering results. https:\/\/towardsdatascience.com\/evaluating-clustering-results-f13552ee7603"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1175\/1520-0434(1996)011"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","unstructured":"Daniel M\u00fcllner. 2011. Modern hierarchical agglomerative clustering algorithms. 10.48550\/ARXIV.1109.2378","DOI":"10.48550\/ARXIV.1109.2378"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0307545100"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1057\/978-1-349-95121-5_2565-1"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic","author":"Ng Andrew Y.","year":"2001","unstructured":"Andrew Y. Ng, Michael I. Jordan, and Yair Weiss. 2001. On Spectral Clustering: Analysis and an Algorithm. In Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic (Vancouver, British Columbia, Canada) (NIPS'01). MIT Press, Cambridge, MA, USA, 849--856."},{"key":"e_1_2_1_53_1","volume-title":"The Web Conference.","author":"Page Lawrence","year":"1999","unstructured":"Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The PageRank Citation Ranking : Bringing Order to the Web. In The Web Conference."},{"key":"e_1_2_1_54_1","volume-title":"Using graph theory to analyze biological networks. BioData mining 4","author":"Pavlopoulos Georgios A","year":"2011","unstructured":"Georgios A Pavlopoulos, Maria Secrier, Charalampos N Moschopoulos, Theodoros G Soldatos, Sophia Kossida, Jan Aerts, Reinhard Schneider, and Pantelis G Bagos. 2011. Using graph theory to analyze biological networks. BioData mining 4 (2011), 1--27."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.6084\/m9.figshare.1164194"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4099"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2023.01.003"},{"key":"e_1_2_1_59_1","unstructured":"Amedeo R. Odoni Richard C. Larsona. 1981. Urban operations research. (1981)."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","unstructured":"Yu Rong Wenbing Huang Tingyang Xu and Junzhou Huang. 2019. DropEdge: Towards Deep Graph Convolutional Networks on Node Classification. 10.48550\/ARXIV.1907.10903","DOI":"10.48550\/ARXIV.1907.10903"},{"key":"e_1_2_1_61_1","volume-title":"Graph Sparsification Approaches for Laplacian Smoothing. In International Conference on Artificial Intelligence and Statistics.","author":"Sadhanala Veeranjaneyulu","unstructured":"Veeranjaneyulu Sadhanala, Yu-Xiang Wang, and Ryan J. Tibshirani. 2016. Graph Sparsification Approaches for Laplacian Smoothing. In International Conference on Artificial Intelligence and Statistics."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989399"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2008.2005605"},{"key":"e_1_2_1_64_1","volume-title":"Centrality and Connectivity in Public Transport Networks and their Significance for Transport Sustainability in Cities. (07","author":"Scheurer Jan","year":"2006","unstructured":"Jan Scheurer and Sergio Porta. 2006. Centrality and Connectivity in Public Transport Networks and their Significance for Transport Sustainability in Cities. (07 2006)."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2018.00052"},{"key":"e_1_2_1_66_1","unstructured":"Daniel Spielman. 2023. Laplacians.jl. https:\/\/github.com\/danspielman\/Laplacians.jl."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","unstructured":"Christian L. Staudt Aleksejs Sazonovs and Henning Meyerhenke. 2014. NetworKit: A Tool Suite for Large-scale Complex Network Analysis. 10.48550\/ARXIV.1403.3005","DOI":"10.48550\/ARXIV.1403.3005"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gky1131"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.3390\/a6010100"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO56248.2022.00089"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","unstructured":"Petar Veli\u0107kovi\u0107 Guillem Cucurull Arantxa Casanova Adriana Romero Pietro Li\u00f2 and Yoshua Bengio. 2017. Graph Attention Networks. 10.48550\/ARXIV.1710.10903","DOI":"10.48550\/ARXIV.1710.10903"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2016.7752223"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM54844.2022.00158"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281280"},{"key":"e_1_2_1_77_1","volume-title":"Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research), Hal Daum\u00e9 III and Aarti Singh (Eds.)","volume":"119","author":"Zheng Cheng","year":"2020","unstructured":"Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. 2020. Robust Graph Representation Learning via Neural Sparsification. In Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research), Hal Daum\u00e9 III and Aarti Singh (Eds.), Vol. 119. PMLR, 11458--11468. https:\/\/proceedings.mlr.press\/v119\/zheng20d.html"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3358106"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3632093.3632106","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T11:33:16Z","timestamp":1705750396000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3632093.3632106"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11]]},"references-count":78,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["10.14778\/3632093.3632106"],"URL":"https:\/\/doi.org\/10.14778\/3632093.3632106","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,11]]},"assertion":[{"value":"2024-01-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}