PaperlayerView exact revision on arXiv

Source-linked AI summary

On Graphical Models via Univariate Exponential Family Distributions

Eunho Yang, Pradeep Ravikumar, Genevera I. Allen, Zhandong Liu

arXiv:1301.4183v2math.STstat.ML

TL;DR

The paper asks how to choose graphical-model distributions for non-Gaussian and non-categorical data. It constructs multivariate models from univariate exponential-family node-conditionals and develops node-wise M-estimators with theoretical graph-recovery guarantees. The framework yields models including Poisson and exponential MRFs and supports genomic and proteomic network analyses, while model-fit testing and parameter restrictions remain important limitations.

  • Problem

    Choosing an appropriate graphical-model subclass is unclear for non-Gaussian and non-categorical data, despite suitable univariate distributions for counts, durations, and skewed variables.

  • Method

    The paper constructs exponential family MRFs from univariate exponential-family node-conditionals and fits them using sparsity-constrained node-wise conditional likelihood M-estimators.

  • Results

    The estimators recover the true graphical-model structure with high probability, and the framework provides Poisson and exponential MRFs with applications to genomic and proteomic networks.

  • Takeaways & Limitations

    The framework broadens available graphical models beyond standard Ising and Gaussian choices to multivariate extensions of univariate families such as Poisson, exponential, and negative binomial distributions.

  • Takeaways & Limitations

    Model fit lacks a rigorous general goodness-of-fit test, and some infinite-domain instances such as Poisson and exponential MRFs can represent only negative conditional dependencies.

Abstract

from arXiv · show

Undirected graphical models, or Markov networks, are a popular class of statistical models, used in a wide variety of applications. Popular instances of this class include Gaussian graphical models and Ising models. In many settings, however, it might not be clear which subclass of graphical models to use, particularly for non-Gaussian and non-categorical data. In this paper, we consider a general sub-class of graphical models where the node-wise conditional distributions arise from exponential families. This allows us to derive multivariate graphical model distributions from univariate exponential family distributions, such as the Poisson, negative binomial, and exponential distributions. Our key contributions include a class of M-estimators to fit these graphical model distributions; and rigorous statistical analysis showing that these M-estimators recover the true graphical model structure exactly, with high probability. We provide examples of genomic and proteomic networks learned via instances of our class of graphical models derived from Poisson and exponential distributions.

1. Introduction

The paper addresses the challenge of choosing graphical-model distributions for non-Gaussian and non-categorical data by extending univariate exponential families to multivariate graphical models. It develops tractable node-wise estimators with sparsistency guarantees for recovering graph structure.

  • Motivation: Graphical models represent joint distributions through clique-wise compatibility functions, but selecting an appropriate subclass is difficult for count-valued and other nonstandard data.Existing examples include Ising, Potts, and Gaussian Markov random fields.
  • Motivation: Univariate modeling already provides distributions suited to counts, call-times, website durations, diffusion processes, life-cycles, and skewed variables.The paper asks whether this modeling toolkit can be extended to multivariate graphical distributions.
  • Proposed framework: Exponential family MRFs construct global multivariate distributions from node-conditionals belonging to univariate exponential families.The resulting distributions factor according to graph-defined cliques and broaden standard Ising, indicator-discrete, and Gaussian MRFs.
  • Proposed framework: The framework supports multivariate extensions for distributions such as Poisson, exponential, gamma, chi-squared, and negative binomial families.This provides models for applications involving call-times, website durations, diffusion processes, life-cycles, skewed data, and counts.
  • Estimation and theory: The paper fits these models through sparsity-constrained node-conditional likelihood maximization and analyzes exact graph recovery through sparsistency guarantees.The analysis generalizes results for specific logistic and multinomial models to broader generalized linear models.
  • Contributions: The expanded manuscript introduces Poisson and exponential MRFs, tighter finite-sample analysis, simpler proofs, less restrictive assumptions, and broader experimental evaluation.It studies theoretical rates, structural recovery, and estimator robustness for the two novel instances.

2. Exponential Family Graphical Models

