CCMamba: Topologically-Informed Selective State-Space Networks on Combinatorial Complexes for Higher-Order Graph Learning

Deze paper introduceert CCMamba, het eerste Mamba-gebaseerde neurale framework voor combinatorische complexen dat hogere-orde relaties efficiënt modelleert door selectieve state-space modellering, waardoor het de schaalbaarheids- en expressiviteitsbeperkingen van bestaande topologische deep learning-methoden overwint.

De kern

Stel je voor dat je een enorme, ingewikkelde stad probeert te begrijpen.

Het oude probleem: De "Vriendenlijst"-benadering
Tot nu toe hebben computersystemen (zoals AI) die steden bestuderen, vaak alleen gekeken naar paar-tje-relaties. Ze zagen alleen wie met wie bevriend was op een kaartje.

• Voorbeeld: "Jan kent Piet." "Piet kent Lisa."
• Het nadeel: Dit werkt goed voor simpele dingen, maar faalt bij complexe groepen. Wat als Jan, Piet en Lisa samen in een band zitten? Of wat als ze samen een project doen? De oude systemen zagen alleen de individuele lijntjes, niet de groep als geheel. Ze zagen de bomen, maar misten het bos.

Daarnaast waren deze oude systemen erg traag. Als je een hele stad wilde analyseren, moesten ze elke mogelijke combinatie van mensen met elkaar vergelijken. Dat is als proberen alle mogelijke gesprekken in een stadion van 100.000 mensen tegelijk te horen. Het kostte enorm veel tijd en energie (rekenkracht).

De nieuwe oplossing: CCMamba
De auteurs van dit paper hebben een nieuwe manier bedacht, genaamd CCMamba. Ze gebruiken een slimme techniek die "Mamba" heet (geïnspireerd op een slang die zich soepel door struiken beweegt, in plaats van als een robot te springen).

Hier is hoe het werkt, vertaald naar alledaagse taal:

1. De Stad is meer dan alleen straten (Combinatorial Complexes)

In plaats van alleen naar straten (lijnen tussen punten) te kijken, kijkt CCMamba naar gebouwen, blokken en wijken.

• 0-dimensionaal: De mensen (punten).
• 1-dimensionaal: De straten (lijnen).
• 2-dimensionaal: De blokken (gebieden die door straten worden omringd).
• Hoger: Zelfs hele wijken of gebouwen.

CCMamba ziet deze hele structuur als één groot, samenhangend systeem. Het begrijpt dat een "blok" (een groep mensen die samenwerken) iets anders is dan twee individuele vrienden.

2. De "Mamba"-slang in plaats van de "Lawaaiige Feestzaal"

De oude methoden werkten als een lawaaiige feestzaal (Attention-mechanisme):

• Iedereen schreeuwt naar iedereen om te horen wat er gebeurt.
• Hoe meer mensen er zijn, hoe luider en chaotischer het wordt. De energie-explosie is enorm (kwadratische complexiteit).

CCMamba werkt als een slimme, gerichte slang:

• In plaats van naar iedereen te schreeuwen, beweegt de slang zich gericht door de stad.
• Het kiest slim uit: "Ik luister nu naar deze groep, en ignoreer die andere."
• Het kan ver weg kijken zonder dat het energie kost. Het kan een boodschap van het ene einde van de stad naar het andere brengen alsof het een korte stap is.
• Het resultaat: Het is veel sneller en kan veel grotere steden (data) aan zonder vast te lopen.

3. De "Rangorde"-slang (Rank-Aware)

Dit is het slimste deel. De slang weet precies welk type "gebied" het is.

• Als de slang een straat (lijn) bekijkt, weet hij: "Ah, dit verbindt twee mensen."
• Als hij een blok (vlak) bekijkt, weet hij: "Ah, dit is een groep van drie of meer."
• Hij behandelt deze verschillende niveaus niet als hetzelfde, maar past zijn strategie aan. Hij weet dat informatie in een groep anders stroomt dan tussen twee individuen.

Waarom is dit geweldig?

Stel je voor dat je een ziekte probeert te bestrijden in een ziekenhuis.

