Une introduction accessible aux réseaux de neurones de graphes

 (distill.pub)
1 points par GN⁺ 2024-12-21 | 1 commentaires | Partager sur WhatsApp
  • Les réseaux de neurones de graphes (GNN) sont des modèles qui traitent conjointement les nœuds, les arêtes, le contexte global et la structure de connexion. Ils conviennent aux données où un même graphe doit être interprété de la même façon même si l’ordre des nœuds change
  • Les molécules, les réseaux sociaux et les réseaux de citations, mais aussi les grilles de pixels d’images et les séquences de tokens textuels, peuvent être vus comme des graphes. Mais les graphes ayant des tailles et des connectivités très variables, ils sont difficiles à traiter comme de simples entrées sous forme de tableaux
  • Les problèmes de prédiction avec les GNN se déclinent au niveau du graphe entier, des nœuds ou des arêtes. Une même famille de modèles peut préserver la structure d’entrée tout en prédisant des labels à différents niveaux
  • L’opération centrale est le message passing, qui agrège et met à jour les informations des nœuds et arêtes voisins. En empilant plusieurs couches, les informations de voisins plus éloignés à k sauts peuvent être intégrées aux représentations
  • Les performances réelles dépendent de la profondeur des couches, de la dimension des embeddings, de la fonction d’agrégation et du flux de messages entre représentations de nœuds, d’arêtes et globales. Augmenter les paramètres ou la profondeur ne donne pas toujours les meilleurs résultats

Données de graphe et notions de base des GNN

  • Un graphe est composé de nœuds (node), qui sont les entités, et d’arêtes (edge), qui représentent les relations entre nœuds
  • Des informations supplémentaires peuvent être stockées respectivement sur les nœuds, les arêtes et le graphe entier
    • Les nœuds peuvent contenir des caractéristiques comme le type d’atome, les valeurs RGB d’un pixel ou l’embedding d’un document
    • Les arêtes peuvent contenir des informations comme le type de liaison ou le type de relation
    • Le graphe entier peut disposer d’un contexte global
  • Les arêtes peuvent être représentées comme des directed edges, avec direction, ou des undirected edges, sans direction
  • Un GNN transforme les nœuds, les arêtes et le contexte global de manière apprenable, tout en devant traiter une même structure de graphe avec le même sens même si l’ordre des nœuds change

Données représentables sous forme de graphes

  • Une image est généralement représentée comme un tableau de type 244×244×3, mais on peut aussi la voir comme un graphe régulier où chaque pixel est un nœud et les pixels adjacents sont reliés par des arêtes
    • Un pixel qui n’est pas en bordure possède exactement 8 voisins
    • Chaque nœud stocke un vecteur à 3 dimensions représentant les valeurs RGB
  • Un texte peut être vu comme un graphe orienté où les caractères, mots ou tokens sont des nœuds, avec des arêtes vers le token suivant
    • Cela rejoint la représentation des séquences de tokens dans les RNN
    • Un Transformer peut être vu comme un graphe entièrement connecté qui apprend les relations entre tokens
  • Les images et les textes ont des structures très régulières, ce qui peut rendre leur représentation en graphe redondante
    • La matrice d’adjacence d’une image présente une structure en bandes à cause des connexions de la grille
    • La matrice d’adjacence d’un texte est proche d’une structure diagonale, chaque mot n’étant connecté qu’aux mots précédent et suivant
  • Les molécules se représentent commodément comme des graphes où les atomes sont des nœuds et les liaisons covalentes des arêtes
    • Les distances varient selon la paire d’atomes et le type de liaison, par exemple liaison simple ou double
  • Les réseaux sociaux modélisent les personnes, institutions et organisations comme des nœuds, et les relations comme des arêtes
  • Les réseaux de citations représentent les articles comme des nœuds et la relation par laquelle un article en cite un autre comme une arête orientée
    • Chaque nœud d’article peut recevoir des informations supplémentaires, comme des embeddings des mots du résumé
  • Les objets de scènes en vision par ordinateur, les modèles de machine learning, le code de programmation et les équations mathématiques peuvent aussi être représentés comme des graphes, avec des variables ou objets comme nœuds, et des opérations ou relations comme arêtes

