PaperlayerView exact revision on arXiv

Source-linked AI summary

Federated Causal Discovery via Regression-Directed Cumulants

Pablo Torrijos, Fabio Stella, José A. Gámez, José M. Puerta

arXiv:2609.03705v1cs.LG

TL;DR

Federated causal discovery can preserve data locality, but DirectLiNGAM cannot be straightforwardly federated, and FedISHC has a symmetric-noise weakness. The paper introduces FedRCD variants built around fourth-order cumulants and covariance-based deflation. At deployment-scale sample sizes, cumulant methods track a DAG-induced variance ladder rather than population asymmetry, while marginal standardisation makes them near-random and leaves DirectLiNGAM unaffected.

  • Problem

    Federated causal discovery can support privacy-constrained settings, but DirectLiNGAM relies on centralised data and FedISHC has a symmetric-noise weakness.

    Source: §1 · p. 2, §2.4 · p. 5

  • Method

    FedRCD pairs a fourth-order source criterion with covariance-based deflation in three variants that trade off communication rounds against algebraic noise.

    Source: §1 · p. 3

  • Results

    At deployment-scale sample sizes, cumulant methods rank variables by a DAG-induced variance ladder; marginal standardisation makes them near-random, while scale-invariant DirectLiNGAM is unaffected.

    Source: §1 · p. 3, §5 · p. 12

  • Takeaways & Limitations

    Cumulant methods are appropriate when downstream variables accumulate variance from their ancestors, a structural regime illustrated by the Danube river-flow benchmark.

    Source: §5 · p. 12

    FedISHC’s third-order identification score and deflation coefficient divide by source skewness, which vanishes under symmetric noise; replacing only the score does not fix its third-order deflation.

    Source: §2.4 · p. 5

Abstract

from arXiv · show

In this paper we study linear non-Gaussian acyclic models (LiNGAM) when used in federated environments. These causal models allow one to go beyond Markov equivalence. However, in many domains data are scarce, and increasing the sample size by centralising data from different clients is not advisable due to regulations such as the GDPR. The federated environment offers an attractive option to balance privacy and causal discovery accuracy. Unfortunately, the standard centralised estimator in the LiNGAM setting, i.e., DirectLiNGAM, cannot be straightforwardly federated. Higher-order cumulant tensors offer a way around this obstacle: they depend only on the joint distribution of the variables involved and add exactly across independent sample groups, so a single communication round suffices in horizontal, vertical, and hybrid partitions. However, FedISHC, i.e., the current federated method along these lines, breaks down under near-symmetric noise. To overcome the above limitation, we introduce the FedRCD family of causal discovery algorithms, and investigate three variants that trade off communication rounds against algebraic noise; two of them are exact federated counterparts of the centralised high-order cumulant (HC) and HC-LiNGAM algorithms, and the single-round variants further effectively support exact unlearning at any granularity, from a single observation to a whole client. Numerical experiments show that at sample sizes typical of real deployments, the entire cumulant-based federated family does not actually rank variables by the population asymmetry that the scores encode at zero. It ranks them by a variance ladder induced by the DAG along its directed paths, the cumulant counterpart of varsortability. Marginal standardisation collapses every cumulant method to near-random ordering, while scale-invariant DirectLiNGAM, not federable under this protocol, is unaffected.

1. Introduction

The paper develops federated LiNGAM methods for privacy-constrained settings where centralising data is inadvisable and DirectLiNGAM cannot be straightforwardly federated. It introduces FedRCD to address FedISHC’s symmetric-noise weakness and finds that cumulant methods rank variables by a DAG-induced variance ladder at deployment-scale sample sizes.

1. Introduction

  • Federated learning keeps client data local and exchanges aggregated statistics, addressing privacy constraints while supporting causal learning across horizontal, vertical, and hybrid partitions.Cumulants depend on the joint distribution of variables and add across independent sample groups, enabling a single-round protocol and exact unlearning by subtracting raw moments.Source: §1 · p. 2
  • FedRCD addresses FedISHC’s symmetric-noise failure by pairing a fourth-order source criterion with stable covariance-based deflation; changing only the score leaves third-order deflation unchanged.FedISHC’s identification score and deflation coefficient divide by the candidate source’s skewness, which is zero for symmetric distributions.Source: §1 · pp. 2–3
  • At deployment-scale sample sizes, cumulant methods rank variables by a DAG-induced variance ladder rather than population asymmetry; standardisation makes them near-random, while DirectLiNGAM is unaffected.Descendants accumulate variance from ancestors, and cumulant row sums line up with DAG depth.Source: §1 · p. 3
  • FedRCD’s three variants trade off communication rounds against algebraic noise, and the empirical evaluation covers Erdős-Rényi DAGs under eleven noise families and eight bnlearn repository topologies.Two variants are exact federated counterparts of centralised high-order cumulant and HC-LiNGAM algorithms.Source: §1 · p. 3

