Efficient Causal Graph Discovery Using Large Language Models

Probleemstelling

Causale ontdekking (causal discovery) is het proces van het identificeren van causale relaties tussen variabelen, wat resulteert in een Gerichte Acyclische Grafiek (DAG). Traditionele methoden (zoals GES, PC, NOTEARS) vertrouwen op numerieke observatiedata en statistische optimalisatie. Hoewel deze methoden strikt zijn, vereisen ze vaak grote hoeveelheden data en zijn ze computatie-intensief.

Recente werken hebben Large Language Models (LLMs) gebruikt om causale relaties af te leiden op basis van metadata (variabele namen en beschrijvingen) in plaats van ruwe data. Echter, bestaande LLM-benaderingen gebruiken een paarsgewijze query-aanpak (pairwise query). Bij deze methode wordt voor elke mogelijke combinatie van twee variabelen (A en B) een vraag gesteld aan het LLM om de richting van de causaliteit te bepalen.

• Het probleem: Voor een grafiek met $n$ variabelen vereist deze aanpak $\binom{n}{2}$ queries, wat leidt tot een kwadratische complexiteit van $O(n^2)$.
• Gevolg: Deze methode is niet schaalbaar voor grotere grafieken. Experimenten in eerdere studies waren beperkt tot zeer kleine grafieken (bijv. 12 variabelen), omdat het aantal queries voor grotere sets (bijv. 200+ variabelen) onpraktisch groot wordt.

Methodologie

De auteurs stellen een nieuw framework voor dat een Breadth-First Search (BFS) strategie combineert met de kennis van LLMs om volledige causale grafieken te ontdekken met een lineaire query-complexiteit van $O(n)$.

Het framework bestaat uit drie fasen:

1. Initialisatie (Initialization Stage):

   • Het LLM wordt gevraagd om variabelen te identificeren die niet worden veroorzaakt door andere variabelen in de grafiek (de "bronnen" of root nodes).
   • Deze variabelen worden toegevoegd aan een BFS-queue.
   • Prompt: Het model krijgt alle variabelebeschrijvingen en moet de onafhankelijke variabelen selecteren.

2. Expansie (Expansion Stage):

   • Het LLM wordt iteratief gevraagd om, gegeven een huidige knoop (uit de queue), alle variabelen te identificeren die door deze knoop worden veroorzaakt.
   • In plaats van één paar te vragen, vraagt het model om een lijst van alle mogelijke effecten van de huidige variabele.
   • Prompt: Het model krijgt de huidige graafstructuur (reeds voorspelde relaties) en de beschrijving van de huidige knoop, en moet een lijst van beïnvloede variabelen genereren.

3. Insertie en Cycluscontrole (Insertion Stage):

   • De voorspelde randen (edges) worden toegevoegd aan de graaf, mits ze geen cyclus creëren.
   • Omdat LLMs soms randen genereren die de DAG-constraint schenden, voert het algoritme een cycluscontrole uit (via Depth-First Search) voordat een rand wordt geaccepteerd.
   • Nieuw verbonden variabelen worden toegevoegd aan de queue voor verdere expansie.
   • Dit proces herhaalt zich totdat alle knopen zijn bezocht.

Optimalisatie met Observatiedata:
Hoewel de methode primair op metadata werkt, tonen de auteurs aan dat het toevoegen van statistische informatie (zoals Pearson-correlatiecoëfficiënten) aan de prompt de prestaties kan verbeteren wanneer observatiedata beschikbaar is. Dit helpt het LLM wanneer zijn interne kennis ontoereikend is.

Belangrijkste Bijdragen

1. Lineaire Schaalbaarheid: De methode reduceert het aantal benodigde LLM-queries van $O(n^2)$ naar $O(n)$ door gebruik te maken van de topologische volgorde en BFS-expansie. Dit maakt het toepasbaar op veel grotere grafieken dan eerder mogelijk was.
2. Onafhankelijkheid van Observatiedata: Het framework kan volledig werken op basis van semantische kennis (metadata) zonder numerieke data, wat het uniek maakt ten opzichte van traditionele statistische methoden.
3. Garantie van DAG-constraint: Door een cycluscontrole in te bouwen, wordt gegarandeerd dat het resultaat een acyclische graaf is, ondanks dat LLMs soms inconsistenties genereren.
4. Eerste toepassing op grote grafieken: Dit is, voor zover bekend, de eerste LLM-methode die succesvol wordt getest op grafieken met honderden variabelen.

Resultaten

De auteurs hebben hun methode getest op drie datasets van verschillende grootte:

1. Asia: 8 knopen, 8 randen (Klein).
2. Child: 20 knopen, 25 randen (Middelgroot).
3. Neuropathic Pain: 221 knopen, 770 randen (Groot).

Kernbevindingen:

• Prestaties: De voorgestelde methode behaalde state-of-the-art resultaten op alle drie de grafieken, gemeten aan de hand van F-score en de genormaliseerde Hamming-distantie (NHD) ratio.
  • Op de Asia-grafiek behaalde de methode zonder data een F-score van 0.93.
  • Op de Child-grafiek behaalde de methode met data (10.000 samples) een F-score van 0.63, wat beter was dan alle numerieke baselines.
  • Op de Neuropathic Pain-grafiek (221 knopen) faalden traditionele methoden (GES, PC) of konden ze niet worden uitgevoerd vanwege geheugen- of rekenlimieten. De LLM-methode was de enige die een redelijke prestatie leverde (F-score 0.35), terwijl paarsgewijze queries onpraktisch zouden zijn (24.310 queries vereist).
• Efficiëntie: De methode vereist aanzienlijk minder data dan numerieke methoden (die vaak duizenden tot tienduizenden samples nodig hebben voor vergelijkbare prestaties) en is veel sneller in termen van query-aantal.
• Data vs. Kennis: Op kleine grafieken volstaat de interne kennis van het LLM vaak. Op grotere grafieken verbetert het toevoegen van correlatiestatistieken de prestaties aanzienlijk.

Betekenis en Toekomstperspectief

Dit paper markeert een belangrijke stap in het veld van causale ontdekking. Het bewijst dat LLMs, wanneer ze op een slimme, gestructureerde manier (BFS) worden ingezet, kunnen fungeren als krachtige tools voor het reconstrueren van complexe causale structuren zonder de noodzaak van uitgebreide datasets.

• Toepassingsbereik: De methode is direct toepasbaar in domeinen waar data schaars is of waar alleen expertkennis (beschrijvingen) beschikbaar is.
• Toekomstig werk: De auteurs suggereren het combineren van LLM-kennis met statistische methoden (hybride aanpakken), het gebruik van geavanceerde prompting-strategieën zoals "Tree of Thoughts", en het testen op verschillende LLM-modellen om de invloed van modelgrootte te onderzoeken.

Samenvattend biedt deze aanpak een flexibele, schaalbare en data-efficiënte oplossing voor een van de meest uitdagende problemen in AI: het begrijpen van oorzakelijke relaties in complexe systemen.