🤖 machine learning

Ordering-based Causal Discovery via Generalized Score Matching

This paper extends the score matching framework to discrete data by introducing a novel leaf discriminant criterion, enabling accurate causal order inference that significantly enhances the performance of existing causal discovery methods.

Original authors: Vy Vo, He Zhao, Trung Le, Edwin V. Bonilla, Dinh Phung

Published 2026-07-28

📖 9 min read🧠 Deep dive

CC BY 4.0

Original authors: Vy Vo, He Zhao, Trung Le, Edwin V. Bonilla, Dinh Phung

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 solve a mystery, but you only have a pile of clues left behind at the scene. You don't have a confession, a video recording, or a timeline of events. You just have a snapshot of everything that happened. Your goal? To figure out who caused what. Did the broken window cause the alarm to go off, or did the alarm cause the window to break? In the world of science, this is called causal discovery. It's the art of figuring out the hidden chain of cause-and-effect that links different things together, like how a virus spreads, why a stock market crashes, or what makes a plant grow.

The tricky part is that nature often hides the "arrow of time." If you see two things happening together—like ice cream sales and shark attacks both going up in July—you might guess one causes the other. But usually, a third thing (hot weather) causes both. To solve this, scientists use math to look for patterns that only appear when one thing truly pushes another. For a long time, these mathematical tricks worked great for smooth, continuous things like temperature or speed. But the real world is full of "discrete" things—categories like "yes/no," "red/blue/green," or "sick/healthy." Until now, the best math tools for finding cause-and-effect didn't know how to handle these categories. They were like a wrench that only fit round nuts, leaving square ones untouched.

This paper, titled "Ordering-based Causal Discovery via Generalized Score Matching," is like inventing a new wrench that fits square nuts perfectly. The authors, a team from Monash University and CSIRO, have taken a powerful mathematical method called Score Matching and taught it how to work with discrete, categorical data. Their big idea is to figure out the order of events by finding the "leaf nodes"—the very last items in a chain that don't cause anything else. Imagine a family tree where you start at the great-grandparents and work your way down. This paper shows how to start at the very bottom (the great-grandchildren) and work your way up, even when the data is just a list of categories rather than numbers.

They tested this new method on both computer-generated puzzles and real-world datasets, like medical records and ecological models. The results suggest that by correctly identifying the order of events first, they can significantly boost the accuracy of existing tools that try to draw the full map of causes. It's not a magic wand that solves every mystery instantly, but it's a major step forward, proving that we can now use these advanced math tricks on the messy, categorical data that makes up so much of our daily lives.

The Detective's New Toolkit

So, how does this actually work? Let's break it down with a story.

Imagine you are in a room full of people passing notes. Some people write notes and pass them to others; some just receive notes and stop. You can't see who is writing to whom, but you can see the final pile of notes everyone is holding. Your job is to figure out who started the chain and who just ended it.

In the world of data, the "notes" are the variables (like "smoking," "coughing," or "lung cancer"). The "chain" is the Directed Acyclic Graph (DAG). "Directed" means there's a specific direction (cause $\to$ effect), and "Acyclic" means you can't have a loop where A causes B, B causes C, and C causes A (that would be a time-travel paradox!).

For years, scientists had a brilliant tool called Score Matching. Think of "score" not as points in a game, but as a measure of how "surprised" a system is by a specific piece of data. If you know the rules of the game, you can calculate a "score" for every possible outcome. In continuous data (like temperature), this score is like a slope on a hill. If you are at the very top of a hill (a leaf node), the slope behaves in a very specific, predictable way. By looking at these slopes, scientists could figure out who was at the end of the chain (the leaf) and peel them off the list, one by one, to reveal the whole order.

The Problem: This only worked for smooth, continuous data. If your data was discrete—like "Red," "Blue," or "Green"—the concept of a "slope" or a "derivative" breaks down. You can't take a slope of a color! It's like trying to measure the steepness of a staircase with a ruler meant for a ramp. The old tools just couldn't handle the "steps."

The Paper's Big Breakthrough

The authors of this paper asked a simple question: Can we reinvent the "score" for discrete data?

They said, "Yes, but we have to change the rules of the game." Instead of looking at slopes, they looked at randomness.

Here is the analogy: Imagine a game of telephone.

The Parent: Someone starts with a very clear, specific message (low randomness).
The Child: They whisper it to the next person, but maybe they mumble a little, or the next person mishears a word (adding a tiny bit of noise/randomness).
The Grandchild: The message gets passed down again, accumulating more errors.

In a causal chain, the "parent" variable is usually more ordered and predictable. The "child" variable, which is the result of the parent plus some random noise, becomes more chaotic and uncertain. The authors realized that if you measure the randomness (or "spread") of the data, the items at the very end of the chain (the leaves) should be the most random or "spread out" in a specific mathematical sense.

