{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,2]],"date-time":"2026-08-02T23:47:49Z","timestamp":1785714469233,"version":"3.56.0"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["2202412, 62102341, 6230242"],"award-info":[{"award-number":["2202412, 62102341, 6230242"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Basic and Applied Basic Research Fund in Guangdong Province","award":["2023A1515011280"],"award-info":[{"award-number":["2023A1515011280"]}]},{"name":"Guangdong Talent Program","award":["2021QN02X826"],"award-info":[{"award-number":["2021QN02X826"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>Sparse matrices are often used to model the interactions among different objects and they are prevalent in many areas including e-commerce, social network, and biology. As one of the fundamental matrix operations, the sparse matrix chain multiplication (SMCM) aims to efficiently multiply a chain of sparse matrices, which has found various real-world applications in areas like network analysis, data mining, and machine learning. The efficiency of SMCM largely hinges on the order of multiplying the matrices, which further relies on the accurate estimation of the sparsity values of intermediate matrices. Existing matrix sparsity estimators often struggle with large sparse matrices, because they suffer from the accuracy issue in both theory and practice. To enable efficient SMCM, in this paper we introduce a novel row-wise sparsity estimator (RS-estimator), a straightforward yet effective estimator that leverages matrix structural properties to achieve efficient, accurate, and theoretically guaranteed sparsity estimation. Based on the RS-estimator, we propose a novel ordering algorithm for determining a good order of efficient SMCM. We further develop an efficient parallel SMCM algorithm by effectively utilizing multiple CPU threads. We have conducted experiments by multiplying various chains of large sparse matrices extracted from five real-world large graph datasets, and the results demonstrate the effectiveness and efficiency of our proposed methods. In particular, our SMCM algorithm is up to three orders of magnitude faster than the state-of-the-art algorithms.<\/jats:p>","DOI":"10.1145\/3654959","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-27","source":"Crossref","is-referenced-by-count":4,"title":["On Efficient Large Sparse Matrix Chain Multiplication"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-3937-8657","authenticated-orcid":false,"given":"Chunxu","family":"Lin","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, Guangdong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1463-814X","authenticated-orcid":false,"given":"Wensheng","family":"Luo","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, Guangdong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5047-8593","authenticated-orcid":false,"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, Guangdong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3243-8512","authenticated-orcid":false,"given":"Chenhao","family":"Ma","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, Guangdong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-4870-1012","authenticated-orcid":false,"given":"Xilin","family":"Liu","sequence":"additional","affiliation":[{"name":"HUAWEI CLOUD, Shenzhen, Guangdong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-3304-1389","authenticated-orcid":false,"given":"Yuchi","family":"Ma","sequence":"additional","affiliation":[{"name":"HUAWEI CLOUD, Shenzhen, Guangdong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486196"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3168804"},{"key":"e_1_2_1_3_1","volume-title":"Memory Optimized Dynamic Matrix Chain Multiplication Using Shared Memory in GPU. In International Conference on Distributed Computing and Internet Technology. 160--172","author":"Biswas Girish","year":"2021","unstructured":"Girish Biswas and Nandini Mukherjee. 2021. Memory Optimized Dynamic Matrix Chain Multiplication Using Shared Memory in GPU. In International Conference on Distributed Computing and Internet Technology. 160--172."},{"key":"e_1_2_1_4_1","first-page":"52","article-title":"SystemML's Optimizer: Plan Generation for Large-Scale Machine Learning Programs","volume":"37","author":"Boehm Matthias","year":"2014","unstructured":"Matthias Boehm, Douglas R Burdick, Alexandre V Evfimievski, Berthold Reinwald, Frederick R Reiss, Prithviraj Sen, Shirish Tatikonda, and Yuanyuan Tian. 2014. SystemML's Optimizer: Plan Generation for Large-Scale Machine Learning Programs. IEEE Data Eng. Bull. 37, 3 (2014), 52--62.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2008.45"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2008.4536313"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250877"},{"key":"e_1_2_1_8_1","volume-title":"arXiv preprint arXiv:2201.04058","author":"Chatzopoulos Serafeim","year":"2022","unstructured":"Serafeim Chatzopoulos, Thanasis Vergoulis, Dimitrios Skoutas, Theodore Dalamagas, Christos Tryfonopoulos, and Panagiotis Karras. 2022. arXiv preprint arXiv:2201.04058 (2022)."},{"key":"e_1_2_1_9_1","volume-title":"Performance-aware model for sparse matrix-matrix multiplication on the sunway taihulight supercomputer","author":"Chen Yuedan","year":"2018","unstructured":"Yuedan Chen, Kenli Li, Wangdong Yang, Guoqing Xiao, Xianghui Xie, and Tao Li. 2018. Performance-aware model for sparse matrix-matrix multiplication on the sunway taihulight supercomputer. IEEE transactions on parallel and distributed systems 30, 4 (2018), 923--938."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-18381-2_13"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365694"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009716300509"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687576"},{"key":"e_1_2_1_14_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms. MIT Press."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699470"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-019-07257-y"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098036"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380756"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. 1797--1806","author":"Lee Wang-Chien","year":"2017","unstructured":"Tao-yang Fu, Wang-Chien Lee, and Zhen Lei. 2017. Hin2vec: Explore meta-paths in heterogeneous information networks for representation learning. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. 1797--1806."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380297"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2015.19"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3571157"},{"key":"e_1_2_1_23_1","series-title":"SIAM journal on matrix analysis and applications 13, 1","volume-title":"Sparse matrices in MATLAB: Design and implementation","author":"Gilbert John R","year":"1992","unstructured":"John R Gilbert, Cleve Moler, and Robert Schreiber. 1992. Sparse matrices in MATLAB: Design and implementation. SIAM journal on matrix analysis and applications 13, 1 (1992), 333--356."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1973.5009182"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/355791.355796"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3358061"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3352460.3358275"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC41405.2020.00076"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3070607.3070608"},{"key":"e_1_2_1_31_1","unstructured":"Moritz Kaufmann Manuel Then Alfons Kemper and Thomas Neumann. 2017. Parallel Array-Based Single-and Multi-Source Breadth First Searches on Large Dense Graphs.. In EDBT. 1--12."},{"key":"e_1_2_1_32_1","unstructured":"David Kernert Frank K\u00f6hler and Wolfgang Lehner. 2015. SpMacho-Optimizing Sparse Linear Algebra Expressions with Probabilistic Density Estimation. In EDBT. 289--300."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3574245.3574259"},{"key":"e_1_2_1_34_1","volume-title":"Relational retrieval using a combination of path-constrained random walks. Machine learning 81","author":"Lao Ni","year":"2010","unstructured":"Ni Lao and William W Cohen. 2010. Relational retrieval using a combination of path-constrained random walks. Machine learning 81 (2010), 53--67."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00085"},{"key":"e_1_2_1_36_1","volume-title":"Introduction to algorithms","author":"Leiserson Charles Eric","unstructured":"Charles Eric Leiserson, Ronald L Rivest, Thomas H Cormen, and Clifford Stein. 1994. Introduction to algorithms. Vol. 3. MIT press Cambridge, MA, USA."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA51647.2021.00070"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2007.1027"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1002\/cta.796"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.47"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2015.06.010"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2184751.2184817"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNC.2011.62"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3503221.3508431"},{"key":"e_1_2_1_45_1","unstructured":"NVIDIA. 2020. Nvidia cuSPARSE library. Retrieved from https:\/\/developer.nvidia.com\/cusparse."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2018.00067"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-20119-1_4"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490181"},{"key":"e_1_2_1_49_1","first-page":"396","article-title":"Sparsity-driven matrix representation to optimize operational and storage efficiency","volume":"9","author":"Reinwald Berthold","year":"2016","unstructured":"Berthold Reinwald, Shirish Tatikonda, and Yuanyuan Tian. 2016. Sparsity-driven matrix representation to optimize operational and storage efficiency. US Patent 9,396,164.","journal-title":"US Patent"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2967938.2967943"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS47924.2020.00022"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2833443"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319854"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO50266.2020.00068"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402736"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735507"},{"key":"e_1_2_1_57_1","unstructured":"Stijn Marinus Van Dongen. 2000. Graph clustering by flow simulation. Ph.D. Dissertation."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1798596.1798597"},{"key":"e_1_2_1_59_1","volume-title":"Intel Math Kernel Library","author":"Wang Endong","unstructured":"Endong Wang, Qing Zhang, Bo Shen, Guangyong Zhang, Xiaowei Lu, Qing Wu, and Yajuan Wang. 2014. Intel Math Kernel Library. Springer International Publishing, 167--188."},{"key":"e_1_2_1_60_1","doi-asserted-by":"crossref","unstructured":"Xiao Wang Houye Ji Chuan Shi Bai Wang Yanfang Ye Peng Cui and Philip S Yu. 2019. Heterogeneous graph attention network. In The world wide web conference. 2022--2032.","DOI":"10.1145\/3308558.3313562"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293883.3295701"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2017.8091043"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00083"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.150"},{"key":"e_1_2_1_65_1","volume-title":"Graph transformer networks. Advances in neural information processing systems 32","author":"Yun Seongjun","year":"2019","unstructured":"Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim. 2019. Graph transformer networks. Advances in neural information processing systems 32 (2019)."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-93037-4_16"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA47549.2020.00030"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594532"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654959","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654959","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:40:38Z","timestamp":1755787238000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654959"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":68,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654959"],"URL":"https:\/\/doi.org\/10.1145\/3654959","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}