Local Fisher Information Enables Sparse Causal Discovery

Byeongguk Kang; Donghyeon Lee; Euijong Song; Gunwoong Park

stat.MLOct 3, 2026

Local Fisher Information Enables Sparse Causal Discovery

Authors: Byeongguk Kang, Donghyeon Lee, Euijong Song, Gunwoong Park

Organizations: Interdisciplinary Program in Artificial Intelligence Seoul National University, Korea · Department of Statistics Seoul National University, Korea · Institute for Data Innovation in Science Seoul National University, Korea

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.

Figures & tables

Figure 1: Fisher parent completion. Black curves show the conditional density of

X_{i}

given

X_{T}

, while gray curves show translated noise densities

p_{\varepsilon_{i}}(x_{i}-m)

for possible values of

m=f_{i}(X_{\mathrm{Pa}(i)})

. Parent omission averages over multiple translations, giving

I_{i}(T)<I_{i}^{\varepsilon}

(left); parent completion leaves a single translation, giving

I_{i}(T)=I_{i}^{\varepsilon}

(right). Solid and dashed black curves denote the conditional density before and after a small location shift

\delta

Panel of Figure 2 — Figure 2: Mean graph-recovery F1 versus sample size for $p=50$ , $100$ , and $200$ from left to right; error bars indicate one standard deviation.

Figure 3: Mean ordering accuracy (left) and graph-recovery F1 (right) versus dimension at

n=100

Method	$A_{\mathrm{top}}\uparrow$	F1 $\uparrow$	SHD $\downarrow$	$A_{\mathrm{top}}\uparrow$	F1 $\uparrow$	SHD $\downarrow$	$A_{\mathrm{top}}\uparrow$	F1 $\uparrow$	SHD $\downarrow$
	Danube			Sachs			CausalRivers
FiCS	1.000	0.452	17	0.529	0.538	11	0.975 (0.076)	0.563 (0.165)	4.53 (1.63)
CaPS	0.909	0.351	36	0.529	0.500	11	0.733 (0.314)	0.408 (0.166)	6.03 (1.43)
SCORE	1.000	0.400	33	0.529	0.444	12	0.717 (0.292)	0.401 (0.175)	6.20 (1.40)
NoGAM	0.727	0.225	52	0.529	0.452	14	0.742 (0.304)	0.416 (0.188)	6.83 (1.66)
DAGMA	–	0.000	11	–	0.000	17	–	0.286 (0.337)	3.53 (1.25)

Table 1: Reference-graph recovery on Danube (

n=500,p=12

), Sachs (

n=853,p=11

), and CausalRivers (

n=500,p=5

). Parentheses give SD over 30 subgraphs. Bold marks the best reported mean per metric; – denotes no separate ordering stage.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Method	Candidate 1	Candidate 2	Candidate 3	Candidate 4
FiCS $(u,r,c)$	$(1.5,.5,.2)$	$(.75,.5,.2)$	$(1.5,.1,.2)$	$(1.5,.5,.8)$
CaPS $(\lambda_{1},\lambda_{2})$	$(50,50)$	$(2,50)$	$(2,25)$	$(5,50)$
SCORE $(\eta,\xi)$	$(.001,.001)$	$(.001,.05)$	$(.01,.001)$	$(.01,.05)$
NoGAM $(\alpha,\gamma)$	$(.01,.1)$	$(.001,.1)$	$(.1,.1)$	$(.01,1)$
DAGMA $(\lambda_{1},t)$	$(.02,.3)$	$(.02,.1)$	$(.005,.3)$	$(.005,.1)$

Appendix

Table 2: Hyperparameter candidates evaluated on the independent synthetic tuning datasets.

$p$	$n$	Numerical failures
50	50	1
100	50	22
100	100	5
200	50	28
200	100	19
200	200	4

Appendix

Table 3: CaPS numerical failures among 30 attempts per setting in Figure 2 . Only settings with a recorded numerical error are listed.

$p$	$n$	FiCS	CaPS	SCORE	NoGAM	DAGMA
50	200	0.45	0.37	0.30	0.64	5.61
50	500	2.84	1.90	0.51	1.39	13.48
100	200	3.65	16.72	1.15	2.72	14.52
100	500	23.18	8.77	1.91	5.55	42.07
200	200	58.75	1025.06 †	11.85	23.27	173.34
200	500	307.32	630.60	20.36	50.09	239.59

Appendix

Table 4: Wall-clock fitting time (minutes) on three paired graph–sample inputs per setting. Entries are medians of three completed fits, except CaPS at

(p,n)=(200,200)

. Its marked value is the time of the single completed fit (1/3), not a median.

Panel of Figure 4 — Figure 4: Sensitivity to the data-generating model. Mean F1 and one-SD error bars over 20 DAGs per condition, at $p=50,n=200$ . Each panel changes one factor from the ER3, joint-GP, unit-Gaussian reference condition. Horizontal offsets separate methods within each category.

Panel of Figure 5 — Figure 5: Effect of the linear-mechanism proportion. Mean and one-SD error bars over all 20 DAGs per condition, at $p=50,n=200$ . Increasing $\alpha$ replaces nonlinear GP mechanisms with linear ones; $\alpha=0.5$ matches the main generator. All methods retain their fixed synthetic settings.

		Danube		Sachs		CausalRivers
Parameter	Value	F1 $\uparrow$	SHD $\downarrow$	F1 $\uparrow$	SHD $\downarrow$	F1 $\uparrow$	SHD $\downarrow$
Common configuration	–	0.452	17	0.538	11	0.563	4.53
Bandwidth multiplier $u$	0.25	0.467	16	0.429	12	0.548	4.77
	1.0	0.467	16	0.417	13	0.520	4.93
