La classification multi-labels graduée est la tâche d'affecter à chaque donnée l'ensemble des labels qui lui correspondent selon une échelle graduelle de degrés d'appartenance. Les labels peuvent donc avoir à la fois des relations d'ordre et de co-occurrence. D'un côté, le fait d'ignorer les relations entre les labels risque d'aboutir à des prédictions incohérentes, et d'un autre côté, le fait de prendre en compte ces relations risque de propager l'erreur de prédiction d'un label à tous les labels qui lui sont reliés. Les approches de l'état d'art permettent soit d'ignorer les relations entre les labels, soit d'apprendre uniquement les relations correspondant à une structure de dépendance figée. L'approche que nous proposons permet l'apprentissage des relations entre les labels sans fixer une structure de dépendance au préalable. Elle est basée sur un ensemble de classifieurs mono-labels, un pour chaque label. L'idée est d'apprendre d'abord toutes les relations entre les labels y compris les relations cycliques. Ensuite les dépendances cycliques sont résolues en supprimant les relations d'intérêt minimal. Des mesures sont proposées pour évaluer l'intérêt d'apprendre chaque relation. Ces mesures permettent d'agir sur le compromis entre l'apprentissage de relations pour une prédiction cohérente et la minimisa- tion du risque de la propagation d'erreur de prédiction.