18.S096: Spectral Clustering and Cheeger’s Inequality

A new set of Lecture notes for my course is available here. This one is about spectral clustering and Cheeger’s Inequality. In a nutshell spectral clustering can be seen as attempting to cluster a graph by clustering the corresponding points of its Diffusion Maps embedding and Cheeger’s Inequality provides a guarantee of performance (for the case of two clusters). Take a look!

As usual, I will document the open problems here. I remind that there is a much more detailed description of the problems on the notes, including description of partial progress.

Open Problem 3.1.

Cheeger’s inequality (see my notes) allows to efficiently approximate the Cheeger number of a graph up to a square root factor. It means in particular that, given and we can efficiently between the cases where: or . Can this be improved in the following sense?

Does there exists a constant such that it is -hard to, given , and distinguish between the cases

1. , and

2. ?

It turns out that this is a consequence of an important conjecture in Theoretical Computer Science, the Small-Set Expansion Hypothesis. (see this nice survey and references within). In particular, this conjecture is known to imply the Unique-Games Conjecture, that we will discuss in future lectures. (see my notes for references)

Open Problem 3.2. (Certifying that matrices are PSD)

Given a symmetric matrix with small condition number, is there a quasi-linear time (on and the number of non-zero entries of ) procedure that certifies that . More specifically, the procedure can be randomized in the sense that it may, with some probably not certify that even if that is the case, what is important is that it never produces erroneous certificates (and that it has a bounded-away-from-zero probably of succeeding, provided that ).

The Cholesky decomposition produces such certificates, but we do not know how to compute it in quasi-linear time. Note also that the power method can be used in to produce certificates that have arbitrarily small probability of being false certificates. Later in these lecture we will discuss the practical relevance of such a method as a tool to quickly certify solution produced by heuristics.

Open Problem 3.3.

Given a graph , a natural way of evaluating -way clusterign is via the -way expansion constant:

where the maximum is over all choice of disjoint subsets of (but not necessarily forming a partition).

Let be a graph and a positive integer, is the following true?

This is a Theorem by Lee et al if we replace the poly-logarithmic factor by a quadratic factor.

Interestingly, this ( with the poly-logarithmic factor) is known not to hold if we ask that the subsets form a partition (meaning that every vertex belongs to at least one of the sets), see notes and references therein. Note also that no dependency on would contradict the Small-Set Expansion Hypothesis above.

Advertisement