Ridge multiplier $r$	0.25	0.500	16	0.444	14	0.554	4.63
	0.5	0.452	17	0.500	13	0.551	4.67

Appendix

Table 5: Sensitivity to bandwidth multiplier, ridge multiplier, and subset size on all three datasets. The common row uses

(u,r,c)=(0.5,1.0,0.0003)

and

q=\min\{2,p-1\}

. Each other row changes only its named parameter. CausalRivers values are means over the same 30 subnetworks.

$c$	F1 $\uparrow$	SHD $\downarrow$	Edges	F1 $\uparrow$	SHD $\downarrow$	Edges	F1 $\uparrow$	SHD $\downarrow$	Edges
	Danube			Sachs			CausalRivers
0.0001	0.438	18	21	0.500	11	11	0.567	4.57	6.80
0.0003	0.452	17	20	0.538	11	9	0.563	4.53	6.63
0.0005	0.452	17	20	0.538	11	9	0.534	4.67	6.37
0.001	0.308	18	15	0.538	11	9	0.514	4.73	6.17
0.002	0.308	18	15	0.560	10	8	0.510	4.77	6.13

Appendix

Table 6: Sensitivity to the parent penalty multiplier

c

\lambda=c\sqrt{\log(p)/n}

. Bandwidth and ridge multipliers remain

0.5

and

1.0

, respectively, and

q=\min\{2,p-1\}

in both stages. Bold

c

identifies the main-table setting. Edges is the number of selected edges; CausalRivers entries are means over the same 30 subnetworks.

	Population $A_{\mathrm{top}}$			$n=100$ $A_{\mathrm{top}}$
Generator	FiCS	VarSort	$R^{2}$ Sort	FiCS	VarSort	$R^{2}$ Sort
50–50	0.482	0.282	0.324	0.565	0.520	0.359
DaO	0.320	0.114	0.535	0.353	0.293	0.543
IPA	0.478	0.457	0.475	0.510	0.476	0.481
UUMC	0.465	0.468	0.492	0.493	0.471	0.482
iSCM	0.499	0.487	0.468	0.526	0.510	0.482

Appendix

Table 7: Mean ordering accuracy

A_{\mathrm{top}}

across six linear Gaussian generator regimes (

p=20

; 30 graphs per regime and setting). Population criteria use exact SCM covariances; finite-sample criteria use

n=100

. Higher is better; bold marks the best method within each regime and setting.

Causal Discovery

Causal discovery infers cause-and-effect structures from observational and interventional data, distinguishing causal relationships from correlation.

See all 220 papers

The Statistical Cost of Causal Discovery with Feedback
Sep 28, 2026Sunmin Oh, Seungsu Han, Gunwoong ParkSample Complexity Causal Discovery
Department of Statistics; Institute for Data Innovation in Science, Seoul National University, Korea · Department of Operations Research and Financial Engineering, Princeton University, USA · Department of Statistics; Interdisciplinary Program in Artificial Intelligence; Institute for Data Innovation in Science, Seoul National University, Korea.
Learning Sparsest Linear Causal DAGs with Latent Confounders via Higher-Order Cumulants
Jul 7, 2026Ming Cai, Hisayuki HaraStructural Causal Models Causal Discovery
Graduate School of Informatics, Kyoto University, Kyoto, Japan · Institute for Liberal Arts and Sciences, Kyoto University, Kyoto, Japan
Discrete Score Matching Enables Causal Discovery from Count Data
Sep 30, 2026Euijong Song, Hyewon Park, Gunwoong ParkScore Matching Causal Discovery
Department of Statistics Seoul National University, Korea · Interdisciplinary Program in Artificial Intelligence; Institute for Data Innovation in Science, Seoul National University, Korea

Sep 28, 2026J/K move · Enter open · S save

The Statistical Cost of Causal Discovery with Feedback

Sunmin Oh, Seungsu Han, Gunwoong Park

Department of Statistics; Institute for Data Innovation in Science, Seoul National University, Korea · Department of Operations Research and Financial Engineering, Princeton University, USA · Department of Statistics; Interdisciplinary Program in Artificial Intelligence; Institute for Data Innovation in Science, Seoul National University, Korea.

Sample Complexity Causal Discovery Causal Structure Learning

Open paper AskPDF arXiv

What determines the unavoidable sample cost of learning cyclic causal structure? For cyclic linear non-Gaussian models, we study exact condensation recovery from observational data: identifying the strongly connected component (SCC) partition and all edges between components. We establish the first information-theoretic lower bounds on sample complexity for this target. For

p

variables, maximum SCC size

s_{\max}

, and maximum external-parent count

d_B

, any estimator requires order

s_{\max}\log(ep/s_{\max})+d_B\log(ep/d_B)

samples in the worst case over a regular model class. These bounds distinguish the costs of SCC membership and external-parent selection. Under principal invertibility and without correlation faithfulness, we establish a population block-exogeneity principle that identifies unknown root SCCs through residual independence and inclusion minimality. A sparse-adjustment characterization shows that small adjustment sets suffice to identify SCCs and their direct external parents, without regressing on all previously recovered variables. These characterizations yield BlockExo, which attains a structurally matching sample bound without knowing

s_{\max}

d_B

under suitable conditions. Simulations support the structural dependence of our sample bound and demonstrate BlockExo's sample-efficient recovery in comparisons with other methods for cyclic causal discovery.

Abstract

Causal Discovery

Explore similar work

The Statistical Cost of Causal Discovery with Feedback

Learning Sparsest Linear Causal DAGs with Latent Confounders via Higher-Order Cumulants

Discrete Score Matching Enables Causal Discovery from Count Data