SubQuad: Near-Quadratic-Free Structure Inference with Distribution-Balanced Objectives in Adaptive Receptor framework

SubQuad is an end-to-end pipeline that overcomes the computational and data imbalance bottlenecks in large-scale adaptive immune repertoire analysis by integrating near-subquadratic MinHash retrieval, GPU-accelerated affinity kernels, and fairness-constrained clustering to enable scalable, bias-aware discovery of clinically relevant clonotypes.

The Gist

Imagine your immune system as a massive, bustling library inside your body. This library doesn't store books; it stores millions of unique "security guards" (called T-cells and B-cells), each with a specific ID card (a receptor sequence) designed to recognize a particular germ or cancer cell.

When scientists want to understand how your body fights a virus or a tumor, they need to compare these millions of ID cards to find patterns. But here's the problem: The library is too big, and the rules are unfair.

The Two Big Problems

1. The "Too Many to Count" Problem:
   If you have 1 million guards, and you want to check every single one against every other one to see who looks alike, you have to do about one trillion comparisons. It's like trying to introduce every person in a stadium to every other person one by one. It would take forever and crash your computer. This is the "near-quadratic" cost mentioned in the paper.

2. The "Bullies in the Library" Problem:
   In any immune library, there are a few "popular" guards that show up in huge numbers (fighting common colds, for example). There are also rare, specialized guards (fighting a specific new virus strain or a rare cancer mutation) that appear only a handful of times.
   Old computer methods are like bullies: they focus only on the popular guards because they are easier to find. They accidentally ignore the rare, specialized guards. But those rare guards are often the most important for creating new vaccines or cures! If the computer ignores them, we miss the cure.

The Solution: SubQuad

