Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/46575Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Grohe, Martin | - |
| dc.contributor.author | Standke, Christoph | - |
| dc.contributor.author | STEEGMANS, Juno | - |
| dc.contributor.author | VAN DEN BUSSCHE, Jan | - |
| dc.date.accessioned | 2025-08-14T13:18:57Z | - |
| dc.date.available | 2025-08-14T13:18:57Z | - |
| dc.date.issued | 2025 | - |
| dc.date.submitted | 2025-07-24T14:52:34Z | - |
| dc.identifier.citation | Sudeepa, Roy; Ahmet, Kara (Ed.). Proceedings of the International Conference on Database Theory (ICDT), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, p. 9:1 -9:18 (Art N° 9) | - |
| dc.identifier.issn | 1868-8969 | - |
| dc.identifier.uri | http://hdl.handle.net/1942/46575 | - |
| dc.description.abstract | We lay the foundations for a database-inspired approach to interpreting and understanding neural network models by querying them using declarative languages. Towards this end we study different query languages, based on first-order logic, that mainly differ in their access to the neural network model. First-order logic over the reals naturally yields a language which views the network as a black box; only the input-output function defined by the network can be queried. This is essentially the approach of constraint query languages. On the other hand, a white-box language can be obtained by viewing the network as a weighted graph, and extending first-order logic with summation over weight terms. The latter approach is essentially an abstraction of SQL . In general, the two approaches are incomparable in expressive power, as we will show. Under natural circumstances, however, the white-box approach can subsume the black-box approach; this is our main result. We prove the result concretely for linear constraint queries over real functions definable by feedforward neural networks with a fixed number of hidden layers and piecewise linear activation functions. | - |
| dc.description.sponsorship | Martin Grohe: Funded by the European Union (ERC, SymSim, 101054974). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. Christoph Standke: Funded by the German Research Foundation (DFG) under grants GR 1492/16-1 and GRK 2236 (UnRAVeL). Juno Steegmans: Supported by the Special Research Fund (BOF) of UHasselt. Jan Van den Bussche: Partially supported by the Flanders AI Program (FAIR). | - |
| dc.language.iso | en | - |
| dc.publisher | Schloss Dagstuhl – Leibniz-Zentrum für Informatik | - |
| dc.relation.ispartofseries | Leibniz International Proceedings in Informatics (LIPIcs) | - |
| dc.rights | MartinGrohe,Christoph Standke, Juno Steegmans, and Jan Van den Bussche; licensed under Creative Commons License CC-BY 4.0 | - |
| dc.subject.other | Expressive power of query languages | - |
| dc.subject.other | Machine learning models | - |
| dc.subject.other | languages for interpretability | - |
| dc.subject.other | explainable AI | - |
| dc.subject.other | Theory of computation → Database query languages (principles) | - |
| dc.title | Query Languages for Neural Networks | - |
| dc.type | Proceedings Paper | - |
| local.bibliographicCitation.authors | Sudeepa, Roy | - |
| local.bibliographicCitation.authors | Ahmet, Kara | - |
| local.bibliographicCitation.conferencedate | 2025, March 25-28 | - |
| local.bibliographicCitation.conferencename | International Conference on Database Theory (ICDT) | - |
| local.bibliographicCitation.conferenceplace | Barcelona, Spain | - |
| dc.identifier.epage | 9:18 | - |
| dc.identifier.spage | 9:1 | - |
| dc.identifier.volume | 328 | - |
| local.format.pages | 18 | - |
| local.bibliographicCitation.jcat | C1 | - |
| dc.relation.references | Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. URL: http://webdam.inria.fr/Alice/. A. Albarghouthi. Introduction to neural network verification. Foundations and Trends in Programming Languages, 7(1–2):1–157, 2021. URL: https://verifieddeeplearning.com, doi:10.1561/2500000051. Marcelo Arenas, Daniel Báez, Pablo Barceló, Jorge Pérez, and Bernardo Subercaseaux. Foundations of symbolic languages for model interpretability. In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, ed- itors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, vir- tual, pages 11690–11701, 2021. URL: https://proceedings.neurips.cc/paper/2021/hash/ 60cb558c40e4f18479664069d9642d5a-Abstract.html. Marcelo Arenas, Pablo Barceló, Diego Bustamante, Jose Caraball, and Bernardo Subercaseaux. A uniform language to explain decision trees. In Pierre Marquis, Magdalena Ortiz, and Maurice Pagnucco, editors, Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, KR 2024, Hanoi, Vietnam. November 2-8, 2024, pages 60–70, 2024. doi:10.24963/kr.2024/6. S. Basu, R. Pollack, and M.-F. Roy. Algorithms in Real Algebraic Geometry. Springer, second edition, 2008. Michael Benedikt, Martin Grohe, Leonid Libkin, and Luc Segoufin. Reachability and connectivity queries in constraint databases. J. Comput. Syst. Sci., 66(1):169–206, 2003. doi:10.1016/S0022-0000(02)00034-X. F. Bodria, F. Giannotti, R. Guidotti, F. Naretto, D. Pedreschi, and S. Rinzivillo. Benchmarking and survey of explanation methods for black box models. Data Mining and Knowledge Discovery, 37:1719–1778, 2023. doi:10.1007/s10618-023-00933-9. Molnar Christoph. Interpretable Machine Learning: A Guide for Making Black Box Mod- els Explainable. Leanpub, second edition, 2022. URL: https://christophm.github.io/ interpretable-ml-book. George Cybenko. Approximation by superpositions of a sigmoidal function. Math. Control. Signals Syst., 2(4):303–314, 1989. doi:10.1007/BF02551274. Floris Geerts and Bart Kuijpers. On the decidability of termination of query evaluation in transitive-closure logics for polynomial constraint databases. Theor. Comput. Sci., 336(1):125– 151, 2005. doi:10.1016/j.tcs.2004.10.034. Ian J. Goodfellow, Yoshua Bengio, and Aaron C. Courville. Deep Learning. Adaptive computation and machine learning. MIT Press, 2016. URL: http://www.deeplearningbook. org/. E. Grädel and Y. Gurevich. Metafinite model theory. Information and Computation, 140(1):26– 81, 1998. doi:10.1006/inco.1997.2675. Erich Grädel, Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema, and Scott Weinstein. Finite Model Theory and Its Applications. Texts in Theo- retical Computer Science. An EATCS Series. Springer, 2007. doi:10.1007/3-540-68804-8. Martin Grohe, Christoph Standke, Juno Steegmans, and Jan Van den Bussche. Query languages for neural networks. CoRR, abs/2408.10362, 2024. arXiv:2408.10362, doi:10.48550/arXiv. 2408.10362. Dan Halperin. Arrangements. In Jacob E. Goodman and Joseph O’Rourke, editors, Handbook of Discrete and Computational Geometry, Second Edition, chapter 24, pages 529–562. Chapman and Hall/CRC, second edition, 2004. doi:10.1201/9781420035315.ch24. Wilfrid Hodges. Model Theory, volume 42 of Encyclopedia of mathematics and its applications. Cambridge University Press, 1993. Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural Networks, 4(2):251–257, 1991. doi:10.1016/0893-6080(91)90009-T. P.C. Kanellakis, G.M. Kuper, and P.Z. Revesz. Constraint query languages. Journal of Computer and System Sciences, 51(1):26–52, aug 1995. doi:10.1006/jcss.1995.1051. A. Klug. Equivalence of relational algebra and relational calculus query languages having aggregate functions. Journal of the ACM, 29(3):699–717, 1982. doi:10.1145/322326.322332. A. Kohn, V. Leis, and Th. Neumann. Tidy tuples and flying start: fast compilation and fast execution of relational queries in Umbra. VLDB Journal, 30(5):883–905, 2021. doi: 10.1007/s00778-020-00643-4. Gabriel M. Kuper, Leonid Libkin, and Jan Paredaens, editors. Constraint Databases. Springer, 2000. doi:10.1007/978-3-662-04031-7. Marta Kwiatkowska and Xiyue Zhang. When to trust AI: advances and challenges for certification of neural networks. In Maria Ganzha, Leszek A. Maciaszek, Marcin Paprzycki, and Dominik Slezak, editors, Proceedings of the 18th Conference on Computer Science and Intelligence Systems, FedCSIS 2023, Warsaw, Poland, September 17-20, 2023, volume 35 of Annals of Computer Science and Information Systems, pages 25–37. Polish Information Processing Society, 2023. doi:10.15439/2023F2324. L. Libkin. Expressive power of SQL. Theoretical Computer Science, 296:379–404, 2003. doi:10.1016/S0304-3975(02)00736-3. Leonid Libkin. Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2004. URL: http://www.cs.toronto.edu/%7Elibkin/fmt, doi: 10.1007/978-3-662-07003-1. Changliu Liu, Tomer Arnon, Christopher Lazarus, Christopher Strong, Clark Barrett, Mykel J Kochenderfer, et al. Algorithms for verifying deep neural networks. Foundations and Trends® in Optimization, 4(3-4):244–404, 2021. doi:10.1561/2400000035. X. Liu and E. Lorini. A unified logical framework for explanations in classifier systems. Journal of Logic and Computation, 33(2):485–515, 2023. doi:10.1093/logcom/exac102. Scott M. Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In NIPS, pages 4765–4774, 2017. URL: https://proceedings.neurips.cc/paper/2017/hash/ 8a20a8621978632d76c43dfd28b67767-Abstract.html. Abo Khamis M., H.Q. Ngo, and A. Rudra. Juggling functions inside a database. SIGMOD Record, 46(1):6–13, 2017. doi:10.1145/3093754.3093757. João Marques-Silva. Logic-based explainability in machine learning. In Leopoldo E. Bertossi and Guohui Xiao, editors, Reasoning Web. Causality, Explanations and Declarative Knowledge - 18th International Summer School 2022, Berlin, Germany, September 27-30, 2022, Tutorial Lec- tures, volume 13759 of Lecture Notes in Computer Science, pages 24–104. Springer, 2022. URL: https://doi.org/10.1007/978-3-031-31414-8_2, doi:10.1007/978-3-031-31414-8_2. Mark Raasveldt and Hannes Mühleisen. Duckdb: an embeddable analytical database. In Peter A. Boncz, Stefan Manegold, Anastasia Ailamaki, Amol Deshpande, and Tim Kraska, editors, Proceedings of the 2019 International Conference on Management of Data, SIGMOD Conference 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, pages 1981–1984. ACM, 2019. doi:10.1145/3299869.3320212. C. Rudin. Stop explaining black box maching learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1:206–215, 2019. doi: 10.1038/s42256-019-0048-x. Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. URL: http://arxiv.org/abs/1312.6199, doi:10.48550/arXiv.1312.6199. A. Tarski. A Decision Method for Elementary Algebra and Geometry. University of California Press, 1951. Vincent Tjeng, Kai Yuanqing Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL: https://openreview.net/forum?id=HyGIdiRqtm. Szymon Torunczyk. Aggregate queries on sparse databases. In Dan Suciu, Yufei Tao, and Zhewei Wei, editors, Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020, pages 427–443. ACM, 2020. doi:10.1145/3375395.3387660. Steffen van Bergerem and Nicole Schweikardt. Learning concepts described by weight ag- gregation logic. In Christel Baier and Jean Goubault-Larrecq, editors, 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, January 25-28, 2021, Ljubljana, Slovenia (Virtual Conference), volume 183 of LIPIcs, pages 10:1–10:18. Schloss Dagstuhl - Leibniz- Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.CSL.2021.10. Sandra Wachter, Brent D. Mittelstadt, and Chris Russell. Counterfactual explanation without opening the black box: Automated decisions and the GDPR. Harvard Journal of Law & Technology, 31(2):841–887, 2018. doi:10.2139/ssrn.3063289. | - |
| local.type.refereed | Refereed | - |
| local.type.specified | Proceedings Paper | - |
| local.bibliographicCitation.artnr | 9 | - |
| dc.identifier.doi | 10.4230/lipics.icdt.2025.6 | - |
| dc.identifier.url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.9 | - |
| local.provider.type | datacite | - |
| local.bibliographicCitation.btitle | Proceedings of the International Conference on Database Theory (ICDT) | - |
| local.uhasselt.international | yes | - |
| local.contributor.datacreator | Grohe, Martin | - |
| local.contributor.datacreator | Standke, Christoph | - |
| local.contributor.datacreator | Steegmans, Juno | - |
| local.contributor.datacreator | Van den Bussche, Jan | - |
| local.format.extent | 18 pages | - |
| local.format.mimetype | application/pdf | - |
| local.contributororcid.datacreator | 0000-0002-0292-9142 | - |
| local.contributororcid.datacreator | 0000-0002-3034-730X | - |
| local.contributororcid.datacreator | 0000-0003-2087-9430 | - |
| local.contributororcid.datacreator | 0000-0003-0072-3252 | - |
| dc.rights.access | Creative Commons Attribution 4.0 International license | - |
| item.accessRights | Closed Access | - |
| item.fulltext | With Fulltext | - |
| item.contributor | Grohe, Martin | - |
| item.contributor | Standke, Christoph | - |
| item.contributor | STEEGMANS, Juno | - |
| item.contributor | VAN DEN BUSSCHE, Jan | - |
| item.contributor | Steegmans, Juno | - |
| item.contributor | Van den Bussche, Jan | - |
| item.fullcitation | Grohe, Martin; Standke, Christoph; STEEGMANS, Juno & VAN DEN BUSSCHE, JanGrohe, Martin; Standke, Christoph; Steegmans, Juno & Van den Bussche, Jan (2025) Query Languages for Neural Networks. Sudeepa, Roy; Ahmet, Kara (Ed.). Proceedings of the International Conference on Database Theory (ICDT), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, p. 9:1 -9:18 (Art N° 9). | - |
| Appears in Collections: | Research publications | |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.