Information-theoretic limits of selecting binary graphical models in high dimensions

Narayana Santhanam; Martin J. Wainwright

Source-linked AI summary

Information-theoretic limits of selecting binary graphical models in high dimensions

Narayana Santhanam, Martin J. Wainwright

arXiv:0905.2639v1May 16, 2009cs.ITcs.LGmath.ST

TL;DR

The paper asks how many samples are required to recover high-dimensional binary graphical models. It analyzes Ising models using information-theoretic lower bounds and explicit graph decoders, obtaining necessary and sufficient scaling laws for bounded-edge and bounded-degree classes.

Problem
The problem is to recover an unknown Markov random-field graph from samples when graph size and structural parameters grow with sample size.
Method
The paper analyzes pairwise binary Ising models using Fano-based necessary conditions and explicit graph decoders for sufficient conditions.
Results
For Gp,k, recovery requires at least c k log p samples and succeeds above c' k^2 log p; for Gp,d, the corresponding bounds are c d^2 log p and c' d^3 log p.
Takeaways & Limitations
The results characterize information-theoretic graph-selection capacity and indicate when computationally efficient methods may be optimal or sub-optimal.
Takeaways & Limitations
The analysis is limited to pairwise binary Markov random fields, or Ising models.

Abstract

from arXiv · show

The problem of graphical model selection is to correctly estimate the graph structure of a Markov random field given samples from the underlying distribution. We analyze the information-theoretic limitations of the problem of graph selection for binary Markov random fields under high-dimensional scaling, in which the graph size $p$ and the number of edges $k$, and/or the maximal node degree $d$ are allowed to increase to infinity as a function of the sample size $n$. For pairwise binary Markov random fields, we derive both necessary and sufficient conditions for correct graph selection over the class $\mathcal{G}_{p,k}$ of graphs on $p$ vertices with at most $k$ edges, and over the class $\mathcal{G}_{p,d}$ of graphs on $p$ vertices with maximum degree at most $d$. For the class $\mathcal{G}_{p, k}$, we establish the existence of constants $c$ and $c'$ such that if $\numobs < c k \log p$, any method has error probability at least 1/2 uniformly over the family, and we demonstrate a graph decoder that succeeds with high probability uniformly over the family for sample sizes $\numobs > c' k^2 \log p$. Similarly, for the class $\mathcal{G}_{p,d}$, we exhibit constants $c$ and $c'$ such that for $n < c d^2 \log p$, any method fails with probability at least 1/2, and we demonstrate a graph decoder that succeeds with high probability for $n > c' d^3 \log p$.

1 Introduction

The paper studies the information-theoretic limits of recovering binary Markov random-field graphs when graph size and structural parameters scale with sample size. It derives necessary and sufficient conditions for bounded-edge and bounded-degree graph classes using lower-bound arguments and explicit decoders.

Motivation: Markov random fields represent joint distributions through graphs encoding conditional independences, and graph selection recovers the unknown graph from samples.These models are used in image analysis, social networks, and computational biology.
High-dimensional setting: High-dimensional graph selection allows p, k, and d to increase with n, unlike analyses that fix the graph while increasing sample size.The paper focuses on scaling relations among sample size, graph size, edge count, and maximum degree.
Problem formulation: The information-theoretic problem considers n i.i.d. samples from a model whose graph belongs to either Gp,k or Gp,d.The classes constrain total edge count or maximum vertex degree.
Scope: The analysis is restricted to pairwise binary Markov random fields, also called Ising models.The paper notes applications of Ising models in image analysis, social-network modeling, and gene-network analysis.
Information-theoretic perspective: The paper treats observations as a channel communicating graph information and relates graph distances to KL divergence for controlling testing errors.This perspective is used to characterize graph-selection capacity.
Why the limits matter: Understanding graph-selection capacity can identify when efficient algorithms are optimal up to constants and when existing methods are sub-optimal.The paper states that its analysis has consequences of both types.
Contributions: Four main theorems provide necessary and sufficient conditions for bounded-edge and bounded-degree classes.Necessary conditions use Fano-type arguments on graph subfamilies, while sufficient conditions use explicit graph decoders.

2 Background and problem formulation

