  The second eigenvalue of the Laplacian matrix and its associated eigenvector
are fundamental features of an undirected graph, and as such they have found
widespread use in scientific computing, machine learning, and data analysis. In
many applications, however, graphs that arise have several \emph{local} regions
of interest, and the second eigenvector will typically fail to provide
information fine-tuned to each local region. In this paper, we introduce a
locally-biased analogue of the second eigenvector, and we demonstrate its
usefulness at highlighting local properties of data graphs in a semi-supervised
manner. To do so, we first view the second eigenvector as the solution to a
constrained optimization problem, and we incorporate the local information as
an additional constraint; we then characterize the optimal solution to this new
problem and show that it can be interpreted as a generalization of a
Personalized PageRank vector; and finally, as a consequence, we show that the
solution can be computed in nearly-linear time. In addition, we show that this
locally-biased vector can be used to compute an approximation to the best
partition \emph{near} an input seed set in a manner analogous to the way in
which the second eigenvector of the Laplacian can be used to obtain an
approximation to the best partition in the entire input graph. Such a primitive
is useful for identifying and refining clusters locally, as it allows us to
focus on a local region of interest in a semi-supervised manner. Finally, we
provide a detailed empirical evaluation of our method by showing how it can
applied to finding locally-biased sparse cuts around an input vertex seed set
in social and information networks.
