Multi-labels problems with a lot of labels are a good use case of metric learning, so we could add support for it in the algorithms. In supervised ones it would mean modifying the loss function a bit (we have been discussing it with @bellet for NCA's PR in scikit-learn for instance)
For weakly supervised ones it would mean make tuples from multi-labeled data (it seems that there are several strategies to do so, like how much labels do points share, etc...)