This section defines the Ising-model setting, graph classes, parameter constraints, sampling problem, and decoder-based error criterion. It also explains why large neighborhood weights make graph distinction difficult and motivates the paper’s parameterized classes.

2.1 Markov random fields and Ising models: An undirected graph has vertices and edges; degree is neighbor-set cardinality, while d is maximum degree and k is total edge count.The paper forbids self-loops.
2.1 Markov random fields and Ising models: In an Ising model, each vertex variable takes values −1 or +1, and the parameter vector is zero outside the graph’s edge set.Each edge weight describes conditional dependence between its incident variables given the others.
2.2 Classes of graphical models: The model classes Gp,d and Gp,k constrain graphs by maximum degree d or by at most k edges, respectively.These graph families are used to define corresponding distribution classes with parameter restrictions.
2.2 Classes of graphical models: Minimum edge weight λ matters because interactions near zero are difficult to detect, while large edge weights can mask other interactions.The paper therefore studies both a lower bound on edge weights and an upper bound on maximum neighborhood weight.
2.2 Classes of graphical models: Figure 1 uses three two-edge graphs on three vertices to show that increasing a common edge weight makes their induced distributions increasingly difficult to separate.In the infinite-weight limit, the models become non-identifiable through a hard-core constraint.
2.2 Classes of graphical models: The sample size needed to distinguish graphs grows exponentially with the maximum neighborhood weight.This motivates explicitly parameterizing model classes by λ and ω.
2.3 Graph decoders and error criterion: The statistician observes n i.i.d. samples of binary vectors and uses a graph decoder to infer the underlying graph under 0-1 loss.Risk is the probability of incorrect graph selection.
2.3 Graph decoders and error criterion: The paper studies known- and unknown-edge-weight variants, with lower bounds proved for the known case and separate sufficiency conditions for the variants.The unknown-edge-weight problem is stated to be more difficult.

3 Main results and some consequences

The paper derives worst-case necessary and sufficient sample-size conditions for graph recovery over bounded-degree and bounded-edge graph families. Its bounds reveal logarithmic dependence on p, polynomial dependence on d or k, and gaps between information-theoretic lower bounds and decoder guarantees.

Necessary conditions: For bounded-degree graphs, any method requires at least n > c max{d^2, λ^-2} log p samples to recover the graph with probability at least 1/2.This is a worst-case necessary condition for increasing maximum degree d.
Necessary conditions: For graphs with at most k edges, any method requires at least n > c max{k, λ^-2} log p samples for recovery probability at least 1/2 in the worst case.The lower bound uses adversarial graph constructions, including dense subgraphs, so it need not translate directly to every graph with k edges.
Proof strategy: The paper proves four main theorems: Fano-based lower bounds and direct analyses of explicit graph decoders for the two graph classes.The framework treats necessary conditions as limits applying to any decoder and sufficient conditions as guarantees for constructed procedures.
Consequences: For bounded-degree graphs, known edge weights achieve the information-theoretic scaling λ^-2 log p, while unknown weights have the weaker guarantee λ^-4 log p.The paper notes that the unknown-weight guarantee may be improvable through more careful analysis.
Sufficient conditions: For increasing maximum degree, a graph decoder succeeds with high probability using n > c1 max{d^2, λ^-2} d log p samples.Together with the necessary condition, this leaves a factor-d gap in the sample-complexity bounds.
Sufficient conditions: When λ ≍ k^-1/2, a known-weight decoder succeeds with high probability using n > c k^2 log p samples, within a factor k of the necessary condition.The sufficient condition is stated for the known edge-weight variant.

4 Proofs of necessary conditions

The necessary-condition proofs combine divergence-based distinguishability analysis with Fano-style lower bounds over carefully constructed graph ensembles. These constructions establish when no decoder can reliably recover the graph.

