Tensor Network Moral Graph Recovery of Discrete Probability Distributions

Á. Troyano Olivas; Chi-Hang Fred Fung; Hans H. Brunner; Momtchil Peev; Vicente Martin

Source-linked AI summary

Tensor Network Moral Graph Recovery of Discrete Probability Distributions

Á. Troyano Olivas, Chi-Hang Fred Fung, Hans H. Brunner, Momtchil Peev, Vicente Martin

arXiv:2609.09258v1Sep 8, 2026stat.MLcs.ITcs.LGmath.PRquant-ph

TL;DR

The paper addresses recovery of a causal DAG’s moral graph from a discrete observational distribution. It uses nuclear-norm-regularized FCTNs whose bond corrections expose the effective graph, and proves exact recovery for every optimal zero-error solution under faithfulness, positivity, and no implicit rerouting, with approximate guarantees for ε > 0.

Problem
The paper seeks to recover the moral graph of a causal DAG from a probability distribution over discrete variables.
Method
It decomposes the distribution with FCTNs whose all-ones bond baselines receive low-rank corrections penalized through a variational nuclear-norm formulation.
Results
Under faithfulness, positivity, and no implicit rerouting, every optimal zero-error FCTN has effective graph exactly equal to the moral graph.
Takeaways & Limitations
The effective graph is read directly from optimized bond matrices, while approximate recovery is controlled using conditional-mutual-information continuity bounds.
Takeaways & Limitations
Exact contraction costs O(d^m · r_max^(m−1)), limiting the method to small m, and the recovery proofs require no implicit rerouting.

Abstract

from arXiv · show

We present a method for recovering the moral graph of a causal DAG from a probability distribution over discrete variables, using fully connected tensor networks (FCTNs) with nuclear-norm-regularized bond corrections. Each bond matrix is parameterized as a baseline all-ones matrix plus a low-rank correction $C_{ij} = U_{ij}V_{ij}^\top$, and the nuclear norm of the correction implemented via the variational Frobenius norm penalty on the factors drives unnecessary bonds to zero. We prove that under faithfulness, positivity, and a no-implicit-rerouting assumption on the local tensor architecture, \textbf{every} optimal FCTN with zero reconstruction error $\varepsilon = 0$ has effective graph exactly equal to the moral graph. For the approximate regime ($\varepsilon > 0$), we provide explicit recovery bounds using the Fannes-Audenaert continuity of conditional mutual information, and derive a sufficient condition on the regularization parameter $β$. The effective graph is read directly from the optimized bond matrices.

1 Introduction

The paper proposes recovering a causal DAG’s moral graph from observational discrete distributions using sparsity-regularized fully connected tensor networks. Its theorems establish exact recovery under structural assumptions and approximate guarantees based on conditional-mutual-information continuity.

Method: The method decomposes the observed distribution into an FCTN with all-ones baselines plus low-rank bond corrections, whose nuclear-norm penalty removes unnecessary bonds.The effective graph is obtained from bonds with nonzero corrections.
Recovery mechanism: Non-moral edges are driven to zero because they have zero conditional mutual information and rerouting them is strictly suboptimal under the architectural assumption.The argument rules out null, implicit, and explicitly rerouted corrections.
Approximate recovery: For ε > 0, Fannes–Audenaert continuity of conditional mutual information yields explicit recovery bounds and a sufficient condition on β.The approximate theorem shows convergence toward the moral graph as ε approaches zero.
Exact recovery: Every optimal zero-error FCTN recovers exactly the moral graph under faithfulness, positivity, and no implicit rerouting.The result applies to all optimal solutions, not merely to an existence result.

2 Problem Statement

The problem is to recover the moral graph of an unknown causal DAG from its joint distribution over discrete variables. The proposed FCTN representation is designed so that optimization exposes the target edge set directly.

Target: The goal is to recover the moral-graph edge set from a faithful distribution over discrete variables alone.The distribution is assumed faithful to an unknown causal DAG.
Representation: The method represents the distribution with FCTN bonds parameterized by fixed all-ones baselines and trainable low-rank corrections.Unnecessary bonds are driven to zero by regularization.
Output: The effective graph is read directly from the optimized solution, with the formal ansatz, objective, and recovery guarantees developed in later sections.This makes graph recovery an output of the tensor-network optimization.

