---
name: sc-label-propagation
description: Annotate cell types in single-cell RNA-seq data using graph-based label propagation. Minimal dependencies, runs in seconds.
allowed-tools: Bash(python3 *), Bash(pip install *)
---

# Single-Cell Label Propagation

## Dependencies

```bash
pip install numpy scipy scanpy
```

## Quick Start

```python
from sc_label_prop import LabelPropagator
import scanpy as sc

# Load data
adata = sc.datasets.pbmc3k()

# Preprocess
sc.pp.filter_cells(adata, min_genes=200)
sc.pp.filter_genes(adata, min_cells=3)
sc.pp.normalize_total(adata, target_sum=1e4)
sc.pp.log1p(adata)
sc.pp.highly_variable_genes(adata, n_top_genes=2000)

# Create propagator
lp = LabelPropagator(n_neighbors=15, n_pcs=50)

# Provide seed labels (5 per cluster)
seed_indices = [...]  # indices of labeled cells
seed_labels = [...]   # one-hot encoded labels

# Propagate
predictions = lp.fit_predict(adata, seed_indices, seed_labels)
```

## Full Implementation

```python
import numpy as np
from scipy.sparse import csr_matrix, lil_matrix
from scipy.spatial.distance import cdist

class LabelPropagator:
    """Graph-based label propagation for scRNA-seq."""
    
    def __init__(self, n_neighbors=15, n_pcs=50, alpha=0.85, max_iter=50):
        self.n_neighbors = n_neighbors
        self.n_pcs = n_pcs
        self.alpha = alpha
        self.max_iter = max_iter
    
    def _build_knn_graph(self, X):
        """Build k-NN graph using cosine similarity."""
        n = X.shape[0]
        
        # Normalize rows
        norms = np.linalg.norm(X, axis=1, keepdims=True)
        X_norm = X / (norms + 1e-10)
        
        # Compute similarities
        sim = X_norm @ X_norm.T
        
        # Keep top k neighbors
        graph = lil_matrix((n, n))
        for i in range(n):
            top_k = np.argsort(sim[i])[-(self.n_neighbors + 1):]
            for j in top_k:
                if i != j:
                    graph[i, j] = sim[i, j]
        
        return csr_matrix(graph)
    
    def fit_predict(self, adata, seed_indices, seed_labels):
        """Propagate labels from seeds to all cells."""
        # Get PCA representation
        if 'X_pca' not in adata.obsm:
            from sklearn.decomposition import PCA
            pca = PCA(n_components=self.n_pcs)
            adata.obsm['X_pca'] = pca.fit_transform(
                adata[:, adata.var['highly_variable']].X
            )
        
        X = adata.obsm['X_pca']
        n = X.shape[0]
        n_classes = seed_labels.shape[1]
        
        # Build graph
        A = self._build_knn_graph(X)
        
        # Create seed label matrix
        Y = np.zeros((n, n_classes))
        for idx, label in zip(seed_indices, seed_labels):
            Y[idx] = label
        
        # Normalize Y for seeds
        Y[seed_indices] = seed_labels
        
        # Row-normalize adjacency
        row_sums = np.array(A.sum(axis=1)).flatten()
        row_sums[row_sums == 0] = 1
        D_inv = csr_matrix(np.diag(1 / row_sums))
        A_norm = D_inv @ A
        
        # Propagate
        p = Y.copy()
        for iteration in range(self.max_iter):
            p_new = self.alpha * (A_norm @ p) + (1 - self.alpha) * Y
            if np.abs(p_new - p).max() < 1e-6:
                break
            p = p_new
        
        # Get predictions
        predictions = np.argmax(p, axis=1)
        return predictions

# Demo on synthetic data
if __name__ == '__main__':
    np.random.seed(42)
    
    # Generate synthetic clusters
    n_cells = 500
    n_genes = 1000
    n_clusters = 5
    
    # Create cluster centers
    centers = np.random.randn(n_clusters, n_genes) * 2
    
    # Generate cells
    cells = []
    labels_true = []
    for i in range(n_cells):
        cluster = i * n_clusters // n_cells
        cell = centers[cluster] + np.random.randn(n_genes) * 0.5
        cells.append(cell)
        labels_true.append(cluster)
    
    X = np.array(cells)
    
    # Select 5 seeds per cluster
    seed_indices = []
    seed_labels_onehot = []
    for c in range(n_clusters):
        cluster_cells = [i for i, l in enumerate(labels_true) if l == c]
        seeds = np.random.choice(cluster_cells, 5, replace=False)
        for s in seeds:
            seed_indices.append(s)
            onehot = np.zeros(n_clusters)
            onehot[c] = 1
            seed_labels_onehot.append(onehot)
    
    seed_labels_onehot = np.array(seed_labels_onehot)
    
    # Create simple AnnData-like object
    class SimpleAnnData:
        def __init__(self, X):
            self.X = X
            self.var = {'highly_variable': np.ones(X.shape[1], dtype=bool)}
            self.obsm = {}
    
    adata = SimpleAnnData(X)
    
    # Run label propagation
    lp = LabelPropagator(n_neighbors=10, n_pcs=20)
    predictions = lp.fit_predict(adata, np.array(seed_indices), seed_labels_onehot)
    
    # Evaluate
    correct = sum(p == t for p, t in zip(predictions, labels_true))
    accuracy = correct / len(labels_true)
    print(f"Accuracy: {accuracy:.2%}")
```

## Verification

```bash
python3 sc_label_prop.py
# Expected output: Accuracy > 90%
```