  In the recent years, we have witnessed the development of multi-label
classification methods which utilize the structure of the label space in a
divide and conquer approach to improve classification performance and allow
large data sets to be classified efficiently. Yet most of the available data
sets have been provided in train/test splits that did not account for
maintaining a distribution of higher-order relationships between labels among
splits or folds. We present a new approach to stratifying multi-label data for
classification purposes based on the iterative stratification approach proposed
by Sechidis et. al. in an ECML PKDD 2011 paper. Our method extends the
iterative approach to take into account second-order relationships between
labels. Obtained results are evaluated using statistical properties of obtained
strata as presented by Sechidis. We also propose new statistical measures
relevant to second-order quality: label pairs distribution, the percentage of
label pairs without positive evidence in folds and label pair - fold pairs that
have no positive evidence for the label pair. We verify the impact of new
methods on classification performance of Binary Relevance, Label Powerset and a
fast greedy community detection based label space partitioning classifier.
Random Forests serve as base classifiers. We check the variation of the number
of communities obtained per fold, and the stability of their modularity score.
Second-Order Iterative Stratification is compared to standard k-fold, label
set, and iterative stratification. The proposed approach lowers the variance of
classification quality, improves label pair oriented measures and example
distribution while maintaining a competitive quality in label-oriented
measures. We also witness an increase in stability of network characteristics.
