PREVIOUS SEMINAR - 3rd December 2021

Housen Li (University of Göttingen)

Title: Distributional limits of graph cuts on discretized samples


Abstract - Graph cuts are well-established tools for clustering and classification analysis, with prominent applications found in a plethora of scientific fields, e.g. statistics, computer science and machine learning. In particular, they can be seen as a change point problem on graphs. Distributional limits are fundamental in understanding and designing statistical procedures on randomly sampled data, but no such results are known for graph cuts in the literature. To fill this gap, in this paper explicit limiting distributions for balanced graph cuts in general on a fixed but arbitrary discretization are provided. In particular, we show that Minimum Cut, Ratio Cut and Normalized Cut behave asymptotically normal as sample size increases. Besides, our results reveal an interesting dichotomy for Cheeger Cut: The limiting distribution is normal for a partition when the balancing term is differentiable while otherwise, the limiting distribution is a random mixture of normals (i.e. a mixture of normals with non-deterministic weights). We verify and support these theoretical findings by means of simulation, pointing out differences between the cuts and the dependency on the underlying distribution. This is a joint work with Axel Munk (University of Göttingen) and Leo Suchan (University of Göttingen).