🤖 machine learning

The Polynomial Counting Capabilities of Message Passing Neural Networks

Dit artikel onderzoekt het polynoomtelpotentieel van Message Passing Neural Networks (MPNNs) en toont aan dat deze met behulp van gemiddelde-aggregatie globale en specifieke lokale polynoombeperkingen in met labels voorziene knoopgrafen kunnen verifiëren, met name onder voorwaarden zoals regelmatige grafen, niet-geneste modaliteiten of boomachtige structuren.

Oorspronkelijke auteurs: Marco Sälzer, Pascal Bergsträßer, Anthony W. Lin

Gepubliceerd 2026-05-12

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Marco Sälzer, Pascal Bergsträßer, Anthony W. Lin

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

Stel je een Message Passing Neural Network (MPNN) voor als een team van detectives die werken in een stad (het graf). Elke detective (een knooppunt) staat op een kruispunt en praat met hun directe buren om aanwijzingen te verzamelen. Ze hebben ook een speciale radio waarmee ze een samenvatting kunnen horen van wat er in de hele stad gebeurt.

Het doel van dit artikel is om uit te zoeken hoe goed deze detectives zijn in tellen. Kunnen ze meer dan alleen tellen "hoeveel rode huizen er in de buurt zijn?" Kunnen ze complexe wiskundige raadsels oplossen, zoals: "Is het aantal rode huizen gekwadrateerd groter dan het aantal blauwe huizen gekubiseerd?"

Hier is een uiteenzetting van wat het artikel ontdekte, met eenvoudige analogieën:

1. Het Probleem: Lineair versus Polynoom Tellen

Het merendeel van het eerdere onderzoek toonde aan dat deze detectives uitstekend zijn in lineair tellen.

Voorbeeld: "Zijn er meer rode huizen dan blauwe huizen?" (Dit is als $Red > Blue$).
De Beperking: Ze hadden moeite met polynoom tellen, waarbij getallen met zichzelf worden vermenigvuldigd (gekwadrateerd, gekubiseerd, enz.).
Het Doel van het Artikel: De auteurs wilden onderzoeken of de detectives deze moeilijkere, "polynoom"-wiskundige problemen aankunnen.

2. Het Geheime Wapen: De "Gemiddelde" Aggregator

De detectives hebben verschillende manieren om naar hun buren te luisteren:

Som: Ze tellen alle getallen die ze horen bij elkaar op.
Max: Ze luisteren alleen naar het luidste stemgeluid.
Gemiddelde (Mean): Ze berekenen het gemiddelde van alle stemmen.

De auteurs ontdekten dat het Gemiddelde (average) de geheime saus is voor polynoom tellen. Door te middelen, kunnen de detectives op natuurlijke wijze de deling en vermenigvuldiging aan die nodig zijn voor complexe wiskunde. Om dit echter perfect te laten werken, moet de stad echter aan specifieke regels voldoen.

3. De Drie Regels voor Succes

Het artikel vond dat de detectives, om deze moeilijke wiskundige raadsels op te lossen, doorgaans een van drie "speciale voorwaarden" nodig hebben:

Voorwaarde A: De "Gemerkte" Detective (De VIP)
Stel je voor dat één detective een fel, uniek hoedje draagt dat niemand anders heeft. Dit is een "gemarkeerd knooppunt".
- Waarom dit helpt: Het geeft het team een vast referentiepunt. Zonder dit raken de detectives in de war over welke getallen bij wie horen wanneer ze complexe delingen uitvoeren.
- Wereldse analogie: Het is als een specifiek "Start Hier"-bord op een kaart hebben, zodat je precies weet waar je bent ten opzichte van de rest van de stad.
Voorwaarde B: De "Perfect Regelmatige" Stad
Stel je een stad voor waar elk kruispunt exact hetzelfde aantal wegen heeft dat eruit loopt.
- Waarom dit helpt: Als elke detective hetzelfde aantal buren heeft, blijft de wiskunde consistent. Als één detective 3 buren heeft en een ander 10, wordt het "gemiddelde" rommelig en moeilijk te vergelijken.
- Wereldse analogie: Een perfect symmetrisch rooster, zoals een schaakbord, waar elk vakje precies 4 buren heeft.
Voorwaarde C: De "Boom-achtige" Stad
Stel je een stad voor zonder lussen of cirkels—zoals een stamboom of een vertakkende rivier.
- Waarom dit helpt: Deze structuur voorkomt dat informatie vastloopt in cirkels, waardoor de detectives dingen kunnen tellen op verschillende "afstanden" van het centrum zonder in de war te raken.

