📊 statistics

Learning a directed acyclic graph with additive heteroscedastic errors

This paper introduces RESQUE, a novel iterative method that leverages additive heteroscedastic errors in structural equation models to achieve identifiability and recover the causal structure and topological order of directed acyclic graphs, even in high-dimensional settings where the number of variables grows with the sample size.

Original authors: Xintao Xia, Li Chen, Yue Hu, Chunlin Li

Published 2026-05-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Xintao Xia, Li Chen, Yue Hu, Chunlin Li

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

Imagine you are a detective trying to figure out the order of events in a mystery, but you only have a blurry photo of the aftermath. You can see that a window is broken and a vase is shattered, but you don't know if the rock hit the window first (causing the glass to fly and break the vase) or if the vase fell first (shattering the glass and hitting the window).

In the world of data science, this is called Causal Discovery. Researchers want to know: "Did A cause B, or did B cause A?" Usually, looking at just the average behavior of data (the "mean") isn't enough to solve this mystery. It's like looking at the blurry photo and seeing only the broken pieces; you can't tell the story.

This paper introduces a new detective tool called RESQUE (Residual Simultaneous Quantile Estimation) that solves this mystery by looking at something most people ignore: the noise.

The Core Idea: Listening to the Static

In most data models, scientists assume the "noise" (the random errors or unexpected jitters in the data) is the same everywhere. They treat it like a steady, quiet hum.

However, the authors noticed that in the real world, noise is often heteroscedastic. This is a fancy way of saying the "static" gets louder or quieter depending on the situation.

The Analogy: Imagine a radio. When you are close to the station, the music is clear and the static is low. When you drive far away, the music gets fuzzy and the static gets loud. The volume of the static tells you how far you are from the source.

The paper argues that this changing volume of static (variance) holds the secret to the direction of causality. If the "static" of Variable B changes depending on the value of Variable A, but the "static" of A doesn't change based on B, then A is likely the cause and B is the effect.

The New Method: RESQUE

The authors built a two-step process to find these clues:

The "Subtract and Listen" Step: First, they try to predict the average behavior of the data. Whatever the prediction misses is the "residual" (the leftover noise). They take the logarithm of this leftover noise to measure its "loudness."
The "Quantile Detective" Step: Instead of just looking at the average loudness, they look at the noise at different levels (like the quietest 10% of the time, the middle 50%, and the loudest 10%).
- The Magic Trick: If a variable is a "sink" (a final destination in the chain of events, with no children), the relationship between its parents and its noise "loudness" stays the same no matter which level of noise you look at. It's like a lighthouse beam that looks the same whether you are looking at the top or the bottom of the beam.
- If the relationship changes depending on the noise level, that variable is likely in the middle of the chain, not the end.

By repeatedly finding these "sinks" (the end of the line) and removing them, the algorithm works backward to reconstruct the entire timeline of events, from the very first cause to the final effect.

Why This Matters

