PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficiently learning Ising models on arbitrary graphs

Guy Bresler

arXiv:1411.6156v2cs.LGcs.ITstat.ML

TL;DR

The paper asks whether Ising-model structure on arbitrary bounded-degree graphs can be learned faster than exhaustive p^d neighborhood search. It proposes a greedy conditional-influence procedure and proves that a neighbor with high mutual information always exists, enabling graph recovery in near-quadratic time. The method requires only identifiability-related parameter bounds, but its dependence on degree is doubly exponential.

  • Problem

    Learning Ising structure on general p-node graphs of maximum degree d was not known to be possible in less than the p^d cost of exhaustive neighborhood search.

  • Method

    The algorithm greedily adds nodes with highest conditional influence to form a constant-size pseudo-neighborhood, using a structural high-mutual-information property.

  • Results

    Given n = f(d) log p samples, the underlying graph can be learned in time f(d)p^2 log p on arbitrary graphs of maximum degree at most d.

  • Takeaways & Limitations

    Efficient structure learning extends from trees to arbitrary bounded-degree Ising graphs and does not require correlation decay or high-temperature assumptions.

  • Takeaways & Limitations

    The factor f(d) in sample complexity and runtime depends doubly-exponentially on d, despite exponential dependence on βd being necessary.

Abstract

from arXiv · show

We consider the problem of reconstructing the graph underlying an Ising model from i.i.d. samples. Over the last fifteen years this problem has been of significant interest in the statistics, machine learning, and statistical physics communities, and much of the effort has been directed towards finding algorithms with low computational cost for various restricted classes of models. Nevertheless, for learning Ising models on general graphs with $p$ nodes of degree at most $d$, it is not known whether or not it is possible to improve upon the $p^{d}$ computation needed to exhaustively search over all possible neighborhoods for each node. In this paper we show that a simple greedy procedure allows to learn the structure of an Ising model on an arbitrary bounded-degree graph in time on the order of $p^2$. We make no assumptions on the parameters except what is necessary for identifiability of the model, and in particular the results hold at low-temperatures as well as for highly non-uniform models. The proof rests on a new structural property of Ising models: we show that for any node there exists at least one neighbor with which it has a high mutual information. This structural property may be of independent interest.

1 Introduction

Learning Ising-model structure on arbitrary bounded-degree graphs was previously approached through exhaustive neighborhood searches or restrictive assumptions. This paper gives a greedy O(p^2 log p) approach, supported by a structural mutual-information property.

  • 1 Introduction: p^d computation is required by exhaustive searches over candidate neighborhoods when learning general graphs of maximum degree d.The search tests whether each candidate neighborhood implies the relevant conditional independence.
  • 1 Introduction: Previous efficient algorithms typically restrict graph structure or interactions, often requiring correlation decay.Examples include tree-structured models and models in high-temperature regimes.
  • 1.2 Results: For every node, some neighbor has mutual information at least a constant independent of p.A stronger conditional-influence statement allows conditioning on arbitrary node subsets and yields a mutual-information lower bound.
  • 1.2 Results: A greedy algorithm reconstructs arbitrary bounded-degree Ising graphs in time f(d)p^2 log p, with f(d) depending on interaction-strength range and degree.The result uses n = f(d) log p samples.
  • 1.2 Results: The runtime and sample-complexity factor f(d) depends doubly-exponentially on d, while exponential dependence on βd is necessary.The paper identifies improving this degree dependence as an important direction for practical applicability.
  • 1.2 Results: The algorithm greedily adds nodes according to conditional influence to form a constant-size pseudo-neighborhood containing the true neighborhood.It only adds nodes; under long-range correlations, this supports a potential argument based on reducing conditional entropy.

2 Preliminaries

