Module cut_aware_hnsw 

Cut-Aware HNSW: Dynamic Min-Cut Integration with Vector Search

This module bridges dynamic minimum cut tracking with HNSW vector search, enabling coherence-aware navigation that respects graph boundaries.

Overview

Traditional HNSW blindly follows similarity edges during search. This module adds “coherence gates” - weak cuts in the graph that represent semantic boundaries. When searching, we can optionally halt expansion at these boundaries to stay within coherent regions.

Key Concepts

• Cut Value: The total weight of edges crossing a partition
• Coherence Boundary: A weak cut indicating semantic separation
• Gated Search: Search that respects coherence boundaries
• Coherence Zone: A region of the graph with strong internal connections

References

• Stoer-Wagner algorithm for global min-cut
• Euler Tour Trees for dynamic connectivity
• HNSW for approximate nearest neighbor search

Structs

CoherenceZone

A coherent region in the graph

CutAwareConfig

Configuration for cut-aware HNSW

CutAwareHNSW

Extended HNSW that respects coherence boundaries

CutAwareMetrics

Performance metrics for cut-aware operations

DynamicCutWatcher

Dynamic cut watcher using incremental min-cut updates

EdgeUpdate

Edge update operation

LayerCutStats

Cut statistics per layer

SearchResult

Search result with coherence information

UpdateStats

Statistics from batch update

Enums

UpdateKind

Type of edge update