Graph Clustering using Symmetric Polynomials and Local Linear Embedding
Edwin R. Hancock, Richard C. Wilson, Bing Xiao · 2003
Although graph structures have proved useful in high level vision for object recognition and matching, they can prove computationally cumbersome because of the need to establish reliable correspondences between nodes. Hence, standard pattern recognition techniques can not be easily applied to graphs since feature vectors and not easily contructed. To overcome this problem, in this paper we turn to the spectral matrix. We show how the elements of this matrix can be used to construct symmetric polynomials that are permutation invariants. The co-efficients of these polynomials can be used as graph-features which can be encoded in a vectorial manner. We demonstrate that these vectors can be embedded in a low dimensional space using locally linear embedding, and that the embedding results in well defined graph clusters.