Graph Neural Networks

Большинство данных в мире - это графы. Молекулы - граф атомов и связей. Социальные сети - граф людей и отношений. Карты - граф дорог. CNN работают с сетками пикселей, RNN - с последовательностями. Как обучить нейросеть на нерегулярных структурах, где у каждого узла разное число соседей? GNN - ответ на этот вопрос.

• **Google Maps ETA** использует GNN на дорожном графе для предсказания времени в пути - точность улучшилась на 40% по сравнению с предыдущими методами
• **DeepMind AlphaFold 2** применяет graph transformer (Evoformer) для предсказания 3D структуры белков - задача, над которой биологи работали 50 лет
• **Pinterest Pinpoint** - GNN-based рекомендательная система обрабатывает граф из 3B узлов (пины, пользователи, доски) для персонализации
• **Uber Fraud Detection** - GNN на транзакционном графе обнаруживает мошеннические схемы, невидимые при анализе отдельных транзакций

Marco Gori, Franco Scarselli и первая Graph Neural Network

Сам термин Graph Neural Network ввели Marco Gori с коллегами в 2005 году, а затем формализовали Franco Scarselli, Marco Gori и соавторы в статье 2009 года 'The Graph Neural Network Model'. Их модель распространяла информацию по узлам до достижения фиксированной точки, из-за чего обучение было медленным и нестабильным. Область оставалась нишевой до 2016 года, когда Thomas Kipf и Max Welling предложили Graph Convolutional Network (GCN) для semi-supervised классификации, упростив спектральную свёртку до дешёвого послойного обновления. GCN сделала GNN практичными и запустила взрыв графового deep learning.

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

• Backpropagation и обучение нейронных сетей
• Механизм attention (его переиспользуют GAT и Graph Transformers)
• Базовая линейная алгебра: матрицы смежности и степеней, матричное умножение

• Backpropagation: как нейронные сети учатся
• Transformers

Message Passing Framework

**GNN строятся на одной фундаментальной идее:** каждый узел агрегирует информацию от соседей, обновляет своё представление, и так несколько раз. После k итераций узел «знает» о своём k-hop окружении. Это называется Message Passing - обобщённый фреймворк, частными случаями которого являются GCN, GAT, GraphSAGE и десятки других архитектур.

Message Passing эквивалентен умножению матрицы смежности на матрицу признаков - но PyG делает это эффективно через sparse operations. Граф с 1M узлов и 10M рёбер обрабатывается за секунды на одном GPU, тогда как плотная матрица смежности не поместилась бы в память.

Graph Convolutional Network (GCN)

**GCN (Kipf & Welling, 2017)** - простейшая и самая влиятельная GNN архитектура. Один слой GCN: нормализуй матрицу смежности, умножь на признаки, примени обучаемые веса и нелинейность. Нормализация учитывает степень узла - хабы (много соседей) не «заглушают» периферийные узлы.

Математически слой GCN: H' = sigma(D^(-1/2) * A_hat * D^(-1/2) * H * W), где A_hat = A + I (self-loops), D - матрица степеней. Нормализация обеспечивает стабильный средний сигнал независимо от степени узла.

Graph Attention Networks (GAT)

**Проблема GCN:** все соседи агрегируются с весами, зависящими только от степени узла. GAT добавляет механизм attention - узел сам учится, какие соседи важнее. Коэффициент внимания между узлами i и j вычисляется через обучаемую сеть на конкатенации их признаков, затем softmax нормализует веса.

GATv2 (2022) исправляет теоретический изъян оригинала: в GATv1 attention ранжировал соседей одинаково для всех центральных узлов (static attention). GATv2 делает внимание динамическим - важность соседа зависит от состояния запрашивающего узла.

Graph Transformers

**Graph Transformers** - следующий шаг: attention не ограничен рёбрами графа, а применяется ко всем парам узлов. Это снимает ограничение локальности, но возвращает проблему O(N^2) сложности. Ключевое новшество - специальные positional encodings, кодирующие топологию графа.

**DeepMind AlphaFold 2** использует Evoformer - специализированный graph transformer для белковых структур. Модель предсказывает 3D структуру белка по аминокислотной последовательности с атомарной точностью, решив 50-летнюю задачу биологии. Граф здесь - попарные расстояния между аминокислотами.

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

• **Message Passing** - универсальный фреймворк: узел агрегирует соседей, обновляет себя, k итераций = k-hop рецептивное поле
• **GCN** - нормализованная агрегация с обучаемыми весами; self-loops гарантируют сохранение собственных признаков узла
• **GAT** - attention механизм учит важность каждого соседа; GATv2 делает веса динамически зависящими от запрашивающего узла
• **Graph Transformers** - attention между всеми парами + топологические positional encodings; основа AlphaFold 2

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

GNN объединяет идеи из нескольких областей:

• Transformer и Attention — GAT применяет scaled dot-product attention к графовым структурам; Graph Transformers - прямое расширение трансформера на графы
• Vision Transformers (ViT) — ViT и Graph Transformers используют схожие positional encoding идеи, но для разных типов структур
• Self-Supervised Learning — GraphMAE и DGI - self-supervised методы для GNN, позволяющие обучаться без разметки узлов

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

• GNN агрегируют соседей как множество, теряя порядок. Для каких задач порядок соседей важен? Как его закодировать без потери permutation invariance по всему графу?
• Over-smoothing: после многих слоёв GCN все узлы сходятся к похожим представлениям. Почему это происходит математически, и как residual connections и PairNorm борются с этим?
• AlphaFold 2 работает с виртуальным графом - добавляет рёбра между всеми аминокислотами в радиусе. Почему это лучше, чем работать только с ковалентными связями?

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

• dl-06 — GAT применяет scaled dot-product attention к рёбрам графа
• dl-07 — ViT и Graph Transformers разделяют идеи positional encoding
• dl-17 — GraphMAE и DGI обучают GNN без разметки узлов
• ds-16-graphs-intro — Граф как структура данных из узлов и рёбер
• alg-12-bfs — Передача сообщений распространяется как обход в ширину
• la-35-spectral-graph — Спектральные GNN используют собственный базис лапласиана графа
• la-01-vectors-intro