{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T23:54:39Z","timestamp":1776297279943,"version":"3.50.1"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032227515","type":"print"},{"value":"9783032227522","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"},{"start":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T00:00:00Z","timestamp":1776297600000},"content-version":"vor","delay-in-days":105,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-22752-2_1","type":"book-chapter","created":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T21:51:18Z","timestamp":1776289878000},"page":"3-22","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testing"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-5446-9150","authenticated-orcid":false,"given":"Chia-Hsuan","family":"Lu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-8341-2004","authenticated-orcid":false,"given":"Tony","family":"Tan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2964-0880","authenticated-orcid":false,"given":"Michael","family":"Benedikt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,4,16]]},"reference":[{"key":"1_CR1","unstructured":"Serbe Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995."},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Ksenia Bestuzheva, Mathieu Besan\u00e7on, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, Leona Gottwald, Christoph Graczyk, Katrin Halbig, Alexander Hoen, Christopher Hojny, Rolf van\u00a0der Hulst, Thorsten Koch, Marco L\u00fcbbecke, Stephen\u00a0J. Maher, Frederic Matter, Erik M\u00fchmer, Benjamin M\u00fcller, Marc\u00a0E. Pfetsch, Daniel Rehfeldt, Steffan Schlein, Franziska Schl\u00f6sser, Felipe Serrano, Yuji Shinano, Boro Sofranac, Mark Turner, Stefan Vigerske, Fabian Wegscheider, Philipp Wellner, Dieter Weninger, and Jakob Witzig. Enabling Research through the SCIP Optimization Suite 8.0. ACM Trans. Math. Softw., 49(2), June 2023.","DOI":"10.1145\/3585516"},{"key":"1_CR3","unstructured":"Aleksandar Bojchevski and Stephan G\u00fcnnemann. Certifiable robustness to graph perturbations. In NeurIPS, 2019."},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Houssem\u00a0Ben Braiek and Foutse Khomh. Machine learning robustness: A primer, 2024.","DOI":"10.1016\/B978-0-44-323761-4.00012-2"},{"key":"1_CR5","unstructured":"David Duvenaud, Dougal Maclaurin, Jorge Aguilera-Iparraguirre, Rafael G\u00f3mez-Bombarelli, Timothy Hirzel, Al\u00e1n Aspuru-Guzik, and Ryan\u00a0P. Adams. Convolutional networks on graphs for learning molecular fingerprints. In NeurIPS, 2015."},{"key":"1_CR6","unstructured":"Matthias Fey and Jan\u00a0E. Lenssen. Fast graph representation learning with PyTorch Geometric. arXiv:1903.02428, 2019."},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"Ben Finkelshtein, Chaim Baskin, Evgenii Zheltonozhskii, and Uri Alon. Single-node attacks for fooling graph neural networks. Neurocomputing, 513:1\u201312, 2022.","DOI":"10.1016\/j.neucom.2022.09.115"},{"key":"1_CR8","unstructured":"Justin Gilmer, Samuel\u00a0S. Schoenholz, Patrick\u00a0F. Riley, Oriol Vinyals, and George\u00a0E. Dahl. Neural message passing for quantum chemistry. In ICML, 2017."},{"key":"1_CR9","unstructured":"Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024."},{"key":"1_CR10","unstructured":"William\u00a0L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017."},{"key":"1_CR11","unstructured":"Christopher Hojny, Shiqiang Zhang, Juan\u00a0S. Campos, and Ruth Misener. Verifying message-passing neural networks via topology-based bounds tightening. In ICML, 2024."},{"key":"1_CR12","unstructured":"Hongwei Jin, Zhan Shi, Venkata Jaya Shankar\u00a0Ashish Peruri, and Xinhua Zhang. Certified robustness of graph convolution networks for graph classification under topological attacks. In NeurIPS, 2020."},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Guy Katz, Clark\u00a0W. Barrett, David\u00a0L. Dill, Kyle Julian, and Mykel\u00a0J. Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. In CAV, 2017.","DOI":"10.1007\/978-3-319-63387-9_5"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"Guy Katz, Derek\u00a0A. Huang, Duligur Ibeling, Kyle Julian, Christopher Lazarus, Rachel Lim, Parth Shah, Shantanu Thakoor, Haoze Wu, Aleksandar Zeljic, David\u00a0L. Dill, Mykel\u00a0J. Kochenderfer, and Clark Barrett. The Marabou Framework for Verification and Analysis of Deep Neural Networks. In CAV, 2019.","DOI":"10.1007\/978-3-030-25540-4_26"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"Steven\u00a0M. Kearnes, Kevin McCloskey, Marc Berndl, Vijay\u00a0S. Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of Computer Aided Molecular Design, 30(8):595\u2013608, 2016.","DOI":"10.1007\/s10822-016-9938-8"},{"key":"1_CR16","unstructured":"Tobias Ladner, Michael Eichelbeck, and Matthias Althoff. Formal verification of graph convolutional networks with uncertain node features and uncertain graph structure. Trans. Mach. Learn. Res., 2025, 2025."},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"Yuni Lai, Yulin Zhu, Bailin Pan, and Kai Zhou. Node-aware bi-smoothing: Certified robustness against graph injection attacks. In IEEE SP, 2024.","DOI":"10.1109\/SP54263.2024.00241"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"Chang Liu, Yinpeng Dong, Wenzhao Xiang, Xiao Yang, Hang Su, Jun Zhu, Yuefeng Chen, Yuan He, Hui Xue, and Shibao Zheng. A comprehensive study on robustness of image classification models: Benchmarking and rethinking. Int. J. Comput. Vision, 133(2):567\u2013589, August 2024.","DOI":"10.1007\/s11263-024-02196-3"},{"key":"1_CR19","unstructured":"Minghao Liu, Chia-Hsuan Lu, and Marta Kwiatkowska. Exact verification of graph neural networks with incremental constraint solving, 2025. https:\/\/www.arxiv.org\/abs\/2508.09320."},{"key":"1_CR20","unstructured":"Nikolaos Louloudakis, Perry Gibson, Jose Cano, and Ajitha Rajan. Assessing robustness of image recognition models to changes in the computational environment. In NeurIPS ML Safety Workshop, 2022."},{"key":"1_CR21","unstructured":"Chia-Hsuan Lu, Tony Tan, and Michael Benedikt. Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testing, 2025. arxiv."},{"key":"1_CR22","unstructured":"Christopher Morris, Nils\u00a0M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataset: A collection of benchmark datasets for learning with graphs. ArXiv, abs\/2007.08663, 2020."},{"key":"1_CR23","unstructured":"Hongbin Pei, Bingzhen Wei, Kevin Chen-Chuan Chang, Yu\u00a0Lei, and Bo\u00a0Yang. Geom-gcn: Geometric graph convolutional networks. In ICLR, 2020."},{"key":"1_CR24","doi-asserted-by":"crossref","unstructured":"Marco S\u00e4lzer and Martin Lange. Reachability is np-complete even for the simplest neural networks. In RP, 2021.","DOI":"10.1007\/978-3-030-89716-1_10"},{"key":"1_CR25","doi-asserted-by":"crossref","unstructured":"Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification in network data. AI Mag., 29(3):93\u2013106, September 2008.","DOI":"10.1609\/aimag.v29i3.2157"},{"key":"1_CR26","doi-asserted-by":"crossref","unstructured":"Jonathan Shlomi, Peter Battaglia, and Jean-Roch Vlimant. Graph neural networks in particle physics. Machine Learning: Science and Technology, 2(2):021001, 2021.","DOI":"10.1088\/2632-2153\/abbf9a"},{"key":"1_CR27","doi-asserted-by":"crossref","unstructured":"Renchi Yang, Jieming Shi, Xiaokui Xiao, Yin Yang, Sourav\u00a0S. Bhowmick, and Juncheng Liu. PANE: scalable and effective attributed network embedding. The VLDB Journal, 32(6):1237\u20131262, March 2023.","DOI":"10.1007\/s00778-023-00790-4"},{"key":"1_CR28","doi-asserted-by":"crossref","unstructured":"Daniel Z\u00fcgner and Stephan G\u00fcnnemann. Certifiable robustness of graph convolutional networks under structure perturbations. In KDD, 2020.","DOI":"10.1145\/3394486.3403217"}],"container-title":["Lecture Notes in Computer Science","Tools and Algorithms for the Construction and Analysis of Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-22752-2_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T23:14:47Z","timestamp":1776294887000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-22752-2_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032227515","9783032227522"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-22752-2_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"16 April 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TACAS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Tools and Algorithms for the Construction and Analysis of Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Turin","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"32","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tacas2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/about\/tacas\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}