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
Cyr, C.M., Kimia, B.B.: 3D Object Recognition Using Shape Similarity-Based Aspect Graph. In: ICCV 2001, pp. I: 254–261 (2001)
Eshera, M.A., Fu, K.S.: An image understanding system using attributed symbolic representation and inexact graph-matching. Journal of the Association for Computing Machinery 8(5), 604–618 (1986)
Hofmann, T., Buhmann, J.M.: Pairwise data clustering by deterministic annealing. PAMI 19(2), 192–192 (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., Hancock, E.R.: Spectral Feture Vectors for Graph Clustering multivariate analysis. In: Caelli, T.M., Amin, A., Duin, R.P.W., Kamel, M.S., de Ridder, D. (eds.) SPR 2002 and SSPR 2002. LNCS, vol. 2396, pp. 83–93. Springer, Heidelberg (2002)
Murase, H., Nayar, S.K.: Illumination planning for object recognition using parametric eigenspaces. IEEE Transactions on Pattern Analysis and Machine Intelligence 16(12), 1219–1227 (1994)
Sanfeliu, A., Fu, K.S.: A distance measure between attributed relational graphs for pattern recognition. IEEE Transactions Systems, Man and Cybernetics 13(3), 353–362 (1983)
Sengupta, K., Boyer, K.L.: Organizing large structural modelbases. PAMI 17(4), 321–332 (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: Petkov, N., Westenberg, M.A. (eds) Computer Analysis of Images and Patterns. CAIP 2003. Lecture Notes in Computer Science, vol 2756. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45179-2_66
Download citation
DOI: https://doi.org/10.1007/978-3-540-45179-2_66
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40730-0
Online ISBN: 978-3-540-45179-2
eBook Packages: Springer Book Archive