Local Fisher Information Enables Sparse Causal Discovery
Abstract
Sparse causal discovery calls for methods that exploit graph structure without estimating high-dimensional densities. We introduce Fisher Information Completion Search (FiCS), a source-first algorithm for additive noise models that uses one local Fisher score for both ordering and parent selection. Under regularity and nonconstant-parent conditions, we prove that a node's local Fisher information equals the noise Fisher information exactly when the conditioning set contains all parents, provided that it contains no descendants. This Fisher parent completion identifies the parent set as the unique minimal Fisher completion. With a maximum conditioning set size q at least the maximum indegree d, population FiCS queries marginals of at most q+1 variables and recovers the true directed acyclic graph under a positive ordering margin. Bounded conditioning also has a population advantage: reducing q toward d cannot decrease, and can strictly increase, the ordering margin. A growing non-Gaussian family separates local Fisher selection from conditional-variance and leaf-first Fisher ordering. For the regularized kernel Stein estimator, we establish high-dimensional DAG consistency under q{1+log(p/q)}+log p=o(n), uniform Fisher separation, local approximation, and compatible ridge and parent penalty parameters. Experiments show the strongest gains when n is small relative to p, quantify the effect of the conditioning size, and demonstrate competitive reference-graph recovery on three real-data benchmarks.
Related
- Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models
- Discrete Score Matching Enables Causal Discovery from Count Data
- On the discrete Fisher information
- A Sharp Fisher-Information Inequality for Boolean Pairs: Proof of the Amari--Kobayashi Conjecture
- Conditional Fisher-Information Central Limit Theorems under Log-Concavity with Information-Theoretic Consequences
BibTeX
@misc{kang2026local,
title = {{Local Fisher Information Enables Sparse Causal Discovery}},
author = {Byeongguk Kang and Donghyeon Lee and Euijong Song and Gunwoong Park},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04291},
eprint = {2610.04291},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04291},
}
RIS
TY - UNPB
TI - Local Fisher Information Enables Sparse Causal Discovery
AU - Byeongguk Kang
AU - Donghyeon Lee
AU - Euijong Song
AU - Gunwoong Park
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2610.04291
UR - https://arxiv.org/abs/2610.04291
AB - Sparse causal discovery calls for methods that exploit graph structure without estimating high-dimensional densities. We introduce Fisher Information Completion Search (FiCS), a source-first algorithm for additive noise models that uses one local Fisher score for both ordering and parent selection. Under regularity and nonconstant-parent conditions, we prove that a node's local Fisher information equals the noise Fisher information exactly when the conditioning set contains all parents, provided that it contains no descendants. This Fisher parent completion identifies the parent set as the unique minimal Fisher completion. With a maximum conditioning set size q at least the maximum indegree d, population FiCS queries marginals of at most q+1 variables and recovers the true directed acyclic graph under a positive ordering margin. Bounded conditioning also has a population advantage: reducing q toward d cannot decrease, and can strictly increase, the ordering margin. A growing non-Gaussian family separates local Fisher selection from conditional-variance and leaf-first Fisher ordering. For the regularized kernel Stein estimator, we establish high-dimensional DAG consistency under q{1+log(p/q)}+log p=o(n), uniform Fisher separation, local approximation, and compatible ridge and parent penalty parameters. Experiments show the strongest gains when n is small relative to p, quantify the effect of the conditioning size, and demonstrate competitive reference-graph recovery on three real-data benchmarks.
ER -