Skip to content

SCC v1.2

Choose a tag to compare

View all tags
@schulzchristian schulzchristian released this 28 Mar 18:55
· 5 commits to main since this release
v1.2
80f371d

SCC v1.2 -- Scalable Correlation Clustering

Performance: 1.24x faster with identical solution quality.

Systematic performance tuning of the multilevel solver using Algorithm Engineering methodology. 30+ experiments evaluated; 18 optimizations kept. All changes are internal — no API, CLI, or output format changes. Done automatically using
https://github.com/CHSZLab/AgenticAlgorithmEngineering skill and claude.

Highlights:

  • 1.24x speedup on geometric mean across 20 benchmark instances (signed social networks and image segmentation graphs)
  • Zero quality change: bit-identical solutions for scc; better solutions for scc_evolutionary (more iterations within the same time budget)
  • Best-of-50 improvements with scc_evolutionary (100s budget): cityscape7 -268, cityscape52 -96, cityscape34 -50, wikisigned-k2 -20

What changed internally:

  • Dense vectors replacing hash maps in hot paths (label remapping, priority queue indexing)
  • Counting-sort graph contraction eliminating ~24MB intermediate allocations per level
  • Block-ID caching and sweep specialization in label propagation for degree ≤ 32 nodes
  • Pointer hoisting with __restrict__ in LP and FM refinement inner loops
  • Stack allocation of framework objects; persistent buffers across coarsening levels
  • tcmalloc_minimal linking on Linux for reduced allocator overhead

Install: brew install KaHIP/kahip/scc

Assets 2
Loading