DEEPSPLIT: An Efficient Splitting Method for Neural Network Verification via Indirect Effect Analysis

Patrick Henriksen, Alessio Lomuscio

Abstract

We propose a novel, complete algorithm for the verification and analysis of feed-forward, ReLU-based neural networks. The algorithm, based on symbolic interval propagation, introduces a new method for determining split-nodes which evaluates the indirect effect that splitting has on the relaxations of successor nodes. We combine this with a new efficient linear-programming encoding of the splitting constraints to further improve the algorithm’s performance. The resulting implementation, DeepSplit, achieved speedups of 1–2 orders of magnitude and 21-34% fewer timeouts when compared to the current SoA toolkits.
BibTeX
@inproceedings{henriksen2021deepsplit,
  author = {Patrick Henriksen and Alessio Lomuscio},
  title = {{DEEPSPLIT: An Efficient Splitting Method for Neural Network Verification via Indirect Effect Analysis}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/351},
}

Loading related content...

Figure