The paper models binary spins with pairwise interactions on a graph and studies exact graph recovery from independent samples. Its formulation imposes bounded degree and identifiable interaction parameters, with worst-case reconstruction error as the performance criterion.

  • 2.1 Ising model: An Ising model is a Markov random field with binary spin variables and pairwise potential functions.Each configuration assigns values in {−,+} to the graph’s nodes.
  • 2.1 Ising model: The graph has p nodes, each node’s degree is at most d, and ∂i denotes its neighbor set.The model is defined on G = (V,E) with |V| = p.
  • 2.1 Ising model: The parameter vector contains edge couplings and node-wise external fields, with α ≤ |θij| ≤ β on edges and |θi| ≤ h.These bounds are necessary for identifiability and enter the sample complexity.
  • 2.1 Ising model: Given all other spins, a node is conditionally independent of non-neighbors once its neighbors’ values are known.This Markov property underlies conditional-independence-based structure learning.
  • 2.2 Graphical model learning: The learning algorithm maps n independent samples to an estimated graph and is evaluated by zero-one loss for exact graph recovery.The goal is worst-case reconstruction risk tending to zero as p grows while using as few samples as possible.
  • 2.2 Graphical model learning: Exponential dependence of sample complexity, and therefore runtime, on βd is unavoidable.This follows from an established lower bound cited by the paper.

3 Measuring the influence of a variable

The paper defines conditional influence and its averaged empirical counterpart for testing whether a candidate node belongs to a neighborhood. The influence vanishes for non-neighbors once the full neighborhood is conditioned on, while at least one missing neighbor retains a constant lower bound.

  • Conditional influence measures the change in P(Xu = +) when Xi switches state under a configuration xS.
  • Average conditional influence weights the absolute conditional influence over configurations of XS using λi(xS).The weight is λi(xS) = 2 · P(Xi = +|XS = xS)P(Xi = −|XS = xS).
  • If ∂u ⊆ S, conditional influence is zero for every candidate i outside S ∪ {u}.This follows from the Markov property.
  • When S omits part of ∂u, Proposition 5.3 guarantees at least one remaining neighbor has average conditional influence bounded below.The algorithm uses this property to determine whether the neighborhood has been fully included.
  • The empirical version replaces the population probabilities with empirical probabilities computed from samples.
  • Event A(ℓ, ǫ) requires empirical influences for conditioning sets of size at most ℓ to be accurate within additive ǫ.The required sample size is controlled through this uniform accuracy event.

4 Algorithm

LearnNbhd greedily constructs a pseudo-neighborhood by adding the node with highest empirical average conditional influence until no candidate exceeds a threshold, then prunes low-influence nodes. Its guarantee is simultaneous correctness and near-quadratic runtime with high probability.

  • LearnNbhd builds a pseudo-neighborhood by greedily adding the node with highest empirical average conditional influence.The procedure targets the neighborhood of one node u using samples and threshold τ.
  • Including non-neighbors lets each addition reduce H(Xu|XS) by at least τ, so nonnegativity of entropy bounds the pseudo-neighborhood size.This potential argument is the stated reason for allowing spurious nodes during construction.
  • Proposition 5.3 ensures the algorithm does not stop before all neighbors are added and does not remove neighbors during pruning.
  • The algorithm adds the maximizer when its influence is at least τ and stops otherwise, then performs a pruning step.
  • With probability at least 1−ζ, LearnNbhd returns correct neighborhoods for all nodes and has the claimed runtime for each node.The theorem statement supplies the probability guarantee and runtime claim.
  • The stated guarantee is probabilistic, although terminating when runtime exceeds its bound yields a deterministic runtime guarantee.

5 Algorithm correctness

Correctness follows from a structural lower bound on the influence of an omitted neighbor, an entropy-based bound on pseudo-neighborhood size, and concentration of empirical influences. Pruning then removes exactly the non-neighbors.

  • If LearnNbhd adds a node to the pseudo-neighborhood, its conditional mutual information with u given previously added nodes is at least a positive threshold.
  • A potential argument bounds the pseudo-neighborhood size by ℓ(τ, ǫ) = 2(τ − ǫ)^−2.Each added node contributes a lower-bounded conditional mutual-information increment.
  • The runtime of the pseudo-neighborhood step is O(|S|pn) = O(ℓ*pn), which dominates the runtime.
  • Proposition 5.3 guarantees a remaining neighbor with sufficiently large influence whenever the current set omits part of the true neighborhood.
  • Consequently, the pseudo-neighborhood contains the true neighborhood, and after pruning it equals ∂u.
  • The theorem completes the argument by choosing n so event A(ℓ*, ǫ*) holds with probability at least 1−ζ.

6 Proof of Proposition 5.3

