Revisiting the Isoperimetric Graph Partitioning Problem
Isoperimetric graph partitioning, which is also known as the Cheeger cut, is NP-hard in its original form. In the literature, multiple modifications to this problem have been proposed to obtain approximation algorithms for clustering applications. In the context of image segmentation, a heuristic co...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2019-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8694009/ |
| _version_ | 1818613354575429632 |
|---|---|
| author | Sravan Danda Aditya Challa B. S. Daya Sagar Laurent Najman |
| author_facet | Sravan Danda Aditya Challa B. S. Daya Sagar Laurent Najman |
| author_sort | Sravan Danda |
| collection | DOAJ |
| description | Isoperimetric graph partitioning, which is also known as the Cheeger cut, is NP-hard in its original form. In the literature, multiple modifications to this problem have been proposed to obtain approximation algorithms for clustering applications. In the context of image segmentation, a heuristic continuous relaxation to this problem introduced by Leo Grady and Eric L. Schwartz has yielded good quality results. This algorithm is based on solving a linear system of equations involving the Laplacian of the image graph. Furthermore, the same algorithm applied to a maximum spanning tree (MST) of the image graph was shown to produce similar results at a much lesser computational cost. However, the data reduction step (i.e., considering an MST, a much sparser graph compared to the original graph) leading to a faster yet useful algorithm has not been analyzed. In this paper, we revisit the isoperimetric graph partitioning problem and rectify a few discrepancies in the simplifications of the heuristic continuous relaxation, leading to a better interpretation of what is really done by this algorithm. We then use the power watershed (PW) framework to show that is enough to solve the relaxed isoperimetric graph partitioning problem on the graph induced by the union of MSTs (UMST) with a seed constraint. The UMST has a lesser number of edges compared to the original graph, thus improving the speed of sparse matrix multiplication. Furthermore, given the interest of PW framework in solving the relaxed seeded isoperimetric partitioning problem, we discuss the links between the PW limit of the discrete isoperimetric graph partitioning and watershed cuts. We then illustrate with experiments, a detailed comparison of solutions to the relaxed seeded isoperimetric partitioning problem on the original graph with the ones on the UMST and an MST. Our study opens many research directions, which are discussed in the conclusion section. |
| first_indexed | 2024-12-16T16:00:47Z |
| format | Article |
| id | doaj.art-883e562faf554767b305687086781387 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-16T16:00:47Z |
| publishDate | 2019-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-883e562faf554767b3056870867813872022-12-21T22:25:28ZengIEEEIEEE Access2169-35362019-01-017506365064910.1109/ACCESS.2019.29010948694009Revisiting the Isoperimetric Graph Partitioning ProblemSravan Danda0https://orcid.org/0000-0002-2253-4324Aditya Challa1B. S. Daya Sagar2Laurent Najman3Systems Science and Informatics Unit, Indian Statistical Institute at Bangalore, Bengaluru, IndiaSystems Science and Informatics Unit, Indian Statistical Institute at Bangalore, Bengaluru, IndiaSystems Science and Informatics Unit, Indian Statistical Institute at Bangalore, Bengaluru, IndiaLIGM, Equipe A3SI, ESIEE, Université Paris-Est, Paris, FranceIsoperimetric graph partitioning, which is also known as the Cheeger cut, is NP-hard in its original form. In the literature, multiple modifications to this problem have been proposed to obtain approximation algorithms for clustering applications. In the context of image segmentation, a heuristic continuous relaxation to this problem introduced by Leo Grady and Eric L. Schwartz has yielded good quality results. This algorithm is based on solving a linear system of equations involving the Laplacian of the image graph. Furthermore, the same algorithm applied to a maximum spanning tree (MST) of the image graph was shown to produce similar results at a much lesser computational cost. However, the data reduction step (i.e., considering an MST, a much sparser graph compared to the original graph) leading to a faster yet useful algorithm has not been analyzed. In this paper, we revisit the isoperimetric graph partitioning problem and rectify a few discrepancies in the simplifications of the heuristic continuous relaxation, leading to a better interpretation of what is really done by this algorithm. We then use the power watershed (PW) framework to show that is enough to solve the relaxed isoperimetric graph partitioning problem on the graph induced by the union of MSTs (UMST) with a seed constraint. The UMST has a lesser number of edges compared to the original graph, thus improving the speed of sparse matrix multiplication. Furthermore, given the interest of PW framework in solving the relaxed seeded isoperimetric partitioning problem, we discuss the links between the PW limit of the discrete isoperimetric graph partitioning and watershed cuts. We then illustrate with experiments, a detailed comparison of solutions to the relaxed seeded isoperimetric partitioning problem on the original graph with the ones on the UMST and an MST. Our study opens many research directions, which are discussed in the conclusion section.https://ieeexplore.ieee.org/document/8694009/Image segmentationisoperimetric partitioningCheeger cutspectral clusteringpower watersheds |
| spellingShingle | Sravan Danda Aditya Challa B. S. Daya Sagar Laurent Najman Revisiting the Isoperimetric Graph Partitioning Problem IEEE Access Image segmentation isoperimetric partitioning Cheeger cut spectral clustering power watersheds |
| title | Revisiting the Isoperimetric Graph Partitioning Problem |
| title_full | Revisiting the Isoperimetric Graph Partitioning Problem |
| title_fullStr | Revisiting the Isoperimetric Graph Partitioning Problem |
| title_full_unstemmed | Revisiting the Isoperimetric Graph Partitioning Problem |
| title_short | Revisiting the Isoperimetric Graph Partitioning Problem |
| title_sort | revisiting the isoperimetric graph partitioning problem |
| topic | Image segmentation isoperimetric partitioning Cheeger cut spectral clustering power watersheds |
| url | https://ieeexplore.ieee.org/document/8694009/ |
| work_keys_str_mv | AT sravandanda revisitingtheisoperimetricgraphpartitioningproblem AT adityachalla revisitingtheisoperimetricgraphpartitioningproblem AT bsdayasagar revisitingtheisoperimetricgraphpartitioningproblem AT laurentnajman revisitingtheisoperimetricgraphpartitioningproblem |