Computer Science – Data Structures and Algorithms
Scientific paper
2009-12-03
Computer Science
Data Structures and Algorithms
24 pages. Completely rewritten; substance is still the same, but the presentation is reworked
Scientific paper
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.
Mahoney Michael W.
Orecchia Lorenzo
Vishnoi Nisheeth K.
No associations
LandOfFree
A Local Spectral Method for Graphs: with Applications to Improving Graph Partitions and Exploring Data Graphs Locally does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Local Spectral Method for Graphs: with Applications to Improving Graph Partitions and Exploring Data Graphs Locally, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Local Spectral Method for Graphs: with Applications to Improving Graph Partitions and Exploring Data Graphs Locally will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-517821