Statistical Limit Laws for Graph Cuts and Efficient Surrogate Algorithms

by Leo Athanasius Suchan
Doctoral thesis
Date of Examination:2024-11-29
Date of issue:2024-12-05
Advisor:Prof. Dr. Axel Munk
Referee:Prof. Dr. Axel Munk
Referee:Prof. Dr. Max Wardetzky
Persistent Address: http://dx.doi.org/10.53846/goediss-10926

 

 

Files in this item

Name:Dissertation_Leo_Suchan.pdf
Size:14.5Mb
Format:PDF
Description:DIssertation

The following license files are associated with this item:

Abstract

English

Graph cuts are a powerful tool that has been used in many applications, from image segmentation and machine learning to network analysis and cluster identification, often in the form of a convex relaxation such as spectral clustering that sacrifices cut quality for computational speed. In this thesis we propose Xist, a polynomial algorithm that produces partitions which imitate graph cuts from a qualitative perspective while retaining a fast computation speed. By applying Xist to a variety of different data, we demonstrate that it outperforms state-of-the-art algorithms by factors of up to 20 in terms of graph cut value while being comparable in terms of computational speed. We additionally show that within a discretization framework, graph cuts admit a limiting distribution, thus deriving the first central limit theorem for graph cuts. In particular, we discover that Cheeger Cut can be highly sensitive towards changes in the structure of the underlying distribution by admitting two different limiting distributions depending on a specific volume equality condition. We showcase the applicability of our asymptotic theory by proving bootstrap consistency and by deriving a limiting distribution for our Xist algorithm, enabling us to test homogeneity in data, for instance. We support these findings by extensive simulations, applications to large network data and clustering biological cell images.
Keywords: asymptotic distribution; central limit theorem; combinatorial optimization; discretization; graph cut; sparsest cut; graph theory; partitioning algorithms; clustering algorithms; image segmentation
 
Statistik