论文标题
用于分散图的动态模式分解方法
A Dynamic Mode Decomposition Approach for Decentralized Spectral Clustering of Graphs
论文作者
论文摘要
我们提出了一种新型的强大分散图聚类算法，该算法与流行的光谱聚类方法相当。我们提出的方法使用现有的波方程聚类算法，该算法基于通过图的传播波。但是，我们提出的方法没有在每个节点上使用快速的傅立叶变换（FFT）计算，而是利用了Koopman操作员框架。具体而言，我们表明，在图中传播波，然后在每个节点处进行局部动态模式分解（DMD）计算，能够检索图形laplacian的特征值和局部特征向量组件，从而为所有节点提供局部群集分配。我们证明，DMD计算比现有的基于FFT的方法更强大，并且需要少20倍波动方程的步骤才能准确恢复群集信息并通过数量级来减少相对误差。我们在一系列图集聚类问题上演示了分散的方法。
We propose a novel robust decentralized graph clustering algorithm that is provably equivalent to the popular spectral clustering approach. Our proposed method uses the existing wave equation clustering algorithm that is based on propagating waves through the graph. However, instead of using a fast Fourier transform (FFT) computation at every node, our proposed approach exploits the Koopman operator framework. Specifically, we show that propagating waves in the graph followed by a local dynamic mode decomposition (DMD) computation at every node is capable of retrieving the eigenvalues and the local eigenvector components of the graph Laplacian, thereby providing local cluster assignments for all nodes. We demonstrate that the DMD computation is more robust than the existing FFT based approach and requires 20 times fewer steps of the wave equation to accurately recover the clustering information and reduces the relative error by orders of magnitude. We demonstrate the decentralized approach on a range of graph clustering problems.
