В новом выпуске Machine Learning Street Talk гостем стал Зак Джост (Zak Jost), исследователь из AWS и эксперт в области графовых нейронных сетей (GNN). В беседе с ведущим Тимом Скарфом он подробно разобрал математическую природу сверток на графах, проблему «бутылочного горлышка» выразительности моделей и то, почему современные сложные архитектуры иногда проигрывают классическим методам сглаживания данных.
🧬 Геометрическое глубокое обучение и основы симметрии 1:03
Фундаментом обсуждения стала концепция Geometric Deep Learning, формализованная Майклом Бронштейном (Michael Bronstein) и его коллегами. Зак Джост объясняет, что эта концепция служит «чертежом» для большинства современных архитектур: от CNN и RNN до трансформеров .
Ключевое различие, которое необходимо понимать для работы с пространственными данными, — это разница между эквивариантностью и инвариантностью:
- Эквивариантность (Equivariance): если вы перемешиваете или сдвигаете входные данные, выходные данные изменяются (перемешиваются) соответствующим образом. Примером служит фильтр в CNN: если «кошка» на картинке сместилась, то и область активации детектора сместится .
- Инвариантность (Invariance): выход остается неизменным вне зависимости от симметричных преобразований входа. Классический пример — операция пулинга (pooling), сообщающая лишь о наличии объекта в кадре, не учитывая его точные координаты .
По словам Зака Джоста, использование этих симметрий делает архитектуры более «параметрически эффективными». Вместо того чтобы обучаться распознавать специфический паттерн в каждой точке пространства отдельно, модель использует общие фильтры, что значительно сужает пространство гипотез и облегчает оптимизацию .
📉 Математика графовых сверток: от Фурье до полиномов Чебышева 11:02
Основная сложность GNN в сравнении с обычными сверточными сетями (CNN) заключается в нестабильности топологии. В сетке пикселей у каждого узла фиксированное количество соседей, а в графе их число варьируется.
Зак Джост описывает эволюцию графовых сверток через спектральную теорию:
- Частотная область: изначально свертка на графе определялась через преобразование Фурье. Это требовало поиска собственных векторов лапласиана графа .
- Вычислительная сложность: вычисление собственных векторов — операция сложностью $O(n^3)$. Для графов с миллиардами узлов это невозможно .
- Потеря локальности: каждый собственный вектор зависит от всех узлов графа, что лишает модель локальности — свойства, за которое мы любим CNN .
Решением стал переход к пространственным методам (message passing) через аппроксимацию. Ученые (в частности, Томас Кипф) предложили использовать полиномиальное разложение (например, полиномы Чебышева) от матрицы смежности $A$ или лапласиана . Умножение вектора признаков на матрицу смежности — это и есть акт передачи сообщения (message passing) от ближайших соседей .
- $A^1$ собирает данные от соседей в 1 прыжке (1-hop).
- $A^2$ агрегирует информацию о путях длиной в 2 шага.
- $A^k$ охватывает окрестность радиуса $k$.
Современные GNN (такие как GCN) используют аппроксимацию первого порядка. Это ограничивает влияние информации только ближайшим окружением, что делает вычисления линейными и решат проблему нелокальности .
⚠️ Проблемы глубоких GNN: Оверсмузинг и Оверсквошинг 26:39
В отличие от классических нейросетей, простое увеличение количества слоев в GNN часто ведет к деградации модели. Зак Джост выделяет две фундаментальные проблемы:
- Over-smoothing (Избыточное сглаживание): при многократном повторении message passing узлы постоянно усредняют свои признаки с признаками соседей. В итоге все узлы в графе становятся практически идентичными «гомогенными пятнами», и их невозможно различить для классификации .
- Over-squashing (Избыточное сжатие): количество информации в окрестности узла растет экспоненциально с каждым слоем (степень узла $d$ в степени слоя $k$). По словам Зака, попытка сжать этот объем данных в вектор фиксированного размера (например, 8 флоатов по 32 бита) неизбежно ведет к потере критически важных сигналов из удаленных частей графа .
В качестве решения обсуждаются методы Graph Rewiring (перестройка графа). Исследователи, включая Бронштейна, предлагают добавлять или удалять ребра на основе кривизны Риччи (Ricci curvature), чтобы оптимизировать потоки информации и убрать «бутылочные горлышки» .
🧪 Диффузионный взгляд и «необъяснимая эффективность» простых методов 33:17
Зак Джост отмечает влияние физики на deep learning. GNN можно рассматривать как дискретизированное решение уравнения диффузии тепла . Эммануэль Росси (Emanuel Rossi) в своей недавней работе показал, что распространение признаков по графу работает аналогично решению дифференциальных уравнений в частных производных с граничными условиями (где существующие признаки — это границы, а отсутствующие — искомые значения) .
Удивительным фактом для индустрии стали результаты работы «Correct and Smooth» . Простой алгоритм обошел сложные GNN на многих бенчмарках:
- Обучается обычная модель (например, XGBoost) только на признаках узла.
- Ошибки (residual) распространяются по графу методом Label Propagation.
- Итоговый прогноз корректируется с учетом этих сглаженных ошибок.
По мнению Зака Джоста, это ставит вопрос: действительно ли нам нужна высокая выразительная мощность GNN, или в большинстве реальных задач достаточно простого локального сглаживания (фильтра низких частот)?
🧠 Тест Вайсфейлера — Лемана и предел выразительности 48:28
Разговор коснулся теоретического предела GNN, который связан с 1-WL тестом (Weisfeiler-Lehman) на изоморфизм графов . Стандартные графовые сети не могут различить графы, которые не различает 1-WL тест (например, кольцо из 6 узлов против двух треугольников по 3 узла) .
Ключ к мощности GNN — в функции агрегации:
- Чтобы достичь мощности 1-WL теста, функция агрегации должна быть инъективной (уникальный набор входов дает уникальный выход).
- Агрегатор
Mean(среднее) менее мощный, чемSum(сумма), так как среднее не может отличить пропорцию признаков от их общего количества .
Зак упоминает архитектуру GIN (Graph Isomorphism Networks), которая математически гарантирует мощность на уровне 1-WL теста за счет использования суммирования и глубоких MLP .
📚 Образовательный проект Зака Джоста 58:16
Последние полгода Зак Джост посвятил созданию курса по Graph Neural Networks, который сочетает теорию (преобразования Фурье, спектральные методы) и практику (решение задач классификации узлов, предсказания связей и классификации целых графов) . Курс проводится в формате когорт, что, по мнению Зака, критически важно для доведения обучения до конца благодаря дедлайнам и комьюнити в Discord .
