Updated the change log. Let me know if anything else is needed.

Don't understand the codecov/patch failure, all local tests are passing for me. What does this failure mean?

@jnothman This seems pretty clean now, everything is passing.

I think that the mathematically proper fix is changing in sklearn/manifold/spectral_embedding_.py the present

        laplacian = _set_diag(laplacian, 1 + 1e-5, norm_laplacian)

        # noinspection PyUnboundLocalVariable
        ml = smoothed_aggregation_solver(check_array(laplacian, 'csr'))

into

        laplacian = _set_diag(laplacian, 1, norm_laplacian)

        # noinspection PyUnboundLocalVariable
        ml = smoothed_aggregation_solver(check_array(laplacian + 1e-5 * sparse.eye(laplacian.shape[0], 'csr'))

so that the LOBPCG solver is still called on the unchanged Laplacian, but only the AMG preconditioner is fed with the shifted Laplacian. I have updated my #13393 to highlight this.

I am unsure how the memory allocation would work in my suggestion above. May be to save memory one can do something like:

        laplacian = _set_diag(laplacian, 1, norm_laplacian)
        laplacian = laplacian + 1e-5 * sparse.eye(laplacian.shape[0]
        # noinspection PyUnboundLocalVariable
        ml = smoothed_aggregation_solver(check_array(laplacian, 'csr'))
        laplacian = laplacian - 1e-5 * sparse.eye(laplacian.shape[0]

@whitews are you continuing with this?

@jnothman Yes, I've updated the PR. Have the tests changed? Getting a 404 response for a deb package in the np_atlas Azure build.

Yes, bit I've been low on time to review this and other pull requests. I hope one of us can get to it soon.

@jnothman is there a plan trying to finish this one?

Please merge the master from upstream to avoid the Circle CI failure.

@jnothman I think this is ready. Are there any outstanding requests?

https://scikit-learn.org/stable/modules/generated/sklearn.cluster.spectral_clustering.html, says that using amg eigen solver may lead to instabilities. This can be now removed, I think.