Résumé Technique : Pouvoir de Séparation des Réseaux de Neurones Équivariants

Énoncé du Problème

L'expressivité des modèles d'apprentissage automatique est souvent quantifiée par leur universalité — la capacité à approximer n'importe quelle fonction au sein d'une classe spécifique. Cependant, pour les réseaux de neurones équivariants (ceux respectant des symétries telles que les permutations ou les rotations), l'universalité est contrainte par l'incapacité inhérente du réseau à distinguer des entrées qui sont équivalentes sous le groupe de symétrie. Cette limitation crée une interaction complexe entre la capacité d'un réseau à discriminer des entrées distinctes et les structures invariantes/équivariantes qu'il doit préserver.

Bien que la communauté de l'apprentissage sur graphes ait étudié de manière extensive le pouvoir de séparation des réseaux de neurones sur graphes (GNN) en utilisant le test de Weisfeiler-Leman (WL) et le comptage d'homomorphismes, ces outils combinatoires présentent de sévères limitations lorsqu'ils sont appliqués à des classes plus larges de modèles équivariants, particulièrement ceux traitant des données géométriques ou utilisant des convolutions régulières. Il existe un manque d'outils analytiques fins pour caractériser l'ensemble des entrées indiscernables (la relation d'identification) pour les réseaux de neurones équivariants généraux avec des activations non polynomiales, des représentations de dimension finie et une équivariance par permutation.

Méthodologie

Le papier introduit un cadre théorique pour caractériser le pouvoir de séparation $\rho(\mathcal{N})$ d'une famille de réseaux de neurones équivariants $\mathcal{N}$. Le pouvoir de séparation est défini comme la relation d'équivalence identifiant les paires d'entrées $(\alpha, \beta)$ telles que $f(\alpha) = f(\beta)$ pour tout $f \in \mathcal{N}$.

La contribution méthodologique centrale est l'« Astuce du Réseau Jumeau » (Twin Network Trick), qui transforme le problème d'identification des entrées indiscernables en un problème de lieu nul (zero locus). En construisant un réseau jumeau $\hat{\eta}(\alpha, \beta) = \eta(\alpha) - \eta(\beta)$, les auteurs reformulent la relation d'identification comme la recherche de l'ensemble des points projetés vers zéro par l'espace du réseau jumeau.

Cette réduction permet aux auteurs d'appliquer des techniques récursives dérivées de la théorie des équations fonctionnelles. Plus précisément, ils exploitent des résultats concernant les équations fonctionnelles linéaires impliquant des fonctions continues non polynomiales (par exemple, ReLU, sigmoid) pour dériver une formule explicite et récursive pour le lieu nul. Cette formule relie le lieu nul d'un réseau de profondeur $d$ aux lieux nuls de réseaux de profondeur $d-1$, impliquant des unions et des intersections d'espaces spécifiques définis par l'architecture du réseau et les termes de biais.

L'analyse suppose :

1. Représentations par Permutation : Les réseaux agissent sur des espaces de fonctions à valeurs réelles sur des ensembles finis, équivariants sous des groupes finis agissant comme des permutations.
2. Activations Non Polynomiales : Les fonctions d'activation sont continues et non polynomiales.
3. Biais Complet : Les couches affines incluent des termes de biais subordonnés à la partition d'orbite de l'espace de représentation.

Contributions Clés et Résultats

1. Caractérisation Complète des Entrées Indiscernables

Le papier fournit une caractérisation complète de l'ensemble des paires d'entrées identifiées par des réseaux possédant une architecture fixe.

• Théorème 1 (Théorème de Caractérisation) : Établit une formule récursive pour le lieu nul d'un espace neuronal. Cette formule décompose la relation d'identification en fonction de la profondeur du réseau, des propriétés d'activation et de la partition de l'espace de représentation induite par les termes de biais.

2. Équivalence des Activations Non Polynomiales

• Théorème 2 : Prouve que pour une architecture fixée, toute fonction d'activation continue, réelle, élément par élément et non polynomiale produit le même pouvoir de séparation. Par conséquent, les activations communes comme ReLU, sigmoid et tanh sont équivalentes dans leur capacité à distinguer les entrées et atteignent toutes le pouvoir de séparation maximal pour cette architecture. Les activations polynomiales sont exclues de cette équivalence.

3. Le Rôle de la Profondeur

