GraphInfer: Statistical Inference for Decomposable Graphical Models in R

arXiv:2611.17074 · stat.ME, stat.CO · Submitted 2026-11-12 · Read on arXiv

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

Where the paper says it

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.

The package supports decomposable models of continuous, discrete, and mixed data types, including conditional Gaussian models. p. 0
Where the paper says it

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 offers four primary themes:

  1. 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.

  2. 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.

  3. 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.

  4. 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

Where the paper says it

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.

margLik and.edgeStat), structure-inference modules, exact tests, and covariate adjustment modules. p. 1
Where the paper says it

3 Exact likelihood-ratio tests . 4 Covariate adjustment .

The common calculation relies fundamentally on the decomposability of the model. p. 2
Where the paper says it

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).

A critical constraint is that a graph containing a chordless cycle cannot be fitted, and strong decomposability excludes further graphs in the mixed data case. p. 2
Where the paper says it

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.

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

    Where 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.

    Extended BIC is implemented for Gaussian graphical models and serves as a heuristic extension for mixed, heterogeneous, and sparse discrete models. p. 7
    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 stepSearch function 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: searchGlobal explores 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. 0

    Where 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 accTest function 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

Where the paper says it

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.

Limitations noted are that exact tests are unavailable for data with missing values or in the mixed case with covariate designs. p. 0
Where 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.

Furthermore, search efforts demonstrate that greedy searches can converge far from the optimal value, necessitating stochastic global search for dense problems. p. 8
Where the paper says it

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.

The accumulation model specifically requires binary events and tree moves demand either all discrete or all continuous data. p. 0
Where the paper says it

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.

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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. 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

Related papers