# MaxCutPool: differentiable feature-aware Maxcut for pooling in graph neural networks

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 51 of its 73 references that are in the map.
- First posted on arXiv 8 Sep 2024.

## Builds on (most cited first, 30 of 51)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [On the Opportunities and Risks of Foundation Models](https://mlsanity.com/paper/2108.07258/) (2021)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [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)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [Graph Neural Networks with convolutional ARMA filters](https://mlsanity.com/paper/1901.01343/) (2019)
- [Understanding Attention and Generalization in Graph Neural Networks](https://mlsanity.com/paper/1905.02850/) (2019)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations](https://mlsanity.com/paper/1911.07979/) (2019)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Hierarchical Graph Pooling with Structure Learning](https://mlsanity.com/paper/1911.05954/) (2019)
- [Understanding Pooling in Graph Neural Networks](https://mlsanity.com/paper/2110.05292/) (2021)
- [Structural Entropy Guided Graph Hierarchical Pooling](https://mlsanity.com/paper/2206.13510/) (2022)
- [Memory-Based Graph Networks](https://mlsanity.com/paper/2002.09518/) (2020)
- [Edge Contraction Pooling for Graph Neural Networks](https://mlsanity.com/paper/1905.10990/) (2019)
- [Topology-Aware Graph Pooling Networks](https://mlsanity.com/paper/2010.09834/) (2020)
- [AdaGNN: Graph Neural Networks with Adaptive Frequency Response Filter](https://mlsanity.com/paper/2104.12840/) (2021)
- [Graph Coarsening with Preserved Spectral Properties](https://mlsanity.com/paper/1802.04447/) (2018)
- [p-Laplacian Based Graph Neural Networks](https://mlsanity.com/paper/2111.07337/) (2021)

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

- [Towards Efficient Training of Graph Neural Networks: A Multiscale Approach](https://mlsanity.com/paper/2503.19666/) (2025)
- [BN-Pool: Bayesian Nonparametric Pooling for Graphs](https://mlsanity.com/paper/2501.09821/) (2025)
- [Torch Geometric Pool: the PyTorch library for pooling in Graph Neural Networks](https://mlsanity.com/paper/2512.12642/) (2025)
- [Neural QAOA2: Differentiable Joint Graph Partitioning and Parameter Initialization for Quantum Combinatorial Optimization](https://mlsanity.com/paper/2605.13072/) (2026)
- [Hierarchical Pooling for Sheaf Neural Networks](https://mlsanity.com/paper/2606.20932/) (2026)

## Abstract (arXiv)

We propose a novel approach to compute the MAXCUT in attributed graphs, i.e., graphs with features associated with nodes and edges. Our approach works well on any kind of graph topology and can find solutions that jointly optimize the MAXCUT along with other objectives. Based on the obtained MAXCUT partition, we implement a hierarchical graph pooling layer for Graph Neural Networks, which is sparse, trainable end-to-end, and particularly suitable for downstream tasks on heterophilic graphs.