Trois niveaux de problèmes de prédiction sur graphes

  • Une Graph-level task prédit une propriété unique pour l’ensemble du graphe
    • Par exemple, prédire l’odeur d’un graphe moléculaire ou s’il se liera à un récepteur lié à une maladie
    • Comme en classification d’images ou en analyse de sentiment de phrases, un seul label est associé à toute l’entrée
  • Une Node-level task prédit la propriété ou le rôle de chaque nœud du graphe
    • Le dataset Zach’s karate club consiste à classer les nœuds correspondant aux individus selon le club auquel ils resteront fidèles après un conflit politique
    • C’est comparable au fait de labelliser le rôle de chaque pixel en segmentation d’image, ou de prédire la partie du discours de chaque mot dans une phrase
  • Une Edge-level task prédit la propriété ou l’existence d’une arête
    • Par exemple, en compréhension de scènes d’images, on peut représenter les objets comme des nœuds et prédire s’il existe une relation entre les objets
    • On peut commencer par connecter complètement toutes les paires de nœuds, puis supprimer des arêtes selon les prédictions pour obtenir un graphe creux
  • La génération de graphes et l’explication des prédictions sur graphes font aussi partie des domaines de recherche associés

Difficultés pour transformer un graphe en entrée de réseau de neurones

  • Les modèles de machine learning classiques sont conçus pour des entrées sous forme de tableaux rectangulaires ou de grilles, ce qui rend difficile l’injection directe de la structure de connexion d’un graphe
  • Un graphe peut contenir jusqu’à quatre types d’informations
    • Nœuds
    • Arêtes
    • Contexte global
    • Connectivité
  • Les nœuds, arêtes et contexte global peuvent être convertis en matrices de caractéristiques, mais la représentation de la connectivité est plus délicate
  • La matrice d’adjacence est facile à tensoriser, mais elle a des limites
    • Un graphe peut contenir des millions de nœuds
    • Le nombre d’arêtes par nœud peut varier fortement
    • La matrice d’adjacence devient très creuse et peu efficace en espace
    • Une même connectivité de graphe peut être représentée par plusieurs matrices d’adjacence, sans garantie qu’un réseau de neurones produise toujours le même résultat
  • La liste d’adjacence est plus adaptée aux graphes creux
    • Elle stocke le fait que l’arête e_k relie les nœuds n_i et n_j sous forme de tuple (i, j)
    • Elle permet une représentation en O(n_edges), proportionnelle au nombre d’arêtes, au lieu de O(n_nodes^2) pour la matrice d’adjacence
  • Dans les représentations tensorielles réelles, les valeurs des nœuds, arêtes et du contexte global ne sont pas des scalaires mais des vecteurs
    • Le tenseur des nœuds a donc la forme [n_nodes, node_dim], et non [n_nodes]

Couches GNN et pooling

  • Le GNN le plus simple n’utilise pas encore la connectivité du graphe, et applique des MLP distincts aux nœuds, arêtes et au contexte global pour apprendre de nouveaux embeddings
    • Chaque vecteur de nœud est mis à jour de la même manière
    • Chaque vecteur d’arête est également mis à jour
    • Le vecteur de contexte global est aussi mis à jour en un embedding unique
  • Un GNN ne modifie pas la connectivité du graphe d’entrée
    • Le graphe de sortie conserve la même liste d’adjacence et le même nombre de vecteurs de caractéristiques
    • Ce qui change, ce sont les embeddings des nœuds, des arêtes et du contexte global
  • Le pooling est utilisé pour la prédiction
    • Les embeddings à collecter sont gather et concaténés en matrice
    • Les embeddings collectés sont généralement aggregate avec une opération comme sum
  • Pour une prédiction au niveau des nœuds, si l’information des nœuds est déjà présente, on peut appliquer un classifieur linéaire à chaque embedding de nœud
  • Si l’information nécessaire à la prédiction des nœuds se trouve uniquement dans les arêtes, il faut pooler l’information des arêtes vers les nœuds
  • Si l’information nécessaire à la prédiction des arêtes se trouve uniquement dans les nœuds, on agrège l’information des nœuds vers les arêtes pour l’utiliser dans la prédiction
  • Pour une prédiction sur le graphe entier, on rassemble toutes les informations de nœuds ou d’arêtes en une représentation globale
    • Cela joue un rôle similaire au Global Average Pooling dans les CNN
    • Par exemple, prédire la toxicité d’une molécule ou la présence d’une odeur donnée

