Motivations for Shi-Malik Algorithm So I've been trying to make sense of the clustering algorithm on page 6 of this paper.  

Are the "first" k eigenvalues they refer to the smallest eigenvalues?
What are the $y_i$ exactly? I don't see the motivation for using them.
If anyone could link other literature or explain how/why the first eigenvectors are being used, that would be great.
 A: 
Are the "first" k eigenvalues they refer to the smallest eigenvalues?

Yes. Note that the eigenvalues will all be >= 0 as L here is symmetric and positive semidefinite (PSD).
Also note that the very first eigenvalue that is equals to 0 and is associated with the constant eigenvector (eigenvector containing all entries that are the same), is usually not considered. This is not mentioned in the paper (and most papers) but is done in practice. You'll understand why as you read on.

What are the $y_i$s exactly?

The $y_i$s can be viewed as the "embedded"/dimension-reduced feature vectors of your original datapoints/feature vectors $x_i$s. There is a $y_i$ for each sample $x_i$. Notice that $y_i \in R^k$, whereas $x_i \in R^m$, where $m$ is the dimension of your original feature vectors, with $k <= m$.
The $y_i$s are obtained like this:


*

*Compute the "first k" eigenvectors of the unnormalized laplacian
$L$, skipping the very first eigenvector which is just a constant
vector(See above).

*Pack these eigenvectors $u_1, \dots, u_k$ as columns side-by-side to
form the matrix $U$.

*Now, the $y_i$s are just the rows of $U$, with $i$ indexing the
rows. $y_1$ is now the new representation for $x_1$, $y_2$ for
$x_2$, and so on.


The above process of turning the $x_i$s to $y_i$s is also referred to as Spectral Embedding, a type of dimension reduction.
Spectral clustering is essentially performing dimension reduction of your original samples $x_i$s to $y_i$s using Spectral Embedding and clustering the $y_i$s instead of the $x_i$s. The clusters are obtained by assigning each $x_i$ to the cluster its corresponding $y_i$ gets clustered into. (Last line of pseudocode on page 6).

I don't see the motivation for using them.

A story of graph-cut
One way is by viewing the eigenvectors as the "relaxed" solution to a "balanced" binary graph-partitioning (i.e. graph cut) problem generalized to $k$ -way partitioning, which is essentially the view presented in the paper you referenced. You'll have to read on to fully understand how this fit in but I'll try to give an overview.
The key derivations that justify this approach (in my opinion) are presented on page 12 and 13 of the paper from the section 5.3 Approximating Ncut, where Ncut is the normalized-cut (alluding to normalized graph-cut) presented in the original Shi-Malik paper.
We start with clustering samples into 2 clusters, i.e., let $k = 2$. This can be viewed as a binary graph-cut problem. Each node in a graph represents a sample $x_i$ and an edge connects a sample to its $r$ nearest (i.e. most similar) neighbors on the graph (I deliberately used $r$ to avoid confusion with $k$, which is used here to indicate the number of partitions/clusters). Next, the graph is partitioned into $k = 2$ parts by finding the minimum cost cut. You can think of this as cutting the graph into 2 parts by disconnecting samples which are as dissimilar as possible while trying to ensure that each cluster is "tightly connected" within itself and have "substantial" number of samples. The samples associated with the nodes in one partition are then placed in one cluster, and those in the other partition in another. By doing things this way, you ensure that you have similar samples within the clusters and dissimilar ones between clusters.
Now how is this "story" of graph-cut related to the graph Laplacian $L$ and its eigenvectors presented above?
Well, basically the graph is represented by the graph Laplacian $L$, and 
everything is basically set up in a way to have the solution of the minimum-cut problem be an indicator vector (The vector $f$ in eqn (6) on page 12), where each entry indicates which partition the corresponding sample belongs to.
Because restricting the entries of the solution vector to only take on values from a finite discrete set makes the problem a NP hard discrete optimization problem, we relax that condition by allowing the entries to take on any real value. Relaxing the problem this way turns it into one where the solution is obtained by minimizing the Rayleigh quotient, the solution being the eigenvector associated with the smallest eigenvalue (consult standard any good linear algebra text on this). The entries of the eigenvector is suppose to indicate which partition the corresponding sample $x_i$ belongs to and one heuristic to do this is to place all samples with corresponding values in the eigenvectors > 0 into one cluster and those < 0 into another.
Note that we ignore the very first eigenvector as it is just the constant vector (hence is not informative) and use the eigenvector corresponding to the second smallest eigenvalue (which could very well be 0) instead.
What do we understand from this? Well, samples which are similar, and hence placed into the same partition should have similar values in the eigenvector.
To generalize to the case of $k > 2$, the idea is to use the remaining eigenvectors to further "refine" the clusterings. (I'm going to leave it vague from here on as I'm short of time.) Basically, in subsequent eigenvectors, similar samples should also have similar values in them. Therefore, if we consider two similar sample $x_i$ and $x_j$, the entries of the eigenvectors in the $ith$ coordinate should be similar to those in the $jth$ coordinates of the eigenvectors (since they will likely be placed in the same partition after graph-partitioning). But $x_i$ and $x_j$ could have similar values in some eigenvectors but different ones in others as each eigenvector basically provide more information to further separate the samples into different partitions. Packing these values in the eigenvectors together (the rows of $U$, i.e. $y_i$s) and considering them as a whole helps to better distinguish the corresponding samples $x_i$ and $x_j$ rather than just relying on any one value from a particular eigenvector. This is why we use the $y_i$s as the new representation for the $x_i$s.

