🤖 machine learning

The Logical Expressiveness of Topological Neural Networks

Deze paper introduceert de $k$ -CCWL-test en topologische tellogica (TC $_k$ ) om de logische uitdrukkingskracht van topologische neurale netwerken (TNNs) te karakteriseren, waarbij wordt bewezen dat deze equivalent zijn aan een topologisch $(k+2)$ -steentjespel.

Oorspronkelijke auteurs: Amirreza Akbari, Amauri H. Souza, Vikas Garg

Gepubliceerd 2026-04-22

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Amirreza Akbari, Amauri H. Souza, Vikas Garg

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 voor dat je een groep vrienden hebt die je wilt leren kennen. Je wilt weten wie wie is, wie met wie praat, en wie in welke groep zit.

Graph Neural Networks (GNNs) zijn als slimme detectives die dit proberen te doen door alleen naar de directe buren van iemand te kijken. Als twee mensen precies dezelfde directe buren hebben, denken deze detectives dat ze identiek zijn. Het probleem? Soms zijn twee groepen mensen totaal verschillend, maar hebben ze toevallig dezelfde directe buren. De detectives worden dan in de war gebracht en kunnen het verschil niet zien. Ze zijn te "kortzichtig".

Topological Neural Networks (TNNs) zijn de nieuwe, super-slimme detectives. Ze kijken niet alleen naar directe buren, maar ook naar hoe mensen met elkaar verbonden zijn via tussenpersonen, of hoe ze samen een groep vormen (zoals een driehoek van vrienden). Ze hebben een veel breder zicht.

Maar de onderzoekers in dit artikel stelden zich een belangrijke vraag: Hoe slim zijn deze nieuwe detectives eigenlijk precies? Kunnen ze alles zien, of zijn er nog steeds dingen die ze missen? En hoe kunnen we dat meten?

Om dit uit te leggen, gebruiken de auteurs drie verschillende manieren om hun "detective-vaardigheden" te testen. Ze noemen dit een "drie-eenheid":

1. De Kleurverf-Test (Het Algorithmische Deel)

Stel je voor dat je een heel complex labyrint hebt met veel verschillende kamers en gangen.

De oude detectives (GNNs) geven elke kamer een kleur op basis van de kleur van de kamer direct ernaast.
De nieuwe detectives (TNNs) geven een kamer een kleur op basis van een heel complex patroon: de kleur van de kamer eronder, de kamer erboven, en zelfs de kleur van de kamers die met elkaar verbonden zijn via een derde kamer.

De auteurs hebben een nieuwe test bedacht, de k-CCWL-test. Dit is als een verfmachine die steeds opnieuw de kleuren van de kamers aanpast. Als na een paar rondes twee labyrinten precies dezelfde kleurpatronen hebben, dan zijn ze voor de detective ononderscheidbaar. Als ze verschillend zijn, heeft de detective het verschil gevonden. Ze bewijzen dat hoe "dieper" je kijkt (hoe groter het getal k is), hoe scherper de verfmachine wordt en hoe meer verschillen hij kan zien.

2. De Taal van de Logica (Het Logische Deel)

Nu kijken we naar de taal die de detective gebruikt om te denken.

Normale detectives kunnen zeggen: "Er is iemand die een rode hoed draagt" (dat is makkelijk).
Maar wat als je wilt zeggen: "Er zijn precies 5 paren mensen die elkaar aankijken en samen een driehoek vormen"? Dat is heel lastig voor de oude taal.

De auteurs hebben een nieuwe taal bedacht, de Topological Counting Logic (TCk). Het belangrijkste nieuwe woord in deze taal is een "paar-teller". In plaats van alleen te tellen hoeveel mensen er zijn, kan deze taal tellen: "Hoeveel paren mensen voldoen aan deze specifieke, ingewikkelde regel?"
Dit is precies wat de nieuwe TNN-detectives nodig hebben om hun complexe wereld te begrijpen. Ze bewijzen dat deze nieuwe taal precies zo sterk is als de verfmachine uit punt 1.

3. Het Speelgoed-Spel (Het Spel-theoretische Deel)

Tot slot spelen ze een spelletje tussen twee spelers: De Verstoorder (Spoiler) en De Verdubbelaar (Duplicator).

