# Alice and the Caterpillar: A more descriptive null model for assessing data mining results

arXiv: https://arxiv.org/abs/2506.09764 · HTML: https://mlsanity.com/paper/2506.09764/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 72 references that are in the map.
- First posted on arXiv 11 Jun 2025.

## Builds on (most cited first, 11 of 11)

- [Fast and Memory-Efficient Significant Pattern Mining via Permutation Testing](https://mlsanity.com/paper/1502.04315/) (2015)
- [The Statistical Physics of Real-World Networks](https://mlsanity.com/paper/1810.05095/) (2018)
- [Graph Generators: State of the Art and Open Challenges](https://mlsanity.com/paper/2001.07906/) (2020)
- [A Tutorial on Statistically Sound Pattern Discovery](https://mlsanity.com/paper/1709.03904/) (2017)
- [Quantifying randomness in real networks](https://mlsanity.com/paper/1505.07503/) (2015)
- [Monte Carlo Null Models for Genomic Data](https://mlsanity.com/paper/1404.5970/) (2014)
- [Sampling motif-constrained ensembles of networks](https://mlsanity.com/paper/1507.08696/) (2015)
- [Measuring and Modeling Bipartite Graphs with Community Structure](https://mlsanity.com/paper/1607.08673/) (2016)
- [On Realizations of a Joint Degree Matrix](https://mlsanity.com/paper/1302.3548/) (2013)
- [Generation and analysis of networks with a prescribed degree sequence and subgraph family: Higher-order structure matters](https://mlsanity.com/paper/1512.01435/) (2015)
- [Random Graphs with Prescribed K-Core Sequences: A New Null Model for Network Analysis](https://mlsanity.com/paper/2102.12604/) (2021)

## Built on by (most cited first, 1 of 1)

- [Few-Shot Resampling for Scalable Statistically-Sound Data Mining](https://mlsanity.com/paper/2606.11235/) (2026)

## Abstract (arXiv)

We introduce novel null models for assessing the results obtained from observed binary transactional and sequence datasets, using statistical hypothesis testing. Our null models maintain more properties of the observed dataset than existing ones. Specifically, they preserve the Bipartite Joint Degree Matrix of the bipartite (multi-)graph corresponding to the dataset, which ensures that the number of caterpillars, i.e., paths of length three, is preserved, in addition to other properties considered by other models. We describe Alice, a suite of Markov chain Monte Carlo algorithms for sampling datasets from our null models, based on a carefully defined set of states and efficient operations to move between them. The results of our experimental evaluation show that Alice mixes fast and scales well, and that our null model finds different significant results than ones previously considered in the literature.