📊 statistics

Exact Graph Learning via Integer Programming

Deze paper introduceert GLIP, een niet-parametrisch framework dat conditional independence-testing combineert met integer programming om exacte en globaal optimale grafen te leren zonder restrictieve aannames, wat resulteert in een open-source R-pakket dat superieure prestaties levert op diverse grafentypen.

Oorspronkelijke auteurs: Lucas Kook, Søren Wengel Mogensen

Gepubliceerd 2026-04-02

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Lucas Kook, Søren Wengel Mogensen

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorme, ingewikkelde machine probeert te begrijpen, zoals een menselijk lichaam, een beursmarkt of een klimaatmodel. Deze machine bestaat uit honderden onderdelen (variabelen) die allemaal met elkaar verbonden zijn. Soms veroorzaakt A een verandering in B, soms beïnvloeden B en C elkaar, en soms is het gewoon toeval.

Het doel van dit onderzoek is om de blauwdruk van deze machine te tekenen. In de wetenschap noemen we deze blauwdruk een "grafiek" of "netwerk". Het probleem is dat we de machine niet van binnen kunnen zien; we kunnen alleen kijken naar de data die eruit komt (bijvoorbeeld metingen). De kunst is om uit die data af te leiden wie met wie praat en wie de baas is.

Hier is hoe de auteurs, Lucas Kook en Søren Wengel Mogensen, dit probleem oplossen, vertaald naar alledaags taal:

1. Het oude probleem: Gissen en gokken

Vroeger waren de methoden om deze blauwdruk te tekenen als een hongerige zoektocht.

De "Gierige" methode: Stel je voor dat je een doolhof probeert te doorlopen. Een oude methode kijkt bij elke afslag alleen naar de eerste weg die eruitziet alsof hij goed is, en loopt daarheen. Het probleem is dat je zo vaak vastloopt in een doodlopende weg (een lokaal optimum) en nooit de echte uitgang vindt. Je mist de beste oplossing omdat je te snel een beslissing neemt.
De "Oracle" methode: Een andere methode deed alsof er een waarzegger (een oracle) was die altijd het juiste antwoord gaf op vragen als "Is A losgekoppeld van B?". Maar in de echte wereld hebben we geen waarzeggers; we hebben alleen onvolmaakte metingen. Als die metingen een beetje ruis bevatten, faalt deze methode.

2. De nieuwe oplossing: GLIP (Het slimme puzzelstukje)

De auteurs hebben een nieuwe methode bedacht genaamd GLIP (Graph Learning via Integer Programming). Je kunt dit zien als het overzetten van het tekenen van de blauwdruk naar een gigantische, logische puzzel die door een supercomputer wordt opgelost.

In plaats van te gissen, zetten ze het hele probleem om in een wiskundige formule (een "Mixed-Integer Program").

De Variabelen: Stel je voor dat elke mogelijke verbinding tussen twee onderdelen een schakelaar is (aan of uit).
De Regels: Ze voegen regels toe die zeggen: "Als schakelaar A aan staat, dan moet schakelaar B uit staan," of "Als er een verbinding is tussen A en C, dan kan er geen directe weg zijn tussen A en B."
De Doelstelling: De computer probeert alle schakelaars zo te zetten dat het resultaat het beste past bij de data die we hebben gemeten.

3. Het geheim: De "Kortste Weg" techniek

Het grootste probleem bij zo'n puzzel is dat er te veel mogelijkheden zijn. Voor een machine met slechts 10 onderdelen zijn er al meer combinaties dan er atomen in het heelal zijn. Als je alle paden zou tellen, zou de computer eeuwen nodig hebben.

Hier komt de creatieve innovatie van de auteurs:
Stel je voor dat je wilt weten of twee steden met elkaar verbonden zijn in een wegennet. Je hoeft niet elke mogelijke route te tellen (via Amsterdam, dan via Utrecht, dan via Rotterdam...). Je hoeft alleen te weten: Is er een kortste route?

De auteurs hebben een slimme manier bedacht om alleen de kortste verbindingen in de puzzel te coderen.
In plaats van een enorme berg variabelen (zoals een berg blokken die tot aan de maan reikt), bouwen ze een compacte, efficiënte structuur (zoals een strakke stapel blokken).
Hierdoor kan de computer veel grotere en complexere netwerken oplossen dan ooit tevoren mogelijk was. Ze noemen dit een "minimale lengte encoding".

4. Waarom is dit beter?