3 Definitions

This section defines the distributions, information quantities, graphical concepts, and FCTN components used to characterize moral-graph recovery. In particular, bonds separate an independent baseline from corrections whose nonzero structure defines the effective graph.

Information quantities: Conditional mutual information measures dependence between variable sets given another set, and vanishes exactly under conditional independence.The central special case conditions on all remaining variables.
Graphical structure: d-separation encodes a DAG’s conditional-independence structure, with faithfulness making the graphical and distributional criteria equivalent.This correspondence underpins the recovery lemmas.
Tensor networks: An FCTN represents a joint distribution by contracting local tensors connected by bond matrices across every pair of sites.Each bond has a fixed maximum dimension and connects two physical-variable sites.
Bond parameterization: Each bond decomposes into an all-ones disconnected baseline and a correction Cij = UijVij^T that captures deviation from independence.The baseline is fixed, while the correction controls whether and how strongly two sites share information.
Bond parameterization: When Cij = 0, the bond produces a product of marginals rather than zeroing the tensor-network output.This establishes the paper’s operational notion of a disconnected bond.
Effective graph: The effective graph contains precisely bonds with nonzero correction nuclear norm, while the correction’s effective rank counts its nonzero singular directions.The nuclear norm measures total deviation from the disconnected state.

4 Objective Function

The objective combines reconstruction error with a regularization penalty on low-rank bond corrections. A variational Frobenius-factor penalty implements the correction nuclear norm and drives unnecessary corrections to zero.

Objective: The objective minimizes reconstruction error plus β times a penalty on the factorized bond corrections.The trainable parameters include local tensors and the factors Uij and Vij, while the all-ones baselines remain fixed.
Nuclear-norm regularization: The variational Frobenius penalty on Uij and Vij implements the nuclear norm of Cij = UijVij^T.At a balanced factorization, the penalty equals the sum of the correction’s singular values.
Optimization: The nuclear-norm identity is minimized by a balanced factorization, so optimization can penalize correction magnitude without computing singular-value decompositions.The factors are updated directly by standard backpropagation.
Graph output: The regularizer drives unnecessary corrections to zero, making the effective graph of the optimal FCTN the method’s direct structural output.The fixed baseline is not penalized; only deviations from it are.

5 Theoretical Framework

Under faithfulness and positivity, moral edges correspond to positive conditional mutual information while non-moral edges have zero conditional mutual information. Continuity bounds then transfer these distinctions to approximate reconstructions.

Assumptions: Faithfulness and positivity provide the graph–independence correspondence and support the Hammersley–Clifford-based reasoning used by the recovery analysis.Faithfulness supplies the d-connection to dependence direction, while positivity supports the required factorization and graphoid properties.
5.1 Basic Lemmas: Moral edges have positive conditional mutual information under faithfulness, covering both direct causal links and co-parent relationships in v-structures.Conditioning on all variables except the pair leaves the relevant trail d-connected.
5.1 Basic Lemmas: Non-moral edges have zero conditional mutual information when conditioning on every other variable.The proof uses d-separation of all trails under the full conditioning set.
5.1 Basic Lemmas: For each variable, the conditional distribution given all remaining variables depends only on its moral neighbors.Non-moral variables can be removed from the conditioning set using conditional independence and the intersection property.
5.2 Continuity of Conditional Mutual Information: The conditional mutual information continuity lemma bounds changes caused by an L1 perturbation using the relevant marginal support size and binary entropy.The paper applies this result to the L2 reconstruction error through an explicit continuity function.

6 Tensor Network Properties

Tensor-network rewiring can remove a nonzero bond while preserving the represented distribution, but it incurs positive penalty overhead. This rerouting cost makes direct representations preferable, subject to the unresolved possibility of implicit rerouting inside saturated local tensors.