The paper defines exponential family graphical models by specifying univariate exponential-family node-conditionals whose compatible joint distribution factors over graph cliques. This construction includes standard Gaussian and Ising models as well as Poisson and other non-Gaussian instances, with parameter restrictions required for normalizability.

  • Graphical-model form: A graphical model is a distribution satisfying Markov independence assumptions with respect to an undirected graph and factoring over its cliques.Clique-wise sufficient statistics and weights determine the factorization.
  • Graphical-model form: The central modeling choice is the sufficient-statistic class, which determines the graphical distribution and can be selected to extend specified univariate families.The paper targets families including negative binomial and Poisson distributions.
  • Univariate exponential families: An exponential family uses a sufficient statistic, base measure, and log-normalization function, and includes Gaussian, Bernoulli, multinomial, Poisson, exponential, gamma, chi-squared, and beta distributions.These families cover skewed continuous and count data.
  • Exponential family construction: If node-conditionals follow a univariate exponential family, their canonical parameters can depend on products of neighboring sufficient statistics, yielding a conditional graphical-model specification.The conditional normalization uses the univariate log-partition function.
  • Exponential family construction: The Hammersley-Clifford theorem implies that these node-conditionals determine a unique joint distribution that belongs to the graphical model defined by the graph.The joint distribution has its own log-normalization constant A(θ).
  • General form: Under bounded clique size and exponential-family node-conditionals, the conditional and joint distributions necessarily have the paper’s tensor-factorized forms.The result establishes the generality of the proposed construction under the stated assumptions.
  • General form: When B(X_r)=X_r, node-conditionals become generalized linear models in canonical form, enabling node-wise modeling through familiar GLM structure.The resulting joint form still depends on the graph’s interaction parameters.
  • Examples: Gaussian and Ising graphical models arise as special cases from Gaussian and Bernoulli univariate exponential families.For Gaussian models, the precision matrix must be positive definite; Ising variables are binary and impose no normalizability constraint on interaction parameters.

3. Statistical Guarantees on Learning Graphical Model Structures

The paper learns graphical-model structure by estimating each node’s neighborhood with an ℓ1-regularized conditional likelihood, under conditions controlling dependence, incoherence, moments, and curvature. Under these conditions, the estimator uniquely recovers true neighborhoods—and therefore the global edge set—with high probability.

  • Estimation procedure: Graph recovery is reduced to node-wise neighborhood estimation, then combined across nodes to estimate the global edge set.The neighborhood is defined by nonzero estimated conditional parameters; asymmetric neighborhood estimates are reconciled when forming the graph.
  • Estimation procedure: The estimator maximizes a sparsity-constrained conditional log-likelihood for each node’s GLM-like conditional distribution.The parameter space may be restricted by the exponential-family model, such as nonpositive interaction parameters for Poisson graphical models.
  • Conditions: The analysis assumes bounded moments and controlled node-wise log-partition curvature, alongside Fisher-information dependency and incoherence conditions.The dependency condition controls eigenvalues on true neighborhoods, while incoherence limits irrelevant variables’ influence on neighboring variables.
  • Sparsistency result: Under Conditions (C1)–(C4) and a sufficient sample size, the M-estimation problem has a unique solution and recovers each true neighborhood exactly with high probability.The sample-size requirement scales with neighborhood size, curvature terms, log p, and logarithmic factors in n and p.
  • Sparsistency result: Exact neighborhood recovery implies exact recovery of the global edge set with high probability by a union-bound argument.The paper explicitly connects node-wise recovery to equality between the estimated and true edge sets.
  • Model-specific guarantees: For Gaussian, Ising, and exponential graphical models, the corollary gives the same uniqueness and neighborhood-recovery guarantees under Conditions (C1)–(C3).The stated probability bound has the form 1 − c1(max{n, p})^-2 − exp(−c2n) − exp(−c3n).

4. Experiments

Simulations evaluate sparsity-constrained Poisson and exponential M-estimators for graph recovery, compare them with Gaussian neighborhood selection, and assess applications to genomic and proteomic networks. Results support logarithmic sample-size scaling, distribution-specific advantages, and practical model-fit challenges.

  • Simulation design: The simulations use ℓ1-penalized neighborhood selection with distribution-specific non-negativity or non-positivity constraints.Optimization uses projected gradient descent.
  • Support recovery: Empirical recovery curves align after rescaling sample size as β = n/(log p), supporting the theoretical logarithmic dependence of n on p.The study repeats each simulation 50 times and measures complete edge-recovery probability.
  • Comparative recovery: Exponential and Poisson M-estimators outperform Gaussian neighborhood selection when data are generated from exponential or Poisson MRFs in the high-dimensional regime n < p.The two estimators perform similarly, plausibly because both conditional means use the same rate parameter λ.
  • Signed dependencies: Poisson and exponential estimators miss positive conditional dependencies but outperform Gaussian estimation for negative dependencies while maintaining false positive rates around 0.15.Their edge-weight constraints force potential positive conditional-dependence weights to zero.
  • Real data examples: Goodness-of-fit assessment remains incomplete because no exact test exists for exponential-family graphical models with unknown network structure.The paper provides a heuristic instead and applies it to real-data examples.
  • Real data examples: The Poisson model identifies a breast-cancer meta-miRNA network with three major hubs, including two previously identified tumor suppressors.Among 40 tested neighborhoods, 36 likelihood-ratio tests had p-values below 0.05 and 34 passed the Bonferroni-adjusted threshold.

