# Accurate Learning of Graph Representations with Graph Multiset Pooling

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

## Key facts

- Cited by 120 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 55 references that are in the map.
- First posted on arXiv 23 Feb 2021.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [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)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation](https://mlsanity.com/paper/1612.00593/) (2016)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Prototypical Networks for Few-shot Learning](https://mlsanity.com/paper/1703.05175/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [MolGAN: An implicit generative model for small molecular graphs](https://mlsanity.com/paper/1805.11973/) (2018)
- [Learning Convolutional Neural Networks for Graphs](https://mlsanity.com/paper/1605.05273/) (2016)
- [Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs](https://mlsanity.com/paper/1704.02901/) (2017)
- [Diffusion-Convolutional Neural Networks](https://mlsanity.com/paper/1511.02136/) (2015)
- [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)
- [Position-aware Graph Neural Networks](https://mlsanity.com/paper/1906.04817/) (2019)
- [ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations](https://mlsanity.com/paper/1911.07979/) (2019)

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

- [Do Transformers Really Perform Bad for Graph Representation?](https://mlsanity.com/paper/2106.05234/) (2021)
- [Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations](https://mlsanity.com/paper/2202.02514/) (2022)
- [G-Mixup: Graph Data Augmentation for Graph Classification](https://mlsanity.com/paper/2202.07179/) (2022)
- [You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks](https://mlsanity.com/paper/2106.13264/) (2021)
- [Graph Mamba: Towards Learning on Graphs with State Space Models](https://mlsanity.com/paper/2402.08678/) (2024)
- [Attending to Graph Transformers](https://mlsanity.com/paper/2302.04181/) (2023)
- [Generative Diffusion Models on Graphs: Methods and Applications](https://mlsanity.com/paper/2302.02591/) (2023)
- [DiffWire: Inductive Graph Rewiring via the Lov'asz Bound](https://mlsanity.com/paper/2206.07369/) (2022)
- [Polynormer: Polynomial-Expressive Graph Transformer in Linear Time](https://mlsanity.com/paper/2403.01232/) (2024)
- [Gophormer: Ego-Graph Transformer for Node Classification](https://mlsanity.com/paper/2110.13094/) (2021)
- [Structural Entropy Guided Graph Hierarchical Pooling](https://mlsanity.com/paper/2206.13510/) (2022)
- [Personalized Subgraph Federated Learning](https://mlsanity.com/paper/2206.10206/) (2022)
- [Graph Pooling for Graph Neural Networks: Progress, Challenges, and Opportunities](https://mlsanity.com/paper/2204.07321/) (2022)
- [CoCo: A Coupled Contrastive Framework for Unsupervised Domain Adaptive Graph Classification](https://mlsanity.com/paper/2306.04979/) (2023)
- [Edge Representation Learning with Hypergraphs](https://mlsanity.com/paper/2106.15845/) (2021)
- [Rewiring with Positional Encodings for Graph Neural Networks](https://mlsanity.com/paper/2201.12674/) (2022)
- [The expressive power of pooling in Graph Neural Networks](https://mlsanity.com/paper/2304.01575/) (2023)
- [A comprehensive survey on deep active learning in medical image analysis](https://mlsanity.com/paper/2310.14230/) (2023)
- [Graph Machine Learning in the Era of Large Language Models (LLMs)](https://mlsanity.com/paper/2404.14928/) (2024)
- [Graph Neural Networks with Adaptive Readouts](https://mlsanity.com/paper/2211.04952/) (2022)
- [Higher-order Clustering and Pooling for Graph Neural Networks](https://mlsanity.com/paper/2209.03473/) (2022)
- [Towards Graph Contrastive Learning: A Survey and Beyond](https://mlsanity.com/paper/2405.11868/) (2024)
- [High-Order Pooling for Graph Neural Networks with Tensor Decomposition](https://mlsanity.com/paper/2205.11691/) (2022)
- [Graph Self-supervised Learning with Accurate Discrepancy Learning](https://mlsanity.com/paper/2202.02989/) (2022)
- [Distribution Knowledge Embedding for Graph Pooling](https://mlsanity.com/paper/2109.14333/) (2021)
- [Rayleigh Quotient Graph Neural Networks for Graph-level Anomaly Detection](https://mlsanity.com/paper/2310.02861/) (2023)
- [Beyond Message Passing: Neural Graph Pattern Machine](https://mlsanity.com/paper/2501.18739/) (2025)
- [Semi-Supervised Hierarchical Graph Classification](https://mlsanity.com/paper/2206.05416/) (2022)
- [Learning Topology-Specific Experts for Molecular Property Prediction](https://mlsanity.com/paper/2302.13693/) (2023)
- [Search to Fine-tune Pre-trained Graph Neural Networks for Graph-level Tasks](https://mlsanity.com/paper/2308.06960/) (2023)

## Abstract (arXiv)

Graph neural networks have been widely used on modeling graph data, achieving impressive results on node classification and link prediction tasks. Yet, obtaining an accurate representation for a graph further requires a pooling function that maps a set of node representations into a compact form. A simple sum or average over all node representations considers all node features equally without consideration of their task relevance, and any structural dependencies among them. Recently proposed hierarchical graph pooling methods, on the other hand, may yield the same representation for two different graphs that are distinguished by the Weisfeiler-Lehman test, as they suboptimally preserve information from the node features. To tackle these limitations of existing graph pooling methods, we first formulate the graph pooling problem as a multiset encoding problem with auxiliary information about the graph structure, and propose a Graph Multiset Transformer (GMT) which is a multi-head attention based global pooling layer that captures the interaction between nodes according to their structural dependencies. We show that GMT satisfies both injectiveness and permutation invariance, such that it is at most as powerful as the Weisfeiler-Lehman graph isomorphism test. Moreover, our methods can be easily extended to the previous node clustering approaches for hierarchical graph pooling. Our experimental results show that GMT significantly outperforms state-of-the-art graph pooling methods on graph classification benchmarks with high memory and time efficiency, and obtains even larger performance gain on graph reconstruction and generation tasks.