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. To date, no deterministic verifier determines 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 multiplication of the number of labels and the number of predicted labels. 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 mixed-integer programming (MIP) encoding for multi-label classifiers. We evaluate MuLLoC on convolutional networks for three multi-label image datasets. Our results show that MuLLoC classifies all labels as robust or not within 23.22 minutes on average and that our fast optimistic queries classify 96.84% of the labels.