PaperlayerView exact revision on arXiv

Source-linked AI summary

Jigsaw-CRL: Recovering Global Latent Causal Order from Fragmented Multi-Client Interventions

Haijie Xu, Chen Zhang

arXiv:2608.28991v1stat.MLcs.LG

TL;DR

The paper addresses CRL when clients access different subsets of a shared latent causal system, making single-client node-wise graph recovery unavailable. Jigsaw-CRL identifies block-structured client fragments under soft interventions and assembles them into the global node-level causal order, with theoretical guarantees and synthetic validation.

  • Problem

    Existing CRL methods commonly assume a shared latent variable set, whereas fragmented clients access only subsets of a common global system and may induce mixed graphs through marginalization.

  • Method

    Jigsaw-CRL uses soft-intervention structure to recover each client’s block partition, block-level ancestral relation, and latent subspaces, then assembles complementary client fragments.

  • Results

    The framework proves client-level identifiability and global assembly guarantees, develops recovery algorithms, and validates Jigsaw-CRL on synthetic fragmented multi-client systems.

  • Takeaways & Limitations

    Each client reveals a block-level causal fragment, while complementary fragments can recover the global node-level latent causal order.

  • Takeaways & Limitations

    The framework assumes client-level intervention coverage, cross-client label alignment, and a cross-client coverage condition for global assembly.

Abstract

from arXiv · show

Causal representation learning (CRL) aims to recover latent causal variables and their structural relations from high-dimensional observations. Existing CRL methods typically assume that all environments are defined over the same latent variables, or at least share a common latent representation space. We study a fragmented multi-client setting, where multiple clients interact with the same global latent causal system but each client only accesses and intervenes on a subset of the latent variables. In this regime, marginalizing unused latent variables induces bidirected edges, so a single client no longer admits a node-wise latent causal graph, and the global latent causal order must be recovered by assembling client-specific structural fragments. We propose \textbf{Jigsaw-CRL}, a framework for recovering global latent causal order from such fragmented interventions. Under soft interventions, differences between precision matrices across environments exhibit a low-rank structure governed by latent ancestor relations. This enables recovery, for each client, of a block partition, the corresponding block-level ancestral order, and latent subspaces, and then assembly of these fragments into the global node-level latent causal order. We establish identifiability guarantees, develop practical algorithms, and validate the framework on synthetic data. Our codes are available on https://anonymous.4open.science/r/code-for-Jigsaw-CRL-7B26

1 Introduction

The paper studies CRL when clients observe and intervene on different subsets of one global latent causal system. It introduces Jigsaw-CRL to recover client-level causal fragments and assemble them into a global latent causal order.

  • Existing CRL methods generally assume observations share the same latent variables or representation space.
  • In the fragmented multi-client setting, each client accesses and intervenes on only a subset of the global latent variables.
  • Marginalizing unused variables can induce directed shortcuts and bidirected dependencies, so a client-specific latent structure is no longer an ordinary DAG.
  • Jigsaw-CRL recovers block partitions, block-level ancestral orders, and latent subspaces from client-specific interventions before assembling complementary fragments globally.
  • The framework establishes identifiability results, develops recovery algorithms, and validates the approach on synthetic fragmented multi-client systems.

2 Problem Setup and Client-Specific Block Structure

The setup defines a shared global latent SEM observed through client-specific subsets and soft interventions. Because marginalized variables alter each client’s graph, the recovery target is a block structure with a block-level ancestral order assembled across clients.

  • 2.1 Problem formulation: fragmented multi-client CRL: The global latent variables follow a linear structural equation model whose coefficient matrix defines a latent DAG and ancestral relation.
  • 2.1 Problem formulation: fragmented multi-client CRL: Each client directly uses only a subset of latent variables, while the remaining variables are marginalized from its observations.
  • 2.1 Problem formulation: fragmented multi-client CRL: Clients observe one observational regime and multiple single-node soft interventional regimes targeting nodes they directly access.
  • 2.1 Problem formulation: fragmented multi-client CRL: The recovery problem has two levels: identify structural information remaining in each client’s fragment, then assemble fragments to recover the global ancestral relation.
  • 2.2 Client-specific induced graph and block structure: Marginalization creates directed shortcuts and correlated effective noises, represented respectively by directed and bidirected relations in the client-specific mixed graph.
  • 2.2 Client-specific induced graph and block structure: Client-level blocks group mutually reachable nodes that are structurally entangled, while a meaningful ancestral order remains defined across blocks.

3 Client-level Identifiability from Low-rank Precision Perturbations

