  We present new methods for multilabel classification, relying on ensemble
learning on a collection of random output graphs imposed on the multilabel and
a kernel-based structured output learner as the base classifier. For ensemble
learning, differences among the output graphs provide the required base
classifier diversity and lead to improved performance in the increasing size of
the ensemble. We study different methods of forming the ensemble prediction,
including majority voting and two methods that perform inferences over the
graph structures before or after combining the base models into the ensemble.
We compare the methods against the state-of-the-art machine learning approaches
on a set of heterogeneous multilabel benchmark problems, including multilabel
AdaBoost, convex multitask feature learning, as well as single target learning
approaches represented by Bagging and SVM. In our experiments, the random graph
ensembles are very competitive and robust, ranking first or second on most of
the datasets. Overall, our results show that random graph ensembles are viable
alternatives to flat multilabel and multitask learners.