The authors created a new system called SubQuad (Short for "Sub-Quadratic," meaning it's faster than the old slow way). Think of SubQuad as a super-smart, fair librarian who uses three special tricks to organize the library.

Trick 1: The "Speedy Sketch" (MinHash)

Instead of reading every single ID card word-for-word, SubQuad first takes a quick "sketch" or a fingerprint of each guard.

• Analogy: Imagine you have a million photos. Instead of comparing every pixel, you quickly scan the photo to see if it has a "red hat" or a "blue shirt." If two photos don't have similar features, you don't bother comparing them closely.
• Result: This instantly throws away 99% of the useless comparisons, making the process super fast without losing the important matches.

Trick 2: The "Smart Translator" (Multimodal Fusion)

Once the librarian finds a few promising matches, she doesn't just look at the ID card text. She uses a "translator" that understands biology.

• Analogy: Imagine two people speaking different languages. A simple translator might just swap words. But SubQuad's translator understands context. It knows that even if two guards look slightly different on paper, they might be fighting the same enemy because of their shape or chemical structure.
• Result: It combines different types of clues (text, shape, chemical structure) to make a much smarter decision about which guards belong together.

Trick 3: The "Fairness Rule" (Equity-Constrained Clustering)

This is the most important part. When the librarian groups the guards into teams (clusters), she has a strict rule: No group can be formed without including the rare specialists.

• Analogy: Imagine organizing a school dance. A normal algorithm might put all the popular kids in one huge group and leave the shy kids alone. SubQuad acts like a strict teacher who says, "Every table must have at least one kid from every grade, even if that grade only has two students."
• Result: The rare, life-saving guards are guaranteed a seat at the table. This ensures that when scientists look for vaccine targets, they don't miss the rare ones that could save lives.

Why Does This Matter?

Before SubQuad, scientists had to choose between speed (ignoring rare guards) or accuracy (taking forever to check everyone).

SubQuad gives them both. It runs fast enough to handle millions of guards on a single computer, but it's smart enough to ensure that the rare, critical guards aren't left behind.

In short: SubQuad is a high-speed, fair-sorting machine that helps doctors find the "needles in the haystack" (rare immune responses) much faster, leading to better vaccines and cancer treatments. It turns a chaotic, impossible math problem into a clean, organized, and fair solution.

Technical Summary

1. Problem Statement

The paper addresses two critical bottlenecks in the comparative analysis of large-scale adaptive immune repertoires (T-cell and B-cell receptors):

• Computational Scalability: Traditional pairwise affinity evaluations grow quadratically ($O(n^2)$) with the number of sequences. Modern datasets containing $10^6$ to $10^7$ sequences per donor make exhaustive comparison computationally infeasible.
• Data Imbalance and Fairness: Immune repertoires are highly imbalanced, dominated by abundant clonotypes while rare, antigen-specific clonotypes (e.g., those reacting to rare viral variants or tumor neoantigens) occur at very low frequencies. Standard clustering and retrieval methods often optimize for aggregate speed or dominant patterns, systematically omitting these clinically critical minority groups, which biases downstream tasks like vaccine design and biomarker discovery.

2. Methodology: The SubQuad Framework

SubQuad is an end-to-end pipeline designed to achieve near-subquadratic retrieval while preserving the representation of rare subgroups. It integrates system-level efficiency with biological fidelity through three core components:

A. Antigen-Aware Near-Subquadratic Retrieval

• MinHash Prefiltering: The system employs compact MinHash sketches to generate a sparse candidate list, drastically reducing the number of pairwise comparisons required.
• Antigen-Aligned Blocking: Unlike generic string hashing, SubQuad integrates antigen-aware alignment with block-aligned storage. This organizes MinHash signatures into contiguous blocks based on antigen specificity, reducing random I/O operations by 42% and achieving a 58% storage reduction for repositories of size $10^6$.
• GPU Acceleration: The pipeline utilizes GPU-optimized parallel kernels for low-level similarity computations, leveraging a two-dimensional grid organization to handle large-scale memory hierarchies efficiently.

B. Dual-Phase Meta-Learning Encoder & Multimodal Fusion

• Representation Learning: The backbone uses a dual-phase approach:
  1. Pretraining: Unsupervised reconstruction using an ImmunoBERT-style encoder.
  2. Fine-tuning: Joint optimization with a lightweight meta-network (MetaNet) and downstream task heads.
• Adaptive Gating: A differentiable gating module dynamically weights complementary signals on a per-pair basis. It fuses:
  • Alignment-based signals (sequence similarity).
  • Protein-language embeddings (semantic structure).
  • Local graph features (topological context).
• Dynamic Affinity Fusion: For each candidate pair, a scoring network computes soft weights to fuse multi-channel affinities, capturing both fine-grained edits and higher-level biochemical structures.

C. Fairness-Constrained Clustering & Automated Calibration

• Equity-Aware Objective: The clustering objective minimizes within-cluster variance while maximizing subgroup equity. It employs a Jensen-Shannon (JS) Divergence term to penalize deviations from proportional representation.
  • Innovation: The paper notes that standard JS divergence may fail for extremely long-tailed distributions. To address this, they propose a Weighted Coverage Divergence (WCD) constraint (Theorem D.2) that explicitly enforces a lower bound on the coverage of rare subgroups, ensuring they are not discarded as noise.
• Automated Fairness Tuner: An automated routine (using grid search or binary search) dynamically calibrates the fairness weight ($\lambda$) to meet a target disparity threshold ($\delta_{max}$) without manual intervention.

3. Key Contributions

1. SubQuad Framework: The first end-to-end pipeline coupling high-efficiency sequence retrieval with antigenic sensitivity, enabling the construction of large-scale immune repertoire graphs without quadratic costs.
2. Dual-Phase Meta-Learning: A novel encoder architecture that dynamically integrates alignment-based and embedding-based affinities via a learnable gating controller, supporting robust clonotype-to-phenotype modeling.
3. Fairness-Constrained Clustering: The formulation of an explicit equity-constrained objective combined with an automated calibration routine. This ensures rare but clinically significant antigen-specific subgroups are preserved, addressing a critical gap in current immunoinformatics tools.
4. Theoretical Guarantees: The paper provides theoretical proofs (Theorems D.1 and D.2) regarding the limitations of standard JS divergence in long-tailed distributions and the convergence guarantees of the proposed WCD constraint and meta-learning calibrator.

4. Experimental Results

The system was evaluated on viral (SARS-CoV-2, CMV, EBV), tumor (NEPdb), and autoimmune datasets, including scales up to 10 million sequences.

• Performance & Efficiency:
  • Throughput: Achieved 97.2 k sequences/second on 10k sequences, significantly outperforming baselines like BertTCR (84.5) and GIANA (45.7).
  • Memory: Reduced peak memory usage to 1.4 GB (vs. 2.1–3.8 GB for competitors).
  • Scalability: Processed 1 million sequences in under 40 minutes on a single node; 10 million sequences in 6.3 hours.
• Biological Fidelity:
  • Recall: Maintained high recall (Recall@100 $\ge$ 0.96) even at the 1M sequence scale.
  • Purity: Achieved 92% cluster purity, a 16% improvement over fairness-excluded variants.
  • Fairness: Reduced subgroup representation bias (JS Disparity) to ~12% in tumor neoantigen settings (vs. >20% without fairness constraints).
• Ablation Studies: Confirmed that GPU parallelism drives throughput gains (~67%), while equity-aware objectives are critical for maintaining cluster purity and recovering rare variants.

5. Significance

• Translational Impact: SubQuad provides a scalable, bias-aware platform for vaccine target prioritization and biomarker discovery. By ensuring rare clonotypes are not overlooked, it prevents "blind spots" in therapy design.
• Biological Validity: The framework aligns computational objectives with biological realities, acknowledging that the immune system relies on diversity. It ensures that low-frequency but high-impact clones (e.g., against rare pathogens) are preserved in analysis.
• Clinical Integration: The system includes interactive visual analytics (UMAP, topological maps, disparity heatmaps) designed for clinician interpretation, facilitating wet-lab validation and accelerating decision cycles in multicenter studies.

In summary, SubQuad represents a paradigm shift in immunoinformatics, moving from purely speed-optimized, generic string matching to a biologically grounded, fairness-aware, and hardware-accelerated framework capable of handling the complexity and scale of modern immune repertoire data.