Generalized Root Models: Beyond Pairwise Graphical Models for Univariate Exponential Families

David I. Inouye, Pradeep Ravikumar, Inderjit S. DhillonarXiv 2016 · DOI · arXiv

Abstract

We present a novel k-way high-dimensional graphical model called the Generalized Root Model (GRM) that explicitly models dependencies between variable sets of size k > 2. This model is based on taking the k-th root of the original sufficient statistics of any univariate exponential family with positive sufficient statistics. We provide conditions for parameter normalization using radial conditionals and develop a learning algorithm based on L1-regularized node-wise regressions. Furthermore, we introduce a general method for numerically approximating the log partition function. Empirical results on word count datasets demonstrate the model's ability to capture semantically meaningful higher-order interactions.

Introduction

Standard graphical models, such as the Ising model or Multivariate Gaussian, are primarily limited to pairwise dependencies. While effective for many tasks, these models struggle to capture higher-order interactions ($k > 2$) that are prevalent in complex systems like biological pathways or semantic relationships in natural language. Modeling these dependencies in non-Gaussian data, such as counts (Poisson) or durations (Exponential), presents significant challenges in ensuring distribution normalization and tractable estimation of the log partition function.

The Generalized Root Model (GRM)

The GRM addresses these challenges by applying a $k$-th root transformation to the sufficient statistics of univariate exponential families. For a set of variables $X = \{x_1, \dots, x_p\}$, the interaction terms take the form of the $k$-th root of the product of $k$ variables. For example, a triple-wise interaction between $x_s, x_t, x_u$ is modeled using $\sqrt[3]{x_s x_t x_u}$. This transformation prevents interaction terms from growing too rapidly, which is critical for maintaining a normalizable distribution even in the presence of positive dependencies.

Normalization and Radial Conditionals

A key technical hurdle in non-Gaussian graphical models is ensuring that the probability distribution integrates to one. The authors utilize "radial conditionals"—analyzing the distribution's behavior along rays extending from the origin—to establish normalization conditions.

Comparison of Node and Radial Conditionals used for normalization analysis.

As shown in Figure 3, while node conditionals (horizontal/vertical slices) are standard for learning, radial conditionals provide the necessary geometric framework to prove that Poisson GRMs require no parameter restrictions for normalization, while Exponential GRMs require only mild constraints analogous to negative definiteness.

Numerical Approximation and Learning

Since the log partition function $A(\eta)$ lacks a closed-form solution for GRMs, the authors developed a robust numerical approximation method. The domain is partitioned into subdomains based on the concavity of the exponent, and linear Taylor or Secant bounds are applied.

Numerical approximation of node conditional densities using linear upper and lower bounds.

Figure 5 illustrates how the complex density function is bounded by simpler functions. This approach allows for the approximation of integrals using the standard Cumulative Distribution Function (CDF) of the base exponential family, making the calculation of gradients feasible for optimization.

Learning is performed via $\ell_1$-regularized node-wise regressions. To handle the computational complexity of high-dimensional $k$-way interactions, the authors employ a Newton-like optimization strategy, which offers significantly faster convergence than standard gradient descent.

Empirical Evaluation

The Poisson GRM was evaluated on two text datasets: Classic3 (3,893 research abstracts) and the Grolier Encyclopedia (5,000 articles). Focusing on $k=3$ (triple-wise interactions) among the top 500 words, the model successfully identified semantically coherent triples. For instance, in the Classic3 dataset, it discovered clusters such as layer + skin + friction and information + retrieval + storage. These higher-order dependencies provide a more nuanced representation of the data than simple pairwise correlations.

Conclusion

The Generalized Root Model provides a mathematically sound and computationally tractable framework for capturing $k$-way dependencies in univariate exponential families. By leveraging the $k$-th root transformation and novel numerical approximation techniques, GRMs overcome the historical limitations of non-Gaussian higher-order graphical models. Future work will focus on scaling these models to even larger variable sets using low-rank tensor decompositions and further optimizing the numerical integration steps.

Summary updated

Abstract

We present a novel k-way high-dimensional graphical model called the Generalized Root Model (GRM) that explicitly models dependencies between variable sets of size k > 2---where k = 2 is the standard pairwise graphical model. This model is based on taking the k-th root of the original sufficient statistics of any univariate exponential family with positive sufficient statistics, including the Poisson and exponential distributions. As in the recent work with square root graphical (SQR) models [Inouye et al. 2016]---which was restricted to pairwise dependencies---we give the conditions of the parameters that are needed for normalization using the radial conditionals similar to the pairwise case [Inouye et al. 2016]. In particular, we show that the Poisson GRM has no restrictions on the parameters and the exponential GRM only has a restriction akin to negative definiteness. We develop a simple but general learning algorithm based on L1-regularized node-wise regressions. We also present a general way of numerically approximating the log partition function and associated derivatives of the GRM univariate node conditionals---in contrast to [Inouye et al. 2016], which only provided algorithm for estimating the exponential SQR. To illustrate GRM, we model word counts with a Poisson GRM and show the associated k-sized variable sets. We finish by discussing methods for reducing the parameter space in various situations.
BibTeX
@misc{inouye2016generalized,
  author = {David I. Inouye and Pradeep Ravikumar and Inderjit S. Dhillon},
  title = {{Generalized Root Models: Beyond Pairwise Graphical Models for Univariate Exponential Families}},
  year = {2016},
  eprint = {1606.00813},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1606.00813},
}
Figure