Technische Samenvatting: Wanneer en Hoe te Canoniseren: Een Generalisatieperspectief

Probleemstelling

In domeinen met symmetrische data (bijvoorbeeld grafen, 3D-puntenwolken, moleculaire structuren) zijn de doelwitfuncties vaak invariant ten opzichte van specifieke groepswerkingen. Hoewel gespecialiseerde invariante architecturen standaard zijn, is er groeiende interesse in het bereiken van invariantie door canonisatie toe te passen op niet-invariante backbones. Canonisatie beeldt elke groep-orbit af op één enkel, consistent "canoniek" element, wat rekenkundige efficiëntie biedt in vergelijking met volledige groepsgemiddelde. De theoretische generalisatie-eigenschappen van canonisatie, met name hoe ze zich verhouden tot groepsgemiddelde en hoe de kwaliteit van verschillende canonisatiemethoden het leren beïnvloedt, blijven echter slecht begrepen. Dit artikel adresseert het gebrek aan een rigoureus theoretisch kader om de generalisatiefout van gecanoniseerde modellen te analyseren.

Methodologie

De auteurs introduceren een theoretisch kader gebaseerd op overdekkingsgetallen om de generalisatiefout van invariante modellen te analyseren. Zij maken gebruik van een standaard kader voor generalisatiegrenzen (gebaseerd op [32]) dat generalisatiefout relateert aan de Lipschitz-constanten van het model en de doelwitfunctie, en het overdekkingsgetal van het invoerdomein.

De studie vergelijkt drie soorten modellen:

1. Niet-invariante baselines: $h = \tilde{h}$ (geen symmetriebehandeling).
2. Gecanoniseerde modellen: $h = \tilde{h} \circ c$, waarbij $c$ een canonisatiefunctie is.
3. Met groep gemiddelde modellen: $h(x) = \int_G \tilde{h}(gx) dg$.

De kern van de methodologie bestaat uit het afleiden van bovengrenzen voor de generalisatiefout van deze modellen door de overdekkingsgetallen van hun respectieve domeinen te begrenzen:

• Niet-invariant: De oorspronkelijke ruimte $K$.
• Gecanoniseerd: Het beeld van de canonisatie $c(K)$.
• Met groep gemiddeld/Invariant: De quotiëntruimte $K/G$.

De auteurs stellen een hiërarchie van overdekkingsgetallen vast: $N(K/G) \leq N(c(K)) \leq N(K)$. Zij onderzoeken verder de voorwaarden waaronder een canonisatie $c$ de ondergrens (optimaal) of de bovengrens (slecht) bereikt, en koppelen deze eigenschappen aan de continuïteit en isometrie van de canonisatiefunctie.

Belangrijkste Bijdragen

1. Generalisatiehiërarchie van Canonisatie versus Groepsgemiddelde

Het artikel bewijst dat de generalisatiefoutgrenzen van gecanoniseerde modellen in het beste geval gelijk zijn aan die van met groep gemiddelde modellen en in het slechtste geval gelijk aan niet-invariante baselines.

• Theoretisch Resultaat: $N(K/G, \rho_G, \epsilon) \leq N(c(K), \rho, \epsilon) \leq N(K, \rho, \epsilon)$.
• Implicatie: Hoewel canonisatie rekenkundige voordelen biedt (verwerking van één vertegenwoordiger), kan dit ten koste gaan van de generalisatieprestaties in vergelijking met groepsgemiddelde, afhankelijk van de specifieke gebruikte canonisatie.

2. De Rol van Continuïteit en Isometrie

De auteurs karakteriseren "optimale" en "slechte" canonisaties op basis van hun regulariteit:

• Optimale Canonisaties: Isometrische canonisaties (waarbij $\rho(c(x), c(y)) = \rho_G([x], [y])$) bereiken de optimale ondergrens voor overdekkingsgetallen en komen overeen met de prestaties van groepsgemiddelde. Voorbeelden zijn sorteren voor permutaties en centralisatie voor translaties. Cruciaal is dat isometrische canonisaties altijd continu zijn.
• Slechte Canonisaties: Discontinue canonisaties kunnen leiden tot "slechte" prestaties waarbij het overdekkingsgetal van het gecanoniseerde beeld gelijk is aan dat van de oorspronkelijke niet-invariante ruimte. Het artikel demonstreert dat als een canonisatie $|G|$ partiële limieten heeft in een punt (sterke discontinuïteit), een adversariaal domein kan worden geconstrueerd waarbij de generalisatiegrens degradeert tot die van een niet-invariant model.

