📊 statistics

Tensor Network Moral Graph Recovery of Discrete Probability Distributions

This paper proposes a method using nuclear-norm-regularized fully connected tensor networks to recover the moral graph of a causal DAG from discrete probability distributions, proving that under specific assumptions, optimal networks with zero reconstruction error exactly identify the moral graph while providing explicit recovery bounds for approximate regimes.

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

Published 2026-09-10

📖 5 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Understanding how the world works often begins with mapping the invisible threads that connect events. In the realm of data science, researchers try to uncover these threads by looking at patterns in numbers, asking whether one thing causes another or if they simply happen to occur together. A central challenge in this field is distinguishing between direct cause-and-effect relationships and more complex, indirect connections. When scientists study a system of variables, they often look for a specific type of map called a moral graph. This map connects any two variables that are directly linked, as well as any two variables that share a common child, even if they do not directly influence each other. It serves as a crucial intermediate step in understanding the full causal structure of a system, revealing which pieces of information are truly intertwined without needing to perform physical experiments or interventions.

For decades, researchers have relied on statistical tests to draw these maps, checking if variables remain independent when other factors are held constant. However, these traditional methods often struggle when data is limited or when relationships are subtle, leading to errors in the final map. A new approach, developed by a team of researchers at the Heisenberg Research Center and the Center for Computational Simulation, offers a fundamentally different way to solve this puzzle. Instead of testing variables one by one, they treat the entire system as a single, interconnected web of information. By using a mathematical structure known as a tensor network, they can decompose a complex probability distribution into smaller, manageable pieces. The key innovation lies in how they handle the connections between these pieces. They start with a fully connected web where every variable is linked to every other, but they design the system so that unnecessary links naturally fade away.

The researchers achieved this by parameterizing the connections between variables as a baseline state plus a small, adjustable correction. Think of the baseline as a default setting where variables are independent, and the correction as the specific information that binds them together. To find the true structure, the team applied a mathematical pressure, or penalty, that discourages these corrections from becoming too large or complex. This pressure acts like a filter, driving the corrections for variables that are not truly connected down to zero. As the system optimizes itself to match the observed data, the unnecessary links vanish, leaving behind only the bonds that carry genuine information. The result is a clean, effective map that emerges directly from the optimization process, rather than being constructed through a series of discrete tests.

In their study, the authors proved that under specific, reasonable conditions, this method perfectly recovers the moral graph. They demonstrated that if the data is generated by a true causal system and the model is allowed to fit the data without error, the resulting map will contain exactly the correct connections and no others. The proof relies on the idea that rerouting information through an intermediate variable is always more "expensive" in terms of mathematical complexity than representing a direct connection. Therefore, if a direct link exists, the system will prefer it. Conversely, if no direct link exists, the system finds that trying to force a connection through a non-moral edge is inefficient and will naturally suppress it. This logic holds true for every optimal solution the system finds, ensuring that the result is not just a lucky guess but a mathematically guaranteed outcome for perfect data.

To test their theory, the researchers ran simulations on several small, known systems, including chains of events, branching structures, and complex diamond-shaped patterns. In every case, the method successfully identified the correct moral graph, recovering the exact set of connections predicted by the underlying causal rules. The team also explored what happens when the data is not perfect and the model cannot fit the observations exactly. They showed that even with small errors, the method remains robust, providing clear bounds on how much the recovered map might deviate from the truth. The experiments confirmed that the method works reliably, recovering the correct structure in all tested scenarios, from simple chains to more intricate networks involving shared causes and common effects.

This work represents a significant shift in how causal structures can be discovered. By replacing rigid, step-by-step statistical tests with a continuous, differentiable optimization process, the researchers have created a tool that is both theoretically sound and practically effective. The method does not require the system to be acyclic or the data to be perfect, and it avoids the combinatorial explosion of searching through every possible arrangement of variables. Instead, it lets the structure of the data itself dictate the shape of the final map. While the current experiments are limited to small systems due to the computational cost of handling large networks, the approach opens a new path for understanding complex causal relationships. It suggests that by viewing the problem through the lens of tensor networks, researchers can uncover the hidden architecture of cause and effect with a clarity that was previously difficult to achieve.

