scSAGA: Single-cell Sampled Gromov Wasserstein Alignment for Scalable and Memory-efficient Integration of Multi-modal Single Cell Data

scSAGA is a novel, memory-efficient, and scalable framework that leverages sampled Gromov-Wasserstein alignment to integrate large-scale multi-modal single-cell datasets while preserving geometric manifold structure and outperforming existing methods in accuracy and clustering coherence.

The Gist

Imagine you are trying to organize a massive, chaotic library where the books are written in two completely different languages. One section of the library (let's call it the "Gene Library") describes cells by listing the proteins they make. The other section (the "Chromatin Library") describes the same cells by listing which parts of their DNA are open and active.

The problem? The books in the Gene Library don't have titles that match the books in the Chromatin Library. A book about "Protein A" might be about "DNA Segment X," but there's no dictionary to tell you they are the same story. Furthermore, you have millions of these books, and trying to compare every single book to every other book would take longer than the age of the universe and require a computer the size of a city.

This is the challenge scientists face when trying to combine different types of single-cell data. Enter scSAGA, a new tool designed to solve this puzzle. Here is how it works, using simple analogies:

1. The Old Way: The "Brute Force" Map

Previous methods tried to solve this by creating a giant map of the entire library. They calculated the distance between every single book and every other book to see how similar they were.

• The Problem: If you have 100,000 books, that's 10 billion comparisons. If you have 1 million books, the math explodes. It's like trying to draw a map of every possible walking path between every house in a city of a million people. You run out of paper (memory) and time long before you finish.

2. The scSAGA Solution: The "Smart Scout" Approach

scSAGA changes the strategy. Instead of mapping the whole world at once, it uses three clever tricks:

A. The Neighborhood Map (Sparse Graphs)

Instead of measuring the distance between every house in the city, scSAGA only looks at the immediate neighbors. It builds a "neighborhood map" where you only know who lives next door.

• The Analogy: If you want to know how far it is from your house to a friend's house across town, you don't need to measure the distance to every single house in between. You just follow the path of neighbors. scSAGA only calculates these "neighbor-to-neighbor" distances when it absolutely needs to, saving massive amounts of memory.

B. The "Plan-Guided" Scout (Sampling)

When trying to match a book from the Gene Library to the Chromatin Library, scSAGA doesn't guess randomly. It uses a "scout" system.

• The Analogy: Imagine you are trying to match two huge crowds of people. Instead of asking everyone in Crowd A to introduce themselves to everyone in Crowd B, you first make a rough guess of who might be a match. Then, you only send a small team of "scouts" to verify those specific matches. If the scouts confirm a match, great! If not, you move on. This "plan-guided sampling" means the computer only does the hard math on the most promising pairs, ignoring the rest.

C. The "Ghost" Anchor (Matrix-Free Embedding)

To bring all the different libraries into one room, scSAGA picks one library as the "Anchor" (the reference point). It then pulls the other libraries toward this anchor using the matches it found.

• The Analogy: Think of the Anchor as a giant magnet in the center of a room. The other libraries are sheets of paper with dots on them. Instead of physically moving the heavy sheets and calculating the weight of every dot, scSAGA uses a "ghost" calculation. It simulates the pull of the magnet using simple math tricks (iterative linear algebra) that don't require storing the heavy, dense data. This allows it to handle millions of dots without the computer crashing.

Why Does This Matter?

Before scSAGA, scientists had to choose between accuracy (getting the matches right) and scale (being able to handle big data).

• If they wanted accuracy, they used old methods that could only handle small datasets (like a few thousand cells).
• If they wanted to handle big datasets (like a million cells), they had to use methods that were fast but often made mistakes, mixing up different cell types.

scSAGA is the first tool that does both.

• It can handle millions of cells (like a whole human organ or an entire organism).
• It keeps the geometric shape of the data intact, meaning it doesn't blur the lines between different cell types.
• It works even if the data is unpaired (meaning the cells weren't measured at the exact same time or from the exact same person).

The Result

By using scSAGA, scientists can now take a massive, messy dataset of millions of cells from a human, a mouse, a fish, or even a plant, and organize them into a clean, coherent map. This helps them identify cell types more accurately, understand diseases like Alzheimer's better, and see how different organisms develop, all without needing a supercomputer the size of a building.

In short: scSAGA is the smart, efficient librarian that can organize the world's largest, most confusing library in record time, finding the right connections between books that no one thought could be matched.

Technical Summary

1. Problem Statement

The integration of multi-modal single-cell data (e.g., scRNA-seq and scATAC-seq) is a critical computational challenge. Existing methods generally fall into two categories, both of which have significant limitations for large-scale datasets:

• Shared-Feature Alignment (e.g., Seurat, LIGER): These methods learn a joint latent space using linear or factor models. They often rely on "proxy" shared features (like gene activity scores) which can introduce modeling biases and fail to preserve the true geometric structure of the data, especially when feature spaces are disjoint (genes vs. peaks) or unpaired.
• Geometry-Based Alignment (e.g., SCOT, Pamona): These methods use Gromov–Wasserstein (GW) optimal transport to align datasets based on intra-domain distances (manifold structure) rather than raw features. While theoretically superior for preserving geometry, existing GW-based methods suffer from quadratic memory and runtime complexity ($O(N^2)$). They require precomputing and storing dense all-pairs distance matrices and optimizing over full cost matrices, making them infeasible for datasets exceeding tens of thousands of cells (often failing at ~37k cells).

The Core Gap: There is no existing framework that simultaneously preserves manifold structure (via GW) and scales to organism-wide datasets (millions of cells) without sacrificing geometric fidelity or running out of memory.

2. Methodology: scSAGA

The authors propose scSAGA (Single-Cell Sampled Gromov–Wasserstein Alignment), a framework designed to retain the geometric benefits of GW while eliminating its scalability bottlenecks. The method operates in three main phases:

A. Sparse Geometry with On-the-Fly Geodesics

Instead of precomputing dense $N \times N$ distance matrices, scSAGA represents each dataset as a sparse k-Nearest Neighbor (kNN) graph.

• Mechanism: Geodesic distances (shortest paths on the graph) are computed on-demand only when required during the optimization process.
• Benefit: This reduces memory usage from $O(N^2)$ to $O(N)$ (sparse storage), enabling the handling of massive datasets.

B. Plan-Guided Sampled GW Optimization

Standard GW optimization requires computing costs for all pairwise cell comparisons. scSAGA introduces a sampling strategy to approximate the GW objective:

• Sampling: In each iteration, the algorithm samples a small set of informative cell pairs based on the current transport plan (focusing on pairs with high probability mass).
• Cost Approximation: The GW cost matrix is assembled using only these sampled pairs and their on-the-fly geodesic distances.
• Partial GW: The method incorporates a "virtual sink" mass to handle partial population overlap and unpaired data, allowing unmatched cells to be penalized rather than forced into incorrect matches.
• Optimization: The entropically regularized problem is solved using Sinkhorn iterations, updated with a damping factor to ensure convergence.

C. Matrix-Free Joint Embedding

To create a shared low-dimensional space for all datasets:

• Approach: Instead of constructing a massive dense matrix for the entire integrated system, scSAGA uses iterative linear algebra on sparse operators.
• Mechanism: It constructs a joint embedding by solving a system that enforces two constraints: (1) local smoothness within datasets (via graph Laplacians) and (2) alignment across datasets (via the learned transport plans).
• Benefit: This "matrix-free" approach avoids dense matrix factorization, allowing the embedding to be computed via sparse matrix-vector products and iterative solvers.

3. Key Contributions

1. Scalability: scSAGA is the first geometry-preserving optimal transport framework capable of integrating millions of cells (demonstrated up to 1M+ cells) with near-linear growth in runtime and memory.
2. Memory Efficiency: By avoiding dense distance matrices and using sparse graph operations, it overcomes the "Out of Memory" (OOM) failures common in previous GW methods (SCOT, Pamona) at scales >37k cells.
3. Geometric Fidelity: Unlike shared-feature methods, scSAGA aligns modalities based on intrinsic manifold structure, making it robust to disjoint feature spaces (e.g., RNA vs. ATAC) and unpaired data.
4. Algorithmic Innovation: The combination of on-demand geodesic queries, plan-guided sampling, and matrix-free embedding creates a novel pipeline for large-scale optimal transport.

4. Results and Performance

The authors evaluated scSAGA on diverse paired and unpaired datasets (Human PBMC/BMMC, Mouse Alzheimer's brain, Zebrafish, Arabidopsis root) and compared it against Pamona, SCOTv2, Seurat v5, and LIGER.

• Accuracy & Alignment:
  • On paired Human PBMC data, scSAGA achieved the highest 1:1 matching accuracy (e.g., 0.997 at 600 cells, 0.95 at 22k cells) compared to all baselines.
  • It achieved superior Alignment Scores (neighborhood mixing), outperforming Seurat and LIGER, and matching or exceeding Pamona.
• Scalability:
  • Runtime/Memory: scSAGA scaled linearly. It processed a 1-million-cell integration in ~24,000 seconds using ~86 GB of RAM.
  • Comparison: Competitors like Pamona and SCOT failed (OOM) beyond 37k cells. Seurat failed beyond 450k cells. LIGER could scale to 1M cells but used significantly more memory (139 GB) and yielded lower alignment scores.
• Cross-Organism Generalization:
  • scSAGA successfully integrated datasets from distinct organisms (e.g., Arabidopsis, Zebrafish) where feature spaces differ drastically. It maintained high accuracy (0.86–0.97) where methods relying on shared features (Seurat) performed poorly.
• Downstream Clustering:
  • Integrated embeddings from scSAGA resulted in superior Adjusted Rand Index (ARI), Normalized Mutual Information (NMI), and Average Silhouette Width (ASW) for cell-type identification, indicating that the integration preserved biologically meaningful structures better than other methods.

5. Significance

scSAGA represents a paradigm shift in single-cell data integration. It bridges the gap between theoretical rigor (geometry-preserving optimal transport) and practical applicability (scalability to atlas-scale datasets).

• Biological Impact: It enables the construction of comprehensive, multi-modal atlases across entire organisms, facilitating the study of development, disease, and perturbation at a scale previously impossible for geometry-based methods.
• Technical Impact: It demonstrates that optimal transport does not inherently require quadratic complexity, opening the door for future scalable geometric deep learning and alignment techniques in bioinformatics.

Availability: The code is open-source at https://github.com/AluruLab/scSAGA.