• Oude methode: Je kijkt naar wie met wie in dezelfde kamer zat. Je mist dat ze allemaal in dezelfde operatiezaal zaten en dezelfde lucht deelden.
• CCMamba: Je ziet de hele operatiezaal als één entiteit. Je ziet dat de lucht, de apparatuur en de mensen samenwerken. Je kunt de ziekte veel beter voorspellen en de behandeling veel sneller uitvoeren.

Kortom:
CCMamba is een nieuwe, super-snelle en slimme manier voor computers om complexe groepen en netwerken te begrijpen. Het doet dit niet door iedereen met iedereen te laten praten (wat te traag is), maar door slim, gericht en in één beweging door de hele structuur te "glijden". Hierdoor kunnen we nu veel grotere en complexere problemen oplossen, van medicijnen vinden tot verkeersstromen in megasteden, zonder dat de computer het opgeeft.

Technische samenvatting

Probleemstelling

Bestaande methoden voor topologisch diep leren (Topological Deep Learning - TDL) op complexe structuren zoals hypergrafen, simpliciale complexen en cellulaire complexen, kampen met twee fundamentele beperkingen:

1. Schaalbaarheid: De meeste huidige modellen vertrouwen op mechanismen voor berichtoverdracht (message passing) gebaseerd op attention (zoals Transformers) of lokale aggregatie. Deze methoden hebben een kwadratische complexiteit ($O(n^2)$) wat ze onpraktisch maakt voor grote datasets.
2. Lokale beperkingen en expressiviteit: Traditionele methoden zijn vaak beperkt tot lokale buren en kunnen lange-afstandsafhankelijkheden (long-range dependencies) of gerichte stromingen tussen verschillende rangen (bijv. van knopen naar randen, of van randen naar vlakken) niet effectief modelleren. Bestaande topologische netwerken behouden vaak niet de "rang-bewuste" (rank-aware) informatie die essentieel is voor combinatorische complexen.

Methodologie: CCMamba

De auteurs stellen CCMamba (Combinatorial Complex Mamba) voor, het eerste neurale raamwerk dat gebaseerd is op de Mamba-architectuur (Selectieve State-Space Modellen - SSM) en specifiek is ontworpen voor combinatorische complexen (CC).

Kerncomponenten:

• Combinatorische Complexen (CC): Het model gebruikt CC als een verenigd raamwerk dat grafen, hypergrafen, simpliciale complexen en cellulaire complexen omvat. Entiteiten worden georganiseerd in gerangschikte cellen (0-cellen/knopen, 1-cellen/randen, 2-cellen/vlakken, etc.) verbonden via rand- en co-rand-operatoren.
• Linearisatie naar Sequenties: In plaats van directe attention-mechanismen, lineariseert CCMamba de hogere-orde incidentierelaties van het CC naar gestructureerde sequenties. Hierdoor kan het model de topologische buren behandelen als sequenties die geschikt zijn voor SSM-verwerking.
• Bidirectionele Selectieve State-Space Modulen:
  • Het model gebruikt Bidirectional Mamba (BiMamba) blokken om informatie te verwerken in beide richtingen (voorwaarts en achterwaarts). Dit lost het probleem op dat topologische buren geen canonieke causale volgorde hebben.
  • De SSM's zijn selectief: ze passen de staatsovergang dynamisch aan op basis van de invoer, wat zorgt voor adaptieve filtering van bureninformatie.
  • Dit gebeurt op twee niveaus:
    1. Intra-buurschapsfiltering: Verwerking van informatie binnen een specifieke rang (bijv. knopen naar knopen via gedeelde randen) met behoud van lineaire complexiteit.
    2. Inter-buurschapsaggregatie: Fusie van informatie tussen verschillende rangen (bijv. van knopen naar randen en van randen naar vlakken) via incidentie-operatoren, waardoor de hiërarchische geometrie behouden blijft.
• Architectuur: Het model bestaat uit lagen met residual connections, layernormalisatie en Feed-Forward Networks (FFN), vergelijkbaar met Transformers, maar met de lineaire efficiëntie van SSM.

