Nous introduisons les noyaux de propagation, un cadre général de noyaux sur graphes permettant de mesurer efficacement la similarité des données structurées. Les noyaux de propagation reposent sur la surveillance de la manière dont l’information se propage à travers un ensemble de graphes donnés. Ils exploitent les distributions aux étapes précoce des schémas de propagation, tels que les marches aléatoires, afin de capturer les informations structurelles encodées dans les étiquettes des nœuds, leurs attributs et les informations relatives aux arêtes. Cette approche présente deux avantages majeurs. Premièrement, des schémas de propagation disponibles « de manière standard » peuvent être utilisés pour construire naturellement des noyaux adaptés à de nombreux types de graphes, y compris les graphes étiquetés, partiellement étiquetés, non étiquetés, orientés et attribués. Deuxièmement, en s’appuyant sur des schémas de propagation existants, efficaces et informatifs, les noyaux de propagation peuvent être considérablement plus rapides que les approches de pointe actuelles, sans compromettre la performance prédictive. Nous montrons également que, lorsque les graphes considérés présentent une structure régulière — par exemple dans le cas de modélisation de données d’images ou de vidéos — cette régularité peut être exploitée pour échelonner le calcul du noyau à de grandes bases de données contenant des milliers de nœuds. Nos contributions sont soutenues par des expérimentations exhaustives sur plusieurs graphes réels provenant de divers domaines d’application.