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.