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

Все архитектуры, разобранные до сих пор, опирались на жёсткую структуру данных. Свёрточные сети предполагают решётку: у пикселя есть сосед слева и сосед сверху, и это верно для всех пикселей. Рекуррентные сети предполагают линейный порядок: есть «до» и «после». Трансформеры вообще отказались от структуры и сделали каждый токен соседом каждого.

Но огромная доля реальных данных — это граф: объекты и связи между ними, где связей мало, они нерегулярны и сами по себе несут информацию. Социальная сеть, граф транзакций, молекула, дорожная сеть, граф зависимостей пакетов, схема БД, цитирования статей, взаимодействия «пользователь — товар». У узла может быть 3 соседа или 3 миллиона, и нет никакого «первого» соседа.

Графовые нейронные сети — это ответ на вопрос «какой индуктивный сдвиг правильный для таких данных». Ответ оказался коротким: инвариантность к перестановке узлов плюс локальность. Из этих двух требований почти однозначно выводится вся конструкция, которую мы разберём.

1. Граф как данные: почему нельзя просто взять MLP

Формально граф — это $G = (V, E)$: множество узлов $V$, $|V| = n$, и множество рёбер $E \subseteq V \times V$. Данные обычно приходят в трёх тензорах:

• $X \in \mathbb{R}^{n \times m}$ — признаки узлов (профиль пользователя, тип атома);
• $A \in {0,1}^{n \times n}$ — матрица смежности (на практике — разреженный список рёбер edge_index формы $2 \times |E|$);
• $E_{\text{attr}} \in \mathbb{R}^{|E| \times c}$ — признаки рёбер (тип связи, сумма перевода, тип химической связи).

Наивная идея: развернуть $A$ и $X$ в один длинный вектор и подать в MLP из статьи о перцептроне. Она проваливается по трём причинам, и каждая из них принципиальна.

Первая: нет канонического порядка узлов. Один и тот же граф можно записать $n!$ способами, переставив нумерацию узлов. Для MLP вектор [A[0,1], A[0,2], ...] при перестановке становится совершенно другим входом. Чтобы MLP выучил, что все $n!$ вариантов — один объект, ему нужно увидеть их все. Для графа из 30 узлов это $2.6 \cdot 10^{32}$ примеров. Задача не решается данными — её нужно решать архитектурой.

Вторая: переменный размер. Молекулы бывают из 5 и из 200 атомов, у пользователя 7 или 7000 друзей. MLP требует фиксированной размерности входа.

Третья: разреженность. В графе из $10^8$ узлов матрица $A$ имеет $10^{16}$ элементов, из которых ненулевых — порядка $10^9$. Плотное представление невозможно физически.

Ровно та же логика, что привела нас к свёртке. В CNN мы потребовали эквивариантность к сдвигу и получили разделяемое ядро. Здесь мы потребуем эквивариантность к перестановке и получим передачу сообщений.

2. Три уровня задач и два режима обучения

Прежде чем строить архитектуру, надо понять, что именно мы предсказываем. Уровень задачи определяет, где заканчивается сеть.

Второе важное разделение — режим обучения:

• Трансдуктивный: граф один и он целиком известен при обучении, размечена лишь часть узлов (классика — Cora, Citeseer). Модель не обязана уметь работать с новыми узлами. Именно так формулировалась исходная задача GCN.
• Индуктивный: на инференсе приходят узлы или целые графы, которых при обучении не было (новый пользователь, новая молекула). Это подавляющее большинство продакшн-задач, и именно ради него придумали GraphSAGE.

Разница практическая: трансдуктивные модели вроде классических эмбеддингов DeepWalk/node2vec хранят обучаемую таблицу «узел → вектор» и для нового узла не имеют ничего. GNN же учит функцию от окрестности, поэтому переносится на новые узлы бесплатно — при условии, что у них есть признаки.

Отдельный практический вопрос — как вообще уложить домен в граф. Часто он гетерогенный: несколько типов узлов и несколько типов рёбер.

Такая схема — не просто ER-диаграмма базы, а буквально спецификация графа для модели. Сигнал «два аккаунта заходили с одного устройства» в табличной постановке требует ручного фичеинжиниринга, а в графовой — это ребро, и модель сама решит, насколько оно информативно. Это главная причина, по которой антифрод-команды переходят на GNN.

