Spectral Clustering with Graph Neural Networks for Graph Pooling
This addresses a bottleneck in graph neural networks for researchers and practitioners by providing a more efficient and generalizable pooling method, though it is incremental as it builds on existing spectral clustering and GNN techniques.
The paper tackles the computational expense and sample-specific optimization of spectral clustering in graph pooling by proposing a differentiable GNN-based method that learns a clustering function applicable to out-of-sample graphs, achieving best performance in several supervised and unsupervised tasks.
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.