The proof of Proposition 5.3 analyzes the effect of omitted neighbors after conditioning on an arbitrary set S. It uses conditional probabilities, effective fields, rescaling, inequalities, and averaging to establish the required influence lower bound.

  • For omitted neighbors U = ∂u \ S, the proof fixes a configuration xS and analyzes the conditional distribution of Xu given the remaining neighbors.
  • The effective external field at u incorporates the contribution of neighbors already included in S.
  • The proof represents the remaining-neighbor states by a random vector Y under the conditional law given XS = xS.
  • Rescaling Yi/Q(Yi) to take values ±1 enables the subsequent algebraic bounds.
  • The argument combines inequalities and then averages over xS to obtain the proposition’s lower bound on conditional influence.

7 Technical lemma

The section establishes anti-concentration and positivity properties for a conditioned Ising-model random variable, then uses them to lower-bound the key expectation in Equation (7).

  • Mixture decomposition: The conditioned vector Y assigns positive probability to every configuration, enabling a uniform component in the decomposition of Z.The uniform component has total mass 2t = 2|U| · δ^|U|.
  • Anti-concentration: Lemma 7.1 supplies anti-concentration for weighted sums of independent uniform ±1 variables over intervals of length 2α.This result is combined with a mixture decomposition of the conditioned variable.
  • Mixture decomposition: The mixture argument shows that Z places probability at least t outside a central interval around its mean.With It = (µ − tα, µ + (2 − t)α), the bound is P(Z ∉ It) ≥ t.
  • Deviation bound: The resulting mass-placement argument yields a lower bound on one-sided deviation, E[(µ − Z)1{Z≤µ−αt}] ≥ αt^2/2.At least one of two nonnegative terms contributes at least the average amount.
  • Technical lemma: Using 2g(x)−1 = tanh(x·θuU + eθu), monotonicity and curvature of tanh convert these deviation bounds into a nonnegative lower bound for E[tanh(Z)(Z−µ)].The proof treats µ ≥ 0 and notes that the µ ≤ 0 case is symmetric.
  • Technical lemma: The two terms produced after subtracting tanh(µ)E(Z−µ)=0 are both non-negative, completing the key sign argument.This is the final positivity step used to justify Equation (7).

8 Proof of Lemma 3.2

This section proves Lemma 3.2 by uniformly controlling empirical conditional probabilities over small conditioning sets and choosing the sample size to achieve the desired accuracy.

  • Uniform control: The proof seeks a uniform bound for conditional-probability quantities over all node subsets and configurations of bounded cardinality.The argument assumes the high-probability event in Equation (16) after applying a union bound.
  • Uniform control: At most (ℓ+2)(2p)^(ℓ+2) subset-configuration choices require simultaneous control when conditioning sets have size at most ℓ+2.This combinatorial count drives the union-bound sample requirement.
  • Error decomposition: The comparison between empirical and population quantities uses Bayes’ rule, the triangle inequality, and an algebraic decomposition of products.These steps reduce the target bound to errors in lower-dimensional conditional probabilities.
  • Error decomposition: The denominator lower bound q := δ^ℓ controls conditioning-event probabilities and contributes the factor q^−1 = δ^−ℓ ≥ 2^|S|.This converts uniform joint-probability accuracy into conditional-probability accuracy.
  • Accuracy: Choosing γ = ϵδ^ℓ/12 gives the desired accuracy with the sample size obtained by evaluating the earlier concentration requirement.The resulting sample-size expression is stated after this parameter choice.

9 Discussion

The discussion emphasizes the algorithm’s quadratic runtime while identifying runtime and sample-complexity dependence on parameters, unknown model complexity, and bounded-degree assumptions as open issues.

  • Implications: Quadratic runtime in the number of nodes, ignoring a log factor, shows that high graph degree is not an obstacle to efficient structure learning.The authors also mention possible subquadratic or input-sparsity improvements as open possibilities.
  • Open problems: The doubly-exponential dependence of runtime and sample complexity on βd is identified as the most urgent practical improvement target.The authors suspect singly exponential dependence may be possible.
  • Practical limitations: In practice, the degree d and parameter bounds α, β, h may be unknown, leaving model-complexity selection unresolved.The discussion suggests BIC or another method as a possible aid.
  • Scope: Uniformly bounded node degrees may be restrictive, although the algorithm might be modifiable for graphs with unbounded degree but low average degree.Larger alphabets would also require more complicated non-degeneracy conditions.
Loading 1411.6156v2…