Technical Summary: Tensor Network Moral Graph Recovery of Discrete Probability Distributions

1. Problem Statement

The paper addresses the problem of causal structure learning for systems of discrete random variables. Specifically, the goal is to recover the moral graph of an unknown causal Directed Acyclic Graph (DAG) solely from observational data (a joint probability distribution $p$ ).

The moral graph is an undirected graph where an edge exists between two variables if they share a direct causal link or are co-parents in a $v$ -structure. It is a fundamental invariant of the Markov equivalence class of a DAG and can be identified from purely observational data without interventions. Existing methods typically fall into two categories:

Constraint-based methods (e.g., PC algorithm): Rely on conditional independence (CI) tests, which suffer from finite-sample degradation and weak dependency detection.
Score-based methods (e.g., GES, NOTEARS): Reformulate learning as continuous optimization over DAGs but face combinatorial search spaces and require acyclicity constraints.

This work proposes a fundamentally different approach that avoids discrete CI tests and DAG-space search by decomposing the probability distribution into a Fully Connected Tensor Network (FCTN).

2. Methodology

2.1 Tensor Network Ansatz

The method represents the joint distribution $p(V_1, \dots, V_m)$ as a contraction of a fully connected tensor network. The network consists of:

Local Tensors ( $N^{[i]}$ ): Associated with each variable $V_i$ .
Bond Matrices ( $B_{ij}$ ): Connect every pair of sites $\{i, j\}$ .

Crucially, each bond matrix is parameterized as a baseline plus a low-rank correction:
$B_{ij} = J_{ij} + C_{ij} = J_{ij} + U_{ij}V_{ij}^\top$
where $J_{ij}$ is a fixed all-ones matrix (representing the disconnected baseline where sites are independent) and $C_{ij}$ is a low-rank correction matrix. The factors $U_{ij}$ and $V_{ij}$ are trainable parameters.

2.2 Objective Function and Regularization

The learning objective minimizes the reconstruction error between the true distribution $p$ and the tensor network approximation $TN(\theta)$ , regularized by a nuclear-norm penalty on the corrections:
$J(\theta) = \|p - TN(\theta)\|_2^2 + \frac{\beta}{2} \sum_{\{V_i, V_j\}} (\|U_{ij}\|_F^2 + \|V_{ij}\|_F^2)$
The penalty term implements the nuclear norm $\|C_{ij}\|_*$ via the variational identity $\|C_{ij}\|_* = \min_{C=UV^\top} \frac{1}{2}(\|U\|_F^2 + \|V\|_F^2)$ . This continuous, differentiable penalty drives unnecessary bond corrections to zero.

2.3 Effective Graph Recovery

The effective graph $G_{eff}$ is defined as the set of edges where the correction matrix has a non-zero nuclear norm (or effective rank $>0$ ):
$G_{eff} = \{ \{V_i, V_j\} : \|C_{ij}\|_* > 0 \}$
The method posits that the optimizer will naturally prune non-moral edges (setting $C_{ij} = J_{ij}$ ) while retaining moral edges, allowing the graph structure to emerge directly from the optimized parameters.

3. Theoretical Framework and Key Contributions

The paper provides rigorous theoretical guarantees for exact and approximate recovery under specific assumptions: Faithfulness, Positivity, and a No-Implicit-Rerouting assumption.

3.1 Core Mechanism: Rerouting Cost

A central lemma (Lemma 11) establishes that rerouting a correlation through an intermediate node is strictly more expensive than representing it directly.

If a dependency exists between $V_i$ and $V_j$ , representing it via a direct bond $C_{ij}$ is optimal.
If the direct bond is removed, the dependency must be "rerouted" through other nodes (e.g., $V_i \to V_\omega \to V_j$ ). This requires identity pass-through matrices that increase the Frobenius norm penalty by the rank of the correction ( $K_{ij}$ ).
Consequently, the optimizer prefers direct bonds for genuine conditional dependencies.

