Differentiable and Transportable Structure Learning

Jeroen Berrevoets, Nabeel Seedat, Fergus Imrie, Mihaela van der Schaar

TL;DR

D-Struct is a novel framework for learning Directed Acyclic Graphs (DAGs) that bridges the efficiency of differentiable optimization with the robustness of "transportability." By enforcing a consensus across an ensemble of learners trained on different data subsets, D-Struct achieves significantly higher structural accuracy and up to 20x faster convergence than the seminal NOTEARS algorithm.

The Challenge of Transportability

Discovering the underlying structure of data—represented as a Directed Acyclic Graph (DAG)—is a cornerstone of scientific discovery. It helps researchers understand how complex variables, such as blood pressure, genetics, and heart disease, interact. Historically, this task was a combinatorial nightmare because the number of possible DAGs grows super-exponentially with the number of variables.

The field was revolutionized by NOTEARS, an algorithm that turned this discrete search into a continuous, differentiable optimization problem. However, while NOTEARS drastically reduced search time, it conceded a crucial property: transportability.

Illustration of transportability across different hospitals.

In a scientific context, if you learn a structure from Hospital A's data and a different structure from Hospital B's data, the discovery isn't robust. The underlying biology should remain consistent even if the specific patient populations (and their statistical distributions) differ. Standard differentiable methods are prone to getting stuck in local minima, leading to inconsistent structures that fail to generalize across different distributions within the same domain.

The D-Struct Methodology

To address this, the authors introduce D-Struct, a framework that enforces transportability through two primary innovations:

  1. Ensemble Architecture & Consensus Loss: Instead of relying on a single learner, D-Struct utilizes $K$ parallel differentiable score functions (DSFs). It introduces a novel "transportability" term to the loss function: a Mean Squared Error (MSE) penalty that discourages individual adjacency matrices from deviating from the ensemble's mean. This forces the different learners to "agree" on a single, shared structure.
  2. Smart Subset Construction: To apply this ensemble approach to a single dataset, the authors developed a routine to mimic multi-source data. They sort the data and use overlapping Beta distributions to sample subsets. This ensures that while each subset reflects the same underlying causal mechanisms, they represent different "regions" of the distribution, providing the necessary variety to enforce transportability.
The D-Struct architecture and consensus loss.

Crucially, D-Struct remains fully differentiable. This means it can be seamlessly plugged into existing deep learning architectures as a drop-in replacement for older DAG-learning modules.

Experimental Setup

The researchers evaluated D-Struct primarily on synthetic benchmarks where the "ground truth" structure is known:

  • Erdos-Rényi (ER) & Scale-Free (SF) Graphs: Testing on random graphs with varying connectedness, as well as graphs mimicking real-world networks where a few nodes act as highly-connected hubs.
  • Varying Parameters: Evaluations spanned different sample sizes ($n$), edge densities ($s$), and variable counts ($d$).
  • Non-linear Equations: The data was generated using complex "index-models" (incorporating tanh, cos, and sin functions) to ensure the learning task wasn't trivially easy.

Key Insights

  • Transportability as a Powerful Regularizer: The most surprising insight is that forcing multiple models to agree doesn't just make them more "robust"—it makes them fundamentally better. The consensus constraint effectively prunes the optimization landscape, helping the model avoid the noisy local minima that plague single-instance learners like NOTEARS.
  • The Efficiency Paradox: Usually, ensemble methods are slower because they require more computation. However, D-Struct is often 10x to 20x faster to converge. Because the parallel learners constrain each other toward a shared solution, the optimizer finds the global optimum much more quickly.
  • Mimicking Multi-Source Data: The realization that a model's performance on a single dataset can be improved by artificially splitting it into differently distributed subsets (rather than random, identically distributed splits) is a clever way to bake domain invariance into the learning process.

Results

  • Accuracy: D-Struct consistently outperformed baselines like NOTEARS-MLP and NOTEARS-SOB across almost all metrics. In high-dimensional settings ($d=100$), D-Struct achieved a highly accurate Structural Hamming Distance (SHD) of 3, compared to the baseline's 11.
  • Speedup: The authors report a massive reduction in compute time, showing an average speedup of roughly 10x, and reaching up to 20x for certain sample sizes.
  • Empirical Transportability: In head-to-head tests, the sub-graphs learned by D-Struct were perfectly identical (SHD=0) in 80% of runs, whereas NOTEARS produced conflicting structures nearly every time.

Limitations and Future Work

While D-Struct represents a significant leap forward, the authors note a few limitations:

  • DAGs $\neq$ Causality: While D-Struct is highly effective at finding the "true" mathematical DAG, this does not automatically equate to discovering a causal mechanism. Without specific causal identification assumptions, the output remains a Bayesian Network, not necessarily a definitive roadmap of cause-and-effect.
  • Consensus Strategy: Currently, D-Struct combines internal graphs by averaging adjacency matrices and applying a threshold. More sophisticated "voting" mechanisms or weighted consensus models could further improve performance.
  • High-Dimensional Scaling: While D-Struct scales better than traditional methods, DAG learning remains computationally challenging as the number of variables reaches into the thousands, a common scenario in fields like genomics.

Summary updated

Abstract

Directed acyclic graphs (DAGs) encode a lot of information about a particular distribution in their structure. However, compute required to infer these structures is typically super-exponential in the number of variables, as inference requires a sweep of a combinatorially large space of potential structures. That is, until recent advances made it possible to search this space using a differentiable metric, drastically reducing search time. While this technique--- named NOTEARS ---is widely considered a seminal work in DAG-discovery, it concedes an important property in favour of differentiability: transportability. To be transportable, the structures discovered on one dataset must apply to another dataset from the same domain. We introduce D-Struct which recovers transportability in the discovered structures through a novel architecture and loss function while remaining fully differentiable. Because D-Struct remains differentiable, our method can be easily adopted in existing differentiable architectures, as was previously done with NOTEARS. In our experiments, we empirically validate D-Struct with respect to edge accuracy and structural Hamming distance in a variety of settings.
BibTeX
@inproceedings{berrevoets2023differentiable,
  author = {Jeroen Berrevoets and Nabeel Seedat and Fergus Imrie and Mihaela van der Schaar},
  title = {{Differentiable and Transportable Structure Learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=8pCLQsEMPQ},
}
Figure