It works with "Bounded" Data: Many previous methods failed when data was limited (like a test score that can't go below 0 or above 100). This new method works perfectly even when the data is stuck within a specific range.
It doesn't need a perfect map: Older methods often required the researcher to guess the exact shape of the relationship (a specific mathematical formula). RESQUE is more flexible; it just looks for patterns in the noise without needing to know the exact formula beforehand.
It handles high dimensions: It can solve these puzzles even when there are hundreds of variables involved, not just two.

Real-World Tests

The authors tested their detective tool on two types of cases:

Fake Data: They created thousands of computer-generated scenarios with known causes and effects. RESQUE solved them more accurately than other popular methods, especially when the "noise" carried the most important clues.
Real Biology Data: They applied it to a famous dataset about human immune cells (proteins). In this dataset, the "noise" (variance) was crucial. RESQUE correctly identified more of the true biological connections than other methods, proving that listening to the "static" reveals secrets that the "average" data hides.

The Bottom Line

This paper teaches us that chaos is informative. By paying attention to how the "randomness" of data changes depending on the situation, we can finally figure out the true direction of cause and effect, even in complex, messy systems where traditional methods fail. It's a new way of listening to the data that turns the background noise into a clear signal.

Technical Summary: Learning a Directed Acyclic Graph with Additive Heteroscedastic Errors

Problem Statement
The paper addresses the challenge of causal discovery for Directed Acyclic Graphs (DAGs) using observational data under Structural Equation Models (SEM) with additive heteroscedastic errors. While existing methods often rely on assumptions of homoscedasticity (constant variance) or specific error distributions (e.g., non-Gaussian linear models like LINGAM), real-world data frequently exhibit heteroscedasticity where the noise variance depends on parent variables. A significant gap in the literature is the lack of multivariate causal discovery methods that effectively leverage these variance signals, particularly for bounded variables where traditional identifiability results often fail. Furthermore, likelihood-based methods in heteroscedastic settings are prone to parametric misspecification, and independence testing methods often struggle in high dimensions or require sample splitting.

Methodology: RESQUE
The authors propose Residual Simultaneous Quantile Estimation (RESQUE), a novel iterative procedure designed to recover the topological order and graph structure of a DAG. The method operates under a location-scale noise model:
$X_j = f_j(X_{PA(j)}) + g_j(X_{PA(j)})\varepsilon_j$
where the noise term $\varepsilon_j$ is independent of the parents, but its scale $g_j(\cdot)$ may depend on them.

The RESQUE algorithm proceeds in two main stages per iteration:

Residual Construction: A least squares regression is performed to estimate the mean function $f_j$ , yielding residuals. The log-absolute residuals are then computed to transform the problem into estimating the conditional scale function.
Composite Quantile Regression: A penalized composite quantile regression is applied to the transformed residuals across multiple quantile levels ( $\tau_1, \dots, \tau_K$ $τ_{1}, \dots, τ_{K}$ ).
- Sink Node Identification: The core insight is that for a sink node (a node with no children), the conditional scale coefficients are invariant across different quantile levels. The algorithm identifies sink nodes by checking if the estimated coefficient vectors across all quantiles shrink to the same value (using a penalty term that encourages equality).
- Iterative Removal: Identified sink nodes are removed from the graph, and the process repeats on the remaining subgraph. This recursive removal recovers the topological order from sinks to sources.
- Graph Structure Recovery: Once the order is established, the method uses variable selection (via folded concave penalties or hard thresholding) on both the mean and variance components to identify the specific directed edges.

Key Contributions

New Identifiability Results: The paper establishes theoretical identifiability for DAGs with additive heteroscedastic errors. Crucially, it unifies the theory for both bounded and unbounded continuous variables. The authors demonstrate that causal discovery among bounded variables requires milder conditions than for unbounded variables, leveraging boundary properties to ensure identifiability without requiring unbounded support.
Novel Estimation Procedure (RESQUE): The authors introduce an iterative framework that exploits the invariance of conditional scale coefficients across quantiles to identify sink nodes. This approach circumvents the need for likelihood optimization (avoiding parametric misspecification) and transforms independence testing into a feature selection problem, thereby avoiding the pitfalls of sample splitting and high-dimensional independence tests.
Theoretical Guarantees: The paper provides consistency results for both the topological order and the graph structure. It proves that RESQUE consistently recovers the true DAG even when the number of variables diverges with the sample size, provided sparsity assumptions hold.

Empirical Results
The performance of RESQUE was evaluated through simulation studies and real-data benchmarks:

Synthetic Data: In both low-dimensional and high-dimensional settings (up to $p=100$ ), RESQUE outperformed existing methods (CAM, rank-PC, TL, NOTEARS) in terms of False Discovery Rate (FDR) and True Positive Rate (TPR). It demonstrated robustness across different graph structures (Random, Tree, Scale-free) and error distributions (Uniform, Beta, Gaussian). Notably, while NOTEARS showed low FDR, it suffered from near-zero TPR in high-dimensional settings after standardization, whereas RESQUE maintained high accuracy.
Sachs' Flow Cytometry Dataset: Applied to a dataset of 11 proteins, RESQUE identified 13 out of 20 consensus edges, achieving the highest TPR and lowest Structural Hamming Distance (SHD) among compared methods. Analysis revealed that 4 of the correctly identified edges were detected only through the variance component, highlighting the method's ability to extract causal information encoded in heteroscedasticity.
CauseEffectPairs Collection: On a collection of 99 univariate pairs, RESQUE achieved an accuracy of 71.1%, significantly outperforming competitors like CAM (56.7%) and NOTEARS (25.8%). The authors attribute the failure of linear methods to the nonlinearity and heteroscedasticity present in the data.

Significance and Claims
The paper claims that its central message is twofold: first, bounded variables facilitate the identifiability of heteroscedastic SEMs, and second, structured causal signals embedded in heteroscedastic patterns should be systematically exploited for multivariate causal discovery. By moving beyond mean-based modeling, RESQUE provides a principled framework for causal discovery that is robust to parametric misspecification and effective in high-dimensional settings where variance encodes critical causal direction information. The authors position this work as a step toward building automated learning and reasoning systems that can handle complex, real-world data structures where variance is not merely noise but a source of causal signal.