Appariement de graphes

Comparer des réseaux (de neurones)

Comme tous les organes des animaux, les réseaux de neurones évoluent au fil des générations. Mais leur architecture n’évolue pas au hasard : elle est couplée à celle des organes de perception et de contrôle. En effet un bras, une aile d'oiseau ou une nageoire ne servent à rien sans le réseau neuronal qui assure la perception et le contôle, et réciproquement. En termes d’ingénierie, le hardware — os, muscles, articulations — et le software — les circuits neuronaux — sont physiquement et fonctionnellement distincts, mais couplés par les transductions qu’exigent les boucles sensorimotrices ; aucun des deux ne peut donc évoluer efficacement sans l’autre. C’est ce que l’on appelle l’évolution jointe.

Au laboratoire nous explorons in silico certains mécanismes de cette évolution jointe, avec des « corps » constitués de chaînes articulées à nombre de segments variable et des « contrôleur » constitués de réseaux de neurones artificiel, tous deux dérivés d’un même « génome » que l’on fait évoluer dans une population.

Ces simulations font apparaître des architectures qui reviennent sur un grand nombre de trajectoires évolutives indépendantes. Mais encore faut-il pouvoir établir des correspondances: dire que deux réseaux se ressemblent suppose de savoir à quel neurone de l’un correspond tel neurone de l’autre. C’est un problème d’appariement de graphes.

Apparier deux graphes, c’est chercher la correspondance entre leurs noeuds qui respecte au mieux la structure et les liens entre noeuds. Le problème est NP-complet, et la plupart des méthodes le ramènent à un problème d’affectation linéaire : on construit une matrice de scores entre sommets, puis on la résout, ce qui donne des solutions approximatives.

Apparier la structure et les attributs

L’algorithme GASM (Graph Attributes and Structure Matching) développé au laboratoire permet d'obtenir des solutions de grande qualité sans sacrifier la vitesse de calcul. Son secret ? Il utilise tout l'information disponible, c'est à dire à la fois la structure du graphes mais aussi tous les attributs des liens et des noeuds. Par exemple sur un réseau de neurones artificiel, il se nourrit aussi des poids, biais, fonctions d'activation, et des rôles des neurones (entrée, sortie ou autre). En définissant l'activité du réseau comme attribut, on peut aussi intégrer les aspects fonctionnels dans l'appariement.

Techniquement, l'algorithme calcule itérativement des scores de similarité entre noeuds et entre liens, à la manière du passage de messages des réseaux de neurones sur graphes, dans un cadre léger. Deux idées le distinguent particulièrement: d’une part les contraintes portées par les attributs sont introduites a priori, ce qui couple les attributs et la structure pendant les itérations au lieu de les traiter séparément ; des paramètres d’incertitude disent, attribut par attribut, à quel point la solution doit s’appuyer sur eux plutôt que sur la structure. D’autre part un bruit infinitésimal suffit à lever les dégénérescences dues aux symétries locales. Enfin, le nombre d’itérations n’est pas fixé à l’avance : la distance de passage de messages pertinente est le diamètre du graphe, qui n’est pas le même d’un jeu de données à l’autre, et un critère de convergence dynamique s’y adapte tout seul.

Cet algorithme est donc parfaitement adapté au problème de la comparaison de réseaux de neurones, mais il trouve aussi des applications dans de multiples domaines.

Implémentation open source

GASM-or, l’implémentation de référence en Python, sur processeur et sur carte graphique : PyPI · GitHub · documentation.