Multi-label classification aims to assign a set of proper labels for each instance,where distance metric learning can help improve the generalization ability of instance-based multi-label classification models.Existing multi-label metric learning techniques work by utilizing pairwise constraints to enforce that examples with similar label assignments should have close distance in the embedded feature space.In this pa-per,a novel distance metric learning approach for multi-label classification is proposed by modeling structural interactions between instance space and label space.On one hand,composi-tional distance metric is employed which adopts the representa-tion of a weighted sum of rank-1 PSD matrices based on com-ponent bases.On the other hand,compositional weights are op-timized by exploiting triplet similarity constraints derived from both instance and label spaces.Due to the compositional na-ture of employed distance metric,the resulting problem admits quadratic programming formulation with linear optimization complexity w.r.t.the number of training examples.We also de-rive the generalization bound for the proposed approach based on algorithmic robustness analysis of the compositional metric.Extensive experiments on sixteen benchmark data sets clearly validate the usefulness of compositional metric in yielding ef-fective distance metric for multi-label classification.