Что общего между молекулой кофеина, сценой из «Отелло» и пикселем в фотографии? Все они — графы: наборы объектов, связанных отношениями. А если данные можно описать графом, их можно и обучить предсказывать с помощью Graph Neural Networks.

Что такое граф и почему он везде

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

Возьмём молекулу. Атомы — узлы, ковалентные связи — рёбра. У каждого атома есть тип (углерод, азот, кислород), у каждой связи — кратность (одинарная, двойная, ароматическая). Социальная сеть — люди и их взаимодействия. Сеть цитирования — статьи и ссылки между ними. Даже изображение можно представить как граф, где каждый пиксель связан с восемью соседями, а текст — как цепочку символов, где каждый связан со следующим.

Разница между изображением, текстом и «настоящим» графом в регулярности. У пикселей всегда ровно восемь соседей, у символа — ровно два. У атома в молекуле соседей может быть два, три, четыре — сколько угодно. Именно эта переменная связность делает графы мощным, но сложным форматом данных.

Какие задачи решают GNN

Задачи на графах делятся на три уровня. Графовый уровень — предсказать свойство всей структуры целиком. Пахнет ли молекула резко? Содержит ли граф два кольца? Это аналог классификации изображения или анализа тональности текста.

Узловой уровень — определить роль каждого узла. Классический пример — клуб карате Зака. После раскола между инструктором и администратором каждый член клуба должен был выбрать сторону. Задача GNN — предсказать, к кому примкнёт каждый участник, основываясь на его связях в социальном графе. Это как сегментация изображения, только для узлов.

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

Почему графы сложно скормить нейросети

Нейросети любят прямоугольные массивы: тензоры фиксированной формы. Графы же непостоянны: в одном графе сто узлов, в другом — миллион. Узлы имеют разное число соседей, и нет естественного порядка перечисления узлов.

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

Решение — список смежности. Вместо хранения всех n² возможных связей храним только реальные рёбра в виде пар индексов (i, j). Это компактно, масштабируемо и не зависит от порядка узлов.

Самая простая GNN: граф на входе, граф на выходе

Базовая архитектура GNN работает по принципу «граф внутрь, граф наружу». На вход подаётся граф с векторами, прикреплёнными к узлам, рёбрам и глобальному контексту. Каждый слой GNN по отдельности обновляет эти векторы с помощью многослойного перцептрона (MLP), не меняя саму структуру связей.

После первого слоя граф выглядит так же, но векторы стали более информативными. После второго — ещё более. Сколько угодно слоёв можно наложить друг на друга, и каждый раз узлы, рёбра и глобальный контекст обогащаются новыми представлениями. Но пока мы не использовали главное — связи между узлами.

Pooling: как собирать информацию из соседей

Представим, что у нас есть векторы только для рёбер, а предсказать нужно для узлов. Как передать информацию? Через pooling — сбор и агрегацию. Для каждого узла собираем векторы всех примыкающих рёбер, объединяем их в матрицу и сворачиваем в один вектор операцией агрегации.

Три основных варианта агрегации — sum, mean и max. Sum даёт снимок локального распределения признаков и подчёркивает выбросы. Mean нормализует по числу соседей, полезен при сильно разном количестве связей. Max выделяет наиболее заметный признак в окрестности. На практике sum используется чаще всего, но универсального победителя нет — выбор зависит от данных.

Pooling работает в любом направлении: от рёбер к узлам, от узлов к рёбрам, от всего графа к глобальному вектору. Это позволяет строить предсказания даже когда информация и цель находятся на разных уровнях графа.

Message passing: когда соседи учат друг друга

Чтобы задействовать связность прямо внутри слоя, а не только на этапе предсказания, применяют message passing — передачу сообщений. Каждый узел собирает векторы своих соседей, агрегирует их и пропускает через обучаемую функцию обновления. После одного такого шага узел «знает» о своих ближайших соседях. После двух — о соседях соседей. После k слоёв — обо всём графе в пределах k шагов.

Это напоминает свёртку в CNN: там пиксель агрегирует информацию соседей в фиксированном окне 3×3, здесь узел — с переменным числом соседей. Разница лишь в том, что окно у графа непостоянно.

Можно усложнить: передавать сообщения не только между узлами, но и между узлами и рёбрами. Сначала ребро готовит сообщение из своих векторов и векторов примыкающих узлов, затем передаёт его узлам. Так работает архитектура MPNN — Message Passing Neural Network. Можно чередовать обновления узлов и рёбер в разном порядке, или делать это параллельно в стиле weave-архитектуры.

Глобальное представление: мост между далёкими узлами

У message passing есть ограничение: за k слоёв информация проходит не дальше k рёбер. Если два узла сидят на противоположных концах большого графа, они никогда не обменяются сигналами. Решение — глобальное представление (master node, context vector). Это отдельный вектор, связанный со всеми узлами и рёбрами графа.

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

Чему учит практика: эмпирические уроки

Исследователи из Distill.pub провели масштабное исследование архитектурных выборов GNN на задаче предсказания запаха молекул. Несколько выводов оказались неочевидными.

Во-первых, GNN крайне параметроэффективны. Даже модель с тремя тысячами параметров может показывать высокую точность. Во-вторых, лучшие модели — не самые глубокие. Оптимальная глубина — два слоя, а не три или четыре. Большая глубина размывает представления узлов из-за чрезмерного числа итераций message passing.

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

За пределами базовой архитектуры

Современные GNN выходят далеко за рамки описанного шаблона. Graph Attention Networks (GAT) заменяют равноправное усреднение соседей на взвешенное, где веса вычисляются через scoring-функцию между парами узлов. Это позволяет модели фокусироваться на наиболее релевантных связях.

Трансформеры можно рассматривать как частный случай GNN: полносвязный граф, где attention назначает вес каждой паре узлов. Разница в том, что GNN предполагает разреженную связность, а трансформер моделирует все возможные связи.

Для больших графов применяют сэмплирование: вместо обработки всего графа берут подграфы вокруг случайных узлов. Это позволяет обучать модели батчами фиксированного размера, как в обычном deep learning. Методы Cluster-GCN и GraphSaint строят подграфы так, чтобы сохранить структурные свойства исходного графа.

Для интерпретируемости используют GNNExplainer — метод, который выделяет подграф, наиболее важный для конкретного предсказания. Это критично в научных приложениях, где нужно понимать, почему модель считает молекулу токсичной, а не просто доверять её вердикту.

Где GNN уже работают

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

Каждое из этих применений опирается на одну и ту же идею: если мир вокруг нас состоит из объектов и их связей, то нейросеть, умеющая мыслить связями, будет естественным выбором.

Часто задаваемые вопросы

В чём главное отличие GNN от обычных нейросетей?

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

Можно ли применить GNN к тексту или изображениям?

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

Почему глубокие GNN часто хуже?

С каждым слоем message passing представления узлов размываются из-за усреднения соседей. После четырёх слоёв локальные особенности теряются, и модель начинает переобучаться. На практике оптимальная глубина редко превышает два-три слоя.

Итог

Graph Neural Networks — это не просто ещё один тип нейросети. Это способ мыслить о данных через связи, а не через изолированные объекты. Если ваши данные естественно описываются графом — молекулы, сети, знания — GNN дают реляционный индуктивный bias, который другие архитектуры не обеспечат. Начать стоит с простого: MLP на узлах, pooling для сбора информации, message passing для обмена между соседями. А дальше — внимание, глобальные представления, сэмплирование и генеративные модели. Графы окружают нас повсюду. Пора научить нейросети их видеть.