Référence : « Graph kernels based on tree patterns for molecules », Pierre Mahé · Jean-Philippe Vert

Il est de plus en plus nécessaire de mettre au point des algorithmes pour analyser et classer des données de graphes, spécifiquement pour  diverses applications en chémoinformatique et en bioinformatique.
Un exemple important en chimioformatique est le problème générique de prédiction de diverses propriétés de petites molécules, telles que la toxicité ou l’activité anticancéreuse, étant donné leur graphe moléculaire. Ce graphe représente les liaisons covalentes entre atomes (Leach et Gillet 2003). La classification des graphes est souvent associée au problème de l’exploration de graphes, qui consiste à détecter des motifs intéressants apparaissant dans les graphes et à les utiliser comme éléments pour construire des modèles prédictifs (King et al., 1996, Helma et al. 2004, Deshpande et al., 2005).

Il existe une alternative à cette approche : les méthodes de noyau associées aux noyaux de graphes sont récemment apparues comme une approche prometteuse pour la classification des données de graphe. Les méthodes de noyau telles que les machines vectorielles de support (SVM) fonctionnent implicitement dans un espace de caractéristiques de Hilbert de dimension élevée, en ce sens qu’aucun calcul explicite de l’image des données d’entrée dans l’espace de caractéristiques n’est requis.
Au lieu de cela, seul le produit interne entre les images de deux points de données d’entrée, appelé le noyau, est requis (Schölkopf et Smola 2002, Shawe-Taylor et Cristianini 2004).
L’application de méthodes de noyau à des données de graphe nécessite donc la définition d’un noyau entre les graphes, appelé simplement noyau de graphe.
Le choix d’un noyau de graphe revient implicitement à définir un ensemble d’entités pour représenter les graphes et un produit interne dans l’espace des entités.

Les noyaux de graphe ont été mis au point par Kashima et al. (2004) et Gärtner et al. (2003), qui ont montré comment cartographier des graphes dans un espace de caractéristiques infini-dimensionnel indexé par des sous-graphes linéaires, et calculer un produit interne dans cet espace.
Les noyaux de graphes résultants comparent deux graphes à travers leurs chemins communs, pondérés en fonction de leurs longueurs (Gärtner et al., 2003) ou par leur probabilité sous un modèle de marche aléatoire sur les graphes (Kashima et al., 2004). Bien que cette représentation puisse sembler restrictive, ces noyaux ont conduit à des résultats empiriques prometteurs, souvent comparés à des approches de pointe dans les domaines de la chémoinformatique (Mahé et al 2005, Ralaivola et al., 2005) et de la bioinformatique (Borgwardt et al. 2005, Karklin et al., 2005).

Néanmoins, Ramon et Gärtner (2003) ont mis en évidence l’expressivité limitée des noyaux de graphes basés sur des caractéristiques linéaires, montrant en particulier que de nombreux graphes différents peuvent être mappés au même point dans l’espace caractéristique correspondant. La figure suivante illustre ce problème sur un exemple simple. D’un autre côté, ils ont également montré que le calcul d’un noyau de graphe complet, c’est-à-dire un mappage de graphes non isomorphes par un noyau à des points distincts dans l’espace des objets, est au moins aussi difficile que le problème d’isomorphisme. Cela suggère que l’expressivité des noyaux de graphes doit être échangé pour leur complexité de calcul.

Deux graphiques ayant le même contenu de marche, à savoir
•: × 5;
• → •: × 4
• → • → •: × 2,
par conséquent mappés au même point de l’espace caractéristique correspondant
à un noyau basé sur le nombre de marches (Gärtner et al., 2003)

Différentes approches ont été proposées pour affiner les caractéristiques utilisées dans les noyaux de graphes basés sur la marche.
Horváth et al. (2004) ont introduit des noyaux basés sur la détection de modèles cycliques communs, Menchetti et al. (2005) ont dérivé un noyau de la comparaison des voisinages d’atomes, et Ramon et Gärtner (2003) ont introduit un noyau comparant les graphes sur la base de leurs sous-arbres communs. Cette dernière représentation semble prometteuse en particulier en chimioinformatique, car on sait que les propriétés physicochimiques des atomes sont liées à leur environnement topologique qui pourrait être bien capturé par les sous-arbres. Cependant, la relation entre le nouveau noyau basé sur les sous-arbres et les noyaux basés sur des marches précédentes n’a pas été analysée dans les détails, et la pertinence du nouveau noyau n’a pas été testée empiriquement.