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.
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.
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