Abstract
Szemerédi’s regularity lemma is a deep result from extremal graph theory which states that every graph can be well-approximated by the union of a constant number of random-like bipartite graphs, called regular pairs. Although the original proof was non-constructive, efficient (i.e., polynomial-time) algorithms have been developed to determine regular partitions for arbitrary graphs. This paper reports a first attempt at applying Szemerédi’s result to computer vision and pattern recognition problems. Motivated by a powerful auxiliary result which, given a partitioned graph, allows one to construct a small reduced graph which inherits many properties of the original one, we develop a two-step pairwise clustering strategy in an attempt to reduce computational costs while preserving satisfactory classification accuracy. Specifically, Szemerédi’s partitioning process is used as a preclustering step to substantially reduce the size of the input graph in a way which takes advantage of the strong notion of edge-density regularity. Clustering is then performed on the reduced graph using standard algorithms and the solutions obtained are then mapped back into the original graph to create the final groups. Experimental results conducted on standard benchmark datasets from the UCI machine learning repository as well as on image segmentation tasks confirm the effectiveness of the proposed approach.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Alon, N., Duke, R.A., Lefmann, H., Rödl, V., Yuster, R.: The algorithmic aspects of the regularity lemma. J. of Algorithms 16, 80–109 (1994) (also in Proc. 33rd IEEE FOCS, Pittsburgh, IEEE, 473–481 (1992))
Bengio, Y., Paiement, J., Vincent, P., Delalleau, O., Roux, N.L., Ouimet, M.: Out-of-sample extensions for lle, isomap, mds, eigenmaps, and spectral clustering. In: Thrun, S., Saul, L., Schölkopf, B. (eds.) Advances in Neural Information Processing Systems 16, MIT Press, Cambridge, MA (2004)
Bollobás, B.: Extremal Graph Theory. Academic Press, London (1978)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge, MA (2001)
Czygrinow, A., Rödl, V.: An algorithmic regularity lemma for hypergraphs. SIAM J. Comput. 30(4), 1041–1066 (2000)
Diestel, R.: Graph Theory, 3rd edn. Springer, New York (2005)
Fowlkes, C., Belongie, S., Chung, F.R.K., Malik, J.: Spectral grouping using the Nyström method. IEEE Trans. Pattern Anal. Mach. Intell. 26, 214–225 (2004)
Frieze, A.M., Kannan, R.: A simple algorithm for constructing Szemerédi’s regularity partition. Electron. J. Comb. 6 (1999)
Kohayakawa, Y., Rödl, V., Thoma, L.: An optimal algorithm for checking regularity. SIAM J. Comput. 32(5), 1210–1235 (2003)
Komlós, J., Shokoufandeh, A., Simonovits, M., Szemerédi, E.: The regularity lemma and its applications in graph theory. In: Khosrovshahi, G.B., Shokoufandeh, A., Shokrollahi, A. (eds.) Theoretical Aspects of Computer Science: Advanced Lectures, pp. 84–112. Springer, New York (2002)
Komlós, J., Simonovits, M.: Szemerédi’s regularity lemma and its applications in graph theory. In: Miklós, D., Szonyi, T., Sós, V.T. (eds.) Combinatorics, Paul Erdös is Eighty (vol. 2), pp. 295–352. Bolyai Society Mathematical Studies 2, Budapest (1996)
Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Turán. Canad. J. Math. 17, 533–540 (1965)
Pavan, M., Pelillo, M.: Dominant sets and pairwise clustering. IEEE Trans. Pattern Anal. Mach. Intell. 29, 167–172 (2007)
Pavan, M., Pelillo, M.: Efficient out-of-sample extension of dominant-set clusters. In: Saul, L.K., Weiss, Y., Bottou, L. (eds.) Advances in Neural Information Processing Systems 17, pp. 1057–1064. MIT Press, Cambridge, MA (2005)
Roth, V., Laub, J., Kawanabe, M., Buhmann, J.M.: Optimal cluster preserving embedding of nonmetric proximity data. IEEE Trans. Pattern Anal. Mach. Intell. 25, 1540–1551 (2003)
Szemerédi, E.: Regular partitions of graphs. In: Colloques Internationaux CNRS 260—Problèmes Combinatoires et Théorie des Graphes, Orsay, pp. 399–401 (1976)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sperotto, A., Pelillo, M. (2007). Szemerédi’s Regularity Lemma and Its Applications to Pairwise Clustering and Segmentation. In: Yuille, A.L., Zhu, SC., Cremers, D., Wang, Y. (eds) Energy Minimization Methods in Computer Vision and Pattern Recognition. EMMCVPR 2007. Lecture Notes in Computer Science, vol 4679. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74198-5_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-74198-5_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74195-4
Online ISBN: 978-3-540-74198-5
eBook Packages: Computer ScienceComputer Science (R0)