Abstract
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 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 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.
Introduction
In graph analysis, spectral methods—which rely on the eigenvalues and eigenvectors of a graph's Laplacian matrix—are the gold standard for finding global structure, such as the best way to bisect a network. However, these methods are inherently global; they often "wash out" interesting local features. If a researcher is interested in a specific community within a massive social network or a particular segment of an image, the global second eigenvector might provide no useful information about that target region.
This paper introduces LocalSpectral, a method that bridges the gap between global spectral graph theory and local random walk techniques like Personalized PageRank (PPR). By adding a locality constraint to the standard spectral optimization problem, the authors provide a principled, nearly-linear time algorithm for finding high-quality clusters and sparse cuts near a specific area of interest.
The LocalSpectral Framework
The core innovation of this work is the formulation of local clustering as an optimization problem. The authors take the standard spectral optimization problem (minimizing the Rayleigh quotient of the Laplacian) and incorporate a "locality constraint." This constraint forces the solution vector to maintain a minimum level of correlation (denoted by $\kappa$) with a "seed vector" ($s$) representing the region of interest.
The solution to this constrained problem takes the form of a shifted linear system: $(L_G - \gamma D_G)x = D_G s$. A key mathematical insight is that this solution is a generalization of the Personalized PageRank vector. By varying the parameter $\gamma$, one can smoothly transition from a very local PPR-like view to the global second eigenvector. Because the solution involves solving a symmetric diagonally dominant (SDD) linear system, it can be computed in nearly-linear time using modern solvers.
Geometric Interpretation
The locality constraint can be visualized geometrically. In the high-dimensional space of potential solution vectors, the constraint defines a "spherical cap" centered around the seed vector $s$. The optimal solution must lie within this cap, ensuring that the resulting vector remains "near" the user's area of interest while still minimizing the Laplacian objective.
Key Insights and Results
This axiomatic foundation puts local graph exploration on the same firm theoretical footing as global spectral partitioning. Key contributions include:
- The "Negative Teleportation" Insight: In standard PPR, the "teleportation" parameter is always positive. This paper shows that by allowing the parameter $\gamma$ to approach the second eigenvalue ($\lambda_2$), one can find much larger, well-balanced clusters that standard PPR usually misses.
- Local Cheeger Inequality: The authors prove a theoretical guarantee showing that the conductance of the cut found by their method is quadratically related to the optimal local cut, mirroring the famous global Cheeger Inequality.
- Empirical Success: The method was evaluated on image data for semi-supervised segmentation and on Newman’s Coauthorship Network. On the latter, the method successfully distinguished between "core" nodes (integrated into the main network) and "periphery" nodes (part of small, "whisker" clusters), finding meaningful communities in both cases by simply tuning the teleportation parameter.
Conclusion and Limitations
While LocalSpectral provides a powerful tool for local graph analysis, it does rely on careful parameter selection (specifically $\gamma$ and the size factor $c$). Furthermore, the current framework is designed for undirected graphs; extending this axiomatic approach to directed graphs remains a challenge for future work. Nonetheless, by providing a first-principles derivation of local methods, this work offers a robust primitive for identifying and refining clusters in a semi-supervised manner.
Summary updated