Jigsaw-CRL uses low-rank precision perturbations from soft interventions to recover each client’s block partition, block-level ancestral order, and associated latent subspaces despite fragmented access. These client-level objects are identifiable only up to intrinsic within-block ambiguity, not as a node-wise latent DAG.

  • Client-level identifiability: A single fragmented client identifies a block-structured mixed object rather than a node-wise latent DAG.Marginalization-induced bidirected dependencies make nodes within blocks structurally entangled.
  • Analytical coordinates: The block RQ decomposition separates block-associated row directions from block-ancestor mixing, although its matrix representation is generally non-unique.The identifiable quantities are the block row spaces, not a particular choice of basis or matrix representative.
  • Low-rank precision perturbations: Soft interventions produce low-rank precision perturbations whose row spaces are confined to target blocks and their block ancestors.A single-node intervention yields a rank-2 perturbation, enabling ancestor-closed subspace recovery.
  • Recovery algorithm: Under the stated intervention coverage and genericity assumptions, Algorithm 2 recovers each client’s block partition and block-level ancestral relation.The recovery procedure iteratively uses projected row-space dimensions to identify blocks and their ancestors.
  • Identifiability result: The recovered latent variables are identified up to block-level ancestor mixing, with estimated coordinates related by an invertible block-diagonal transformation and an order-preserving row permutation.This ambiguity preserves the identifiable block-associated row subspaces and causal structure.

4 Global Ancestral Recovery Across Clients

Global latent ancestral order is recovered by assembling client-specific fragments with complementary blockings. Under cross-client coverage, singleton-block parent relations witness every global Hasse edge, and their transitive closure recovers the global order up to intervention-target relabeling.

  • Motivation: A single client cannot generally recover the global node-level order because marginalization may merge several global variables into one client-specific block.Different clients can induce different blockings, creating the information needed for global assembly.
  • Cross-client coverage: Cross-client coverage requires every global Hasse edge to be jointly visible and separately targeted by at least one client.This ensures the edge appears between singleton blocks in that client’s recovered fragment.
  • Global assembly: Algorithm 3 collects recovered parent relations between singleton blocks across clients and takes their transitive closure.The procedure combines the client-level fragments into one global ancestral relation.

5 Finite-sample Method and Experiments

The paper implements its population recovery procedures for finite samples and evaluates them across graph, sparsity, scale, and noise settings. Recovery improves with sample size and reaches the theoretical guarantees when population precision matrices are used.

  • Finite-sample implementation: The finite-sample implementation replaces population precision matrices with empirical estimates and uses thresholded singular values to estimate effective row-space dimensions.The threshold selects the smallest r whose cumulative singular-value mass exceeds 1 − τ, yielding finite-sample versions of Algorithms 1 and 2.
  • Experimental setup: The experiments vary three global graph structures, client missingness patterns, Gaussian or Laplace noise, and sample sizes from 10^3 to 10^6 plus n = ∞.The full specifications are deferred to Appendix M.
  • Evaluation metrics: Evaluation uses E1 for global partial-order F1-score, E2 for block-level row-subspace error, and E3 for support leakage.Higher E1 is better, whereas lower E2 and E3 indicate more accurate recovery.
  • Results: Across all scenarios, increasing n improves global ancestral recovery while decreasing client-specific subspace error and support leakage.The same qualitative pattern appears across graph settings and both noise distributions.
  • Results: At n = ∞, the method obtains E1 = 1 and E2 = E3 = 0, matching the population-level theoretical guarantees.Here empirical precision matrices are replaced by the corresponding population precision matrices.

6 Conclusion

The conclusion frames Jigsaw-CRL as a solution to fragmented multi-client CRL, where marginalization changes the locally identifiable causal object. It reports that client fragments can be assembled into a global latent causal order while identifying assumptions and future extensions.

  • Conclusion: Fragmented clients share a global latent causal system but access and intervene on only subsets of its latent variables.This setting differs from shared-latent-space CRL and related multi-view or multi-domain formulations.
  • Conclusion: Marginalizing unavailable latent variables changes each client’s identifiable object from a node-wise DAG to blocks, block-level ancestry, and latent subspaces up to block-level ancestor mixing.The induced mixed graphs reflect dependencies created by latent marginalization.
  • Conclusion: Client-specific fragments can be assembled across clients to recover the global node-level latent causal order.The assembly requires cross-client alignment and coverage conditions that place fragments in a common global coordinate system.
  • Future directions: Future directions include finite-sample guarantees, nonlinear models, more general observation mappings, and stronger identifiability under hard interventions.The conclusion mentions possible exact recovery of A and H as part of stronger hard-intervention results.
  • Assumptions: The paper’s normalized noise covariance assumption is without loss of generality because equivalent reparameterizations preserve the observed distributions.A general feasible noise covariance can therefore be transformed to the identity covariance case.

D Proof of Proposition 1