6.1 Edge Rewiring: Any nonzero correction bond can be removed and explicitly rerouted through an intermediate node without reconstruction error.The correction is factorized through neighboring bonds while the removed bond returns to its all-ones baseline.
6.2 Rerouting Cost: Longer or split rerouting paths incur aggregate pass-through cost at least K_ij, so every explicit rerouting has strictly positive overhead.The single-intermediate-node route is the cheapest explicit rerouting case.
6.2 Rerouting Cost: The effective graph, rather than the raw tensor-network edge set, is the structure identified by the penalized solution.A star representation can encode the same distribution but at higher penalty cost.
6.2 Rerouting Cost: Explicit rerouting increases the penalized objective by βK_ij, where K_ij is the rank of the removed correction.The increase comes from identity pass-through factors added to the two intermediate bonds.
6.2 Rerouting Cost: The rerouting-cost argument does not formally exclude implicit rerouting through saturated local tensors with enough capacity to encode multi-site dependencies.Constraining local tensors, such as with a Tucker decomposition, is proposed as a way to remove this capacity.

7 Exact Recovery (Zero Error)

Under faithfulness, positivity, and no implicit rerouting, every optimal zero-error FCTN recovers exactly the causal DAG’s moral graph. Moral edges cannot be omitted, while non-moral corrections are eliminated as unnecessary or suboptimal.

Moral-edge inclusion: Moral edges must retain nonzero corrections because rerouting their conditional dependence through indirect bonds is strictly more expensive.The contradiction preserves the represented distribution and zero reconstruction error while reducing the penalty.
Assumptions: The no-implicit-rerouting assumption requires that local tensors cannot internally reconstruct non-adjacent conditional dependencies from incident bonds.A sufficient heuristic condition is rmax < d; this condition held in the experiments except for the fork model, where rmax = d and no implicit rerouting was observed.
Proof scope: The proof’s stronger target-direction clause is used only in Case 2, and a formal route to remove it is left for future work.Lemma 7 suggests that conditionals depend only on moral neighbors, potentially allowing absorption through moral bonds alone.
Non-moral-edge exclusion: Non-moral edges have zero correction because conditional independence makes them unnecessary, while implicit rerouting is excluded and explicit rerouting is penalized.The three-case contraction analysis shows that null, target-direction, and pass-through corrections each contradict optimality under the architectural assumption.
Exact recovery: Every optimal zero-error FCTN has effective graph exactly equal to the moral graph.The result combines inclusion of all moral edges with elimination of every non-moral correction, so it is a uniqueness statement over all optimal solutions.

8 Approximate Recovery (ε > 0)

For approximate reconstructions, continuity of conditional mutual information yields explicit conditions under which moral edges remain and spurious edges become negligible. As reconstruction error tends to zero, the effective graph converges to the moral graph.

Method: Approximate recovery combines the zero-error penalty argument with continuity control, while conditional mutual information provides a post-hoc diagnostic.The diagnostic is evaluated on the reconstructed distribution rather than directly on the target distribution.
Approximate recovery: If f(ε*) < δmin, every moral edge retains a nonzero correction in the optimal approximate reconstruction.Here δmin is the smallest conditional mutual information among moral edges, and f(ε*) is the continuity-bound deviation.
Spurious-edge control: Spurious non-moral edges have reconstructed conditional mutual information at most f(ε*) and can be identified by thresholding at τ = f(ε*).The result follows because non-moral edges have zero conditional mutual information in the target distribution.
Convergence: As ε* → 0, f(ε*) → 0, spurious edges are pruned, and the effective graph converges to the moral graph.The continuity bound eventually satisfies the lower-bound condition needed to preserve moral edges.

9 Synthetic Experiments

Across four synthetic causal models, the rank-based effective-graph criterion exactly recovered each generating DAG’s moral graph. The post-hoc conditional-MI diagnostic was exact only when reconstruction error made the continuity bound informative.

Main result: The rank-based criterion recovered the moral graph exactly in all four synthetic models.The models were a chain, fork, collider, and diamond generated from positive, faithful conditional probability tables.
Model-specific recovery: The recovered collider graph included the moral edge between co-parents X and Y, while the diamond recovered both v-structure moralization and chain edges.These cases test recovery of both co-parent moralization and extended chain structure.
Post-hoc diagnostic: The conditional-MI diagnostic at τ = 10^-3 was exact for the fork and collider but produced a spurious X–Y edge for the chain and retained only one of four moral edges for the diamond.The diagnostic operated on the reconstruction, not directly on the target distribution.
Error sensitivity: The rank-based output remained exact when reconstruction error made the continuity bound vacuous for the chain and diamond.The reported reconstruction error was small for the fork and collider but exceeded one for the chain and diamond.

