There is a possible sign flip in the eigensolver that makes spectral_embedding and therefore SpectralEmbedding not deterministic.
I think we should fix that using a similar method to sklearn.utils.extmath.svd_flip