Graded multi-label classification is the task of associating to each data a set of labels according to an ordinal scale of membership degrees. Therefore labels can have both order and co-occurrence relations. On the one hand, ignoring label relations may lead to inconsistent predictions, and on the other hand, considering those relations may spread the prediction error of a label to all related labels. Unlike state of art approaches which can learn only relations fitting a predefined dependency structure, our proposed approach doesn't set any predefined structure. The idea is to learn all possible relations, then resolve cyclic dependencies using appropriate measures. Those measures allow managing the compromise between considering label relations for a consistent prediction, and ignoring them to minimize the prediction error propagation.