De Verstoorder probeert een verschil te vinden tussen twee labyrinten. Hij pakt twee paren kamers uit het ene labyrint en zegt: "Kijk, deze paren zijn anders dan die in het andere labyrint!"
De Verdubbelaar moet dan in het andere labyrint een paar kamers vinden die precies hetzelfde gedrag vertonen.

Als de Verdubbelaar een strategie heeft om dit spel altijd te winnen (dus nooit een verschil te laten zien), dan zijn de twee labyrinten voor de detective ononderscheidbaar. De auteurs tonen aan dat dit spel precies even moeilijk is als de verfmachine en de nieuwe taal.

Het Grote Geheim (De Conclusie)

Het mooiste resultaat van dit papier is dat deze drie dingen exact hetzelfde zijn.
Het is alsof je drie verschillende kaarten hebt van dezelfde berg:

Een kaart van de wegen (het algoritme).
Een beschrijving in woorden (de logica).
Een spelregelsboek (het spel).

De auteurs bewijzen dat als je één van deze drie kent, je de andere twee ook kent. Ze hebben een formule gevonden:
De nieuwe verfmachine = De nieuwe taal = Het nieuwe spel.

En het allerbelangrijkste: ze laten zien dat als je de "diepte" van je kijk (het getal k) verhoogt, je echt slimmer wordt. Je kunt dan steeds ingewikkelder structuren onderscheiden die de oude detectives nooit zouden zien.

Kortom:
Deze paper geeft ons de eerste echte "meetlat" om te zeggen hoe slim Topological Neural Networks precies zijn. Het laat zien dat ze niet alleen "een beetje" slimmer zijn dan de oude modellen, maar dat ze een heel nieuw niveau van logica en inzicht hebben bereikt, net als een detective die opeens niet alleen naar buren kijkt, maar naar het hele sociale netwerk en de verborgen patronen daarin.

Probleemstelling

Graph Neural Networks (GNNs) zijn de standaard voor het leren van structuren op grafen, maar ze hebben een fundamentele beperking in hun expressiviteit. Hun vermogen om niet-isomorfe grafen te onderscheiden, wordt begrensd door de 1-Weisfeiler-Leman (1-WL) test (ook wel kleurverfijning genoemd). Dit betekent dat GNNs vaak falen bij het herkennen van fundamentele structurele eigenschappen, zoals cycli of samenhangende componenten.

Om dit te overwinnen, zijn Topologische Neural Networks (TNNs) ontwikkeld. Deze netwerken opereren op Combinatorial Complexes (CCs) (zoals simpliciale complexen en hypergrafen) en gebruiken hogere-orde relaties (beyond pairwise edges) via message-passing. Hoewel TNNs empirisch krachtiger lijken, ontbreekt er een theoretisch kader om hun expressieve kracht precies te karakteriseren. De centrale vraag is: Wat is de logische expressiviteit van TNNs en welke binaire classifiers kunnen ze precies representeren?

Methodologie

De auteurs beantwoorden deze vraag door een drietalig analytisch kader te ontwikkelen dat drie perspectieven met elkaar verbindt: algoritmen, logica en speltheorie. Dit is een uitbreiding van het klassieke "k-WL / tellende logica / steenlegspel"-triad dat bekend is voor grafen, maar nu toegepast op Attributed Combinatorial Complexes (ACCs).

Algoritmisch Perspectief (k-CCWL):
De auteurs introduceren de k-dimensionale Combinatorial Complex Weisfeiler-Leman test (k-CCWL). Dit is een verfijning van het klassieke WL-algoritme dat werkt op $k$ -tupels van cellen in een combinatorisch complex.
- Het algoritme houdt rekening met vier soorten topologische buren: boundary (grens), coboundary, upper adjacency en lower adjacency.
- Een cruciale innovatie is de double shift sequence: bij het updaten van een label wordt gekeken naar substituties van twee cellen ( $\alpha, \beta$ ) tegelijkertijd. Dit vereist een logische uitdrukking met $k+2$ variabelen.
- Om globale isomorfisme te testen, wordt een "broadcast-anchor" gadget toegevoegd (een nieuwe 0-cel verbonden met alle bestaande 0-cellen) om lokale verschillen te propageren naar het gehele complex.
Logisch Perspectief (TCk):
Er wordt een nieuwe logica gedefinieerd: Topological Counting Logic (TCk).
- Dit is een extensie van de standaard tellende logica ( $C_k$ ) met een paar-tellende kwantificator: $\exists^N(x_i, x_j) \phi(x_i, x_j)$ .
- Deze kwantificator telt het aantal paren cellen $(x_i, x_j)$ die een bepaalde eigenschap $\phi$ voldoen. Dit is essentieel omdat TNNs vaak informatie aggregeren over paren cellen die via een gemeenschappelijke buur verbonden zijn (bijv. twee randen die een hoekpunt delen), in plaats van alleen over individuele buren.
Speltheoretisch Perspectief (Topological Pebble Game):
De auteurs definiëren een topologische $k$ -pebble game (een variant van het klassieke Ehrenfeucht-Fraïssé spel).
- Speler I (de "Spoiler") kiest een set paren cellen in het ene complex.
- Speler II (de "Duplicator") moet een set van gelijke grootte in het andere complex kiezen.
- Het spel is ontworpen om de semantiek van de paar-tellende kwantificator na te bootsen.

