# MDL-Pool: Adaptive Multilevel Graph Pooling Based on Minimum Description Length

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 50 references that are in the map.
- First posted on arXiv 16 Sep 2024.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [Understanding Pooling in Graph Neural Networks](https://mlsanity.com/paper/2110.05292/) (2021)
- [Edge Contraction Pooling for Graph Neural Networks](https://mlsanity.com/paper/1905.10990/) (2019)
- [PageRank beyond the Web](https://mlsanity.com/paper/1407.5107/) (2014)
- [The ground truth about metadata and community detection in networks](https://mlsanity.com/paper/1608.05878/) (2016)
- [Evaluating Overfit and Underfit in Models of Network Community Structure](https://mlsanity.com/paper/1802.10582/) (2018)
- [Mapping higher-order network flows in memory and multilayer networks with Infomap](https://mlsanity.com/paper/1706.04792/) (2017)
- [Nonparametric weighted stochastic block models](https://mlsanity.com/paper/1708.01432/) (2017)
- [Simplifying Clustering with Graph Neural Networks](https://mlsanity.com/paper/2207.08779/) (2022)
- [Generalizing Downsampling from Regular Data to Graphs](https://mlsanity.com/paper/2208.03523/) (2022)
- [Hierarchical community structure in networks](https://mlsanity.com/paper/2009.07196/) (2020)
- [Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection](https://mlsanity.com/paper/2210.09186/) (2022)

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

- [The Role of Node Features in Graph Pooling](https://mlsanity.com/paper/2605.06250/) (2026)

## Abstract (arXiv)

Graph pooling compresses graphs and summarises their topological properties and features in a vectorial representation. It is an essential part of deep graph representation learning and is indispensable in graph-level tasks like classification or regression. Current approaches pool hierarchical structures in graphs by iteratively applying shallow pooling operators up to a fixed depth. However, they disregard the interdependencies between structures at different hierarchical levels and do not adapt to datasets that contain graphs with different sizes that may require pooling with various depths. To address these issues, we propose MDL-Pool, a pooling operator based on the minimum description length (MDL) principle, whose loss formulation explicitly models the interdependencies between different hierarchical levels and facilitates a direct comparison between multiple pooling alternatives with different depths. MDP-Pool builds on the map equation, an information-theoretic objective function for community detection, which naturally implements Occam's razor and balances between model complexity and goodness-of-fit via the MDL. We demonstrate MDL-Pool's competitive performance in an empirical evaluation against various baselines across standard graph classification datasets.