🤖 machine learning

Universality and Approximation Rates of Graph Neural Networks with Random Features

Dit artikel stelt vast dat message-passing graph neural networks met gedeeltelijk willekeurige node-features beschikken over universele benaderingscapaciteiten voor permutatie-invariante en equivariante functies op grafen van vaste grootte, terwijl het ook theoretische bovengrenzen afleidt voor hun benaderingssnelheden op basis van netwerkcomplexiteit.

Oorspronkelijke auteurs: Lukas Gonon, Thilo Meyer-Brandis, Niklas Weber

Gepubliceerd 2026-07-30

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Lukas Gonon, Thilo Meyer-Brandis, Niklas Weber

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Raadsel van de Vormveranderende Menigte

Stel je voor dat je een computer probeert te leren de wereld te begrijpen, niet als een raster van pixels of een lijst met woorden, maar als een web van verbindingen. Dit is het domein van Graph Neural Networks (GNN's), een tak van kunstmatige intelligentie die is ontworpen om data te verwerken die lijkt op een kaart van vrienden, moleculen of verkeersroutes. In deze kaarten is het belangrijkste niet alleen wat een individueel item is, maar hoe het verbonden is met zijn buren.

Er is echter een lastige regel waar deze computers aan moeten voldoen: symmetrie. Als je een groep vrienden hebt en je wisselt hun namen om, blijft de groep nog steeds dezelfde groep. Een goede grafiek-AI zou niet moeten geven om wie er in stoel A of stoel B zit; het zou alleen moeten geven om het patroon van wie met wie praat. Dit wordt permutatie-invariantie (voor de hele groep) of permutatie-equivariantie (voor de individuen) genoemd. Het probleem is dat standaard AI-modellen hier erg slecht in zijn. Ze raken vaak in de war door de volgorde waarin data binnenkomt, waardoor ze niet herkennen dat twee verschillend ogende lijsten met namen eigenlijk precies dezelfde sociale kring beschrijven.

Om dit op te lossen, hebben wetenschappers geprobeerd de AI "willekeurige ruis" of "willekeurige ID's" te geven om het te helpen individuen uit elkaar te houden, vergelijkbaar met het geven van een tijdelijke, unieke sticker aan elk persoon in een menigte. Maar tot nu toe wisten we niet volledig of deze truc de AI slim genoeg kon maken om elk mogelijk patroon te leren, of dat er grenzen waren aan hoe goed het complexe regels kon leren. Dit artikel duikt diep in die vraag, met de vraag: "Als we deze grafiek-lezende computers voorzien van willekeurige stickers, kunnen ze dan perfect worden in het begrijpen van elke grafiekstructuur?"

De Magie van Willekeurige Stickers

De auteurs van dit artikel, Lukas Gonon, Thilo Meyer-Brandis en Niklas Weber, zetten zich in om te bewijzen dat een specifiek type grafiek-AI, een Permutation-Equivariant Neural Network (PENN), ongelooflijk krachtig wordt wanneer je het voorziet van willekeurige knoopkenmerken (node features). Zie een PENN als een team detectives dat een mysterie probeert op te lossen op een kaart. Normaal gesproken, als twee verdachten er identiek uitzien en dezelfde vrienden hebben, kunnen de detectives hen niet van elkaar onderscheiden. Maar als je elke verdachte een willekeurige, unieke sticker (een willekeurig kenmerk) geeft, kunnen de detectives hen eindelijk onderscheiden en de zaak oplossen.

De belangrijkste ontdekking van het artikel is een "universele" garantie. De auteurs hebben wiskundig bewezen dat als je deze PENNs willekeurige stickers voert, ze elke meetbare functie op een grafiek van een vaste grootte kunnen benaderen met een bijna zekere waarschijnlijkheid (arbitrarily high probability). In gewone mensentaal: als je wilt dat de AI een specifieke regel over een netwerk leert (zoals voorspellen of een molecuul giftig is of welk financieel netwerk een risico loopt), en je geeft het genoeg willekeurige stickers, dan is er een PENN-architectuur die die regel bijna perfect kan leren. Dit geldt zelfs als de regel rommelig of complex is, en zelfs als de data veel verschillende soorten kenmerken aan de knopen en randen heeft verbonden.

Hoe Goed is "Goed Genoeg"?

Maar het artikel zegt niet alleen "het werkt"; het vertelt je ook hoe groot de AI moet zijn om de klus te klaren. De auteurs keken naar functies die vloeiend en goed gedefinieerd zijn (wiskundig gezien " $k$ -maal continu differentieerbaar", waarbij $k \ge 2$ ). Ze hebben een formule afgeleid voor de benaderingssnelheden, wat in feid een snelheidslimiet is voor hoe snel de AI leert naarmate hij groter wordt.

Ze ontdekten dat de diepte van het netwerk (het aantal lagen) slechts logaritmisch hoeft te groeien naarmate je meer nauwkeurigheid eist. Dit is goed nieuws: als je twee keer zo nauwkeurig wilt zijn, hoef je niet de omvang van de hersenen te verdubbelen; je hebt slechts een klein beetje extra diepte nodig. Echter, het aantal verbindingen (niet-nul gewichten) groeit polynoom naarmate je meer nauwkeurigheid eist. Specifiek schalen de complexiteit met een macht van $1/\epsilon$ , waarbij $\epsilon$ je gewenste foutmarge is. Het artikel merkt op dat deze macht afhangt van de "gladheid" van de regel die je probeert te leren ( $k$ ) en de grootte van de grafiek ( $N$ ). In essentie, voor zeer complexe, grillige regels of zeer grote grafieken heb je veel meer verbindingen nodig, maar voor gladde regels blijft de AI efficiënt.

De "Gemiddelde" Truc voor Veiligheid

Een van de meest speelse en praktische inzichten van het artikel behandelt een bijeffect van het gebruik van willekeurige stickers. Omdat de stickers willekeurig zijn, kan het zijn dat als je de AI één keer draait, hij een iets andere uitkomst geeft dan wanneer je hem opnieuw draait met andere stickers. Dit doorbreekt de symmetrie-regel: de AI kan dezelfde groep vrienden anders behandelen, simpelweg omdat de stickers veranderd zijn.

De auteurs stellen een slimme oplossing voor: middelen (averaging). Als je de AI vele malen draait met verschillende willekeurige stickers en het gemiddelde van de resultaten neemt, valt de willekeur weg en wordt de AI weer perfect symmetrisch. Ze bewezen dat deze "gemiddelde" versie nog steeds de superkracht bezit om elke regel te kunnen leren. Het is also wordt je een menigte mensen vraagt om het gewicht van een pompoen te raden; één persoon kan er flink naast zitten, maar als je het gemiddelde neemt van de schattingen van honderd mensen, krijg je een zeer nauwkeurig antwoord. Het artikel laat zien dat je deze perfecte symmetrie en perfect leervermogen tegelijkertijd kunt verkrijgen door simpelweg een aantal runs te middelen.

Wat Dit Betekent voor de Toekomst

De auteurs benadrukken zorgvuldig dat dit een theoretisch bewijs is, geen simulatie van een specifieke dataset. Ze hebben wiskundig aangetoond dat het potentieel bestaat dat deze modellen universele benaderaars zijn. Ze sluiten expliciet de mogelijkheid uit dat je complexe, op maat gemaakte architecturen nodig hebt om dit te bereiken; de standaard PENN-structuur is, wanneer aangevuld met willekeurige kenmerken, voldoende.

Ze verduidelijken ook dat hoewel willekeurige kenmerken de "perfecte symmetrie" van een enkele run doorbreken, ze de "symmetrie in verwachting" (het gemiddelde gedrag) niet doorbreken. Dit suggereert dat het in de praktijk gebruiken van willekeurige kenmerken een robuuste strategie is. Het artikel concludeert dat PENNs met willekeurige kenmerken beschouwd moeten worden als een sterke baseline voor grafiek-leertaken. Ze zijn niet slechts een theoretische curiositeit; ze bieden een concreet, wiskundig onderbouwd blauwdruk voor het bouwen van grafiek-AI's die zowel krachtig als flexibel zijn, in staat om complexe patronen te leren in netwerken variërend van chemische moleculen tot financiële systemen.

Technische Samenvatting: Universaliteit en Approximatiegraden van Graph Neural Networks met Random Features

Probleemstelling

Graph Neural Networks (GNN's), in het bijzonder message-passing architecturen, hebben aanzienlijk empirisch succes geboekt maar kampen met theoretische beperkingen wat betreft hun expressiviteit. Standaard message-passing GNN's worden beperkt door de 1-Weisfeiler–Leman (1-WL) test, wat betekent dat ze bepaalde niet-isomorfe graafstructuren niet kunnen onderscheiden. Hoewel er strategieën bestaan om dit te overwinnen — zoals hogere-orde architecturen of het verrijken van node-features — is er een gebrek aan rigoureuze theoretische resultaten die de universele approximatiecapaciteiten van specifieke, praktische GNN-architecturen vaststellen wanneer deze worden aangevuld met random features. Bovendien leunen bestaande universaliteitsresultaten vaak op restrictieve aannames, zoals het vereisen dat doelinstellingen continu zijn, domeinen compact zijn, of features eindig-dimensionaal zijn, en adresseren ze vaak niet de approximatiegraden (complexiteitsbounds) voor deze modellen.

Methodologie

De auteurs onderzoeken Permutation-Equivariant Neural Networks (PENNs), een klasse van GNN's die veel populaire message-passing architecturen (bijv. GCN, GIN, GraphSAGE, GAT) generaliseert. De kern van de methodologische innovatie is de augmentatie van standaard node-features met random node features.

Architectuurdefinitie: Het artikel definieert PENNs als functies samengesteld uit feedforward neural network (FNN) componenten ( $\rho, \phi, \alpha, \psi$ ) die informatie aggregeren uit buurten en globale graafattributen. Deze structuur omvat het Aggregate-Combine-Readout (ACR) framework.
Random Features: De auteurs introduceren random node features $R$ die "unieke node features" bieden. Dit betekent dat de random features met een hoge waarschijnlijkheid (of bijna zeker) unieke identifiers toekennen aan verschillende nodes, waardoor de symmetrie die standaard GNN's beperkt, effectief wordt doorbroken. Het framework ondersteunt zowel onafhankelijke als identiek verdeelde (i.i.d.) random features en deterministische unieke identifiers (of hun random permutaties).
Approximatie-framework: De studie maakt gebruik van klassieke universele approximatietheorema's voor FNN's (bijv. Leshno et al., 1993), maar past deze aan naar het graafdomein. Het cruciale inzicht is dat als node features uniek zijn, elke permutatie-equivariante functie kan worden gerepresenteerd als een compositie van FNN's die opereren op deze unieke features.
Verwachtingsgestuurde Equivariantie: In het besef dat pathwise permutatie-equivariantie wordt doorbroken door vaste random features, analyseren de auteurs permutatie-equivariantie in verwachting. Ze stellen voor om PENNs te middelen over meerdere resampled random features om de equivariantie-eigenschappen te herstellen terwijl de hoge expressiviteit behouden blijft.

Belangrijkste Bijdragen

1. Universele Approximatietheorema's

Het artikel stelt vast dat PENNs aangevuld met random features universele approximatoren zijn voor meetbare permutatie-invariante en permutatie-equivariante functies op gerichte grafen met een vaste grootte en multidimensionale node/edge-features.

Generaliteit: In tegenstelling tot eerder werk (bijv. Abboud et al., 2020; Puny et al., 2020), vereist dit resultaat niet dat de doelfunctie continu is, noch wordt er aangenomen dat de feature-ruimte compact of eindig is. Het is van toepassing op meetbare functies op onbegrensde domeinen.
Concrete Architectuur: De auteurs specificeren een concrete architectuur (PENNs) waarvoor universaliteit geldt, in plaats van enkel de existentie van een abstracte architectuur te beweren.
Waarschijnlijkheid: De approximatie houdt stand met een willekeurig hoge waarschijnlijkheid, mits de random features unieke node-identifiers induceren.

2. Approximatiegraden en Complexiteitsbounds

Voor $k$ -maal continu differentieerbare functies ( $k \ge 2$ ) gedefinieerd op compacte domeinen, leidt het artikel expliciete bovengrenzen af voor de complexiteit van de PENN-componenten die nodig zijn om een gewenste approximatiefout $\varepsilon$ te bereiken.

Diepte: Het vereiste aantal lagen groeit logaritmisch ten opzichte van $1/\varepsilon$ ( $O(\log(1/\varepsilon))$ ).
Breedte/Gewichten: Het aantal niet-nul gewichten groeit polynomiaal ten opzichte van $1/\varepsilon$ , specifiek als $O(\varepsilon^{-c/(k-1)})$ , waarbij $c$ afhankelijk is van de graafdimensies ( $N, d, d'$ ).
Vloek van de Dimensionaliteit: De bounds weerspiegelen een vorm van de vloek van dimensionaliteit met betrekking tot het graafdomein, maar de ernst hiervan wordt gemitigeerd voor functies met een hogere regulariteit ( $k$ ).

3. Permutatie-Equivariantie in Verwachting

Het artikel adresseert de trade-off tussen expressiviteit en symmetrie. Hoewel een enkele realisatie van een PENN met random features niet pathwise permutatie-equivariante is, bewijzen de auteurs dat de verwachting van de PENN-output (geconditioneerd op de graafinput) permutatie-equivariant is. Verder tonen ze aan dat het middelen over een eindig aantal i.i.d. random feature-samples de universele approximatie-eigenschap behoudt terwijl de bias naar equivariantie wordt verbeterd.

Resultaten

Theorem 9: Stelt vast dat voor elke meetbare permutatie-equivariante functie $f$ en voor elke $\varepsilon, \delta > 0$ , er een PENN met random features bestaat zodanig dat de waarschijnlijkheid dat de approximatiefout $\varepsilon$ overschrijdt, maximaal $\delta$ is.
Theorem 11: Biedt een meettheoretische versie van het universaliteitsresultaat, toepasbaar wanneer de graafdistributie zelf unieke node-features induceert.
Theorem 16: Demonstreert dat de gemiddelde PENN (gebruikmakend van $M$ i.i.d. kopieën van random features) eveneens de universele approximatie-eigenschap voldoet, waarbij de kans op fout begrensd wordt door $\delta$ .
Theorem 18: Levert de kwantitatieve approximatiegraden. Het bewijst dat voor voldoende regelmatige functies, PENNs met specifieke architecturale restricties (diepte en breedte), de doelfunctie uniform kunnen approximeren met een hoge waarschijnlijkheid. De complexiteitsbounds spiegelen die van standaard feedforward neurale netwerken.

Betekenis en Claims

De auteurs claimen dat dit werk substantiële hiaten vult in het theoretische begrip van GNN's:

Brug tussen Theorie en Praktijk: Door te bewijzen dat universaliteit geldt voor een concrete, geheugenefficiënte architectuur (PENNs) in plaats van abstracte modellen, bieden de resultaten een theoretische fundering voor het gebruik van random features in praktische GNN-toepassingen.
Generalisatie van Bestaande Resultaten: De resultaten generaliseren eerdere universaliteitsstellingen door aannames over continuïteit, compactheid en de aard van de doelfuncties (meetbaar vs. continu) te versoepelen.
Praktische Begeleiding: De afgeleide approximatiegraden bieden theoretische begeleiding bij het selecteren van hyperparameters (diepte en breedte) op basis van de gewenste nauwkeurigheid en de regulariteit van de doelfunctie.
Benchmarking: De auteurs suggereren dat PENNs met random features beschouwd moeten worden als sterke baselines voor graaf-leertaken, hetzij als competitieve alternatieven voor state-of-the-art modellen, hetzij als referentiepunt om de capaciteiten van andere architecturen te valideren.

Het artikel concludeert dat hoewel random features mogelijk een verlies van pathwise equivariantie introduceren, de resulterende modellen superieure expressieve kracht bezitten en, wanneer ze worden gemiddeld, de gewenste symmetrie-eigenschappen behouden, wat hen tot een robuust theoretisch en praktisch instrument maakt voor graaf-leren.