2. Background and Problem Formulation

The section introduces LiNGAM’s assumptions and cumulant-based source identification, then sets out how cumulants support federated estimation and why FedISHC is limited under symmetric noise. It also explains why changing only FedISHC’s identification score to fourth order is insufficient.

2.1. The LiNGAM Model

  • LiNGAM identifies the full DAG from the joint distribution when at most one disturbance is Gaussian, under linearity, acyclicity, independent noise, and no unobserved confounders.Heteroscedastic noise is allowed.Source: §2.1 · p. 3
  • DirectLiNGAM does not admit federation by aggregated statistics alone because it uses raw-data ICA or kernel independence tests requiring joint access to tested variables.Both ICA-LiNGAM and DirectLiNGAM are described as computationally costly.Source: §2.1 · pp. 3–4

2.2. Higher-Order Cumulants and Source Identification

  • Cumulants are multilinear, additive for independent variables, and vanish at order three or higher for Gaussian variables; non-Gaussianity supplies directional information.In the population, τij = 0 exactly when xi is an ancestor of xj or the variables are independent, and is positive otherwise.Source: §2.2 · p. 4
  • HC identifies sources iteratively and deflates with OLS, while HC-LiNGAM computes τ once and sorts by row sums.Their stated total costs are O(np^3) for HC and O(np^2) for HC-LiNGAM.Source: §2.2 · p. 4

2.3. Federated Causal Discovery

  • Federated cumulant aggregation requires pair coverage: at least one client must observe each variable pair, or the corresponding cumulant entries are unidentifiable.Because joint cumulants depend on the pair’s distribution and add across independent sample groups, aggregation recovers centralized estimates across horizontal, vertical, and hybrid partitions.Source: §2.3 · pp. 4–5
  • FedISHC aggregates third-order cumulants in one round and performs sequential server-side deflation; FedHC instead sorts by row sums without deflation.FedHC retains the symmetric-noise weakness of the third-order score, but avoids compounding deflation error across steps.Source: §2.3 · p. 5

2.4. Limitations of FedISHC under symmetric noise

  • Under symmetric noise, κ3(xs) vanishes in the population and is dominated by sampling fluctuation, while FedISHC divides by it in both identification and deflation.The variance bound’s leading order is Θ(κ3(xs)^−2/N), so it diverges as κ3(xs) approaches zero.Source: §2.4 · p. 5
  • A fourth-order score avoids the zero-skewness issue, but FedISHC’s third-order deflation leaves the cumulants used by that score unchanged.The score is therefore evaluated on the same matrix at each iteration, restricted to the active set; both identification and deflation require repair.Source: §2.4 · p. 5

3. The FedRCD Family

FedRCD combines a fourth-order source criterion with stable OLS deflation and offers variants that trade communication rounds against algebraic noise. The variants share client-side aggregation and support horizontal, vertical, and hybrid federation, while their deflation choices determine payload and unlearning properties.

3.1. OLS Deflation Coefficient

  • FedRCD pairs the fourth-order source criterion with OLS deflation, whose denominator is positive for non-degenerate sources regardless of noise distribution.The OLS coefficient is consistent for the same structural parameter as the prior coefficient and can be computed from aggregated covariance statistics.Source: §3 · p. 6, §3.1 · p. 6

3.2. The FedRCD-(NI/Def/X) Variants

  • The three variants share τ (4), the OLS coefficient, and client-side aggregation, and apply to horizontal, vertical, and hybrid federation.They differ in where deflation occurs and how many communication rounds are required.Source: §3.2 · p. 6
  • FedRCD-NI computes τ (4) once and sorts by row sums in one pass; it is the federated counterpart of HC-LiNGAM and supports exact unlearning from an observation to a whole client.Raw-moment contributions can be subtracted and aggregates rescaled without retraining.Source: §3.2 · pp. 6–7
  • FedRCD-Def performs exact-at-population-level algebraic cumulant updates on the server in one round, preserving unlearning but accumulating estimation noise across updates.Its server-side updates have O(p^3) total cost.Source: §3.2 · p. 7
  • FedRCD-X recomputes cumulants from actual client residuals in p − 1 rounds, avoiding accumulated algebraic approximation error at O(p^3) total payload.Its sequential rounds prevent exact unlearning because removing a client would invalidate later aggregates.Source: §3.2 · pp. 7–8

