Graph clustering: families, coverage, and design

[Becheler]

Story

DmitriBogdanov listed community detection as the main reason his team did not adopt BGL:

"Lack of community detection / clustering is a big thing so its good to see it addressed in current priorities. SBM would be particularly great to see (especially the weighted version) as currently there doesn't seem to be any implementations in C++."

He also provided the clearest taxonomy of the problem space:

"In community finding there are generally 3 main approaches: spectral (k-means, recursive bisection), agglomerative (Louvain, Leiden and all the other partition -> aggregate schemes) and inference-based (SBM, WSBM and multiple others). They all have different quirks and trade-offs so the seemingly sensible choice would be to implement 1-2 solid classics from every approach."

Louvain just merged. Leiden is the natural next step in the agglomerative family. SBM is the gap nobody else fills. Spectral methods are the third family and raise a hard design question: they require an eigensolver, which is a full external library dependency. BGL cannot pick one unilaterally: but the backend could be injectable (maybe with a sensible default), following the same pattern as quality functions in Louvain.

Dream solution

• BGL covers all three families with at least one solid implementation each.
• A unified output interface (community membership property map) works across all algorithms.
• The spectral backend is injectable so users can bring Eigen, ARPACK, Spectra, or cuSOLVER.

Starting point

DmitriBogdanov's comment in discussion #466
Louvain merged PR #453
Leiden paper, Traag et al. 2019
Karrer & Newman 2011, Stochastic Block Models
Von Luxburg 2007, A Tutorial on Spectral Clustering
Spectra, header-only C++ eigensolver, MPL2

Intermediary objective (45 min)

1. For each family (agglomerative, inference-based, spectral) what is the single most useful algorithm to implement first and why?
2. What should the output interface look like so that all three families return results in a compatible way?
3. For spectral clustering specifically: what does an injectable eigensolver backend need to provide? What are the candidate libraries and what are their license and dependency tradeoffs?
4. Are there any conflicts or overlaps between the three families' APIs that need to be resolved upfront?