Графовые нейронные сети (GNN)

Многие реальные данные имеют структуру графа: социальные сети (пользователи + связи), молекулы (атомы + связи), дорожная сеть (перекрёстки + дороги), знания (сущности + отношения). Стандартные CNN и MLP игнорируют структуру — GNN сохраняют её.

Проблема обучения на графах

Граф G = (V, E): n вершин, m рёбер. Каждая вершина v имеет признаки x_v ∈ ℝᵈ. Матрица смежности A ∈ {0,1}^{n×n}. Задача: предсказание метки каждой вершины (node classification), рёбра (link prediction), или всего графа (graph classification).

Главное отличие от обычных данных: нет фиксированного порядка вершин (граф — permutation-equivariant). Размер графа может быть разным. Необходимо учитывать структуру соседства.

Message Passing Framework

Общий принцип GNN — «обмен сообщениями» между соседями. Каждая вершина агрегирует информацию от соседей, обновляет своё представление:

hᵥ^{(k)} = UPDATE^{(k)}(hᵥ^{(k-1)}, AGGREGATE^{(k)}({hᵤ^{(k-1)}: u ∈ N(v)}))

После K итераций: hᵥ^{(K)} кодирует информацию о K-hop окрестности v.

Конкретные архитектуры GNN

Graph Convolutional Network (GCN, Kipf & Welling, 2017):

H^{(l+1)} = σ(D̃^{−1/2} Ã D̃^{−1/2} H^{(l)} W^{(l)})

Здесь Ã = A + I (добавляем self-loops), D̃ — степенная матрица Ã. D̃^{−1/2} Ã D̃^{−1/2} — нормализованная матрица смежности. Интуиция: усредняем признаки соседей + сама вершина, нормировка предотвращает масштабирование.

Проблема: GCN «сглаживает» признаки — при K→∞ все вершины сходятся к одному значению (over-smoothing).

GraphSAGE (Hamilton et al., 2017):

hᵥ^{(k)} = σ(W · CONCAT(hᵥ^{(k−1)}, AGG({hᵤ^{(k−1)}: u ∈ N(v)})))

AGG может быть: mean, max, LSTM. Inductive: может обобщаться на новые вершины без переобучения (vs GCN — transductive).

Graph Attention Network (GAT, Veličković et al., 2018):

αᵥᵤ = exp(LeakyReLU(aᵀ[Whᵥ || Whᵤ])) / Σₖ exp(...) hᵥ' = σ(Σᵤ αᵥᵤ Whᵤ)

Веса внимания αᵥᵤ учатся автоматически — разные соседи имеют разный вклад. Multi-head attention: несколько независимых механизмов внимания.

Graph Transformer

Graphormer (Ying et al., 2021): обычный Transformer применяется к графу. Специальные позиционные эмбеддинги: centrality encoding (степень вершины), spatial encoding (кратчайший путь между вершинами), edge encoding. SOTA на многих граф-задачах.

Применения GNN

Химия и фармацевтика: Молекула = граф (атомы + связи). GNN предсказывает свойства молекул: растворимость, токсичность, биологическую активность. AlphaFold не использует GNN (трансформер), но GNNs широко используются в DeepMind для молекулярной динамики.

Рекомендательные системы: Граф пользователь-товар. GNN распространяет информацию через граф → лучшие рекомендации. PinSage (Pinterest, 2018): 3 млрд вершин, реальная система.

Детекция мошенничества: Граф транзакций. Мошеннические аккаунты образуют характерные паттерны в графе. GNN выявляет субструктуры мошенничества.

Физические симуляции: Системы частиц как граф (частица = вершина, взаимодействие = ребро). GNN аппроксимирует динамику → 1000× быстрее численного решения. DeepMind MeshGraphNets для CFD-симуляций.

Численный пример

Задача node classification: Cora dataset (2708 научных статей, 7 классов, 5429 цитирований). Признаки: bag-of-words (1433 признака).

Logistic Regression (игнорируем граф): test accuracy 58%. GCN (2 слоя): 81.5%. GAT (2 слоя, 8 голов): 83.0%. GraphSAGE (mean aggregation): 82.1%.

Важность структуры: GCN без рёбер (только признаки вершин) = LR → структура даёт +23%.

Задание: Реализуйте GCN и GAT на PyTorch Geometric для Cora dataset. (1) Обучите GCN (2 слоя, hidden=64): train/val/test accuracy. (2) Обучите GAT (2 слоя, 8 голов). (3) Визуализируйте внимание GAT (heatmap весов αᵥᵤ для 5 вершин) — какие соседи получают максимальный вес? (4) Изучите over-smoothing: как меняется accuracy при 1, 2, 4, 8 слоях? (5) Задача link prediction: предсказать, существует ли ребро между парой вершин.