Spectral Embedding with Asymmetric Matrices/ Directed Graphs

[asaadeldin11]

Describe the workflow you want to enable

Currently, the sklearn.manifold.SpectralEmbedding is restricted to symmetric affinity matrices, and if an asymmetric matrix is passed it is converted through sklearn.utils.validation.check_symmetric into a symmetric matrix. However, in doing so, one loses the underlying asymmetries and potential directional clusters present in the adjacency matrix of the directed graph input.

Describe your proposed solution

The algorithms I propose adding use singular value decomposition, as opposed to eignendecomposition, and a modified Laplacian to perform spectral embedding on directed graphs/asymmetric matrices. Specifically I would like to propose adding Adjacency / Laplacian spectral embedding, ASE and LSE respectively. My thoughts would be to add a new class,sklearn.manifold.DirectedSpectralEmbedding, which users may call directly, or is dispatched to when an asymmetric matrix is passed to sklearn.manifold.SpectralEmbedding. Similarly to SpectralEmbedding, users would specify between ASE and LSE through an affinity parameter.

Additional context

These algorithms have been implemented in GraSPy, (available at ASE and LSE), inputing a graph represented as a dense or sparse matrix, and returning the appropriate embedding.