• Théorème 3 : Démontre qu'augmenter la profondeur du réseau améliore le pouvoir de séparation uniquement jusqu'à un certain seuil de répétition. Au-delà de ce seuil, l'ajout de couches supplémentaires du même type n'améliore pas la capacité à distinguer les entrées ; le pouvoir de séparation se stabilise.
  • Pour les réseaux de graphes $k$-invariants (IGNs), ce seuil est proportionnel au seuil du test $k$-WL.
  • Pour les réseaux avec des représentations cachées régulières, la stabilisation survient après seulement une répétition de couche.

4. Indépendance vis-à-vis de la Largeur des Caractéristiques Cachées et des Caractéristiques Invariantes

• Théorème 4 & Remarque 1 : Montre que le pouvoir de séparation est indépendant de la multiplicité des blocs dans les représentations cachées. Plus précisément, augmenter la largeur des caractéristiques cachées invariantes (par exemple, la dimension de l'espace de caractéristiques dans les IGNs) n'améliore pas la capacité du réseau à distinguer les entrées. Le pouvoir de séparation d'un réseau avec la représentation cachée $V \otimes \mathbb{R}^f$ est identique à celui d'un réseau avec la représentation cachée $V$.

5. Hiérarchie des Types de Représentation

• Théorème 5 : Établit une hiérarchie dans le pouvoir de séparation basée sur le type de représentation utilisé dans les couches. Le pouvoir de séparation correspond à l'ordre partiel des sous-groupes du groupe de symétrie.
  • Les représentations induites par des sous-groupes plus petits (par exemple, le sous-groupe trivial $\{e\}$, correspondant à la représentation régulière) produisent un pouvoir de séparation maximal.
  • Les représentations induites par des sous-groupes plus grands (par exemple, le groupe $G$ lui-même, correspondant aux vecteurs invariants) produisent un pouvoir de séparation minimal.
  • Cela implique que l'utilisation de représentations régulières ($\mathbb{R}^G$) dans les couches cachées est suffisante pour atteindre le pouvoir de séparation maximal autorisé par l'architecture.

Implications pour les Modèles Pratiques

Les auteurs appliquent ces résultats généraux à des modèles pratiques spécifiques :

• Réseaux de Graphes Invariants (IGNs) : Les résultats renforcent les découvertes précédentes en montrant que les $k$-IGNs correspondent au pouvoir de séparation du test $k$-WL, indépendamment des dimensions des caractéristiques cachées. Cela résout la nécessité des résultats précédents qui exigeaient de « grandes » largeurs de caractéristiques cachées pour atteindre l'universalité.
• CNN Circulaires : Le pouvoir de séparation des réseaux de neurones convolutifs circulaux est montré comme dépendant de la taille du filtre. Plus précisément, les réseaux avec des supports de filtres plus larges (approchant la taille totale du groupe) possèdent un pouvoir de séparation strictement plus fin que ceux avec des supports plus petits, formant une hiérarchie stricte.

Signification et Revendications

Le papier prétend fournir une condition nécessaire pour comprendre l'universalité des réseaux de neurones équivariants. En caractérisant précisément la relation d'identification $\rho(\mathcal{N})$, les auteurs permettent une classification des hyperparamètres et des choix architecturaux en deux catégories :

1. Déterminant la Séparation : Choix qui influencent directement l'ensemble des entrées distinguables (ex: type d'activation, profondeur jusqu'à un seuil, type de représentation). Ils impactent significativement tant la capacité d'approximation que le coût computationnel.
2. Indépendant de la Séparation : Choix qui n'affectent pas l'ensemble des entrées distinguables (ex: largeur des caractéristiques cachées, multiplicité des blocs). Ils peuvent influencer l'approximation dans les limites du pouvoir de séparation, mais n'élargissent pas la classe des entrées distinguables.

Les auteurs soulignent que leur cadre est limité aux représentations de permutation et aux activations non polynomiales. Ils reconnaissent que leur approche ne s'étend pas actuellement aux modèles utilisant des coefficients de Clebsch-Gordan ou des approches polynomiales, et qu'elle ne traite pas pleinement les cas où les termes de biais sont absents (bien qu'elle puisse fournir des bornes dans ces cas). Ce travail sert d'outil théorique fondamental pour analyser l'expressivité des modèles équivariants au-delà des contraintes combinatoires des tests spécifiques aux graphes.