Graph Recognition via Subgraph Prediction

Probleemstelling

Het herkennen van visuele relaties in afbeeldingen, vaak gemodelleerd als het extraheren van een graaf (waarbij knopen entiteiten zijn en randen relaties), blijft een uitdagende taak voor kunstmatige intelligentie. Hoewel er grote vooruitgang is geboekt in taken zoals beeldclassificatie en objectdetectie, ontbreekt er een universele aanpak voor "beeld-naar-graaf" vertaling.

• Huidige beperkingen: Bestaande oplossingen zijn vaak specifiek voor één domein (bijv. moleculen, verkeersborden, scène-graaf) en kunnen niet zonder meer worden overgedragen naar andere contexten.
• Technische uitdagingen: Het gebruik van graafstructuren als output van neurale netwerken is complex vanwege:
  1. Compositionaliteit: Graafstructuren vereisen gelijktijdige voorspellingen van knopen, randen en hun eigenschappen, in tegenstelling tot pixels of tokens die vaak onafhankelijk kunnen worden gemodelleerd.
  2. Graph Isomorphism: Een graaf kan op vele manieren worden weergegeven (permutaties van knopen), wat het trainen met standaard verliesfuncties (zoals MSE of cross-entropy) moeilijk maakt omdat de modeloutput niet uniek is.
  3. Discrete en variabele grootte: Graafgroottes en connectiviteit variëren, wat de optimalisatie bemoeilijkt.

Methodologie: GraSP (Graph Recognition via Subgraph Prediction)

De auteurs stellen GraSP voor, een generiek raamwerk dat het probleem omzeilt door niet direct de volledige graaf te genereren, maar een sequentie van subgraaf-voorspellingen te modelleren.

Kernprincipes:

1. Markov Decision Process (MDP): Het generatieproces wordt geformaliseerd als een MDP zonder disconteringsfactor. De staat is een partiële graaf $G_t$, en de actie is het toevoegen van een rand (of een nieuwe knoop).
2. Vervanging van Reinforcement Learning (RL): In plaats van complexe RL-algoritmen te gebruiken om een waarde-functie te leren (wat vaak instabiel is en veel data vereist), transformeren de auteurs het probleem naar een binair classificatieprobleem.
   • De waarde-functie $V^{\pi^*}(G_t|I)$ wordt gedefinieerd als: 1 als $G_t$ een subgraaf is van de doelgraaf in de afbeelding, en 0 anders.
   • Het model leert dus een classifier die voorspelt of een gegeven subgraaf $G_t$ een geldig onderdeel is van de graaf die in de afbeelding $I$ wordt getoond.
3. Decoupling van Beslissing en Generatie:
   • Het model is onafhankelijk van hoe de graaf wordt gebouwd (de volgorde van toevoegingen).
   • Het model is onafhankelijk van wat er precies wordt toegevoegd (de specifieke structuur), zolang het maar een geldige subgraaf is.
   • Dit maakt het model agnostisch ten opzichte van het type graaf en de representatie.

Architectuur:

• Multi-modale input: Het model neemt een afbeelding $I$ en een graaf $G$ als input.
• FiLM-layers: Om visuele en grafische informatie te fusioneren, wordt een Graph Neural Network (GNN) gebruikt om een embedding van de graaf te genereren. Deze embedding fungeert als conditioner voor de beeldembedding (via een CNN, gebaseerd op ResNet-v2) door middel van FiLM-layers (Feature-wise Linear Modulation).
• Output: Een binaire classificatie (is dit een subgraaf?) en een "terminal flag" om te bepalen of het proces moet stoppen.
• Training: Er wordt gebruik gemaakt van een streaming architectuur. In plaats van een vast dataset, worden tijdens het trainen continu triplets $(I, G_t, y)$ gegenereerd, waarbij $y$ aangeeft of $G_t$ een subgraaf is van de doelgraaf in $I$.

Belangrijkste Bijdragen

1. Unificatie van Graafherkenning: GraSP biedt een eerste stap naar een verenigd raamwerk voor visuele graafherkenning dat niet afhankelijk is van domeinspecifieke encoding of complexe pipelines.
2. Omzeiling van Graph Isomorphism: Door te focussen op subgraaf-classificatie in plaats van directe graafgeneratie, worden problemen met knoopordening en isomorfisme opgelost.
3. Transfer Learning: Het model kan naadloos worden overgedragen tussen verschillende taken (bijv. van synthetische bomen naar moleculen) zonder aanpassingen aan de architectuur, mits de MDP-dynamiek (toestanden en acties) correct wordt gedefinieerd.
4. Efficiëntie: Door het gebruik van een binaire classifier in plaats van RL, wordt de trainingstabiliteit en snelheid aanzienlijk verbeterd.

Resultaten

De auteurs evalueren GraSP op synthetische benchmarks en een real-world toepassing:

1. Synthetische Bomen (Kleuren en Grootte):

   • Getest op bomen met 6-9 en 10-15 knopen met variërende kleuren voor knopen en randen.
   • Het model bereikte hoge nauwkeurigheid en toonde zero-shot generalisatie naar grotere bomen (16 knopen) die niet tijdens het trainen waren gezien.
   • De "top-k" nauwkeurigheid toonde aan dat het model fals-positieven effectief kon vermijden.

2. Moleculaire Herkenning (OCSR - Optical Chemical Structure Recognition):

   • Toepassing op de QM9-dataset (chemische structuren).
   • Hoewel GraSP niet de absolute state-of-the-art bereikte vergeleken met gespecialiseerde tools zoals MolGrapher of DECIMER, presteerde het aanzienlijk beter dan rule-based systemen (OSRA) en toonde het aan dat het model transfereerbaar is van synthetische bomen naar complexe moleculaire grafen.
   • Het model leerde semantische nuances (zoals het onderscheiden van atoomlabels en functionele groepen) zonder dat er domeinspecifieke regels in de loss-functie waren ingebouwd.

Betekenis en Toekomstperspectief

• Unificatie: GraSP bewijst dat het mogelijk is om een enkel raamwerk te bouwen dat werkt voor diverse graaftaken, wat de weg vrijmaakt voor meer algemene en krachtige methoden.
• Schaalbaarheid: De streaming-aanpak voor data-generatie maakt training op zeer grote en complexe datasets mogelijk zonder geheugenproblemen.
• Toekomstige uitdagingen:
  • Uitbreiding naar "open vocabulary" door tekst-embeddings van Large Language Models te gebruiken voor knoop- en randtypes (essentieel voor scène-graafherkenning).
  • Verbetering van de inferentie-efficiëntie voor zeer grote grafen door het gebruik van filters om irrelevante toestanden eerder uit te sluiten.
  • Integratie met andere modaliteiten dan alleen afbeeldingen (bijv. vector-embeddings van grafen).

Kortom, GraSP biedt een robuuste, flexibele en efficiënte oplossing voor het probleem van visuele graafherkenning door het generatieproces te herformuleren als een sequentiële subgraaf-classificatie, waardoor de complexiteit van directe graafgeneratie wordt omzeild.