# Maximal Independent Sets for Pooling in Graph Neural Networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 19 references that are in the map.
- First posted on arXiv 24 Jul 2023.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Pooling](https://mlsanity.com/paper/1910.11436/) (2019)
- [Maximal Independent Vertex Set applied to Graph Pooling](https://mlsanity.com/paper/2208.01648/) (2022)

## Abstract (arXiv)

Convolutional Neural Networks (CNNs) have enabled major advances in image classification through convolution and pooling. In particular, image pooling transforms a connected discrete lattice into a reduced lattice with the same connectivity and allows reduction functions to consider all pixels in an image. However, there is no pooling that satisfies these properties for graphs. In fact, traditional graph pooling methods suffer from at least one of the following drawbacks: Graph disconnection or overconnection, low decimation ratio, and deletion of large parts of graphs. In this paper, we present three pooling methods based on the notion of maximal independent sets that avoid these pitfalls. Our experimental results confirm the relevance of maximal independent set constraints for graph pooling.