Repository navigation
Spectral clustering methods #456
Description
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 :
- Integrate classical spectral clustering algorithms (see Ulrike von Luxburg, 2008 )
- Integrate algorithms for spectral decomposition of a graph's Laplacian, ideally with an interative version like Lanczos (see e.g. SLEPc)
- 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.
Reacted by Jeremy W. Murphy
Activity
jeremy-murphy commentedon Feb 15, 2026
I'm happy to take the union-find issue, so I'll split it off as a separate task.
jeremy-murphy commentedon Feb 15, 2026
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 commentedon Apr 10, 2026
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_rankimplementation could be used as reference, though I would need some collaboration on making technical choices that align well with BGL's codebase.[-][FEATURE] Spectral clustering methods[/-][+]Spectral clustering methods[/+]