3.2 Exact Recovery (Zero Error)

Theorem 16 states that under faithfulness, positivity, and the no-implicit-rerouting assumption, every optimal FCTN with zero reconstruction error ( $\varepsilon = 0$ ) has an effective graph exactly equal to the moral graph.

Lower Bound (Theorem 13): Moral edges must have non-zero corrections. If a moral edge were zero, the dependency would have to be rerouted, incurring a higher penalty, contradicting optimality.
Upper Bound (Theorem 15): Non-moral edges must have zero corrections. Non-moral edges carry zero conditional mutual information (CMI). Any non-zero correction on such an edge would either be a null artifact, an explicit rerouting (suboptimal), or an implicit rerouting (ruled out by Assumption 3).

3.3 Approximate Recovery (Non-Zero Error)

For the regime where reconstruction error $\varepsilon > 0$ , the paper derives explicit recovery bounds using the Fannes–Audenaert continuity of conditional mutual information.

Theorem 18: If the reconstruction error is sufficiently small such that the continuity bound $f(\varepsilon)$ is less than the minimum conditional mutual information of true moral edges ( $\delta_{min}$ ), the effective graph contains all moral edges.
Spurious edges (non-moral) with non-zero corrections are bounded by $f(\varepsilon)$ , allowing them to be pruned via thresholding.

4. Experimental Results

The authors validated the method on four synthetic discrete distributions generated from known causal DAGs:

Chain: $X \to Z \to Y$
Fork: $Z \to X, Z \to Y$
Collider: $X \to Z \leftarrow Y$
Diamond: A combination of a $v$ -structure and a chain.

Findings:

In all four cases, the rank-based effective graph extracted from the optimized bond matrices coincided exactly with the ground-truth moral graph.
The method successfully identified the moral edge between co-parents in the collider and diamond structures.
A post-hoc Conditional Mutual Information (CMI) diagnostic on the reconstructed distribution was less robust when reconstruction error was high, confirming the theoretical necessity of the rank-based criterion over simple CMI thresholding in the approximate regime.

5. Significance and Claims

The paper claims the following significance:

Uniqueness of Solution: Unlike many structure learning results that prove existence, this work proves a uniqueness statement: every optimal zero-error solution yields the correct moral graph, not just some.
Continuous Relaxation of Structure Learning: It replaces discrete CI tests with a continuous, differentiable objective function, leveraging the geometry of tensor networks.
Theoretical Rigor: It provides explicit bounds for approximate recovery, linking reconstruction error directly to graph recovery guarantees via information-theoretic continuity.
Novelty in Causal Discovery: It is the first to apply nuclear-norm regularized bond corrections in tensor networks specifically for recovering the moral graph of causal DAGs, distinguishing it from standard tensor network applications in physics or compression.

6. Limitations

The authors acknowledge several limitations:

No-Implicit-Rerouting Assumption: The theoretical guarantees rely on the assumption that local tensors cannot internally compute multi-variable dependencies to substitute for direct bonds. While empirically satisfied in experiments (where bond dimensions were smaller than state spaces), a formal structural proof is left for future work.
Non-Convexity: The objective function is non-convex, meaning global optimality is not guaranteed by gradient descent, though the discrete nature of the effective graph makes the solution robust to small perturbations.
Scalability: The Fully Connected Tensor Network has a treewidth of $m-1$ , leading to exponential contraction costs $O(d^m r^{m-1})$ . This limits the method to small numbers of variables ( $m \lesssim 10$ ) on commodity hardware. The authors suggest approximate contraction strategies (e.g., truncation, renormalization) as a path forward for larger systems.
Causal Orientation: The method recovers the undirected moral graph. Orienting edges to recover the full DAG requires additional information (interventions) or separate orientation rules.