Spectral Clustering with Graph Neural Networks for Graph Pooling

Filippo Maria Bianchi, Daniele Grattarola, Cesare Alippi
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:874-883, 2020.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-bianchi20a, title = {Spectral Clustering with Graph Neural Networks for Graph Pooling}, author = {Bianchi, Filippo Maria and Grattarola, Daniele and Alippi, Cesare}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {874--883}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/bianchi20a/bianchi20a.pdf}, url = {https://proceedings.mlr.press/v119/bianchi20a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Spectral Clustering with Graph Neural Networks for Graph Pooling %A Filippo Maria Bianchi %A Daniele Grattarola %A Cesare Alippi %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-bianchi20a %I PMLR %P 874--883 %U https://proceedings.mlr.press/v119/bianchi20a.html %V 119 %X 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.
APA
Bianchi, F.M., Grattarola, D. & Alippi, C.. (2020). Spectral Clustering with Graph Neural Networks for Graph Pooling. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:874-883 Available from https://proceedings.mlr.press/v119/bianchi20a.html.

Related Material