DiffWire : Réécriture inductive de graphes via la borne de Lovász

Les réseaux de neurones sur graphes (GNNs) ont démontré des performances compétitives dans diverses tâches liées aux graphes, telles que la classification de nœuds et de graphes, la prédiction de liens, ainsi que le regroupement de nœuds et de graphes, dans de multiples domaines. La plupart des GNNs reposent sur un cadre d’échange de messages, ce qui les qualifie de MPNNs (Message Passing Neural Networks). Malgré leurs résultats prometteurs, les MPNNs sont régulièrement confrontés à des problèmes tels que le sur-lissage, le sur-écrasement (over-squashing) et le manque de portée (under-reaching). La réécriture de graphe (graph rewiring) et le pooling de graphe ont été proposés dans la littérature comme solutions à ces limitations. Toutefois, la plupart des méthodes d’état de l’art en réécriture de graphe échouent à préserver la topologie globale du graphe, ne sont ni différentiables ni inducives, et nécessitent une calibration de hyperparamètres. Dans cet article, nous proposons DiffWire, un nouveau cadre pour la réécriture de graphe dans les MPNNs, fondé sur une approche rigoureuse, entièrement différentiable et sans paramètre, en s’appuyant sur la borne de Lovász. L’approche proposée établit une théorie unifiée de la réécriture de graphe en introduisant deux nouvelles couches complémentaires dans les MPNNs : la CT-Layer, qui apprend les temps de retour (commute times) et les utilise comme fonction de pertinence pour le réajustement des poids des arêtes ; et la GAP-Layer, qui optimise l’écart spectral en fonction de la nature du réseau et de la tâche considérée. Nous validons empiriquement la valeur de chacune de ces couches de manière indépendante, sur des jeux de données standards pour la classification de graphes. Nous menons également des études préliminaires sur l’utilisation de la CT-Layer pour des tâches de classification de nœuds homophiles et hétérophiles. DiffWire intègre la capacité d’apprentissage des temps de retour avec des notions connexes de courbure, ouvrant ainsi la voie à la conception de MPNNs plus expressifs.