5. Discussion

The paper broadens graphical models by deriving multivariate distributions from univariate exponential families and fitting them with penalized node-wise estimators. Its examples include networks estimated from Poisson and exponential graphical models, while important parameter restrictions remain for some families.

  • Contributions: The proposed class extends graphical models beyond classical Ising and Gaussian models using exponential-family node-wise conditionals.This framework includes closed-form multivariate extensions of distributions such as Poisson, exponential, and negative binomial.
  • Applications: The exponential graphical model identified PKA as a major inhibitor in an 11-protein cell-signaling network, consistent with the Gaussian graphical model.The exponential model used untransformed flow-cytometry data, whereas the Gaussian model used log-transformed data.
  • Contributions: Penalized conditional exponential-family fits provide simple M-estimators with strong statistical guarantees for graphical-model estimation.The paper also develops an analytic sparsistency framework with tighter finite-sample bounds, simpler proofs, and less restrictive assumptions than prior work.
  • Limitations: Poisson and exponential graphical models can only represent negative conditional dependencies because their parameter spaces impose this restriction.The paper identifies relaxing this restriction as an important direction for future work.

Appendix A. Proof of Theorem 2

The proof relates the joint distribution’s higher-order factors to products of univariate exponential-family terms. It then connects these factors to node-conditional probability ratios to establish the theorem’s stated structure.

  • Proof setup: The proof defines Q(X) as the log ratio between P(X) and the all-zero configuration probability.It also introduces Xr:0 by setting the r-th coordinate to zero.
  • Conditional distributions: The proof then uses Q(X) to relate the joint distribution to conditional probability ratios for a node given all other variables.The conditional exponential-family form is substituted into this ratio, first fixing r = 1 for notational simplicity.
  • Conditional distributions: Setting all coordinates except the selected node to zero simplifies the joint and conditional expressions used in the proof.This reduction is applied after deriving the general conditional relationship.
  • Coordinatewise identities: Pairwise equations are obtained by isolating coordinates r and t while setting the remaining coordinates to zero.The argument first writes the corresponding expressions for indices 1 and r, then combines them.
  • Higher-order expansion: For three nonzero coordinates, the expansion includes unary, pairwise, and triple interaction terms, with all other coordinates fixed at zero.This extends the same construction from pairs to triplets.
  • Factorization result: The general expansion expresses each k-th order factor as a tensor product of terms B(Xr) − B(0).The proof states this for factors indexed by r1 through rk and gives the corresponding coefficient form.

Appendix B. Proof of Proposition 3

The proposition’s proof uses a Taylor expansion under a boundedness condition and then applies Chernoff’s method to obtain a probability bound.

  • Taylor expansion: For a ≤ 1, the proof applies a Taylor series expansion with an intermediate ν ∈ [0, 1].The expansion is combined with Condition (C3).
  • Moment control: Condition (C3) bounds the relevant derivative or sufficient-statistic quantity by κv in the proof.The argument identifies the derivative of the log-partition function with the mean of the corresponding sufficient statistics.
  • Tail bound: The resulting bound is converted into a probability inequality using the standard Chernoff bounding technique.The stated range is all positive a ≤ 1.

Appendix C. Proof of Proposition 4

The proposition’s proof uses a zero-padded parameter, Taylor expansion, and Condition (C3) to derive an exponential upper bound for Xr.

  • Parameter choice: The proof introduces a zero-padded parameter with one nonzero coordinate corresponding to the sufficient statistic Xr.Its Euclidean norm is stated to equal 1.
  • Moment control: A Taylor expansion combined with Condition (C3) produces the intermediate inequality used to control the relevant expression.The expansion again involves an intermediate ν ∈ [0, 1].
  • Tail bound: The proof applies Chernoff’s technique to obtain an exponential upper bound on P(Xr ≥ a).The displayed bound contains the terms −a, κm, and one-half κh.
  • Tail bound: The resulting constant is c = exp(κm + 1/2κh).This is identified as the claimed constant at the end of the proof.

Appendix D. Proof of Theorem 5

