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

图是用于有效地表示诸如社交网络、金融交易等的结构化数据域中的实体之间的交互和结构关系的流行数据结构。其关联图拉普拉斯算子的特征值和特征向量揭示了图的几个特征，例如连通性、规律性、聚类等。在许多应用中，底层图随时间而变化，并且学习这种动态图的表示并发现其中的潜在结构是必不可少的。然而，目前还缺乏有效的算法来计算动态图的谱特性，在这个项目中，我们感兴趣的是更新的时变图的谱特性的潜在结构发现的问题。动态图可能会随着时间的推移进行添加/删除的边缘和/或节点，我们希望开发快速和可扩展的方法来估计这样的图的光谱信息。特别是，我们重点研究了以下两个问题：1.谱聚类：图谱聚类涉及计算图拉普拉斯算子的部分谱。为了跟踪聚类结构，更新变化图的特征向量的问题是在许多应用中发生的基本问题。在这个项目中，我们提出了一种新的方法来更新的特征向量的时变图的投影型方法的基础上。这些方法可以通过假设图的稀疏和低秩更新来廉价地更新特征向量。变点检测：时变图中的变点检测是另一个重要的问题，有几个应用。我们的方法是利用张量框架进行有效的动态图变点检测。这个想法是考虑从变化图的快照中获得的拉普拉斯张量。然后，我们可以探索基于此类张量的t-SVD的变点检测方法。

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.