# Spectral Clustering with Graph Neural Networks for Graph Pooling

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2019.

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

- [Graph-less Neural Networks: Teaching Old MLPs New Tricks via Distillation](https://mlsanity.com/paper/2110.08727/) (2021)
- [VQGraph: Rethinking Graph Representation Space for Bridging GNNs and MLPs](https://mlsanity.com/paper/2308.02117/) (2023)
- [Graph Pooling via Coarsened Graph Infomax](https://mlsanity.com/paper/2105.01275/) (2021)
- [NOSMOG: Learning Noise-robust and Structure-aware MLPs on Graphs](https://mlsanity.com/paper/2208.10010/) (2022)
- [Learning Feature Aggregation for Deep 3D Morphable Models](https://mlsanity.com/paper/2105.02173/) (2021)
- [Graph Convolutional Networks for Multi-modality Medical Imaging: Methods, Architectures, and Clinical Applications](https://mlsanity.com/paper/2202.08916/) (2022)
- [Grouping-matrix based Graph Pooling with Adaptive Number of Clusters](https://mlsanity.com/paper/2209.02939/) (2022)
- [cDP-MIL: Robust Multiple Instance Learning via Cascaded Dirichlet Process](https://mlsanity.com/paper/2407.11448/) (2024)
- [Automatic Identification of Chemical Moieties](https://mlsanity.com/paper/2203.16205/) (2022)
- [Semantic Graph Consistency: Going Beyond Patches for Regularizing Self-Supervised Vision Transformers](https://mlsanity.com/paper/2406.12944/) (2024)
- [VLSI Hypergraph Partitioning with Deep Learning](https://mlsanity.com/paper/2409.01387/) (2024)
- [TopER: Topological Embeddings in Graph Representation Learning](https://mlsanity.com/paper/2410.01778/) (2024)
- [Multi-hop Graph Convolutional Network with High-order Chebyshev Approximation for Text Reasoning](https://mlsanity.com/paper/2106.05221/) (2021)
- [Boosting Graph Neural Networks by Injecting Pooling in Message Passing](https://mlsanity.com/paper/2202.04768/) (2022)
- [Deep Modularity Networks with Diversity-Preserving Regularization](https://mlsanity.com/paper/2501.13451/) (2025)
- [Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation](https://mlsanity.com/paper/2605.10975/) (2026)

## Abstract (arXiv)

Spectral clustering (SC) is a popular clustering technique to find strongly connected communities on a graph. SC can be used in Graph Neural Networks (GNNs) to implement pooling operations that aggregate nodes belonging to the same cluster. However, the eigendecomposition of the Laplacian is expensive and, since clustering results are graph-specific, pooling methods based on SC must perform a new optimization for each new sample. In this paper, we propose a graph clustering approach that addresses these limitations of SC. We formulate a continuous relaxation of the normalized minCUT problem and train a GNN to compute cluster assignments that minimize this objective. Our GNN-based implementation is differentiable, does not require to compute the spectral decomposition, and learns a clustering function that can be quickly evaluated on out-of-sample graphs. From the proposed clustering method, we design a graph pooling operator that overcomes some important limitations of state-of-the-art graph pooling techniques and achieves the best performance in several supervised and unsupervised tasks.