Exploiter la structure de connexion avec le message passing

  • Un GNN simple n’utilise pas la connectivité du graphe à l’intérieur des couches, mais seulement lors du pooling juste avant la prédiction
  • Un GNN plus puissant effectue du message passing à l’intérieur des couches pour intégrer la structure de connexion dans la mise à jour des embeddings
  • Le message passing fonctionne en trois étapes
    • Chaque nœud gather les embeddings ou messages des nœuds voisins
    • Les messages sont aggregate avec une fonction d’agrégation comme sum
    • Les messages agrégés passent dans une fonction de mise à jour apprenable
  • Le message passing est similaire à une convolution standard
    • Dans une image, un pixel rassemble les informations d’un nombre fixe de pixels voisins
    • Dans un graphe, un nœud rassemble les informations d’un nombre variable de nœuds voisins
  • En empilant plusieurs couches GNN, les informations de nœuds plus éloignés sont prises en compte
    • Après 3 couches, un nœud peut inclure des informations venant de nœuds situés à 3 étapes
  • Le message passing peut se faire non seulement entre nœuds, mais aussi entre arêtes, et entre nœuds et arêtes

Représentations des arêtes et représentation globale

  • Les datasets ne contiennent pas toujours à la fois des informations de nœuds, d’arêtes et de contexte global
  • Lorsqu’il n’y a que des informations d’arêtes et qu’une prédiction de nœuds est nécessaire, on peut les pooler vers les nœuds
  • Les informations des nœuds et des arêtes pouvant avoir des tailles ou formes différentes, la manière de les combiner devient un choix de conception
    • On peut apprendre un mapping linéaire de l’espace des arêtes vers celui des nœuds, ou inversement
    • On peut concaténer les deux représentations puis les passer dans une fonction de mise à jour
  • L’ordre dans lequel les propriétés du graphe sont mises à jour fait partie de la conception d’un GNN
    • On peut d’abord mettre à jour les nœuds, puis les arêtes
    • On peut d’abord mettre à jour les arêtes, puis les nœuds
    • Une approche weave combinant les représentations node-to-node, edge-to-edge, node-to-edge et edge-to-node est aussi possible
  • Des nœuds éloignés peuvent avoir du mal à échanger efficacement de l’information même après plusieurs passes de message passing
    • Avec k couches, l’information se propage au maximum sur k steps
  • La représentation globale U peut jouer le rôle d’un master node ou d’un vecteur de contexte connecté à tous les nœuds et arêtes
    • Elle sert de pont pour transmettre l’information entre nœuds et arêtes éloignés
    • Elle peut produire une représentation plus riche du graphe entier
  • Un nouvel embedding de nœud peut être conditionné en concaténant les nœuds voisins, les arêtes connectées, les informations globales, etc.
    • On peut aussi appliquer une addition après mapping linéaire, ou une feature-wise modulation