10 Limitations and Discussion

The method’s guarantees depend on the no-implicit-rerouting assumption, and optimization and contraction impose additional practical limits. It recovers an undirected moral graph, not a fully oriented causal DAG.

Theoretical scope: Both exact and approximate recovery guarantees rely on the no-implicit-rerouting assumption, including its stronger target-direction clause for the upper bound.A formal route to dispense with that stronger clause remains open, although Lemma 7 suggests one.
Optimization: The objective is non-convex, so gradient methods provide no global-optimality certificate.Experiments found that small perturbations did not change the discrete effective graph, but rigorous landscape analysis remains open.
Computational cost: Exact FCTN contraction costs O(d^m · r^(m−1)), limiting the method to small m, approximately m ≲ 10 on commodity hardware.The limitation follows from the FCTN’s treewidth m − 1.
Causal interpretation: The method recovers an undirected moral graph; orienting it into a causal DAG requires interventions or score-based orientation rules.Thus graph recovery does not by itself identify causal edge directions.

11 Conclusions

The paper presents nuclear-norm-regularized FCTNs for recovering a causal DAG’s moral graph from discrete observational distributions. Under stated assumptions, every optimal zero-error network recovers the moral graph, while broader DAG recovery and empirical-sample guarantees remain open.

11 Conclusions: The method recovers a causal DAG’s moral graph from a discrete-variable probability distribution using FCTNs with nuclear-norm-regularized bond corrections.The effective graph is determined by the surviving optimized bond corrections.
11 Conclusions: Under faithfulness, positivity, and no implicit rerouting, every optimal zero-error FCTN has effective graph exactly equal to the moral graph.The result is universal over optimal solutions rather than merely existential.
11 Conclusions: Synthetic experiments confirm exact recovery in all cases tested.
11 Conclusions: Open directions include larger-scale approximate contraction, faster optimization, interventional-data integration, non-convex landscape analysis, and sample-complexity bounds.
11 Conclusions: The moral graph is identifiable from observational conditional-independence structure because it is invariant across Markov-equivalent DAGs.Equivalent DAGs share the same skeleton and unshielded v-structures, which determine moralization.
11 Conclusions: Equal moral graphs do not imply Markov equivalence, so moral-graph recovery does not uniquely identify the full causal DAG.The paper gives two DAGs with the same moral graph but different conditional-independence relations.

Appendix B. Choosing the Regularization Parameter β

Appendix B explains how the regularization parameter β controls approximate reconstruction error while preserving exact-recovery guarantees at zero error. It derives a sufficient β condition using weakest moral-edge dependence, representation cost, dimensionality, and support size, with non-moral edges handled by continuity bounds and thresholding.

Appendix B. Choosing the Regularization Parameter β: At ε*=0, exact recovery holds for any β>0 because the objective becomes J=βP, so β does not change the optimal zero-error solution.
Appendix B. Choosing the Regularization Parameter β: The full optimization satisfies ε*+βP*≤βP0, providing the starting bound for relating reconstruction error to β.
Appendix B. Choosing the Regularization Parameter β: Rerouting a moral-edge dependence is suboptimal for every β>0 because an equivalent representation with a direct correction has lower penalty.This routing argument preserves the contraction output while reducing corrections on indirect bonds.
Appendix B. Choosing the Regularization Parameter β: For ε*>0, β must be small enough that the continuity-bound error remains below the weakest moral-edge conditional mutual information δmin.The sufficient condition compares δmin with the penalty cost P0, dimensionality D, and maximum marginal support size d.
Appendix B. Choosing the Regularization Parameter β: The zero-error penalty P0 can be estimated by optimizing with very small β and measuring the total correction nuclear norm.
Appendix B. Choosing the Regularization Parameter β: At positive error, spurious non-moral edges are controlled by a conditional-mutual-information bound and can be removed by thresholding at τ=f(ε*).The β condition is needed for the lower bound on moral edges, not for the upper bound on non-moral edges.