Belangrijkste Bijdragen en Resultaten

De kernbijdrage van het paper is het bewijs van een strikte equivalentie tussen deze drie benaderingen voor hogere-orde TNNs.

De Hoofdstelling (Corollary 5.3):
Voor twee Attributed Combinatorial Complexes $A$ en $B$ en een parameter $k$ , zijn de volgende drie stellingen equivalent:

Algoritmisch: De $k$ -CCWL verfijning onderscheidt de $k$ -tupels van $A$ en $B$ niet (ze hebben dezelfde stabiele kleuren).
Logisch: $A$ en $B$ zijn niet te onderscheiden door formules in de logica TCk+2.
Speltheoretisch: Speler II heeft een winnende strategie in het topologische $(k+2)$ -pebble spel op $A$ en $B$ .

Formeel uitgedrukt:
$k\text{-CCWL} \equiv TC_{k+2} \equiv \text{Topological } (k+2)\text{-pebble game}$

Specifieke bevindingen:

Expressiviteitshiërarchie: De expressiviteit van $k$ -CCWL (en dus van TNNs) neemt strikt toe met $k$ . Er bestaan paren van niet-isomorfe ACCs die door $k$ -CCWL worden onderscheiden, maar niet door $(k-1)$ -CCWL.
Relatie met GNNs: Voor $k=1$ (op 1-dimensionale ACCs, oftewel grafen) reduceert $k$ -CCWL tot de standaard $k$ -WL test. De paper toont aan dat $k$ -CCWL op grafen exact dezelfde onderscheidende kracht heeft als $k$ -WL.
Pairwise Aggregatie: De noodzaak van de $(k+2)$ -variabele logica (in plaats van $k+1$ zoals bij grafen) komt voort uit de manier waarop TNNs aggregatie uitvoeren: ze kijken naar paren van cellen die via een derde cel verbonden zijn. Dit vereist twee extra "spare" variabelen (pebbles) in het spel om deze relaties te modelleren.
Uniformiteit: De resultaten gelden specifiek voor uniforme ACCs, waar elke cel via een pad van buren bereikbaar is van een 0-cel. Voor niet-uniforme complexen kan de "identical-vs-disjoint" eigenschap falen.

Significantie

Dit paper legt de eerste theoretische basis voor het begrijpen van de expressieve kracht van Topological Neural Networks.

Theoretisch Fundament: Het biedt een precieze karakterisering van welke structurele patronen TNNs kunnen leren. Het bevestigt dat hogere-orde TNNs strikt meer vermogen hebben dan traditionele GNNs, en kwantificeert dit vermogen via de parameter $k$ .
Ontwerprichtlijnen: Voor onderzoekers die TNN-architecturen ontwerpen, geeft het inzicht dat het verhogen van de "orde" van het message-passing (het werken met $k$ -tupels) direct correleert met het vermogen om complexere logische formules (met paar-tellende kwantificatoren) te evalueren.
Verbinding van Domeinen: Het paper verbindt succesvol gebieden van topologische data-analyse, logische expressiviteit en speltheorie, wat een nieuwe weg opent voor het analyseren van andere vormen van hogere-orde deep learning.

Samenvattend: De auteurs hebben bewezen dat de expressiviteit van TNNs exact wordt bepaald door de $TC_{k+2}$ logica en het bijbehorende steenlegspel, wat een robuust theoretisch kader biedt voor de ontwikkeling van krachtigere modellen voor relationeel leren op complexe datastructuren.