Less Greedy Equivalence Search

• URL: http://arxiv.org/abs/2506.22331v1
• Date: Fri, 27 Jun 2025 15:39:48 GMT
• Title: Less Greedy Equivalence Search
• Authors: Adiba Ejaz, Elias Bareinboim,
• Abstract summary: Greedy Equivalence Search (GES) is a score-based algorithm for causal discovery from observational data.<n>We develop Less Greedy Equivalence Search (LGES), a variant of GES that retains its theoretical guarantees while partially addressing these limitations.<n>We prove that LGES recovers the true equivalence class in the sample limit from observational and interventional data, even with misspecified prior assumptions.
• Score: 52.30805873759552
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Greedy Equivalence Search (GES) is a classic score-based algorithm for causal discovery from observational data. In the sample limit, it recovers the Markov equivalence class of graphs that describe the data. Still, it faces two challenges in practice: computational cost and finite-sample accuracy. In this paper, we develop Less Greedy Equivalence Search (LGES), a variant of GES that retains its theoretical guarantees while partially addressing these limitations. LGES modifies the greedy step: rather than always applying the highest-scoring insertion, it avoids edge insertions between variables for which the score implies some conditional independence. This more targeted search yields up to a \(10\)-fold speed-up and a substantial reduction in structural error relative to GES. Moreover, LGES can guide the search using prior assumptions, while correcting these assumptions when contradicted by the data. Finally, LGES can exploit interventional data to refine the learned observational equivalence class. We prove that LGES recovers the true equivalence class in the sample limit from observational and interventional data, even with misspecified prior assumptions. Experiments demonstrate that LGES outperforms GES and other baselines in speed, accuracy, and robustness to misspecified assumptions. Our code is available at https://github.com/CausalAILab/lges.

Related papers

• Your Assumed DAG is Wrong and Here's How To Deal With It [4.262342157729123]
  We propose an efficient, gradient-based optimization method that provides bounds for causal queries over a collection of causal graphs.<n>Our approach aims at providing an easy-to-use and widely applicable rebuttal to the valid critique of What if your assumed DAG is wrong?'
  arXiv  Detail & Related papers  (2025-02-24T10:31:12Z)
• New metrics and search algorithms for weighted causal DAGs [7.424262881242935]
  We study causal graph discovery via adaptive interventions with node-dependent costs. We define a new benchmark that captures the worst-case interventional cost for any search algorithm. We provide adaptive search algorithms that achieve logarithmic approximations under various settings.
  arXiv  Detail & Related papers  (2023-05-08T03:48:37Z)
• Boosting Differentiable Causal Discovery via Adaptive Sample Reweighting [62.23057729112182]
  Differentiable score-based causal discovery methods learn a directed acyclic graph from observational data. We propose a model-agnostic framework to boost causal discovery performance by dynamically learning the adaptive weights for the Reweighted Score function, ReScore.
  arXiv  Detail & Related papers  (2023-03-06T14:49:59Z)
• Parametric Classification for Generalized Category Discovery: A Baseline Study [70.73212959385387]
  Generalized Category Discovery (GCD) aims to discover novel categories in unlabelled datasets using knowledge learned from labelled samples. We investigate the failure of parametric classifiers, verify the effectiveness of previous design choices when high-quality supervision is available, and identify unreliable pseudo-labels as a key problem. We propose a simple yet effective parametric classification method that benefits from entropy regularisation, achieves state-of-the-art performance on multiple GCD benchmarks and shows strong robustness to unknown class numbers.
  arXiv  Detail & Related papers  (2022-11-21T18:47:11Z)
• Tearing Apart NOTEARS: Controlling the Graph Prediction via Variance Manipulation [17.103787431518683]
  We show that we can control the resulting graph with our targeted variance attacks. In particular, we show that we can control the resulting graph with our targeted variance attacks.
  arXiv  Detail & Related papers  (2022-06-14T22:53:05Z)
• On the Eigenvalues of Global Covariance Pooling for Fine-grained Visual Recognition [65.67315418971688]
  We show that truncating small eigenvalues of the Global Covariance Pooling (GCP) can attain smoother gradient. On fine-grained datasets, truncating the small eigenvalues would make the model fail to converge. Inspired by this observation, we propose a network branch dedicated to magnifying the importance of small eigenvalues.
  arXiv  Detail & Related papers  (2022-05-26T11:41:36Z)
• Causal Structure Learning with Greedy Unconditional Equivalence Search [0.26249027950824505]
  We consider the problem of characterizing directed acyclic graph (DAG) models up to unconditional equivalence. We introduce a hybrid algorithm for learning DAG models from observational data, called Greedy Unconditional Equivalence Search (GUES)
  arXiv  Detail & Related papers  (2022-03-01T15:04:49Z)
• BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery [97.79015388276483]
  A structural equation model (SEM) is an effective framework to reason over causal relationships represented via a directed acyclic graph (DAG) Recent advances enabled effective maximum-likelihood point estimation of DAGs from observational data. We propose BCD Nets, a variational framework for estimating a distribution over DAGs characterizing a linear-Gaussian SEM.
  arXiv  Detail & Related papers  (2021-12-06T03:35:21Z)
• Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning [57.88785630755165]
  Empirical risk minimization (ERM) is the workhorse of machine learning, but its model-agnostic guarantees can fail when we use adaptively collected data. We study a generic importance sampling weighted ERM algorithm for using adaptively collected data to minimize the average of a loss function over a hypothesis class. For policy learning, we provide rate-optimal regret guarantees that close an open gap in the existing literature whenever exploration decays to zero.
  arXiv  Detail & Related papers  (2021-06-03T09:50:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.