The proof derives the client’s induced structural equation after partitioning accessed and missing variables, then shows that its ancestral relation exactly restricts the global relation. The resulting covariance and path arguments establish Proposition 1.

  • Induced client model: Partitioning the global latent variables and noise yields the client equation Z_k = A_k Z_k + E_k with E_k combining accessed noise and effects mediated through missing variables.The invertibility of I − [A]_{M_k,M_k} follows from strict upper triangularity.
  • Noise covariance: The induced noise covariance is obtained by substituting E_k = E_{O_k} + B_k E_{M_k} into its covariance expression.The proof uses mutually uncorrelated global exogenous noise and identifies the result with Eq. (12).
  • Ancestral structure: Directed edges in the client graph arise from direct accessed edges or global directed paths whose internal nodes are missing.The finite nilpotent expansion of (I − [A]_{M_k,M_k})^-1 collects these path contributions.
  • Ancestral structure: For accessed nodes, i ≺_k j holds if and only if i ≺ j in the global latent DAG.One direction follows from induced client paths corresponding to global paths, and the other decomposes global paths into client-visible segments.

E Proof of Proposition 2

The proof characterizes block-parent relations by examining directed paths between blocks. A block parent relation requires a witnessing ancestral pair, while its absence excludes ancestral relations for every pair across the blocks.

  • Block-parent relation: A shortest directed path witnessing block ancestry cannot pass through a third block between the parent and child blocks.Such an intermediate block would contradict the absence of a block strictly between a block parent and its child.
  • Non-parent blocks: If block C_{k,j} is not an ancestor of block C_{k,i}, no node in C_{k,j} is an ancestor of any node in C_{k,i}.Otherwise, a node-level ancestral relation would induce the corresponding block-level relation.
  • Block-parent relation: If C_{k,j} is a block parent of C_{k,i}, some node in the first block is an ancestor of a node in the second.This follows directly from the definition of the block-parent relation.
  • Block-parent relation: Therefore, the path contains consecutive nodes u⋆ and v⋆ in the two blocks with u⋆ ∈ P^a_k(v⋆), providing the required witnessing pair.The witness is the first edge crossing from the parent block to the child block along the shortest path.

F Block RQ Decomposition

The block-RQ procedure decomposes Hk into a coefficient matrix Rk and block row-space matrix Qk using a prescribed block order and ancestry. It recovers block-supported coefficients and innovation subspaces, with uniqueness applying to row spaces rather than normalized matrix representatives.

  • Constructive procedure: Algorithm 4 constructs Qk in reverse block topological order by extracting each block’s innovation component after removing ancestor row-space contributions.The corresponding coefficient rows of Rk express each Hk block row using its current block and block ancestors.
  • Block-RQ properties: Each row block of Rk is supported only on its current block and block ancestors.This is the block-support property required by the decomposition.
  • Block-RQ properties: Each block row of Qk is orthogonal to the row space generated by its strict block ancestors.The construction normalizes the resulting innovation rows after projection.
  • Uniqueness: The decomposition is not unique as matrices, but its family of block row spaces is uniquely determined by Hk, the block order, and block ancestry.Different normalized bases can produce different Qk and Rk representatives without changing the identifiable subspaces.
  • Consequences: For nodes in block C, rows of Hk lie in the row space generated by Qk rows indexed by C and its block ancestors.This follows from Hk = RkQk and the support restriction on the corresponding row of Rk.

G Proof of Lemma 1

The proof derives the precision-matrix perturbation caused by a soft intervention and shows that its low-rank generators lie in row spaces associated with the target block and its block ancestors. This establishes the block-ancestral structure needed for identification.

  • Perturbation derivation: The intervention perturbation is analyzed by isolating the target-node precision change and applying the Woodbury identity.The resulting expression is reduced to a combination of terms involving the target-related vectors.
  • Perturbation derivation: The precision perturbation has a low-rank form generated by q and s+d, with coefficients depending on the client and intervention.The displayed expansion uses three scalar coefficients multiplying outer products of these generators.
  • Ancestor restriction: For an intervention targeting block Ck,a, both perturbation generators lie in the row space associated with Ck,a and its block ancestors.The first generator follows from ancestry support, while the second also uses bidirected connectivity within the client block structure.
  • Ancestor restriction: Taking the span of the two generators yields the claimed row-space containment for the intervention perturbation.The proof applies the block-RQ row-space characterization to convert generator support into block-level ancestry.

I Proof of Theorem 1

