Graph Neural Network (GNN)

Графовая нейронная сеть (GNN) — это нейронная сеть, которая работает непосредственно с графами: наборами узлов, соединённых рёбрами, причём узлы и рёбра могут содержать признаки. Молекулы (атомы и связи), социальные сети (пользователи и подписки), дорожные сети (перекрёстки и участки дорог), трёхмерные сетки и суставы человеческого скелета — всё это графы. У графа нет фиксированной сетки или порядка, а у узлов разное число соседей, поэтому свёрточные фильтры свёрточной нейронной сети (CNN) и пошаговая обработка рекуррентной нейронной сетью (RNN) напрямую не подходят. GNN решают эту задачу с помощью передачи сообщений: каждый узел многократно обновляет свой вектор признаков на основе векторов соседей, создавая эмбеддинги узлов, которые кодируют как собственные атрибуты узла, так и его положение в графе.

Как работает передача сообщений#

Слой GNN обновляет каждый узел за три шага. Каждый сосед отправляет сообщение — обычно это обучаемое преобразование его признаков. Узел объединяет входящие сообщения функцией, не зависящей от их порядка, например суммой, средним или максимумом. Затем узел объединяет результат со своими признаками, формируя новое представление. Поскольку агрегирование не зависит от порядка, результат не зависит от нумерации узлов. В 2017 году Джастин Гилмер и его коллеги описали многие GNN как частные случаи подхода нейронных сетей с передачей сообщений. После последнего слоя специализированная для задачи выходная голова использует эмбеддинги узлов, чтобы присвоить метки узлам, предсказать отсутствующие рёбра или классифицировать граф целиком:

Каждый слой расширяет область видимости узла на одно ребро, поэтому после k слоёв эмбеддинг узла зависит от всех узлов в пределах k рёбер — это его рецептивное поле в графе. Приведённый ниже фрагмент кода на PyTorch строит путь из шести узлов, применяет три слоя графовой свёртки с нормализацией из GCN Томаса Кипфа и Макса Веллинга и использует autograd, чтобы перечислить входные узлы, влияющие на узел 0 после каждого слоя:

import torch
from torch import nn

# A path graph 0-1-2-3-4-5 as an adjacency matrix with self-loops
A = torch.eye(6)
for i in range(5):
    A[i, i + 1] = A[i + 1, i] = 1
deg = A.sum(dim=1)
A_hat = A / torch.sqrt(deg[:, None] * deg[None, :])  # GCN normalization D^-1/2 (A + I) D^-1/2

torch.manual_seed(0)
x = torch.randn(6, 4, requires_grad=True)  # 4 input features per node
layers = [nn.Linear(4, 4) for _ in range(3)]

h = x
for k, layer in enumerate(layers, start=1):
    h = torch.tanh(A_hat @ layer(h))  # each node mixes in its neighbors' transformed features
    grad = torch.autograd.grad(h[0].sum(), x, retain_graph=True)[0]
    print(f"After layer {k}, node 0 depends on nodes {grad.abs().sum(dim=1).nonzero().flatten().tolist()}")

Вывод: [0, 1], [0, 1, 2] и [0, 1, 2, 3]: рецептивное поле узла 0 расширяется ровно на одно ребро с каждым слоем.

Распространённые архитектуры GNN#

• GCN: Графовая свёрточная сеть вычисляет H′ = σ(D̃^(−1/2) Ã D̃^(−1/2) H W), где Ã — матрица смежности с петлями, а D̃ — матрица степеней: это среднее по узлу и его соседям с весами, зависящими от степеней, за которым следует матрица весов W, общая для всех узлов.
• GraphSAGE: Сэмплирует фиксированное число соседей для каждого узла и обучает агрегатор, поэтому масштабируется на очень большие графы и позволяет строить эмбеддинги узлов, появившихся после обучения.
• GAT: Графовые сети с механизмом внимания присваивают каждому соседу вес на основе обучаемых оценок внимания, а не фиксированных весов, зависящих от степени узла.
• GIN: Сеть графовых изоморфизмов суммирует представления соседей и применяет MLP. Кеюлу Сюй и его коллеги доказали, что такая сеть различает графы не хуже теста Вайсфейлера — Лемана, который задаёт верхнюю границу возможностей стандартного обмена сообщениями.
• Графовые трансформеры: Применяют самовнимание ко всем узлам и добавляют позиционные кодировки, полученные из структуры графа. Стандартный трансформер сам по себе является GNN на полном графе токенов.

При большом числе слоёв возникает чрезмерное сглаживание: повторное усреднение сближает эмбеддинги узлов, пока они не становятся неразличимыми. Поэтому многие GNN используют всего два или три слоя — как и исходная GCN, в которой их было два. PyTorch Geometric и Deep Graph Library (DGL) эффективно реализуют эти слои для разреженных списков рёбер.

Примеры применения в реальных условиях#

• Прогноз погоды: Модель GraphCast от Google DeepMind, опубликованная в журнале Science в 2023 году, выполняет передачу сообщений по многоуровневой сетке, охватывающей весь земной шар, и менее чем за минуту строит прогноз на 10 дней с разрешением 0,25°. На 90% из 1380 проверочных целевых показателей она превосходит самые точные действующие детерминированные системы.
• Поиск лекарств: В 2020 году исследователи MIT обучили сеть с направленной передачей сообщений предсказывать антибактериальную активность по молекулярным графам. С её помощью они обнаружили галицин — соединение, структурно не похожее на известные антибиотики, которое в лабораторных испытаниях уничтожало множество бактерий, устойчивых к лекарствам.
• Рекомендательные системы: Модель PinSage от Pinterest обучила эмбеддинги пинов на графе из 3 миллиардов пинов и досок с 18 миллиардами рёбер, используя для обучения 7,5 миллиарда примеров.
• Распознавание действий по скелету: ST-GCN рассматривает суставы тела как узлы, связывает их костями в каждом кадре и соединяет каждый сустав с тем же суставом в соседних кадрах, а затем классифицирует действие по полученному пространственно-временному графу. Модели оценки позы YOLO26 возвращают 17 ключевых точек COCO для каждого человека в каждом кадре — координаты суставов, по которым строится такой скелетный граф.

GNN и смежные понятия#

• Граф знаний: Структура данных, которая хранит факты в виде троек «сущность — отношение — сущность». GNN — это модель, способная обучаться на графе знаний, например предсказывать отсутствующие связи.
• Геометрическое глубокое обучение: Область, изучающая сети, построенные с учётом симметрий данных; она охватывает CNN на сетках, GNN на графах, а также модели на сетках и многообразиях.
• CNN: CNN, применённая к изображению, — частный случай передачи сообщений на решёточном графе. У каждого пикселя одинаковое число соседей в фиксированных относительных позициях, поэтому CNN может обучить отдельный вес для каждой позиции соседа, чего GNN на нерегулярном графе сделать не может.