3. Симметрия, из которой всё следует

Пусть $P$ — матрица перестановки. Нам нужны функции двух видов:

• Инвариантная (для задач уровня графа): $f(PX, PAP^\top) = f(X, A)$ — ответ не зависит от нумерации.
• Эквивариантная (для задач уровня узла): $F(PX, PAP^\top) = P,F(X, A)$ — переставили узлы на входе, представления переставились так же.

Простейшая эквивариантная операция над множеством соседей — та, что не зависит от их порядка: сумма, среднее, максимум. Отсюда сразу вытекает канон: представление узла обновляется как функция от него самого и от мультимножества представлений его соседей.

$$h_v^{(l+1)} = \text{UPD}^{(l)}\Big(h_v^{(l)},\ \bigoplus_{u \in \mathcal{N}(v)} \text{MSG}^{(l)}\big(h_v^{(l)}, h_u^{(l)}, e_{uv}\big)\Big)$$

где $\bigoplus$ — перестановочно-инвариантный агрегатор. Это message passing (Gilmer et al., 2017, arXiv:1704.01212) — рамка, в которую укладывается практически весь зоопарк GNN. Для задач уровня графа сверху добавляется READOUT:

$$h_G = \text{READOUT}\big({h_v^{(L)} : v \in V}\big) \quad\text{— тоже инвариантный: sum / mean / max}$$

Обратите внимание на устройство мысли: мы не придумывали архитектуру, мы вывели её из симметрии задачи. Эта программа — «геометрическое глубокое обучение» — единым языком описывает CNN (симметрия сдвига), GNN (перестановки), трансформеры (перестановки на полном графе) и сети на сферах (вращения). Манифест: Bronstein et al., arXiv:2104.13478.

Один слой = один хоп. $L$ слоёв = информация с расстояния $L$:

Правая часть картинки — ключ к пониманию мини-батчей и сложности: для одного узла GNN разворачивается в дерево, размер которого растёт как $O(\bar{d}^{,L})$, где $\bar{d}$ — средняя степень. К этому мы вернёмся в разделе о масштабировании.

Общий поток одного слоя:

Псевдокод обучения полного графа:

вход: X (n x m), edge_index (2 x |E|), веса W[1..L]
H = X
для l = 1..L:
    для каждого ребра (u -> v):
        m[u->v] = MSG(H[v], H[u], e_uv)          # сообщение
    для каждого узла v:
        agg[v] = ⊕ { m[u->v] : u из N(v) }        # инвариантная агрегация
        H'[v]  = σ( UPD(H[v], agg[v]) · W[l] )    # обновление
    H = H'
вернуть H

4. Зоопарк слоёв: чем они реально отличаются

Все популярные слои — это выбор конкретных MSG/AGG/UPD. Разберём четыре опорных.

GCN — Kipf & Welling, 2017

Самый цитируемый слой. Выводится как приближение первого порядка спектральной свёртки на графе, но итоговая формула проста:

$$H^{(l+1)} = \sigma\big(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2} H^{(l)} W^{(l)}\big), \qquad \tilde{A} = A + I,\ \ \tilde{D}_ {ii} = \textstyle\sum_j \tilde{A}_ {ij}$$

Поузловая запись: $h_v^{(l+1)} = \sigma\Big(\sum_{u \in \mathcal{N}(v) \cup {v}} \frac{1}{\sqrt{\hat d_v \hat d_u}} W h_u^{(l)}\Big)$.

Три инженерных решения внутри: петля $A + I$ (иначе узел теряет собственные признаки), симметричная нормализация (иначе хабы с миллионом рёбер взорвут норму активаций — вспомните разговор про нормализацию), общая матрица $W$ для себя и соседей. Последнее и есть слабость: GCN не может отличить «свой признак» от «признак соседа» — они складываются в один пул. Статья: arXiv:1609.02907.

GraphSAGE — Hamilton et al., 2017

Две идеи: разделить себя и соседей, и сэмплировать соседей вместо полного обхода.

$$h_v^{(l+1)} = \sigma\Big(W \cdot \big[,h_v^{(l)} ,|, \text{AGG}{h_u^{(l)}, u \in \mathcal{S}(v)},\big]\Big), \qquad h_v^{(l+1)} \leftarrow \frac{h_v^{(l+1)}}{|h_v^{(l+1)}|_ 2}$$

