Optimization-Free Topological Sort for Causal Discovery via the Schur Complement of Score Jacobians

1. Probleemstelling

Continue causale ontdekking heeft tot doel het onderliggende Gerichte Acyclische Graaf (DAG) te herstellen uit observationele data. Huidige state-of-the-art methoden (bijv. NOTEARS, DAGMA) vertrouwen op continue beperkte optimalisatie, waarbij representatieleren wordt gekoppeld aan structurele optimalisatie via niet-convexe acycliciteitsstraffen (bijv. $tr(e^{W \circ W}) = d$).

Belangrijkste Beperkingen:

• Lokale Optima: De niet-convexe aard van acycliciteitsstraffen zorgt ervoor dat op gradiënten gebaseerde oplosmiddelen vastlopen in lokale minima, vooral in hoogdimensionale regimes.
• Schaalbaarheid: Deze methoden lijden aan $O(d^3)$ rekentkosten per gradiëntstap door herhaalde acycliciteitscontroles, wat de schaalbaarheid beperkt tot hoogdimensionale datasets ($d \gg 100$).
• Overhead van Opnieuw Trainen: Bestaande op scores gebaseerde benaderingen vereisen vaak recursief opnieuw trainen van generatieve modellen op gemarginaliseerde subsets om de volgorde van knopen te identificeren, wat ernstige computatieflessenhalsen creëert.

2. Methodologie: Score-Schur Topologische Sortering (SSTS)

De auteurs stellen een ontkoppeld paradigma voor dat de bottleneck verschuift van niet-convexe optimalisatie naar statistische schatting van scores. De kernidee is dat de causale hiërarchie een geometrische signatuur achterlaat in de Score-Jacobi Informatiematrix (SJIM).

A. Theoretische Grondslag