3. Casestudie: Lexicografisch Sorteren versus Hilbert-curve Canonisatie

Toepassing van het kader op verwerking van puntenwolken (permutatiegroep $S_n$):

• Lexicografisch Sorteren (Lexsort): Het artikel bewijst dat het overdekkingsgetal van Lexsort exponentieel groeit met het aantal punten $n$ (specifiek, $\Omega((1/2\epsilon)^{(d-1)n+1})$). Dit wordt toegeschreven aan de ernstige discontinuïteiten van Lexsort wanneer de eerste coördinaat van punten identiek is.
• Hilbert-curve Canonisatie: Daarentegen groeit het overdekkingsgetal van de Hilbert-curve canonisatie slechts polynomiëel in $n$.
• Betekenis: Dit biedt de eerste formele theoretische rechtvaardiging voor het empirische succes van Hilbert-curve serialisatie in state-of-the-art architecturen zoals Point Transformer V3 [30], en verklaart waarom het Lexsort overtreft in generalisatie.

Experimentele Resultaten

De auteurs voerden experimenten uit om hun theoretische claims te valideren:

• Coverage op ModelNet: Met behulp van real-world puntenwolken-data volgde de "coverage" (een proxy voor overdekkingsgetal) de theoretische hiërarchie: Groepsafstand (quotiënt) < Hilbert < Lexsort < Euclidisch (niet-invariant).
• Classificatieprestaties: Op ModelNet10 en ModelNet40 behaalde een eenvoudige MLP met Hilbert-canonisatie de hoogste testnauwkeurigheid en de laagste generalisatiefout (Test Acc - Train Acc), en presteerde beter dan zowel Lexsort als niet-invariante baselines.
• Groepsgemiddelde versus Canonisatie: Experimenten op ModelNet (met PCA voor rotatie) en Rotated MNIST bevestigden dat groepsgemiddelde (of augmentatie die dit benadert) over het algemeen beter presteert dan canonisatie qua nauwkeurigheid, wat de theoretische hiërarchie ondersteunt waarbij gemiddelde optimaal is.
• Spectrale Embeddings: Aanvullende experimenten op graf-spectrale embeddings (ogbg-molpcba) toonden aan dat willekeurige groepaugmentatie (die gemiddelde benadert) vergelijkbaar presteerde met deterministische canonisatie, wat overeenkomt met de theorie dat voor kleine groepen het verschil verwaarloosbaar kan zijn, maar dat de hiërarchie geldt.

Betekenis en Claims

Het artikel claimt de eerste formele theoretische rechtvaardiging te bieden voor de empirische voorkeur voor Hilbert-curve serialisatie boven lexicografisch sorteren in de verwerking van puntenwolken. Het stelt een rigoureuze methodologie vast voor het vergelijken van verschillende canonisatiestrategieën via overdekkingsgetallen, en verschuift de focus van het louter onderscheiden van symmetrische voorbeelden naar het analyseren van de geometrische eigenschappen (regulariteit/continuïteit) die generalisatie beïnvloeden.

De auteurs concluderen dat hoewel met groep gemiddelde modellen theoretisch preferabel zijn voor generalisatie, ze vaak rekenkundig onhandelbaar zijn. Daarom is de keuze van canonisatie cruciaal: continue, isometrische canonisaties (zoals Hilbert-curves) zijn noodzakelijk om de generalisatiegrenzen van groepsgemiddelde te benaderen, terwijl discontinue canonisaties (zoals Lexsort) het risico lopen de prestaties te degraderen tot het niveau van niet-invariante modellen. Het werk vult bestaande literatuur aan door te benadrukken dat de kwaliteit van de canonisatiefunctie, specifiek haar continuïteit, een doorslaggevende factor is in leerprestaties.