Optimal estimation of Gaussian (poly)trees

Yuhao Wang, Ming Gao, Wai Ming Tai, Bryon Aragam, Arnab Bhattacharyya

TL;DR

This paper establishes the fundamental limits of learning Gaussian trees and polytrees, proving exactly how many samples are needed to learn their distributions or recover their structures. The authors introduce PC-Tree, a simplified version of the classic PC algorithm, and demonstrate that it achieves minimax optimal sample complexity for structure recovery.

What Problem Does This Paper Address?

Graphical models, particularly Directed Acyclic Graphs (DAGs), are the workhorses of causal inference and probabilistic modeling. However, learning these structures from data is notoriously difficult—often NP-hard in the general case.

While researchers have long understood how to learn undirected trees (using the famous Chow-Liu algorithm), the optimal sample complexity for directed trees (polytrees) remained an open question. This paper bridges that gap by answering two fundamental questions:

  1. Distribution Learning: How many samples do we need to find a tree-structured distribution that is "close" (in KL-divergence) to the true distribution?
  2. Structure Learning: How many samples do we need to perfectly recover the graph's skeleton and orientations (up to Markov equivalence)?

Methods

The authors tackle the problem by analyzing three progressively stronger settings: Non-realizable (the true distribution isn't a tree), Realizable (it is a tree), and Faithful (the distribution perfectly reflects the graph's independence structure).

They employ two primary algorithmic approaches:

  • Modified Chow-Liu: Used for distribution learning. It constructs a maximum weight spanning tree using estimated mutual information. While the original algorithm produces an undirected tree, the authors show that any valid orientation of this tree is optimal for distribution estimation.
  • PC-Tree: A specialized version of the classic PC algorithm for structure learning. Standard PC algorithms are computationally expensive because they test conditional independence against all possible subsets of variables. PC-Tree exploits the tree structure to simplify this: it only tests marginal independence and conditional independence given exactly one other node.

Crucially, the authors don't just provide upper bounds (what these algorithms can do); they derive matching lower bounds using information-theoretic tools (like Fano’s inequality) to prove that no algorithm can do better.

Datasets

The paper relies on synthetic datasets to verify its theoretical findings, as the "ground truth" structure must be known to evaluate recovery rates.

  • Tree Generation: Random directed trees were generated using the networkx Python package, with node counts $d \in \{10, 50, 100\}$.
  • Data Generation: Data was produced via Linear Structural Equation Models (SEMs).
  • Noise Distributions: While the theory focuses on Gaussian noise, the authors tested the algorithms' robustness using Uniform and Laplace noise distributions.
  • Baselines: They compared PC-Tree and Chow-Liu against standard implementations of the PC algorithm (via Causal-learn) and GES (Greedy Equivalence Search via py-tetrad).

Key Insights and Ideas

  • The "Easiness" of Structure: Perhaps the most surprising insight is that under typical conditions, structure learning is "easier" than distribution learning. If you have a strong enough signal (faithfulness), you can recover the exact graph with far fewer samples than it takes to accurately estimate the underlying probability values.
  • Phase Transitions: The authors identify a phase transition in sample complexity. In the realizable setting, the complexity scales linearly with the number of nodes ($d/\epsilon$), whereas in the non-realizable setting, it scales quadratically ($d^2/\epsilon^2$).
  • Simplified Faithfulness: For trees, the authors show that the standard, often-criticized "faithfulness" assumption can be significantly relaxed to "tree-faithfulness," which only requires dependencies to hold for very small conditioning sets.

Key Results

  • Optimal Rates: The paper proves the following minimax optimal sample complexities (ignoring log factors):
  • Non-realizable Distribution Learning: $n = \tilde{\Theta}(d^2/\epsilon^2)$
    • Realizable Distribution Learning: $n = \tilde{\Theta}(d/\epsilon)$
    • Structure Learning: $n = \Theta(\log d / c^2)$, where $c$ represents the minimum signal strength.
  • Empirical Superiority: In experiments with 100 nodes, PC-Tree achieved a significantly higher Precise Recovery Rate (PRR) than standard PC or GES. While standard algorithms struggled to reach 40-60% recovery even with 5,000 samples, PC-Tree approached 100% recovery much earlier (around 3,000 samples).
  • Robustness: The algorithms remained effective even when the noise was non-Gaussian (Uniform or Laplace), suggesting the theoretical Gaussian bounds are conservative.

Limitations and Future Work

  • Non-Parametric Extension: The current theoretical guarantees are tied to Gaussian distributions. The authors suggest that extending these optimal bounds to non-parametric settings (where the relationship between nodes isn't linear) is a vital next step.
  • The Low-Signal Regime: There remains an open theoretical question regarding the "gap" where distribution learning is hard but structure learning might be possible (specifically when the error tolerance $\epsilon$ is between $c^2$ and $dc^2$).
  • Real-World Validation: As is common with high-level theory papers, the evaluation is limited to synthetic data. Testing these "optimal" algorithms on real-world biological or social networks where tree structures are suspected would be a valuable practical contribution.

Summary updated

Abstract

We develop optimal algorithms for learning undirected Gaussian trees and directed Gaussian polytrees from data. We consider both problems of distribution learning (i.e. in KL distance) and structure learning (i.e. exact recovery). The first approach is based on the Chow-Liu algorithm, and learns an optimal tree-structured distribution efficiently. The second approach is a modification of the PC algorithm for polytrees that uses partial correlation as a conditional independence tester for constraint-based structure learning. We derive explicit finite-sample guarantees for both approaches, and show that both approaches are optimal by deriving matching lower bounds. Additionally, we conduct numerical experiments to compare the performance of various algorithms, providing further insights and empirical evidence.
BibTeX
@inproceedings{wang2024optimal,
  author = {Yuhao Wang and Ming Gao and Wai Ming Tai and Bryon Aragam and Arnab Bhattacharyya},
  title = {{Optimal estimation of Gaussian (poly)trees}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
}
Figure