# Зак Джост о парадоксе GNN: «Простое сглаживание часто побеждает сложные нейросети» Источник: https://www.youtube.com/watch?v=jAGIuobLp60 Канал: Machine Learning Street Talk Опубликовано: 25.03.2022 --- В новом выпуске Machine Learning Street Talk гостем стал **Зак Джост (Zak Jost)**, исследователь из AWS и эксперт в области графовых нейронных сетей (GNN). В беседе с ведущим Тимом Скарфом он подробно разобрал математическую природу сверток на графах, проблему «бутылочного горлышка» выразительности моделей и то, почему современные сложные архитектуры иногда проигрывают классическим методам сглаживания данных. ## 🧬 Геометрическое глубокое обучение и основы симметрии [[JUMP:01:03]] Фундаментом обсуждения стала концепция **Geometric Deep Learning**, формализованная Майклом Бронштейном (Michael Bronstein) и его коллегами. Зак Джост объясняет, что эта концепция служит «чертежом» для большинства современных архитектур: от CNN и RNN до трансформеров [03:23]. Ключевое различие, которое необходимо понимать для работы с пространственными данными, — это разница между эквивариантностью и инвариантностью: * **Эквивариантность (Equivariance):** если вы перемешиваете или сдвигаете входные данные, выходные данные изменяются (перемешиваются) соответствующим образом. Примером служит фильтр в CNN: если «кошка» на картинке сместилась, то и область активации детектора сместится [05:47]. * **Инвариантность (Invariance):** выход остается неизменным вне зависимости от симметричных преобразований входа. Классический пример — операция пулинга (pooling), сообщающая лишь о наличии объекта в кадре, не учитывая его точные координаты [06:12]. По словам Зака Джоста, использование этих симметрий делает архитектуры более «параметрически эффективными». Вместо того чтобы обучаться распознавать специфический паттерн в каждой точке пространства отдельно, модель использует общие фильтры, что значительно сужает пространство гипотез и облегчает оптимизацию [08:23]. ## 📉 Математика графовых сверток: от Фурье до полиномов Чебышева [[JUMP:11:02]] Основная сложность GNN в сравнении с обычными сверточными сетями (CNN) заключается в нестабильности топологии. В сетке пикселей у каждого узла фиксированное количество соседей, а в графе их число варьируется. Зак Джост описывает эволюцию графовых сверток через спектральную теорию: 1. **Частотная область:** изначально свертка на графе определялась через преобразование Фурье. Это требовало поиска собственных векторов лапласиана графа [14:18]. 2. **Вычислительная сложность:** вычисление собственных векторов — операция сложностью $O(n^3)$. Для графов с миллиардами узлов это невозможно [14:58]. 3. **Потеря локальности:** каждый собственный вектор зависит от всех узлов графа, что лишает модель локальности — свойства, за которое мы любим CNN [15:10]. Решением стал переход к пространственным методам (message passing) через аппроксимацию. Ученые (в частности, Томас Кипф) предложили использовать полиномиальное разложение (например, полиномы Чебышева) от матрицы смежности $A$ или лапласиана [16:16]. Умножение вектора признаков на матрицу смежности — это и есть акт передачи сообщения (message passing) от ближайших соседей [16:30]. * $A^1$ собирает данные от соседей в 1 прыжке (1-hop). * $A^2$ агрегирует информацию о путях длиной в 2 шага. * $A^k$ охватывает окрестность радиуса $k$. Современные GNN (такие как GCN) используют аппроксимацию первого порядка. Это ограничивает влияние информации только ближайшим окружением, что делает вычисления линейными и решат проблему нелокальности [19:56]. ## ⚠️ Проблемы глубоких GNN: Оверсмузинг и Оверсквошинг [[JUMP:26:39]] В отличие от классических нейросетей, простое увеличение количества слоев в GNN часто ведет к деградации модели. Зак Джост выделяет две фундаментальные проблемы: * **Over-smoothing (Избыточное сглаживание):** при многократном повторении message passing узлы постоянно усредняют свои признаки с признаками соседей. В итоге все узлы в графе становятся практически идентичными «гомогенными пятнами», и их невозможно различить для классификации [27:57]. * **Over-squashing (Избыточное сжатие):** количество информации в окрестности узла растет экспоненциально с каждым слоем (степень узла $d$ в степени слоя $k$). По словам Зака, попытка сжать этот объем данных в вектор фиксированного размера (например, 8 флоатов по 32 бита) неизбежно ведет к потере критически важных сигналов из удаленных частей графа [28:52]. В качестве решения обсуждаются методы **Graph Rewiring** (перестройка графа). Исследователи, включая Бронштейна, предлагают добавлять или удалять ребра на основе кривизны Риччи (Ricci curvature), чтобы оптимизировать потоки информации и убрать «бутылочные горлышки» [30:37]. ## 🧪 Диффузионный взгляд и «необъяснимая эффективность» простых методов [[JUMP:33:17]] Зак Джост отмечает влияние физики на deep learning. GNN можно рассматривать как дискретизированное решение уравнения диффузии тепла [34:07]. Эммануэль Росси (Emanuel Rossi) в своей недавней работе показал, что распространение признаков по графу работает аналогично решению дифференциальных уравнений в частных производных с граничными условиями (где существующие признаки — это границы, а отсутствующие — искомые значения) [35:53]. Удивительным фактом для индустрии стали результаты работы **«Correct and Smooth»** [39:03]. Простой алгоритм обошел сложные GNN на многих бенчмарках: 1. Обучается обычная модель (например, XGBoost) только на признаках узла. 2. Ошибки (residual) распространяются по графу методом Label Propagation. 3. Итоговый прогноз корректируется с учетом этих сглаженных ошибок. По мнению Зака Джоста, это ставит вопрос: действительно ли нам нужна высокая выразительная мощность GNN, или в большинстве реальных задач достаточно простого локального сглаживания (фильтра низких частот)? [42:09] ## 🧠 Тест Вайсфейлера — Лемана и предел выразительности [[JUMP:48:28]] Разговор коснулся теоретического предела GNN, который связан с **1-WL тестом (Weisfeiler-Lehman)** на изоморфизм графов [48:41]. Стандартные графовые сети не могут различить графы, которые не различает 1-WL тест (например, кольцо из 6 узлов против двух треугольников по 3 узла) [51:36]. Ключ к мощности GNN — в функции агрегации: * Чтобы достичь мощности 1-WL теста, функция агрегации должна быть **инъективной** (уникальный набор входов дает уникальный выход). * Агрегатор `Mean` (среднее) менее мощный, чем `Sum` (сумма), так как среднее не может отличить пропорцию признаков от их общего количества [53:50]. Зак упоминает архитектуру **GIN (Graph Isomorphism Networks)**, которая математически гарантирует мощность на уровне 1-WL теста за счет использования суммирования и глубоких MLP [55:12]. ## 📚 Образовательный проект Зака Джоста [[JUMP:58:16]] Последние полгода Зак Джост посвятил созданию курса по Graph Neural Networks, который сочетает теорию (преобразования Фурье, спектральные методы) и практику (решение задач классификации узлов, предсказания связей и классификации целых графов) [59:49]. Курс проводится в формате когорт, что, по мнению Зака, критически важно для доведения обучения до конца благодаря дедлайнам и комьюнити в Discord [1:00:28].