# Active causal structure learning with advice

arXiv: https://arxiv.org/abs/2305.19588 · HTML: https://mlsanity.com/paper/2305.19588/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 119 references that are in the map.
- First posted on arXiv 31 May 2023.

## Builds on (most cited first, 30 of 32)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Learning Bayesian Networks: The Combination of Knowledge and Statistical Data](https://mlsanity.com/paper/1302.6815/) (2013)
- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Permutation-based Causal Inference Algorithms with Interventions](https://mlsanity.com/paper/1705.10220/) (2017)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [Learning Causal Graphs with Small Interventions](https://mlsanity.com/paper/1511.00041/) (2015)
- [ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discovery](https://mlsanity.com/paper/1902.10347/) (2019)
- [Strong Completeness and Faithfulness in Bayesian Networks](https://mlsanity.com/paper/1302.4973/) (2013)
- [Cost-Optimal Learning of Causal Graphs](https://mlsanity.com/paper/1703.02645/) (2017)
- [Online Computation with Untrusted Advice](https://mlsanity.com/paper/1905.05655/) (2019)
- [A Transformational Characterization of Equivalent Bayesian Network Structures](https://mlsanity.com/paper/1302.4938/) (2013)
- [Secretaries with Advice](https://mlsanity.com/paper/2011.06726/) (2020)
- [Better and Simpler Learning-Augmented Online Caching](https://mlsanity.com/paper/2005.13716/) (2020)
- [Learning Augmented Energy Minimization via Speed Scaling](https://mlsanity.com/paper/2010.11629/) (2020)
- [Active Structure Learning of Causal DAGs via Directed Clique Tree](https://mlsanity.com/paper/2011.00641/) (2020)
- [Experimental Design for Cost-Aware Learning of Causal Graphs](https://mlsanity.com/paper/1810.11867/) (2018)
- [A Bayesian Approach to Learning Causal Networks](https://mlsanity.com/paper/1302.4958/) (2013)
- [Verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2206.15374/) (2022)
- [Being Bayesian about Network Structure](https://mlsanity.com/paper/1301.3856/) (2013)
- [A Novel Prediction Setup for Online Speed-Scaling](https://mlsanity.com/paper/2112.03082/) (2021)
- [ML-based Fault Injection for Autonomous Vehicles: A Case for Bayesian Fault Injection](https://mlsanity.com/paper/1907.01051/) (2019)
- [Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs](https://mlsanity.com/paper/2012.09679/) (2020)
- [A Universal Error Measure for Input Predictions Applied to Online Graph Problems](https://mlsanity.com/paper/2205.12850/) (2022)
- [Minimal enumeration of all possible total effects in a Markov equivalence class](https://mlsanity.com/paper/2010.08611/) (2020)

## Built on by (most cited first, 10 of 10)

- [Online bipartite matching with imperfect advice](https://mlsanity.com/paper/2405.09784/) (2024)
- [Learning multivariate Gaussians with imperfect advice](https://mlsanity.com/paper/2411.12700/) (2024)
- [Approximate Proportionality in Online Fair Division](https://mlsanity.com/paper/2508.03253/) (2025)
- [Probably approximately correct high-dimensional causal effect estimation given a valid adjustment set](https://mlsanity.com/paper/2411.08141/) (2024)
- [Optimizing Health Coverage in Ethiopia: A Learning-augmented Approach and Persistent Proportionality Under an Online Budget](https://mlsanity.com/paper/2509.00135/) (2025)
- [Product distribution learning with imperfect advice](https://mlsanity.com/paper/2511.10366/) (2025)
- [Membership Testing in Markov Equivalence Classes via Independence Query Oracles](https://mlsanity.com/paper/2403.05759/) (2024)
- [Linear Causal Discovery with Interventional Constraints](https://mlsanity.com/paper/2510.26342/) (2025)
- [Causal Preference Elicitation](https://mlsanity.com/paper/2602.01483/) (2026)
- [Online Allocation with Unknown Shared Supply](https://mlsanity.com/paper/2605.07080/) (2026)

## Abstract (arXiv)

We introduce the problem of active causal structure learning with advice. In the typical well-studied setting, the learning algorithm is given the essential graph for the observational distribution and is asked to recover the underlying causal directed acyclic graph (DAG) G^* while minimizing the number of interventions made. In our setting, we are additionally given side information about G^* as advice, e.g. a DAG G purported to be G^*. We ask whether the learning algorithm can benefit from the advice when it is close to being correct, while still having worst-case guarantees even when the advice is arbitrarily bad. Our work is in the same space as the growing body of research on algorithms with predictions. When the advice is a DAG G, we design an adaptive search algorithm to recover G^* whose intervention cost is at most O(max1, log psi) times the cost for verifying G^*; here, psi is a distance measure between G and G^* that is upper bounded by the number of variables n, and is exactly 0 when G=G^*. Our approximation factor matches the state-of-the-art for the advice-less setting.