4. De Grote Ontdekkingen

Scenario 1: Kijken naar de Hele Stad (Globaal Tellen)
Als de detectives alleen hoeven te tellen in de hele stad (zonder rekening te houden met specifieke buurten), kunnen ze polynoom wiskundige problemen oplossen als er een Gemerkte Detective is (Voorwaarde A). Ze hoeven niet dat de stad perfect regelmatig is.

Scenario 2: Kijken naar Buurten (Lokaal Tellen)
Als de detectives dingen moeten tellen in specifieke buurten (bijvoorbeeld: "Hoeveel rode buren heeft deze specifieke detective?"), wordt het moeilijker.

Strenge Modus: Als ze alleen de "Gemiddelde" (average) gebruiken, moet de stad Perfect Regelmatig zijn (Voorwaarde B) EN moet de detective Gemerkt zijn (Voorwaarde A) EN een Zelflus hebben (staan op hun eigen straathoek).
Ontspannen Modus: Als de detectives "Som" of "Max" naast "Gemiddelde" mogen gebruiken, kunnen ze deze problemen oplossen zelfs als de stad niet perfect regelmatig is. Ze hebben alleen de Gemerkte Detective en de Zelflus nodig.

Scenario 3: Diepe Nesting (De Russische Poppen)
Soms is de wiskunde genest: "Tel de buren van de buren van de buren."

Het artikel vond dat als de stad Boom-achtig is (Voorwaarde C) en de detectives de Gemerkte status hebben, ze deze diepe, geneste polynoomproblemen kunnen oplossen.
Als ze "Som" of "Max" hulpmiddelen mogen gebruiken, kunnen ze zelfs complexere boomstructuren aan.

5. De Conclusie

Het artikel bewijst dat MPNN's veel krachtiger zijn dan we dachten, maar dat ze een beetje hulp nodig hebben.

Ze kunnen complexe polynoomwiskunde doen (zoals $x^2 + y^3$ ) als we hen een referentiepunt geven (een gemerkt knooppunt).
Als we willen dat ze naar specifieke buurten kijken, moet de stad symmetrisch (regelmatig) of boom-vormig zijn, tenzij we hen extra hulpmiddelen geven (Som/Max).

Kortom: Deze neurale netwerken zijn als briljante wiskundigen, maar ze hebben een duidelijk startpunt en een consistente omgeving nodig om hun meest complexe telraadsels op te lossen. Zonder die voorwaarden raken ze verdwaald in de wiskunde.

Technische Samenvatting: De Vermogens van Message Passing Neural Networks voor Polynoomtelling

Probleemstelling
Recent onderzoek heeft vastgesteld dat Message Passing Neural Networks (MPNNs) logische eigenschappen kunnen uitdrukken die tellen tot een drempelwaarde of voldoen aan lineaire rekenkundige beperkingen, vaak gekarakteriseerd met behulp van fragmenten van eerste-orde logica met telling (FOC2) of uitbreidingen met lineaire geheeltallige rekenkunde. Er blijft echter een kloof bestaan in het begrijpen van de expressieve kracht van MPNNs met betrekking tot polynoomtellingbeperkingen (niet-lineaire rekenkunde), die relevant zijn voor geavanceerde grafclassificatietechnieken zoals polynoomkernels. Dit artikel onderzoekt de voorwaarden waaronder MPNNs, specifiek die gebruikmaken van gemiddelde aggregatie, eigenschappen kunnen herkennen die gedefinieerd zijn door Peano Modale Logica (PML). PML breidt Graded Modale Logica uit door polynoombeperkingen toe te staan (bijvoorbeeld $x_1^2 \cdot x_2 \leq x_3$ ) in plaats van alleen lineaire beperkingen.

