Multi-label classification aims to assign a set ofproper labels for each instance, where distance metric learningcan help improve the generalization ability of instance-basedmulti-label classification models. Existing multi-label metriclearning techniques work by utilizing pairwise constraints toenforce that examples with similar label assignments shouldhave close distance in the embedded feature space. In thispaper, a novel distance metric learning approach for multi-label classification is proposed by modeling structural interac-tions between instance space and label space. On one hand,compositional distance metric is employed which adopts therepresentation of a weighted sum of rank-1 PSD matricesbased on component bases. On the other hand, compositionalweights are optimized by exploiting triplet similarity con-straints derived from both instance and label spaces. Due tothe compositional nature of employed distance metric, theresulting problem admits quadratic programming formulationwith linear optimization complexity w.r.t. the number of train-ing examples. We also derive the generalization bound forthe proposed approach based on algorithmic robustness anal-ysis of the compositional metric. Extensive experiments onsixteen benchmark data sets clearly validate the usefulness ofcompositional metric in yielding effective distance metric formulti-label classification.