Why is non-negative eigen value an important property for graph Laplacian?

Question

In Luxburg, A Tutorial on Spectral Clustering, 2007, the author presents several properties of unnormalized graph laplacian, $L = D −W$:

My question is:

• why does Property 4 of $L$ matter?
• Is it related to the following Proposition? If so, how?

PS: The proof of both propositions can be found the original document.

Short answer:

• Why does Property 4 matter?

If not, the minimal value of $f^{'}Lf$ is $-\infty$ (Point 1 of accepted answer), thus the minimization problem of $f^{'}Lf$ is meaningless.

Answer 1

1. If you are asking what would happen when solving $\min_{f} f^\mathrm{T}Lf$ when $L$ is symmetric and has at least one negative eigenvalue, it can be shown that $f^\mathrm{T}Lf$ is not convex and $\min_{f} f^\mathrm{T}Lf=-\infty$ in this case. Check the shape of $g(x,y)=x^2-y^2$, for example. $L=D-W$ has negative eigenvalue(s) if negative weights (entries in $W$) are allowed.
2. If you are asking whether the intuition of proposition 2 and property 4 are related (while the mathematical connection should be in the proofs), we know that $\min_f f^\mathrm{T}Lf=\lambda_1\|f\|^2=0$, this can be achieved by setting the entries of $f$ in the same component to a constant. The constants corresponding to different connected components do not have to be the same. The "degree of freedom" here is of course the number of connected components but also exactly the number of dimensions of the eigenspace of $0$ (because necessarily the optimal $f$ satisfies $Lf=0$). If this is the relation/interpretation you are looking for then yes.