# Structural Entropy Guided Graph Hierarchical Pooling

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

## Key facts

- Cited by 62 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 36 references that are in the map.
- First posted on arXiv 26 Jun 2022.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [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)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (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)
- [Order Matters: Sequence to sequence for sets](https://mlsanity.com/paper/1511.06391/) (2015)
- [ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations](https://mlsanity.com/paper/1911.07979/) (2019)
- [Accurate Learning of Graph Representations with Graph Multiset Pooling](https://mlsanity.com/paper/2102.11533/) (2021)
- [Graph Convolutional Networks with EigenPooling](https://mlsanity.com/paper/1904.13107/) (2019)
- [Rethinking pooling in graph neural networks](https://mlsanity.com/paper/2010.11418/) (2020)
- [A Simple yet Effective Method for Graph Classification](https://mlsanity.com/paper/2206.02404/) (2022)

## Built on by (most cited first, 30 of 62)

- [A Comprehensive Survey on Deep Graph Representation Learning](https://mlsanity.com/paper/2304.05055/) (2023)
- [SE-GSL: A General and Effective Graph Structure Learning Framework through Structural Entropy Optimization](https://mlsanity.com/paper/2303.09778/) (2023)
- [Accelerating Transformers with Spectrum-Preserving Token Merging](https://mlsanity.com/paper/2405.16148/) (2024)
- [Scaling Up Dynamic Graph Representation Learning via Spiking Neural Networks](https://mlsanity.com/paper/2208.10364/) (2022)
- [LSEnet: Lorentz Structural Entropy Neural Network for Deep Graph Clustering](https://mlsanity.com/paper/2405.11801/) (2024)
- [EXGC: Bridging Efficiency and Explainability in Graph Condensation](https://mlsanity.com/paper/2402.05962/) (2024)
- [Rayleigh Quotient Graph Neural Networks for Graph-level Anomaly Detection](https://mlsanity.com/paper/2310.02861/) (2023)
- [HiTIN: Hierarchy-aware Tree Isomorphism Network for Hierarchical Text Classification](https://mlsanity.com/paper/2305.15182/) (2023)
- [Subgraph Pooling: Tackling Negative Transfer on Graphs](https://mlsanity.com/paper/2402.08907/) (2024)
- [SeBot: Structural Entropy Guided Multi-View Contrastive Learning for Social Bot Detection](https://mlsanity.com/paper/2405.11225/) (2024)
- [Hierarchical and Incremental Structural Entropy Minimization for Unsupervised Social Event Detection](https://mlsanity.com/paper/2312.11891/) (2023)
- [Hierarchical State Abstraction Based on Structural Information Principles](https://mlsanity.com/paper/2304.12000/) (2023)
- [MultiSPANS: A Multi-range Spatial-Temporal Transformer Network for Traffic Forecast via Structural Entropy Optimization](https://mlsanity.com/paper/2311.02880/) (2023)
- [The Snowflake Hypothesis: Training Deep GNN with One Node One Receptive field](https://mlsanity.com/paper/2308.10051/) (2023)
- [Graph Classification via Reference Distribution Learning: Theory and Practice](https://mlsanity.com/paper/2408.11370/) (2024)
- [Towards Dynamic Message Passing on Graphs](https://mlsanity.com/paper/2410.23686/) (2024)
- [Adversarial Socialbots Modeling Based on Structural Information Principles](https://mlsanity.com/paper/2312.08098/) (2023)
- [Attend Who is Weak: Enhancing Graph Condensation via Cross-Free Adversarial Training](https://mlsanity.com/paper/2311.15772/) (2023)
- [Boosting Graph Pooling with Persistent Homology](https://mlsanity.com/paper/2402.16346/) (2024)
- [Cluster-wise Graph Transformer with Dual-granularity Kernelized Attention](https://mlsanity.com/paper/2410.06746/) (2024)
- [Unsupervised Skin Lesion Segmentation via Structural Entropy Minimization on Multi-Scale Superpixel Graphs](https://mlsanity.com/paper/2309.01899/) (2023)
- [A Comprehensive Graph Pooling Benchmark: Effectiveness, Robustness and Generalizability](https://mlsanity.com/paper/2406.09031/) (2024)
- [State of the Art and Potentialities of Graph-level Learning](https://mlsanity.com/paper/2301.05860/) (2023)
- [SEGA: Structural Entropy Guided Anchor View for Graph Contrastive Learning](https://mlsanity.com/paper/2305.04501/) (2023)
- [Learning to Approximate Adaptive Kernel Convolution on Graphs](https://mlsanity.com/paper/2401.11840/) (2024)
- [MaxCutPool: differentiable feature-aware Maxcut for pooling in graph neural networks](https://mlsanity.com/paper/2409.05100/) (2024)
- [Feudal Graph Reinforcement Learning](https://mlsanity.com/paper/2304.05099/) (2023)
- [Patch-wise Graph Contrastive Learning for Image Translation](https://mlsanity.com/paper/2312.08223/) (2023)
- [Graph Parsing Networks](https://mlsanity.com/paper/2402.14393/) (2024)
- [Effective Exploration Based on the Structural Information Principles](https://mlsanity.com/paper/2410.06621/) (2024)

## Abstract (arXiv)

Following the success of convolution on non-Euclidean space, the corresponding pooling approaches have also been validated on various tasks regarding graphs. However, because of the fixed compression quota and stepwise pooling design, these hierarchical pooling methods still suffer from local structure damage and suboptimal problem. In this work, inspired by structural entropy, we propose a hierarchical pooling approach, SEP, to tackle the two issues. Specifically, without assigning the layer-specific compression quota, a global optimization algorithm is designed to generate the cluster assignment matrices for pooling at once. Then, we present an illustration of the local structure damage from previous methods in the reconstruction of ring and grid synthetic graphs. In addition to SEP, we further design two classification models, SEP-G and SEP-N for graph classification and node classification, respectively. The results show that SEP outperforms state-of-the-art graph pooling methods on graph classification benchmarks and obtains superior performance on node classifications.