Approaches to bivariate causal discovery based on the minimum description length (MDL) principle approximate the (uncomputable) Kolmogorov complexity of the models in each causal direction, selecting the one with the lower total complexity. The premise is that nature's mechanisms are simpler in their true causal order. Inherently, the description length (complexity) in each direction includes the description of the cause variable and that of the causal mechanism. In this work, we argue that current state-of-the-art MDL-based methods do not correctly address the problem of estimating the description length of the cause variable, effectively leaving the decision to the description length of the causal mechanism. Based on rate-distortion theory, we propose a new way to measure the description length of the cause, corresponding to the minimum rate required to achieve a distortion level representative of the underlying distribution. This distortion level is deduced using rules from histogram-based density estimation, while the rate is computed using the related concept of information dimension, based on an asymptotic approximation. Combining it with a traditional approach for the causal mechanism, we introduce a new bivariate causal discovery method, termed rate-distortion MDL (RDMDL). We show experimentally that RDMDL achieves competitive performance on the Tübingen dataset. All the code and experiments are publicly available at github.com/tiagobrogueira/Causal-Discovery-In-Exchangeable-Data.
Figures & tables
L(X)−L(Y)
full method
bQCD
54.7
71.1
COMIC
55.6
76.0
GPI
49.0
68.1
SLOPE
53.7
80.5
Table 1: AUROC (in %) on the Tübingen dataset, achieved by (L(X)−L(Y)) alone as a prediction score versus the full method, for bQCD, COMIC, GPI, and SLOPE.
Method
AUROC (%)
Accuracy (%)
AUDRC (%)
ANM
61.9
60.4
62.9
bQCD
71.1
69.6
70.1
CAM
46.6
52.3
43.1
CDCI
60.7
61.5
55.0
CDS
59.0
60.5
57.8
CGNN
61.6
61.5
69.6
Table 2: Performance of the 4 RDMDL versions and 17 other methods on the Tübingen benchmarks. The best results in each column are in bold; the second best is underlined.
Method
CE - Cha
CE - Gauss
CE - Multi
CE - Net
AN
AN - s
LS
LS - s
MN - U
SIM
SIM - c
SIM - G
SIM - ln
RDMDL-FD
62.7 ( 60.7 )
64.7 (58.7)
97.0 ( 89.3 )
75.2 (68.3)
51.2 (49.0)
43.3 (45.0)
49.0 (47.0)
13.4 (17.0)
0.9 (6.0)
53.6 (47.0)
59.6 (57.0)
59.4 (55.0)
87.2 (77.0)
RDMDL-R
64.2 (60.3)
64.5 (59.0)
96.5 (88.3)
81.1 (72.0)
84.5 (74.0)
52.3 (51.0)
77.0 (68.0)
6.9 (13.0)
1.3 (7.0)
61.9 (56.0)
66.9 (65.0)
66.2 (57.0)
91.4 (79.0)
RDMDL-Sc
63.7 (59.3)
69.4 (62.7)
96.9 ( 89.0 )
77.5 (69.3)
58.6 (52.0)
34.7 (34.0)
53.5 (51.0)
4.8 (12.0)
0.8 (4.0)
58.1 (53.0)
63.9 (62.0)
60.1 (54.0)
88.6 (78.0)
RDMDL-St
64.0 (60.3)
65.1 (59.0)
96.5 (88.3)
81.7 (72.3)
86.8 (76.0)
53.7 (51.0)
78.5 (69.0)
5.8 (13.0)
1.4 (7.0)
62.8 (56.0)
67.6 (66.0)
66.4 (58.0)
91.6 (79.0)
bQCD
56.3 (55.0)
48.1 (54.3)
53.2 (49.0)
90.7 ( 81.3 )
100.0 ( 100.0 )
90.5 ( 83.0 )
100.0 ( 100.0 )
100.0 ( 100.0 )
100.0 ( 100.0 )
69.9 ( 68.0 )
80.8 ( 77.0 )
71.7 (67.0)
91.9 ( 87.0 )
GPI
64.9 ( 62.4 )
89.1 ( 83.2 )
72.2 (71.5)
88.8 ( 81.3 )
79.2 (85.5)
62.4 (62.5)
72.8 (83.6)
73.8 (70.9)
85.7 (80.7)
88.3 ( 83.7 )
92.4 ( 85.6 )
90.1 ( 80.4 )
92.8 (84.5)
Table 3: Results of the four versions of RDMDL in three collections of synthetic datasets: CE, ANLSMN, and SIM, evaluated using AUROC and accuracy (in parentheses in each cell).The best results for each dataset are in bold and the second-best are underlined.
Figure 1: AUDRC curves in the Tübingen benchmark. Left: RDMDL (green) compared to all other implemented methods (shades of red); right: analysed MDL causal discovery methods.
Predictors-FD
L(Y∣X)
Marginals
correct
incorrect
L(X)
correct
\textcolor green38.2 / \textcolor green16.2
\textcolor green15.8 / \textcolor red4.8
\textcolor green70.2 / \textcolor red4.8
incorrect
\textcolor red8.1 / \textcolor green1.7
\textcolor red8.3 / \textcolor red6.9
\textcolor green1.7 / \textcolor red23.3
Marginals
\textcolor green56.1 / \textcolor red8.1
\textcolor green15.8 / \textcolor red20.0
Table 4: Confusion matrix: in each cell, on the left, the result when taken by (L(X)−L(Y)) and on the right when (L(Y∣X)−L(X∣Y)) dominates. Green indicates a correct decision and red an incorrect decision. Top-left table: RDMDL-FD; top-right table: RDMDL-R; bottom-left table: RDMDL-Sc; bottom-right table: RDMDL-St.
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
LX→Y=LX(X)+LY∣X(X,Y)
Appendix
Algorithm 1 RDMDL
dimX←dim(X).
Appendix
Algorithm 2 LX (from RDMDL)
Hi≈alogϵi+b
Appendix
Algorithm 3 Information Dimension dim(X) (from RDMDL)
LY∣X←min(Lp,Li,Le)
Appendix
Algorithm 5 LY∣X (from RDMDL)
rf,θf←LSf(X,Y),
Appendix
Algorithm 6 fit (from RDMDL)
Method
Source
AN
AN-s
CE-Cha
CE-Multi
CE-Net
LS
LS-s
MN-U
Multi
Net
SIM
SIM-G
SIM-c
SIM-ln
Tübingen
COMIC
COMIC
100
100
43
79
78
100
100
100
57
78
54
89
67
EMD
bQCD
36
33
60
42
83
45
58
40
52
68
GPLVM
GPLVM, COMIC
100
100
100
100
100
83
92
79
90
GRCI
LOCI
100
94
70
98
87
88
77
85
77
70
77
77
82
LiNGAM
bQCD
0
4
7
3
0
42
25
53
31
42
PNL
bQCD
96
63
91
44
66
70
64
65
61
73
Appendix
Table 5: Accuracy (in %) obtained by the different unimplemented methods for all evaluated datasets.
Method
Source
AN
AN-s
CE-Cha
CE-Gauss
CE-Multi
CE-Net
LS
LS-s
MN-U
SIM
SIM-G
SIM-c
SIM-ln
Tübingen
COMIC
COMIC
100
100
47
91
84
100
100
100
58
85
59
95
75
EMD
bQCD
43
GPLVM
GPLVM, COMIC
100
100
82
89
98
99
100
100
100
92
99
91
97
78
LiNGAM
bQCD
30
PNL
bQCD
70
CURE
bQCD
64
Appendix
Table 6: AUROC (in %) obtained by the different unimplemented methods for all evaluated datasets.
Method
Source
AN
AN-s
CE-Cha
LS
LS-s
MN-U
Multi
Net
SIM
SIM-G
SIM-c
SIM-ln
Tübingen
GRCI
LOCI
100
100
71
100
95
97
74
96
90
88
92
92
73
Appendix
Table 7: AUDRC (in %) obtained by the different unimplemented methods for all evaluated datasets.
Method
CE-Cha
CE-Gauss
CE-Multi
CE-Net
AN
AN-s
LS
LS-s
MN-U
SIM
SIM-c
SIM-G
SIM-ln
RDMDL-FD
62.7 (60.7)
64.7 (58.7)
97.0 ( 89.3 )
75.2 (68.3)
51.2 (49.0)
43.3 (45.0)
49.0 (47.0)
13.4 (17.0)
0.9 (6.0)
53.6 (47.0)
59.6 (57.0)
59.4 (55.0)
87.2 (77.0)
RDMDL-R
64.2 (60.3)
64.5 (59.0)
96.5 (88.3)
81.1 (72.0)
84.5 (74.0)
52.3 (51.0)
77.0 (68.0)
6.9 (13.0)
1.3 (7.0)
61.9 (56.0)
66.9 (65.0)
66.2 (57.0)
91.4 (79.0)
RDMDL-Sc
63.7 (59.3)
69.4 (62.7)
96.9 (89.0)
77.5 (69.3)
58.6 (52.0)
34.7 (34.0)
53.5 (51.0)
4.8 (12.0)
0.8 (4.0)
58.1 (53.0)
63.9 (62.0)
60.1 (54.0)
88.6 (78.0)
RDMDL-St
64.0 (60.3)
65.1 (59.0)
96.5 (88.3)
81.7 (72.3)
86.8 (76.0)
53.7 (51.0)
78.5 (69.0)
5.8 (13.0)
1.4 (7.0)
62.8 (56.0)
67.6 (66.0)
66.4 (58.0)
91.6 (79.0)
ANM
34.3 (40.0)
43.3 (45.3)
48.7 (51.0)
56.3 (59.0)
52.8 (51.2)
52.9 (55.8)
59.4 (57.8)
52.3 (57.8)
63.5 (62.2)
49.1 (46.3)
47.8 (43.6)
27.5 (37.2)
60.7 (56.2)
bQCD
56.3 (55.0)
48.1 (54.3)
53.2 (49.0)
90.7 ( 81.3 )
100.0 ( 100.0 )
90.5 (83.0)
100.0 ( 100.0 )
100.0 ( 100.0 )
100.0 ( 100.0 )
69.9 (68.0)
80.8 ( 77.0 )
71.7 (67.0)
91.9 ( 87.0 )
Appendix
Table 8: Performance of the sixteen implemented causal discovery methods, alongside the four versions of RDMDL, in three sets of synthetic benchmarks, evaluated using AUROC (accuracy). The value in bold corresponds to the best result in each column, and those underlined to the second best.
Causal discovery with nonlinear mechanisms and latent confounders remains challenging. Existing methods often rely on either linear assumptions or causal sufficiency, limiting their applicability. We propose an MDL-based causal discovery framework that explicitly accounts for latent confounders while allowing flexible nonlinear mechanisms by minimizing the luckiness normalized maximum likelihood (LNML) code-length. The causal relationship between each variable pair is determined by selecting the shortest code-length of the causal model, and we introduce the notion of Δ-pseudo-collinearity to identify dependencies induced by latent confounders. Based on these ideas, we develop a greedy algorithm, termed Pseudo-Collinearity Guided Causal Discovery (PCG-CD). Experiments on synthetic and real-world datasets demonstrate that the proposed method accurately recovers directed causal relationships and effectively detects latent confounders.
Zhongyi Que, Shin Matsushima, Kenji Yamanishi
Graduate School of Information Science and Technology, The University of Tokyo, Tokyo, Japan · Graduate School of Arts and Sciences, The University of Tokyo, Tokyo, Japan
We present DMCD (DataMap Causal Discovery), a two-phase causal discovery framework that integrates LLM-based semantic drafting from variable metadata with statistical validation on observational data. In Phase I, a large language model proposes a sparse draft DAG, serving as a semantically informed prior over the space of possible causal structures. In Phase II, this draft is audited and refined via conditional independence testing, with detected discrepancies guiding targeted edge revisions. We evaluate our approach on three metadata-rich real-world benchmarks spanning industrial engineering, environmental monitoring, and IT systems analysis. Across these datasets, DMCD achieves competitive or leading performance against diverse causal discovery baselines, with particularly large gains in recall and F1 score. Probing and ablation experiments suggest that these improvements arise from semantic reasoning over metadata rather than memorization of benchmark graphs. Overall, our results demonstrate that combining semantic priors with principled statistical verification yields a high-performing and practically effective approach to causal structure learning.
Samarth KaPatel, Sofia Nikiforova, Giacinto Paolo Saggese +1
Causal discovery seeks to uncover the causal dependencies among variables. For this purpose, we propose an algorithm called Tensor-based Second-order Causal Discovery (TSCD). Its input is a tensor obtained from the covariance matrices of observational and interventional data. Assuming the causal dependencies follow a linear structural equation model on a directed acyclic graph (DAG), TSCD outputs the DAG and the functions on its edges, requiring only that the noise variables are uncorrelated. We also implement a version of the approach for nonlinear models. Our focus on second-order statistics (via the covariance matrices) is motivated by their statistical and computational efficiency relative to higher-order moments, their identifiability relative to first-order statistics, and that they work regardless of whether the variables are Gaussian. We show that TSCD has identifiable causal order and parameters from a number of interventions that is logarithmic in the number of variables. Experiments show that TSCD is robust to noise, competitive with existing methods, and scales to hundreds of variables.