Estimation of spectral properties for discovery of latent structures in dynamic graphs

Graphs are popular data structures used to effectively represent interactions and structural relationships between entities in structured data domains such as social networks, financial transactions, etc. Spectral properties of a graph, i.e., the eigenvalues and eigenvectors of its associated graph Laplacian, reveal several characteristics of the graph such as connectivity, regularity, clustering, etc. In many applications, the underlying graph changes over time, and learning representations of such dynamic graphs and discovering latent structures in them are essential. However, efficient algorithms to compute the spectral properties of dynamic graphs are lacking.

In this project, we are interested in the problem of updating the spectral properties of time varying graphs for latent structure discovery. The dynamic graph may undergo addition/deletion of edges and/or nodes over time, and we wish to develop fast and scalable methods to estimate the spectral information of such graphs. In particular, we focus on the following two problems:

1. Spectral clustering: Graph spectral clustering involves computing the partial spectra of the graph Laplacian. The problem of updating the eigenvectors of a changing graph, in order to keep track of the clustering structure, is a fundamental problem that occurs in many applications. In this project, we propose a novel approach to update the eigenvectors of a time varying graph based on projection type methods. These methods can update the eigenvectors inexpensively, by assuming sparse and low-rank updates to the graph.

2. Change-point detection: Change-point detection in time varying graphs is another important problem with several applications. Our approach is to leverage the tensor framework for efficient dynamic graph change-point detection. The idea is to consider a Laplacian tensor obtained from the snapshots of the changing graph. We can then explore methods for change-point detection based on the t-SVD of such tensors.