Spectral clustering methods

[Becheler]

The Structural BIoinformatics Library uses Boost Graph extensively to represent covalent structure in biomolecules. A few notes:

• The SBL is quite template-heavy and so they appreciate the BGL genericity.
• The tend to use undirected graphs more than directed graphs
• They don't suffer from scalability because proteins never have much more than 10K amino-acids.

A wish-list has been kindly communicated by Frederic Cazals :

1. Integrate classical spectral clustering algorithms (see Ulrike von Luxburg, 2008 )
2. Integrate algorithms for spectral decomposition of a graph's Laplacian, ideally with an interative version like Lanczos (see e.g. SLEPc)
3. some modernization around union find and disjoint sets. From what I understand, the current API is not practical and not competitive against:

• NetworkX (python) UnionFind() auto-initialization
• igraph igraph_union_find_init() internal management.
• So maybe a commodity wrapper is lacking?

Concerning points 1 and 2: if there is interest for spectral clustering, a challenge could be to properly disentangle linear algebra from graphs to keep BGL focused.

[jeremy-murphy]

I'm happy to take the union-find issue, so I'll split it off as a separate task.

[jeremy-murphy]

Boost has an old linear algebra library and a new one, but then there's the industry standard, Eigen. I don't think we want to touch the old one anymore but I'm not sure if the new one covers everything. Ultimately, I think we'll want to give users a choice through compile-time options, however I guess that means we'll want to write a thin wrapper layer just to keep those compile-time shenanigans out of the main logic.

[maniospas]

Hello!
I think this is related, so I am not opening a separate issue, but I have experience with personalized node scoring methods (have previously created a python library for these) that basically skew iterative score propagation schemas towards a personalization vector of example nodes. This helps detect overlapping structural communities (of low conductance) given some example members in a similar setting described above.

If only moderate C++ experience is not an issue, I would be happy to contribute a couple of such methods. The current page_rank implementation could be used as reference, though I would need some collaboration on making technical choices that align well with BGL's codebase.

[Becheler]

Hi @maniospas, thanks for the offer!

Personalized score propagation sounds valuable!

Moderate C++ experience is not an issue, but there are few things to think about:

1. take the personalization as a ReadablePropertyMap over vertices (not a std::vector),
2. template on the scalar type rather than hardcoding double
3. start with a single well-tested algorithm (personalized PageRank is probably the right first one).
4. dont waste time drafting a pure html documentation, we are ditching .html for .adoc in Doc migration #491

The existing page_rank implementation is a good reference for conventions. Feel free to ping me on this thread or elsewhere if you need any help getting started. It may be a good idea to open an issue or discussion (see #484 ) with the exact method you're trying to implement and to present your intended function interface, tests etc before submitting a PR: that way we can collaborate on it if you feel overwhelmed ❤️

Don't worry about the C++. The patterns are learnable from the existing algorithms (it's not completely trivial but still doable)

[Becheler]

PS: very cool python project ! 👏🏽

[Becheler]

I converted this issue to a discussion because too broad. Overlaps with #484