Wilson Richard C, Hancock Edwin R, Luo Bin
Department of Computer Science, University of York, Heslington, York Y01 5DD, UK.
IEEE Trans Pattern Anal Mach Intell. 2005 Jul;27(7):1112-24. doi: 10.1109/TPAMI.2005.145.
Graph structures have proven computationally cumbersome for pattern analysis. The reason for this is that, before graphs can be converted to pattern vectors, correspondences must be established between the nodes of structures which are potentially of different size. To overcome this problem, in this paper, we turn to the spectral decomposition of the Laplacian matrix. We show how the elements of the spectral matrix for the Laplacian can be used to construct symmetric polynomials that are permutation invariants. The coefficients of these polynomials can be used as graph features which can be encoded in a vectorial manner. We extend this representation to graphs in which there are unary attributes on the nodes and binary attributes on the edges by using the spectral decomposition of a Hermitian property matrix that can be viewed as a complex analogue of the Laplacian. To embed the graphs in a pattern space, we explore whether the vectors of invariants can be embedded in a low-dimensional space using a number of alternative strategies, including principal components analysis (PCA), multidimensional scaling (MDS), and locality preserving projection (LPP). Experimentally, we demonstrate that the embeddings result in well-defined graph clusters. Our experiments with the spectral representation involve both synthetic and real-world data. The experiments with synthetic data demonstrate that the distances between spectral feature vectors can be used to discriminate between graphs on the basis of their structure. The real-world experiments show that the method can be used to locate clusters of graphs.
事实证明，图结构在计算上对于模式分析来说很繁琐。原因在于，在将图转换为模式向量之前，必须在可能大小不同的结构节点之间建立对应关系。为了克服这个问题，在本文中，我们转向拉普拉斯矩阵的谱分解。我们展示了拉普拉斯谱矩阵的元素如何用于构造置换不变的对称多项式。这些多项式的系数可以用作图特征，并可以以向量方式进行编码。我们通过使用可以被视为拉普拉斯复类似物的厄米特性质矩阵的谱分解，将这种表示扩展到节点上有一元属性且边上有二元属性的图。为了将图嵌入到模式空间中，我们探索是否可以使用包括主成分分析（PCA）、多维缩放（MDS）和局部保持投影（LPP）在内的多种替代策略，将不变量向量嵌入到低维空间中。通过实验，我们证明这些嵌入会产生定义明确的图簇。我们对谱表示的实验涉及合成数据和真实世界数据。合成数据实验表明，谱特征向量之间的距离可用于根据图的结构区分不同的图。真实世界实验表明，该方法可用于定位图的簇。
