Optimization-Free Topological Sort for Causal Discovery via the Schur Complement of Score Jacobians
Rui Wu, Hong Xie · 2026
Read Optimization-Free Topological Sort for Causal Discovery via the Schur Complement of Score Jacobians by Rui Wu, Hong Xie (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-25295.txt.
Introduction
Wu and Xie propose the Score-Schur Topological Sort, a method finding order from generative models. Causal discovery couples representation learning with structural optimization via non-convex penalties, trapping solvers in local optima. They shift the bottleneck to score estimation, showing iterative graph trimming equals a Schur complement of the Score-Jacobian matrix. For non-linear systems, they formulate the Schur trimming gap and introduce Block-SSTS. SSTS enables causal analysis on non-linear graphs up to dimension 1000.
Catalog record
| CREATOR | Rui Wu, Hong Xie |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 63850 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.25295
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimization-Free Topological Sort for Causal Discovery via the Schur Complement of Score Jacobians Rui Wu, Hong Xie Abstract Continuous causal discovery typically couples representation learning with structural optimization via non-convex acyclicity penalties, which subjects solvers to local optima and restricts scalability in high-dimensional regimes. We propose a decoupled paradigm that shifts the causal discovery bottleneck from non-convex optimization to statistical score estimation. We introduce the Score-Schur Topological Sort (SSTS), an algorithm that extracts topological order directly from unconstrained generative models, bypassing constrained structure optimization. We establish that the causal hierarchy leaves a geometric signature within the score function: iterative graph marginalization is mathematically equivalent to computing the Schur complement of the Score-Jacobian Information Matrix (SJIM) under linear conditions. This translates the acyclicity constraint into an algebraic procedure with a dominant cost of 𝒪 ( d 3 ) \mathcal{O}(d^{3}) operations. For non-linear systems, we formulate the expectation gap of Schur marginalization and introduce Block-SSTS to compress extraction depth, bounding structural error. Empirically, SSTS allows causal structural analysis on non-linear graphs up to d = 1000 d=1000 . At this scale, our framework indicates that once the non-convex optimization bottleneck is mathematically bypassed, the structural fidelity of continuous causal discovery is bounded by the finite-sample estimation variance of the global score geometry. By reducing graph extraction to matrix operations, this work reframes scalable causal discovery from a constrained optimization problem to a statistical estimation challenge. 1 Introduction Discovering the underlying directed acyclic graph (DAG) from observational data is a core problem in statistical machine learning [ 13 , 20 ] . Combinatorial search methods are constrained by exponential scaling. 24 introduced NOTEARS, which established a continuous algebraic characterization of acyclicity ( \mathrm{tr}(e^{W\circ W})=d ), enabling gradient-based optimization algorithms [ 1 ] . While offering computational advantages over search algorithms, continuous constrained optimization faces a persistent bottleneck: acyclicity penalties are non-convex. When applied to high-dimensional or non-linear data, optimizers converge to local minima, producing structural false discoveries. Mitigating this necessitates hyperparameter tuning alongside heuristic post-hoc thresholding. Score-based generative models [ 6 , 19 , 4 ] have been investigated for causal discovery [ 15 ] . The Jacobian of the score function (i.e., the Hessian of the log-density) contains sufficient information to identify topological leaf nodes. Identifying subsequent nodes requires retraining the score model on marginalized subsets or designing masked architectures, restricting scalability. We present the Score-Schur Topological Sort (SSTS) , which extracts causal topological order directly from the score function of an unconstrained generative model. By decoupling representation learning from topological extraction, we demonstrate that causal hierarchy leaves an extractable algebraic signature in the geometry of the score function \nabla_{\mathbf{x}}\log p(\mathbf{x}) . Our contributions are: 1. Algebraic Mapping of Acyclicity (Linear Exactness): In linear Gaussian ANMs, we establish an exact equivalence between iterative leaf-node marginalization and the Schur complement of the Score-Jacobian Information Matrix (SJIM). For non-linear ANMs, we characterize the non-commutativity between expectation and Schur marginalization via an explicit expectation gap. 2. Decoupled Extraction: By bypassing the non-convex optimization bottleneck, SSTS reframes high-dimensional causal discovery from combinatorial search to pure statistical estimation. 3. Characterization of Non-linear Boundaries: We formulate the algebraic expectation gap of Schur marginalization in non-linear Additive Noise Models (ANMs). To bound this structural error accumulation, we introduce Block-SSTS, which compresses the extraction depth and scales causal recovery up to d=1000 variables in experiments. Stage 1: Generative Modeling Stage 2: Algebraic Structure Discovery 1. Input Data \mathbf{X}\in\mathbb{R}^{N\times d} ANM Manifold 2. Pre-trained Score \min_{\theta}\mathbb{E}\|s_{\theta}-\nabla\log p\|^{2}_{2} \nabla_{\mathbf{x}}s_{\theta} Extraction 3. Sparse Hessian \hat{\mathcal{I}}\approx\frac{1}{N}\sum-\nabla_{\mathbf{x}}s_{\theta} w/ Group Lasso \ell_{1,2} 4. Score-Schur Sort Block Marginalization \arg\min(\hat{\mathcal{I}}_{ii})\Rightarrow\mathrm{Leaf} DAG \mathcal{G} Representation Learning Algebraic Extraction Lasso Pruning Geometric Signature \mathcal{O}(d) Iters Figure 1 : Decoupled Architecture of SSTS. Stage 1 optimizes an unconstrained density estimator to capture the data manifold. Stage 2 executes a structure-optimization-free algebraic extraction. Mapping iterative leaf-node marginalization as the Schur complement of the estimated Score-Jacobian Information Matrix replaces constrained acyclicity optimization with deterministic algebraic elimination (exact under linear Gaussian conditions, approximate otherwise). 2 Related Work Continuous Causal Discovery. The transition from combinatorial search to continuous optimization advanced causal discovery. Following NOTEARS [ 24 ] , efforts expanded continuous acyclicity constraints to non-linear neural networks [ 8 ] , graph neural networks [ 21 ] , and exact likelihood frameworks [ 12 ] . Recent advancements integrated differentiable penalties into Bayesian structure learning [ 10 ] and log-determinant characterizations [ 1 ] . Because these paradigms inherently couple graph discovery with parameter estimation, they suffer from non-convex penalty landscapes. Gradient-based optimizers are thus trapped in local optima when scaling to high-dimensional datasets. Order-Based Search and Generative Models. Topological order search reduces the DAG identification space to permutations, enabling algorithms to evaluate edges systematically under continuous Additive Noise Models (ANMs) [ 5 , 14 ] . Generative models, including normalizing flows [ 7 ] and diffusion models [ 4 , 19 ] , have been applied to structure learning. Specifically, score matching techniques isolate leaf nodes from the data log-density [ 15 ] . Extensions of this framework [ 11 , 17 ] , nevertheless, continue to rely on recursive network retraining or diffusion-guided structural search to sequence the remaining nodes, creating severe computational bottlenecks. Our Distinction. Existing score-based paradigms rely on iterative model retraining or heuristic search to sequentially isolate nodes. In contrast, SSTS offers a deterministic algebraic extraction procedure. By mapping continuous graph marginalization to the Schur complement of a single pre-trained Score-Jacobian Information Matrix [ 9 , 3 ] , SSTS decouples generative representation learning from the topological sort. Non-convex acyclicity optimization is bypassed, and the hierarchy is obtained via deterministic matrix operations (exact in linear Gaussian regimes and approximate otherwise). 3 Theoretical Foundation: Score-Jacobian Geometry and Topology In linear Gaussian ANMs, the topological ordering is recoverable from the SJIM via Schur-complement-based elimination. For non-linear ANMs, the same elimination on the expected SJIM introduces an expectation gap, which we characterize below. We consider observational data generated by a continuous Additive Noise Model (ANM) [ 18 , 5 ] . Let \mathcal{G}=(\mathcal{V},\mathcal{E}) be a DAG over d variables. The structural equations are: x_{i}=f_{i}(\mathbf{x}_{\mathrm{pa}(i)})+\epsilon_{i},\quad i=1,\dots,d. (1) where \mathrm{pa}(i) denotes the parents of node i , f_{i} are smooth, twice-differentiable functions, and \epsilon_{i} are mutually independent noise variables. Assumption 3.1 (Homoscedastic Gaussian Noise) . Noise components \epsilon_{i}\sim\mathcal{N}(0,\sigma^{2}) are Gaussian with variance \sigma^{2}>0 . The conditional log-likelihood is \log p_{\epsilon_{i}}(\epsilon_{i})=-\frac{\epsilon_{i}^{2}}{2\sigma^{2}}-\frac{1}{2}\log(2\pi\sigma^{2}) . Assumption 3.2 (Causal Faithfulness and Non-degeneracy) . For any directed edge j\to i\in\mathcal{E} , the structural equation f_{i} is non-degenerate with respect to x_{j} , satisfying: \mathbb{E}_{p(\mathbf{x})}\left[\left(\frac{\partial f_{i}}{\partial x_{j}}\right)^{2}\right]>0 . Let s(\mathbf{x})=\nabla_{\mathbf{x}}\log p(\mathbf{x}) be the true score function. We define \mathcal{I}\in\mathbb{R}^{d\times d} as the Expected Score-Jacobian Information Matrix (SJIM), formulated as the expected negative Hessian of the log-density: \mathcal{I}=\mathbb{E}_{p(\mathbf{x})}\left[-\nabla_{\mathbf{x}}^{2}\log p(\mathbf{x})\right]. (2) Under the strictly additive noise formulation (Assumption 3.1 ), each conditional distribution p(x_{i}\mid\mathbf{x}_{\mathrm{pa}(i)}) forms a location family parameterized by \mathbf{x}_{\mathrm{pa}(i)} . In this regime, the SJIM corresponds to the Fisher Information Matrix with respect to these location parameters. Hereafter, we refer to \mathcal{I} as the structural information matrix. 3.1 Exact Leaf Identifiability via Diagonal Energy Building upon the leaf identifiability principles of score-based causal discovery [ 15 ] , we show that the diagonal elements of \mathcal{I} explicitly encode the DAG’s topological hierarchy.