Szemeredi's Regularity Lemma and Its Applications to Pairwise Clustering and Segmentation

Anna Sperotto, M. Pelillo

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    11 Citations (Scopus)
    41 Downloads (Pure)

    Abstract

    Szemeredi’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 Szemeredi’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, Szemeredi’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.
    Original languageUndefined
    Title of host publicationEnergy Minimization Methods in Computer Vision and Pattern Recognition Energy Minimization Methods in Computer Vision and Pattern Recognition, 6th International Conference, EMMCVPR 2007
    Place of PublicationBerlin
    PublisherSpringer
    Pages13-27
    Number of pages15
    ISBN (Print)978-3-540-74195-4
    DOIs
    Publication statusPublished - 14 Aug 2007
    Event6th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition, EMMCVPR 2007 - EZhou, Hubei, China
    Duration: 27 Aug 200729 Aug 2007
    Conference number: 6

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer Verlag
    Volume4679

    Conference

    Conference6th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition, EMMCVPR 2007
    Abbreviated titleEMMCVPR
    CountryChina
    CityEZhou, Hubei
    Period27/08/0729/08/07

    Keywords

    • EWI-10951
    • IR-61893
    • METIS-245730

    Cite this