L’appariement de multi-graphes est une tâche importante de prédiction structurée, dans laquelle l’étiquette prédite est contrainte à l’espace des appariements cohérents cycliquement. Bien que la minimisation directe de la perte soit une méthode efficace pour l’apprentissage de prédicteurs sur des espaces d’étiquettes structurés, elle ne peut pas être appliquée de manière efficace au problème considéré, car l’exécution d’un solveur spécialisé sur des ensembles de prédictions d’appariement s’avère prohibitivement coûteuse en termes computationnels. En outre, aucune supervision n’est disponible sur les appariements vérité terrain au sein des ensembles de prédictions cohérentes cycliquement.Notre idée principale consiste à imposer strictement les contraintes d’appariement dans les prédictions d’appariement par paires, tout en imposant doucement les contraintes de cohérence cyclique en les reformulant comme des termes de perte pondérés, de sorte que l’importance de l’incohérence par rapport aux prédictions globales soit ajustée par un paramètre de pénalité. Inspirés par la méthode classique des pénalités, nous démontrons théoriquement que notre approche permet de récupérer la solution optimale de l’appariement de multi-graphes sous contraintes.Les avantages de notre méthode se révèlent clairement dans les résultats expérimentaux obtenus sur la tâche populaire d’appariement de points clés, sur les jeux de données Pascal VOC et Willow ObjectClass.