Distance measures: The analysis defines KL-based distances between Ising models to quantify their distinguishability.It uses ordinary and symmetrized KL divergences, along with a divergence based on an averaged model.
Model classes: Graph-class cardinality bounds provide large model families for the bounded-edge and bounded-degree settings.The paper derives bounds for |G_p,k| and |G_p,d| and constructs many bounded-degree graphs using grouped vertices and permutations.
Fano lower bounds: Fano’s lemma and its variants show that sufficiently small sample sizes make every decoder unreliable over a finite model family.The condition depends on the family size and information shared between the random model index and the samples.
Fano lower bounds: The lower-bound construction seeks many models that remain close in symmetrized KL divergence while differing in their graph structures.Controlling the mean parameters on changed edges controls the divergence between the corresponding distributions.
Key separation construction: Removing one edge from a complete graph creates an ensemble of Ising models whose edge correlations approach their maximum exponentially quickly as ω = λm grows.Each model assigns weight λ to every retained edge and zero to the removed edge.
Proof of Theorem 1: For bounded-degree models, single-edge and grouped graph ensembles yield explicit sample-size regimes where graph recovery is unreliable.The argument applies Fano’s inequality to multiple ensembles contained in G_p,d(λ, ω).

5 Proofs of sufficient conditions

The sufficient-condition proofs analyze explicit graph decoders directly. The paper uses maximum likelihood decoding and large-deviation control to establish reliable recovery.

Proof strategy: The sufficient conditions are proved by direct analysis of explicit graph decoders.The decoder searches over candidate graphs in the prescribed class rather than using an indirect impossibility argument.
Proof strategy: The maximum likelihood decoder exhaustively searches the graph class and selects the model with highest likelihood.Its performance is governed by a standard large-deviations bound.
Proof strategy: The remaining proof establishes conditions under which the decoder’s error probability vanishes.This requires controlling likelihood comparisons across competing graphs.

5.1 ML decoding and large deviations bound

This section formalizes maximum likelihood decoding and bounds its error by comparing the true model with every competing graph. A large-deviation inequality controls each comparison.

ML decoding: The maximum likelihood decoder maps the samples to a graph maximizing the model likelihood over the graph class.Ties are resolved by choosing some maximizing graph.
ML decoding: The decoder fails only when another graph achieves likelihood at least as large as the true graph.The analysis conservatively counts equality as failure.
Large deviations: A union bound reduces the decoder’s total error probability to a sum over competing graphs.This makes pairwise likelihood-comparison bounds sufficient for controlling overall error.
Large deviations: The Chernoff bound provides an exponential control on the probability that a competing model’s likelihood exceeds the true model’s likelihood.The argument applies the bound to the likelihood-ratio random variable under the true distribution.
Large deviations: The resulting exponent is expressed through the divergence J(θ ∥θ′) and the model normalization constants.The proof invokes the cumulant-function representation of J.

5.2 Lower bounds based on matching

The matching-based argument lower-bounds divergence between distinct graph models by isolating disjoint edge discrepancies. The chain rule then decomposes the comparison into conditional contributions.

Graph discrepancy: The relevant graph discrepancy is the symmetric difference E∆E′ between the two edge sets.Its matching number measures how many mutually vertex-disjoint changed edges can be selected.
Matching construction: A maximal matching in E∆E′ supplies disjoint edge pairs for the divergence analysis.The proof denotes these edges by e_1, ..., e_m and separates vertices not involved in the matching.
Divergence lower bound: The chain rule for KL divergences decomposes the symmetrized divergence into conditional divergences associated with the matched edges.Conditional distributions are formed for the variables on each edge given previously selected variables.

5.3 Proof of Theorem 3(a)

For graphs with maximum degree at most d, the proof bounds the number of competing graphs by their edge mismatch and applies concentration and matching-based separation to control decoder error.

ℓ = |E ∆E′| ranges from 1 to dp for graphs with maximum degree at most d.A graph with maximum degree d has at most dp/2 edges.
Graphs differing from a fixed graph in ℓ edges have their matching number lower-bounded by ℓ/(4d).
The proof applies a union bound, a large deviations bound, and the matching-based lower bound to control the graph decoder’s error probability.
The resulting error probability is at most δ under the sample-size conditions in Theorem 3(a).

5.4 Proof of Theorem 4

For graphs with at most k edges, the proof counts alternatives by their edge mismatch using vertex-cover structure, then combines this count with concentration and separation bounds.

