# Maximal Independent Vertex Set applied to Graph Pooling

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 15 references that are in the map.
- First posted on arXiv 2 Aug 2022.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [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)
- [Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Pooling](https://mlsanity.com/paper/1910.11436/) (2019)
- [Maximum Entropy Weighted Independent Set Pooling for Graph Neural Networks](https://mlsanity.com/paper/2107.01410/) (2021)

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

- [Generalizing Downsampling from Regular Data to Graphs](https://mlsanity.com/paper/2208.03523/) (2022)
- [Maximal Independent Sets for Pooling in Graph Neural Networks](https://mlsanity.com/paper/2307.13011/) (2023)

## Abstract (arXiv)

Convolutional neural networks (CNN) have enabled major advances in image classification through convolution and pooling. In particular, image pooling transforms a connected discrete grid into a reduced grid with the same connectivity and allows reduction functions to take into account all the pixels of an image. However, a pooling satisfying such properties does not exist for graphs. Indeed, some methods are based on a vertex selection step which induces an important loss of information. Other methods learn a fuzzy clustering of vertex sets which induces almost complete reduced graphs. We propose to overcome both problems using a new pooling method, named MIVSPool. This method is based on a selection of vertices called surviving vertices using a Maximal Independent Vertex Set (MIVS) and an assignment of the remaining vertices to the survivors. Consequently, our method does not discard any vertex information nor artificially increase the density of the graph. Experimental results show an increase in accuracy for graph classification on various standard datasets.