Less Greedy Equivalence Search

• URL: http://arxiv.org/abs/2506.22331v2
• Date: Thu, 06 Nov 2025 21:42:42 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.
• Score: 52.818153111470394
• 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 knowledge, and can correct this knowledge when contradicted by data. Finally, LGES can use interventional data to refine the learned observational equivalence class. We prove that LGES recovers the true equivalence class in the sample limit, even with misspecified knowledge. Experiments demonstrate that LGES outperforms GES and other baselines in speed, accuracy, and robustness to misspecified knowledge. Our code is available at https://github.com/CausalAILab/lges.

Related papers

• AlgoVeri: An Aligned Benchmark for Verified Code Generation on Classical Algorithms [54.99368693313797]
  Existing benchmarks test only individual languages/tools, so the performance numbers are not directly comparable.<n>We address this gap with AlgoVeri, a benchmark that evaluates vericoding of $77$ classical algorithms in Dafny, Verus, and Lean.
  arXiv  Detail & Related papers  (2026-02-10T06:58:26Z)
• Enhancing Node-Level Graph Domain Adaptation by Alleviating Local Dependency [8.229138664380324]
  Transfering knowledge effectively from one graph to another remains a critical challenge.<n>In this paper, we show that conditional shift can be observed only if there exists local dependencies among node features.<n>We propose to improve GDA by decorrelating node features, which can be specifically implemented through decorrelated GCN layers and graph transformer layers.
  arXiv  Detail & Related papers  (2025-12-15T10:00:25Z)
• Extremely Greedy Equivalence Search [2.486161976966064]
  We propose eXtremely Greedy Equivalent Search (XGES) to improve the search strategy of Greedy Equivalence Search (GES)<n>XGES favors deleting edges early in the search over inserting edges, which reduces the possibility of the search ending in local optima.<n>XGES consistently outperforms GES in recovering the correct graphs, and it is 10 times faster.
  arXiv  Detail & Related papers  (2025-02-26T20:45:04Z)
• 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)
• Analyzing Data-Centric Properties for Contrastive Learning on Graphs [32.69353929886551]
  We investigate how do graph SSL methods, such as contrastive learning (CL), work well? Our work rigorously contextualizes, both empirically and theoretically, the effects of data-centric properties on augmentation strategies and learning paradigms for graph SSL.
  arXiv  Detail & Related papers  (2022-08-04T17:58:37Z)
• 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)
• Direction Matters: On the Implicit Bias of Stochastic Gradient Descent with Moderate Learning Rate [105.62979485062756]
  This paper attempts to characterize the particular regularization effect of SGD in the moderate learning rate regime. We show that SGD converges along the large eigenvalue directions of the data matrix, while GD goes after the small eigenvalue directions.
  arXiv  Detail & Related papers  (2020-11-04T21:07:52Z)
• Combining Label Propagation and Simple Models Out-performs Graph Neural Networks [52.121819834353865]
  We show that for many standard transductive node classification benchmarks, we can exceed or match the performance of state-of-the-art GNNs. We call this overall procedure Correct and Smooth (C&S) Our approach exceeds or nearly matches the performance of state-of-the-art GNNs on a wide variety of benchmarks.
  arXiv  Detail & Related papers  (2020-10-27T02:10:52Z)
• Generalized Zero-Shot Learning via VAE-Conditioned Generative Flow [83.27681781274406]
  Generalized zero-shot learning aims to recognize both seen and unseen classes by transferring knowledge from semantic descriptions to visual representations. Recent generative methods formulate GZSL as a missing data problem, which mainly adopts GANs or VAEs to generate visual features for unseen classes. We propose a conditional version of generative flows for GZSL, i.e., VAE-Conditioned Generative Flow (VAE-cFlow)
  arXiv  Detail & Related papers  (2020-09-01T09:12:31Z)
• Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case [93.37576644429578]
  Graph neural networks (GNNs) have made great progress recently on learning from graph-structured data in practice. We provide a theoretically-grounded generalizability analysis of GNNs with one hidden layer for both regression and binary classification problems.
  arXiv  Detail & Related papers  (2020-06-25T00:45:52Z)

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.