The K Means Clustering run on the distinct $a_i$ data points, assigns them to different clusters. The question then arises, how does this allow us to assign cluster assigments to the original data points?

Well, matrix M has dimensionality n x k, i.e. it has n separate points that are classified by the K Means algorithm. Each of these n points is in a one-to-one correspondence with each of the n points in the original similarity matrix i.e. each node of the graph which directly encodes every data point. Thus the assignment of the ith row in M is the same as the cluster assignment of the ith data point.

Thus spectral clustering helps us be more efficient with assigning clusters to points of high dimensionality, by mapping them to a lower dimension and then running K means on them.