So this is 100x faster? That's nice :)

Not sure if we want to require amg to build docs. How does the output compare?

Not sure if we want to require amg to build docs. How does the output compare?

If we non't include pyamg inside build_docs.sh, the circleCI will fail.

"How does the output compare?" was a separate question about whether the example is materially the same with a different solver

when the assign_label in sklearn.cluster.SpectralClustering is "kmeans", the graphs look the same. But when the assign_label is "discretize". The graphs look different.
The new graphs:

The old graphs:

The documentation does not much explain how discretize works, and I've not looked into it... But these certainly seem to be very different results. Why?

In the document https://scikit-learn.org/stable/modules/generated/sklearn.cluster.spectral_clustering.html, it says that using amg eigen solver may lead to instabilities.

The documentation does not much explain how discretize works, and I've not looked into it... But these certainly seem to be very different results. Why?

Both implemented methods k-means and discretize are imperfect, and expected to give very different results. #12316 implements an alternative method for choosing the clusters from the eigenvectors, outperforming both k-means and discretize.

The documentation does not much explain how discretize works, and I've not looked into it... But these certainly seem to be very different results. Why?

In the document https://scikit-learn.org/stable/modules/generated/sklearn.cluster.spectral_clustering.html, it says that using amg eigen solver may lead to instabilities.

1. Instabilities in AMG simply make the code crash.
2. Fix for spectral clustering error when using 'amg' solver #13707 fixes AMG instability for spectral clustering

#13707 resolves the instability problem of AMG preconditioning and is now merged in master. Indeed this does not change anything for the current PR (it's unrelated).

I tested this PR with the latest scikit-learn version and unable to get a clustering that looks like the original. I prefer the slower solver since it gives more stable results compared to a faster solver that does not. I think we likely need a different approach to speeding up this example. With that in mind, I am closing this PR.