This paper introduces the Mondrian Process, an elegant stochastic process that brings the recursive partitioning logic of computer science data structures (like $kd$-trees) into the world of Bayesian nonparametrics. It provides a flexible, "self-consistent" prior for relational data, allowing for local clusters to be modeled with high resolution without forcing unnecessary splits across the entire dataset.
The Problem: Breaking the Grid
When modeling relational data—such as trade between countries or links in a social network—researchers often rely on Stochastic Block Models. These models group objects into clusters and define the probability of a relationship based on those clusters.
However, standard block models suffer from a major structural flaw: they induce a "regular grid" partition. If you need to split a group of objects to capture fine-grained detail in one specific part of the data, that split is forced across the entire row or column of the relational array. This "global resolution" requirement is computationally wasteful and fails to reflect reality, where complexity is usually localized.
The authors sought a way to create "hierarchical" partitions that are not constrained to a grid—much like the abstract, rectangular paintings of Piet Mondrian—while ensuring the model remains mathematically sound (specifically, "exchangeable" and "consistent").
The Solution: The Mondrian Process
The core contribution of the paper is the Mondrian Process ($MP$), a recursive generative process that essentially turns the $kd$-tree into a formal probability distribution. The process works as follows:
- The Budget: The process begins with a "time" budget, denoted as $\lambda$.
- The Cost: For a given rectangle in the space, the time until the next "cut" is an exponential random variable. The rate of this variable is proportional to the linear dimension (perimeter) of the rectangle.
- The Cut: If a cut occurs before the budget runs out, an axis is chosen (with probability proportional to its length), and a cut point is chosen uniformly along that axis.
- Recursion: The process then repeats independently for the two resulting sub-rectangles using the remaining budget.
In one dimension, this process recovers the cuts of a standard Poisson process. In higher dimensions, it creates a tree of axis-aligned cuts known as "guillotine partitions."
A critical property of the $MP$ is self-consistency. If you observe a Mondrian process restricted to a small window, it has the exact same distribution as if you had sampled a Mondrian process specifically for that window. This property allows the model to be seamlessly extended to infinite spaces, serving as a multidimensional generalization of the stick-breaking process used in Dirichlet processes.
Experiments and Results
The authors evaluated the Mondrian Process on three distinct types of data to demonstrate its flexibility and recovery capabilities:
- Synthetic Mondrian Painting: The authors generated relational data based on the structure of an actual painting by Piet Mondrian (Composition with Large Blue Plane, Red, Black, Yellow, and Gray, 1921). Using MCMC (Markov Chain Monte Carlo) sampling, the model was able to exactly recover the block structure of the synthetic data after 1,500 iterations, proving its ability to capture complex, non-grid artistic partitions.
- Global Trade Patterns: The model was applied to a classic network analysis dataset detailing five types of relations (trade in food, crude materials, minerals, basic goods, and diplomatic exchange) between 24 countries in 1984. It successfully identified salient blocs, such as grouping Japan, the UK, Switzerland, and Spain as a cluster of major exporters, while noting China's distinct behavior as an importer in that specific context.
- Social Network Roles: In a small-scale simulation of nine university employees with relations like "friends," "works-with," and "gives-orders-to," the model correctly partitioned the relations into homogeneous blocks that reflected underlying roles (janitors, students, professors) and their hierarchical interactions.
Limitations and Future Work
While the Mondrian Process offers a significant leap forward in relational data modeling, the authors note several areas for future exploration:
- Inference Complexity: Searching through the vast space of possible trees and partitions is challenging. While MCMC schemes are a solid starting point, more sophisticated sampling methods will be required to scale to very large datasets.
- Identifiability: It remains an open theoretical question whether the underlying Mondrian process can be perfectly recovered as the amount of data approaches infinity.
- Symmetry: The current model does not explicitly represent symmetric relationships (e.g., undirected friendships). The authors suggest reflecting the process across the $y=x$ line as a potential solution.
- Beyond Axis-Aligned Cuts: Axis-aligned cuts are computationally convenient, but real-world data might be better served by diagonal or non-linear partitions in future iterations of the model.
Summary updated