Let νi and ui be the eigenvalues and eigenvectors of ℒ. We index these {i = 0, 1, …, N − 1} in reference to the first “trivial” eigenvector u0 associated with eigenvalue ν0 = 0. We replace H with I − ℒ, where I is the identity matrix, and map the the ith subject into a lower dimensional space according to Equation 2, where ui and λi = max{0, 1 − νi}, respectively, are the eigenvectors and truncated eigenvalues of I − ℒ. In Results, we show that estimating the ancestry from the eigenvectors of ℒ (which are the same as the eigenvectors of I − ℒ) leads to more meaningful clusters than ancestry estimated directly from ϒϒt. Some intuition as to why this is the case can be gained by relating eigenmaps to spectral clustering and “graph cuts.” In graph-theoretic language, the goal of clustering is to find a partition of the graph so that the connections between different groups have low weight and the connections within a group have high weight. For two disjoint sets A and