где $\mathcal{S}(v)$ — случайная выборка фиксированного размера (например, 25 соседей). Конкатенация вместо суммы решает проблему GCN; сэмплирование делает стоимость шага предсказуемой независимо от степени узла. Это первая по-настоящему индуктивная и масштабируемая GNN. arXiv:1706.02216.

GAT — Veličković et al., 2018

А если соседи не равноценны? Пусть модель сама решит, кого слушать — это внимание, ограниченное рёбрами графа:

$$e_{vu} = \text{LeakyReLU}\big(a^\top [W h_v ,|, W h_u]\big), \qquad \alpha_{vu} = \frac{\exp(e_{vu})}{\sum_{k \in \mathcal{N}(v)} \exp(e_{vk})}, \qquad h_v’ = \sigma\Big(\sum_{u} \alpha_{vu} W h_u\Big)$$

Плюс несколько голов, как в трансформере. Ключевое отличие от self-attention: softmax берётся не по всем узлам, а только по соседям — сложность $O(|E|)$, а не $O(n^2)$. GAT особенно хорош на зашумлённых графах, где часть рёбер — мусор: коэффициенты внимания их гасят. arXiv:1710.10903. Важная поправка: в исходном GAT внимание «статично» — ранжирование соседей одинаково для всех запросов; GATv2 (arXiv:2105.14491) переставляет нелинейность и чинит это. В PyG есть оба.

GIN — Xu et al., 2019

Спроектирован не ради точности, а ради выразительности (см. раздел 6):

$$h_v^{(l+1)} = \text{MLP}^{(l)}\Big((1 + \epsilon^{(l)}), h_v^{(l)} + \sum_{u \in \mathcal{N}(v)} h_u^{(l)}\Big)$$

Здесь важна именно сумма: mean теряет размер мультимножества (три одинаковых соседа неотличимы от одного), max теряет кратности вообще. GIN — стандартный базлайн для задач уровня графа (молекулы). arXiv:1810.00826.

Сводка выбора:

5. Реализация: сначала руками, потом библиотекой

Пишем слой GCN на голом PyTorch через разреженное умножение, чтобы было видно, что внутри нет магии.

import torch
import torch.nn as nn
import torch.nn.functional as F


def normalized_adj(edge_index: torch.Tensor, num_nodes: int) -> torch.Tensor:
    """Строит разреженную D^-1/2 (A + I) D^-1/2.

    edge_index: LongTensor [2, |E|] — граф считаем неориентированным,
    то есть оба направления уже присутствуют в списке рёбер.
    """
    # добавляем петли: узел обязан видеть собственные признаки
    loops = torch.arange(num_nodes, device=edge_index.device)
    loops = loops.unsqueeze(0).repeat(2, 1)
    ei = torch.cat([edge_index, loops], dim=1)

    row, col = ei[0], ei[1]
    deg = torch.zeros(num_nodes, device=ei.device)
    deg.scatter_add_(0, row, torch.ones_like(row, dtype=torch.float))
    d_inv_sqrt = deg.pow(-0.5)
    d_inv_sqrt[torch.isinf(d_inv_sqrt)] = 0.0   # изолированные узлы

    values = d_inv_sqrt[row] * d_inv_sqrt[col]  # вес каждого ребра
    return torch.sparse_coo_tensor(ei, values, (num_nodes, num_nodes)).coalesce()


class GCNLayer(nn.Module):
    def __init__(self, in_dim: int, out_dim: int):
        super().__init__()
        self.lin = nn.Linear(in_dim, out_dim, bias=True)
        # Glorot — стандарт для GCN: дисперсия сохраняется при усреднении
        nn.init.xavier_uniform_(self.lin.weight)
        nn.init.zeros_(self.lin.bias)

    def forward(self, x: torch.Tensor, adj: torch.Tensor) -> torch.Tensor:
        # ВАЖНО: сначала проекция (n x m -> n x d), потом распространение.
        # Обратный порядок даёт тот же результат, но стоит дороже при m > d.
        x = self.lin(x)                 # O(n * m * d)
        return torch.sparse.mm(adj, x)  # O(|E| * d)


