Multi-label feature selection is regarded as one of the most promising techniques that can be used to maximize the efficacy and efficiency of multi-label classification. However, because multi-label feature selection algorithms must consider multiple labels concurrently, the task is more difficult than singlelabel feature selection tasks. In this paper, we propose the Mutual Information-based multi-label feature selection method using interaction information. This method is naturally able to measure dependencies among multiple variables. To develop an efficient multi-label feature selection method, we derive theoretical bounds for the interaction information. Empirical studies indicate that our proposed multi-label feature selection method discovers effective feature subsets for multi-label classification problems.