sheaf

Sheaf and hierarchy algorithms.

sheaf includes clustering, community detection, hierarchy reconciliation, and conformal intervals for tree-structured predictions.

Problem

Use it for clustering points, detecting graph communities, and making tree-structured predictions sum to their parents.

Examples

See examples/README.md for the full runnable example map.

Embeddings to communities. Build a kNN graph from 2D points and detect clusters with connectivity-refined Louvain:

cargo run --example embedding_clustering --features knn-graph

Forecast reconciliation. Given a tree of predictions, reconcile the point forecasts to the hierarchy, then produce marginal conformal intervals:

cargo run --example forecast_reconciliation

The clustering-evaluation metrics check whether two point sets share the same cluster structure: for example, whether a generated set of earthquake locations forms the same geographic clusters as the USGS catalog.

What it provides

• Clustering: k-means, DBSCAN, hierarchical clustering.
• Community detection: kNN graph construction (feature-gated), Louvain with or without connectivity refinement, and label propagation.
• Hierarchy + conformal: hierarchical point-forecast reconciliation and split conformal intervals.
• Metrics: clustering evaluation helpers.

Custom distance metrics

K-means and DBSCAN accept a pluggable distance metric via with_metric. Built-in metrics re-exported from clump: Euclidean, SquaredEuclidean, CosineDistance, InnerProductDistance. Implement DistanceMetric for your own.

use sheaf::{Kmeans, CosineDistance};

let data = vec![vec![1.0, 0.0], vec![0.9, 0.1], vec![0.0, 1.0]];
let km = Kmeans::with_metric(2, CosineDistance)
    .with_seed(42)
    .with_seeding_alpha(2.0); // oversampling factor for k-means++
let labels = km.fit(&data)?;

use sheaf::cluster::{Dbscan, CosineDistance};

// epsilon is compared against cosine distance (range [0, 2])
let db = Dbscan::with_metric(0.3, 5, CosineDistance);
let labels = db.fit(&data);

Usage

[dependencies]
sheaf = "0.1"

use sheaf::{HierarchicalConformal, HierarchyTree, ReconciliationMethod};

// Build hierarchy, get summing matrix
let h_tree = HierarchyTree::from_raptor(&tree);
let s = h_tree.summing_matrix();

// Calibrate on held-out data
let mut cp = HierarchicalConformal::new(s, ReconciliationMethod::Ols);
cp.calibrate(&y_calib, &y_hat_calib, 0.1)?; // 90% coverage

// Marginal prediction intervals around reconciled forecasts
let (lower, upper) = cp.predict_intervals(&y_hat_test)?;

References

• Principato et al. (2024). "Conformal Prediction for Hierarchical Data."
• Qiu & Li (2015). "IT-Dendrogram: A new representation for hierarchical clustering."
• Sarthi et al. (2024). "RAPTOR: Recursive Abstractive Processing for Tree-Organized Retrieval."

License

MIT OR Apache-2.0