Gromov-Wasserstein

Как сравнить форму белка с формой галактики? Белок задан матрицей контактов аминокислот, галактика - картой плотности звёзд. У них нет общего пространства, поэтому Wasserstein неприменим - он требует общей метрики для измерения стоимости транспортировки. Факундо Мемоли (Memoli, 2011) предложил другой вопрос: не 'куда переместить каждую точку', а 'какой план сохраняет попарные расстояния внутри каждого объекта'. Это и есть Gromov-Wasserstein.

• **Биоинформатика:** выравнивание мозговых коннектомов разных испытуемых через FGW - структура нейронных связей + функциональные активации регионов
• **Single-cell multi-omics:** интеграция RNA-seq и ATAC-seq данных одних клеток через GW - пространства экспрессии и хроматиновой доступности разные, но GW находит соответствие
• **Shape analysis:** сравнение 3D форм молекул для drug discovery - GW инвариантен к вращениям и отражениям, Wasserstein - нет

Предварительные знания

• Wasserstein distances

Формулировка Gromov-Wasserstein

Как сравнить форму белка с формой галактики, если они живут в совершенно разных метрических пространствах? Нельзя применить Wasserstein - нет общего пространства, в котором оба объекта лежат. Факундо Мемоли (Memoli, 2011) предложил ответ: вместо того чтобы транспортировать точки, транспортировать попарные расстояния. Транспортный план хорош, если расстояния внутри источника соответствуют расстояниям внутри цели.

Формально: даны метрические пространства $(X, d_X, \mu)$ и $(Y, d_Y, \nu)$ с мерами. Транспортный план $T$ - вероятностная мера на $X \times Y$ с маргиналями $\mu$ и $\nu$. Проблема Gromov-Wasserstein:

**Задача Gromov-Wasserstein (Memoli 2011):** $GW(\mu, \nu) = \min_{T \in \Pi(\mu, \nu)} \iint_{X \times Y} \iint_{X \times Y} |d_X(x, x') - d_Y(y, y')|^2 \, dT(x,y) \, dT(x',y')$ Цена транспорта: насколько расстояние между $x$ и $x'$ в пространстве $X$ отличается от расстояния между их образами $y$ и $y'$ в пространстве $Y$. **Дискретный случай** (матрицы расстояний $C^X \in \mathbb{R}^{m \times m}$, $C^Y \in \mathbb{R}^{n \times n}$): $GW = \min_{T \in \Pi(\mu, \nu)} \sum_{i,j,k,l} |C^X_{ik} - C^Y_{jl}|^2 T_{ij} T_{kl}$ где $T_{ij} \geq 0$, $\sum_j T_{ij} = \mu_i$, $\sum_i T_{ij} = \nu_j$.

Квадратичная природа GW и Fused GW

Задача GW квадратична по $T$: функционал содержит $T_{ij} T_{kl}$, а не просто $T_{ij}$. Это принципиальное отличие от Wasserstein, который линеен по $T$ и потому решается как LP. GW - это задача квадратичного программирования с симплексными ограничениями, что делает поиск глобального оптимума NP-сложным в общем случае.

**Fused Gromov-Wasserstein (Titouan et al. 2019):** Когда у точек есть и структура (граф/метрика), и признаки (features), Fused GW балансирует оба аспекта: $FGW_{\alpha}(\mu, \nu) = \min_{T \in \Pi} \alpha \cdot GW(T) + (1-\alpha) \cdot W(T)$ где $\alpha \in [0,1]$ - баланс между структурной частью (GW) и признаковой (Wasserstein). **Применения FGW:** - **Мозговые коннектомы:** граф нейронных связей + активации регионов. GW выравнивает топологию, W - функциональные профили - **Single-cell RNA-seq:** клетки двух образцов живут в разных пространствах экспрессии. FGW находит соответствие сохраняя и транскриптомный профиль (W) и взаимные расстояния клеток (GW)

Вычисление GW: Frank-Wolfe и Sliced GW

Стандартный подход к GW - метод Франка-Вульфа (alternating projections): линеаризовать квадратичный функционал относительно текущего $T$, решить линеаризованную задачу как Wasserstein (LP), сделать шаг по направлению к решению. Каждая итерация стоит $O(m^2 n^2)$ (матрично-матричные операции) плюс решение W (транспортная задача). Для больших графов это тяжело.

**Алгоритм Frank-Wolfe для GW:** 1. Инициализация: $T^{(0)} = \mu \nu^\top$ (независимый транспортный план) 2. Итерация $t$: - Вычислить градиент: $\nabla_T \mathcal{L}(T^{(t)}) = $ линейная функция от $T^{(t)}$ - Решить линеаризованную задачу: $S = \arg\min_{T'\in\Pi} \langle \nabla_T \mathcal{L}, T' \rangle$ (задача W) - Обновление: $T^{(t+1)} = (1-\gamma_t) T^{(t)} + \gamma_t S$ 3. Сходится к локальному оптимуму **Sliced Gromov-Wasserstein (Vayer et al. 2019):** Проецировать оба распределения на случайные одномерные подпространства, вычислить 1D GW (решается аналитически), усреднить. Сложность: $O(mn \log(mn))$ вместо $O(m^2 n^2)$. Смещённая оценка, но масштабируется на большие графы.

Ключевые идеи

• **GW = транспорт попарных расстояний:** $\min_T \iint |d_X(x,x') - d_Y(y,y')|^2 dT dT$. Применимо когда общего пространства нет
• **Квадратичность = NP-сложность:** в отличие от W (линеен по T, решается как LP), GW квадратичен. Frank-Wolfe сходится к локальному оптимуму
• **Fused GW:** $\alpha \cdot GW + (1-\alpha) \cdot W$ балансирует структуру и признаки. Используется в мозговых коннектомах, single-cell биологии
• **POT library:** `ot.gromov.gromov_wasserstein`, `ot.gromov.fused_gromov_wasserstein`. Sliced GW для масштабируемости

Связанные темы

GW расширяет теорию оптимального транспорта за пределы одного пространства:

• Wasserstein Distance — GW обобщает W на случай разных метрических пространств
• Sinkhorn Algorithm — Sinkhorn решает W с энтропийной регуляризацией; аналогичная регуляризация применима к GW

Вопросы для размышления

• GW инвариантен к изометриям пространства (вращениям, отражениям). Почему это свойство критично для сравнения молекулярных форм?
• Fused GW с alpha=0 вырождается в Wasserstein, с alpha=1 - в чистый GW. Какое значение alpha выбрать для задачи, где структура графа важнее признаков вершин?
• Frank-Wolfe сходится к локальному оптимуму GW. Как выбор начального плана T^(0) влияет на итоговое решение?

Связанные уроки

• ot-03-wasserstein — GW обобщает Wasserstein на разные метрические пространства
• ot-04-sinkhorn — Sinkhorn решает W регуляризованно; для GW есть аналогичная итерация
• calc-01-sequences