• Scorefunctie & SJIM: Laat $s(x) = \nabla_x \log p(x)$ de scorefunctie zijn. De SJIM, $I$, wordt gedefinieerd als de verwachte negatieve Hessian van de log-dichtheid: $I = \mathbb{E}[-\nabla^2_x \log p(x)]$.
• Identificeerbaarheid van Bladeren (Stelling 3.1): In lineaire Gaussische Additieve Ruismodellen (ANM's) coderen de diagonaalelementen van de SJIM de topologische hiërarchie. Specifiek is een knoop $l$ een topologisch blad (sink) dan en slechts dan als zijn diagonaalelement $I_{ll}$ minimaal is ($1/\sigma^2$).
• Exacte Marginalisatie via Schur-complement (Stelling 3.2): Zodra een blad is geïdentificeerd, is het verwijderen ervan uit de grafiek wiskundig equivalent aan het berekenen van het Schur-complement van de SJIM met betrekking tot dat blad. Dit maakt recursieve eliminatie mogelijk zonder het generatieve model opnieuw te trainen.
• Niet-lineaire Uitbreiding & Verwachtingskloof: In niet-lineaire ANM's commuteren de verwachtingsoperator en de matrixinversie niet ($\text{Schur}(\mathbb{E}[H]) \neq \mathbb{E}[\text{Schur}(H)]$). De auteurs leiden een Verwachtingskloof ($\Delta$) af die evenredig is met de covariantie van de gradiënt van het ruismechanisme. Deze kloof introduceert structurele fouten in niet-lineaire situaties.

B. Algorithmus: Block-SSTS

Om de verwachtingskloof en variantie bij eindige steekproeven aan te pakken, introduceren de auteurs Block-SSTS:

1. Generatieve Modellering: Train een onbeperkt scorenetwerk (bijv. MLP) om $s_\theta(x)$ te schatten.
2. Sparre Jacobiaanse Prior: Pas een Group Lasso ($\ell_{1,2}$) straf toe op de gewichten van de invoerlaag om sparsiteit in de empirische Jacobiaan te induceren, waardoor de schattingsvariantie in hoge dimensies wordt verminderd.
3. Blok-Marginalisatie: In plaats van sequentiële verwijdering van één knoop, groepeert het algoritme parallelle bladknopen (die met vergelijkbare diagonale energieën binnen een tolerantie $\gamma$) en voert het een blok-Schur-complement inversie uit.
   • Dit comprimeert de extractiediepte en truncateert de accumulatie van de niet-lineaire verwachtingskloof.
   • Het vermijdt de $O(Nd^3)$ kosten van exacte steekproefsgewijze covariantiepatching.
4. Rand-Pruning: Zodra de topologische volgorde is geëxtraheerd, wordt het DAG hersteld via standaard sparre regressie (Lasso) voor elke knoop tegenover zijn toegestane voorouders.

3. Belangrijkste Bijdragen

1. Algebraïsche Mapping van Acycliciteit: Bewezen dat iteratieve marginalisatie van bladknopen exact equivalent is aan het Schur-complement van de SJIM in lineaire Gaussische ANM's. Voor niet-lineaire ANM's hebben ze de benaderingsfout (Verwachtingskloof) gekarakteriseerd.
2. Ontkoppelde Extractie: De niet-convexe optimalisatiebottleneck is volledig geëlimineerd. Causale ontdekking wordt herformuleerd als een statistisch schattingsprobleem gevolgd door deterministische matrixoperaties ($O(d^3)$ totaal, maar slechts één keer).
3. Schaalbaarheid tot $d=1000$: Introductie van Block-SSTS om hoogdimensionale niet-lineaire grafen te hanteren, met structurele herstel tot 1000 variabelen, een regime waar continue optimalisatiemethoden falen.
4. Metriscorrectie: Argumenteren tegen het gebruik van rangcorrelatie (Kendall's $\tau$) voor het evalueren van parallelle DAG's, en voorstellen van Edge Violations (EV) als de rigoureuze metriek die invariant is voor topologische ambiguïteit.

4. Experimentele Resultaten

• Lineaire Regimes: SSTS bereikt nul causale randovertredingen voor dimensies tot $d=1000$ op lineaire ANM's, wat de theoretische exactheid valideert.
• Niet-lineaire Regimes:
  • Efficiëntie: Bij $d=50$ reduceert SSTS de uitvoertijd van ~2700s (DAGMA) naar 3,66s terwijl het een aanzienlijk lagere Structurele Hamming-afstand (SHD: 2,6 vs 93,0) bereikt.
  • Schaalbaarheid: Bij $d=1000$ voltooit SSTS de extractie in minder dan 1 seconde, terwijl continue methoden computationeel onuitvoerbaar zijn.
  • Trade-off: Hoewel SSTS door de niet-lineaire verwachtingskloof een kleine structurele fout introduceert, blijft deze begrensd door de variantie van de schatting van het scorenetwerk bij eindige steekproeven.
• Real-world Data: Op het Sachs-eiwitsignaleringsnetwerk ($d=12$) presteerde SSTS beter dan DAGMA en Scalable SCORE in zowel nauwkeurigheid (SHD 13,8 vs 15,0/16,2) als snelheid (6,62s vs 182s/56s).
• Ablatiestudies:
  • Sparsiteit: Group Lasso-priors zijn cruciaal voor stabiliteit in data-arme regimes ($N=500, d=100$).
  • Blok-tolerantie: Matige blok-tolerantie ($\gamma \approx 0,05$) optimaliseert de truncatie van foutaccumulatie zonder de causale hiërarchie te schenden.

5. Betekenis en Conclusie

Dit werk herformuleert causale ontdekking fundamenteel van een beperkt optimalisatieprobleem naar een statistisch schattingsuitdaging. Door gebruik te maken van de geometrische eigenschappen van de scorefunctie en de algebraïsche eigenschappen van het Schur-complement, omzeilt SSTS de lokale optima en schaalbaarheidsproblemen die inherent zijn aan continue acycliciteitsstraffen.

Implicaties:

• Theoretisch: Vestigt een directe link tussen score-matching, informatiogeometrie en topologische sortering.
• Praktisch: Maakt het leren van causale structuren mogelijk op hoogdimensionale, niet-lineaire datasets (tot $d=1000$) die voorheen ontoegankelijk waren voor continue optimalisatiemethoden.
• Beperkingen: De fideliteit van de methode in niet-lineaire regimes wordt uiteindelijk begrensd door de nauwkeurigheid van de schatting van de scorefunctie (variantie bij eindige steekproeven) en de grootte van de niet-lineaire verwachtingskloof, en niet door convergentie van optimalisatie.

Kortom, SSTS biedt een deterministische, optimalisatievrije weg naar causale ontdekking, en bewijst dat zodra de niet-convexe bottleneck is verwijderd, de primaire uitdaging de statistische schatting van de score-geometrie wordt.