Embracing Discrete Search: A Reasonable Approach to Causal Structure Learning
- URL: http://arxiv.org/abs/2510.04970v1
- Date: Mon, 06 Oct 2025 16:04:53 GMT
- Title: Embracing Discrete Search: A Reasonable Approach to Causal Structure Learning
- Authors: Marcel Wienöbst, Leonard Henckel, Sebastian Weichwald,
- Abstract summary: We present FLOP, a score-based causal discovery algorithm for linear models.<n>It pairs fast parent selection with iterative Cholesky-based score updates, cutting run-times over prior algorithms.<n>The resulting structures are highly accurate across benchmarks, with near-perfect recovery in standard settings.
- Score: 4.838245844232486
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present FLOP (Fast Learning of Order and Parents), a score-based causal discovery algorithm for linear models. It pairs fast parent selection with iterative Cholesky-based score updates, cutting run-times over prior algorithms. This makes it feasible to fully embrace discrete search, enabling iterated local search with principled order initialization to find graphs with scores at or close to the global optimum. The resulting structures are highly accurate across benchmarks, with near-perfect recovery in standard settings. This performance calls for revisiting discrete search over graphs as a reasonable approach to causal discovery.
Related papers
- Score-matching-based Structure Learning for Temporal Data on Networks [17.166362605356074]
Causal discovery is a crucial initial step in establishing causality from empirical data and background knowledge.<n>Current score-matching-based algorithms are primarily designed to analyze independent and identically distributed (i.i.d.) data.<n>We have developed a new parent-finding subroutine for leaf nodes in DAGs, significantly accelerating the most time-consuming part of the process: the pruning step.
arXiv Detail & Related papers (2024-12-10T12:36:35Z) - A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near
Neighbor Graph [51.880164098926166]
Graph-based algorithms have demonstrated state-of-the-art performance in the nearest neighbor search (NN-Search) problem.
There exists a practice-to-theory gap in the graph-based NN-Search algorithms.
We present theoretical guarantees of solving NN-Search via greedy search on ANN-Graph for low dimensional and dense vectors.
arXiv Detail & Related papers (2023-03-10T21:18:34Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
We propose a bi-level optimization approach for learning the optimal graph structure.
We also explore a low-rank approximation model for further reducing the time complexity.
arXiv Detail & Related papers (2022-05-06T03:37:00Z) - Score matching enables causal discovery of nonlinear additive noise
models [63.93669924730725]
We show how to design a new generation of scalable causal discovery methods.
We propose a new efficient method for approximating the score's Jacobian, enabling to recover the causal graph.
arXiv Detail & Related papers (2022-03-08T21:34:46Z) - Reinforcement Learning Based Query Vertex Ordering Model for Subgraph
Matching [58.39970828272366]
Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G.
matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms.
In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
arXiv Detail & Related papers (2022-01-25T00:10:03Z) - Deep Probabilistic Graph Matching [72.6690550634166]
We propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints.
The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k) and it outperforms all previous state-of-the-arts on all benchmarks.
arXiv Detail & Related papers (2022-01-05T13:37:27Z) - Effective and efficient structure learning with pruning and model
averaging strategies [9.023722579074734]
This paper describes an approximate BN structure learning algorithm that combines two novel strategies with hill-climbing search.
The algorithm starts by pruning the search space graphs, where the pruning strategy can be viewed as an aggressive version of the pruning strategies.
It then performs model averaging in the hill-climbing search process and moves to the neighbouring graph that maximises the objective function.
arXiv Detail & Related papers (2021-12-01T10:35:34Z) - Mathematical Models for Local Sensing Hashes [7.400475825464313]
We show that approximated index structures offer a good opportunity to accelerate the neighbor search for clustering and outlier detection.
We indicate directions to mathematically model the properties of local sensing hashes.
arXiv Detail & Related papers (2021-11-16T10:40:55Z) - Towards a Model for LSH [7.400475825464313]
Clustering and outlier detection algorithms are becoming increasingly time-consuming.
We show how approximated index structures offer a good opportunity to accelerate the neighbor search for clustering and outlier detection.
arXiv Detail & Related papers (2021-05-11T15:39:55Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
This paper investigates the classical integer least-squares problem which estimates signals integer from linear models.
The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning.
We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
arXiv Detail & Related papers (2021-01-07T08:00:02Z)
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.