Reproduce “Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Models” on OpenResearch

About this paper

Ehsan Sharifian, Saber Salehkaleybar, Negar Kiyavash

This research presents an adaptive experiment design strategy for learning causal structures in linear non-Gaussian cyclic models, which are difficult to identify from observational data. The approach combinatorially characterizes equivalence classes of graphs and uses an adaptive greedy intervention policy, achieving near-optimal performance in identifying true causal structures and demonstrating robustness in finite-sample settings.

Key insights

• Distribution-equivalent graphs in linear non-Gaussian cyclic models correspond to unique perfect matchings in a specific bipartite graph, with strongly connected components (SCCs) remaining invariant.
• The defined reward function for experiment design is adaptive monotone and adaptive submodular, providing a theoretical guarantee that a greedy adaptive policy achieves a near-optimal approximation.
• Each single-variable intervention explicitly identifies one true matching edge in the bipartite graph, efficiently eliminating incompatible causal graphs from the equivalence class.

Summary by alphaXiv.