class GCN(nn.Module):
    def __init__(self, in_dim, hid_dim, n_classes, dropout=0.5):
        super().__init__()
        self.l1 = GCNLayer(in_dim, hid_dim)
        self.l2 = GCNLayer(hid_dim, n_classes)
        self.dropout = dropout

    def forward(self, x, adj):
        x = F.relu(self.l1(x, adj))
        x = F.dropout(x, p=self.dropout, training=self.training)
        return self.l2(x, adj)          # логиты, softmax внутри cross_entropy

Обучение на цитатном графе (трансдуктивный режим: считаем forward по всем узлам, а лосс — только по размеченным):

model = GCN(in_dim=1433, hid_dim=64, n_classes=7)
opt = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)
adj = normalized_adj(data.edge_index, data.num_nodes)

for epoch in range(200):
    model.train()
    opt.zero_grad()
    out = model(data.x, adj)                       # forward по всему графу
    loss = F.cross_entropy(out[data.train_mask],   # лосс — только по train-узлам
                           data.y[data.train_mask])
    loss.backward()
    opt.step()

    model.eval()
    with torch.no_grad():
        pred = model(data.x, adj).argmax(dim=1)
        acc = (pred[data.val_mask] == data.y[data.val_mask]).float().mean()

Обратите внимание на weight_decay=5e-4 при всего 140 размеченных узлах в Cora: это классический случай, где регуляризация решает больше, чем архитектура.

Тот же смысл на PyTorch Geometric, где всё это уже написано и оптимизировано:

from torch_geometric.nn import GCNConv, SAGEConv, GATv2Conv, global_mean_pool


class Net(torch.nn.Module):
    def __init__(self, in_dim, hid, out):
        super().__init__()
        self.conv1 = GATv2Conv(in_dim, hid, heads=8, dropout=0.6)
        self.conv2 = GATv2Conv(hid * 8, out, heads=1, concat=False)

    def forward(self, x, edge_index):
        x = F.dropout(x, p=0.6, training=self.training)
        x = F.elu(self.conv1(x, edge_index))
        x = F.dropout(x, p=0.6, training=self.training)
        return self.conv2(x, edge_index)

Для задач уровня графа добавляется пулинг и батч из нескольких графов (PyG склеивает их в один большой блочно-диагональный граф, вектор batch говорит, какой узел какому графу принадлежит):

from torch_geometric.nn import GINConv, global_add_pool

def gin_layer(dim_in, dim_out):
    mlp = nn.Sequential(nn.Linear(dim_in, dim_out), nn.BatchNorm1d(dim_out),
                        nn.ReLU(), nn.Linear(dim_out, dim_out), nn.ReLU())
    return GINConv(mlp, train_eps=True)

# ...
h = global_add_pool(h, batch)   # sum-пулинг: сохраняет информацию о размере графа
logits = head(h)

Сложность

Для одного слоя с разреженным распространением, $d$ — размерность скрытого слоя:

• Время: $O(|E| \cdot d)$ на агрегацию $+\ O(n \cdot d^2)$ на линейное преобразование. На разреженных графах ($|E| \sim n\bar{d}$, $\bar d \ll d$) доминирует второе слагаемое, но узкое место по факту — нерегулярный доступ к памяти при gather/scatter, а не арифметика. GPU-утилизация у GNN обычно куда ниже, чем у CNN, именно поэтому.
• Память (full-batch): $O(L \cdot n \cdot d)$ на активации для обратного прохода плюс $O(|E|)$ на граф. Это и есть предел: граф на $10^8$ узлов при $d = 256$ и $L = 3$ требует ~300 ГБ активаций.
• GAT добавляет $O(|E| \cdot H)$ памяти на коэффициенты внимания ($H$ голов).

6. Пределы выразительности: барьер 1-WL

Неприятный сюрприз: message passing не всесилен, и его предел известен точно.

Тест Вейсфейлера — Лемана (1-WL) — классический эвристический алгоритм проверки изоморфизма графов: каждому узлу присваивается цвет, затем итеративно цвет пересчитывается как хеш от пары «свой цвет, мультимножество цветов соседей». Если гистограммы цветов двух графов разошлись — графы неизоморфны.

Это буквально message passing, только с хешем вместо нейросети. Отсюда теорема (Xu et al., Morris et al., 2019): никакая MPNN не различает графы, которые не различает 1-WL. GIN достигает этого предела, GCN и GraphSAGE — нет.