GNN Playground et exemple de prédiction d’odeur moléculaire

  • GNN Playground traite un problème de prédiction graph-level sur de petits graphes moléculaires
  • Les données proviennent du Leffingwell Odor Dataset et contiennent des molécules ainsi que des labels de perception d’odeurs
  • L’expérience classe avec un unique label binaire le fait qu’un graphe moléculaire dégage ou non une odeur “pungent”
    • pungent désigne une odeur forte et marquée
    • Exemples : l’ail et la moutarde, qui peuvent contenir de l’allyl alcohol, ainsi que la piperitone utilisée dans les bonbons au goût menthe poivrée
  • Les molécules sont représentées avec les atomes comme nœuds et les liaisons comme arêtes
    • Les nœuds ont une identité d’atome Carbon, Nitrogen, Oxygen ou Fluorine encodée en one-hot
    • Les arêtes ont un type de liaison single, double, triple ou aromatic encodé en one-hot
  • Le template de modèle consiste en des couches GNN séquentielles suivies d’un modèle linéaire avec activation sigmoid
  • Les choix de conception sont contrôlés selon quatre axes
    • Le nombre de couches GNN, c’est-à-dire la profondeur
    • La dimension d’embedding de chaque propriété
    • La fonction d’agrégation du pooling : max, mean, sum
    • Les propriétés, parmi représentations des nœuds, des arêtes et globale, à mettre à jour et à faire participer au message passing
  • Le Playground exécuté dans le navigateur fonctionne sur tfjs
  • Les graph embeddings de grande dimension sont réduits en 2D avec PCA afin de visualiser les représentations autour de la frontière de décision

Tendances de conception GNN observées dans les expériences

  • Les performances dépendent des données, de la manière de construire le graphe et de la manière de définir ses caractéristiques
  • Un plus grand nombre de paramètres était corrélé aux performances, mais les GNN pouvaient aussi trouver des modèles performants avec peu de paramètres
    • Des modèles très performants ont été trouvés avec environ 3k paramètres
  • Une dimension d’embedding plus élevée avait tendance à améliorer les performances moyennes et le plancher de performance, mais les meilleurs modèles ont aussi été obtenus avec de petites dimensions
  • Le nombre de couches avait tendance à augmenter les performances moyennes, mais le meilleur modèle n’avait pas 3 ou 4 couches : il en avait 2
    • Avec 4 couches, le plancher de performance diminuait
    • Davantage de couches diffusent l’information plus loin, mais il existe un risque de dilution des représentations de nœuds par répétitions successives
  • Parmi les fonctions d’agrégation, sum semblait très légèrement meilleure en performance moyenne, mais max et mean pouvaient produire des modèles tout aussi bons
  • Plus les messages circulaient entre les propriétés de nœuds, d’arêtes et globales, plus la performance moyenne des modèles avait tendance à s’améliorer
    • Comme cette tâche était centrée sur la représentation globale, apprendre explicitement une propriété globale avait tendance à améliorer les performances
    • Les représentations de nœuds semblaient plus utiles que les représentations d’arêtes, car davantage d’information se trouvait dans les propriétés des nœuds

Graphes plus complexes et apprentissage par batch

  • Le framework de message passing peut s’appliquer à des structures de graphes plus complexes
  • Dans un Multigraph, une même paire de nœuds peut partager plusieurs types d’arêtes
    • Dans un réseau social, des types de relations comme acquaintance, friend et family peuvent être utilisés comme types d’arêtes
    • On peut définir des étapes de message passing différentes selon le type d’arête
  • Dans un nested graph, un nœud peut lui-même représenter un graphe
    • Dans un réseau de molécules, un nœud peut être une molécule, et une arête une réaction transformant une molécule en une autre
    • On peut entraîner en alternance un GNN au niveau moléculaire et un GNN au niveau du réseau de réactions
  • Dans un hypergraph, une arête peut être connectée non pas à deux nœuds, mais à plusieurs
    • On peut identifier des communautés de nœuds et introduire des hyper-edges connectées à l’ensemble de la communauté
  • Comme les graphes n’ont pas un nombre fixe de nœuds et d’arêtes, l’apprentissage classique par mini-batch de taille fixe est difficile
  • L’essentiel de l’apprentissage par batch sur graphes est de créer des sous-graphes qui préservent les propriétés importantes du grand graphe
    • Dans un citation network, l’échantillonnage de sous-graphes peut être naturel
    • Pour les molécules, un sous-graphe correspond à une nouvelle molécule plus petite, ce qui peut constituer une manipulation forte
  • L’échantillonnage de graphes est particulièrement important lorsque le grand graphe ne tient pas en mémoire
    • Des architectures et stratégies d’apprentissage comme Cluster-GCN et GraphSaint y sont liées