The proof uses a primal-dual witness construction to establish support recovery and uniqueness for the convex graphical-model estimator. It controls the score, estimation error, and Taylor remainder under high-probability conditions.

  • Primal-dual witness construction: The primal-dual witness proof constructs restricted estimates and subgradients supported on the true edge set S.The construction fixes θ_Sc = 0, solves the restricted optimization problem, and extends the subgradient to the complement.
  • Support recovery: Strict dual feasibility and sign consistency together ensure the constructed solution is the unique estimator with the correct support.Strict dual feasibility requires ||bZ_Sc||∞ < 1, while sign consistency requires that the estimated support is not strictly smaller than S.
  • Concentration and remainder control: The optimality analysis decomposes the subgradient condition into a sample score W_n, parameter deviation, Fisher-information term, and remainder R_n.The proof controls these terms through separate lemmas, using Q* as the Fisher information matrix.
  • High-probability bounds: Under the stated regularization and sample-size conditions, the score and remainder bounds hold with high probability.The proof selects λ_n and imposes conditions involving κ constants, p′ = max{n,p}, and log p′.
  • Conclusion: The resulting lemmas establish strict dual feasibility and correct sign recovery, completing the proof of Theorem 5.The argument uses Lemmas 9, 10, and 11 together with the chosen regularization parameter and sufficiently large sample size.

D.1 Proof of Lemma 9

The proof of Lemma 9 bounds the sample score using moment-generating-function estimates, Taylor expansion, tail bounds, and a union bound. The resulting score control holds with high probability.

  • Moment-generating-function bound: The proof bounds the conditional moment-generating function of the score-related variable using a second-order Taylor expansion.The expansion is combined with derivative control from the model conditions.
  • Tail control: Tail bounds for the coordinate variables are combined across indices through a union bound.The proof defines an event controlling these variables and bounds its complement using the stated κ constants.
  • Score concentration: The Chernoff bound yields a coordinatewise score bound that scales with λ_n under the prescribed regularization conditions.The argument sets δ proportional to λ_n and uses the relationship between λ_n and κ_1(n,p), κ_2(n,p), and κ_4.

D.2 Proof of Lemma 10

The proof of Lemma 10 controls the restricted estimator’s deviation by showing a function is positive on the boundary of an appropriately chosen Euclidean ball. This yields a high-probability error bound.

  • Deviation control: The proof reduces control of the restricted estimation error to showing F(u_S) > 0 on the boundary of a radius-B ball.The radius is chosen as B = Mλ_n^d, with M selected later in the proof.
  • Uniform control: Taylor expansion and concentration on event ξ_1 control the terms in F(u_S) uniformly over the boundary.The argument uses bounds on the coordinates of X^(i) and Condition (C4) for higher derivatives.
  • Parameter choice: Choosing λ_n sufficiently small ensures a lower bound on q* and makes the boundary expression strictly positive.The proof obtains q* ≥ ρ_min/2 under the stated regularization condition and chooses M = 5/ρ_min.
  • Conclusion: The positivity argument completes the proof of the deviation lemma.

D.3 Proof of Lemma 11

The proof of Lemma 11 controls the Taylor remainder R_n by applying the mean value theorem coordinatewise and bounding the resulting derivative terms. The result is then related to Lemma 10.

  • Remainder target: The proof targets an infinity-norm bound on the Taylor remainder proportional to the restricted estimation error.The stated target involves κ_3(n,p), log p′, ρ_max, and ||bθ_S − θ*_S||_2.
  • Conclusion: Because Lemma 11’s conditions are stronger than Lemma 10’s, the result of Lemma 10 supplies the needed conclusion.
  • Mean-value expansion: The remainder is represented coordinatewise through the mean value theorem using intermediate points between the estimated and true parameters.For fixed t, the proof writes R_n,t in terms of an intermediate coefficient v_t ∈ [0,1].
  • Derivative control: Conditioning on ξ_1 and applying the model’s derivative bounds controls the coordinatewise remainder terms.The proof performs algebra after the conditional bound to obtain the required norm estimate.

Appendix E. Optimization Problems for Poisson and Exponential Graphical Model Neighborhood Selection

The paper fits Poisson and exponential graphical models through node-wise conditional likelihoods with ℓ1 sparsity penalties and parameter constraints that ensure valid Markov random fields. These concave optimization problems are solved using projected gradient descent.

  • Parameter constraints: Additional parameter-space constraints are imposed when needed to ensure that the fitted distribution is a proper Markov random field.The constraints are represented as θ^(r) ∈ C for the node-specific parameter vector.
  • Neighborhood selection: Neighborhood selection maximizes each node’s conditional likelihood given all other nodes, with an ℓ1 penalty inducing sparse edge weights.The optimization is formulated as a penalized generalized linear model for each node.
  • Distribution-specific constraints: Poisson graphical models constrain edge weights to be non-positive, whereas exponential graphical models constrain them to be non-negative.These sign restrictions define the respective constrained optimization problems.
  • Model specification: The intercept is omitted by assuming it equals zero, following common practice in related neighborhood-selection methods.This assumption is applied to both neighborhood-selection problems.
  • Optimization: Both problems are concave with smooth log-likelihoods and linear constraints, and are solved using projected gradient descent.The chosen optimization scheme is stated to have a convergence guarantee.
Loading 1301.4183v2…