4. Experimental Evaluation

Across experiments, cumulant-based methods rank variables by a DAG-induced variance ladder at finite sample sizes, and marginal standardisation removes that signal. FedRCD-X performs strongly across noise regimes, while federation invariance holds across partitionings for fixed data.

4.1. Setup; 4.2. Reproducibility

  • Experiments use ER-2 DAGs, eleven noise settings, and 10 seeds; evaluation uses ancestral accuracy against the DAG’s partial order, with SHD also reported.Implementations use Python 3.13 and Flower; several methods were reimplemented because no public source code was available.Source: §4.1 · pp. 8–9, §4.2 · p. 9

4.3. Robustness Across Noise Distributions

  • FedRCD-X is close to DirectLiNGAM across symmetric and skewed noise, followed by FedRCD-NI, FedHC, and FedRCD-Def; the mixed-noise ranking shifts slightly.The hierarchy also holds on synthetic and bnlearn topologies; FedISHC trails most under symmetric noise.Source: Figure 1 · p. 9, §4.3 · pp. 9–10

4.4. Ablation Study

  • Changing identification from τ(3) to τ(4) raises AncAcc from 0.802 for FedISHC to 0.959 for FedISHC(τ(4)), matching FedRCD-NI at 0.960.The larger gain comes from correcting identification rather than deflation; FedRCD-X remains best on average.Source: §4.4 · p. 10
  • As p grows, FedISHC(τ(4)) converges with FedRCD-NI and FedHC as row-sum noise overtakes its small-p active-set advantage.DirectLiNGAM and FedRCD-X are the most stable; Figure 2(b) reports mean AncAcc against p at K = 10.Source: Figure 2 · p. 10, §4.4 · p. 10
  • At p = 20, all federated methods’ AncAcc curves remain flat as K varies because cumulant aggregation is lossless for fixed data across pair-covering splits.The reported federation invariance extends to vertical and hybrid partitions.Source: Figure 2 · p. 10, §4.4 · p. 10

4.5. What the cumulant family actually reads

  • At finite sample sizes, cumulant rankings across federated and centralised methods follow a DAG-induced variance ladder rather than population asymmetry.The paper calls this regularity variance stratification, the cumulant counterpart of varsortability.Source: §4.5 · p. 11
  • Every cumulant method collapses to at-or-below-random AncAcc after marginal standardisation, while DirectLiNGAM is unaffected.Standardisation removes the depth-monotone scale; the paper attributes DirectLiNGAM’s resilience to its kernel-based independence tests on raw residuals.Source: Table 2 · p. 11, §4.5 · pp. 11–12
  • FedISHC’s raw-data deficit reflects deflation noise: FedRCD-X recomputes residual cumulants, while FedRCD-Def’s algebraic updates still inject finite-sample noise.FedHC and FedRCD-NI preserve stratification without deflation; FedRCD-X restores it on increasingly clean residual data.Source: §4.5 · p. 12

5. Conclusion

The FedRCD family addresses FedISHC’s symmetric-noise failure by pairing a fourth-order source criterion with stable covariance-based deflation. The paper finds that cumulant methods rank variables by a DAG-induced variance ladder, not population asymmetry, and become near-random after marginal standardisation.

5. Conclusion

  • FedRCD fixes FedISHC’s symmetric-noise failure by combining a fourth-order source criterion with covariance-based OLS deflation.FedRCD-NI and FedRCD-X are exact federated counterparts of HC-LiNGAM and HC, respectively.Source: §5 · p. 12
  • FedRCD-NI and FedRCD-Def support exact unlearning at any granularity, and the family applies to horizontal, vertical, and hybrid federation.The single-round variants support exact unlearning; the methods match their centralised counterparts given the same aggregated statistics.Source: §5 · p. 12
  • Across the cumulant-based federated family and centralised baselines, finite-sample rankings follow the DAG-induced variance ladder rather than the population asymmetry encoded by their scores.Marginal standardisation collapses every cumulant method to near-random ordering, while scale-invariant DirectLiNGAM keeps full performance.Source: §5 · p. 12
  • FedRCD-X reaches the ceiling of exact federation under cumulant aggregation, whereas FedISHC falls below it under both symmetric and asymmetric noise.The paper identifies future work on when stratification suffices, the sample size needed to access population asymmetry, and differential privacy for transmitted tensors.Source: §5 · p. 12

