Sur les noyaux d'affectation optimaux et leurs applications à la classification de graphes

Le succès des méthodes à noyaux a initié la conception de nouvelles fonctions semi-définies positives, en particulier pour les données structurées. Un paradigme de conception prédominant pour cela est le noyau de convolution, qui décompose les objets structurés en leurs parties et somme sur toutes les paires de parties. En revanche, les noyaux d'affectation sont obtenus à partir d'une bijection optimale entre les parties, ce qui peut fournir une notion plus valide de similarité. Cependant, en général, les affectations optimales produisent des fonctions indéfinies, ce qui complique leur utilisation dans les méthodes à noyaux. Nous caractérisons une classe de noyaux de base utilisés pour comparer les parties qui garantit des noyaux d'affectation optimaux semi-définis positifs. Ces noyaux de base engendrent des hiérarchies à partir desquelles les noyaux d'affectation optimaux sont calculés en temps linéaire par intersection d'histogrammes. Nous appliquons ces résultats en développant le noyau d'affectation optimal Weisfeiler-Lehman pour les graphes. Il fournit une haute précision de classification sur des jeux de données de référence largement utilisés, améliorant ainsi le noyau Weisfeiler-Lehman original.