Biais inductifs adaptés aux graphes

  • Un modèle peut obtenir de meilleures performances prédictives, un temps d’apprentissage plus court, moins de paramètres et une meilleure généralisation lorsqu’il est conçu pour exploiter les symétries et régularités des données
  • Les modèles d’images utilisent des convolutions translation invariant afin d’exploiter le fait qu’un objet reste le même où qu’il apparaisse dans l’image
  • Dans le texte, l’ordre des tokens étant important, les RNN le traitent séquentiellement, tandis que les modèles de la famille Transformer peuvent prêter attention à d’autres parties de la phrase
  • Dans les graphes, les relations entre arêtes, nœuds et éléments globaux sont importantes, ce qui exige un biais inductif relationnel
    • Il faut préserver la structure d’adjacence, qui correspond aux relations explicites
    • Il faut préserver l’invariance par permutation, qui est une symétrie du graphe
    • Le modèle doit fonctionner indépendamment de l’ordre des nœuds ou des arêtes, et traiter des entrées en nombre variable

Choix de l’opération d’agrégation

  • Pooler les informations des nœuds et arêtes voisins est une étape clé des architectures GNN puissantes
  • Comme chaque nœud a un nombre différent de voisins et que le résultat doit être indépendant de l’ordre d’entrée, il faut une fonction d’agrégation différentiable et invariante par permutation
  • Les candidats représentatifs sont sum, mean, max
    • Tous acceptent un nombre variable d’entrées et produisent une sortie indépendante de leur ordre
  • Aucune opération n’est toujours optimale
    • mean est utile lorsque le nombre de voisins varie fortement ou lorsqu’une perspective normalisée sur les caractéristiques du voisinage local est nécessaire
    • max est utile pour mettre en avant une caractéristique unique saillante dans le voisinage local
    • sum montre la distribution des caractéristiques locales et, n’étant pas normalisée, peut aussi accentuer les valeurs aberrantes
  • En pratique, sum est souvent utilisé
  • Principal Neighborhood Aggregation concatène plusieurs opérations d’agrégation et ajoute une scaling function qui varie selon le degré de connectivité
  • Des opérations d’agrégation spécifiques à un domaine, comme Tetrahedral Chirality, peuvent également être conçues

GCN, multiplication matricielle et parcours de graphes

  • Un GCN ou MPNN avec k couches et une consultation de voisinage à 1 degré peut être vu comme un réseau de neurones opérant sur des embeddings de sous-graphes de taille k
    • La représentation mise à jour d’un nœud reflète de manière limitée l’information des voisins situés à une distance k
    • Les représentations d’arêtes peuvent être interprétées de la même manière
  • Le produit AX de la matrice d’adjacence A et de la matrice de caractéristiques des nœuds X implémente un message passing simple utilisant l’agrégation sum
    • Le cas où A_i,k est positif correspond à l’existence d’une arête entre node_i et node_k
    • La multiplication matricielle peut être vue comme une opération rassemblant les valeurs d’une dimension de caractéristique donnée des nœuds voisins
  • Avec une matrice A creuse, il n’est pas nécessaire d’additionner tous les termes nuls, ce qui rend la liste d’adjacence plus efficace
  • Une implémentation fondée sur une liste d’adjacence facilite aussi l’utilisation d’opérations d’agrégation autres que sum
  • La puissance A^K de la matrice d’adjacence est liée aux walks de longueur K
    • A^2_ij compte le nombre de walks de longueur 2 allant de node_i à node_j
    • Cette intuition s’étend de A^3 à A^k

