eigenvalues-eigenvectorsgraph theorygraph-laplacianlinear algebrapositive-semidefinite
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?
Use the inner product. For an eigenvalue $\lambda$ and eigenvector $x$ of $B^*B$
$\lambda ||x||^2=\langle B^*Bx,x\rangle=||Bx||^2$.
Hence $\lambda$ is real and nonnegative.
I can make two sort of hand-wavy observations. From basic linear algebra properties we know that given a matrix $ \mathbf{L} $ \begin{equation} \sum_{i}d_{i}= \sum_{i}\lambda_{i} \end{equation}
where $ \lambda $ are the eigenvalues, and $ d $ are the the diagonal elements of your matrix $ \mathbf{L} $.
The elements on the diagonal of the Laplacian correspond to the degrees of the vertices. Assuming no isolated vertices and that the graph is simple (i.e weights are either $0$ or $1$), $ d_{i} \geq 1 $.
If most of your eigenvalues are equal to $1$, then their sum is also likely a small number. That means that the sum of degrees is also a small number, which means that your graph is probably sparsely connected.
The next observation has to do with star graphs. In general, complete bipartite graphs with $n$ and $m$ vertices on each group respectively, have Laplacian eigenvalues:
Consider the star graph below which is a complete bipartite graph with $n=1$ and $m=8$
Its eigenvalues are $1$ with multiplicity $7$, $0$ with multiplicity $1$ and $9$ with multiplicity $1$.
So, if your graph contains starlike subgraphs, then your Laplacian is going to have a bunch of $1$-eigenvalues. I include two examples below (the random isolated component belongs to the graph on the right).
. 
Both of these graphs have eigenvalue $1$ with multiplicity $9$.
Best Answer
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.