TriMap is a fast dimensionality reduction method that uses triplet constraints to preserve both local and global structure. For each point, it creates triplets of (anchor, similar point, dissimilar point) and optimizes the embedding so that similar points stay closer than dissimilar ones.
Best for:
- Large datasets where speed matters
- When you want both local and global structure
- As a faster alternative to t-SNE
- General-purpose visualization
Avoid when:
- You need the best possible quality (use t-SNE/UMAP)
- Very small datasets (overhead not worth it)
- You need deterministic results without setting random_state
TriMap asks: "For each point A, should point B be closer than point C?" It creates many such triplet comparisons and optimizes coordinates so these relationships hold. By mixing nearby neighbors (local structure) with random far points (global structure), it preserves both scales.
A single triplet constraint looks like this:
graph LR
i((i)) -- "near" --> j((j))
i((i)) -- "far" --> k((k))
TriMap samples lots of these constraints and optimizes an embedding that satisfies them:
flowchart TD
X["Input points X"] --> N["Find nearest neighbors"]
N --> T["Sample triplets (i, j, k)<br/>j near i; k far from i"]
T --> W["Assign weights (harder triplets matter more)"]
W --> Y0["Initialize embedding Y"]
Y0 --> OPT["Optimize triplet objective"]
OPT --> Y["Output embedding"]
Local/global balance (conceptually):
flowchart LR
L["More inliers (n_inliers)"] --> L2["Sharper local neighborhoods"]
G["More outliers/random (n_outliers, n_random)"] --> G2["Stronger global scaffold"]
- Find nearest neighbors: k-NN for each point
- Generate triplets:
- Inlier triplets: (anchor, near neighbor, far neighbor)
- Outlier triplets: (anchor, near neighbor, random far point)
- Random triplets: (anchor, random point 1, random point 2)
- Compute weights: Based on distance margins
- Optimize: Gradient descent to satisfy triplet constraints
Triplet loss: For triplet (i, j, k) where j should be closer to i than k:
L = Σ wᵢⱼₖ · loss(||yᵢ - yⱼ||, ||yᵢ - yₖ||)
where loss penalizes when ||yᵢ - yⱼ|| > ||yᵢ - yₖ||
Complexity: O(n × (n_inliers + n_outliers + n_random) × n_iter)
- Type: int
- Default: 2
- Description: Output dimensions
- Recommendations: 2-3 for visualization
- Type: int
- Default: 12
- Description: Number of nearest neighbors per point (similar points)
- Effect: Higher preserves more local structure
- Recommendations: 10-20 range
- Type: int
- Default: 4
- Description: Number of far neighbors per point (dissimilar points)
- Effect: Higher preserves more global structure
- Recommendations: 3-10 range
- Type: int
- Default: 3
- Description: Number of random triplets per point
- Effect: Adds global structure preservation
- Recommendations: 1-5 range
- Type: int
- Default: 800
- Description: Number of optimization iterations
- Recommendations: 400-1000
- Type: float
- Default: 0.1
- Description: Gradient descent step size
- Recommendations: 0.05-0.5 range
- Type: float
- Default: 50.0
- Description: Weight adjustment for triplet importance
- Effect: Higher emphasizes hard triplets
- Recommendations: Default usually works
- Type: int or None
- Default: None
- Description: Random seed for reproducibility
import squeeze
from sklearn.datasets import load_digits
# Load data
digits = load_digits()
X = digits.data
# Apply TriMap
trimap = squeeze.TriMap(n_components=2, n_inliers=12, n_outliers=4, random_state=42)
X_embedded = trimap.fit_transform(X)
# Visualize
import matplotlib.pyplot as plt
plt.scatter(X_embedded[:, 0], X_embedded[:, 1], c=digits.target, cmap='tab10', s=5)
plt.title('TriMap Embedding')
plt.show()import squeeze
import matplotlib.pyplot as plt
fig, axes = plt.subplots(1, 3, figsize=(15, 5))
configs = [
{'n_inliers': 20, 'n_outliers': 2, 'title': 'More Local (20 inliers, 2 outliers)'},
{'n_inliers': 12, 'n_outliers': 4, 'title': 'Balanced (12 inliers, 4 outliers)'},
{'n_inliers': 5, 'n_outliers': 10, 'title': 'More Global (5 inliers, 10 outliers)'},
]
for ax, config in zip(axes, configs):
trimap = squeeze.TriMap(
n_inliers=config['n_inliers'],
n_outliers=config['n_outliers'],
random_state=42
)
X_emb = trimap.fit_transform(X)
ax.scatter(X_emb[:, 0], X_emb[:, 1], c=y, s=5, cmap='tab10')
ax.set_title(config['title'])import squeeze
import numpy as np
# Large dataset
X_large = np.random.randn(50000, 100)
# TriMap handles this efficiently
trimap = squeeze.TriMap(n_components=2, n_iter=500)
X_embedded = trimap.fit_transform(X_large) # Much faster than t-SNE| Metric | Value |
|---|---|
| Time Complexity | O(n × triplets × iterations) |
| Memory | O(n × triplets) |
| Scalability | Good (handles 100k+ points) |
| Benchmark (Digits) | 0.30s |
| Trustworthiness | 0.500 |
- Fast, scales to large datasets
- Preserves both local and global structure
- Simple, interpretable triplet constraints
- Good for quick exploration
- Lower quality than t-SNE/UMAP on small datasets
- Triplet sampling introduces variance
- Results depend on random triplet selection
- May not separate clusters as cleanly
| Method | Speed | Quality | Global Structure |
|---|---|---|---|
| TriMap | Fast | Good | Good |
| PaCMAP | Fast | Better | Good |
| UMAP | Medium | Best | Good |
| t-SNE | Slow | Best | Poor |
- Start with defaults: The default parameters work well for most data
- Increase n_inliers if local structure is most important
- Increase n_outliers if global structure is most important
- Set random_state for reproducible results
- Consider PaCMAP which often gives better results at similar speed
@article{amid2019trimap,
title={TriMap: Large-scale Dimensionality Reduction Using Triplets},
author={Amid, Ehsan and Warmuth, Manfred K},
journal={arXiv preprint arXiv:1910.00204},
year={2019}
}