Geen gissen meer: In plaats van een gokje te wagen, garandeert deze methode dat je de beste mogelijke blauwdruk vindt die past bij de data. Het is alsof je niet meer naar een kaartje kijkt, maar de hele stad in 3D scant en de exacte wegen tekent.
Snelheid: Door slim te coderen (alleen de kortste wegen te bekijken), is het sneller dan de oude, "gierige" methoden, zelfs voor grote systemen.
Flexibiliteit: Het werkt voor verschillende soorten netwerken:
- DAGs: Netwerken zonder lussen (zoals een stamboom: je kunt niet je eigen grootvader zijn).
- ADMGs: Netwerken met verborgen variabelen (waarbij we niet alles kunnen meten, maar wel de gevolgen zien).
- Chain Graphs: Complexe netwerken met zowel eenrichtings- als tweerichtingsverkeer.

5. Het resultaat in de praktijk

De auteurs hebben hun methode getest op simulated data (virtuele machines) en echte datasets (zoals medische gegevens).

Ze ontdekten dat hun methode vaak sneller was dan de beste bestaande methoden.
Ze vonden betere oplossingen. Waar oude methoden soms verkeerde verbindingen maakten door ruis in de data (bijvoorbeeld door hoge correlaties die niet echt een oorzaak-gevolg relatie waren), zag GLIP de echte structuur.
Ze hebben de code openbaar gemaakt in een pakketje genaamd glip, zodat iedereen het kan gebruiken.

Samenvattend

Stel je voor dat je een detective bent die een moordzaak probeert op te lossen.

De oude methoden waren als een detective die alleen naar de eerste verdachte kijkt die er verdacht uitziet en dan stopt met zoeken.
GLIP is als een detective die alle mogelijke scenario's tegelijkertijd op een groot whiteboard schrijft, alle tegenstrijdigheden wegstreept met een rode stift, en dan precies het ene scenario overhoudt dat logisch klopt met alle bewijsstukken.

Dit papier laat zien dat je, door slimme wiskunde (Integer Programming) te combineren met een slimme manier van tellen (minimale lengte), complexe systemen exact kunt doorgronden, zonder te hoeven gokken.

Titel: Exacte Grafleer via Integer Programming (GLIP)

1. Het Probleem

Het leren van de afhankelijkheidsstructuur tussen variabelen in complexe systemen (bijv. in de geneeskunde, natuurwetenschappen en sociale wetenschappen) is een centraal probleem. Deze structuren worden vaak gemodelleerd als grafen, waarbij het infereren van deze grafen uit data bekendstaat als grafleer of causale ontdekking.

Bestaande methoden hebben echter significante beperkingen:

Beperkende aannames: Veel methoden vereisen specifieke verdelingsaannames (bijv. lineair Gaussisch) of functionele vormen.
Greedy algoritmen: Methodes zoals PC (Peter-Clark) of FCI (Fast Causal Inference) werken vaak op basis van een "oracle" (een ideale test voor conditionele onafhankelijkheid). In de praktijk, met eindige steekproeven, leiden deze greedy benaderingen tot suboptimale oplossingen omdat ze edges lokaal verwijderen op basis van niet-verwerpen van tests, wat gevoelig is voor schijnbare correlaties (multicollineariteit).
Benaderende oplossingen: Score-based methoden zonder strikte aannames lossen vaak slechts een benadering van het probleem op en garanderen geen globaal optimaal resultaat.

Het doel is een methode te vinden die globaal optimaal is, niet-parametrisch (geen verdelingsaannames) en exact werkt op basis van conditionele onafhankelijkheidstests.

2. Methodologie: GLIP

De auteurs introduceren GLIP (Graph Learning via Integer Programming), een raamwerk dat het probleem van grafleer formuleert als een Mixed-Integer Program (MIP).

Kernprincipes:

Doelfunctie: GLIP minimaliseert een score die gebaseerd is op de discrepantie tussen de conditionele onafhankelijkheden die door een graf worden voorspeld en de empirische $p$ -waarden verkregen uit conditionele onafhankelijkheidstests op de data.
Exactheid: In tegenstelling tot greedy methoden, zoekt GLIP naar de globale optimum van het optimalisatieprobleem.
Non-parametrisch: De methode maakt geen aannames over de onderliggende data-genererende processen (zoals lineariteit of normaliteit), zolang er maar conditionele onafhankelijkheidstests beschikbaar zijn.

De Innovatie: Minimal-Length Encoding
De grootste technische bijdrage is een nieuwe manier om grafische scheiding (separation) te coderen in een integer-programma:

