Directed Acyclic Graph Convolutional Networks

Résumé technique : Réseaux de convolution sur graphes acycliques orientés (DCN)

Énoncé du problème
Les graphes acycliques orientés (DAG) sont fondamentaux pour les applications impliquant l'inférence causale, la planification et la conception d'architectures neuronales. Cependant, l'apprentissage à partir de signaux supportés sur des DAG présente des défis uniques pour les réseaux de neurones sur graphes (GNN). Les GNN standards reposent sur un passage de messages itératif et une analyse spectrale basée sur des opérateurs de décalage de graphe (GSO). Dans les DAG, la matrice d'adjacence est strictement triangulaire inférieure et nilpotente, ce qui entraîne un spectre effondré (toutes les valeurs propres sont nulles). Cela rend les outils standards de la théorie spectrale des graphes vains et empêche l'application directe des GNN convolutifs conventionnels. De plus, les mécanismes d'agrégation génériques dans les GNN standards ne tiennent pas explicitement compte du fort biais inductif de l'ordre partiel inhérent aux DAG. Les modèles spécifiques aux DAG existants, tels que D-VAE et DAGNN, reposent souvent sur des opérations séquentielles intensives en calcul (par exemple, des unités récurrentes) qui ne se généralisent pas bien aux grands graphes.

Méthodologie
Les auteurs proposent le Réseau de convolution sur DAG (DCN), une architecture novatrice fondée sur les principes du traitement du signal sur graphes (GSP) adaptés aux DAG. La méthodologie centrale repose sur des filtres de graphe causaux dérivés du cadre de la fermeture transitive pondérée.

1. Opérateurs de décalage de graphe causaux (GSO) : Au lieu d'utiliser la matrice d'adjacence $A$, le DCN utilise un ensemble de GSO causaux $\{S_k\}_{k \in V}$. Ces opérateurs sont définis via la matrice de fermeture transitive pondérée $W = (I - A)^{-1}$, qui correspond au graphe de reachabilité du DAG. Un GSO causal $S_k$ agrège les contributions du signal provenant des ancêtres communs d'un nœud $v_i$ et d'un nœud de référence $v_k$.
2. Interprétation spectrale : Les colonnes de $W$ servent de base de Fourier pour les signaux DAG. Les GSO causaux sont idempotents et partagent $W$ comme leur matrice de vecteurs propres, permettant une représentation bien définie dans le domaine spectral où le filtrage correspond à une mise à l'échelle ponctuelle des coefficients de Fourier.
3. Architecture DCN : Le DCN implémente des convolutions couche par couche en utilisant une banque de ces GSO causaux. Pour un signal d'entrée $X$, la sortie de la couche $\ell$ est calculée comme suit :
   $$X^{(\ell)} = \sigma \left( \sum_{k \in V} S_k X^{(\ell-1)} \Theta^{(\ell)}_k \right)$$
   où $\Theta^{(\ell)}_k$ sont des coefficients de filtre appris et $\sigma$ est une non-linéarité. Cette structure capture efficacement les dépendances à long terme des ancêtres via des multiplications de matrices clairsemées.
4. DCN Parallèle (PDCN) : Pour résoudre les problèmes de mise à l'échelle où le nombre de paramètres dans le DCN croît linéairement avec le nombre de nœuds $N$, les auteurs introduisent le PDCN. Cette variante traite les signaux décalés $\{S_k X\}$ dans des branches parallèles via un Perceptron Multicouche (MLP) partagé, et les sorties sont sommées. Cette conception découple le nombre de paramètres appris de la taille du graphe, le rendant évolutif pour de grands $N$.

Contributions clés

• Architecture novatrice : Le développement du DCN, qui formalise les opérations convolutives sur les DAG en utilisant des filtres de graphe causaux, fournissant une interprétation spectrale précédemment indisponible pour les signaux DAG.
• Variante évolutive : L'introduction du PDCN, qui maintient les performances prédictives tout en garantissant que le nombre de paramètres reste constant quelle que soit la taille du DAG.
• Propriétés théoriques :
  • Équivariance par permutation : Les auteurs prouvent que le DCN et le PDCN sont équivariants par permutation, assurant une robustesse face au reclassement des nœuds.
  • Puissance expressive : Il est établi que le PDCN satisfait les conditions du test de Weisfeiler-Lehman (WL), capable de distinguer des DAG non isomorphes.
  • Unicité : La proposition 2 démontre que l'ensemble des GSO causaux identifie de manière unique la structure sous-jacente du DAG.
• Efficacité : L'architecture exploite des opérations de matrices clairsemées et des opérateurs de décalage précalculables, offrant des avantages computationnels significatifs par rapport aux modèles de DAG séquentiels.

Résultats expérimentaux
L'article évalue le (P)DCN sur des données synthétiques et réelles par rapport à des références de l'état de l'art (incluant GCN, GIN, D-VAE, DAGNN et DAG+NodeFormer).

• Tâches synthétiques :
  • Apprentissage de la diffusion : Le DCN atteint une erreur quadratique moyenne normalisée (NMSE) inférieure aux références dans la prédiction de signaux diffusés, démontrant une robustesse supérieure au bruit et aux densités d'arêtes variables.
  • Identification de sources : Les variantes du DCN (utilisant spécifiquement des GSO transposés) atteignent une haute précision dans le traçage des sources de signaux, surpassant les modèles agnostiques aux DAG et montrant une meilleure évolutivité que les modèles séquentiels comme DAGNN.
  • Évolutivité : À mesure que la taille du graphe augmente (jusqu'à $N=1000$), le DCN et le PDCN maintiennent leurs performances et des temps d'entraînement raisonnables, tandis que des modèles comme DAGNN et D-VAE échouent à se terminer (DNF) en raison de contraintes de mémoire et de temps.
• Applications réelles :
  • Imputation de l'expression génique : Sur un jeu de données d'Arabidopsis Thaliana, le DCN et le PDCN imputent avec succès les niveaux d'expression génique manquants, atteignant une NMSE comparable à D-VAE et DAGNN mais avec un nombre de paramètres inférieur de plusieurs ordres de grandeur et des temps d'entraînement plus rapides.
  • Prévision hydrologique : Sur les données de la Tamise, le DCN surpasse toutes les références dans la prédiction des concentrations chimiques sur des sites non observés, exploitant efficacement la structure d'écoulement amont-aval.

Signification et affirmations
L'article positionne le (P)DCN comme un cadre viable pour l'apprentissage profond sur des données structurées en DAG, conçu à partir des principes fondamentaux du traitement du signal sur graphes. Les auteurs affirment que, en intégrant l'ordre partiel des DAG directement dans les opérateurs convolutifs, les modèles atteignent un fort biais inductif qui améliore la précision, la robustesse et l'efficacité computationnelle par rapport aux méthodes existantes. Ce travail comble le fossé entre les modèles d'inférence causale et l'apprentissage profond, offrant une alternative fondée sur des principes aux méthodes d'agrégation séquentielle. Les auteurs reconnaissent les limites, notant que la dépendance à un grand nombre de GSO dans le DCN complet peut encore poser des défis pour des graphes très grands, suggérant un travail futur sur la sélection adaptative des GSO.