Source-linked AI summary
High-dimensional consistency in score-based and hybrid structure learning
Preetam Nandy, Alain Hauser, Marloes H. Maathuis
TL;DR
Score-based and hybrid structure-learning methods lacked high-dimensional consistency guarantees, motivating a principled analysis of GES-based restrictions. The paper introduces adaptively restricted GES, proves consistency for GES and ARGES across several sparse settings, and reports favorable simulation comparisons with PC.
Problem
High-dimensional consistency had been established for constraint-based methods such as PC, but not for score-based methods or most hybrid methods.
Method
The paper develops adaptive GES restrictions that add current-CPDAG shields to CIG- or skeleton-based search spaces and uses a new independence-map characterization.
Results
GES and ARGES are proved consistent in sparse high-dimensional settings for Gaussian, linear SEM, and nonparanormal distributions, and simulations indicate they generally outperform PC.
Takeaways & Limitations
ARGES provides a consistent hybrid approach that can scale to large sparse graphs while retaining CPDAG outputs useful for applications such as causal-effect identification.
Takeaways & Limitations
The results rely on distributional and sparsity assumptions, including DAG-perfectness for the classical consistency result and specific sparse high-dimensional settings.
Abstract
from arXiv · showhide
Main approaches for learning Bayesian networks can be classified as constraint-based, score-based or hybrid methods. Although high-dimensional consistency results are available for constraint-based methods like the PC algorithm, such results have not been proved for score-based or hybrid methods, and most of the hybrid methods have not even shown to be consistent in the classical setting where the number of variables remains fixed and the sample size tends to infinity. In this paper, we show that consistency of hybrid methods based on greedy equivalence search (GES) can be achieved in the classical setting with adaptive restrictions on the search space that depend on the current state of the algorithm. Moreover, we prove consistency of GES and adaptively restricted GES (ARGES) in several sparse high-dimensional settings. ARGES scales well to sparse graphs with thousands of variables and our simulation study indicates that both GES and ARGES generally outperform the PC algorithm.
1. Introduction.
The paper addresses missing consistency results for score-based and hybrid structure-learning methods, proposing adaptive GES restrictions and proving consistency in classical and sparse high-dimensional settings.
- Motivation: Constraint-based methods such as PC have high-dimensional consistency results, whereas score-based and most hybrid methods lack comparable guarantees.Hybrid methods generally scale well, but their consistency results are lacking even in the classical setting.
- Motivation: Naively restricting GES to an estimated CIG or CPDAG-skeleton can be inconsistent, even when the true CPDAG lies within the restricted search space.The GES search path may need to leave these spaces during optimization.
- Contributions: ARGES adaptively expands the restricted search space by allowing shields of v-structures or unshielded triples in the current CPDAG.The restriction changes with the algorithm’s current state, rather than remaining fixed at the estimated CIG or skeleton.
- Contributions: The paper proves consistency of GES and ARGES in sparse high-dimensional settings for Gaussian, linear SEM, and nonparanormal distributions.The results connect constraint-based and score-based methods and motivate rank-correlation scoring for nonparanormal distributions.
- Evaluation: Simulations compare PC, GES, ARGES, and max-min hill-climbing, while an ARGES implementation is provided in the R-package pcalg.The paper reports finite-sample performance and runtime comparisons in sparse high-dimensional settings.
2. Preliminaries.
The preliminaries define the graph, Bayesian-network, independence, scoring, and GES concepts used to analyze structure learning from observational data.
- Graphical definitions: Graphs represent variables as nodes and relationships as directed, undirected, or partially directed edges, with acyclicity defining DAGs and PDAGs.The notation also specifies adjacency, parents, paths, descendants, and related graph concepts.
- Bayesian networks: A Bayesian network combines a DAG with conditional distributions for each node given its parents, thereby encoding conditional independence constraints.The distribution factorizes according to the DAG, and d-separation characterizes its encoded independencies.
- Independence structure: DAG-perfectness requires a DAG to encode exactly the distribution’s conditional independencies, including both the global Markov property and faithfulness.Such a DAG is called a perfect map of the distribution.
- Independence structure: Markov-equivalent DAGs share the same conditional independencies and are represented uniquely by a CPDAG.Markov equivalence is characterized by identical skeletons and v-structures.
- Greedy equivalence search: GES greedily optimizes a score over CPDAGs through forward edge additions followed by backward edge deletions.Each move changes one skeleton edge, although orientations of several edges may change; score-equivalent, decomposable, and consistent criteria are assumed.
3. Inconsistency of GES restricted to the CIG/CPDAG-skeleton.
Restricting GES to the true CIG or CPDAG-skeleton can prevent recovery of the correct CPDAG, demonstrating inconsistency of naive hybrid restrictions.
- Restricted search: Naive restricted GES permits an edge addition only when its endpoints are adjacent in the CIG or CPDAG-skeleton.The inconsistency example assumes these restricted graphs are estimated consistently, so the failure is not attributed to estimation error.
- Counterexample: The example’s data-generating DAG has edges X1 → X3, X2 → X3, X2 → X4, and X3 → X4, while its CIG and CPDAG-skeleton omit different edges.The CIG omits X1 − X4, and the CPDAG-skeleton additionally omits X1 − X2.
- Counterexample: In the linear Gaussian example, unrestricted GES converges to the true CPDAG, whereas RGES-CIG and RGES-skeleton converge to different outputs.These are large-sample-limit results under the BIC criterion.
- Broader implication: The same linear Gaussian SEM also demonstrates inconsistency for restricted hill-climbing DAG searches and related methods.The paper notes this includes CIG- and CPDAG-skeleton-restricted variants such as max-min hill-climbing.
4. Adaptively restricted greedy equivalence search (ARGES).
ARGES restricts GES edge additions using estimated graph structure and the algorithm’s current CPDAG, while adaptively retaining edges needed for consistency. Its consistency follows from a new independence-map characterization and extends to CIG- and skeleton-based variants.
- Consistency argument: Theorem 4.1 characterizes when a DAG is not an independence map through skeleton mismatches, v-structure discrepancies, or conditional-dependence discrepancies.This characterization supplies the basis for proving that admissible edge additions can repair independence-map violations.
- Adaptive restrictions: ARGES permits edge additions from an estimated CIG or CPDAG-skeleton and additionally allows shields of v-structures or unshielded triples in the current CPDAG.These adaptive restrictions modify the forward phase; the backward phase remains identical to GES.
- Algorithm: The forward phase sequentially adds one edge by selecting the score-minimizing admissible move, then terminates when no improving admissible move remains.The admissible moves depend on both the estimated restriction graph and the current CPDAG.
- ARGES variants: ARGES-skeleton uses a typically smaller skeleton-based graph than the CIG, making its base restriction stronger but its adaptive relaxation less restrictive.The two admissibility definitions therefore trade off the restrictiveness of their graph-based and adaptive conditions.
- Adaptive restrictions: ARGES allows an edge between two nonadjacent nodes when they are adjacent in the restriction graph or when the edge shields a current v-structure or unshielded triple.For ARGES-CIG, the restriction graph is an estimated CIG; for ARGES-skeleton, it is an estimated CPDAG-skeleton.
- Consistency argument: A new corollary ensures that non-independence-map states admit score-improving admissible additions, enabling ARGES consistency proofs for both CIG- and skeleton-based variants.The resulting consistency statements are given for ARGES-CIG and ARGES-skeleton.
5. High-dimensional consistency of GES and ARGES in the multivariate Gaussian setting.
The paper establishes high-dimensional consistency for GES and adaptively restricted GES under sparse multivariate Gaussian settings, using a connection between score improvements and conditional independence. It also characterizes conditions under which restricted forward searches recover the target CPDAG.
- Proof strategy: The proof constructs sound oracle versions of (AR)GES and shows that the sample algorithm matches an oracle version with probability approaching one.The oracle argument uses an ℓ0-penalized log-likelihood score and a suitably chosen penalty sequence.
- Score-based and constraint-based methods: A penalized likelihood edge addition improves the score exactly when the corresponding sample partial correlation is nonzero, linking GES operations to conditional independence tests.This connection supplies a key ingredient for the high-dimensional consistency proof.
- Assumptions and scope: The required assumptions retain a strong-faithfulness condition because the authors cannot guarantee that greedy search reaches the global optimum without it.The forward-phase output can depend on the absolute values of nonzero partial correlations, complicating characterization of distributions satisfying the assumptions.
- Structural guarantees: For forest CPDAG skeletons, the oracle forward phase of (AR)GES recovers the true CPDAG under the stated assumptions and δ_n restrictions.The result also connects GES's oracle forward phase to greedy learning of optimal polytrees using conditional mutual information.
6. High-dimensional consistency of GES and ARGES for linear structural equation models.
The paper extends high-dimensional consistency of GES and ARGES from Gaussian models to linear structural equation models with sub-Gaussian errors. The extension uses Gaussian-score arguments together with assumptions controlling covariance submatrices and sparsity.
- Consistency for linear SEMs: GES and ARGES are shown high-dimensionally consistent for DAG-perfect linear SEMs with sub-Gaussian error variables.The theorem applies the same ARGES-CIG, ARGES-skeleton, and GES outputs with a penalized Gaussian log-likelihood score.
- Assumptions: The extension assumes a DAG-perfect linear SEM and covariance-submatrix conditions involving spectral norms, sparsity, and degree-growth quantities.These assumptions supplement the conditions used for the multivariate Gaussian setting.
- Proof connection: Conditional independence in a DAG-perfect linear SEM is equivalent to zero partial correlation, regardless of the error distribution.This equivalence lets the Gaussian oracle-score arguments support linear SEMs with non-Gaussian errors.
- Dimensionality: The results allow an ultra-high-dimensional regime with p_n = O(exp(n^a)) when the covariance inverse norm grows at a controlled rate satisfying an additional restriction.The stated restriction is a + 4f < b2 − 2 max(d1, d2), with 0 ≤ a < 1 and 0 ≤ f < 1/4.
7. High-dimensional consistency of GES and ARGES in the nonparanormal setting.
The paper develops a rank-based scoring criterion and proves high-dimensional consistency of GES and ARGES for sparse nonparanormal distributions. The construction leverages invariance of conditional independence and rank correlations under monotone marginal transformations.
- Relation to prior methods: The nonparanormal theory is presented alongside Rank PC, whose high-dimensional consistency motivated the rank-based GES and ARGES construction.The paper then compares finite-sample performance and computational efficiency with PC and MMHC.
- Underlying connection: Monotone marginal transformations preserve the relevant conditional-independence relations, while sample rank correlations remain identical across the transformed and latent Gaussian variables.These properties connect nonparanormal structure learning to partial correlations of the latent Gaussian representation.
- Rank-based scoring criterion: The rank-based score is motivated by the Gaussian partial-correlation argument and uses rank correlation estimates to construct edge-wise score differences.The resulting score is well-defined and invariant to the order in which directed edges are added.
- Score properties: The proposed score assigns equal values to Markov-equivalent DAGs, supporting optimization over CPDAG equivalence classes.The paper also requires scoring criteria to be score equivalent, decomposable, and consistent for GES.
- Consistency for nonparanormal distributions: GES and ARGES are proved consistent for DAG-perfect nonparanormal distributions under strengthened sparsity, correlation, and covariance assumptions.The result applies to ARGES-CIG, ARGES-skeleton, and GES using the rank-based score ˜S_λn.
8. Simulations.
The simulations compare GES, ARGES variants, MMHC, and PC on CPDAG estimation quality and runtime across high-dimensional and decreasing-sparsity settings.
- 8.1. Simulation settings: The experiments generate random weighted DAGs and Gaussian samples, estimate CPDAGs, and compare methods using averaged ROC curves over tuning parameters and repetitions.ARGES-CIG uses LASSO neighborhood selection, whereas ARGES-skeleton uses MMPC; GES and MMHC use an ℓ0-penalized likelihood score.
- 8.3. Results: As n and p_n increase together, averaged ROC curves improve, supporting the high-dimensional consistency theory of (AR)GES and PC.The ROC curves evaluate skeleton and directed-part recovery across simulation settings.
- 8.3. Results: PC < MMHC < (A)RGES-skeleton < (A)RGES-CIG ≈ GES < ARGES-CIG* in estimation performance.ARGES-CIG* performs best but requires the true CIG, making it infeasible in practice.
- 8.3. Results: GES does not scale well to large graphs, while (AR)GES and PC have somewhat similar runtimes, excluding (AR)GES preprocessing costs.MMHC is substantially slower than (A)RGES-skeleton despite using the same estimated CPDAG-skeleton.
- 8.4. Simulation with decreasing sparsity level: In the most adverse decreasing-sparsity setting, ARGES-CIG outperforms GES, whereas both methods perform equally well in the first three settings.Adaptive-LASSO CIG estimation improves the performance gain as sparsity decreases, despite producing a subgraph of the LASSO-based estimated CIG.
9. Discussion.
The paper establishes consistency for GES and ARGES under classical and several sparse high-dimensional settings, while identifying computational trade-offs and assumptions. It also connects score-based and constraint-based methods and reports that GES generally outperforms PC in estimation quality.
- Consistency and computation: GES and ARGES are consistent in sparse high-dimensional settings, while ARGES can achieve similar performance to GES in less time when its estimated CIG is sufficiently dense.ARGES requires an additional tuning parameter, and restricted search can sometimes improve estimation performance.
- Output guarantees: GES and ARGES provide CPDAG outputs, unlike the sample PC algorithm, which often produces partially directed graphs that are not CPDAGs.This output guarantee matters for applications including joint-IDA and the generalized adjustment criterion.
- Connection to constraint-based methods: GES and PC are closely related in Gaussian models because both use partial-correlation-based conditional independence information, but GES integrates skeleton learning and edge orientation.The authors suggest this connection can motivate score-based and hybrid methods based on broader conditional independence tests.
- Empirical comparison: GES outperforms PC in estimation quality in the Gaussian setting, possibly because it considers the skeleton and edge orientations simultaneously.The sequential PC procedure first estimates the skeleton and then orients edges.
- Proof assumptions: The high-dimensional consistency proofs require an assumption on the growth of oracle versions of GES and ARGES, unlike the corresponding PC result.The paper gives structural conditions under which this assumption holds and connects GES with the Chow-Liu algorithm to derive them.
- Classical consistency: The classical consistency result requires only that the joint distribution be DAG-perfect, rather than imposing a specific distributional family.The result applies even to discrete distributions; future work concerns ARGES for minimal independence maps under weaker assumptions.