# Maximal Independent Sets for Pooling in Graph Neural Networks

Source: [Maximal Independent Sets for Pooling in Graph Neural Networks](<https://www.sota2.com/research/paper/68fa70261e209131cea4962d>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-26T01:35:15.802Z

Authors: Stevan Stanovic, Benoit Ga\\"uz\\\`ere, Luc Brun

Published: 2023-07-24T13:47:30.000Z

## Abstract

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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2307.13011>)

[PDF](<https://arxiv.org/pdf/2307.13011.pdf>)