Learning Pairwise Graphical Models with Nonlinear Sufficient Statistics

Xiao–Tong Yuan, Ping Li, Tong ZhangarXiv 2013 · DOI · arXiv

Abstract

We investigate a generic problem of learning pairwise exponential family graphical models with pairwise sufficient statistics defined by a global mapping function, e.g., Mercer kernels. This subclass of pairwise graphical models allow us to flexibly capture complex interactions among variables beyond pairwise product. We propose two $\ell_1$-norm penalized maximum likelihood estimators to learn the model parameters from i.i.d. samples. The first one is a joint estimator which estimates all the parameters simultaneously. The second one is a node-wise conditional estimator which estimates the parameters individually for each node. For both estimators, we show that under proper conditions the extra flexibility gained in our model comes at almost no cost of statistical and computational efficiency. We demonstrate the advantages of our model over state-of-the-art methods on synthetic and real datasets.

Introduction

Undirected Graphical Models (UGMs), such as Gaussian Graphical Models (GGMs) and Ising models, are fundamental for representing dependencies in high-dimensional systems. However, traditional models typically assume that interactions between variables are linear, relying on the pairwise product $X_s X_t$ as a sufficient statistic. In many real-world scenarios, variable dependencies are highly nonlinear. For instance, two variables might only be related when their values are within a specific proximity, a relationship that linear models fail to capture. This paper introduces Semi-parametric Exponential Family Graphical Models (Semi-EFGMs) to bridge this gap, offering a flexible framework that maintains statistical and computational efficiency.

The Semi-EFGM Framework

The core innovation of the Semi-EFGM is the replacement of standard pairwise products with a bivariate mapping function $\phi(X_s, X_t)$, such as a Mercer kernel. This allows the model to capture complex, nonlinear interactions. To learn these models, the authors propose two $\ell_1$-norm penalized estimators:

  1. Joint MLE: A simultaneous estimation of all graph parameters.
  2. Node-wise Conditional MLE: An individual estimation for each node based on its conditional distribution, which is highly parallelizable.

By leveraging Mercer kernels, these estimators can be relaxed into standard convex optimization problems: the joint estimator becomes a log-determinant program, and the node-wise estimator reduces to a Lasso program. This ensures that the model can be solved using existing high-performance optimization software.

Experimental Results

The proposed approach was evaluated against traditional methods like GGMs and Nonparanormal estimators using both synthetic and real-world data.

Synthetic Data Recovery

In simulations involving nonlinear interactions (e.g., Heat Kernels), the Semi-EFGM demonstrated superior performance in recovering the underlying graph structure. While traditional GGMs struggled to identify connections beyond simple noise, the Semi-EFGM accurately captured the block-diagonal structures of the ground truth.

Comparison of graph structure recovery: (a) Ground truth, (b) traditional GGM recovery, and (c) the proposed Semi-EFGM approach.

Real-World Application: S&P 500

The model was applied to historical price data for 465 stocks. The Semi-EFGM successfully identified clusters of stocks belonging to the same industry sectors without prior knowledge of those categories. This suggests that financial dependencies are inherently nonlinear and that capturing this nonlinearity provides a more accurate representation of market dynamics.

Conclusion

Semi-EFGMs provide a powerful extension to traditional graphical models by incorporating nonlinear sufficient statistics. Crucially, this added flexibility does not compromise statistical convergence rates, which remain minimax optimal. Future work may explore automatically learning the mapping function $\phi$ from data, potentially using a linear combination of basis functions within a Reproducing Kernel Hilbert Space (RKHS).

Summary updated

Abstract

We investigate a generic problem of learning pairwise exponential family graphical models with pairwise sufficient statistics defined by a global mapping function, e.g., Mercer kernels. This subclass of pairwise graphical models allow us to flexibly capture complex interactions among variables beyond pairwise product. We propose two $\ell_1$-norm penalized maximum likelihood estimators to learn the model parameters from i.i.d. samples. The first one is a joint estimator which estimates all the parameters simultaneously. The second one is a node-wise conditional estimator which estimates the parameters individually for each node. For both estimators, we show that under proper conditions the extra flexibility gained in our model comes at almost no cost of statistical and computational efficiency. We demonstrate the advantages of our model over state-of-the-art methods on synthetic and real datasets.
BibTeX
@misc{yuan2013learning,
  author = {Xiao–Tong Yuan and Ping Li and Tong Zhang},
  title = {{Learning Pairwise Graphical Models with Nonlinear Sufficient Statistics}},
  year = {2013},
  eprint = {1311.5479},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1311.5479},
}
Figure