{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,20]],"date-time":"2025-07-20T22:55:42Z","timestamp":1753052142313,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T00:00:00Z","timestamp":1620604800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>Dense subregion (subgraph &amp; subtensor) detection is a well-studied area, with a wide range of applications, and numerous efficient approaches and algorithms have been proposed. Approximation approaches are commonly used for detecting dense subregions due to the complexity of the exact methods. Existing algorithms are generally efficient for dense subtensor and subgraph detection, and can perform well in many applications. However, most of the existing works utilize the state-or-the-art greedy 2-approximation algorithm to capably provide solutions with a loose theoretical density guarantee. The main drawback of most of these algorithms is that they can estimate only one subtensor, or subgraph, at a time, with a low guarantee on its density. While some methods can, on the other hand, estimate multiple subtensors, they can give a guarantee on the density with respect to the input tensor for the first estimated subsensor only. We address these drawbacks by providing both theoretical and practical solution for estimating multiple dense subtensors in tensor data and giving a higher lower bound of the density. In particular, we guarantee and prove a higher bound of the lower-bound density of the estimated subgraph and subtensors. We also propose a novel approach to show that there are multiple dense subtensors with a guarantee on its density that is greater than the lower bound used in the state-of-the-art algorithms. We evaluate our approach with extensive experiments on several real-world datasets, which demonstrates its efficiency and feasibility.<\/jats:p>","DOI":"10.1145\/3446668","type":"journal-article","created":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T22:24:14Z","timestamp":1620685454000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Density Guarantee on Finding Multiple Subgraphs and Subtensors"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4494-6714","authenticated-orcid":false,"given":"Quang-huy","family":"Duong","sequence":"first","affiliation":[{"name":"Norwegian University of Science and Technology, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Heri","family":"Ramampiaro","sequence":"additional","affiliation":[{"name":"Norwegian University of Science and Technology, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kjetil","family":"N\u00f8rv\u00e5g","sequence":"additional","affiliation":[{"name":"Norwegian University of Science and Technology, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thu-lan","family":"Dam","sequence":"additional","affiliation":[{"name":"Norwegian University of Science and Technology, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,5,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1824777.1824780"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95995-3_3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00243-8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1062"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684822.2685298"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of The Web Conference. 83--93","author":"Ban Yikun","year":"2019","unstructured":"Yikun Ban , Xin Liu , Yitao Duan , Xue Liu , and Wei Xu . 2019 . No place to hide: Catching fraudulent entities in tensors . In Proceedings of The Web Conference. 83--93 . Yikun Ban, Xin Liu, Yitao Duan, Xue Liu, and Wei Xu. 2019. No place to hide: Catching fraudulent entities in tensors. In Proceedings of The Web Conference. 83--93."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44436-X_10"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2014.2298533"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00061"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357958"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0464-z"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083676"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1314498.1314572"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872427.2883037"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-018-0815-z"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939747"},{"volume-title":"Proceedings of the IEEE ICDM. 781--786","author":"Jiang M.","key":"e_1_2_1_18_1","unstructured":"M. Jiang , A. Beutel , P. Cui , B. Hooi , S. Yang , and C. Faloutsos . 2015. A general suspiciousness metric for dense blocks in multimodal data . In Proceedings of the IEEE ICDM. 781--786 . M. Jiang, A. Beutel, P. Cui, B. Hooi, S. Yang, and C. Faloutsos. 2015. A general suspiciousness metric for dense blocks in multimodal data. In Proceedings of the IEEE ICDM. 781--786."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_50"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/07070111X"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557074"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00106"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(00)00139-0"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.95"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2011.80"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 2017 ACM CIKM. 1817--1826","author":"Uddin Nasir Muhammad Anis","year":"2017","unstructured":"Muhammad Anis Uddin Nasir , Aristides Gionis , Gianmarco De Francisci Morales , and Sarunas Girdzijauskas . 2017 . Fully dynamic algorithm for top-k densest subgraphs . In Proceedings of the 2017 ACM CIKM. 1817--1826 . Muhammad Anis Uddin Nasir, Aristides Gionis, Gianmarco De Francisci Morales, and Sarunas Girdzijauskas. 2017. Fully dynamic algorithm for top-k densest subgraphs. In Proceedings of the 2017 ACM CIKM. 1817--1826."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2010.2058802"},{"volume-title":"Proceedings of the 34th IEEE ICDE. 1120--1131","author":"Oh Sejoon","key":"e_1_2_1_30_1","unstructured":"Sejoon Oh , Namyong Park , Lee Sael , and U. Kang . 2018. Scalable tucker factorization for sparse tensors - algorithms and discoveries . In Proceedings of the 34th IEEE ICDE. 1120--1131 . Sejoon Oh, Namyong Park, Lee Sael, and U. Kang. 2018. Scalable tucker factorization for sparse tensors - algorithms and discoveries. In Proceedings of the 34th IEEE ICDE. 1120--1131."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111322.1111330"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00538-z"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623674"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00055"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3046791"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-018-0602-x"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1093\/brain\/awz125"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46128-1_17"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154414"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018676"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098087"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2017.2690524"},{"key":"e_1_2_1_43_1","volume-title":"FROSTT: The Formidable Repository of Open Sparse Tensors and Tools.","author":"Smith Shaden","year":"2017","unstructured":"Shaden Smith , Jee W. Choi , Jiajia Li , Richard Vuduc , Jongsoo Park , Xing Liu , and George Karypis . 2017 . FROSTT: The Formidable Repository of Open Sparse Tensors and Tools. Retrieved from http:\/\/frostt.io\/. Shaden Smith, Jee W. Choi, Jiajia Li, Richard Vuduc, Jongsoo Park, Xing Liu, and George Karypis. 2017. FROSTT: The Formidable Repository of Open Sparse Tensors and Tools. Retrieved from http:\/\/frostt.io\/."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741119"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3067421.3067424"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.143"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939763"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3446668","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3446668","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:31Z","timestamp":1750193251000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3446668"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,10]]},"references-count":47,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3446668"],"URL":"https:\/\/doi.org\/10.1145\/3446668","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2021,5,10]]},"assertion":[{"value":"2020-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}