A Trainable Optimal Transport Embedding for Feature Aggregation and its Relationship to Attention

Grégoire Mialon, Dexiong Chen, Alexandre d'Aspremont, Julien Mairal

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:

  1. The Reference Set: The model maintains a "reference set" of trainable vectors, which act as prototypes or bins.
  2. 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.
  3. Weighted Pooling: The input features are then aggregated into buckets corresponding to the reference elements, weighted by the OT plan.
Optimal Transport Alignment and Pooling

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

Abstract

We address the problem of learning on sets of features, motivated by the need of performing pooling operations in long biological sequences of varying sizes, with long-range dependencies, and possibly few labeled data. To address this challenging task, we introduce a parametrized representation of fixed size, which embeds and then aggregates elements from a given input set according to the optimal transport plan between the set and a trainable reference. Our approach scales to large datasets and allows end-to-end training of the reference, while also providing a simple unsupervised learning mechanism with small computational cost. Our aggregation technique admits two useful interpretations: it may be seen as a mechanism related to attention layers in neural networks, or it may be seen as a scalable surrogate of a classical optimal transport-based kernel. We experimentally demonstrate the effectiveness of our approach on biological sequences, achieving state-of-the-art results for protein fold recognition and detection of chromatin profiles tasks, and, as a proof of concept, we show promising results for processing natural language sequences. We provide an open-source implementation of our embedding that can be used alone or as a module in larger learning models at https://github.com/claying/OTK.
BibTeX
@inproceedings{mialon2021trainable,
  author = {Grégoire Mialon and Dexiong Chen and Alexandre d'Aspremont and Julien Mairal},
  title = {{A Trainable Optimal Transport Embedding for Feature Aggregation and its Relationship to Attention}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=ZK6vTvb84s},
}
Figure