结构图的谱分解及聚类研究

Graph Spectral Decomposition and Clustering

探索用图谱方法嵌入和聚类非加权图,以图的邻接矩阵主要特征向量来定义邻接矩阵的特征模.对每个特征模,我们计算谱特征向量,包括特征模周界、特征模体积、Cheeger 常数、模间邻接矩阵和模间边界距离.用两种对比方法嵌入这些向量到一个模式空间:1)用谱模式特征的协方差矩阵的主成分分析(PCA)和独立分量分析(ICA);2)两类模式向量在 L2范数下的多维尺度变换方法(MDS).另外,我们在三维多面体的二维图像中用角点特征来表示邻近图,以描述不同嵌入方法的聚类效果.

This paper explore how to use spectral methods for embedding and clustering unweighted graphs. The leading eignvectors of the graph adjacency matrix are employed to define eignmodes of the adjacency matrix . For each eigenmode , vectors of spectral properties are computed as feature vectors. These properties include the eigenmode perimeter, eigenmode volume, Cheeger number, inter-mode adjacency matrices and intermode edge-distance. Then these vectors are embedded in a pattern-space using two contrasting approachs . The first of these involves performing principal or independent component analysis on the covariance matrix for the spectral pattern vectors. The second approach involves performing multidimensional scaling on the L2 norm for pairs of patten vectors. This paper also illustrate the utility of the embedding methods on neighbourhood graphs representing the arrangement of corner features in 2D images of 3D polyhedral objects. Experimental results show that clustering graphs using spectral properties of graphs is practical and effective.