(My own question) If the $y_i$s are similar if the $x_i$s are similar, why don't we just use the $x_i$s to begin with?

The key to answering this question is in the last equation on page 4:
\begin{equation}
y^TLy = \sum_{i,j=1}^n w_{ij}(y_i - y_j)^2
\end{equation}
Note that I have replaced $f$ in the original equation with $y$ to be consistent with the notation used here. Also, here $y \in R^n$ and the $y_i$ is an entry in $y$, whereas the $y_i$ above are rows of $U$ (and hence vectors).
Further, When the "normalized" Laplacians are used, the above equation changes slightly to take into account the specific normalization introduced by the choice of "normalized" Laplacian but the overall "form" of the equations and idea remains the same.
Now, if you stare hard enough at the above equation, you'll notice that it is the objective in the binary graph-cut problem that we are trying to minimize.
By constraining $\vert\vert y \vert\vert^2 = 1$ we turn the problem into one minimizing the Rayleigh quotient mentioned above and in the paper.
Here $w_{ij}$ is a measure of similarity between $x_i$ and $x_j$, with larger values indicating they are more similar. Hence, because we are minimizing the objective and solving for the $y_i$s, we are encouraging $y_i$ to be close in value to $y_j$ so that they "cancel" each other out if $w_{ij}$ is large ($x_i$ similar to $x_j$). The key thing to note is the idea that similarities propagate through the graph. This somewhat cryptic sentence basically means that if $x_i$ is very similar to $x_j$, and $x_j$ in turn is very similar to $x_k$, then $y_i$ and $y_k$ will also have close values by virtue of both having to be similar to $y_j$. In this way, the $y_i$s of "densely" packed $x_i$s which are actually far apart can have $y_i$ values close to each other whereas in their original representation, the $x_i$s, points at "2 ends" of a densely packed region may have very dissimilar values if the region is spread far apart. Hence, the $y_i$s make far better representation than the $x_i$s if the criteria you are doing density-based clustering or if you are trying to improve the representation of the $x_i$s using relational information. Think of the standard "2 crescent moon" synthetic dataset as you meditate on this.
The key part of spectral clustering is really just the spectral embedding part. The idea is related to manifold learning and the graph laplacian is also a key part of some semi-supervised learning algorithm (for enforcing label similarity). It is a huge area that I cannot cover in this already long post, so I'll direct you to some references (in no particular order).


*

*The one you are reading is perhaps already the best. Give it more time.

*Ulrike von Luxburg's video lecture on spectral clustering on
videolectures.net

*Semi-Supervised Learning Edited by Olivier Chapelle, Bernhard
Schölkopf and Alexander Zien

*Introduction to Semi-Supervised Learning Synthesis Lectures on
Artificial Intelligence and Machine Learning by Xiaojin Zhu and
Andrew B. Goldberg

*Dimension Reduction: A Guided Tour", Foundations and Trends in
Machine Learning by Christopher J. C. Burges (available on his
website)

*Segmentation using eigenvectors: a unifying view, by Yair Weiss.


The above is a non-exhaustive list. I'm sure others will be able to direct you to more useful ones.
Disclaimer: I wrote this in a hurry and I'm sure there will be mistakes so read it with this in mind. If I can find time, I may come back and improve this.