Methodologie
De auteurs maken gebruik van een formeel kader om de expressieve capaciteiten van MPNNs te analyseren door ze te vergelijken met fragmenten van PML.

Modeldefinitie: De studie richt zich op MPNNs ( $M_{mean}$ ) die gemiddelde aggregatie gebruiken voor zowel lokale (buur) als globale (gehele graf) informatie. De auteurs overwegen ook varianten ( $M_{mean, x}$ ) die extra som- of max-aggregatie toestaan.
Logicadefinitie: Zij definiëren PML, waarbij modale formules $\langle \pi_1, \dots, \pi_m \rangle \psi(x_1, \dots, x_m)(\phi_1, \dots, \phi_m)$ knopen tellen die aan subformules $\phi_i$ voldoen binnen specifieke buurten (gedefinieerd door modaliteiten $\pi \in \{id, E_{in}, E_{out}, \top\}$ ) en controleren of de tellingen voldoen aan een Peano-rekenkundige beperking $\psi$ .
Herkenkader: Een MPNN wordt geacht een formule $\phi$ te "herkennen" over een klasse van gepunte grafen als de uitvoerstatus van het netwerk voor de focusknop $v$ niet-nul is (specifiek $\geq c(|V|)$ ) als de graf aan $\phi$ voldoet, en nul anders. De zekerheid $c(|V|)$ mag afhankelijk zijn van de grafgrootte.
Constructiestrategie: De bewijzen behelzen het stap-voor-stap construeren van specifieke MPNN-architecturen. Deze constructies maken gebruik van "gadgets" (combinaties van ReLU-neuronen) om rekenkundige bewerkingen (vermenigvuldiging, optelling, vergelijking) uit te voeren op geaggregeerde waarden. Een belangrijke technische uitdaging die wordt aangepakt, is de verwerking van noemers die worden geïntroduceerd door gemiddelde aggregatie (bijvoorbeeld $1/|V|$ of $1/|neigh(v)|$) bij het evalueren van polynoomtermen van wisselende graden.

Belangrijkste Bijdragen en Resultaten
Het artikel identificeert specifieke structurele aannames over invoergrafen die het mogelijk maken voor mean-MPNNs om polynoomtellingseigenschappen te vangen. De resultaten worden gecategoriseerd op basis van de diepte van modaliteiten (on diep versus genest) en het type gebruikte modaliteiten (globaal versus lokaal).

