Introduction
In fields like bioinformatics and natural language processing (NLP), models frequently process "sets" of features—such as amino acids in a protein or words in a sentence. These sets vary in length and often possess complex, long-range dependencies. The standard approach to handling them is "pooling," which collapses these features into a single vector.
However, simple pooling (like taking the mean) loses critical information. Conversely, sophisticated "set-aware" architectures like Transformers struggle with computational complexity (self-attention scales quadratically, $O(n^2)$, with sequence length), require massive datasets to learn effectively, and face challenges when handling very long biological sequences with sparse labels.
To address this, researchers introduce Optimal Transport Kernel Embedding (OTKE). By leveraging Optimal Transport (OT) to align input data with a trainable reference set, OTKE provides a scalable, theoretically grounded alternative to standard attention mechanisms that excels on long sequences and in small-data regimes.
How OTKE Works
The core of the paper is the OTKE mechanism, which acts as a highly expressive pooling layer. The process works in three main steps:
- The Reference Set: The model maintains a "reference set" of trainable vectors, which act as prototypes or bins.
- Optimal Transport Alignment: Instead of comparing every input element to every other input element (as in self-attention), the model computes the Optimal Transport plan between the input set and the reference set. This plan determines how to best distribute the mass of the input features onto the reference prototypes with minimal cost.
- Weighted Pooling: The input features are then aggregated into buckets corresponding to the reference elements, weighted by the OT plan.
To make this process efficient and differentiable, the authors introduce several key innovations:
- Sinkhorn Iterations: To make OT differentiable and fast, the authors use the Sinkhorn algorithm, allowing the reference set to be trained end-to-end via backpropagation.
- Nyström Approximation: To handle high-dimensional kernel spaces efficiently, they use Nyström approximation, providing a finite-dimensional embedding that remains computationally tractable.
- Positional Integration: They introduce a way to penalize similarities based on the physical distance between elements, effectively "baking in" positional information similar to relative positional encoding in Transformers.
Key Insights: OT as "Linearized" Attention
One of the most striking insights from the paper is the relationship between OTKE and standard Attention. While self-attention requires $O(n^2)$ operations, OTKE operates in $O(np)$ time, where $p$ is the size of the reference set. If $p$ is small and fixed, the complexity becomes linear with respect to the input length.
Furthermore, unlike many deep set models, the reference set in OTKE can be initialized or trained entirely without labels using K-means or Wasserstein barycenters. This provides a strong starting point for supervised tasks. By using a shared reference set across the entire dataset, the model learns a global "coordinate system" for features, which appears more robust than the instance-specific alignment of self-attention when training data is scarce.
Experimental Results
The authors evaluated OTKE across several domains, demonstrating its versatility:
- Bioinformatics: OTKE achieved state-of-the-art results on large-scale protein fold recognition (SCOP 1.75 & 2.06) and chromatin profile detection (DeepSEA). On SCOP, it significantly outperformed both standard CNNs and Set Transformers.
- Natural Language Processing: On the SST-2 sentiment analysis benchmark, OTKE performed competitively with BERT-based models. Adding an OTKE layer on top of pre-trained features outperformed simple mean pooling and was much faster than complex set-processing baselines like RepSet.
- Scaling with Pre-trained Models: When used to aggregate features from massive pre-trained protein models (like ESM-1), OTKE improved accuracy over mean pooling while using 2,500x fewer parameters than a fully fine-tuned model.
Limitations and Future Work
While highly effective, OTKE has some limitations. Extending it to a "multi-layer OTKE" (similar to a multi-layer Transformer) is not straightforward, as defining optimal intermediate feature aggregation remains an open question. Additionally, while more efficient than $O(n^2)$ attention for long sequences, the Sinkhorn iterations still add computational overhead compared to simple global mean or max pooling. Finally, performance is sensitive to hyperparameters like the number of supports and references, requiring careful tuning for different data types.
Summary updated