Technische Samenvatting: GraphScan voor Vision State Space Models

1. Probleemstelling

Vision State Space Models (SSM's), met name die gebaseerd op de Mamba-architectuur, bieden efficiënte modellering op lange afstand met lineaire complexiteit. Hun prestaties zijn echter kritiek afhankelijk van hoe tweedimensionale visuele feature maps worden gesequenced tot eendimensionale token-sequenties voor verwerking.

Bestaande scan-operatoren in Vision SSM's vallen over het algemeen in twee categorieën:

1. Vaste Geometrische Traverseringen: Vooraf gedefinieerde paden (bijv. raster, bidirectioneel, fractaal) die het 2D-rooster sequentiëren tot een 1D-sequentie. Deze blootstellen het model aan vaste ordeningen die mogelijk niet overeenkomen met semantische inhoud.
2. Dynamische Coördinatie-gebaseerde Scans: Methoden die offsets of bemonsteringslocaties voorspellen en tokens herschikken via interpolatie (bijv. bilineaire interpolatie). Hoewel adaptief, passen deze voornamelijk aan waar er wordt bemonsterd op basis van geometrie, in plaats van expliciet te modelleren welke lokale patches informatie moeten uitwisselen op basis van semantische relevantie voordat globale mixing plaatsvindt.

De auteurs identificeren een gat: huidige mechanismen passen paden of bemonsteringscoördinaten aan, maar modelleren geen lokale semantische buurten expliciet om tokens te preconditioneren voordat ze de selectieve state-space mixer binnenkomen. De centrale vraag is of op grafen gebaseerde routing Vision SSM's kan helpen om "beter te zien" door semantische verbindingen tot stand te brengen voordat globale propagatie plaatsvindt.

2. Methodologie: GraphScan

Het artikel introduceert GraphScan, een door grafen geïnduceerde dynamische scan-operator die is ontworpen om de selectieve SSM vooraf te gaan. In tegenstelling tot methoden die de SSM vervangen door een Graph Neural Network (GNN), fungeert GraphScan als een lichtgewicht, input-adaptieve preconditioner die tokens verrijkt met lokale semantische context.

Kernmechanisme

Voor elke token $x_i$ in de feature map:

1. Lokaal Grafconstructie: Een lokaal kandidaatset $S_r(i)$ die ruimtelijk begrensd is, wordt gedefinieerd rond de roostercoördinaat van de token, met een vaste straal $r$.
2. Feature-geconditioneerde Affiniteiten: In plaats van geometrische interpolatie, berekent GraphScan attention-achtige affiniteiten tussen de query-token en zijn buren op basis van feature-相似heid en relatieve positionele bias.
   • Projecties voor Query, Key en Value worden berekend: $q_i, k_j, v_j$.
   • Affiniteitsscores $s_{ij}$ worden berekend met behulp van dot-producten en een leerbare relatieve positionele bias $b_{rel}(g_j - g_i)$.
   • Softmax-normalisatie levert gewichten $\alpha_{ij}$ op.
3. Eén-staps Message Passing: De output-token $x'_i$ wordt gegenereerd door waarde-features uit het semantische buurtgebied te aggregeren en een residu-verbinding toe te voegen:
   $$x'_i = x_i + \left( \sum_{j \in S_r(i)} \alpha_{ij} v_j \right) W_o$$
   Dit vervangt de geïsoleerde patch-representatie door een semantisch mengsel van nabijgelegen visuele bewijslast.

Integratie in Backbone

GraphScan is geïntegreerd in een hiërarchische Vision Mamba-backbone (GraphScan-Mamba) als een pre-SSM routing-laag.

• Architectuur: De backbone volgt een standaard vier-staps ontwerp met overlappende convolutiestammen en stapsgewijze downsampling.
• Plaatsing: Binnen elke blok is de stroom: Depthwise Conv (Vast Lokaal) $\to$ GraphScan (Gestudeerd Lokaal) $\to$ Selectieve SSM (Globaal).
• Adaptiviteit: De grafstraal $r$ neemt toe met de diepte van de stap (bijv. $r=1$ in vroege stadia, $r=3$ in latere stadia), waardoor het receptieve veld groeit van lokaal naar effectief globaal terwijl lineaire schaling behouden blijft.

Theoretische Implicaties

De auteurs analyseren GraphScan als een spaarzame, input-adaptieve preconditioner. Door de token-sequentie $X$ te wijzigen naar $X'$ voordat de SSM, beïnvloedt GraphScan de SSM op twee manieren:

1. Value Injectie: Het verandert de waarden die in de recurrente staat worden geschreven.
2. Parameter Modulatie: Omdat Mamba-stijl SSM's recurrente parameters ($\Delta, B, C$) genereren vanuit de huidige token, verandert het wijzigen van de token ook de selectieve parameters die staatspropagatie en uitlezing beheersen.
   Dit creëert een "lokaal-globale kern" waarbij een bronpatch de output beïnvloedt via een lokale semantische affiniteit $\alpha_{ij}$ en een globale selectieve propagatiefactor $K'_{t,i}$.

3. Belangrijkste Bijdragen

1. GraphScan Operator: Een nieuw scan-mechanisme dat scannen behandelt als "gestudeerd lokaal semantisch routing" in plaats van geometrische sequentiëring of coördinatie-selectie. Het behoudt het token-aantal en lineaire schaling terwijl het semantisch bewustzijn introduceert.
2. GraphScan-Mamba Backbone: Een hiërarchische implementatie van GraphScan die state-of-the-art (SOTA) prestaties bereikt onder Vision SSM's over meerdere taken zonder de kern SSM-recurrente logica te wijzigen.
3. Orthogonaliteit: De methode blijkt orthogonaal te zijn ten opzichte van verbeteringen aan de recurrente kant (bijv. SSD, niet-causale formuleringen), en biedt een complementaire ontwerphefboom voor Vision SSM's.
4. Interpreteerbaarheid: De methode induceert interpreteerbare verplaatsingsvelden over het token-rooster, visualiserend hoe het model informatie routeert op basis van semantische inhoud in plaats van vaste geometrie.

4. Experimentele Resultaten

De auteurs evalueren GraphScan-Mamba op drie standaard benchmarks, met vergelijkingen tegen ConvNets, Transformers en bestaande Vision SSM's (bijv. VMamba, DAMamba, Spatial-Mamba) bij vergelijkbare parameter- en FLOP-budgetten.

• ImageNet-1K Classificatie:
  • GraphScan-Mamba-B bereikt 86,5% top-1 nauwkeurigheid, wat de sterkste Vision SSM-baseline (Spatial-Mamba-B met 85,3%) met +1,2% overtreft en VMamba-B met +2,6%.
  • Het overtreft ook sterke ConvNet- en Transformer-backbones (bijv. ConvNeXt-B, Swin-B) bij vergelijkbare schalen.
• COCO Objectdetectie & Instance Segmentatie (Mask R-CNN):
  • Onder het 1x-schema bereikt GraphScan-Mamba-B 51,9 box mAP en 46,0 mask mAP, leidend alle Vision SSM-baselines.
  • Winsten worden effectief overgedragen naar dichte voorspellings taken, wat aangeeft dat de gestudeerde tokens robuust zijn voor detectie-schaal ruimtelijke structuren.
• ADE20K Semantische Segmentatie (UperNet):
  • GraphScan-Mamba-B bereikt 53,2% mIoU (single-scale), wat de beste Vision SSM-baseline (DAMamba-B met 51,9%) met +1,3% overtreft.
  • Multi-scale resultaten tonen consistente verbeteringen (53,6% vs 52,3%).

Ablatie Studies:

• Plaatsing: Pre-SSM plaatsing is kritiek; het verplaatsen van GraphScan post-SSM resulteert in een daling van 0,7% in nauwkeurigheid.
• Straal-schema: Een groeiend straal-schema $(1, 1, 2, 3)$ biedt de beste Pareto-front tussen rekenkracht en nauwkeurigheid.
• Relatieve Positionele Bias: Het opnemen van een leerbare relatieve positionele bias levert een consistente, zij het kleine, winst op.

5. Betekenis en Claims

Het artikel concludeert dat grafieken Vision SSM's wel helpen om beter te zien. De betekenis van dit werk ligt in het verschuiven van het ontwerpparadigma voor Vision SSM's:

• Van Geometrie naar Semantiek: Scannen mag niet worden behandeld als louter geometrische sequentiëring (een pad of coördinaat kiezen), maar als gestudeerd lokaal semantisch routing voordat globale state-space modellering plaatsvindt.
• Input-kant Complement: GraphScan biedt een oplossing aan de input-kant die aanvullend is op vooruitgang aan de recurrente kant. Het zorgt ervoor dat de tokens die de selectieve mixer binnenkomen al lokaal verankerd en semantisch bewust zijn, waardoor de conditionering van de globale sequentie verbetert zonder de interne dynamiek van de SSM te wijzigen.
• Generaliseerbaarheid: De aanpak is orthogonaal ten opzichte van de specifieke SSM-kern (bijv. Mamba-1/S6), wat suggereert dat deze kan worden toegepast op toekomstige SSM-varianten.

De auteurs claimen bescheiden dat hoewel GraphScan de prestaties en interpreteerbaarheid verbetert, het geen generalisatie garandeert in een formeel controle-theoretisch zin zonder verdere aannames, maar het wel een structureel mechanisme biedt voor rijkere lokale semantische inputs.