Attention, explicabilité et modèles génératifs

  • Les Graph Attention Networks n’agrègent pas simplement les informations des voisins par somme, mais par somme pondérée
    • Une fonction de score f(node_i, node_j) calcule la pertinence entre le nœud central et un nœud voisin
    • Un softmax normalise les poids afin d’accorder davantage d’importance aux voisins utiles pour la tâche
    • Le calcul des scores par paire préserve l’invariance par permutation
  • Un Transformer peut être vu comme un GNN doté d’un mécanisme d’attention
    • Il modélise des éléments comme des tokens de caractères en tant que nœuds d’un graphe entièrement connecté
    • L’attention calcule les embeddings et les poids des arêtes pour chaque paire de nœuds
    • La différence est que les GNN supposent un motif de connexions creux, tandis que les Transformer modélisent toutes les connexions
  • L’explicabilité des GNN peut être importante pour la fiabilité des modèles, le débogage et la découverte scientifique
    • Dans les molécules, la présence d’un sous-graphe particulier peut être importante
    • Dans les réseaux de citations, le degré de connexion d’un article peut être important
    • GNNExplainer adopte une approche consistant à extraire les sous-graphes pertinents importants pour la tâche
    • Les techniques d’attribution attribuent un rang d’importance à certaines parties du graphe
  • Les modèles génératifs de graphes échantillonnent de nouveaux graphes à partir d’une distribution apprise ou complètent un graphe donné comme point de départ
    • Une application consiste à concevoir de nouveaux graphes moléculaires dotés de propriétés particulières comme candidats médicaments
  • La principale difficulté de la génération de graphes est la modélisation de la topologie du graphe
    • La topologie peut avoir une taille très variable et contenir N_nodes^2 termes
    • On peut modéliser directement une matrice d’adjacence comme une image avec un autoencoder
    • On peut réduire la charge N_nodes^2 en ne prédisant que les arêtes existantes et une partie des arêtes inexistantes
    • Une autre approche consiste à construire le graphe séquentiellement en répétant des actions discrètes comme l’ajout ou la suppression de nœuds et d’arêtes

Conclusion

  • Les graphes sont un type de données structurées ayant des forces et des contraintes différentes de celles des images et des textes
  • Les GNN mettent à jour les nœuds, arêtes et le contexte global d’un graphe tout en gérant la structure de connexion et l’invariance par permutation
  • Le pooling, le message passing, les représentations d’arêtes, les représentations globales et le choix des fonctions d’agrégation sont des éléments clés de la conception des GNN
  • Les performances réelles dépendent fortement non seulement de la profondeur, de la dimension et du nombre de paramètres, mais aussi des propriétés du graphe qui échangent des messages entre elles et de la manière dont le graphe est construit

À lire aussi

