{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:01:59Z","timestamp":1750309319077,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,2,13]],"date-time":"2024-02-13T00:00:00Z","timestamp":1707782400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["CCF-2041519 (CAREER), CCF-2021309 (SHF), and CCF-2011412 (SHF)"],"award-info":[{"award-number":["CCF-2041519 (CAREER), CCF-2021309 (SHF), and CCF-2011412 (SHF)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2024,5,31]]},"abstract":"<jats:p>\n            Recent\n            <jats:italic>spectral graph sparsification<\/jats:italic>\n            research aims to construct ultra-sparse subgraphs for preserving the original graph spectral (structural) properties, such as the first few Laplacian eigenvalues and eigenvectors, which has led to the development of a variety of nearly-linear time numerical and graph algorithms. However, there is very limited progress for spectral sparsification of directed graphs. In this work, we prove the existence of nearly-linear-sized spectral sparsifiers for directed graphs under certain conditions. Furthermore, we introduce a practically-efficient spectral algorithm (diGRASS) for sparsifying real-world, large-scale directed graphs leveraging spectral matrix perturbation analysis. The proposed method has been evaluated using a variety of directed graphs obtained from real-world applications, showing promising results for solving directed graph Laplacians, spectral partitioning of directed graphs, and approximately computing (personalized) PageRank vectors.\n          <\/jats:p>","DOI":"10.1145\/3639568","type":"journal-article","created":{"date-parts":[[2024,1,4]],"date-time":"2024-01-04T21:35:07Z","timestamp":1704404107000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["diGRASS:\n            <u>Di<\/u>\n            rected\n            <u>Gra<\/u>\n            ph\n            <u>S<\/u>\n            pectral\n            <u>S<\/u>\n            parsification via Spectrum-Preserving Symmetrization"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3864-8673","authenticated-orcid":false,"given":"Ying","family":"Zhang","sequence":"first","affiliation":[{"name":"Stevens Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7239-6604","authenticated-orcid":false,"given":"Zhiqiang","family":"Zhao","sequence":"additional","affiliation":[{"name":"Stevens Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2989-2597","authenticated-orcid":false,"given":"Zhuo","family":"Feng","sequence":"additional","affiliation":[{"name":"Stevens Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,2,13]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_2_2","DOI":"10.1145\/2213977.2214015"},{"doi-asserted-by":"crossref","unstructured":"Reyan Ahmed Greg Bodwin Faryad Darabi Sahneh Keaton Hamm Mohammad Javad Latifi Jebelli Stephen Kobourov and Richard Spence. 2020. Graph spanners: A tutorial review. Computer Science Review 1 37 (2020) 100253.","key":"e_1_3_2_3_2","DOI":"10.1016\/j.cosrev.2020.100253"},{"doi-asserted-by":"publisher","key":"e_1_3_2_4_2","DOI":"10.1007\/BF02189308"},{"doi-asserted-by":"publisher","key":"e_1_3_2_5_2","DOI":"10.5555\/1255378.1255381"},{"doi-asserted-by":"publisher","key":"e_1_3_2_6_2","DOI":"10.1137\/090772873"},{"doi-asserted-by":"publisher","key":"e_1_3_2_7_2","DOI":"10.1145\/2492007.2492029"},{"key":"e_1_3_2_8_2","first-page":"47","volume-title":"Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC)","author":"Bencz\u00far Andr\u00e1s A","year":"1996","unstructured":"Andr\u00e1s A Bencz\u00far and David R Karger. 1996. Approximating st minimum cuts in \u00d5 (n 2) time. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC). ACM, 47\u201355."},{"doi-asserted-by":"publisher","key":"e_1_3_2_9_2","DOI":"10.1137\/1.9780898719505"},{"key":"e_1_3_2_10_2","volume-title":"Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)","author":"Cen Ruoxu","year":"2021","unstructured":"Ruoxu Cen, Yu Cheng, Debmalya Panigrahi, and Kevin Sun. 2021. Sparsification of directed graphs via cut balance. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"doi-asserted-by":"publisher","key":"e_1_3_2_11_2","DOI":"10.1145\/1993636.1993674"},{"doi-asserted-by":"publisher","key":"e_1_3_2_12_2","DOI":"10.1007\/s00026-005-0237-z"},{"doi-asserted-by":"publisher","key":"e_1_3_2_13_2","DOI":"10.1109\/FOCS.2018.00089"},{"doi-asserted-by":"publisher","key":"e_1_3_2_14_2","DOI":"10.1145\/3055399.3055463"},{"doi-asserted-by":"publisher","key":"e_1_3_2_15_2","DOI":"10.1109\/FOCS.2016.69"},{"doi-asserted-by":"crossref","unstructured":"T. Davis and Y. Hu. 2011. The university of florida sparse matrix collection. ACMTransactions on Mathematical Software 38 1 (2011) 1.","key":"e_1_3_2_16_2","DOI":"10.1145\/2049662.2049663"},{"issue":"1","key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2049662.2049663","article-title":"The university of florida sparse matrix collection","volume":"38","author":"Davis Timothy A","year":"2011","unstructured":"Timothy A Davis and Yifan Hu. 2011. The university of florida sparse matrix collection. ACM Transactions on Mathematical Software 38, 1 (2011), 1\u201325.","journal-title":"ACM Transactions on Mathematical Software"},{"doi-asserted-by":"publisher","key":"e_1_3_2_18_2","DOI":"10.1137\/050641661"},{"doi-asserted-by":"publisher","key":"e_1_3_2_19_2","DOI":"10.1145\/2897937.2898094"},{"doi-asserted-by":"publisher","key":"e_1_3_2_20_2","DOI":"10.1109\/TCAD.2020.2968543"},{"doi-asserted-by":"publisher","key":"e_1_3_2_21_2","DOI":"10.1017\/CBO9781139020411"},{"doi-asserted-by":"publisher","key":"e_1_3_2_22_2","DOI":"10.1145\/195058.195422"},{"doi-asserted-by":"publisher","key":"e_1_3_2_23_2","DOI":"10.1137\/1.9781611973402.16"},{"unstructured":"Pavel Kolev and Kurt Mehlhorn. 2015. Approximate spectral clustering: Efficiency and guarantees. arXiv preprint arXiv:1509.09188.","key":"e_1_3_2_24_2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_25_2","DOI":"10.1109\/FOCS.2010.29"},{"doi-asserted-by":"publisher","key":"e_1_3_2_26_2","DOI":"10.1109\/FOCS.2016.68"},{"doi-asserted-by":"publisher","key":"e_1_3_2_27_2","DOI":"10.1145\/3055399.3055477"},{"doi-asserted-by":"publisher","key":"e_1_3_2_28_2","DOI":"10.1145\/3055399.3055477"},{"doi-asserted-by":"publisher","key":"e_1_3_2_29_2","DOI":"10.1137\/16M1061850"},{"doi-asserted-by":"publisher","key":"e_1_3_2_30_2","DOI":"10.1109\/FOCS.2018.00044"},{"doi-asserted-by":"publisher","key":"e_1_3_2_31_2","DOI":"10.1137\/110843563"},{"doi-asserted-by":"publisher","key":"e_1_3_2_32_2","DOI":"10.1016\/j.physrep.2013.08.002"},{"doi-asserted-by":"publisher","key":"e_1_3_2_33_2","DOI":"10.5555\/541643"},{"key":"e_1_3_2_34_2","first-page":"622","volume-title":"Proceedings of the 23rd International Conference on Architectural Support for Programming Languages and Operating Systems","author":"Sabet Amir Hossein Nodehi","year":"2018","unstructured":"Amir Hossein Nodehi Sabet, Junqiao Qiu, and Zhijia Zhao. 2018. Tigr: Transforming irregular graphs for GPU-friendly graph processing. In Proceedings of the 23rd International Conference on Architectural Support for Programming Languages and Operating Systems. ACM, 622\u2013636."},{"doi-asserted-by":"publisher","key":"e_1_3_2_35_2","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_3_2_36_2","first-page":"1423","volume-title":"Proceedings of the 28th Conference on Learning Theory (COLT)","author":"Peng Richard","year":"2015","unstructured":"Richard Peng, He Sun, and Luca Zanetti. 2015. Partitioning well-clustered graphs: Spectral clustering works. In Proceedings of the 28th Conference on Learning Theory (COLT). 1423\u20131455."},{"doi-asserted-by":"publisher","key":"e_1_3_2_37_2","DOI":"10.1137\/0907058"},{"doi-asserted-by":"publisher","key":"e_1_3_2_38_2","DOI":"10.1145\/1951365.1951407"},{"doi-asserted-by":"publisher","key":"e_1_3_2_39_2","DOI":"10.1137\/080734029"},{"doi-asserted-by":"publisher","key":"e_1_3_2_40_2","DOI":"10.1109\/SFCS.1996.548468"},{"doi-asserted-by":"publisher","key":"e_1_3_2_41_2","DOI":"10.1137\/08074489X"},{"doi-asserted-by":"publisher","key":"e_1_3_2_42_2","DOI":"10.1137\/090771430"},{"doi-asserted-by":"publisher","key":"e_1_3_2_43_2","DOI":"10.1007\/s11222-007-9033-z"},{"doi-asserted-by":"publisher","key":"e_1_3_2_44_2","DOI":"10.1145\/3195970.3196114"},{"doi-asserted-by":"publisher","key":"e_1_3_2_45_2","DOI":"10.1109\/ICESS.2019.8782449"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639568","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639568","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:56Z","timestamp":1750291436000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639568"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,13]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,5,31]]}},"alternative-id":["10.1145\/3639568"],"URL":"https:\/\/doi.org\/10.1145\/3639568","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2024,2,13]]},"assertion":[{"value":"2022-03-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-06","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}