  The smallest eigenvalues and the associated eigenvectors (i.e., eigenpairs)
of a graph Laplacian matrix have been widely used for spectral clustering and
community detection. However, in real-life applications the number of clusters
or communities (say, $K$) is generally unknown a-priori. Consequently, the
majority of the existing methods either choose $K$ heuristically or they repeat
the clustering method with different choices of $K$ and accept the best
clustering result. The first option, more often, yields suboptimal result,
while the second option is computationally expensive. In this work, we propose
an incremental method for constructing the eigenspectrum of the graph Laplacian
matrix. This method leverages the eigenstructure of graph Laplacian matrix to
obtain the $K$-th eigenpairs of the Laplacian matrix given a collection of all
the $K-1$ smallest eigenpairs. Our proposed method adapts the Laplacian matrix
such that the batch eigenvalue decomposition problem transforms into an
efficient sequential leading eigenpair computation problem. As a practical
application, we consider user-guided spectral clustering. Specifically, we
demonstrate that users can utilize the proposed incremental method for
effective eigenpair computation and determining the desired number of clusters
based on multiple clustering metrics.