Appendix A. Proofs of Propositions 1 and 2

The proofs contrast FedISHC’s ill-conditioned skewness ratio with a well-conditioned covariance ratio. Near-zero source skewness inflates the former’s variance, whereas the covariance ratio has variance of order N^-1 under the stated moment condition.

Proofs of Propositions 1 and 2

  • The cumulant-ratio variance analysis applies the delta method to f(a, b) = a/b when b ≠ 0.Here a and b are population cumulants, with unbiased aggregated estimators.Source: Appendix A · p. 15
  • When source skewness κ3(xs) approaches zero, the leading variance order of the estimated cumulant ratio is Θ(κ3(xs)^−2/N).Joint fourth-order moments remain bounded away from zero even when κ3(xs)=0; finiteness of sixth moments ensures the relevant variances and covariance are finite.Source: Appendix A · p. 15
  • For the covariance ratio, sample covariance estimators have variance O(N^-1) under bounded fourth moments, with no near-zero cumulant in the denominator.The denominator is ν = Var(xs) > 0.Source: Appendix A · p. 15

Appendix B. Algebraic Cumulant Updates for FedRCD-Def

FedRCD-Def updates aggregated arrays in place after replacing each variable with its residual using the identified source. Its cumulant updates use empirical cross-cumulants directly or, for a lower-communication approximation, a source condition that is exact in population for a true source.

Appendix B. Algebraic Cumulant Updates for FedRCD-Def

  • FedRCD-Def replaces each variable xj with residual rj = xj − βjs xs and updates all aggregated arrays in place.Here xs is the source identified in the current iteration.Source: Appendix B · p. 15
  • Equations (12) and (13) use empirical cross-cumulants directly, without the substitution indicated in the passage; this supports direct use but does not establish which method’s substitution is omitted.Source: Appendix B · p. 15
  • Equations (14) and (15) use κ2,1(xs, xi) ≈ βis κ3(xs) to avoid transmitting trivariate cumulants at O(p^3) cost.This approximation is exact in population when xs is a true source.Source: Appendix B · p. 15

C.1. Per-Noise-Family Breakdown

The per-family breakdown reports AncAcc and SHD across eleven noise families. FedISHC is consistently the weakest federated method, while FedRCD-X is strongest except under Mixed noise.

C.1. Per-Noise-Family Breakdown

  • Across the eleven noise families, FedISHC is consistently the worst federated method by AncAcc; FedRCD-X is best except with Mixed noise.Figure 3 reports AncAcc per noise family at p=20 and K=10.Source: §C.1 · p. 16, Figure 3 · p. 16
  • For SHD across the noise families, FedISHC is consistently the worst federated method and FedRCD-X is best except with Mixed noise.Figure 4 reports SHD per noise family at p=20 and K=10.Source: §C.1 · p. 16, Figure 4 · p. 16
  • FedRCD-NI and FedHC track close behind FedRCD-X in the per-family results.The breakdown covers eleven individual noise families.Source: §C.1 · p. 16

C.2. Real-World Topologies

On eight bnlearn topologies, FedRCD-X leads federated methods on symmetric and skewed inputs, while federated methods cluster under mixed noise.

C.2. Real-World Topologies

  • The eight bnlearn networks are Asia, Sachs, Child, Insurance, Water, Mildew, Alarm, and Barley, ranging from p = 8 to p = 48.Source: §C.2 · p. 16
  • Each topology is evaluated across eleven noise families using the same edge-weight pipeline as the main experiments.Source: §C.2 · p. 16
  • FedRCD-X leads on symmetric and skewed inputs, while FedHC, FedRCD-NI, and FedRCD-X are essentially tied under mixed noise.Figure 5 reports mean performance across eight bnlearn topologies (K=10).Source: §C.2 · p. 16, Figure 5 · p. 17
Loading 2609.03705v1…