Technische Samenvatting: Scheidingsvermogen van Equivariante Neurale Netwerken

Probleemstelling

De expressiviteit van machine learning-modellen wordt vaak gekwantificeerd door hun universaliteit—het vermogen om elke functie binnen een specifieke klasse te benaderen. Echter, voor equivariante neurale netwerken (die symmetrieën zoals permutaties of rotaties respecteren) wordt de universaliteit beperkt door de inherente onmogelijkheid van het netwerk om inputs te onderscheiden die equivalent zijn onder de symmetriegroep. Deze beperking creëert een complexe interactie tussen het vermogen van een netwerk om onderscheidende inputs te discrimineren en de invariante/equivariante structuren die het moet behouden.

Terwijl de grafenleer-gemeenschap uitgebreid heeft gestudeerd naar het scheidingsvermogen van Graph Neural Networks (GNN's) met behulp van de Weisfeiler-Leman (WL) test en homomorfietelling, hebben deze combinatorische instrumenten ernstige beperkingen wanneer ze worden toegepast op bredere klassen van equivariante modellen, met name die processen van geometrische data of gebruikmaken van reguliere convoluties. Er is een gebrek aan fijnmazige analytische instrumenten om de verzameling ononderscheidbare inputs (de identificatierelatie) te karakteriseren voor algemene equivariente neurale netwerken met niet-polynomiale activaties, einddimensionale representaties en permutatie-equivariantie.

Methodologie

Het artikel introduceert een theoretisch kader om het scheidingsvermogen $\rho(\mathcal{N})$ van een familie van equivariente neurale netwerken $\mathcal{N}$ te karakteriseren. Het scheidingsvermogen wordt gedefinieerd als de equivalentierelatie die paren inputs $(\alpha, \beta)$ identificeert waarvoor geldt dat $f(\alpha) = f(\beta)$ voor alle $f \in \mathcal{N}$.

De kern bijdrage van de methodologie is de "Twin Network Trick", die het probleem van het identificeren van ononderscheidbare inputs transformeert naar een nulverzamelingprobleem (zero locus problem). Door een tweelingnetwerk $\hat{\eta}(\alpha, \beta) = \eta(\alpha) - \eta(\beta)$ te construeren, herformuleren de auteurs de identificatierelatie als het vinden van de verzameling punten die door de tweelingnetwerkruimte naar nul worden afgebeeld.

Deze reductie stelt de auteurs in staat om recursieve technieken toe te passen die zijn afgeleid van de theorie van functionele vergelijkingen. Specifiek maken zij gebruik van resultaten met betrekking tot lineaire functionele vergelijkingen met niet-polynomiale continue functies (bijv. ReLU, sigmoid) om een expliciete, recursieve formule voor de nulverzameling af te leiden. Deze formule relateert de nulverzameling van een netwerk met diepte $d$ aan de nulverzamelingen van netwerken met diepte $d-1$, waarbij gebruik wordt gemaakt van unies en intersecties van specifieke subruimten gedefinieerd door de architectuur en bias-termen van het netwerk.

De analyse gaat uit van:

1. Permutatie-representaties: De netwerken opereren op ruimtes van reële functies over eindige verzamelingen, equivariant onder eindige groepen die optreden als permutaties.
2. Niet-polynomiale activaties: De activatiefuncties zijn continu en niet-polynomiaal.
3. Volledige Bias: De affine lagen bevatten bias-termen die ondergeschikt zijn aan de orbit-partitie van de representatieruimte.

Belangrijkste Bijdragen en Resultaten

1. Volledige Karakterisering van Ononderscheidbare Inputs

Het artikel biedt een volledige karakterisering van de verzameling inputparen die worden geïdentificeerd door netwerken met een vaste architectuur.

• Theorem 1 (Karakteriseringstheorema): Stelt een recursieve formule vast voor de nulverzameling van een neurale ruimte. Deze formule deelt de identificatierelatie op basis van de diepte van het netwerk, de eigenschappen van de activatie en de partitie van de representatieruimte geïnduceerd door de bias-termen.

2. Equivalentie van Niet-Polynomiale Activaties

• Theorem 2: Bewijst dat voor een vaste architectuur elke continue, reële, elementwijze, niet-polynomiale activatiefunctie dezelfde scheidingskracht oplevert. Bijgevolg zijn veelvoorkomende activaties zoals ReLU, sigmoid en tanh equivalent in hun vermogen om inputs te onderscheiden en bereiken ze allemaal de maximale scheidingskracht voor die architectuur. Polynomiale activaties zijn uitgesloten van deze equivalentie.

3. De Rol van Diepte

• Theorem 3: Demonstreert dat het vergroten van de diepte van het netwerk de scheidingskracht verhoogt tot een specifieke repetitiedrempel. Voorbij deze drempel leidt het toevoegen van verdere lagen van hetzelfde type niet tot een verbetering van het vermogen om inputs te onderscheiden; het scheidingsvermogen stabiliseert.
  • Voor $k$-Invariante Grafen Netwerken (IGN's) is deze drempel proportioneel aan de drempel van de $k$-WL test.
  • Voor netwerken met reguliere verborgen representaties vindt stabilisatie plaats na slechts één laag-repetitie.

4. Onafhankelijkheid van Verborgen Feature-breedte en Invariante Features

• Theorem 4 & Remark 1: Toont aan dat het scheidingsvermogen onafhankelijk is van de multipliciteit van blokken in verborgen representaties. Specifiek: het vergroten van de breedte van invariante verborgen features (bijv. de dimensie van de feature-ruimte in IGN's) verbetert het vermogen van het netwerk om inputs te onderscheiden niet. Het scheidingsvermogen van een netwerk met verborgen representatie $V \otimes \mathbb{R}^f$ is identiek aan dat van een netwerk met verborgen representatie $V$.

5. Hiërarchie van Representatietypes

• Theorem 5: Stelt een hiërarchie vast in scheidingskracht op basis van het type representatie dat in de lagen wordt gebruikt. Het scheidingsvermogen komt overeen met de partiële ordening van deelgroepen van de symmetriegroep.
  • Representaties geïnduceerd door kleinere deelgroepen (bijv. de triviale groep $\{e\}$, overeenkomend met de reguliere representatie) leveren een maximale scheidingskracht.
  • Representaties geïnduceerd door grotere deelgroepen (bijv. de groep $G$ zelf, overeenkomend met invariante vectoren) leveren een minimale scheidingskracht.
  • Dit impliceert dat het gebruik van reguliere representaties ($\mathbb{R}^G$) in verborgen lagen voldoende is om de maximale scheidingskracht te bereiken die door de architectuur wordt toegestaan.

Implicaties voor Praktische Modellen

De auteurs passen deze algemene resultaten toe op specifieke praktische modellen:

• Invariante Grafen Netwerken (IGN's): De resultaten versterken eerdere bevindingen door aan te tonen dat $k$-IGN's de scheidingskracht van de $k$-WL test evenaren, ongeacht de verborgen feature-dimensies. Dit lost de noodzaak op voor eerdere resultaten die "grote" verborgen feature-breedtes vereisten om universaliteit te bereiken.
• Circulaire CNN's: Het scheidingsvermogen van Circulaire Convolutionele Neurale Netwerken blijkt afhankelijk te zijn van de filtergrootte. Specifiek hebben netwerken met grotere filter-supports (die de volledige groep benaderen) een strikt fijnere scheidingskracht dan die met kleinere supports, wat een strikte hiërarchie vormt.

Betekenis en Claims

Het artikel beweert een noodzakelijke voorwaarde te bieden voor het begrijpen van de universaliteit van equivariente neurale netwerken. Door de identificatierelatie $\rho(\mathcal{N})$ nauwkeurig te karakteriseren, stellen de auteurs het mogelijk om hyperparameters en architecturale keuzes te classificeren in twee categorieën:

1. Scheidings-Bepalend: Keuzes die direct invloed hebben op de verzameling onderscheidbare inputs (bijv. type activatie, diepte tot een drempelwaarde, type representatie). Deze hebben een significante impact op zowel de benaderingscapaciteit als de computationele kosten.
2. Scheidings-Onafhankelijk: Keuzes die geen invloed hebben op de verzameling onderscheidbare inputs (bijv. verborgen feature-breedte, multipliciteit van blokken). Deze kunnen de benadering binnen de beperkingen van de scheidingskracht beïnvloeden, maar breiden de klasse van onderscheidbare inputs niet uit.

De auteurs benadrukken dat hun kader beperkt is tot permutatie-representaties en niet-polynomiale activaties. Zij erkennen dat hun aanpak momenteel niet uitbreidbaar is naar modellen die Clebsch-Gordan coëfficiënten of polynomiale benaderingen gebruiken, en dat het niet volledig de gevallen behandelt waarin bias-termen ontbreken (hoewel het in dergelijke gevallen wel grenzen kan bieden). Het werk dient als een fundamenteel theoretisch instrument voor het analyseren van de expressiviteit van equivariente modellen voorbij de combinatorische beperkingen van grafen-specifieke testen.