They introduced a new way to measure this using something called a reciprocal discrete score. Instead of a slope, they looked at how likely a specific category is given everything else. If a variable is a "leaf" (it doesn't cause anything else), its randomness follows a special pattern that is different from the variables in the middle of the chain.

How They Did It (The "Leaf Hunter")

The paper proposes a step-by-step process to find the order:

Estimate the Score: They use a fancy AI model (a continuous-time diffusion model) to estimate these "scores" from the data. This is like training a robot to understand the probability of every note in the room.
Find the Leaf: They calculate a "randomness score" for every variable. The variable with the highest randomness (according to their specific math rule) is identified as the leaf node—the one at the end of the chain.
Peel and Repeat: Once they find a leaf, they remove it from the list. Now, the new "end" of the chain is exposed. They repeat the process until they have ordered everyone from the very first cause to the very last effect.

What They Found (and What They Didn't)

The authors ran this new method through a gauntlet of tests:

Simulated Data: They created thousands of fake worlds with random rules to see if their math held up. They tested graphs with up to 60 nodes (variables) and different types of connections.
Real-World Data: They tested it on six real datasets, including medical records (like the "Sachs" dataset with 11 variables and the "Alarm" dataset with 37 variables) and ecological models.

The Results:
In almost every test, using their new ordering method significantly boosted the performance of existing causal discovery tools. When they gave the ordering to standard algorithms (like PC or GES), those algorithms made fewer mistakes.

They measured this using metrics like F1 score (a measure of accuracy) and SID (a measure of how well the graph predicts what happens if you intervene). Their method consistently improved these scores.
They found that even if the ordering wasn't perfect, it was still "good enough" to help the other tools find the right answer.

What They Ruled Out:
The paper is careful to say what they didn't do. They did not claim to have solved the problem of causal discovery for all situations.

They explicitly state that their method relies on a specific condition: that the randomness (uncertainty) increases as you go down the causal chain. If the real world has a weird situation where a child is less random than its parent, the method might struggle.
They did not claim to have a magic bullet that works without any assumptions. Like all causal discovery, it needs some structure to work.
They noted that while the math works for continuous data too, they focused on discrete data because that's where the old tools failed. They didn't claim to have solved the continuous case with this specific implementation.

The Bottom Line

This paper is a bridge. For a long time, the bridge between "advanced causal math" and "discrete, categorical data" was broken. The authors built a new path across it. They showed that by looking at randomness instead of slopes, we can find the order of events in data that looks like lists of categories.

They didn't just say "it might work." They ran the numbers, tested it on real-world problems, and showed that it robustly enables more accurate causal discovery. It's a tool that helps scientists and data detectives sort out the "who caused what" in a world full of yes/no answers, red/blue choices, and sick/healthy states. While it's not a perfect solution for every mystery (no single tool is), it's a powerful new addition to the detective's kit, proving that we can finally apply these sophisticated mathematical lenses to the messy, categorical data that surrounds us every day.

Technical Summary: Ordering-based Causal Discovery via Generalized Score Matching

Problem Statement

Causal discovery from purely observational data remains a significant challenge, primarily due to two factors: the identifiability of causal models (where multiple structures can generate the same data distribution) and the computational intractability of searching the combinatorial space of Directed Acyclic Graphs (DAGs), which is NP-hard. While ordering-based approaches offer a solution by first identifying a topological order and then pruning edges, existing methods leveraging score matching are currently restricted to continuous data. A critical gap exists in extending these powerful frameworks to discrete (categorical) data, where the concept of a score function (the gradient of the log-likelihood) is not well-defined.

Methodology

The paper proposes a framework to extend score matching to discrete variables for the purpose of identifying causal orders. The methodology proceeds through the following key theoretical and algorithmic steps:

1. Generalized Score Matching for Discrete Data

The authors utilize the Generalized Score Matching framework proposed by Lyu [32]. Instead of the gradient operator used for continuous data, they employ the marginalization operator ( $\mathcal{M}$ ).

For a discrete variable $X_i$ , the score is defined via the reciprocal of the singleton conditional density: $r_i(x_{-i}) = p(X_i | x_{-i})$ .
This discrete score function is estimated using continuous-time discrete diffusion models (specifically the architecture proposed by Sun et al. [58]), which circumvents the need to calculate the data score function directly and ensures consistency.

2. Identifiability via Non-Decreasing Randomness

To identify leaf nodes (nodes with no children) in a discrete Structural Causal Model (SCM), the paper introduces a new identifiability condition based on randomness measures rather than variance.

Randomness Measure ( $\phi$ ): The authors define a measure of randomness using Schur-concave functions (e.g., Shannon entropy, negative variance). A distribution is considered "more random" if it is majorized by another.
Non-Decreasing Randomness Condition (Condition 3): The core theoretical assumption is that along a true causal order, the conditional randomness of a variable given its parents is less than or equal to the minimum conditional randomness of its children given their respective parents:
$\phi(X_i | X_{pa_i}) \leq \min_{j \in ch_i} \phi(X_j | X_{pa_j})$
This reflects the intuition that exogenous noise accumulates as one moves down the causal chain (e.g., an ice cube melting into water increases disorder).

3. Theoretical Guarantees

Theorem 1 establishes that if a randomness measure $\phi$ satisfies the non-decreasing randomness condition, a node $X_j$ is a leaf node if and only if it maximizes the expected randomness of its reciprocal score:
$X_j \text{ is a leaf} \iff j \in \arg\max_{i \in [d]} \mathbb{E}_{X_{-i}}[\phi(r_i(x_{-i}))]$
This allows for a sequential leaf-detection algorithm (Algorithm 1) to recover the full topological order. The paper also provides Proposition 1, offering a structural check for this condition under symmetric Dirichlet priors without requiring additive noise assumptions.

4. Practical Diagnosis and Post-Processing

Recognizing that the non-decreasing randomness condition may not hold perfectly in real-world data, the authors propose:

Algorithm 2: A practical diagnostic test using conditional independence tests (Chi-square) to estimate the in-degree distribution induced by a candidate ordering. If the estimated in-degrees exceed the known sparsity bounds (maximum in-degree), the ordering is flagged as potentially invalid.
Post-Processing Strategies: Once an order is estimated, the paper suggests two strategies to improve DAG recovery:
1. Edge Pruning: Removing edges that violate the inferred order (effective for high-recall, low-precision methods like PC).
2. Edge Insertion: Iteratively adding edges from predecessors to the current node if they improve the scoring function (effective for high-precision, low-recall methods like GES).

Key Contributions

First Discrete Score Matching Method: The paper presents the first score matching method capable of learning a full causal order from discrete data, bridging a gap in existing literature limited to continuous variables.
New Identifiability Theory: It characterizes the identifiability of topological orders in discrete SCMs without assuming an additive noise structure. It generalizes existing results by replacing the "non-decreasing variance" assumption with a "non-decreasing randomness" condition applicable to Schur-concave measures.
Robust Framework: The approach provides a fresh perspective on learning from categorical variables, moving beyond classical independence tests and score-and-search approaches.
Empirical Validation: The theory is validated through extensive experiments on synthetic (Erdos-Rényi and Scale-Free) and real-world datasets (from the bnlearn repository).

Experimental Results

The authors evaluated their method (SCORE+[X], where X is a baseline) against standard baselines including PC, GES, ORDCD, and GAMs.

Performance: Across synthetic and real-world datasets, the proposed method consistently improved F1 scores and Structural Intervention Distance (SID) compared to baselines.
Robustness: Even when the non-decreasing randomness condition was not strictly satisfied (simulated noisy regimes), the inferred orders provided sufficient information to boost the performance of downstream causal discovery algorithms.
Metrics: While Structural Hamming Distance (SHD) sometimes increased slightly (due to the method's tendency to predict more edges rather than fewer), the SID and F1 improvements indicated higher reliability for causal inference and better overall accuracy.
Diagnosis: The proposed in-degree diagnostic test showed a positive correlation between the proportion of "invalid" nodes (those violating sparsity bounds) and the topological divergence ( $D_{top}$ ), confirming its utility as a validity check.

Significance and Claims

The paper claims to provide a theoretical foundation for applying score matching to discrete causal discovery, a domain previously considered intractable for this approach due to the lack of a defined score function.

Modest Claims: The authors acknowledge that their identifiability results rely on the non-decreasing randomness condition, which requires prior knowledge or assumptions about the data-generating process. They do not claim the method works universally without assumptions but argue it is a significant step forward for discrete data.
Limitations: The authors note that the current approach requires retraining the diffusion model at every iteration of the leaf-detection process, leading to higher computational costs ( $O(d)$ training iterations). They suggest future work could focus on adaptive masking strategies to approximate scores with a single model.
Scope: The work is explicitly framed as an extension of score matching to discrete variables; while the theory is theoretically applicable to continuous data, the authors focus on the discrete domain due to the statistical bottlenecks in estimating conditional densities for continuous variables.

In summary, this work demonstrates that by redefining the score function for discrete data and leveraging randomness measures, it is possible to recover causal orders that significantly enhance the accuracy of existing causal discovery algorithms, even under noisy and relaxed conditions.