GRADE: Graph Dynamic Embedding
This work addresses the challenge of explicitly capturing temporal community dynamics in evolving graphs, which is incremental as it builds on prior graph representation learning methods by incorporating community structures.
The paper tackles the problem of modeling dynamic graph evolution by capturing both node-level and mesoscale community-level dynamics, which existing methods neglect, and demonstrates that GRADE outperforms baselines in dynamic link prediction and shows favorable performance in dynamic community detection.
Representation learning of static and more recently dynamically evolving graphs has gained noticeable attention. Existing approaches for modelling graph dynamics focus extensively on the evolution of individual nodes independently of the evolution of mesoscale community structures. As a result, current methods do not provide useful tools to study and cannot explicitly capture temporal community dynamics. To address this challenge, we propose GRADE - a probabilistic model that learns to generate evolving node and community representations by imposing a random walk prior over their trajectories. Our model also learns node community membership which is updated between time steps via a transition matrix. At each time step link generation is performed by first assigning node membership from a distribution over the communities, and then sampling a neighbor from a distribution over the nodes for the assigned community. We parametrize the node and community distributions with neural networks and learn their parameters via variational inference. Experiments demonstrate GRADE outperforms baselines in dynamic link prediction, shows favourable performance on dynamic community detection, and identifies coherent and interpretable evolving communities.