In real-world applications, multi-label feature selection has been widely attract considerable attention due to the importance of multi-label data. However, previous methods do not fully consider the relationship between the feature set and the multi-label set but devote attention to either of them. In addition, the existence of irrelevant and redundant information in the feature set and the multi-label set makes previous methods obtain inaccurate results. Moreover, traditional multi-label learning utilizes logical labels to estimate the relevance between the feature set and the label set so that the importance of labels can not be well-reflected. To deal with these issues, we propose a novel robust multi-label feature selection method named RLEFS in this paper. RLEFS utilizes a shared space by mapping patterns to excavate semantic similarity structure in features and labels. Besides, we reconstruct the label space to obtain numerical labels by a label enhancement regularization term during mining semantic similarity structure process. Furthermore, the local and global structures are considered to ensure effective information can be captured as fully as possible during feature selection process. Finally, we integrate the above terms into one joint learning framework, and then a simple yet effective optimization method with provable convergence is proposed to solve the above problems. Experimental results on multiple data sets show that the superiority of the proposed method.