GraphInfer: Statistical Inference for Decomposable Graphical Models in R
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Statistics. The day in statistics: methods, theory and the inference under them.
Tom: We're looking at the paper: "GraphInfer: Statistical Inference for Decomposable Graphical Models in R".
Jane: Here's the gist of the paper. Decomposable graphical models are addressed by GraphInfer, an R package designed for closed-form maximum likelihood estimation coupled with local model comparison, making structure inference practical for models with many variables.
Tom: The package supports decomposable models of continuous, discrete, and mixed data types, including conditional Gaussian models.
Jane: GraphInfer offers four primary themes: 1.
Tom: Common Inferential Framework: It provides a single framework for fitting decomposable Gaussian, discrete, or conditional Gaussian models using one likelihood calculation and a unified convention for model dimension.
Paper summary: Jane: So, wrapping up this discussion on "GraphInfer: Statistical Inference for Decomposable Graphical Models in R", what's the main message we should take away from this work?
Tom: The central idea is making structure inference practical for models with many variables by combining closed-form maximum likelihood estimation with local model comparison. It unifies the approach across continuous, discrete, and mixed data types.
Lu: It really makes graph search feasible in high-dimensional settings because of those closed-form estimates and the properties of decomposable models that allow adding or removing one edge to be tested locally.
Meng: For me, it means if I'm deploying a model, I need to know if I can efficiently find the right structure without running prohibitively expensive global searches every single time.
Tom: That’s right, and the package gives you those methods—stepwise search for speed or stochastic global search for thoroughness—so you can choose your search effort based on what your problem demands.
Jane: And it addresses messy data too, offering ways to fit models with missing values through techniques like EM or multiple imputation structure inference. It’s a complete toolkit for handling the whole pipeline from structure to final model fit.
Lu: The framework also extends to more specialized scenarios, like irreversible event accumulation on trees, allowing testing hypotheses at both the graph level and the full level with measurement noise included.
Meng: The limitations they state are important too: exact tests aren't available for data with missing values or in the mixed case when you have covariate designs, and greedy searches can get stuck far from optimal solutions.
Tom: So, that’s the balance—it’s a very capable tool for many decomposable models, but you need to know when to use an exact test versus when to rely on more heuristic search strategies.
Conclusion: Tom: So we've been talking about GraphInfer, right? It’s an R package for figuring out how to build these decomposable graphical models, which are those complex structures with a lot of variables that can be broken down into simpler pieces.
Jane: Yeah, and the authors, they made it practical. They built something that lets you do closed-form maximum likelihood estimation right alongside model comparison so structure inference isn't just some theoretical exercise anymore.
Tom: Exactly. It’s about taking those tricky models—continuous data, discrete data, mixed things—and giving you a single framework for fitting them using one likelihood calculation and one way to measure model size, that dimension formula they use is pretty neat too.
Lu: I think the real power here is how they handle the structure search. They offer things like exact minimum forests for certain parts of it, stepwise searches that move edge by edge based on local tests, and even a global search that tries to explore beyond those local traps using a kind of iterated local search strategy.
Meng: For us in production, the part I’m most interested in is how they handle missing values. They have specific tasks for fitting a graph when you already have data, selecting the best graph when your data is missing, and then actually filling in those missing bits using methods like multiple imputation structure inference. That’s real utility for deployment.
Lalam: From my perspective, I see this as a way to rigorously test assumptions about how things are connected in a system. If you’re dealing with event accumulation—like tracking some process over time on a tree structure—they have tools to test the hypothesis that those events actually accumulate, both when there's no noise and when there's measurement noise involved.
Tom: So, what does this all mean for us right now? It means we can finally tackle these complicated graphical models without getting totally stuck in manual, brute-force search methods anymore.
Jane: It means for anyone trying to understand complex data relationships, you can use a single tool to go from a raw graph idea to a fitted model and then rigorously test whether that structure is actually the right one.
Tom: And it opens the door for things that are currently too computationally heavy or too niche for standard software packages. We need to see if this framework can handle real-world data at scale, which is where my concerns lie about how fast these searches actually run on massive datasets.
Department of Mathematics, Aarhus University · RLstatLab
stat.ME, stat.CO
Submitted: 2026-11-12
Updated: 2026-11-12
Comments: 44 pages, 2 figures, 15 tables. The R package GraphInfer 0.1.0 will be submitted to CRAN; until then, the package and the replication material are available from the author on request
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 81/100
The gist: Decomposable graphical models are addressed by GraphInfer, an R package designed for closed-form maximum likelihood estimation coupled with local model comparison…
Key concepts
- Decomposable Graphical Models
- These are statistical models where the overall structure can be broken down into simpler, independent components. This property is crucial because it allows the software to use a single likelihood calculation, simplifying the fitting process for complex models with many variables.
- Structure Inference
- This refers to determining which edges exist in a graphical model based on data. GraphInfer offers multiple methods ranging from exact minimum forests and stepwise searches to stochastic global searches, allowing users to find the most likely underlying structure.
- Likelihood Factorisation
- Decomposability allows the likelihood function of a model to be factored into simpler parts. This factorization is key because it enables local updates; adding or removing an edge can be tested efficiently by only looking at the affected local parts of the model.
- Extended BIC
- This is a heuristic criterion used for selecting graphs, especially in models with mixed or sparse discrete data. It extends standard Bayesian information criteria to provide a penalty that helps balance model fit against complexity when exact methods are not feasible.
Terminology
Summary
Decomposable graphical models are addressed by GraphInfer, an R package designed for closed-form maximum likelihood estimation coupled with local model comparison, making structure inference practical for models with many variables. p. 0 GraphInfer: Statistical Inference for Decomposable Graphical
Models in R
Rodrigo Labouriau ∗
Abstract
Decomposable graphical models combine closed-form maximum likelihood estimation
with local model comparison, which makes structure inference practical with many
variables. The R package GraphInfer provides one likelihood framework for decomposable
models of continuous, discrete and mixed data, the last as conditional Gaussian
models. GraphInfer: Statistical Inference for Decomposable Graphical
Models in R
Rodrigo Labouriau ∗
Abstract
Decomposable graphical models combine closed-form maximum likelihood estimation
with local model comparison, which makes structure inference practical with many
variables. The R package GraphInfer provides one likelihood framework for decomposable
models of continuous, discrete and mixed data, the last as conditional Gaussian
models.Where the paper says it
Where the paper says it
GraphInfer offers four primary themes:
-
Common Inferential Framework: It provides a single framework for fitting decomposable Gaussian, discrete, or conditional Gaussian models using one likelihood calculation and a unified convention for model dimension.
-
Structure Inference: Structure inference is offered across multiple levels of effort: exact minimum forests, stepwise search, stochastic global search, and local analysis around specific vertices.
-
Inference with Missing Values: It handles missing data through three distinct tasks: fitting a given graph using Expectation-Maximization (EM), selecting a graph via structural EM, and completing the data through imputation methods like multiple imputation structure inference.
-
Substantive Models: The framework extends to graphical models arising from irreversible event accumulation on trees, allowing testing of the accumulation hypothesis at both the graph level (noise-free) and full level (with measurement noise).
The underlying architecture involves layers: a model object, graph utilities (like perfect orderings and clique trees), a likelihood core (. p. 4 Labouriau - GraphInfer: Statistical Inference for Decomposable Graphical Models in R
Complete
data
Missing
values
Event data
minForest(), stepSearch(),
searchGlobal()
searchEM(), stepTreeEM(),
searchMI()
accSearch(), searchGlobal(),
treeFromGraph()
fitModel(), anova(), drop1(),
lrtGauss()
fitModelEM(),
imputeMissing()
accFit(), accTest()
Data Structure inference Fitting and testing
Model object • likelihood core • graph utilities
Figure 1: Main routes through the package. For event data searchGlobal() runs with
compatible = TRUE. 3 Exact likelihood-ratio tests . 4 Covariate adjustment . A common inferential framework. Decomposable Gaussian, discrete and conditional
Gaussian models are handled by one likelihood calculation, with one convention for
model dimension, shared by all fitting, testing and search procedures (Sections 3
and 5). These properties extend to mixed data through conditional Gaussian distributions, under the stronger requirement of strong decomposability
(Lauritzen and Wermuth, 1989; Frydenberg and Lauritzen, 1989). They are what make a
search over graphs feasible when the number of variables is large.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Key features include:
-
Likelihood Factorisation and Model Dimension: Decomposition allows single edge moves to be local; if adding an edge preserves strong decomposability, its separator is defined as the set of common neighbors of the two vertices. The dimension of a saturated marginal model is calculated based on occupied cells using the formula d hom(A) = (KA - 1) + KAgA + gA(gA + 1)/2. p. 6
Where the paper says it
Labouriau - GraphInfer: Statistical Inference for Decomposable Graphical Models in R marginal model counts occupied cells: dhom(A) = (KA − 1) + KAgA + gA(gA + 1) 2 , dhet(A) = (KA − 1) + KA gA + gA(gA + 1) 2 , for the cell probabilities, the cell means and the covariance matrices. The decomposition makes a single edge move local.
-
Model Selection Criteria: Selection procedures minimize a penalized criterion C k(G) = -2 (G) + k d(G), where k at least 0. Choices include maximum likelihood (k=0), AIC (k=2), and BIC (n). p. 7
Extended BIC is implemented for Gaussian graphical models and serves as a heuristic extension for mixed, heterogeneous, and sparse discrete models. p. 7Where the paper says it
3 Model-selection criteria and conventions The selection procedures minimise the penalised criterion Ck(G) = −2ℓ(G) + k d(G), k ≥ 0. The choices k = 0, 2 and log n give maximum likelihood, AIC and BIC (Akaike, 1974; Schwarz, 1978), specified by stat = "ML" ("LR", the name used in gRapHD, is an alias), "AIC" and "BIC", or by a numerical k.
Where the paper says it
When the number of variables is large relative to the sample size, BIC may select too many edges, and the package also implements the extended BIC (Chen and Chen, 2008; Foygel and Drton, 2010), C EBIC γ (G) = −2ℓ(G) + (log n) d(G) + 4γ (log |V |)|E|, with stat = "EBIC" (γ = 1/2); stat = c(k, kEdge) gives −2ℓ(G) + k d(G) + kE|E| in general, and EBIC() evaluates the criterion of a fitted model for any γ. The consistency results for the extended BIC were established for Gaussian graphical models; for mixed, heterogeneous and sparse discrete models we use it as a heuristic extension, whose behaviour Section 9.
-
Structure Inference Methods:
-
Minimum Forests: For a potential edge, the statistics D uv and q uv of equation (2) with an empty separator represent the marginal independence of X u and X v. The criterion is defined as C k(F) = C k(G 0) - X for edges in the forest F. p. 8
Where the paper says it
Edges may be excluded, and sets of vertices forced to be cliques. With user-defined edge scores the result is a maximum-weight spanning tree when the restrictions allow one: excluded edges can leave a spanning forest, and forced cliques are included as given.
-
Stepwise Search: The
stepSearchfunction navigates admissible models by sequentially adding or removing one edge at a time, utilizing local evaluations based on the separator S and caching scores for speed. -
Global Search:
searchGlobalexplores the space of strongly decomposable graphs beyond local optima using an iterated local search (ILS) strategy, which alternates between forward and backward stepwise moves interspersed with random perturbations (kick
). -
Model Fitting and Inference:
-
Exact Likelihood-Ratio Tests: For nested decomposable Gaussian models, the likelihood-ratio statistic possesses an exact distribution (Lauritzen, 1996), allowing for the computation of exact and chi-squared p-values via
lrtGauss. -
Inference with Missing Values: GraphInfer distinguishes between fitting a graph given data using EM (
fitModelEM), selecting a graph by structural EM (searchEM), and imputing missing data using methods like multiple imputation structure inference. Structural EM searches for an unknown graph, operating on weighted pseudo-samples that reproduce conditional expectations of complete-data sufficient statistics. p. 0Where the paper says it
Nested models are compared by likelihood-ratio tests whose null distributions are exact in finite samples: conditionally on the discrete data for edges with a continuous endpoint, and conditionally on the discrete margins of the smaller model for edges between discrete variables. Missing values are handled by EM, by structural EM, which reuses the complete-data searches through a weighted pseudosample of expected sufficient statistics, and by multiple imputation; selected models are fit to the observed data likelihood.
-
Graphical Models Induced by Accumulation Trees: The framework supports models derived from irreversible event accumulation on trees, employing tree moves compatible with the model class and fitting a full model for the latent-class mechanism incorporating measurement noise. The
accTestfunction tests the accumulation hypothesis at two levels: graph level (noise-free) and full level (with noise).
The package is implemented in pure R, emphasizing readability and computational speed through leveraging data structures. p. 3 Its speed comes from the local structure of decomposable models
rather than from a compiled language. A planned companion package, GraphInferComplex,
is intended to speed up the identified computational kernels for the larger problems. Nested models are compared by likelihood-ratio tests whose
null distributions are exact in finite samples: conditionally on the discrete data for
edges with a continuous endpoint, and conditionally on the discrete margins of the
smaller model for edges between discrete variables. Missing values are handled by EM,
by structural EM, which reuses the complete-data searches through a weighted pseudosample of expected sufficient statistics, and by multiple imputation; selected models are
fit to the observed data likelihood. For mixed data an
edge is also rejected when it creates a forbidden path, and the procedure yields the optimal
strongly decomposable forest (Edwards et al. The forest is thus one of the few
structure problems whose optimum is obtained without iterative search. Missing values are handled by EM,
by structural EM, which reuses the complete-data searches through a weighted pseudosample of expected sufficient statistics, and by multiple imputation; selected models are
fit to the observed data likelihood. The package also treats the graphical models induced
by irreversible event accumulation on trees: a search over the compatible graphs whose
tree moves overcome an obstruction to single-edge moves, fitting of the full accumulation
model with measurement noise and bootstrap tests of the accumulation hypothesis.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Support for Decomposable Graphical Models: The system can handle continuous, discrete, and mixed data by using a single likelihood calculation framework that is shared across all fitting, testing, and search procedures.
-
Structure Inference at Multiple Levels: The system can perform structure inference from exact minimum forests to stochastic global searches while also supporting local analysis around selected vertices for variables of interest.
-
Missing Value Handling through EM and Structural EM: The system can fit models by EM for a given graph, select graphs using structural EM, and perform multiple imputation to complete data, all on the observed-data likelihood.
-
Exact Likelihood-Ratio Tests in Mixed Models: The system can calculate exact likelihood-ratio tests for nested decomposable Gaussian models with edges having a continuous endpoint or between discrete variables.
-
Model Selection via Penalized Criteria: The system can select graphs by minimizing a penalised criterion Ck(G) = -2l(G) + k d(G), including maximum likelihood (k=0), AIC, BIC, and extended BIC for large variable sets.
-
Accumulation Tree Models: The system can fit and test graphical models induced by irreversible event accumulation on trees, including reconstruction of the tree structure and testing of the accumulation hypothesis at two levels.
-
Handling Large Data Sets: The system can manage large data sets by employing vectorised forest statistics for mixed data and performing local searches that exploit the locality of decomposable models, though global searches may require significant computational effort.
-
Covariate Adjustment: The system can adjust model means using covariate adjustment via residualization to account for explanatory variables, allowing the inference on covariance structure to be based on residuals.
Abstract
Decomposable graphical models combine closed-form maximum likelihood estimation with local model comparison, which makes structure inference practical with many variables. The R package GraphInfer provides one likelihood framework for decomposable models of continuous, discrete and mixed data, the last as conditional Gaussian models. Structure inference ranges from exact minimum forests and stepwise search to stochastic global search. Nested models are compared by likelihood-ratio tests whose null distributions are exact in finite samples: conditionally on the discrete data for edges with a continuous endpoint, and conditionally on the discrete margins of the smaller model for edges between discrete variables. Missing values are handled by EM, by structural EM, which reuses complete-data searches through a weighted pseudo-sample of expected sufficient statistics, and by multiple imputation; selected models are fit to the observed-data likelihood. The package also treats the graphical models induced by irreversible event accumulation on trees: a search over the compatible graphs whose tree moves overcome an obstruction to single-edge moves, fitting of the full accumulation model with measurement noise and bootstrap tests of the accumulation hypothesis. GraphInfer is an independent, pure R successor to the archived package gRapHD. The implementation is validated against independent references, and simulation studies inform its defaults.
Sources
- Extended Bayesian Information Criteria for Gaussian Graphical Models
- Graphical Models Induced by Irreversible Event Accumulation on Trees
- Learning mixed graphical models from data with p larger than n
Related papers
- Learning Robust Treatment Rules for Censored Data
- Neural Estimation of Summary Statistics for Simulation-Based Inference with Non-Asymptotic Guarantees
- Spectral divide-and-conquer MCMC for long stationary time series
- Improving the Efficiency of Subgroup Analysis in Randomized Controlled Trials with TMLE
- Personalized Federated Vector Autoregression with Personalization Diversity
- Doubly Robust and Efficient Calibration of Prediction Sets for Right-Censored Time-to-Event Outcomes