The linter is breaking because you need to run black on the file:

• sklearn/cluster/_spectral.py
• sklearn/cluster/tests/test_spectral.py

Another way would be to install pre-commit that will run black for you before committing and ensure that you don't forget to do it.

Here are some concerns that have been already raised in the past:

• the method does not fulfil the inclusion criterion
• there is currently no unit tests for the function itself
• we would need to investigate more on a variety of typical spectral clustering problems to see the benefit in terms of various types of performance: time, memory, statistical score

While the two last points need to be fulfilled, I think that we have now scikit-learn-extra that could allow us to bypass the first point. In this case, we could accept a generic callable to cluster the map using any function. However, even in scikit-learn-extra, points 2 and 3 need to be fulfilled.

@rth do you have any thought regarding the inclusion in scikit-learn-extra once the function is properly tested and we investigated the performance?

The linter is breaking because you need to run black on the file:

• sklearn/cluster/_spectral.py
• sklearn/cluster/tests/test_spectral.py

Another way would be to install pre-commit that will run black for you before committing and ensure that you don't forget to do it.

If there is no way around it, this looks like a bug in CI framework - breaking the ability of purely web-based PR submission and maintenance, which was available prior to requiring this black check. @glemaitre Let's move this topic to #21169 that I have just created.

Here are some concerns that have been already raised in the past:

• the method does not fulfil the inclusion criterion

@glemaitre @jnothman @ogrisel The original PR was 3 years ago. Since then, the papers that use the clusterQR (I renamed into cluster_qr) have been cited maybe hundred times. The original original report and the paper alone are cited 25 times https://scholar.google.com/citations?view_op=view_citation&hl=en&user=Kv-Y1qYAAAAJ&citation_for_view=Kv-Y1qYAAAAJ:_FxGoFyzp5QC ; see also
https://www.google.com/search?q=%22Robust+and+efficient+multi-way+spectral+clustering%22

Our own implementation https://doi.org/10.1109/HPEC.2017.8091045 has won MIT/AWS Graph Challenge 2017 Student Innovation Awards https://graphchallenge.mit.edu/champions. 3 years later, it remains a canonical approach, answering @jnothman, most recently implemented and tested in https://ieeexplore.ieee.org/document/9286181 that has won MIT/AWS Graph Challenge 2020 Innovation Award, https://graphchallenge.mit.edu/champions.

What else needs to happed to fulfil the inclusion criterion?

do you have any thought regarding the inclusion in scikit-learn-extra

Happy to include it there, but it looks like it might be hard to integrate while leaving all the rest of spectral_clustering code in scikit-learn. Or at least that would require supporting spectral_clustering(assign_labels=..) as a callable for instance.

Our own implementation [..] it remains a canonical approach

What else needs to happen to fulfill the inclusion criterion?

For context, I think historically there is some reluctance to include algorithms proposed by their authors in scikit-learn because there can be a conflict of interest between including some feature in the best interest of users and increased paper citations as a result of it.

I'm not saying it's an issue here, and the code certainly look straightforward and short. However, IMO the most compelling argument is still, #21148 (comment)

we would need to investigate more on a variety of typical spectral clustering problems to see the benefit in terms of various types of performance: time, memory, statistical score

as in how this would impact the average user.

For context, I think historically there is some reluctance to include algorithms proposed by their authors in scikit-learn because there can be a conflict of interest between including some feature in the best interest of users and increased paper citations as a result of it.

@rth to clarify, I am not an author of the algorithm, but a happy user. In contrast to kmeans, it actually works, which one can observe, e.g., in the included example #12164 (comment)

The authors just provided the MATLAB implementation https://github.com/asdamle/QR-spectral-clustering, The algorithm is so simple that turning it from MATLAB into Python is trivial - getting it into sklearn has turned out to be not :-)

The authors have provided convincing examples in their paper, using their MATLAB code, but I agree that

we would need to investigate more on a variety of typical spectral clustering problems to see the benefit in terms of various types of performance: time, memory, statistical score

so someone will need to write a good benchmark for the present codes. My feeling is that cluster_qr would well outperform the competitors in terms of quality, yet being faster, and probably with a smaller memory footprint.

For benchmarking, we can follow the example of https://github.com/glemaitre/bench_lobpcg/blob/master/bench_lobpbcg.py and for the data use examples from the stochastic block model http://graphchallenge.mit.edu/data-sets
Low Block Overlap and Low Block Size Variation    | Low level of overlap and low level of size variation between blocks (easiest)
Static Graphs | 1K | 5K | 20K | 50K | 200K | 1M

Please let me know if there are alternative suggestions. If not, someone would probably need to download the files. We could alternatively generate the data on the fly. Please advise and let me know the preference.

Here is a first superficial review.

Even though I still need to get in the details of the paper and of the implementation of cluster_qr, to me this looks like an relevant labeling method. 👍

@jjerphan thanks for your first review! I've made all the requested changes. Please let me know if I need to do anything else.

Hi @lobpcg,

I am busy with more urgent tasks but will come back to you when possible.
Feel free to ping me here via mentions or by requesting another request if I am not replying.

@jjerphan all proposed changes finally made (sorry for missing your earlier suggestions). All green, should be ready to merge?

@ogrisel @jjerphan thanks for reviewing! What should I do next for this PR to be merged?

@lobpcg if all the reviews have been addressed then this PR should be merged. I don't want to start a new review so only pinging @ogrisel to be sure that his +1 is still standing (which should be) and he will merge this PR.

I would also wait for his approval regarding your latest changes.

@ogrisel could you please have a look, hopefully final?
I want to start another PR and need to clean/delete my old sklearn repo fork before that as far as I can see, so this PR is a blocker for me.

Merged, thank you very much for the contrib!

I am glad to see this long journey finally completed. Thanks very much everyone involved!