Source-linked AI summary
Graph Dirichlet Energy for Fitting-Free Bivariate Causal Inference
Povilas Daniušis
TL;DR
Bivariate causal direction is generally not identifiable from observational data alone without additional assumptions. GDECI compares graph Dirichlet energies after marginal equalization, using a fitting-free criterion. It ranked fifth in macro accuracy on synthetic suites, ranked third and fifth on the two Tuebingen accuracy measures, and was fastest up to about n=10^4.
Problem
Observational joint distributions generally do not identify whether X causes Y or Y causes X without additional assumptions.
Source: §1 · p. 1Method
Results
GDECI ranked fifth in macro accuracy on 12 synthetic suites (0.776), third in unweighted Tuebingen accuracy (0.684), and fifth in weighted accuracy (0.678); it was fastest up to n ≈ 10^4.
Source: §5.4 · p. 5, §7 · p. 8Takeaways & Limitations
On the evaluated benchmarks, GDECI showed a favorable trade-off between accuracy and computational cost.
Source: §7 · p. 8The theoretical guarantees hold only under restricted conditions and do not establish identifiability in general.
Source: §6 · p. 7
Abstract
from arXiv · showhide
We propose the Graph Dirichlet Energy Causal Inference (GDECI) criterion for distinguishing cause from effect in bivariate settings. For a candidate direction $X\to Y$, we construct a kernel similarity graph from $X$ and treat $Y$ as a graph signal. The score is the Dirichlet energy of this signal, induced by the unnormalized graph Laplacian. The reverse score swaps the variables, and the lower-energy direction is inferred as causal. The method requires neither regression fitting nor independence testing. After the empirical probability integral transform, its decisions are invariant under strictly monotone transformations of either variable, and the graph operations reduce to convolutions, allowing exact evaluation in $O(n\log n)$ time and $O(n)$ memory. At the population level, GDECI compares degree-weighted Bayes squared prediction errors plus a non-negative smoothness term of the regression function. As the bandwidth tends to zero, the weights become uniform and the smoothness term vanishes, reducing the criterion to a RECI-type comparison of expected conditional variances in copula space. Empirically, we compare GDECI with QCCD, GRCI, CAM, IGCI (two variants), RESIT, LOCI, QPE-k, and RECI (two variants), in accuracy on 1899 cause--effect pairs and in inference speed. GDECI ranked fifth of eleven methods in macro-averaged accuracy on 12 synthetic suites ($0.776$). On the real-world Tuebingen pairs, it ranked third in unweighted accuracy ($0.684$) and fifth in weighted accuracy ($0.678$). It was also the fastest of the compared methods up to $n\approx10^{4}$. The accompanying code repository: https://github.com/povidanius/gdeci.
1 Introduction
Bivariate causal discovery seeks direction from observational data, although the joint distribution alone generally does not identify it without assumptions. GDECI proposes a fitting-free graph-energy criterion and evaluates it alongside existing methods.
1 Introduction
- Observational joint distributions generally do not identify causal direction without additional assumptions, motivating methods that exploit directional statistical or structural asymmetries.Such direction estimates matter where interventions are costly or infeasible.Source: §1 · p. 1
- Existing approaches use assumptions such as additive or location–scale noise, quantile partial effects, or independence of cause and mechanism to obtain directional asymmetries.Examples include residual-independence tests, fitted additive models, and comparisons of regression errors or quantile scores.Source: §1 · pp. 1–2
- GDECI tests whether graph Dirichlet energy differs by direction, treating one variable as a signal on a similarity graph built from the other.The score uses the unnormalized graph Laplacian; the paper presents this graph-based framework as a new approach to bivariate causal asymmetry.Source: §1 · p. 2
- The proposed criterion is fitting-free, invariant under strictly monotone transformations, and decomposes at population level into weighted prediction error plus smoothness.As bandwidth tends to zero, the smoothness term vanishes and the criterion becomes a RECI-type comparison in copula space; an algorithm runs in O(n log n) time and O(n) memory.Source: §1 · p. 2
- The empirical study benchmarks GDECI against QCCD, GRCI, CAM, IGCI, RESIT, LOCI, QPE-k, and RECI on 1,899 cause–effect pairs.The reported comparison covers accuracy and inference time.Source: §1 · p. 2
2 Method
GDECI equalizes the marginal scales and compares directional scores, selecting the direction with lower score. It uses a bandwidth scaled to the median distance and an unnormalized Laplacian to preserve monotone-transformation invariance.
2 Method
- The method maps continuous variables to uniform-marginal copula variables, so directional signals are not confounded by differing one-dimensional marginals.In practice, normalized empirical ranks replace the population transforms.Source: §2 · p. 2
- The reverse score swaps the variables, and GDECI returns the direction with the smaller score.Source: §2 · p. 2
- Bandwidth σ is parameterized by multiplier m times the pair-specific median interpoint distance, making m the only free parameter.After marginal equalization, both directions share the same bandwidth.Source: §2 · p. 2
- Marginal equalization and the unnormalized Laplacian make decisions invariant to strictly monotone transformations, including decreasing transformations.The normalized Laplacian generally lacks invariance under strictly decreasing transformations.Source: §2 · p. 3
3 Theoretical analysis
The population criterion combines degree-weighted prediction error with a smoothness term, and its zero-bandwidth limit is a copula-space conditional-variance comparison. Theoretical direction-selection results hold under specified mechanism conditions.
3 Theoretical analysis
- At fixed bandwidth, the empirical directional scores converge to population criteria; as bandwidth tends to zero, smoothness vanishes and the criteria become expected conditional variances.The limiting comparison is in copula space.Source: §3 · p. 3
- At small bandwidth, degree weighting contributes at first order, while the smoothness terms affect the score difference only beyond first order.For the stated mechanism conditions, the causal direction is selected whenever its expected conditional variance is not larger.Source: §3 · p. 3
- For non-injective mechanisms, sufficiently small noise and bandwidth make the population score favor the causal direction, and the rank-based rule selects it almost surely for sufficiently large samples.The result assumes the mechanism and distributions specified in Theorem 1.Source: §3 · p. 3
- For bounded monotone location–scale mechanisms, the causal-direction smoothness term is O(σ^3), while the reverse term is bounded below by order σ^3 log(1/σ).Under these conditions, if the causal expected conditional variance is no larger, sufficiently small bandwidth favors the causal direction.Source: §3 · p. 3
- GDECI approaches a RECI-type comparison with Bayes-optimal regression in copula space, but positive bandwidth adds degree weighting and smoothness without fitting a regression.The paper reports that the positive-bandwidth component improved overall accuracy relative to an extrapolated zero-bandwidth estimate.Source: §3 · p. 3
4 Efficient computation
Marginal equalization lets the computation reuse a rank-indexed kernel matrix in both directions. Fast Fourier transforms evaluate the required convolutions exactly in O(n log n) time and O(n) memory.
4 Efficient computation
- Sorting by either variable’s ranks yields the same Toeplitz kernel matrix, with weights determined by rank lag and a shared bandwidth.The two directional scores differ only through their reordered signals.Source: §4 · p. 4
- The graph energies use a single Laplacian formed from the Toeplitz kernel matrix, with degrees given by its row sums.Source: §4 · p. 4
- Fast Fourier transforms compute the convolution-based energies exactly in O(n log n) time and O(n) memory.Source: §4 · p. 4
5 Experiments
The experiments compare GDECI with established bivariate causal-discovery methods across benchmark suites, scoring variants, accuracy, and computational cost. GDECI ranks fifth on synthetic suites and third in unweighted Tuebingen accuracy, while its positive-bandwidth component contributes directional signal.
5.1 Methods
- The comparison includes QCCD, GRCI, CAM, IGCI variants, RESIT, LOCI, QPE-k, and two RECI configurations; several methods use released per-pair outputs.LOCI, RECI, and QPE-k were run locally.Source: §5.1 · p. 4
5.2 Datasets
- The evaluation covers 13 benchmark suites, including synthetic mechanism families and 99 eligible real-world Tuebingen pairs.Tuebingen results include both unweighted accuracy and accuracy using supplied pair weights.Source: §5.2 · pp. 4–5
5.3 GDECI scores evaluated
- They compare empirical-rank PIT with standardized preprocessing; bandwidth multipliers are selected on 300 independent pairs, and EDGEMASS uses marginal information alone.Under the PIT, both samples are permutations of the same grid, so comparing scores reduces to comparing energies.Source: §5.3 · p. 5
5.4 Benchmark results
- 0.776 macro accuracy ranked fifth on 12 synthetic suites; GDECI ranked third unweighted (0.684) and fifth weighted (0.678) on Tuebingen.Most methods’ confidence intervals overlap on the 99 Tuebingen pairs.Source: §5.4 · p. 5
- At n = 10^3, GDECI was the cheapest method; more accurate methods on synthetic suites were about two to five orders of magnitude slower.The fast algorithm followed the predicted O(n log n) rate; beyond n ≈ 2 × 10^4, RECI was faster.Source: §5.4 · p. 6
5.5 Ablation: does the σ > 0 part carry directional signal?
- 0.732 overall accuracy for the full score exceeded 0.686 for the conditional-variance component and 0.663 for the positive-bandwidth component; macro synthetic accuracy rose from 0.731 to 0.776 with bandwidth.Adding the positive-bandwidth component corrected 185 decisions and misdirected 101, a net gain of +84.Source: §5.5 · p. 7
6 Limitations
GDECI’s theoretical guarantees apply only in restricted settings and do not establish causal identifiability in general. Its limiting comparison requires taking the sample-size limit before the bandwidth tends to zero, and the method is intended for dependent pairs without unobserved confounding.
6 Limitations
- The guarantees cover only restricted settings and do not establish identifiability in general.They identify settings where a conditional-variance or smoothness term favors the causal direction.Source: §6 · p. 7
- The zero-bandwidth population rule compares expected conditional variances after n tends to infinity, and GDECI is intended for dependent pairs without unobserved confounding.A preliminary independence test can help avoid orienting independent pairs but cannot rule out unobserved confounding.Source: §6 · p. 7
- Positive bandwidth improved macro accuracy over the estimated zero-bandwidth limit, but the gain was uneven and negative on two of 12 synthetic suites.Source: §6 · p. 7
7 Conclusion
The conclusion presents GDECI as a fitting-free bivariate causal criterion based on graph Dirichlet energy, with monotone-transformation invariance and a population form combining degree-weighted prediction error and smoothness. Its experiments show a favorable accuracy–cost trade-off on evaluated benchmarks, while its theory provides restricted guarantees and the authors identify multivariate extensions as future work.
7 Conclusion
- The unnormalized-Laplacian criterion is fitting-free and invariant to strictly monotone transformations after rank transformation, with a population score combining degree-weighted Bayes squared prediction error and non-negative smoothness.As bandwidth tends to zero, the weights become uniform and the smoothness term vanishes, yielding a RECI-like conditional-variance comparison in copula space.Source: §7 · p. 7
- For specified non-injective mechanisms, sufficient conditions yield causal-direction selection; for bounded-support additive-noise and heteroscedastic models, the causal-direction smoothness term is smaller at sufficiently small bandwidth.These guarantees take n → ∞ at fixed bandwidth, require sufficiently small bandwidth, and do not establish identifiability in general.Source: §7 · p. 7
- Marginal equalization reduces graph operations to convolutions, giving an algorithm with O(n log n) time and O(n) memory.The authors suggest its use for large samples and screening candidate pairs before slower methods.Source: §7 · p. 8
- GDECI ranked fifth in macro accuracy on 12 synthetic suites, third in unweighted and fifth in weighted accuracy on Tuebingen pairs, and was fastest up to n ≈ 10^4.Four methods were more accurate on synthetic suites but about two to five orders of magnitude slower; no compared method was both faster and more accurate at n = 10^3.Source: §7 · p. 8
- Future work includes multivariate extensions and GDECI-based directionality constraints between latent factors in causal representation learning.Source: §7 · p. 8
A Invariance under monotone transformations.
The appendix establishes that rank-based GDECI decisions are invariant to strictly monotone transformations of either variable. The argument uses symmetry and the zero-row-sum property of the unnormalized Laplacian, properties that generally fail for the normalized Laplacian.
A Invariance under monotone transformations.
- For rank vectors u and v, the rule compares the graph energies vᵀL_uv and uᵀL_vu, with each graph built from the other variable’s ranks.Source: A Invariance under monotone… · p. 11
- A strictly increasing transformation leaves ranks unchanged, while a decreasing transformation maps ranks to 1 − z; both preserve the energies using the unnormalized Laplacian’s symmetry and zero-row-sum property.Source: A Invariance under monotone… · p. 11
- The resulting empirical-score invariance carries to population limits, whereas the normalized Laplacian generally lacks the property needed for the same invariance.Source: A Invariance under monotone… · p. 11
B Population limit and partial identifiability
At fixed bandwidth, the population scores converge to degree-weighted conditional-variance terms plus regression-function smoothness terms. As bandwidth tends to zero, the smoothness terms vanish and the scores converge to expected conditional variances, yielding a directional ordering under specified conditions.
B Population limit and partial identifiability
- For fixed σ > 0, the population scores are degree-weighted conditional variances plus normalized Dirichlet terms of the directional regression functions.The rank-based scores have the same population limits.Source: B Population limit and partial… · p. 13
- As σ ↓ 0, the Dirichlet terms vanish and the population scores converge to E Var(V | U) and E Var(U | V).Source: B Population limit and partial… · pp. 13–14
- If the two expected conditional variances differ, their ordering matches the population-score ordering for all sufficiently small positive bandwidth, taking n → ∞ first.Source: B Population limit and partial… · p. 14
- For the stated non-injective mechanisms, sufficiently small noise and bandwidth make the forward population score lower, and the rank-based rule selects the causal direction almost surely for sufficiently large samples.The result assumes independent continuous X and N, a continuous outcome at zero noise, and a mechanism not injective on any full-probability Borel set.Source: B Population limit and partial… · pp. 15, 17
C Causal information at positive bandwidth
This section analyzes the causal score at positive bandwidth, combining degree-weighted conditional variances with Dirichlet energy and examining how regression smoothness affects their rates. For bounded location–scale mechanisms, it gives conditions under which the forward score is smaller at sufficiently small positive bandwidth, including the additive case.
C Causal information at positive bandwidth
- For a Lipschitz regression, D_σ[g]/μ_σ = O(σ^2), smaller than the O(σ) correction in the degree-weighted conditional-variance terms.An inverse-square-root singularity in the derivative can introduce an additional log(1/σ) factor.Source: C Causal information at positive… · p. 19
- For these mechanisms, D_σ[r] ≤ C_1σ^3, while ν_r has positive endpoint values and ν_s tends to zero at both endpoints.The forward regression is Lipschitz; the reverse regression’s derivative has an inverse-square-root singularity near the endpoints, adding a logarithmic factor to its Dirichlet-energy rate.Source: C Causal information at positive… · p. 19
- If E_r ≤ E_s, then Q_σ(U → V) < Q_σ(V → U) for all sufficiently small σ under the stated bounded location–scale assumptions.The result includes monotone additive models Y = f(X) + N with f′ ≥ λ > 0.Source: C Causal information at positive… · p. 19
- For sufficiently small σ > 0, the forward score is smaller whenever Er ≤ Es: the difference tends to Es − Er if Es > Er, and has a strictly positive σ coefficient if Es = Er.In the equality case, this coefficient is strictly positive because νr(0), νr(1) > 0.Source: C Causal information at positive… · p. 23
- The additive case follows by taking g ≡ 1.Source: C Causal information at positive… · p. 23
D Efficient computation
After rank-transforming the variables, the computation orders observations by rank and reduces the graph operations to discrete convolutions. Fast Fourier transforms yield exact energies in O(n log n) time and O(n) memory.
D Efficient computation
- The rank-based kernel weights depend only on rank lag, producing a symmetric Toeplitz matrix shared by both directions.The common bandwidth is determined by sample size and the median rank distance.Source: D Efficient computation · p. 24
- With ties broken at random, the two directions have equal total edge mass, so the rule selects the direction with lower energy.Ordering observations by each variable’s rank yields the corresponding reordered signals for the energy comparison.Source: D Efficient computation · pp. 23–24
- O(n log n) time and O(n) memory suffice to compute the two energies exactly using FFT-based convolutions.The convolution products and cumulative sums avoid forming the full kernel-weight matrix.Source: D Efficient computation · p. 24
E Auxiliary tables and figures
The auxiliary materials describe a positive-bandwidth ablation and a robustness table for the small-bandwidth decomposition.
E Auxiliary tables and figures
- Figure 2 compares conditional-variance, positive-bandwidth, and full-score accuracy across suites, and shows full-score accuracy over a bandwidth grid.The figure reports results by suite, macro over 12 synthetic suites, and pooled over all pairs; the bandwidth grid also separates Tuebingen and individual synthetic suites.Source: Figure 2 · p. 25
- Table 3 compares B-alone and full-score decisions across fitting windows, reporting corrected, misdirected, and net counts alongside pooled accuracy.The caption identifies k = 5 as the main analysis.Source: Table 3 · p. 25