Belangrijkste Bijdragen

1. Eerste Mamba-architectuur voor Combinatorische Complexen: CCMamba is het eerste unified framework dat Mamba toepast op hogere-orde grafen, waardoor het in staat is om grafen, hypergrafen, simpliciale en cellulaire complexen in één model te verwerken.
2. Lineaire Schaalbaarheid: Door de kwadratische complexiteit van self-attention te vervangen door lineaire SSM-verwerking, overwint CCMamba de schaalbaarheidsproblemen van bestaande topologische netwerken.
3. Theoretische Expressiviteit: De auteurs bewijzen theoretisch dat de uitdrukkingskracht van CCMamba wordt begrensd door de 1-dimensionale Combinatorial Complex Weisfeiler-Lehman (1-CCWL) test. Dit betekent dat het model minstens zo expressief is als deze geavanceerde isomorfietest voor topologische structuren.
4. Robuustheid tegen Over-smoothing: In tegenstelling tot traditionele GNN's die last hebben van over-smoothing (waarbij signalen vervagen in diepe netwerken), behoudt CCMamba zijn discriminatieve vermogen zelfs bij zeer grote dieptes (tot 64 lagen) dankzij de input-afhankelijke gating van de SSM.

Resultaten

Uitgebreide experimenten zijn uitgevoerd op diverse benchmarks (TUDatasets, citation networks, en heterofiele grafen) voor zowel graf-classificatie als knoop-classificatie.

• Prestaties: CCMamba (vooral de variant die alle rangen gebruikt, "rank-cell") presteert consistent beter dan bestaande state-of-the-art methoden, waaronder GCN, GAT, HyperGCN, Simpliciale Neural Networks (SCNN) en Cellulaire Netwerken (CCNN).
  • Bijvoorbeeld: Op de MUTAG-dataset verbeterde het de prestaties met +5,36% ten opzichte van een graf-variant en +2,64% ten opzichte van de beste cellulaire baseline (CWN).
  • Op knoop-classificatie (bijv. Cora, PubMed) overtrof het attention-based modellen zoals GAT en CCCN aanzienlijk.
• Vergelijking Attention vs. SSM: CCMamba toonde aan dat selectieve state-space modellen fundamenteel beter geschikt zijn voor hogere-orde representaties dan standaard attention-mechanismen, vooral op complexe structuren zoals simpliciale complexen.
• Efficiëntie: CCMamba reduceert het GPU-geheugengebruik aanzienlijk (tot 85,8% minder geheugen op grote datasets zoals PROTEINS) en versnelt de trainingstijd in vergelijking met multi-head attention-modellen.
• Diepte-robustheid: Terwijl traditionele modellen (zoals GCN en HyperGCN) instorten bij diepere netwerken (bijv. van 84% naar 12% op Cora bij 8 lagen), behoudt CCMamba zijn nauwkeurigheid tot 32 lagen en blijft stabiel tot 64 lagen.

Significantie

Deze paper markeert een belangrijke doorbraak in het veld van topologisch diep leren. Het bewijst dat Selectieve State-Space Modellen (SSM) een krachtig alternatief zijn voor Transformers in de context van complexe, niet-pairwise data.

• Unificatie: Het biedt een verenigd raamwerk dat de kloof tussen verschillende topologische structuren (graf, hypergraaf, simpliciaal, cellulair) overbrugt zonder de noodzaak van specifieke architecturen per structuur.
• Schaalbaarheid: Het maakt het mogelijk om zeer grote en complexe topologische netwerken te trainen die voorheen onbereikbaar waren door de kwadratische complexiteit van attention.
• Toekomstperspectief: CCMamba opent de deur voor het modelleren van lange-afstandsafhankelijkheden in complexe systemen (zoals biologische netwerken, sociale interacties en fysieke systemen) met lineaire complexiteit, terwijl het de fundamentele topologische eigenschappen van de data behoudt.

Kortom, CCMamba combineert de theoretische sterkte van topologische inductie met de praktische efficiëntie van moderne state-space modellen, wat leidt tot een nieuw standaard voor hogere-orde grafenleren.