The Taub Faculty of Computer Science Events and Talks

Multi-label neural networks are important in various tasks, including safety-critical tasks. Several works show that these networks are susceptible to adversarial attacks, which can remove a target label from the predicted label list or add a target label to this list. However, no verifier can deterministically determine the list of labels for which a multi-label neural network is locally robust. The main challenge is that the complexity of the analysis increases by a factor exponential in the number of predicted classes and the total number of classes.

We propose MuLLoC, a sound and complete robustness verifier for multi-label image classifiers that determines the robust labels in a given neighborhood of inputs. To scale the analysis, MuLLoC relies on fast, optimistic queries to the network or to a constraint solver. Its queries include sampling and pair-wise relation analysis via numerical optimization and mixed-integer linear programming (MILP). For the remaining unclassified labels, MuLLoC performs an exact analysis by a novel MILP encoding for multi-label classifiers.

We evaluate MuLLoC on three multi-label image datasets and several convolutional networks. Our results show that MuLLoC classifies all labels as robust or not within 17 minutes on average and that sampling and pair-wise relation analysis classify 94.62% of the labels.