Source-linked AI summary
Reconstruction of Markov Random Fields from Samples: Some Easy Observations and Algorithms
Guy Bresler, Elchanan Mossel, Allan Sly
TL;DR
The paper studies reconstructing the dependency graph of a bounded-degree Markov random field from independent samples. It proposes reconstruction algorithms with near-sharp sample complexity, analyzes computational costs, and examines noisy, partial, and hidden-variable settings.
Problem
The central problem is recovering a Markov random field's graph structure from independent samples of its high-dimensional distribution.
Method
The paper analyzes simple neighborhood-testing algorithms based on marginal and conditional correlations, extending them to noisy observations, partial observations, and selected hidden-variable models.
Results
The algorithms use O(d ε^-2δ^-4 log n) samples under non-degeneracy conditions, with runtime O(n^d+2 ε^-2δ^-4 log n) and improved runtime under correlation decay.
Takeaways & Limitations
The results provide high-probability graph reconstruction for broad model classes, while weak noise can be tolerated and sufficiently large noise can make reconstruction non-identifiable.
Takeaways & Limitations
The guarantees require non-degeneracy conditions, and without assumptions on the model or noise the graph is not necessarily identifiable.
Abstract
from arXiv · showhide
Markov random fields are used to model high dimensional distributions in a number of applied areas. Much recent interest has been devoted to the reconstruction of the dependency structure from independent samples from the Markov random fields. We analyze a simple algorithm for reconstructing the underlying graph defining a Markov random field on $n$ nodes and maximum degree $d$ given observations. We show that under mild non-degeneracy conditions it reconstructs the generating graph with high probability using $Θ(d ε^{-2}δ^{-4} \log n)$ samples where $ε,δ$ depend on the local interactions. For most local interaction $\eps,δ$ are of order $\exp(-O(d))$. Our results are optimal as a function of $n$ up to a multiplicative constant depending on $d$ and the strength of the local interactions. Our results seem to be the first results for general models that guarantee that {\em the} generating model is reconstructed. Furthermore, we provide explicit $O(n^{d+2} ε^{-2}δ^{-4} \log n)$ running time bound. In cases where the measure on the graph has correlation decay, the running time is $O(n^2 \log n)$ for all fixed $d$. We also discuss the effect of observing noisy samples and show that as long as the noise level is low, our algorithm is effective. On the other hand, we construct an example where large noise implies non-identifiability even for generic noise and interactions. Finally, we briefly show that in some simple cases, models with hidden nodes can also be recovered.
1 Introduction
The paper studies reconstruction of bounded-degree Markov random-field graphs from independent samples, proposing algorithms with near-optimal sample complexity under non-degeneracy conditions. It also treats noisy and partial observations, computational complexity, and broader interaction structures than prior work.
- Our Results: O(d ε^-2δ^-4 log n) samples suffice for reconstruction under mild non-degeneracy conditions, with ε and δ determined by local marginal interactions.For many models, ε and δ are exp(-O(d)); for fixed degree, they are constant.
- Our Results: With weak noise, the reconstruction algorithms remain effective, whereas sufficiently large unknown noise can make graph recovery non-identifiable.The paper also gives sufficient conditions for reconstruction from partial observations.
- Our Results: O(n^(d+2) ε^-2δ^-4 log n) time is provided generally, while correlation decay yields O(d n^2 ε^-2δ^-4 log n) time.The improved running time applies to some Markov random fields exhibiting decay of correlation.
- Our Results: The algorithms target the generating graph itself, unlike approaches that only seek a distribution close in Kullback–Leibler divergence.The paper contrasts exact structure recovery with prior KL-based model approximation.
- Related Work: The framework extends beyond pairwise Ising models to Markov random fields with potentials on larger cliques.Prior cited work is described as restricted to pairwise potentials and binary variables.
2 Preliminaries
The preliminaries define Markov random fields through graph separation and describe their factorized representation over clique potentials. They then formalize graph reconstruction from independent samples for bounded-degree graphs.
- Definitions: A Markov random field is a distribution on assignments to graph vertices satisfying conditional independence across graph separators.The definition uses disjoint sets W, U, and S where every path from W to U passes through S.
- Definitions: The Hammersley–Clifford representation factors the distribution over graph cliques using potential functions and a normalizing constant.Each potential maps assignments on a clique to real values or negative infinity.
- Problem Setup: The reconstruction problem receives k independent samples and estimates the underlying graph from the class of labeled graphs with maximum degree at most d.A structure estimator maps sample sequences to candidate graphs in this class.
3 Lower Bound on Sample Complexity
The paper proves an information-theoretic lower bound showing that reconstructing a uniformly random bounded-degree graph requires order d log n samples. The proof compares the number of possible graphs with the information supplied by observations.
- Proof Strategy: The proof uses a uniform prior over bounded-degree graphs and bounds the maximum a posteriori estimator’s success probability.The argument counts possible graphs and compares that count with the information available from k samples.
- Lower Bound Theorem: Ω(d log n) samples are necessary for reliable reconstruction of a uniformly random graph with maximum degree at most d.If k ≤ c d log n for a sufficiently small constant c, every estimator has vanishing probability of correct reconstruction.
- Lower Bound Theorem: The lower bound applies without assumptions on the graph potentials, including settings where the graph may not be identifiable from unlimited samples.The theorem concerns any potentials consistent with the generating graph.
- Proof Strategy: The graph-counting lemma supplies the combinatorial estimate needed to relate the number of candidate graphs to n and d.The proof constructs larger bounded-degree graphs from smaller ones and handles even and odd n separately.
4 Reconstruction
The paper reconstructs each vertex neighborhood by testing candidate sets against the Markov property, with two algorithms trading stronger non-degeneracy assumptions for faster computation. Under suitable conditions, the resulting estimator recovers the generating graph with high probability using O(d ε^-2δ^-4 log n) samples, while correlation decay reduces the running time for fixed degree.
- Reconstruction method: The algorithms test candidate neighborhoods using conditional-probability relations implied by the Markov property.For each vertex, candidate sets of size at most d are evaluated; the selected set is the smallest or largest candidate passing the relevant score test.
- Reconstruction method: The two reconstruction theorems differ in non-degeneracy requirements and running time, with the first using more stringent conditions for faster computation.The faster estimator is computable in O(n^(d+2) log n) operations, whereas the more general estimator takes O(n^(2d+1) log n).
- Model conditions: The general theorem covers soft-constraint models and Ising models when their interaction potentials satisfy the required non-degeneracy conditions.For soft constraints, bounded potentials and a nonzero interaction condition yield ε and δ depending on d, K, and γ.
- Computational improvement: O(n^2 log n) running time is achievable for fixed d when correlations decay exponentially with graph distance and neighboring correlations remain above a positive threshold.The algorithm first restricts candidate neighborhoods to a constant-radius correlation neighborhood before applying the general reconstruction procedure.
5 Noisy and Incomplete Observations
The paper extends graph reconstruction to noisy observations and settings with missing vertices. Weak noise can preserve recovery, while unrestricted noise can destroy identifiability; under structural assumptions, missing vertices can also be recovered.
- Noisy observations: Small amounts of noise preserve reconstruction under a sufficient condition comparing observed and original local probabilities.The condition bounds differences in joint and conditional probabilities using ϵ′ < ϵ and δ′ < δ.
- Noisy observations: k = C′d log n samples suffice for high-probability reconstruction under the stated noise conditions.The reconstruction algorithm from Theorem 3 continues to recover G correctly with high probability.
- Non-identifiability: Without assumptions on the model or noise, one distribution can correspond to different graph structures, making reconstruction non-identifiable.An Ising example is given where unknown noise prevents distinguishing a three-vertex graph with two edges from one with three edges.
- Models With Hidden Variables: Replacing each maximal clique in the observed graph with a vertex connected to its clique members exactly reconstructs the graph with high probability.The construction relies on each missing vertex producing a clique among its observed neighbors in the triangle-free setting.
- Models With Hidden Variables: The distance-at-least-3 assumption simplifies recovery because the cliques associated with missing vertices are disjoint.A more involved algorithm can handle missing vertices at distance 2.