Cluster analysis on dynamic graphs

• Main Author: Er, Jia Chin
• Other Authors: Ke Yiping, Kelly
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2021
• Subjects: Engineering::Computer science and engineering::Data::Data structures; Engineering::Computer science and engineering::Computing methodologies::Pattern recognition
• Online Access: https://hdl.handle.net/10356/153299
• Institution: Nanyang Technological University

Graph clustering aims to group nodes into a cluster by their features or by some similarity measure, with nodes in the same cluster having higher similarity than those outside of their cluster. Earlier work on graph clustering studied clustering on static graphs, which do not evolve over time. This is in stark contrast to real world graphs, which are dynamic in nature and evolve with the addition and deletion of edges and nodes. Current approaches to dynamic graphs model it as a stream of interactions between nodes, such that any graph event is an interaction in the stream. However, another model of framing dynamic graphs are graph snapshots, which represent the state of the graph at different timestamps. For systems lacking fine-grained time measures, such graph snapshots are the only way to capture the temporal nature of the graph. This paper addresses the topic of graph clustering, first in the static domain and secondly in the dynamic domain, where the graph can evolve over time. We examine prior work in graph clustering, from the unsupervised methods initially where we optimize the clusters based on some quality measure to the application of graph neural networks on graph clustering. Next, we apply the concept of temporal attention along with transitional recurrent neural networks to the topic of dynamic graph clustering on graph snapshots. We then formulate a concept of temporal attention over graph snapshots and apply this to create our model. The results obtained from the model beat out transitional recurrent neural networks using graph convolution and empirical data shows that there is a gain in accuracy from this encoding of temporal attention.