What do negative eigenvalues for Laplacian matrix, if possible, represent? I created a Laplacian matrix for data points, which is $L = D - A$, 
and when I do compute the eigenvalues of $L$, I sometimes get a negative eigenvalue. I know that for nonlinear dimensionality reduction (manifold learning), I need to use eigenvectors that correspond to the $M$ smallest eigenvalues, but I thought $L$ is always positive semidefinite...
What do negative eigenvalues of the Laplacian matrix represent?
 A: Assuming you are talking about the Laplacian matrix of a simple (undirected) graph, you were right: it never has negative eigenvalues. As such, negative eigenvalues of the Laplacian do not represent anything; they merely indicate that you made a mistake in computing the Laplacian or finding its eigenvalues. That's all one can say with the information you provided.
If you are somehow working with a directed graph, then it is not clear what the Laplacian even means (what are the diagonal entries?). Even if you overcome this obstacle in the definition, you will typically end up with complex eigenvalues since the matrix is no longer symmetric.

I suggest this: if you wrote your own code (or used built-in functions of a computer algebra system) to compute the eigenvalues, then you may post your code on the relevant Q&A Community (such as StackOverflow, Mathematica Stack Exchange or ASKSAGE). In that case, you may want to read the hints provided here to avoid your question being closed as off-topic.
