  Graph Neural Networks (GNNs) have achieved state-of-the-art results on many
graph analysis tasks such as node classification and link prediction. However,
important unsupervised problems on graphs, such as graph clustering, have
proved more resistant to advances in GNNs. Graph clustering has the same
overall goal as node pooling in GNNs - does this mean that GNN pooling methods
do a good job at clustering graphs?
  Surprisingly, the answer is no - current GNN pooling methods often fail to
recover the cluster structure in cases where simple baselines, such as k-means
applied on learned representations, work well. We investigate further by
carefully designing a set of experiments to study different signal-to-noise
scenarios both in graph structure and attribute data. To address these methods'
poor performance in clustering, we introduce Deep Modularity Networks (DMoN),
an unsupervised pooling method inspired by the modularity measure of clustering
quality, and show how it tackles recovery of the challenging clustering
structure of real-world graphs. Similarly, on real-world data, we show that
DMoN produces high quality clusters which correlate strongly with ground truth
labels, achieving state-of-the-art results with over 40% improvement over other
pooling methods across different metrics.
