Algebraic statistics in practice: applications to networks

Marta Casanellas, Sonja Petrović, Caroline UhlerQRU 2020 · DOI · arXiv

Abstract: Algebraic statistics uses tools from algebra (especially from multilinear algebra, commutative algebra, and computational algebra), geometry, and combinatorics to provide insight into knotty problems in mathematical statistics. In this review, we illustrate this on three problems related to networks: network models for relational data, causal structure discovery, and phylogenetics. For each problem, we give an overview of recent results in algebraic statistics, with emphasis on the statistical achievements made possible by these tools and their practical relevance for applications to other scientific disciplines.

Introduction

While "Algebraic Statistics" might sound like a contradiction in terms—mixing the rigid structures of algebra with the inherent randomness of statistics—it has emerged as a powerhouse for analyzing complex networks. Tools from commutative algebra, algebraic geometry, and combinatorics provide rigorous solutions to network problems where traditional "black-box" statistical methods often stumble.

Addressing the Complexity of Networks

Standard statistical tools often rely on "asymptotics"—the idea that if you have an infinite amount of data, your errors will follow a nice bell curve. However, networks (like social circles, protein interactions, or gene regulators) are notoriously difficult because they are discrete, often sparse, and their edges are rarely independent.

This research addresses three specific gaps:

  1. Goodness-of-Fit: Determining if an Exponential Random Graph Model (ERGM) actually describes a real-world network when standard tests fail for sparse data.
  2. Causal Discovery: Moving beyond correlation to find the true underlying structure of a system, especially when common assumptions like "faithfulness" are mathematically fragile.
  3. Phylogenetics: Reconstructing the "Tree of Life" from DNA sequences when the evolutionary process involves complex mixtures of rates and models.

Algebraic and Geometric Methods

The paper highlights several novel algebraic and geometric "heavy hitters":

  • Markov Bases: Derived from commutative algebra, these are sets of "moves" that allow researchers to sample from a "fiber"—a collection of all possible networks sharing the same summary statistics as the observed one. This allows for exact conditional tests of model fit.
  • Algebraic Hypersurfaces: Algebraic geometry shows that "unfaithful" distributions (where causal discovery fails) live on thin geometric slices called hypersurfaces, allowing researchers to quantify failure likelihood.
  • DAG Associahedra: By viewing the space of causal orderings as a high-dimensional polytope, greedy search algorithms can be made provably consistent.
  • Phylogenetic Invariants: Polynomial equations that act as "algebraic fingerprints" to identify correct evolutionary tree topologies.

Real-World Applications

These methods are illustrated using several real-world examples, including the Ji and Jin (2016) Statistician Network, which tracks co-authorship and citation patterns among statisticians.

Co-authorship and citation networks of statisticians used to demonstrate algebraic goodness-of-fit tests.

Key Insights and Results

One of the most striking insights is the "Geometry of Failure." Using real algebraic geometry, the authors show that the "faithfulness" assumption—a cornerstone of causal inference—is mathematically thin. As the number of variables grows, the failure points can fill the entire space, explaining why traditional algorithms struggle in high dimensions.

In practice, algebraic exact tests reveal complexities that simpler models miss. For instance, while a citation network might appear to fit a simple model at first glance, the goodness-of-fit statistic can reveal hidden transitive effects.

Histogram of the goodness-of-fit statistic for a citation network, where the red line indicates the observed value relative to the distribution.

Limitations and Future Frontiers

Despite their power, these tools face scalability challenges. Computing a full Markov basis for a massive network is often NP-hard. Future work focuses on "dynamic" algorithms that generate only necessary moves on the fly. Additionally, generalizing these methods to handle latent (hidden) variables and optimizing experimental design for interventions remain critical open challenges in the field.

Summary updated

Abstract

Algebraic statistics uses tools from algebra (especially from multilinear algebra, commutative algebra, and computational algebra), geometry, and combinatorics to provide insight into knotty problems in mathematical statistics. In this review, we illustrate this on three problems related to networks: network models for relational data, causal structure discovery, and phylogenetics. For each problem, we give an overview of recent results in algebraic statistics, with emphasis on the statistical achievements made possible by these tools and their practical relevance for applications to other scientific disciplines.
BibTeX
@inproceedings{casanellas2020algebraic,
  author = {Marta Casanellas and Sonja Petrović and Caroline Uhler},
  title = {{Algebraic statistics in practice: applications to networks}},
  booktitle = {QRU},
  year = {2020},
  doi = {10.1146/annurev-statistics-031017-100053},
}
Figure