# Checking extracted rules in Neural Networks

arXiv: https://arxiv.org/abs/2509.16547 · HTML: https://mlsanity.com/paper/2509.16547/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 17 references that are in the map.
- First posted on arXiv 20 Sep 2025.

## Builds on (most cited first, 7 of 7)

- [A Survey on Deep Learning in Medical Image Analysis](https://mlsanity.com/paper/1702.05747/) (2017)
- [A Survey of Deep Learning Techniques for Autonomous Driving](https://mlsanity.com/paper/1910.07738/) (2019)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [A Survey of the Recent Architectures of Deep Convolutional Neural Networks](https://mlsanity.com/paper/1901.06032/) (2019)
- [Classification-based Financial Markets Prediction using Deep Neural Networks](https://mlsanity.com/paper/1603.08604/) (2016)
- [Rule Extraction Algorithm for Deep Neural Networks: A Review](https://mlsanity.com/paper/1610.05267/) (2016)
- [Rule-Extraction Methods From Feedforward Neural Networks: A Systematic Literature Review](https://mlsanity.com/paper/2312.12878/) (2023)

## Built on by (most cited first, 1 of 1)

- [Security Properties of Neural Networks as Decision Problems](https://mlsanity.com/paper/2609.39768/) (2026)

## Abstract (arXiv)

In this paper we investigate formal verification of extracted rules for Neural Networks under a complexity theoretic point of view. A rule is a global property or a pattern concerning a large portion of the input space of a network. These rules are algorithmically extracted from networks in an effort to better understand their inner way of working. Here, three problems will be in the focus: Does a given set of rules apply to a given network? Is a given set of rules consistent or do the rules contradict themselves? Is a given set of rules exhaustive in the sense that for every input the output is determined? Finding algorithms that extract such rules out of networks has been investigated over the last 30 years, however, to the author's current knowledge, no attempt in verification was made until now. A lot of attempts of extracting rules use heuristics involving randomness and over-approximation, so it might be beneficial to know whether knowledge obtained in that way can actually be trusted. We investigate the above questions for neural networks with ReLU-activation as well as for Boolean networks, each for several types of rules. We demonstrate how these problems can be reduced to each other and show that most of them are co-NP-complete.