Research map / Graph learning / Graph algorithms and clustering

Differentiable Structure Learning with Partial Orders

NeurIPS 2024 · Graph learning › Graph algorithms and clustering · approach: Continuous DAG structure learning · 3 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a plug-and-play augmented acyclicity constraint that encodes partial order priors into differentiable DAG structure learning by adding maximal paths of the transitive reduction to the adjacency matrix.

Problem

Differentiable structure learning has lacked a feasible way to integrate partial order constraints (prior ordering knowledge) because such constraints live in the ordering space while continuous optimization operates in the graph space.

Approach

Converts partial orders into path-prohibition constraints and augments the acyclicity function with one term per maximal path of the transitive reduction of the partial order (each path added to the adjacency matrix with weight tau), which is proven equivalent to enforcing the partial order while being far cheaper than per-pair path prohibitions.

Key results

• On the Sachs dataset, linear NOTEARS with a partial order over 11 nodes using only 50 samples outperforms NOTEARS with all 853 samples.
• Single-chain partial orders improve SHD and F1 over NOTEARS, NOTEARS-MLP and DAGMA on most synthetic settings, with gains growing as chain length increases.
• The augmented acyclicity formulation achieves comparable F1 to the path-absence formulation (Eq. 8) but runs substantially faster (e.g., 41.9 s vs 1475.3 s at d=50 in one setting).

Measured effects reported in the paper

Surprising findings

• Some random ordering chains degrade performance, attributed to invalid or uninformative priors from non-unique topological sorts.
• Runtime with multiple chains first increases then decreases as the number of chains grows, because denser orders yield fewer maximal paths.

Limitations

• The augmented acyclicity constraint cannot be strictly satisfied during augmented Lagrangian optimization, so some prior orders may be violated in outputs.
• Runtime grows with complex multi-chain partial orders because the number of maximal paths increases.
• Incorrect ordering priors can strongly degrade results since the method strictly enforces them.

Experimental setup

Datasets: Sachs et al. 2005 flow cytometry dataset synthetic ER and SF random DAGs

Benchmarks: Sachs dataset synthetic ER and SF graphs

Metrics: SHD F1-score FDR TPR CPU time

Baselines: NOTEARS NOTEARS-MLP DAGMA

Builds on: NOTEARS NOTEARS-MLP DAGMA Wei et al. 2020 acyclicity characterization

Closest papers by meaning

• Differentiable Structure Learning with Ancestral Constraints (ICML 2025 · similarity 0.89)
• Markov Equivalence and Consistency in Differentiable Structure Learning (NeurIPS 2024 · similarity 0.89)
• Differentiable Structure Learning and Causal Discovery for General Binary Data (NeurIPS 2025 · similarity 0.86)
• DCILP: A Distributed Approach for Large-Scale Causal Structure Learning (AAAI 2025 · similarity 0.86)
• $\texttt{STRCMP}$: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization (NeurIPS 2025 · similarity 0.85)
• Scores for Learning Discrete Causal Graphs with Unobserved Confounders (AAAI 2024 · similarity 0.85)