Let's first clarify the terminology a little. The data you have, according to the description, is a multi-class data rather than a multi-label one. In both cases, the number of possible classes/labels of the data set is equal or larger than 2, i.e., $\lvert Y \rvert \ge 2$. The difference is, in a multi-class data set, one instance $\mathbf{x}$ is associated with one and only one label, i.e., $\lvert \mathbf{y}_\mathbf{x} \rvert = 1$, while in the multi-label case, one instance $\mathbf{x}$ is associated with one or more labels, i.e., $\lvert \mathbf{y}_\mathbf{x} \rvert \ge 1$. As you see, multi-class setting is a special case of the multi-label setting.
In the conventional setting of outlier detection, the instances are not labeled. In that case, unsupervised techniques such as one-class SVM or density estimation (e.g., mixture of Gaussians) are often applied.
As you have labels at hand, it would be silly not using them. There are at least three options I can think of.
- Define the outlier score separately on the feature space $\mathcal{X}$ and the label space $\mathcal{Y}$. On $\mathcal{X}$, conventional unsupervised techniques can be used. On $\mathcal{Y}$, similarity measures for sets or binary vectors can be used. At the end, you obtain two outlier scores $S_\mathcal{X}$ and $S_\mathcal{Y}$ and the final outlier score can be defined as $S = S_\mathcal{X} + \lambda S_\mathcal{y}$, where $\lambda$ is a trade-off parameter to balance these two values and it should be tuned.
- Train a multi-class classifier on the training data. When a test instance arrives, apply the classifier on it and if the predicted label is different from the test label, this instance is likely an outlier. (If the data set is multi-label instead of multi-class, we need to have a similarity measure on the label space to quantify if the predicted labels are significantly different from the given labels.)
- Simply concatenate the feature vector and the label/class vector and apply the standard unsupervised techniques on the combined vectors.
