Профессор Массачусетского технологического института (MIT) Филип Изола открывает пятую лекцию курса по архитектурам глубокого обучения, посвящая её графовым нейронным сетям (GNN). По мнению Изолы, глубокое обучение — это «самая красивая математика», а графы — универсальный язык для описания связей в мире, от социальных сетей до молекулярных структур.
🕸️ Почему графы повсюду: от соцсетей до физики 4:06
Филип Изола начинает с того, что графовые структуры являются естественным способом представления данных во многих областях. В отличие от стандартных табличных данных, графы описывают объекты (узлы) и их взаимоотношения (ребра).
Сферы применения графовых моделей, упомянутые в лекции:
- Социальные сети: Пользователи и их дружеские связи .
- Биология и генетика: Взаимодействие генов и белков .
- Химия: Молекулы как графы, где атомы — узлы, а химические связи — ребра . Это критически важно для предсказания токсичности лекарств .
- Веб-поиск: Алгоритм PageRank от Google, рассматривающий интернет как граф гиперссылок .
- Логистика и навигация: Google Maps использует графы дорог для поиска кратчайшего пути .
- Физика: Моделирование динамики жидкостей и частиц как системы взаимодействующих узлов .
Профессор отмечает, что хотя для многих из этих задач существуют классические алгоритмы (например, алгоритм Дейкстры для кратчайшего пути), нейросети могут работать быстрее, обучаясь специфическим эвристикам на конкретных распределениях данных .
🧱 Архитектура GNN: как это работает 14:02
Графовая нейронная сеть принимает на вход два основных компонента:
- Матрица смежности (Adjacency Matrix): Описывает топологию графа (кто с кем соединен) .
- Атрибуты узлов: Векторы признаков для каждого узла (например, тип атома в молекуле) .
Проблема обычных нейросетей (MLP)
Если просто «развернуть» матрицу смежности в один длинный вектор и подать её в обычный перцептрон (MLP), возникнет проблема чувствительности к перестановке (permutation sensitivity) . По словам Изолы, выбор индексов для узлов (какой узел будет первым, какой — четвертым) абсолютно произволен. Модель должна выдавать один и тот же результат, как бы мы ни перемешали строки и столбцы в матрице смежности, если структура графа осталась прежней. Это свойство называется инвариантностью к перестановкам .
Алгоритм передачи сообщений (Message Passing) 32:59
Основной цикл работы GNN состоит из двух повторяющихся шагов для каждого слоя $k$:
- Агрегация (Aggregate): Узел собирает «сообщения» (векторы признаков) от всех своих соседей . Функция агрегации должна быть инвариантной к порядку соседей (например, сумма, среднее или максимум) .
- Обновление (Update): Узел объединяет собранное сообщение со своим собственным текущим вектором признаков, чтобы получить новое представление .
Этот процесс повторяется $k$ раз, что позволяет информации распространяться по графу. После $k$ шагов каждый узел «знает» о своих соседях на расстоянии $k$ хопов .
🔄 GNN как обобщение других архитектур 54:32
Изола подчеркивает, что многие знакомые архитектуры — это лишь частные случаи графовых сетей:
- MLP (Многослойный перцептрон): Это GNN, состоящая всего из одного узла без связей .
- CNN (Сверточные нейросети): Это GNN, работающая на регулярной сетке (решетке), где у каждого узла фиксированное количество соседей в строго определенных позициях .
- Трансформеры (Transformers): Это GNN на полносвязном графе (каждый узел соединен с каждым), где в качестве функции агрегации используется механизм внимания (attention) .
📐 Теоретические пределы: что GNN не могут «увидеть» 1:06:33
Один из самых глубоких разделов лекции посвящен мощности аппроксимации. Профессор объясняет, что стандартные GNN не всесильны.
Существуют пары графов, которые структурно различны, но для GNN выглядят абсолютно одинаково . Это происходит потому, что GNN видит мир через «дерево окрестностей». Если деревья развертки для всех узлов в двух разных графах совпадают, сеть выдаст идентичные предсказания для обоих .
Филип Изола проводит параллель с классической теорией графов:
- Мощность GNN по различению графов эквивалентна тесту Вайсфейлера — Лемана (1-WL algorithm), разработанному еще в 1960-х годах .
- GNN не могут определить такие свойства, как длина самого длинного цикла или диаметр графа .
🛠️ Практические нюансы и инструменты 1:15:31
Профессор приводит пример того, как мелкие детали реализации влияют на результат:
- Сумма vs Среднее: Использование среднего арифметического (Mean) вместо суммы (Sum) при агрегации может резко снизить точность . По мнению Изолы, среднее «теряет» информацию о количестве соседей (степени узла), что критично для многих задач .
- Позиционное кодирование: Чтобы обойти ограничения и различать изоморфные (с точки зрения 1-WL) графы, узлам можно добавлять информацию об их положении. Популярный метод — использование собственных векторов Лапласиана графа (graph Laplacian eigenvectors) .
Для реализации GNN в коде участникам рекомендуется использовать специализированные библиотеки (хотя конкретные названия инструментов вроде PyTorch Geometric не звучат, упоминается общая работа в PyTorch ).
Как обучить свою GNN (пошаговый алгоритм):
- Подготовить данные: Представить входные данные в виде списка узлов с признаками и списка ребер (матрицы смежности) .
- Выбрать функции: Определить функцию агрегации (например, MLP + Sum) и функцию обновления (например, Linear + ReLU) .
- Определить задачу:
- Запустить обучение: Использовать стандартный метод обратного распространения ошибки (backpropagation) через развернутый граф вычислений .
