Colorful Talks with Graphs: Human-Interpretable Graph Encodings for Large Language Models

Probleemstelling

Grootte Taalmodellen (LLMs) hebben zich uitstekend bewezen in het verwerken van ongestructureerde tekst, maar kampen met fundamentele beperkingen bij het oplossen van grafproblemen. Grafen zijn combinatorische objecten zonder canonieke volgorde, wat vereist dat modellen permutatie-invariantie, symmetrie en redenering over multi-hop relationele structuren kunnen hanteren. Bestaande methoden om grafen naar tekst te vertalen (graph-to-text) lijden vaak onder de volgende tekortkomingen:

• Semantische kloof: LLMs zijn getraind op menselijke taal en hebben moeite met het redeneren over willekeurige numerieke labels of opake symbolische coderingen die vaak worden gebruikt om grafstructuren weer te geven.
• Schaalbaarheid en complexiteit: Veel grafproblemen (zoals subgraaf-isomorfisme) zijn NP-hard. Bestaande aanpakken presteren vaak goed op lokale queries (bijv. graad van een knooppunt) maar falen bij taken die globale structurele redenering vereisen, zoals het vinden van kortste paden of maximale stromen in grotere grafen.
• Gebrek aan interpretatie: Bestaande coderingen missen vaak semantische betekenis die aansluit bij de inductieve bias van LLMs.

Methodologie: CL-OWL

De auteurs introduceren CL-OWL (Colorful Ordered Weisfeiler-Leman), een methode die grafstructuren vertaalt naar menselijk interpreteerbare teksten door gebruik te maken van een variatie van het Weisfeiler-Leman (WL) verfijningsschema, gekoppeld aan kleurtokens.

1. Structuurcodering (Ordered 1-WL Refinement):
In plaats van standaard WL-labels (willekeurige gehele getallen uit een hash-functie) te gebruiken, ontwikkelen de auteurs een geordende 1-WL verfijning.

• Het algoritme initialiseert knooppunten en verfijnt hun labels iteratief door de multiset van de labels van buren te aggregeren.
• Cruciaal is dat de aggregatie een deterministische, ordebehoudende canonisering toepast. Hierdoor krijgen knooppunten met een hogere structurele connectiviteit (bijv. hogere graad of meer buren in de buurt) systematisch hogere numerieke labels.
• Dit creëert een labelreeks die correleert met concepten als "centrale" knooppunten en afstand-gewogen connectiviteit, wat wiskundig wordt onderbouwd door een relatie met afstandsschelpen (distance shells).

2. Vertaling naar Menselijke Tokens (Kleuren):
De numerieke WL-labels worden vertaald naar natuurlijke taal kleurtokens (bijv. "rood", "oranje", "groen").

• Semantische gronding: LLMs hebben een sterke voorkeur voor semantisch betekenisvolle tokens die tijdens pre-training zijn geleerd. Kleuren bieden een intuïtief vergelijkingskader (bijv. "rood is dichter bij oranje dan bij blauw").
• Behoud van structuur: De mapping is zo ontworpen dat knooppunten met vergelijkbare structurele rollen vergelijkbare kleuren krijgen, en dat de volgorde van de kleuren de volgorde van de structurele complexiteit weerspiegelt.
• Prompt Constructie: De uiteindelijke prompt bevat de graaf (als lijsten van buren), de WL-labels, de bijbehorende kleuren, en de taakomschrijving. Dit stelt de LLM in staat om te redeneren over zowel lokale als globale structurele afhankelijkheden.

Belangrijkste Bijdragen

1. Menselijk interpreteerbare structuurcodering: Een nieuwe graph-to-text strategie die expliciete structurele informatie injecteert in prompts via WL-gebaseerde tokens die zijn gemapt naar natuurlijke kleurtokens.
2. Theoretische onderbouwing: Een principieel bewijs dat de geordende 1-WL-verfijning consistent is met een brede klasse van centraliteitsmaten en afstand-gewogen connectiviteit. Dit valideert dat de gegenereerde labels niet willekeurig zijn, maar betekenisvolle structurele informatie dragen.
3. Uitgebreide experimentele evaluatie: Een grondige studie over diverse graf-families (Erdős–Rényi, Barabási–Albert) en taken (lokaal tot globaal), inclusief synthetische en real-world datasets (Cora, Citeseer, PubMed, OGBN-ArXiv).

Resultaten

De experimenten tonen aanzienlijke verbeteringen aan ten opzichte van bestaande baselines (zoals "Talk Like a Graph" of TLG):

• Verbeterde Redenering: CL-OWL en de varianten (alleen kleuren of alleen labels) presteren significant beter op complexe taken zoals Maximale Stroom, Kortste Pad en Bereikbaarheid. De verbetering is het grootst bij taken die globale structuur vereisen.
• Compressie en Schaalbaarheid: De methode maakt "compressed prompting" mogelijk. Door alleen de directe buren van een query-knooppunt te serialiseren, maar wel de WL-afgeleide kleuren te behouden, behouden de modellen hun prestaties. Baselines die de volledige graaf moeten serialiseren, zien hun prestaties sterk dalen bij grotere grafen. CL-OWL behoudt hoge nauwkeurigheid zelfs met slechts 1-hop context.
• Aanpassing aan Dataset Complexiteit:
  • Voor kleinere, minder complexe grafen presteert de "kleur-only" variant (C-OWL) vaak het beste.
  • Voor grotere, complexere grafen (zoals OGBN-ArXiv) presteert de combinatie van labels en kleuren (CL-OWL) het beste, wat suggereert dat menselijk interpreteerbare cues helpen bij het vastleggen van lange-afstandsafhankelijkheden.
• Ablatie-studies: Het gebruik van natuurlijke kleurtokens presteert aanzienlijk beter dan het gebruik van synthetische hue-identificatoren of menselijke namen, wat bevestigt dat de semantische gronding van de tokens essentieel is voor de LLM.

Betekenis en Conclusie

Dit paper toont aan dat de kloof tussen grafstructuren en LLM-redenering kan worden overbrugd door menselijk interpreteerbare, semantisch gewenste coderingen te gebruiken in plaats van willekeurige symbolen.

De kerninzicht is dat LLMs beter kunnen redeneren over grafen wanneer de structuur wordt gepresenteerd in een vorm die aansluit bij hun linguïstische vooropleiding (zoals kleuren die relaties en gradaties uitdrukken). CL-OWL biedt een trainingsvrije, schaalbare oplossing die de prestaties van LLMs op grafproblemen verbetert zonder de noodzaak van dure fine-tuning of het integreren van zware graf-neurale netwerken (GNNs) als embedders. Dit opent de deur voor het gebruik van algemene LLMs als universele oplossers voor gestructureerde redeneringstaken.