Практические следствия неприятные:

• MPNN не умеет считать циклы. Два несвязных треугольника и один шестиугольник (у всех узлов степень 2, все окрестности выглядят одинаково) для неё — один и тот же объект. Для химии это катастрофа: бензольное кольцо — цикл.
• MPNN не различает регулярные графы одной степени.
• MPNN не вычисляет расстояния между узлами, а значит слабо решает предсказание связей «в лоб» (два симметричных относительно графа узла получат одинаковые представления и одинаковый скор к любой цели).

Как чинят:

1. Структурные и позиционные кодировки — дописать к признакам узла то, что message passing вычислить не может: собственные векторы лапласиана (Laplacian PE), диагональ матрицы случайного блуждания (RWSE), число треугольников/циклов, степень. Дёшево, эффективно, стандарт де-факто.
2. Subgraph GNN — прогонять сеть по набору подграфов и агрегировать (ESAN, GNN-AK). Дороже, выразительнее.
3. Разметка целевых узлов — для предсказания связей пометить пару $(u,v)$ специальным признаком и работать с окрестностью пары: это подход SEAL (arXiv:1802.09691), который обходит проблему симметрии и стабильно бьёт наивный dot-product-декодер.
4. Высшие порядки WL ($k$-GNN) — теоретически сильнее, практически $O(n^k)$ и почти не применяются.

Практический вывод: если ваша задача завязана на подсчёт подструктур (циклы, клики, мотивы) — не ждите, что GNN выучит их сама. Посчитайте их заранее и подайте признаком.

7. Две болезни глубоких GNN

С CNN мы привыкли: больше слоёв — лучше. С GNN всё наоборот: типичная рабочая глубина — 2–4 слоя, и это не лень, а фундаментальное ограничение.

Переглаживание (over-smoothing)

Усреднение по соседям — это шаг диффузии. Повторите его много раз, и все узлы связной компоненты сойдутся к одному вектору, пропорциональному степеням узлов (стационарное распределение случайного блуждания). Представления становятся неразличимыми, точность падает. Li et al., 2018, arXiv:1801.07606 — первый строгий разбор.

Лечение:

• Остаточные связи и «начальный остаток»: GCNII подмешивает $h^{(0)}$ на каждом слое и делает identity-отображение весов, что позволяет обучать 64 слоя (arXiv:2007.02133).
• PairNorm / нормализация — явно удерживать попарные расстояния между узлами.
• DropEdge — случайно выбрасывать рёбра, замедляя диффузию (и заодно регуляризуя).
• Jumping Knowledge — конкатенировать выходы всех слоёв, чтобы классификатор сам выбрал нужный радиус.
• Самое частое и самое дешёвое: просто не делайте сеть глубокой.

Пережатие (over-squashing)

Проблема-близнец, но противоположная по природе. Чтобы узел получил информацию с расстояния $K$, она должна пройти через узкие места графа и уместиться в вектор фиксированной размерности $d$, тогда как количество узлов на расстоянии $K$ растёт экспоненциально. Градиент по дальним узлам затухает — прямой аналог проблемы долгих зависимостей в RNN. Alon & Yahav, arXiv:2006.05205 показали это на синтетической задаче NeighborsMatch, где обычные GNN проваливаются.

Лечение:

• Rewiring — менять граф: добавлять рёбра там, где узко. Формально узкость измеряется кривизной Риччи рёбер; SDRF (Topping et al., arXiv:2111.14522) хирургически добавляет рёбра в отрицательно искривлённых местах.
• Полносвязный последний слой — дешёвый хак из статьи Alon & Yahav: сделать последний слой глобальным.
• Виртуальный узел — добавить один узел, соединённый со всеми: диаметр графа становится 2. Стандартный приём в молекулярных бенчмарках.
• Graph transformer — глобальное внимание вместо распространения (раздел 9).

Важно понимать конфликт: переглаживание требует меньше распространения, пережатие — больше. Между ними и живёт настоящая инженерия GNN.

Ещё один частый провал, не связанный ни с тем, ни с другим: гетерофилия. GCN неявно предполагает, что соседи похожи (гомофилия — как в цитатных графах). Но в графе транзакций мошенник соседствует с жертвами, а не с мошенниками; в графе белков связываются противоположности. На таких данных GCN проигрывает обычному MLP на признаках узла. Диагностика — метрика гомофилии рёбер (доля рёбер между узлами одного класса); лечение — архитектуры с раздельными весами для себя и соседей, H2GCN, знаковое распространение, или высокочастотные фильтры.

