Technische Samenvatting: Weisfeiler–Leman is Onvolledig op Simpele Spectrumgrafen, dus Canoniseer Ze

Probleemstelling

Graph Neural Networks (GNN's) worden veel gebruikt voor leren op grafgestructureerde data, maar hun expressieve kracht wordt vaak begrensd door de Weisfeiler–Leman (WL) hiërarchie. Het is een bekend resultaat dat de $k$-dimensionale WL-test ($k$-WL) niet alle niet-isomorfe grafen kan onderscheiden. Een specifieke klasse van grafen echter—die met een simpel spectrum (waarbij de adjacentiematrix verschillende eigenwaarden heeft)—staat een isomorfietest in kubische tijd toe. Ondanks deze theoretische hanteerbaarheid bleef het een open vraag of de WL-hiërarchie, die de expressiviteit van veel GNN's bovenaf begrenst, alle grafen met een simpel spectrum kan onderscheiden.

Bovendien lijden spectrale positionele encodingen (zoals Laplacian-eigenvectoren), die vaak in GNN's worden geïntegreerd om de expressiviteit te vergroten, aan inherente ambiguïteiten: tekenambiguïteit voor simpele spectra en basisambiguïteit voor herhaalde eigenwaarden. Bestaande methoden om deze ambiguïteiten op te lossen (zoals SignNet, MAP en OAP) zijn bewezen onvolledig op grafen met een simpel spectrum en falen in het onderscheiden van bepaalde niet-isomorfe paren. Deze onvolledigheid beperkt het vermogen van spectrale GNN's om universele approximatie te bereiken op deze klasse van grafen.

Methodologie

1. Bewijs van WL-onvolledigheid op Simpele Spectra

De auteurs stellen eerst vast dat de gehele WL-hiërarchie onvolledig is op grafen met een simpel spectrum.

• Constructie: Zij maken gebruik van de Cai–Fürer–Immerman (CFI)-constructie, die paren van niet-isomorfe grafen genereert die niet door $k$-WL kunnen worden onderscheiden.
• Encoding: Aangezien standaard CFI-grafen geen simpel spectrum bezitten, introduceren de auteurs een nieuw integraal encodingmechanisme. Zij koppelen de CFI-adjacentiepatronen aan een orthogonale matrix $\tilde{X}$ bestaande uit gehele getallen.
• Vorming van Multigrafen: Met behulp van deze orthogonale matrix en een diagonaalmatrix met verschillende gehele eigenwaarden construeren zij een paar van symmetrische multigrafen ($A_{G,0}$ en $A_{G,1}$) met simpele spectra.
• Resultaat: Zij bewijzen dat deze geconstrueerde multigrafen met simpel spectrum ononderscheidbaar blijven door de $k$-WL-test, wat aantoont dat geen enkel niveau van de WL-hiërarchie het isomorfieprobleem voor deze klasse kan oplossen, ondanks dat het probleem in kubische tijd oplosbaar is.

2. PRiSM: Een Volledige Canonisatie

Om de beperkingen van bestaande spectrale methoden aan te pakken, stellen de auteurs PRiSM (Partition, Refine, Solve, Match) voor, een bewezen volledige canonisatieprocedure voor eigendecomposities van grafen met een simpel spectrum.

• Invoer: Een kolomsgewijs orthonormale matrix $U$ van eigenvectoren.
• Ambiguïteitsgroep: De procedure behandelt de ambiguïteitsgroep $S_n \times \{-1, 1\}^k$ (permutaties en tekenflip).
• Vier Stadia:
  1. Partitioneren: Vertices worden gegroepeerd op basis van hun teken-invariante signatuur (absolute waarden van eigenvector-invoer).
  2. Verfijnen: Een spectrale variant van de WL-kleurenverfijnprocedure wordt toegepast op de partitie. Dit verfijnt iteratief de vertexklassen met behulp van het multiset van randkenmerken gedefinieerd door elementgewijze producten van eigenvector-invoer ($U_v \odot U_u$) totdat de partitie stabiliseert.
  3. Oplossen: De stabiele partitie definieert een stelsel lineaire vergelijkingen over het veld $\mathbb{Z}_2$. Het stelsel eist dat elke partitieklasse ten minste één rij bevat met niet-negatieve invoer. Het oplossen van dit stelsel bepaalt de unieke canonieke tekens voor de eigenvectoren (tot op grafautomorfismen).
  4. Matchen: Zodra de tekens zijn vastgesteld, worden de rijen lexico grafisch gesorteerd om de permutatie-ambiguïteit op te lossen, wat resulteert in een unieke canonieke matrix.
• Extensie: Voor grafen met herhaalde eigenwaarden (geen simpel spectrum) wordt PRiSM heuristisch uitgebreid. De basisprocedure wordt toegepast op het blok met simpel spectrum ($m=1$) en QR-decompositie met pivotselectie wordt gebruikt om hogere-orde eigenruimten op te lossen ($m > 1$).

3. Theoretische Garanties

• Volledigheid: PRiSM is bewezen een geldige canonisatie te zijn, wat betekent dat het dezelfde output produceert voor isomorfe grafen en verschillende output voor niet-isomorfe grafen met een simpel spectrum.
• Universele Approximatie: Door PRiSM te combineren met een universele setnetwerk (zoals DeepSets of Transformers), bereikt het resulterende model universele approximatie voor elke isomorfie-invariante functie op grafen met een simpel spectrum. Dit lost het open probleem op van het bereiken van volledigheid voor spectrale GNN's op deze klasse.

Belangrijkste Resultaten

Theoretische Bevindingen

• Stelling 1: Voor elk natuurlijk getal $k$ bestaan er niet-isomorfe multigrafen met een simpel spectrum en $\Theta(k)$ knopen die niet worden onderscheiden door het $k$-WL-algoritme. Dit impliceert dat alle $k$-WL-uitgelijnde GNN-families (inclusief PPGN, $k$-GNN's en Graph Transformers) onvolledig zijn op grafen met een simpel spectrum.
• Stelling 2: PRiSM biedt een geldige canonisatie voor eigendecomposities met een simpel spectrum.
• Stelling 3: Modellen samengesteld uit PRiSM en universele setnetwerken bereiken universele approximatie op grafen met een simpel spectrum.

Empirische Prestaties

De auteurs hebben PRiSM geëvalueerd op drie benchmarks:

1. BREC Expressivity Benchmark: PRiSM presteerde beter dan concurrerende canonisaties (MAP, OAP) in het onderscheiden van niet-isomorfe grafparen, met name in de categorieën Regular en Extension. Het onderscheidde correct 212/360 paren, vergeleken met 199/360 voor MAP/OAP.
2. Voorspelling van Moleculaire Eigenschappen (ZINC, OGB-Mol): PRiSM behaalde state-of-the-art of gelijk beste prestaties op moleculaire regressie (ZINC) en classificatie (MOLTOX21, MOLPCBA) taken, met zowel GatedGCN- als PNA-ruggengraten.
3. Transformer-ruggengraten (OGB, Alchemy): Wanneer gebruikt als positionele encoding voor Graph Transformers, presteerde PRiSM beter dan alle baselines (LPE, MAP, OAP) op alle vier de datasets (MOLHIV, MOLCLINTOX, MOLBBBP, ALCHEMY). De auteurs schrijven dit toe aan het feit dat PRiSM een deterministische vertexordening biedt in aanvulling op teken-correcte eigenvectoren, wat cruciaal is voor Transformer-attentie-mechanismen.

Betekenis en Claims

Het artikel claimt een fundamentele kloof in het theoretische begrip van GNN-expressiviteit en spectrale methoden op te lossen:

1. Onvolledigheid van WL: Het bewijst definitief dat de WL-hiërarchie, ondanks haar toenemende kracht, niet alle grafen met een simpel spectrum kan onderscheiden, een klasse waarbij isomorfie theoretisch eenvoudig is.
2. Eerste Volledige Canonisatie: PRiSM wordt gepresenteerd als de eerste bewezen volledige teken-canonisatie voor eigendecomposities met een simpel spectrum, die de beperkingen van eerdere methoden zoals MAP en OAP overwint, die onvolledig zijn op deze klasse.
3. Universele Approximatie: Het werk stelt vast dat spectrale GNN's universele approximatie kunnen bereiken op grafen met een simpel spectrum als ze worden gekoppeld aan een volledige canonisatie zoals PRiSM, wat het gebruik van gecanoniseerde Laplacian-positionele encodingen rechtvaardigt.
4. Praktisch Nut: Empirisch toont de methode aan dat het volledig oplossen van spectrale ambiguïteiten leidt tot tastbare verbeteringen in downstream-taken, en beter presteert dan bestaande teken-invariante en canonisatie-aanpakken.

De auteurs merken beperkingen op, specifiek dat de volledigheidsgarantie strikt geldt voor grafen met een simpel spectrum (of multigrafen geconstrueerd in het bewijs) en dat de canonisatieprocedure discontinu is, een eigenschap die zij betogen wiskundig onvermijdelijk is voor volledige teken-canonisaties. Zij laten de uitbreiding van het onvolledigheidsbewijs naar simpele combinatorische grafen (zonder meerdere randen) over als toekomstig werk.