Abstract
Causal structure discovery is a fundamental challenge in scientific research, often hindered by the NP-hard nature of searching for Directed Acyclic Graphs (DAGs). While continuous optimization methods have gained popularity, they frequently converge to local optima. This paper presents Bloom, a novel framework that reformulates causal discovery as a bilevel polynomial optimization problem. By integrating observational and interventional data and employing semidefinite programming (SDP) relaxations via the Lasserre hierarchy, Bloom provides theoretical guarantees for global optimality and convergence. Empirical results on synthetic and real-world datasets, including the Sachs protein-signaling network, demonstrate that Bloom significantly outperforms existing state-of-the-art methods in accuracy and robustness.
Introduction
Identifying causal relationships—the "who-causes-what"—is essential across disciplines such as genetics, economics, and social sciences. Traditionally, this involves searching for the true Directed Acyclic Graph (DAG) that represents the underlying system. However, this search space grows super-exponentially with the number of variables, making the problem NP-hard.
Recent advancements have shifted toward "continuous optimization" methods, such as Notears, which treat graph discovery as a calculus problem. While these methods are computationally efficient, they rely on gradient-based local search, which often traps the algorithm in local optima. Furthermore, these methods frequently struggle to effectively integrate interventional data—where variables are actively manipulated—with observational data.
The Bloom Framework
To address these challenges, the authors introduce Bloom (Bilevel polynomial optimization), a framework designed to provide global optimality guarantees. Bloom's methodology is built upon three core innovations:
1. Bilevel Modeling
Bloom employs a two-tier optimization structure. The upper level leverages interventional data to refine the graph's causal directions, while the lower level ensures the model remains consistent with the patterns found in observational data. This hierarchical approach respects the inherent differences between the two data types, allowing for more precise structure identification.
2. Polynomial Reformulation and SDP Relaxations
The discrete problem of determining the presence and direction of edges is transformed into a continuous polynomial optimization problem (POP). By applying Karush-Kuhn-Tucker (KKT) conditions, the bilevel problem is collapsed into a single-level optimization task.
To solve this POP globally, Bloom utilizes the Lasserre hierarchy to relax the problem into a sequence of Semidefinite Programming (SDP) tasks. Unlike gradient descent, which can stall in local minima, SDPs can be solved using Interior Point Methods. These methods offer quadratic convergence and a theoretical path to the global optimum, ensuring the discovered graph is the best possible fit for the data.
3. Distributed and Scalable Architecture
Recognizing the computational cost of SDPs, the authors implement "correlative sparsity" and "term sparsity" to decompose large matrices into smaller, manageable blocks. This allows Bloom to scale to graphs with up to 100 nodes. Additionally, Bloom supports a distributed setting where clients share learned model parameters rather than raw data, enhancing privacy and reducing communication overhead.
Experimental Evaluation
The researchers evaluated Bloom against several baseline algorithms, including LINGAM, PC, GES, and Notears, using both synthetic and real-world datasets.
- Synthetic Datasets: Scale-free (SF) graphs with 5 to 100 nodes were used to test performance across linear and complex polynomial causal relationships.
- Real-World Data: The Sachs flow cytometry dataset, a gold standard in causal discovery, was used to map protein-signaling networks in human immune cells (11 nodes, 17 edges).
Key Results
- Accuracy: In linear experiments with 15 nodes, Bloom achieved a True Positive Rate (TPR) of 0.9412, outperforming GIES (0.9176) and Notears (0.8235).
- Real-World Performance: On the Sachs dataset, Bloom achieved a Structural Hamming Distance (SHD) of 5, a significant improvement over GIES, which recorded an SHD of 13.
- Convergence: Bloom reached optimal solutions in approximately 20 iterations using Interior Point Methods, whereas gradient-based methods often required hundreds of iterations without reaching the same accuracy.
- Robustness: The framework maintained high performance even under significant data noise (standard deviation up to 6.0).
Discussion and Conclusion
The primary contribution of Bloom is the shift from local, gradient-based search to a global search strategy rooted in polynomial optimization. By treating observational and interventional data as hierarchical components, Bloom avoids the pitfalls of simple data mixing.
Despite its strengths, Bloom faces challenges regarding computational complexity as the number of nodes increases, due to the growth of moment matrices in SDP relaxations. Future research will focus on further optimizing SDP solvers for larger biological networks and exploring advanced privacy-preserving techniques for distributed applications.
In summary, Bloom represents a significant step forward in causal discovery, providing a mathematically rigorous framework with strong convergence and optimality guarantees.
Citation: Chengbo Qiu and Kai Yang, "Interventional Causal Structure Discovery over Graphical Models with Convergence and Optimality Guarantees," Journal of LaTeX Class Files, Vol. 14, No. 8, August 2021 (arXiv:2408.04819v1).
Summary updated