Aanpak van Eberhardt et al. (2025): Deze eerdere methode gebruikte een variabele voor elk mogelijk pad in de graf. Dit leidt tot een aantal variabelen dat factorieel groeit ( $d!$ ), wat de methode onbruikbaar maakt voor grafen met meer dan 6 knopen.
GLIP-aanpak: In plaats van individuele paden te tellen, coderen de auteurs de lengte van het kortste verbindende pad tussen twee knopen gegeven een conditie-set.
- Ze definiëren variabelen $l^C_{\{i,j\}}$ die de lengte van het kortste pad vertegenwoordigen.
- Door gebruik te maken van regels over hoe paden samengesteld kunnen worden (bijv. als er een pad is van $i$ naar $k$ en een rand van $k$ naar $j$ , dan is er een pad van $i$ naar $j$ ), kunnen ze de relaties tussen deze lengte-variabelen lineair uitdrukken.
- Resultaat: Het aantal variabelen in het integer-programma groeit lineair met het aantal input $p$ -waarden, in plaats van factorieel. Dit maakt het mogelijk om veel grotere grafen exact op te lossen.

Ondersteunde Grafklassen:
GLIP is flexibel en ondersteunt diverse grafklassen, waaronder:

Gerichte Acyclische Grafen (DAGs)
Acyclische Gerichte Gemengde Grafen (ADMGs)
Gerichte Gemengde Grafen (DMGs)
Chain Graphs
Het kan zowel volledige Markov-equivalentieklassen als "zwakke" equivalentieklassen (waarbij alleen kleine conditie-sets worden overwogen) leren.

3. Belangrijkste Bijdragen

Formulering als MIP: Het probleem van grafleer is succesvol omgezet in een Mixed-Integer Program dat een globale optimum garandeert.
Efficiënte Codering: De introductie van "minimal-length encoding" reduceert de complexiteit van het probleem drastisch, waardoor het oplossen van grafen met 9 tot 14 knopen haalbaar wordt binnen redelijke rekentijden.
Open Source Implementatie: De auteurs hebben een R-pakket genaamd glip ontwikkeld en open-source beschikbaar gesteld, dat de methode implementeert voor DAGs, ADMGs en Chain Graphs.
Warm-start Strategie: Voor praktische toepassing wordt aanbevolen om een snelle, benaderende methode (zoals PC of FCI) eerst te draaien en het resultaat te gebruiken als "warm-start" voor GLIP. GLIP verbetert vervolgens deze initiële oplossing binnen een bepaald tijdsbudget.

4. Resultaten

De auteurs hebben GLIP geëvalueerd op zowel gesimuleerde data als benchmark datasets (zoals ALARM, ASIA, SACHS) en vergeleken met state-of-the-art methoden (PC, FCI, NOTEARS, en eerdere exacte methoden gebaseerd op Answer Set Programming - ASP).

Snelheid: GLIP is over het algemeen sneller dan de bestaande exacte ASP-methoden voor grafen tot 9 knopen. Voor grotere grafen (tot 14 knopen bij zwakke leer) is GLIP vaak de enige exacte methode die binnen een redelijke tijd (600 seconden) een oplossing vindt.
Kwaliteit: GLIP presteert consistent beter dan of gelijk aan greedy methoden (PC/FCI) en score-based methoden (NOTEARS) op maatstaven zoals de Structurele Hamming Afstand (SHD) en de F1-score.
Foutcorrectie: Een opmerkelijke bevinding is dat GLIP vaak een graf kan leren die beter overeenkomt met de waarheid dan de ruwe input $p$ -waarden suggereren. Dit wijst op een inherente "foutcorrectie" eigenschap: door de globale structuur te optimaliseren, kan de methode inconsistenties in individuele tests oplossen.
Schalingsvermogen: Waar eerdere exacte methoden faalden bij grafen groter dan 6 knopen, kan GLIP grafen met 9 knopen (voor volledige leer) en 14 knopen (voor zwakke leer) exact oplossen.

5. Betekenis en Conclusie

Dit werk is een doorbraak in het veld van causale ontdekking en grafleer. Het overbrugt de kloof tussen:

Exactheid: Het garandeert een globaal optimale oplossing, in tegenstelling tot greedy algoritmen.
Schalbaarheid: Door de nieuwe codering is het toepasbaar op grafen van een grootte die relevant is voor praktische toepassingen, in plaats van beperkt te blijven tot zeer kleine systemen.
Robuustheid: Het is non-parametrisch en minder gevoelig voor schijnbare correlaties die greedy methoden vaak verkeerd interpreteren.

De beschikbaarheid van het glip-pakket maakt deze geavanceerde techniek direct toepasbaar voor onderzoekers in diverse disciplines. De methode biedt een nieuw standaard voor het leren van complexe afhankelijkheidsstructuren waarbij de betrouwbaarheid van de gevonden structuur cruciaal is.