Assign new point to a class using spectral clustering Say I used spectral clustering to cluster a data-set $D$ of points $X_0 - X_n$ into a number $C$ of clusters. How can I efficiently assign a new single point $X_{n+1}$ to his convenient cluster?

Do I have to do the classification from the beginning (destroy all the clusters and apply the algorithm to the data-set $X_0 - X_{n+1}$), or is there an optimized way to extend to the point $X_{n+1}$?
I think you do not, since I was able to find several papers that proposed algorithms for the same:


Incremental spectral clustering by efficiently updating the eigen-system
Incremental kernel spectral clustering for online learning of non-stationary data
A Fast Incremental Spectral Clustering for Large Data Sets


Such algorithms are called sequential, incremental, streaming, or online. Armed with this knowledge, you can find more papers on your own.