{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:05:45Z","timestamp":1750309545536,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":70,"publisher":"ACM","license":[{"start":{"date-parts":[[2025,4,22]],"date-time":"2025-04-22T00:00:00Z","timestamp":1745280000000},"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":[],"published-print":{"date-parts":[[2025,4,28]]},"DOI":"10.1145\/3696410.3714730","type":"proceedings-article","created":{"date-parts":[[2025,4,22]],"date-time":"2025-04-22T22:47:11Z","timestamp":1745362031000},"page":"3874-3884","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Counting Cohesive Subgraphs with Hereditary Properties"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3105-5325","authenticated-orcid":false,"given":"Rong-Hua","family":"Li","sequence":"first","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0982-341X","authenticated-orcid":false,"given":"Xiaowei","family":"Ye","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0609-8833","authenticated-orcid":false,"given":"Fusheng","family":"Jin","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4129-7704","authenticated-orcid":false,"given":"Yu-Ping","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6282-6057","authenticated-orcid":false,"given":"Ye","family":"Yuan","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0181-8379","authenticated-orcid":false,"given":"Guoren","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,4,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137651"},{"key":"e_1_3_2_1_2_1","volume-title":"Duffield","author":"Ahmed Nesreen K.","year":"2015","unstructured":"Nesreen K. Ahmed, Jennifer Neville, Ryan A. Rossi, and Nick G. Duffield. 2015. Efficient Graphlet Counting for Large Networks. In ICDM. 1--10."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00026-N"},{"key":"e_1_3_2_1_4_1","unstructured":"Thomas Aynaud. 2020. python-louvain x.y: Louvain algorithm for community detection. hrefhttps:\/\/github.com\/taynaud\/python-louvain https:\/\/github.com\/taynaud\/python-louvain."},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the 35th International Conference on Neural Information Processing Systems (NIPS '21)","author":"Barcel\u00f3 Pablo","year":"2024","unstructured":"Pablo Barcel\u00f3, Floris Geerts, Juan Reutter, and Maksimilian Ryschkov. 2024. Graph neural networks with local graph parameters. In Proceedings of the 35th International Conference on Neural Information Processing Systems (NIPS '21). Curran Associates Inc., Article 1936, 14 pages."},{"key":"e_1_3_2_1_6_1","volume-title":"cs.DS\/0310049","author":"Batagelj Vladimir","year":"2003","unstructured":"Vladimir Batagelj and Matjaz Zaversnik. 2003. An O(m) Algorithm for Cores Decomposition of Networks. CoRR, Vol. cs.DS\/0310049 (2003)."},{"key":"e_1_3_2_1_7_1","volume-title":"Science","volume":"353","author":"Benson Austin R","year":"2016","unstructured":"Austin R Benson, David F Gleich, and Jure Leskovec. 2016. Higher-order organization of complex networks. Science, Vol. 353, 6295 (2016), 163--166."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186586"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_3_2_1_10_1","volume-title":"LION (Lecture Notes in Computer Science","volume":"55","author":"Brunato Mauro","year":"2007","unstructured":"Mauro Brunato, Holger H. Hoos, and Roberto Battiti. 2007. On Effectively Finding Maximal Quasi-cliques in Graphs. In LION (Lecture Notes in Computer Science, Vol. 5313). 41--55."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2618795"},{"volume-title":"Cohesive Subgraph Computation Over Large Sparse Graphs","author":"Chang Lijun","key":"e_1_3_2_1_12_1","unstructured":"Lijun Chang and Lu Qin. 2018. Cohesive Subgraph Computation Over Large Sparse Graphs. Springer Cham."},{"key":"e_1_3_2_1_13_1","volume-title":"Lu Qin, Xuemin Lin, Chengfei Liu, and Weifa Liang.","author":"Chang Lijun","year":"2013","unstructured":"Lijun Chang, Jeffrey Xu Yu, Lu Qin, Xuemin Lin, Chengfei Liu, and Weifa Liang. 2013. Efficiently computing k-edge connected components via graph decomposition. In SIGMOD. 205--216."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.105131"},{"key":"e_1_3_2_1_15_1","unstructured":"Zhengdao Chen Lei Chen Soledad Villar and Joan Bruna. 2020. Can Graph Neural Networks Count Substructures?. In NeurIPS."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.04.003"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Seshadhri Comandur and Srikanta Tirthapura. 2019. Scalable Subgraph Counting: The Methods Behind The Madness. In WWW. 1317--1318.","DOI":"10.1145\/3308560.3320092"},{"key":"e_1_3_2_1_19_1","volume-title":"Daniele De Sensi, Roberto Grossi, Andrea Marino, and Luca Versari.","author":"Conte Alessio","year":"2018","unstructured":"Alessio Conte, Tiziano De Matteis, Daniele De Sensi, Roberto Grossi, Andrea Marino, and Luca Versari. 2018. D2K: Scalable Community Detection in Massive Networks via Small-Diameter k-Plexes. In KDD. 1272--1281."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588931"},{"key":"e_1_3_2_1_21_1","unstructured":"Qiangqiang Dai Rong-Hua Li Hongchao Qin Meihao Liao and Guoren Wang. 2022. Scaling Up Maximal k-plex Enumeration. In CIKM. 345--354."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Maximilien Danisch Oana Balalau and Mauro Sozio. 2018. Listing k-cliques in Sparse Real-World Graphs. In WWW. 589--598.","DOI":"10.1145\/3178876.3186125"},{"key":"e_1_3_2_1_23_1","unstructured":"Daniel Edler Anton Holmgren and Martin Rosvall. 2023. The MapEquation software package. https:\/\/mapequation.org."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2543629"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Jacob Focke and Marc Roth. 2022. Counting small induced subgraphs with hereditary properties. In STOC. 1543--1551.","DOI":"10.1145\/3519935.3520008"},{"key":"e_1_3_2_1_26_1","volume-title":"Community detection in graphs. Physics reports","author":"Fortunato Santo","year":"2010","unstructured":"Santo Fortunato. 2010. Community detection in graphs. Physics reports, Vol. 486, 3--5 (2010), 75--174."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Jian Gao Zhenghang Xu Ruizhi Li and Minghao Yin. 2022. An Exact Algorithm with New Upper Bounds for the Maximum k-Defective Clique Problem in Massive Sparse Graphs. In AAAI. 10174--10183.","DOI":"10.1609\/aaai.v36i9.21257"},{"key":"e_1_3_2_1_28_1","volume-title":"Classes of complex networks defined by role-to-role connectivity profiles. Nature physics","author":"Guimera Roger","year":"2007","unstructured":"Roger Guimera, Marta Sales-Pardo, and Luis AN Amaral. 2007. Classes of complex networks defined by role-to-role connectivity profiles. Nature physics, Vol. 3, 1 (2007), 63--69."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btt717"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Xin Huang Hong Cheng Lu Qin Wentao Tian and Jeffrey Xu Yu. 2014. Querying k-truss community in large and dynamic graphs. In SIGMOD. 1311--1322.","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Shweta Jain and C. Seshadhri. 2017. A Fast and Provable Method for Estimating Clique Counts Using Tur\u00e1n's Theorem. In WWW. 441--449.","DOI":"10.1145\/3038912.3052636"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Shweta Jain and C. Seshadhri. 2020. The Power of Pivoting for Exact Clique Counting. In WSDM. 268--276.","DOI":"10.1145\/3336191.3371839"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741101"},{"key":"e_1_3_2_1_34_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Jure Leskovec Kevin J Lang Anirban Dasgupta and Michael W Mahoney. 2008. Statistical properties of community structure in large social and information networks. In WWW. 695--704.","DOI":"10.1145\/1367497.1367591"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407843"},{"key":"e_1_3_2_1_37_1","volume-title":"Community detection in complex networks via clique conductance. Scientific reports","author":"Lu Zhenqi","year":"2018","unstructured":"Zhenqi Lu, Johan Wahlstr\u00f6m, and Arye Nehorai. 2018. Community detection in complex networks via clique conductance. Scientific reports, Vol. 8, 1 (2018), 5982."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289199"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2909990.2909998"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_3_2_1_41_1","volume-title":"Science","volume":"303","author":"Milo Ron","year":"2004","unstructured":"Ron Milo, Shalev Itzkovitz, Nadav Kashtan, Reuven Levitt, Shai Shen-Orr, Inbal Ayzenshtat, Michal Sheffer, and Uri Alon. 2004. Superfamilies of evolved and designed networks. Science, Vol. 303, 5663 (2004), 1538--1542."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41109-017-0027-2"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2078195"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Jian Pei Daxin Jiang and Aidong Zhang. 2005. On mining cross-graph quasi-cliques. In KDD. 228--238.","DOI":"10.1145\/1081870.1081898"},{"key":"e_1_3_2_1_45_1","volume-title":"ESCAPE: Efficiently Counting All 5-Vertex Subgraphs. In WWW. 1431--1440.","author":"Pinar Ali","year":"2017","unstructured":"Ali Pinar, C. Seshadhri, and Vaidyanathan Vishal. 2017. ESCAPE: Efficiently Counting All 5-Vertex Subgraphs. In WWW. 1431--1440."},{"key":"e_1_3_2_1_46_1","volume-title":"Silva","author":"Ribeiro Pedro","year":"2022","unstructured":"Pedro Ribeiro, Pedro Paredes, Miguel E. P. Silva, David Apar\u00edcio, and Fernando M. A. Silva. 2022. A Survey on Subgraph Counting: Concepts, Algorithms, and Applications to Network Motifs and Graphlets. ACM Comput. Surv., Vol. 54, 2 (2022), 28:1--28:36."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjst\/e2010-01179-1"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Ahmet Erdem Sariy\u00fcce C. Seshadhri Ali Pinar and \u00dcmit V. \u00c7ataly\u00fcrek. 2015. Finding the Hierarchy of Dense Subgraphs using Nucleus Decompositions. In WWW. 927--937.","DOI":"10.1145\/2736277.2741640"},{"key":"e_1_3_2_1_49_1","volume-title":"Graph clustering. Computer science review","author":"Schaeffer Satu Elisa","year":"2007","unstructured":"Satu Elisa Schaeffer. 2007. Graph clustering. Computer science review, Vol. 1, 1 (2007), 27--64."},{"volume-title":"Introduction to information retrieval","author":"Schutze Hinrich","key":"e_1_3_2_1_50_1","unstructured":"Hinrich Schutze, Christopher D Manning, and Prabhakar Raghavan. 2008. Introduction to information retrieval. Cambridge University Press."},{"key":"e_1_3_2_1_51_1","volume-title":"Network structure and minimum degree. Social networks","author":"Seidman Stephen B","year":"1983","unstructured":"Stephen B Seidman. 1983. Network structure and minimum degree. Social networks, Vol. 5, 3 (1983), 269--287."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1978.9989883"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.06.015"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"crossref","unstructured":"Charalampos E. Tsourakakis. 2015. The K-clique Densest Subgraph Problem. In WWW. 1122--1132.","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"crossref","unstructured":"Charalampos E. Tsourakakis Jakub Pachocki and Michael Mitzenmacher. 2017. Scalable Motif-aware Graph Clustering. In WWW. 1451--1460.","DOI":"10.1145\/3038912.3052653"},{"key":"e_1_3_2_1_56_1","article-title":"Near linear time algorithm to detect community structures in large-scale networks","volume":"76","author":"Usha Nandini Raghavan R\u00e9ka Albert","year":"2007","unstructured":"R\u00e9ka Albert Usha Nandini Raghavan and Soundar Kumara. 2007. Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E, Vol. 76, 036106 (2007).","journal-title":"Phys. Rev. E"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1553374.1553511"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"crossref","unstructured":"Hanchen Wang Rong Hu Ying Zhang Lu Qin Wei Wang and Wenjie Zhang. 2022a. Neural Subgraph Counting with Wasserstein Estimator. In SIGMOD. 160--175.","DOI":"10.1145\/3514221.3526163"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2756836"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"crossref","unstructured":"Zhengren Wang Yi Zhou Mingyu Xiao and Bakhadyr Khoussainov. 2022b. Listing Maximal k-Plexes in Large Real-World Graphs. In WWW. 1517--1527.","DOI":"10.1145\/3485447.3512198"},{"key":"e_1_3_2_1_62_1","volume-title":"Data Mining","volume":"2","author":"Witten Ian H","year":"2005","unstructured":"Ian H Witten, Eibe Frank, Mark A Hall, Christopher J Pal, and MINING DATA. 2005. Practical machine learning tools and techniques. In Data Mining, Vol. 2."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0806082105"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"crossref","unstructured":"Jaewon Yang and Jure Leskovec. 2012. Defining and evaluating network communities based on ground-truth. In KDD. 1--8.","DOI":"10.1145\/2350190.2350193"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"crossref","unstructured":"Xiaowei Ye Rong-Hua Li Qiangqiang Dai Hongzhi Chen and Guoren Wang. 2022. Lightning Fast and Space Efficient k-clique Counting. In WWW. 1191--1202.","DOI":"10.1145\/3485447.3512167"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.97.052306"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl014"},{"key":"e_1_3_2_1_68_1","volume-title":"Hao Zhang, Qiyan Li, and Yu Rong.","author":"Zhao Kangfei","year":"2021","unstructured":"Kangfei Zhao, Jeffrey Xu Yu, Hao Zhang, Qiyan Li, and Yu Rong. 2021. A Learned Sketch for Subgraph Counting. In SIGMOD. 2142--2155."},{"key":"e_1_3_2_1_69_1","volume-title":"Weifa Liang, Baichen Chen, and Jianxin Li.","author":"Zhou Rui","year":"2012","unstructured":"Rui Zhou, Chengfei Liu, Jeffrey Xu Yu, Weifa Liang, Baichen Chen, and Jianxin Li. 2012. Finding maximal k-edge-connected subgraphs from a large graph. In EDBT. 480--491."},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"crossref","unstructured":"Yi Zhou Shan Hu Mingyu Xiao and Zhang-Hua Fu. 2021. Improving Maximum k-plex Solver via Second-Order Reduction and Graph Color Bounding. In AAAI. 12453--12460.","DOI":"10.1609\/aaai.v35i14.17477"}],"event":{"name":"WWW '25: The ACM Web Conference 2025","sponsor":["SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web"],"location":"Sydney NSW Australia","acronym":"WWW '25"},"container-title":["Proceedings of the ACM on Web Conference 2025"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3696410.3714730","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3696410.3714730","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:41Z","timestamp":1750295921000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3696410.3714730"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,22]]},"references-count":70,"alternative-id":["10.1145\/3696410.3714730","10.1145\/3696410"],"URL":"https:\/\/doi.org\/10.1145\/3696410.3714730","relation":{},"subject":[],"published":{"date-parts":[[2025,4,22]]},"assertion":[{"value":"2025-04-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}