# Maximum Entropy Weighted Independent Set Pooling for Graph Neural Networks

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 69 references that are in the map.
- First posted on arXiv 3 Jul 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Learning deep representations by mutual information estimation and maximization](https://mlsanity.com/paper/1808.06670/) (2018)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [MINE: Mutual Information Neural Estimation](https://mlsanity.com/paper/1801.04062/) (2018)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization](https://mlsanity.com/paper/1908.01000/) (2019)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs](https://mlsanity.com/paper/1704.02901/) (2017)
- [PairNorm: Tackling Oversmoothing in GNNs](https://mlsanity.com/paper/1909.12223/) (2019)
- [Revisiting Graph Neural Networks: All We Have is Low-Pass Filters](https://mlsanity.com/paper/1905.09550/) (2019)
- [Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks](https://mlsanity.com/paper/1909.01315/) (2019)
- [Order Matters: Sequence to sequence for sets](https://mlsanity.com/paper/1511.06391/) (2015)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)

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

- [A Variational Edge Partition Model for Supervised Graph Representation Learning](https://mlsanity.com/paper/2202.03233/) (2022)
- [Generalizing Downsampling from Regular Data to Graphs](https://mlsanity.com/paper/2208.03523/) (2022)
- [Union Subgraph Neural Networks](https://mlsanity.com/paper/2305.15747/) (2023)
- [Contrastive Graph Pooling for Explainable Classification of Brain Networks](https://mlsanity.com/paper/2307.11133/) (2023)
- [A Class-Aware Representation Refinement Framework for Graph Classification](https://mlsanity.com/paper/2209.00936/) (2022)
- [Maximal Independent Vertex Set applied to Graph Pooling](https://mlsanity.com/paper/2208.01648/) (2022)
- [AutoHEnsGNN: Winning Solution to AutoGraph Challenge for KDD Cup 2020](https://mlsanity.com/paper/2111.12952/) (2021)
- [Structure-Sensitive Graph Dictionary Embedding for Graph Classification](https://mlsanity.com/paper/2306.10505/) (2023)
- [Graph Structure Prompt Learning: A Novel Methodology to Improve Performance of Graph Neural Networks](https://mlsanity.com/paper/2407.11361/) (2024)
- [Contrastive Representation Learning for Dynamic Link Prediction in Temporal Networks](https://mlsanity.com/paper/2408.12753/) (2024)
- [Enhancing Persona Classification in Dialogue Systems: A Graph Neural Network Approach](https://mlsanity.com/paper/2412.13283/) (2024)
- [Multilevel Graph Wavelet Compressed Sensing with Scale-Aware Neural Recovery](https://mlsanity.com/paper/2607.20857/) (2026)

## Abstract (arXiv)

In this paper, we propose a novel pooling layer for graph neural networks based on maximizing the mutual information between the pooled graph and the input graph. Since the maximum mutual information is difficult to compute, we employ the Shannon capacity of a graph as an inductive bias to our pooling method. More precisely, we show that the input graph to the pooling layer can be viewed as a representation of a noisy communication channel. For such a channel, sending the symbols belonging to an independent set of the graph yields a reliable and error-free transmission of information. We show that reaching the maximum mutual information is equivalent to finding a maximum weight independent set of the graph where the weights convey entropy contents. Through this communication theoretic standpoint, we provide a distinct perspective for posing the problem of graph pooling as maximizing the information transmission rate across a noisy communication channel, implemented by a graph neural network. We evaluate our method, referred to as Maximum Entropy Weighted Independent Set Pooling (MEWISPool), on graph classification tasks and the combinatorial optimization problem of the maximum independent set. Empirical results demonstrate that our method achieves the state-of-the-art and competitive results on graph classification tasks and the maximum independent set problem in several benchmark datasets.