KONG Min1,2, CHEN SiBao1, ZHAO HaiFeng1, LUO Bin1
1.School of Computer Science and Technology, Anhui University, Hefei 230039 2.Department of Machine and Electron Engineering, West Anhui University, Lu’an 237012
Abstract：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, intermode adjacency matrices and intermode edgedistance. Then these vectors are embedded in a patternspace 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.
[1] Eshera M A, Fu K S. An Image Understanding System Using Attributed Symbolic Representation and Inexact Graph-Matching. IEEE Trans on Patterns Analysis and Machine Intelligence, 1986, 8(5): 604-618 [2] Sanfeliu A, Fu K S. A Distance Measure between Attributed Relational Graphs for Pattern Recognition. IEEE Trans on Systems, Man and Cybernetics, 1983,13(3): 353-362 [3] Gǘnter S, Bunke H. Self-Organizing Map for Clustering in the Graph Domain. Pattern Recognition Letters, 2002, 23(4): 405-417 [4] Hagenbuchner M, Sperduti A, Tsoi A C. A Self-Organizing Map for Adaptive Processing of Structured Data. IEEE Trans on Neural Networks, 2003, 14(3): 491-505 [5] Luo B, Wilson R C, Hancock E R. Spectral Embedding of Graphs. Pattern Recognition, 2003, 36(10): 2213-2223 [6] Serratosa F, Alquezar R, Sanfeliu A. Synthesis of Function-Described Graphs and Clustering of Attributed Graphs. International Journal of Pattern Recognition and Artificial Intelligence, 2002,16(6): 621-655 [7] Sengupta K, Boyer K L. Organizing Large Structural Modelbases. IEEE Trans on Pattern Analysis and Machine Intelligence, 1995, 17(4): 321-332 [8] Luo B, Robles-Kelly A, Torsello A, Wilson R C, et al. Learning Shape Categories by Clustering Shock Trees // Proc of the IEEE International Conference on Image Processing. Thessaloniki, Greece, 2001, Ⅲ: 672-675 [9] Murase H, Nayer S K. Illumination Planning for Object Recognition Using Parametric Eigenspaces. IEEE Trans on Pattern Analysis and Machine Intelligence, 1994, 16(12): 1219-1227 [10] Kruskal J B. Nonmetric Multidimensional Scaling: A Numerical Method. Psychometrika, 1964, 29: 115-129
2006, Vol. 19 
