  We study the problem of clustering nodes in a dynamic graph, where the
connections between nodes and nodes' cluster memberships may change over time,
e.g., due to community migration. We first propose a dynamic stochastic block
model that captures these changes, and a simple decay-based clustering
algorithm that clusters nodes based on weighted connections between them, where
the weight decreases at a fixed rate over time. This decay rate can then be
interpreted as signifying the importance of including historical connection
information in the clustering. However, the optimal decay rate may differ for
clusters with different rates of turnover. We characterize the optimal decay
rate for each cluster and propose a clustering method that achieves almost
exact recovery of the true clusters. We then demonstrate the efficacy of our
clustering algorithm with optimized decay rates on simulated graph data.
Recurrent neural networks (RNNs), a popular algorithm for sequence learning,
use a similar decay-based method, and we use this insight to propose two new
RNN-GCN (graph convolutional network) architectures for semi-supervised graph
clustering. We finally demonstrate that the proposed architectures perform well
on real data compared to state-of-the-art graph clustering algorithms.