1 commentaires

 
GN⁺ 2024-12-21
Commentaires sur Hacker News

  • Beaucoup d’articles utilisent les GNN pour la simulation physique (par exemple la mécanique des fluides numérique). Dans ce type d’application, le maillage non structuré qui discrétise le domaine du problème correspond très bien à une structure de graphe.
    En pratique, chaque maillage/graphe est souvent utilisé une seule fois pour résoudre un problème donné, donc entraîner un GNN pour un graphe particulier n’a pas grand intérêt. Si la plupart des articles l’ont tout de même fait, c’est probablement parce qu’on n’a pas encore trouvé comment créer des GNN qui s’adaptent bien à différents maillages/graphes et paramètres de simulation. Je me demande si une percée permettant cette généralisation arrivera bientôt.

    • Les mots à l’intérieur et autour d’une phrase semblent eux aussi former une sorte de graphe, en agissant comme des nœuds feuilles qui référencent d’autres mots ou sont référencés par eux. Vu le succès du mécanisme d’attention dans les LLM modernes, je me demande à quel point un LLM entraîné pour traiter de vrais graphes serait performant.
      Pour obtenir des performances optimales, il faudrait probablement un tokenizer différent.
    • Un solveur de graphes généraliste devrait être une intelligence généraliste. Il pourrait même modéliser avec succès la théorie des catégories.

  • Le niveau de qualité du travail est très élevé, et il est dommage que distill.pub n’ait pas trouvé de voie durable [1].
    L’une des raisons pour lesquelles on parle moins des GNN pourrait être le manque de jeux de données [2]. C’est un problème qui a aussi touché le domaine du Web sémantique.
    [1] https://distill.pub/2021/distill-hiatus/
    [2] https://huggingface.co/datasets?task_categories=task_categor...

    • Une astuce personnelle que j’utilise avant de me plonger directement dans des articles d’un domaine inconnu consiste à chercher « explained » sur YouTube.
      Pour les domaines populaires, beaucoup de gens ont intérêt à produire des vidéos courtes et captivantes, et la qualité est souvent bonne même à un niveau mathématique assez abstrait. Les supports visuels aident vraiment à se faire une intuition des concepts abstraits, et 3Blue1Brown l’a déjà démontré. Pour les GNN aussi, regarder quelques bonnes vidéos de moins de 10 minutes suffit à se donner un point d’appui avant d’entrer dans la littérature.
    • Franchement, en voyant ça arriver en première page, j’ai espéré que distill avait trouvé une façon d’avancer, mais ce n’était pas le cas.

  • Les GNN m’ont personnellement pas mal déçu. Je les ai appliqués plusieurs fois dans mes recherches, mais ça ne s’est jamais bien passé.
    Pendant longtemps, les GNN ont été présentés comme une généralisation des CNN, mais les CNN sont plus puissants parce que leurs « poids de voisinage » ont davantage de sens : ils apprennent des relations de position relative. Les GNN, eux, s’appuient généralement sur du pooling, comme expliqué ici. Un CNN peut produire une image en sortie, mais produire un graphe avec un GNN n’est pas facile. La topologie doit toujours être définie à l’avance, et parfois même pendant l’entraînement. Le coup de grâce, ce sont les performances : les GNN sont incroyablement lents par rapport aux CNN.
    Aujourd’hui, pour ces raisons, j’ai l’impression que l’attention a largement remplacé les GNN. On peut aussi construire des GNN qui utilisent l’attention au lieu du pooling, mais ça n’apporte pas grand-chose. En général, on parcourt le graphe uniquement pour construire une matrice de masque, puis on utilise un transformeur ordinaire pour le reste. Et s’il existe déjà une certaine mesure de distance, on n’a souvent même pas besoin de l’adjacence du graphe.
    Les GNN doivent bien être très utiles quelque part, pour quelqu’un, mais d’après mon expérience, c’était plutôt un marteau à la recherche d’un clou.

    • Il y a au moins un cas où les GNN sont utiles : quand les données sont un ensemble d’atomes dont les interactions définissent un élément de donnée, que cet ensemble est assez grand pour qu’on ne puisse pas s’en sortir en forçant grossièrement avec de l’attention, qu’il existe dans l’ensemble une structure de voisinage/géométrique définie par les interactions, et que la préserver rend les données équivariantes par permutation, sans qu’on trouve de moyen pertinent de représenter implicitement cette structure géométrique. Par exemple, quand la structure change d’un échantillon à l’autre, on transmet alors la structure de voisinage/d’interaction en entrée pour la traiter.
      Dans presque tous les autres cas, on peut exploiter une structure supplémentaire pour gagner en efficacité. Si l’on peut définir un ordre, on utilisera un modèle séquentiel ; s’il y a une structure euclidienne/riemannienne, un CNN ou un modèle conscient de la variété ; si l’on n’a pas besoin d’état global, un réseau de nuages de points ; s’il existe une hiérarchie explicite, une version U-Net adaptée à cette modalité, etc.
      Ce qui rend les GNN élégants, c’est qu’ils 1) encodent la notion même de relation et 2) ont un bon lien avec les équations différentielles discrétisées totalement générales. Pour quelqu’un qui travaille sur les systèmes complexes/dynamiques, c’est intéressant, mais si l’on peut spécialiser, il existe tout de même des méthodes plus simples.
    • Je me demande si tu parles de données régulières comme en vision.
      Pour les raisons que tu évoques, ce n’est pas un hasard si les GNN sont surtout populaires dans des domaines comme la recommandation, où le modèle de domaine lui-même ressemble à un graphe. Dans ces domaines, le saut vers une topologie utile est moins grand.
      Ce qui m’a personnellement encore plus frustré, c’est que beaucoup de ces domaines de type graphe reposent sur des données machine/humaines comportementales, comme des logs, avec énormément de dimensions catégorielles. La partie graphe aide, mais bien capturer les dimensions catégorielles est tout aussi important, et pour bien le faire on finit souvent par utiliser des méthodes hors de ce type de modèles, comme les forêts aléatoires. Il est plus simple de commencer par là, et la partie GNN ajoute beaucoup de travail pour « un petit gain supplémentaire ».
      Bien sûr, si c’est le cœur du business et que des millions de dollars sont en jeu, cela peut se justifier. Mais cela reste difficile pour la plupart des équipes d’exploitation. En pratique, avec des utilisateurs de pygraphistry, on finit souvent par faire quelque chose comme xgboost + umap et passer à autre chose. Rien que faire fonctionner correctement un RGCN demande déjà beaucoup d’efforts.
    • GraphCast de Google est un GNN : https://deepmind.google/discover/blog/graphcast-ai-model-for...
    • J’ai eu une expérience similaire. J’ai vu beaucoup de propositions visant à utiliser des GNN sur des problèmes qui utilisaient jusque-là des modèles « plats », par exemple en tenant compte de la structure HTML pour prédire des labels de page. Même dans des cas qui semblaient vraiment bien s’y prêter en apparence, ça n’a pas bien fonctionné.
    • J’ai suivi les GNN en biologie et les ai appliqués à quelques domaines, mais jusqu’ici les résultats ont été décevants. C’était un peu surprenant, car j’ai utilisé avec succès d’autres approches basées sur les graphes en biologie.

  • Les GNN semblent fonctionner sur une topologie fixe. Que faire si l’on veut approximer une transformation de la topologie du graphe ? Par exemple apprendre une mise en page de graphe, ou transformer l’arbre de syntaxe abstraite d’un programme en graphe de flux de données.

  • Le point essentiel des GNN est qu’ils généralisent à une topologie arbitraire en conditionnant explicitement la notion de « voisin » par le graphe qui spécifie la topologie. Le placement de graphes a été tenté ici et https://github.com/limbo018/DREAMPlace a beaucoup attiré l’attention, mais il existe aussi récemment des controverses à ce sujet https://www.semanticscholar.org/paper/The-False-Dawn%3A-Reev...
    Les transformations de graphes sont également étudiées https://arxiv.org/abs/2012.01470. Cela dit, c’est un problème délicat, car il faut implicitement résoudre le problème d’appariement de graphes

    • L’homologie pourrait peut-être aider. C’est une sorte de calcul différentiel pour les structures discrètes, qui consiste à compter combien de trous à N dimensions existent au fil du temps. Je ne sais pas pour les réseaux de neurones, mais on peut l’utiliser de cette façon en IRMf

  • J’aimerais que distill revienne

  • C’est vraiment dommage que distill.pub n’accepte plus de nouvelles soumissions

  • Je me demande quel est ce logiciel de visualisation interactive. D3.js ?

  • Je me sens vraiment idiot. Sur cette page, il y a un exemple avec 4 nœuds (a, b, c, d), et elle montre qu’il y a 24 combinaisons possibles
    Je me demande quelle est la formule généralisée pour calculer cela, étant donné un nombre de nœuds, et quand il faut aussi prendre en compte les arêtes. L’article ne semble pas l’expliquer, et je pense que c’est peut-être une factorielle

    • En combinatoire, on peut souvent calculer rapidement avec des factorielles. S’il y a 4 choix possibles et que, dans chaque cas, on choisit les 4 exactement une fois, c’est 4!. Intuitivement, au premier choix il y a 4 possibilités, puis 3, puis 2, et enfin 1. Donc 4 * 3 * 2 * 1 = 24
      Si vous voulez vous familiariser davantage avec le sujet, ce site semble offrir un assez bon aperçu : https://www.geeksforgeeks.org/mathematics-combinatorics-basi...
    • On pourrait probablement calculer cela avec un coefficient binomial, ou des coefficients binomiaux imbriqués. Par exemple, quelque chose comme (n choose 4)
      Comme chaque arête peut exister ou ne pas exister, il faudrait peut-être aussi multiplier le coefficient binomial par 2