8. Масштабирование: от Cora до миллиардов рёбер

Full-batch GCN на Cora (2708 узлов) обучается за секунды на ноутбуке. Продакшн-граф на $10^9$ рёбер в память не влезает, и наивный мини-батч не помогает: чтобы посчитать один узел на 3 слоях, нужны все его 3-хоповые соседи, а это в социальном графе — половина графа («экспоненциальный взрыв соседей»).

Четыре зрелых подхода:

Мини-батч через NeighborLoader в PyG:

from torch_geometric.loader import NeighborLoader

loader = NeighborLoader(
    data,
    num_neighbors=[15, 10],       # fanout по слоям: 15 на первом хопе, 10 на втором
    batch_size=1024,              # 1024 «целевых» узла на батч
    input_nodes=data.train_mask,
    shuffle=True,
    num_workers=4,
)

for batch in loader:
    opt.zero_grad()
    out = model(batch.x, batch.edge_index)
    # ключевая деталь: первые batch.batch_size узлов — целевые,
    # остальные подтянуты только как контекст, лосс по ним считать НЕЛЬЗЯ
    loss = F.cross_entropy(out[:batch.batch_size],
                           batch.y[:batch.batch_size])
    loss.backward()
    opt.step()

Стоимость батча: $O(B \cdot \prod_l f_l \cdot d)$, где $f_l$ — fanout слоя $l$. Для [15, 10] и $B = 1024$ это ~150 тыс. узлов в развёрнутом дереве — уже ощутимо, а [25, 10, 10] даст 2.5 млн и упрётся в память. Отсюда правило: fanout убывает с глубиной, и три хопа — практический потолок для больших графов.

Отдельная боль — инференс в реальном времени. Полный обход двух хопов по горячему графу за 50 мс SLA невозможен, поэтому в проде почти всегда разделяют пути:

Эта схема — по сути PinSage в Pinterest: тяжёлый GNN считает эмбеддинги офлайн на MapReduce-кластере (3 млрд узлов, 18 млрд рёбер), а онлайн остаётся только поиск ближайших соседей. Отдельно отметим, что PinSage сэмплирует соседей не равномерно, а по весам персонализированного PageRank — это заметно лучше случайной выборки на графах с хабами. arXiv:1806.01973.

9. Предсказание связей — и главная ловушка в нём

Самая денежная задача на графах: «какой товар порекомендовать», «каких людей показать в разделе «Вы можете знать»», «какой факт добавить в граф знаний».

Схема encoder-decoder: GNN даёт $h_u, h_v$, декодер превращает пару в скор.

class LinkPredictor(nn.Module):
    def __init__(self, in_dim, hid):
        super().__init__()
        self.enc = Net(in_dim, hid, hid)          # любая GNN-энкодер
        self.dec = nn.Sequential(nn.Linear(2 * hid, hid), nn.ReLU(),
                                 nn.Linear(hid, 1))

    def forward(self, x, message_edges, target_edges):
        # message_edges — рёбра, ПО КОТОРЫМ распространяем сообщения
        # target_edges  — рёбра, КОТОРЫЕ предсказываем; пересекаться не должны
        h = self.enc(x, message_edges)
        u, v = target_edges
        return self.dec(torch.cat([h[u], h[v]], dim=-1)).squeeze(-1)


def loss_fn(model, x, message_edges, pos_edges, num_nodes, k_neg=1):
    pos = model(x, message_edges, pos_edges)
    # негативы: случайные несуществующие рёбра; на практике полезнее «hard negatives» —
    # узлы, близкие по популярности/категории, иначе задача слишком лёгкая
    neg_edges = torch.randint(0, num_nodes, (2, pos_edges.size(1) * k_neg),
                              device=x.device)
    neg = model(x, message_edges, neg_edges)
    return (F.binary_cross_entropy_with_logits(pos, torch.ones_like(pos)) +
            F.binary_cross_entropy_with_logits(neg, torch.zeros_like(neg)))

