  Evasion attack in multi-label learning systems is an interesting, widely
witnessed, yet rarely explored research topic. Characterizing the crucial
factors determining the attackability of the multi-label adversarial threat is
the key to interpret the origin of the adversarial vulnerability and to
understand how to mitigate it. Our study is inspired by the theory of
adversarial risk bound. We associate the attackability of a targeted
multi-label classifier with the regularity of the classifier and the training
data distribution. Beyond the theoretical attackability analysis, we further
propose an efficient empirical attackability estimator via greedy label space
exploration. It provides provably computational efficiency and approximation
accuracy. Substantial experimental results on real-world datasets validate the
unveiled attackability factors and the effectiveness of the proposed empirical
attackability indicator
