with eigenvalue 0.
Corollary 1. For a complete graph , any vector perpendicular to is also an eigenvector of the graph Laplacian.
Proof: Since is complete, the graph Laplacian can be written as If , then . This also proves that the eigenvalue has algebraic multiplicity .
First, note that
allowing us to rewrite the cut ratio as
One very interesting and surprising fact is that the sum of squared pairwise differences in the numerator and denominator of can be written in terms of matrix products using the graph Laplacian. Specifically, we can write
| || |
where is the graph Laplacian of and is the graph Laplacian of the complete graph on .
This, along with the fact allows us to bound this re-expressed cut ratio:
| ||To prove this, we can use the fact that every Laplacian can be written as a sum of edge Laplacians, . Then Note that this also proves that the Laplacian is positive semi-definite. |
While removing the in the denominator makes a convex objective, the minimization problem is still NP-hard because of the support of . We can further relax the problem by letting since we can threshold the values of to make it binary. Then, note that WLOG, we can also assume that since we could arbitrarily shift however we wanted. Therefore, our final optimization problem is
To solve this elegantly, we will appeal to classical properties of the graph Laplacian.
| ||This innocuous constraint also buys us . To see this, think about the sum in terms of a dot product. |
Since we can assume that , Corollary 1 allows us to rewrite our optimization problem as
This bounded quadratic form is present in many optimization problems, and since the graph Laplacian is symmetric, we can solve it using the Courant–Fischer theorem. Specifically, appealing to Corollary 1 in the PCA derivation, we can solve , where are the eigenvalues of . Note that we know the eigenvalues of are non-negative because we proved that is positive semi-definite in deriving the approximate objective function.
Therefore, the final solution to the graph cut relaxation is
| ||For background on the Courant–Fischer theorem, see this derivation of PCA. In this proof, we use the variant of Courant–Fischer where the eigenvalues are sorted in ascending order. The statement is mostly the same, except the min-max becomes a max-min. |