m = |E ∆E′| ranges from 1 to 2k for competing graphs in Gp,k.
A maximal matching over the mismatched edges yields a vertex cover used to enumerate competing graphs.
The enumeration proceeds by specifying missing edges, cover vertices, and vertices connected to the cover, producing the stated bound on possibilities.
The proof combines the union bound, a large deviations bound, and matching-based separation to bound the decoder error.
The error probability is less than δ under the conditions of Theorem 4.

5.5 Proof of Theorems 3(b) and 4(b)

The sufficient-condition proofs use a projection-based decoder comparing empirical mean parameters with graph-constrained model classes, controlled by deviation and pairwise-separation lemmas.

The unknown-parameter setting rules out the simple ML decoder and motivates a decoder based on graphwise projection distances.
The decoder computes the graph whose constrained model class is closest to the empirical mean parameters, allowing ties.
Decoder failure can occur only when some competing graph has a nonpositive difference in projection distance from the true graph.
The key lower bound separates competing population mean parameters while subtracting twice the empirical mean-parameter deviation.
Lemma 5 controls elementwise sample-to-population deviations using a tail bound derived from Hoeffding’s inequality.
Lemma 6 establishes pairwise separation on edges where two graph structures differ, using conditional distributions and divergence bounds.
Combining the lemmas yields positivity of the projection-distance difference under the sufficient sample-size conditions.

6 Discussion

The discussion summarizes necessary and sufficient sample-size bounds for sparse and bounded-degree binary graphical model selection, with tightness for fixed structural complexity and gaps for growing complexity.

The paper establishes necessary and sufficient conditions for graph classes bounded by edge count k or maximum degree d in a high-dimensional setting.
The analysis focuses on pairwise binary graphical models, while many techniques and results may extend to more general discrete graphical models.
For Gp,d, any algorithm requires at least n > c d^2 log p samples, while the demonstrated algorithm succeeds using n < c′ d^3 log p samples.
For Gp,k, any algorithm requires at least n > c k log p samples, while the demonstrated algorithm succeeds using n < c′ k^2 log p samples.
For constant d or k, the bounds characterize information-theoretic complexity up to constant factors; growing parameters leave gaps of order d and k.

A A separation lemma

The lemma establishes a separation property for two distinct graphical models by analyzing how their conditional distributions and parameter differences respond to configuration changes. Its proof uses a contradiction argument involving quadratic inequalities and configuration flips.

A A separation lemma: Lemma 7 compares distinct graphs when an edge belongs to E but not E′, conditioning on any subset U excluding that edge’s endpoints.The comparison is expressed through the divergence between conditional distributions of (X_u, X_v) given X_A = x_A.
A A separation lemma: The proof introduces the parameter difference Δ(x) through the ratio α(x) = exp(Δ(x)/2) between the two model expressions.The notation is organized around unnormalized distributions Qθ and Qθ′ and the edge contributions in the two graphs.
A A separation lemma: Configuration flips preserve enough of β(y) while mapping configurations in Y*(x_U) outside that set, with at most three source configurations mapping to one target.The flip-based counting argument uses a factor of exp(2ω) to control the change in β(y).

B Proof of a flipping lemma

The flipping lemma shows that a missing edge in one model forces a detectable change in the model discrepancy when either endpoint’s spin is flipped. The proof establishes this by decomposing neighborhood contributions and ruling out a constant discrepancy through contradiction.

B Proof of a flipping lemma: For any edge in E\E′, flipping either endpoint or both changes Δ(x) by at least |θ_st|.This is the lemma’s central quantitative separation guarantee for configurations in {−1, +1}^p.
B Proof of a flipping lemma: The proof represents neighborhood terms using N(s), N′(s), N(t), and N′(t), then isolates contributions not involving the two flipped vertices.These auxiliary quantities organize the comparison of the two models’ edge contributions.
B Proof of a flipping lemma: Assuming Δ(x) remains fixed for all four endpoint-spin assignments implies θ_st = 0, contradicting that (s,t) is an edge present only in E.The argument compares equations for different choices of (x_s, x_t) and combines them algebraically.
B Proof of a flipping lemma: If all four discrepancy values lie within an interval of width 2ε around a common value, the inequalities force θ_st ≤ ε.Repeating the argument with reversed inequalities supplies the corresponding lower-side constraint.