TL;DR
This paper introduces ARCS, a novel method for learning Bayesian Networks (BNs) by optimizing a "regularized Cholesky score" over node orderings. ARCS combines global simulated annealing with a fast proximal gradient algorithm, significantly improving accuracy over existing methods for both observational and experimental data.
What Problem Does This Paper Address?
Learning the structure of Bayesian Networks (BNs) is crucial for understanding complex relationships between variables. Traditional methods often struggle with the high dimensionality and combinatorial complexity of the search space. Specifically, score-based methods that search over possible graph structures can be computationally prohibitive. While searching over "topological sorts" (ordered sequences of nodes) offers a more manageable search space and automatically enforces the acyclicity constraint of Directed Acyclic Graphs (DAGs), efficiently exploring this space and finding optimal structures remains challenging. Existing methods often get trapped in local optima or require computationally expensive steps. This paper aims to address these limitations by proposing a more efficient and accurate order-based search strategy.
Methods
The core of the proposed method, ARCS (Annealing on Regularized Cholesky Score), lies in its novel scoring function and optimization strategy.
- Regularized Cholesky Score: The authors reformulate the problem of learning Gaussian BN structures as optimizing a "regularized Cholesky score." This score is derived from the Gaussian DAG likelihood and is connected to the problem of sparse Cholesky factorization. By introducing a concave penalty (Minimax Concave Penalty - MCP) to the Cholesky loss, the method encourages sparsity in the network structure, effectively breaking the symmetry that makes different topological sorts yield the same likelihood.
- Order-Based Search: Instead of searching directly over DAGs, ARCS searches over the space of topological sorts (permutations of nodes). This significantly reduces the search space and guarantees acyclicity.
- Global Optimization (Simulated Annealing): To explore the vast permutation space and avoid local optima, ARCS employs simulated annealing. This allows for a global search over possible node orderings.
- Efficient Score Computation (Proximal Gradient): For each candidate permutation, computing its score involves optimizing a continuous problem over a lower triangular matrix. This is efficiently handled by a proximal gradient algorithm, which is well-suited for optimizing functions with both smooth and non-smooth components.
- Data-Driven Parameter Selection: A Bayesian Information Criterion (BIC) is used to select the tuning parameters for the MCP penalty function, providing a principled way to adapt the regularization to the data.
- Structure Refinement: After the annealing process, a constraint-based structure refinement step is applied to prune false positive edges, further improving accuracy.
Datasets
The paper evaluates ARCS on both simulated and real-world datasets.
- Simulated Data: Data was generated from synthetic DAG structures and real-world networks (e.g., Asia, Sachs, Alarm, Barley) with varying numbers of variables ($p$) and edges ($s_0$), and different sample sizes ($n$). Both high-dimensional ($n < p$) and low-dimensional ($n > p$) settings were considered.
- Real-World Networks: The authors used publicly available Bayesian networks from the bnlearn repository, including networks like Asia, Sachs, Alarm, Barley, Hailfinder, Andes, Hepar2, Win95pts, and Pigs. Some networks were duplicated to increase their size.
Key Insights and Ideas
- Order-Based Search as Sparse Cholesky Factorization: The paper establishes a compelling link between learning Gaussian BN structures and the sparse Cholesky factorization problem. This provides a new perspective and allows leveraging techniques from numerical linear algebra.
- Global Search + Local Optimization Synergy: ARCS effectively combines global search (simulated annealing over permutations) with efficient local optimization (proximal gradient for score computation). This hybrid approach is key to its success.
- Concave Penalties for Sparsity: The use of Minimax Concave Penalty (MCP) is shown to be more effective than L1 penalties for promoting sparsity and achieving higher accuracy in BN structure learning.
- Experimental Interventions Improve Accuracy: For learning causal structures, experimental interventions significantly improve accuracy, leading to lower SHDs and a reduced proportion of reversed edges compared to observational data alone.
Key Results
- Substantial Accuracy Improvements: ARCS consistently outperformed existing state-of-the-art methods (CD, GES, HC, PC, MMHC, GA) across various datasets and settings, achieving significantly lower Structural Hamming Distances (SHD) and higher Jaccard Indices (JI). For instance, ARCS(GES) achieved SHD reductions of up to 40% on some networks.
- Efficiency: The proximal gradient algorithm allows for efficient computation of the RC score, making the overall ARCS algorithm practical for larger networks.
- Improved Parameter Selection: The BIC-based tuning parameter selection method proved effective, leading to better performance compared to methods with less principled parameter choices.
- Experimental Data Advantage: ARCS demonstrated a significant advantage when using experimental intervention data, leading to more accurate causal structure recovery.
Limitations and Future Work
- Computational Cost for Very Large Networks: While ARCS is efficient, the paper notes that for extremely large networks (e.g., $p > 50$), the annealing process might require more time to thoroughly search the permutation space. In such cases, initializing ARCS with estimates from other local methods and a low temperature is recommended.
- Extension to Discrete BNs: The current framework is for Gaussian BNs. The authors suggest that extending ARCS to discrete BNs is a promising future direction, potentially by adapting the proximal gradient step for multinomial likelihoods.
- Theoretical Properties: Future work could focus on establishing theoretical properties of the method, such as the consistency of the regularized Cholesky score and the convergence guarantees of the ARCS algorithm, especially when initialized with a good guess.
- Alternative Operators for Annealing: Investigating different operators for proposing new permutations in the simulated annealing step could further enhance the search process.
Summary updated