How can I perform multi-label classification if many labels are missing?
This is called Automatic Document/Text Categorization (a lecture note on this). There're some approaches you can take, such as ATC with semi-supervised learning or building one-vs-all classifier and labeling a new test sample with a new label when all classifiers reject it. This was discussed here as well.