  Many real-world applications of image recognition require multi-label
learning, whose goal is to find all labels in an image. Thus, robustness of
such systems to adversarial image perturbations is extremely important.
However, despite a large body of recent research on adversarial attacks, the
scope of the existing works is mainly limited to the multi-class setting, where
each image contains a single label. We show that the naive extensions of
multi-class attacks to the multi-label setting lead to violating label
relationships, modeled by a knowledge graph, and can be detected using a
consistency verification scheme. Therefore, we propose a graph-consistent
multi-label attack framework, which searches for small image perturbations that
lead to misclassifying a desired target set while respecting label hierarchies.
By extensive experiments on two datasets and using several multi-label
recognition models, we show that our method generates extremely successful
attacks that, unlike naive multi-label perturbations, can produce model
predictions consistent with the knowledge graph.
