However, similar to multi-class classification, multiple recent studies [1]}, [2]}, [3]} showed that multi-label classification is also vulnerable to adversarial examples. In particular, an attacker can manipulate the set of labels predicted by a multi-label classifier for an input via adding carefully crafted perturbation to it. Adversarial examples pose severe security threats to the applications of multi-label classification in security-critical domains. To mitigate adversarial examples to multi-label classification, several empirical defenses [4]}, [5]}, [3]} have been proposed. For instance, Melacci et al. [3]} proposed to use the domain knowledge on the relationships among the classes to improve the robustness of multi-label classification. However, these defenses have no provable robustness guarantees, and thus they are often broken by more advanced attacks. For instance, Melacci et al. [3]} showed that their proposed defense can be broken by an adaptive attack that exploits the domain knowledge used in the defense. Moreover, existing provably robust defenses [9]}, [10]}, [11]}, [12]}, [13]}, [14]} are all for multi-class classification, which achieve sub-optimal provable robustness guarantee when extended to multi-label classification as shown by our experimental results.