Globale Modaliteiten (On diepe Diepte):
- Homogene Beperkingen: Voor formules die uitsluitend de globale modaliteit ( $\top$ ) en homogene Peano-termen gebruiken (geen constante termen, dezelfde graad voor alle monomen), kunnen mean-MPNNs de logica herkennen zonder aanvullende graf-aannames (Lemma 1).
- Algemene Polynoombeperkingen: Om willekeurige globale polynoombeperkingen te herkennen (inclusief niet-homogene termen en constanten), moeten de invoergrafen een gemarkeerde knop bevatten (een knop met een unieke kleur). Onder deze aanname kunnen mean-MPNNs noemers aligneren naar $|V|^k$ en de logica herkennen (Stelling 1).
Lokale Modaliteiten (On diepe Diepte):
- Regulariteitsvereiste: Voor formules die uitsluitend lokale modaliteiten ( $E_{in}, E_{out}$ ) gebruiken, vereisen mean-MPNNs dat de invoergrafen regulier zijn (alle knopen hebben dezelfde in-/uitgraad) en dat de focusknop sterk gemarkeerd is (gemarkeerd en met een zelflus). Dit stelt het netwerk in staat om lokale buurgroottes te normaliseren (Stelling 2).
- Verzachten van Regulariteit: Als de MPNN mag gebruikmaken van som- of max-aggregatie in aanvulling op gemiddelde, kan de regulariteitsaanname worden losgelaten. Het netwerk kan dan lokale polynoombeperkingen herkennen op elke graf waar de focus sterk gemarkeerd is (Stelling 3).
Gemengde Modaliteiten (On diepe Diepte):
- Bij het combineren van globale en lokale modaliteiten kunnen de resultaten uit de vorige secties worden gecombineerd. Mean-MPNNs herkennen deze formules op reguliere, sterk gemarkeerde grafen (Stelling 4).
- Met de toevoeging van som/max-aggregatie is de regulariteitsaanname opnieuw verwijderbaar (Stelling 5).
Geneste Modaliteiten (Willekeurige Diepte):
- Globale Nesting: Het nesten van globale modaliteiten verhoogt de expressieve kracht niet boven diepte 1; ze kunnen worden afgevlakt (Propositie 1).
- Lokale Nesting: Voor formules met geneste lokale modaliteiten introduceert het artikel een klasse van grafen genaamd $(T \circlearrowleft_\phi)^p_\bullet$ . Dit zijn "boomachtige" structuren waarbij de focus gemarkeerd is en de grafstructuur unieke sporen garandeert voor knopen op specifieke afstanden (waardoor ambiguïteit in buurttellingen wordt vermeden).
- Resultaten: Mean-MPNNs kunnen geneste lokale PML herkennen op deze boomachtige, reguliere, sterk gemarkeerde grafen (Stelling 6). Als som/max-aggregatie wordt toegestaan, wordt de regulariteitsbeperking verwijderd, waardoor herkenning mogelijk is op algemene boomachtige, sterk gemarkeerde grafen (Stelling 7).

Betekenis en Claims
Het artikel claimt de minimale voorwaarden te identificeren die nodig zijn voor MPNNs om zich te generaliseren van lineaire rekenkunde naar polynoomtelling.

Theoretische Generalisatie: De resultaten suggereren dat MPNNs met gemiddelde aggregatie technieken kunnen generaliseren die worden gebruikt in grafclassificatie die vertrouwen op polynoomkernels (bijvoorbeeld SVM's met polynoomkernels), mits de invoergegevens voldoen aan specifieke structurele eigenschappen (gemarkeerde knopen, regulariteit of boomachtigheid).
Rol van Aggregatie: De studie benadrukt dat hoewel gemiddelde aggregatie voldoende is voor polynoomtelling onder strikte structurele aannames, de opname van som- of max-aggregatie deze vereisten aanzienlijk verzacht (specifiek het verwijderen van de noodzaak voor grafregulariteit).
Beperkingen: De auteurs stellen expliciet dat zonder deze structurele aannames (gemarkeerde knopen, regulariteit of boomachtige structuren) mean-MPNNs niet alle polynoombeperkingen kunnen uitdrukken. Bijvoorbeeld, Lemma 2 toont aan dat mean-MPNNs niet kunnen onderscheiden tussen bepaalde niet-reguliere grafen die voldoen aan een eenvoudige polynoombeperking.

Het artikel concludeert dat hoewel MPNNs vermogens voor polynoomtelling bezitten, het realiseren daarvan ofwel specifieke architecturale keuzes vereist (toevoegen van som/max) of specifieke data-preprocessing/structurele aannames (markeer knopen, zorgen voor regulariteit of boomachtige structuren). Er wordt voorgesteld om in toekomstig werk willekeurige Boolese combinaties van modaliteiten te onderzoeken en het vergelijken van tellingen op verschillende afstanden, die momenteel niet worden gedekt door het gebruikte PML-kader.