Probabilistic graphical models (PGMs) provide a powerful language for representing dependencies between variables. However, for decades, the field has been bifurcated by a structural property called decomposability (or chordality). Decomposable graphs are those where every cycle of length four or more has a "chord"—an edge connecting two non-adjacent nodes in the cycle.
While decomposability allows for elegant, closed-form solutions to complex statistical problems, it is often an unrealistic physical assumption. A growing body of research seeks to break this "chordal glass ceiling," enabling rigorous inference and learning on the more complex, non-decomposable structures that define real-world networks.
The Decomposability Trap
The preference for decomposable models is driven by mathematical convenience. In a decomposable Gaussian Graphical Model (GGM), the global likelihood of the data can be factored into a product of local likelihoods over the graph's cliques and separators. This allows researchers to calculate normalizing constants and marginal likelihoods analytically.
As noted by Jukka Corander and colleagues in Learning Chordal Markov Networks by Constraint Satisfaction, this tractability comes at a high cost: to satisfy the chordal requirement, algorithms must often perform "triangulation," adding spurious edges to the graph. These artificial edges create "ghost" dependencies that do not exist in the underlying system, leading to inaccurate models of everything from protein interactions to social networks.
Beyond Closed-Form Solutions
When we move to non-decomposable graphs—those containing chordless cycles—the "local-to-global" mapping breaks down. The normalizing constants (the denominators of Bayes' rule) become notoriously difficult to compute.
Recent breakthroughs have attacked this intractability from several angles:
- Exact Formulas for General Graphs: Alex Lenkoski and Donald Richards in Exact formulas for the normalizing constants of Wishart distributions for graphical models utilized fractional calculus to derive the first explicit formulas for G-Wishart normalizing constants on non-chordal graphs, a problem previously deemed "intractable."
- Fourier Analysis: More recently, Ching Wong and colleagues demonstrated in A new way to evaluate G-Wishart normalising constants via Fourier analysis that these high-dimensional integrals can be transformed into low-dimensional real integrals, achieving "numerically exact" results hundreds of times faster than traditional Monte Carlo methods.
- Pseudo-Likelihood Approaches: To avoid the normalizing constant altogether, Henrik Nyman and Jukka Corander developed Marginal Pseudo-Likelihood (MPL). As detailed in Marginal Pseudo-Likelihood Learning of Markov Network structures, this scoring criterion allows for the consistent learning of non-chordal structures without the computational burden of full Bayesian integration.
Geometric and Distributed Perspectives
The challenge of non-decomposability also appears in spatial and distributed settings. Simón Lunagómez and Sayan Mukherjee proposed a geometric alternative in Geometric Representations of Random Hypergraphs. By mapping variables to points in $d$-dimensional space, they can represent higher-order interactions and non-decomposable dependencies more naturally than traditional graph-based priors.
In the realm of sensor networks, Yi-Cheng Chen and Rick S. Blum have highlighted that while distributed testing is efficient for decomposable models, extending these "quickest change detection" methods to non-decomposable topologies remains a frontier for energy-efficient signal processing (Testing the Structure of a Gaussian Graphical Model With Reduced Transmissions in a Distributed Setting).
Why It Works: The Intuition of Partitioning
The core intuition behind these advances is that even if a graph is not globally decomposable, it often contains "pockets" of structure that can be exploited.
For instance, the bridge-block decomposition introduced by Jiaxi Ying and Daniel P. Palomar in Learning Large-Scale MTP2 Gaussian Graphical Models via Bridge-Block Decomposition identifies "bridges"—edges whose removal increases the number of connected components. This allows a massive precision matrix estimation problem to be broken into smaller, independent sub-problems, even if the individual blocks themselves are non-decomposable.
By shifting from a rigid requirement of global chordality to more flexible forms of local partitioning and sophisticated integral approximations, researchers are finally able to model the "messy" cycles and complex loops that characterize real-world data.