Theorem 1 is proved by induction over Algorithm 2’s reverse block-topological iterations. Each iteration identifies one true block, recovers its ancestors, and adds the corresponding innovation row space, yielding exact client-level recovery up to intrinsic transformations.

  • Induction invariants: Algorithm 2 maintains an ancestor-closed set of recovered blocks and previously recovered block rows related to Qk by blockwise transformations and order-preserving permutations.These two invariants form the induction hypothesis.
  • Block identification: The block-selection claims rule out partial blocks and unrecovered block parents, so the selected set must equal one whole true block.Minimality of the remaining block partial order supplies a valid next block.
  • Ancestor recovery: The ancestor-recovery step retains true block parents and removes previously recovered blocks that are not true ancestors.The updated partial order therefore remains correct after inserting the newly identified block.
  • Row-space update: Projecting away previously recovered ancestor row spaces produces the innovation subspace for the newly identified block.The normalized vectors constructed by the algorithm span that block’s row space in an admissible block-RQ representation.
  • Conclusion: After all iterations, every client block and its ancestral relation are recovered, with Q̂k = SkPσ,kQk up to blockwise invertible transformations and order-preserving permutations.This is the theorem’s intrinsic ambiguity.

J Proof of Corollary 1

Corollary 1 transfers Theorem 1’s block-RQ recovery to the estimated latent variables. Each recovered variable depends only on the matched true block and its block ancestors, up to within-block transformations and block relabeling.

  • Transformation ambiguity: Theorem 1 implies that the estimated Q̂k differs from Qk only by a block-diagonal invertible transformation and an order-preserving block permutation.These operations preserve the block-associated dependence pattern.
  • Latent-variable recovery: For every estimated variable in a recovered block, its latent representation lies in the span of the true latent variables belonging to that block’s ancestors.The result is stated after matching estimated and true blocks through ψ.
  • Latent-variable recovery: Each recovered block is a linear combination of true latent blocks indexed by its matched block and block ancestors.The ancestor-restricted dependence follows from the support structure of the block-RQ coefficient matrix.

K Proof of Theorem 2

The proof establishes that Algorithm 3 exactly recovers the global ancestral relation up to relabeling, using correct client-level structures and coverage of global cover edges. Supporting lemmas characterize precision-matrix perturbation supports and covariance identities underlying the client-level recovery.

  • Global assembly: Algorithm 3 recovers the global ancestral structure exactly up to relabeling under the bijection ψ : j 7→tj.Its output satisfies (V, ˆ≺) = (V, ≺) after relabeling.
  • Global assembly: The proof obtains equality by showing both ≺⊆ˆ≺ and ˆ≺⊆≺, then using transitivity of the global relation.Every global cover edge is represented by singleton blocks for some client, while every inserted relation is a true global ancestral relation.
  • Global assembly: Client-level correctness ensures that relations between singleton blocks correspond to genuine node-level parent-child relations in the induced client graph.The induced client ancestral relation is the restriction of the global ancestral relation to the client’s accessed variables.
  • Algebraic ingredients: The appendix uses the identity Cov(X)† = HᵀKH for the observed covariance pseudoinverse in the latent linear model.This follows from the full-column-rank observation matrix and invertible latent covariance assumptions.
  • Perturbation supports: A soft intervention changes only the targeted structural row, so directed perturbation support is confined to the target’s induced parent coordinates.The support is indexed by ρk(pak(t)).
  • Perturbation supports: The corresponding covariance perturbation affects only the off-diagonal row and column associated with bidirected neighbors of the target.Its support is indexed by ρk(spk(t)).

M.6 Sensitivity and scalability analysis

The experiments test sensitivity to latent dimension, client count, and coverage across finite-sample scenarios. Recovery improves with sample size, while global assembly depends strongly on client coverage and number, and runtime depends more on client-level dimensions and block search than on client count.

  • Finite-sample behavior: Across all settings, E1 increases with sample size while E2 and E3 generally decrease.This pattern is evaluated across three graph settings and two noise settings.
  • Latent dimension: At n = ∞, E1 decreases from 1.00 to 0.77 as p increases from 10 to 40, while E2 ≤0.05 and E3 ≤0.02.Incomplete coverage primarily affects global assembly rather than client-level recovery in this experiment.
  • Clients and coverage: At n = ∞, E1 increases from 0.34 to 1.00 as K increases from 5 to 20 and from 0.82 to 1.00 as q increases from 0.5 to 0.8.The trends are consistent with Assumption 3 being satisfied more frequently.
  • Runtime: Runtime increases from 0.17 to 4.23 seconds as p grows from 10 to 40, but only from 0.25 to 0.49 seconds as K grows from 5 to 20.The reported runtime uses population precision-matrix inputs and excludes data generation and precision estimation.
  • Runtime: Runtime is not necessarily monotone in q because higher coverage enlarges client dimensions but generally reduces induced block sizes and combinatorial block search.Thus, coverage affects both matrix dimensions and the difficulty of block search.
Loading 2608.28991v1…