Ловушка №1 — утечка через рёбра. Если ребро $(u,v)$ есть и в message_edges, и в target_edges, модель просто «подсматривает» ответ: она агрегирует $h_v$ в $h_u$ по тому самому ребру, которое должна предсказать. Валидационная метрика взлетает до 0.99 AUC, продакшн умирает. Ребро-цель обязано быть удалено из графа распространения. В PyG для этого есть RandomLinkSplit(..., disjoint_train_ratio=...) — используйте его, а не самописный split.

Ловушка №2 — временная утечка. На динамическом графе разбиение должно быть по времени, а не случайным: рёбра из будущего не имеют права участвовать в предсказании прошлого. Случайный split на графе транзакций даёт метрику, которая не воспроизводится ни в одном A/B.

Ловушка №3 — метрика. Accuracy бессмысленна при доле положительных $10^{-6}$. Смотрите Hits@K, MRR, AUC-PR — и обязательно сравнивайте с честными базлайнами: Adamic-Adar, common neighbors, популярность. На многих графах простая эвристика общих соседей бьёт GNN, и это нормальный результат, о котором надо знать до релиза, а не после.

10. Связь с трансформерами

Полезно осознать: self-attention — это GNN на полном графе. Токены — узлы, внимание — обучаемые веса рёбер, позиционное кодирование — способ вернуть структуру, которую полный граф потерял.

Отсюда мост в обе стороны. Со стороны графов: если MPNN страдает от пережатия и ограничена 1-WL, почему бы не взять глобальное внимание? Graph transformers так и делают, но теряют информацию о связях, поэтому вкладывают её в кодировки:

• Graphormer (arXiv:2106.05234) — три вида смещений: по степени узла, по длине кратчайшего пути между парой, по признакам рёбер на пути. Выиграл OGB-LSC PCQM4M.
• GraphGPS (arXiv:2205.12454) — гибрид: на каждом слое параллельно локальный MPNN и глобальное внимание, результаты складываются. Сейчас это разумный дефолт для средних графов.

Цена — $O(n^2)$: графовые трансформеры работают на молекулах (десятки атомов) и не работают на социальном графе на $10^8$ узлов. Там по-прежнему правит сэмплирующий message passing.

Обратно: идея «внимание, ограниченное графом» — это и есть разреженное внимание, которое в LLM применяют для длинного контекста (см. большие языковые модели).

11. Как это выглядит в проде

Что реально работает и приносит деньги:

Рекомендации. Pinterest (PinSage), Alibaba, Uber Eats, Twitter. Ключевой выигрыш не в замене ранжировщика, а в генерации кандидатов: GNN-эмбеддинги + ANN-индекс дают лучший recall на длинном хвосте, чем коллаборативная фильтрация, и переносятся на новые товары (холодный старт), потому что учат функцию от признаков и связей, а не таблицу.

Антифрод и AML. Мошенничество — по природе групповое явление: фермы аккаунтов, кольцевые переводы, общие устройства и адреса. Табличная модель видит одну транзакцию, GNN видит структуру. Практическая тонкость — сильная гетерофилия и экстремальный дисбаланс классов, так что нужны специальные архитектуры и взвешенные лоссы.

Химия и биология. Предсказание свойств молекул — задача уровня графа, на которой GNN стали стандартом после MPNN (Gilmer et al., 2017). Громкий результат — открытие антибиотика галицина: модель на графах молекул отранжировала библиотеку соединений, и топ-кандидат оказался работающим антибиотиком (Stokes et al., Cell 2020). Внутри AlphaFold — по сути обучение на графе взаимодействий остатков.

Инфраструктура и физика. Google Maps использует GNN для прогноза времени прибытия: дорожная сеть режется на «суперсегменты», и GNN предсказывает время проезда; в ряде городов ошибка сократилась примерно на 20–50% (arXiv:2108.11482). Похожие модели предсказывают динамику частиц, нагрузку в энергосетях, погоду (GraphCast).

Код и безопасность. Граф зависимостей, AST, control-flow graph — естественные графы; GNN применяют для поиска уязвимостей и типовых багов.

12. Типичные ошибки

