Abstract
In this paper we explore how to use spectral methods for embedding and clustering unweighted graphs. We use the leading eigenvectors of the graph adjacency matrix to define eigenmodes of the adjacency matrix. For each eigenmode, we compute vectors of spectral properties. These include the eigenmode perimeter, eigenmode volume, Cheeger number, inter-mode adjacency matrices and intermode edge-distance. We embed these vectors in a pattern-space using two contrasting approaches. The first of these involves performing principal or independent components analysis on the covariance matrix for the spectral pattern vectors. The second approach involves performing multidimensional scaling on the L2 norm for pairs of pattern vectors. We illustrate the utility of the embedding methods on neighbourhood graphs representing the arrangement of corner features in 2D images of 3D polyhedral objects.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
C.M. Cyr and B.B. Kimia. 3D Object Recognition Using Shape Similarity-Based Aspect Graph. In ICCV01, pages I: 254–261, 2001.
M.A. Eshera and K.S. Fu. An image understanding system using attributed symbolic representation and inexact graph-matching. Journal of the Association for Computing Machinery, 8(5):604–618, 1986.
T. Hofmann and J.M. Buhmann. Pairwise data clustering by deterministic annealing. PAMI, 19(2):192–192, February 1997.
Kruskal J.B. Nonmetric multidimensional scaling: A numerical method. Psychometrika, 29:115–129, 1964.
Gower J.C. Some distance properties of latent root and vector methods used in multivariate analysis. Biometrika, 53:325–328, 1966.
Luo N, Wilson R.C and Hancock E.R. Spectral Feture Vectors for Graph Clustering multivariate analysis. Proc. SSPR02, LNCS 2396, pp. 83–93, 2002.
H. Murase and S.K. Nayar. Illumination planning for object recognition using parametric eigenspaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(12):1219–1227, 1994.
A. Sanfeliu and K.S. Fu. A distance measure between attributed relational graphs for pattern recognition. IEEE Transactions Systems, Man and Cybernetics, 13(3):353–362, May 1983.
K. Sengupta and K.L. Boyer. Organizing large structural modelbases. PAMI, 17(4):321–332, April 1995.
Torgerson W.S. Multidimensional scaling. i. theory and method. Psychometrika, 17:401–419, 1952.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Luo, B., Wilson, R.C., Hancock, E.R. (2003). Spectral Clustering of Graphs. In: Hancock, E., Vento, M. (eds) Graph Based Representations in Pattern Recognition. GbRPR 2003. Lecture Notes in Computer Science, vol 2726. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45028-9_17
Download citation
DOI: https://doi.org/10.1007/3-540-45028-9_17
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40452-1
Online ISBN: 978-3-540-45028-3
eBook Packages: Springer Book Archive