{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:12:58Z","timestamp":1779174778987,"version":"3.51.4"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>\n                    Graph-processing systems, including Graph Database Management Systems (GDBMSes) and graph libraries, are designed to analyze and manage graph data efficiently. They are widely used in applications such as social networks, recommendation systems, and fraud detection. However, logic bugs in these systems can lead to incorrect results, compromising the reliability of applications. While recent research has explored testing techniques specialized for GDBMSes, it is unclear how to adapt them to graph-processing systems in general. This paper proposes G\n                    <jats:sc>raph<\/jats:sc>\n                    -\n                    <jats:sc>cutting<\/jats:sc>\n                    , a universal approach for detecting logic bugs in both GDBMSes and various algorithms in graph libraries. Our key idea is inspired by the observation that certain graph patterns are critical for various graph-processing tasks. Dividing graph data into subgraphs that preserve those patterns establishes a natural relationship between query results on the original graph and its subgraphs, allowing for the detection of logic bugs when this relationship is violated. We implemented Graph-cutting as a tool, GSlicer, and evaluated it on 3 popular graph-processing systems, NetworkX, Neo4j, and K\u00f9zu. GSlicer detected 39 unique and previously unknown bugs, out of which 34 have been fixed and confirmed by developers. At least 8 logic bugs detected by GSlicer cannot be detected by baseline strategies. Additionally, by leveraging just a few concrete relationships, Graph-cutting can cover over 100 APIs in NetworkX. We expect this technique to be widely applicable and that it can be used to improve the quality of graph-processing systems broadly.\n                  <\/jats:p>","DOI":"10.1145\/3725300","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-27","source":"Crossref","is-referenced-by-count":3,"title":["Finding Logic Bugs in Graph-processing Systems via Graph-cutting"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-4462-8527","authenticated-orcid":false,"given":"Qiuyang","family":"Mang","sequence":"first","affiliation":[{"name":"School of Data Science, The Chinese University of Hong Kong, Shenzhen, Shenzhen, Guangdong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4008-9225","authenticated-orcid":false,"given":"Jinsheng","family":"Ba","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3377-8129","authenticated-orcid":false,"given":"Pinjia","family":"He","sequence":"additional","affiliation":[{"name":"School of Data Science, The Chinese University of Hong Kong, Shenzhen, Shenzhen, Guangdong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8303-2099","authenticated-orcid":false,"given":"Manuel","family":"Rigger","sequence":"additional","affiliation":[{"name":"School of Computing, National University of Singapore, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Survey of graph database models. ACM Computing Surveys (CSUR), 40(1):1--39","author":"Angles Renzo","year":"2008","unstructured":"Renzo Angles and Claudio Gutierrez. Survey of graph database models. ACM Computing Surveys (CSUR), 40(1):1--39, 2008."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE48619.2023.00174"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3597503.3639076"},{"key":"e_1_2_2_4_1","volume-title":"An exploratory case study of query plan representations","author":"Ba Jinsheng","year":"2024","unstructured":"Jinsheng Ba and Manuel Rigger. An exploratory case study of query plan representations, 2024."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654991"},{"key":"e_1_2_2_6_1","volume-title":"The oracle problem in software testing: A survey","author":"Barr Earl T","year":"2014","unstructured":"Earl T Barr, Mark Harman, Phil McMinn, Muzammil Shahbaz, and Shin Yoo. The oracle problem in software testing: A survey. IEEE transactions on software engineering, 41(5):507--525, 2014."},{"issue":"1","key":"e_1_2_2_7_1","first-page":"35","article-title":"Unpacking burt's redundancy measures","volume":"20","author":"Borgatti Stephen P","year":"1997","unstructured":"Stephen P Borgatti. Structural holes: Unpacking burt's redundancy measures. Connections, 20(1):35--38, 1997.","journal-title":"Connections"},{"key":"e_1_2_2_8_1","volume-title":"Motif counting beyond five nodes. ACM Transactions on Knowledge Discovery from Data (TKDD), 12(4):1--25","author":"Bressan Marco","year":"2018","unstructured":"Marco Bressan, Flavio Chierichetti, Ravi Kumar, Stefano Leucci, and Alessandro Panconesi. Motif counting beyond five nodes. ACM Transactions on Knowledge Discovery from Data (TKDD), 12(4):1--25, 2018."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3077136.3080779"},{"key":"e_1_2_2_10_1","volume-title":"Semmt: a semantic-based testing approach for machine translation systems. ACM Transactions on Software Engineering and Methodology (TOSEM), 31(2):1--36","author":"Cao Jialun","year":"2022","unstructured":"Jialun Cao, Meiziniu Li, Yeting Li, Ming Wen, Shing-Chi Cheung, and Haiming Chen. Semmt: a semantic-based testing approach for machine translation systems. ACM Transactions on Software Engineering and Methodology (TOSEM), 31(2):1--36, 2022."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3611643.3616258"},{"key":"e_1_2_2_12_1","volume-title":"Metamorphic testing: a new approach for generating next test cases. arXiv preprint arXiv:2002.12543","author":"Chen Tsong Y","year":"2020","unstructured":"Tsong Y Chen, Shing C Cheung, and Shiu Ming Yiu. Metamorphic testing: a new approach for generating next test cases. arXiv preprint arXiv:2002.12543, 2020."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3551349.3556924"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3698810"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454092"},{"key":"e_1_2_2_16_1","volume-title":"CIDR","author":"Feng Xiyang","year":"2023","unstructured":"Xiyang Feng, Guodong Jin, Ziyi Chen, Chang Liu, and Semih Salihoglu. K\u00f9zu graph database management system. In CIDR, 2023."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190657"},{"key":"e_1_2_2_18_1","volume-title":"AAAI Fall Symposium: Capturing and Using Patterns for Evidence Detection","volume":"45","author":"Gallagher Brian","year":"2006","unstructured":"Brian Gallagher. Matching structure and semantics: A survey on graph-based pattern matching. In AAAI Fall Symposium: Capturing and Using Patterns for Evidence Detection, volume 45, 2006."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_2_20_1","volume-title":"Los Alamos National Laboratory (LANL)","author":"Hagberg Aric","year":"2008","unstructured":"Aric Hagberg, Pieter J Swart, and Daniel A Schult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Laboratory (LANL), Los Alamos, NM (United States), 2008."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE43902.2021.00047"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452815"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588736"},{"key":"e_1_2_2_24_1","volume-title":"Database Language GQL -- 2024 Article 39075. https:\/\/jtc1info.org\/wp-content\/uploads\/2024\/04\/2024-Article-39075-Database-Language-GQL.docx.pdf","author":"IEC","year":"2024","unstructured":"ISO\/IEC JTC1. Database Language GQL -- 2024 Article 39075. https:\/\/jtc1info.org\/wp-content\/uploads\/2024\/04\/2024-Article-39075-Database-Language-GQL.docx.pdf, 2024. [Online; accessed 11-Oct-2024]."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3597503.3623307"},{"key":"e_1_2_2_26_1","first-page":"4949","volume-title":"32nd USENIX Security Symposium (USENIX Security 23)","author":"Jiang Zu-Ming","year":"2023","unstructured":"Zu-Ming Jiang, Jia-Ju Bai, and Zhendong Su. {DynSQL}: Stateful fuzzing for database management systems with complex and valid {SQL} query generation. In 32nd USENIX Security Symposium (USENIX Security 23), pages 4949--4965, 2023."},{"key":"e_1_2_2_27_1","first-page":"821","volume-title":"18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24)","author":"Jiang Zu-Ming","year":"2024","unstructured":"Zu-Ming Jiang and Zhendong Su. Detecting logic bugs in database engines via equivalent expression transformation. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), pages 821--835, 2024."},{"key":"e_1_2_2_28_1","first-page":"821","volume-title":"18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24)","author":"Jiang Zu-Ming","year":"2024","unstructured":"Zu-Ming Jiang and Zhendong Su. Detecting logic bugs in database engines via equivalent expression transformation. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), pages 821--835, 2024."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3357377.3357382"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3597926.3598044"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594334"},{"key":"e_1_2_2_32_1","volume-title":"Several measures of trophic structure applicable to complex food webs. Journal of theoretical Biology, 83(2):195--207","author":"Levine Stephen","year":"1980","unstructured":"Stephen Levine. Several measures of trophic structure applicable to complex food webs. Journal of theoretical Biology, 83(2):195--207, 1980."},{"key":"e_1_2_2_33_1","volume-title":"Gdsmith: Detecting bugs in graph database engines. arXiv preprint arXiv:2206.08530","author":"Lin Wei","year":"2022","unstructured":"Wei Lin, Ziyue Hua, Luyao Ren, Zongyang Li, Lu Zhang, and Tao Xie. Gdsmith: Detecting bugs in graph database engines. arXiv preprint arXiv:2206.08530, 2022."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3650212.3680311"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3510003.3510093"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3597503.3639200"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3468264.3468573"},{"key":"e_1_2_2_38_1","volume-title":"Representing paths in graph database pattern matching. arXiv preprint arXiv:2207.13541","author":"Martens Wim","year":"2022","unstructured":"Wim Martens, Matthias Niewerth, Tina Popp, Stijn Vansummeren, and Domagoj Vrgoc. Representing paths in graph database pattern matching. arXiv preprint arXiv:2207.13541, 2022."},{"issue":"1","key":"e_1_2_2_39_1","first-page":"100","article-title":"Differential testing for software","volume":"10","author":"McKeeman William M","year":"1998","unstructured":"William M McKeeman. Differential testing for software. Digital Technical Journal, 10(1):100--107, 1998.","journal-title":"Digital Technical Journal"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3580305.3599306"},{"key":"e_1_2_2_41_1","unstructured":"Neo4j. Neo4j 2024."},{"key":"e_1_2_2_42_1","unstructured":"Lawrence Page. The pagerank citation ranking: Bringing order to the web. Technical report Technical Report 1999."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556569"},{"key":"e_1_2_2_44_1","volume-title":"David Aparicio, and Fernando Silva. A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets. ACM Computing Surveys (CSUR), 54(2):1--36","author":"Ribeiro Pedro","year":"2021","unstructured":"Pedro Ribeiro, Pedro Paredes, Miguel EP Silva, David Aparicio, and Fernando Silva. A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets. ACM Computing Surveys (CSUR), 54(2):1--36, 2021."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3368089.3409710"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428279"},{"key":"e_1_2_2_47_1","first-page":"667","volume-title":"14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20)","author":"Rigger Manuel","year":"2020","unstructured":"Manuel Rigger and Zhendong Su. Testing database engines via pivoted query synthesis. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), pages 667--682, 2020."},{"key":"e_1_2_2_48_1","volume-title":"Generalizations of the clustering coefficient to weighted complex networks. Physical Review E-Statistical, Nonlinear, and Soft Matter Physics, 75(2):027105","author":"Saram\u00e4ki Jari","year":"2007","unstructured":"Jari Saram\u00e4ki, Mikko Kivel\u00e4, Jukka-Pekka Onnela, Kimmo Kaski, and Janos Kertesz. Generalizations of the clustering coefficient to weighted complex networks. Physical Review E-Statistical, Nonlinear, and Soft Matter Physics, 75(2):027105, 2007."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE48619.2023.00175"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983990.2984038"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588909"},{"issue":"1","key":"e_1_2_2_53_1","first-page":"1","article-title":"Efficient k-clique listing: An edge-oriented branching strategy","volume":"2","author":"Yu Kaiqiang","year":"2024","unstructured":"KaixinWang, Kaiqiang Yu, and Cheng Long. Efficient k-clique listing: An edge-oriented branching strategy. Proceedings of the ACM on Management of Data, 2(1):1--26, 2024.","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149197"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611540.3611614"},{"key":"e_1_2_2_56_1","volume-title":"Dinkel: Testing graph database engines via state-aware query generation. arXiv preprint arXiv:2408.07525","author":"W\u00fcst Dominic","year":"2024","unstructured":"Dominic W\u00fcst, Zu-Ming Jiang, and Zhendong Su. Dinkel: Testing graph database engines via state-aware query generation. arXiv preprint arXiv:2408.07525, 2024."},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3611643.3616295"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3533767.3534389"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3649815"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3650212.3680392"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICST60714.2024.00012"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3533767.3534409"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3417260"},{"key":"e_1_2_2_64_1","volume-title":"Scaling automated database system testing","author":"Zhong Suyang","year":"2025","unstructured":"Suyang Zhong and Manuel Rigger. Scaling automated database system testing, 2025."},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654922"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.14778\/3636218.3636236"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687727"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725300","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:56:30Z","timestamp":1774983390000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725300"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":67,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725300"],"URL":"https:\/\/doi.org\/10.1145\/3725300","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}