1. Строить GNN там, где хватает градиентного бустинга. Если сигнал целиком в признаках узла, а граф случаен — GNN проиграет CatBoost и по метрике, и по стоимости эксплуатации. Проверьте гомофилию и сравните с базлайном «MLP без графа» до того, как строить пайплайн.
2. Забыть петли и нормализацию. Без $A+I$ узел не видит себя; без нормализации хабы взрывают активации.
3. Строить слишком глубокую сеть. 8 слоёв GCN почти гарантированно хуже двух.
4. Утечка через целевые рёбра в предсказании связей (раздел 9) — самая дорогая ошибка в этой области.
5. Случайный split вместо временного на динамических графах.
6. Mean-агрегация там, где важна кратность. Если «10 переводов на один счёт» отличается от «1 перевода», mean это стирает — нужна сумма или явный признак степени.
7. Игнорирование направленности рёбер. Библиотеки часто ожидают, что неориентированный граф записан двумя направленными рёбрами. Забыли — половина графа не участвует в распространении, и это молчаливая ошибка.
8. Обучение на full-batch и инференс на сэмплированной окрестности (или наоборот) — рассогласование распределений; проверяйте, что train и serving видят один и тот же вид окрестности.
9. Одинаковый dropout как в CNN. GNN на маленьких графах переобучаются мгновенно; рабочие значения dropout 0.5–0.6 плюс weight decay — не перестраховка.
10. Оценка на Cora/Citeseer как доказательство. Эти датасеты крошечные, дисперсия по сплитам огромна; для серьёзных выводов есть OGB (arXiv:2005.00687).

Мини-итог

• Граф — это данные без канонического порядка; правильный индуктивный сдвиг — эквивариантность к перестановке узлов, из которой напрямую следует передача сообщений.
• Один слой = один хоп. Все популярные архитектуры — это разные MSG/AGG/UPD: GCN (нормализованное среднее), GraphSAGE (конкатенация + сэмплирование), GAT (внимание по рёбрам), GIN (сумма + MLP).
• Стоимость слоя $O(|E|d + nd^2)$, узкое место — нерегулярный доступ к памяти.
• Выразительность MPNN ограничена сверху тестом 1-WL: циклы и расстояния надо подавать признаками, а не надеяться, что модель их выучит.
• Глубина ограничена переглаживанием сверху и пережатием снизу; рабочий диапазон 2–4 слоя, дальше — остаточные связи, rewiring или глобальное внимание.
• В проде почти всегда: офлайн-вычисление эмбеддингов + ANN-индекс онлайн, сэмплирование соседей при обучении, и очень аккуратные сплиты.

Источники

• Hamilton W. Graph Representation Learning Book — лучший учебник по теме, бесплатно: cs.mcgill.ca/~wlh/grl_book
• Sanchez-Lengeling B. et al. A Gentle Introduction to GNNs — интерактивно: distill.pub/2021/gnn-intro
• Kipf T., Welling M. Semi-Supervised Classification with GCN, 2017 — arXiv:1609.02907
• Hamilton W. et al. Inductive Representation Learning on Large Graphs, 2017 — arXiv:1706.02216
• Veličković P. et al. Graph Attention Networks, 2018 — arXiv:1710.10903
• Xu K. et al. How Powerful are Graph Neural Networks?, 2019 — arXiv:1810.00826
• Gilmer J. et al. Neural Message Passing for Quantum Chemistry, 2017 — arXiv:1704.01212
• Alon U., Yahav E. On the Bottleneck of GNNs, 2021 — arXiv:2006.05205
• Chiang W.-L. et al. Cluster-GCN, 2019 — arXiv:1905.07953
• Zeng H. et al. GraphSAINT, 2020 — arXiv:1907.04931
• Schlichtkrull M. et al. Modeling Relational Data with R-GCN, 2017 — arXiv:1703.06103
• Bronstein M. et al. Geometric Deep Learning, 2021 — arXiv:2104.13478
• Документация: PyTorch Geometric, DGL, бенчмарки OGB
• Курс Stanford CS224W Machine Learning with Graphs — web.stanford.edu/class/cs224w

Что дальше

Мы всё время говорили «представление узла» — вектор, в который сеть сжимает объект вместе с его контекстом. Это та же сущность, что эмбеддинг слова в NLP и вектор изображения из CNN: универсальная валюта современного глубокого обучения. Дальше — Эмбеддинги и обучение представлений: как их обучают без разметки, что такое контрастивное обучение, почему косинусная близость работает и как всё это связано с поиском и генеративными моделями.