Efficient Neural Network Verification via Layer-based Semidefinite Relaxations and Linear Cuts

Batten, Ben; Kouvaros, Panagiotis; Lomuscio, Alessio; Zheng, Yang

doi:10.24963/ijcai.2021/301

Efficient Neural Network Verification via Layer-based Semidefinite Relaxations and Linear Cuts

Ben Batten, Panagiotis Kouvaros, Alessio Lomuscio, Yang Zheng

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 2184-2190.

https://doi.org/10.24963/ijcai.2021/301

Keywords

Multidisciplinary Topics and Applications: Validation and Verification
Machine Learning: Explainable/Interpretable Machine Learning
Machine Learning: Deep Learning

Abstract

We introduce an efficient and tight layer-based semidefinite relaxation for verifying local robustness of neural networks. The improved tightness is the result of the combination between semidefinite relaxations and linear cuts. We obtain a computationally efficient method by decomposing the semidefinite formulation into

layerwise constraints. By leveraging on chordal graph decompositions, we show that the formulation here presented is provably tighter than current approaches. Experiments on a set of benchmark networks show that the approach here proposed enables the verification of more instances compared to other relaxation methods. The results also demonstrate that the SDP relaxation here proposed is one order of magnitude faster than previous SDP methods.

Ben Batten, Panagiotis Kouvaros, Alessio Lomuscio, and Yang Zheng. 2021. Efficient Neural Network Verification via Layer-based Semidefinite Relaxations and Linear Cuts. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 2184–2190. https://doi.org/10.24963/ijcai.2021/301

@inproceedings{ijcai2021p301,
  title     = {Efficient Neural Network Verification via Layer-based Semidefinite Relaxations and Linear Cuts},
  author    = {Batten, Ben and Kouvaros, Panagiotis and Lomuscio, Alessio and Zheng, Yang},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {2184--2190},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/301},
  url       = {https://doi.org/10.24963/ijcai.2021/301},
}

TY  - CPAPER
TI  - Efficient Neural Network Verification via Layer-based Semidefinite Relaxations and Linear Cuts
AU  - Batten, Ben
AU  - Kouvaros, Panagiotis
AU  - Lomuscio, Alessio
AU  - Zheng, Yang
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 2184
EP  - 2190
DO  - 10.24963/ijcai.2021/301
UR  - https://doi.org/10.24963/ijcai.2021/301
ER  -