Name
Title | ||
|---|---|---|
Stochastic Gradient Descent For Spectral Embedding With Implicit Orthogonality Constraint |
Abstract | ||
|---|---|---|
In this paper, we propose a scalable algorithm for spectral embedding. The latter is a standard tool for graph clustering. However, its computational bottleneck is the eigendecomposition of the graph Laplacian matrix, which prevents its application to large-scale graphs. Our contribution consists of reformulating spectral embedding so that it can be solved via stochastic optimization. The idea is to replace the orthogonality constraint with an orthogonalization matrix injected directly into the criterion. As the gradient can be computed through a Cholesky factorization, our reformulation allows us to develop an efficient algorithm based on mini-batch gradient descent. Experimental results, both on synthetic and real data, confirm the efficiency of the proposed method in term of execution speed with respect to similar existing techniques. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/icassp.2019.8683286 | 2019 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP) |
Keywords | Field | DocType |
Spectral Clustering, Stochastic Optimization, Cholesky factorization, Multilayer Graph | Laplacian matrix,Mathematical optimization,Stochastic optimization,Stochastic gradient descent,Gradient descent,Embedding,Algorithm,Eigendecomposition of a matrix,Orthogonalization,Mathematics,Cholesky decomposition | Journal |
Volume | ISSN | Citations |
abs/1812.05721 | 1520-6149 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mireille El Gheche | 1 | 14 | 6.39 |
| Giovanni Chierchia | 2 | 176 | 14.74 |
| Pascal Frossard | 3 | 3015 | 230.41 |