Графовая нейронная сеть

Материал из MachineLearning.

Текущая версия

Статья написана с использованием LLM Claude Sonnet 3.5 и DeepSeek V4-Flash и проверена участником Dan-Кhaiaa Lakpazhap 20:16, 30 июня 2026 (MSD). Промпт приводится полностью в Обсуждение:Графовая нейронная сеть.

Гра́фовая нейро́нная сеть (англ. Graph Neural Network, GNN) — класс искусственных нейронных сетей, предназначенных для работы с данными, представленными в виде графа: с вершинами (узлами) и рёбрами, которые задают произвольные, не обязательно регулярные связи между объектами. В отличие от свёрточных нейронных сетей (работающих с сеткой пикселей) и рекуррентных сетей (работающих с последовательностями), графовые нейронные сети обобщают идею локальной свёртки на данные без фиксированной структуры соседства, что делает их естественным инструментом машинного обучения на социальных сетях, молекулах, дорожных сетях, рекомендательных системах, базах знаний и других графовых структурах^[1][1].

Ключевая идея GNN — передача сообщений (англ. message passing): каждая вершина итеративно обновляет своё векторное представление (эмбеддинг), агрегируя информацию от своих соседей. После нескольких раундов такого обновления представление вершины отражает не только её собственные признаки, но и структуру её локального (а при достаточной глубине — и более широкого) окружения в графе^[1].

История

Идея применения нейронных сетей к графовым данным восходит к работам конца 1990-х — начала 2000-х годов о рекурсивных нейронных сетях для обработки направленных ациклических графов^[1]. Термин «графовая нейронная сеть» и первая общая формализация модели, способной обрабатывать произвольные (в том числе циклические) графы через итеративный процесс распространения состояния до достижения неподвижной точки, были предложены Марко Гори, Габриэле Монфардини и Франко Скарселли в 2005 году^[1], а в развёрнутом виде — в статье Скарселли и соавторов 2009 года The Graph Neural Network Model^[1].

Современный этап развития начался с переноса идей свёртки на графы. В 2013—2014 годах появились спектральные графовые свёртки, определяемые через спектр графового лапласиана^[1]; в 2016 году Деффар, Брессон и Вандергейнст предложили эффективное приближение спектральных фильтров через полиномы Чебышёва (ChebNet)^[1]. Переломным моментом стала статья Томаса Кипфа и Макса Веллинга 2017 года, упростившая спектральный подход до простого и эффективного слоя — графовой свёрточной сети (GCN)^[1], после чего число публикаций по GNN стало расти экспоненциально. В последующие годы были предложены индуктивная модель GraphSAGE^[1], механизм внимания на графах GAT^[1], единый фреймворк сетей передачи сообщений (MPNN)^[1] и теоретически наиболее выразительная в своём классе графовая изоморфная сеть (GIN)^[1].

Формальные основания

Представление графа

Граф задаётся парой , где — множество вершин, а — множество рёбер. Структуру связей часто удобно описывать матрицей смежности размера , а признаки вершин — матрицей , где строка — вектор признаков вершины . Рёбра также могут иметь собственные признаки (например, тип связи или вес), а граф в целом может быть направленным, взвешенным, гетерогенным (с несколькими типами вершин и рёбер) или динамическим (меняющимся во времени)^[1].

Три типа задач

Задачи, решаемые GNN, обычно делят на три уровня^[1]:

• на уровне вершины (англ. node-level) — например, классификация вершин (предсказание категории пользователя в социальной сети) или регрессия на вершинах;
• на уровне ребра (англ. edge-level) — например, предсказание связей (англ. link prediction), то есть оценка вероятности существования ребра между двумя вершинами;
• на уровне графа (англ. graph-level) — классификация или регрессия над графом целиком, например предсказание свойства молекулы по её структуре.

Передача сообщений

Большинство современных архитектур GNN укладываются в единую вычислительную схему — фреймворк сетей передачи сообщений (англ. Message Passing Neural Networks, MPNN), предложенный Гилмером и соавторами^[1]. На каждом слое представление вершины обновляется по правилу

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

Для задач уровня графа итоговые представления вершин объединяются функцией считывания (англ. readout), например суммированием или более сложным дифференцируемым пулингом:

Основные архитектуры

Спектральные графовые свёрточные сети

Первый подход к обобщению свёртки на графы опирался на теорию обработки сигналов на графах: свёртка определялась как операция в спектральной области, заданной собственными векторами лапласиана графа^[1]. Такой подход требовал дорогостоящего разложения матрицы и был плохо переносим между графами разной структуры. Деффар и соавторы предложили аппроксимировать спектральные фильтры полиномами Чебышёва степени , что позволило вычислять свёртку локально, без явного разложения лапласиана^[1].

Графовая свёрточная сеть (GCN)

Кипф и Веллинг показали, что при ограничении полинома Чебышёва первым порядком спектральный фильтр упрощается до одного линейного слоя, действующего на всю матрицу признаков^[1]:

где — матрица смежности с добавленными петлями (самопересылка), — соответствующая ей диагональная матрица степеней, — обучаемая матрица весов слоя, а — нелинейная функция активации (обычно ReLU). Эта модель, известная как GCN, стала одной из самых цитируемых работ в области и фактическим ориентиром для последующих архитектур благодаря простоте и хорошей масштабируемости^[1].

GraphSAGE

Модель GCN исходно является трансдуктивной: она обучается сразу на всём графе, включая тестовые вершины, и плохо переносится на новые, ранее не виденные вершины. Хэмилтон, Ин и Лесковец предложили GraphSAGE (от SAmple and aggreGatE) — индуктивный подход, в котором для каждой вершины на каждом слое выбирается (сэмплируется) фиксированное число соседей, а функция агрегации обучается один раз и применяется затем к произвольным, в том числе ранее не встречавшимся, вершинам и графам^[1]:

Это сделало GNN применимыми к очень большим и постоянно растущим графам, например к промышленным рекомендательным системам^[1].

Графовые сети внимания (GAT)

Велкович и соавторы предложили заменить фиксированные (нормированные по степени) веса соседей на веса, вычисляемые механизмом внимания, — по аналогии с трансформерами^[1]. Коэффициент внимания между вершинами и вычисляется как

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

Сети передачи сообщений и графовая изоморфная сеть (GIN)

Гилмер и соавторы обобщили GCN, GraphSAGE, GAT и ряд других моделей (в том числе более ранние управляемые графовые сети, Gated Graph Neural Networks^[1]) в единый фреймворк MPNN, включающий также признаки на рёбрах, что оказалось особенно полезным для задач хемоинформатики — предсказания свойств молекул^[1].

Отдельный теоретический вопрос — какова предельная различающая способность GNN. Сю, Ху, Лесковец и Йегелка показали, что стандартные архитектуры (GCN, GraphSAGE) не могут различать некоторые простые, но неизоморфные графы, и что различающая способность любой GNN с передачей сообщений ограничена сверху классическим комбинаторным тестом Вейсфейлера — Лемана на изоморфизм графов. Они предложили графовую изоморфную сеть (англ. Graph Isomorphism Network, GIN) с агрегирующей функцией

которая при подходящем выборе доказуемо достигает различающей способности, равной тесту Вейсфейлера — Лемана, то есть является максимально мощной в классе GNN на основе суммирующей агрегации^[1].

Обучение

Трансдуктивная и индуктивная постановки

В трансдуктивном сценарии обучения модель видит весь граф целиком (включая признаки и связи тестовых вершин), но не видит их меток; типичный пример — классификация вершин одного большого графа цитирования. В индуктивном сценарии модель должна уметь строить представления для вершин и графов, отсутствовавших на этапе обучения, — например, для новых пользователей социальной сети или новых молекул^[1].

Функции потерь

Как и в остальном глубоком обучении, параметры GNN оптимизируются методом обратного распространения ошибки и вариантами стохастического градиентного спуска. Выбор функции потерь зависит от задачи: перекрёстная энтропия для классификации вершин, рёбер или графов; среднеквадратичная ошибка для регрессии; при отсутствии размеченных данных применяются задачи самообучения (англ. self-supervised learning), например реконструкция скрытых рёбер или максимизация взаимной информации между локальными и глобальными представлениями графа (Deep Graph Infomax).

Масштабирование на больших графах

Полный проход по всему графу на каждом шаге обучения неприменим для графов из миллионов и миллиардов вершин. Для решения этой проблемы применяются сэмплирование соседей (GraphSAGE)^[1], сэмплирование подграфов (например, кластеризация графа перед формированием мини-пакетов) и другие методы приближённого вычисления градиента.

Проблемы и ограничения

Переобучение сглаживанием (over-smoothing)

При увеличении числа слоёв GNN представления разных, даже далёких друг от друга вершин имеют тенденцию становиться неразличимыми — этот эффект называют переобучением сглаживанием (англ. over-smoothing). Ли, Хань и Ву показали, что операция свёртки в GCN эквивалентна разновидности лапласова сглаживания признаков, из-за чего глубокие GCN быстро теряют дискриминативную способность^[1]. Уно и Судзуки формально доказали, что с ростом глубины информация об исходных признаках и локальной структуре графа экспоненциально затухает, если не используются пропускающие соединения или другие компенсирующие механизмы^[1].

Over-squashing («переобжатие» информации)

Алон и Яхав описали смежную проблему — over-squashing: при передаче сообщений через «узкие места» графа (например, длинные пути или мосты) экспоненциально растущий объём информации из дальней окрестности вынужденно «сжимается» в вектор фиксированной размерности, что искажает или теряет часть сигнала и ограничивает способность GNN учитывать дальние взаимодействия между вершинами^[1].

Устойчивость

Как и другие нейросетевые модели, GNN уязвимы к состязательным (adversarial) возмущениям — небольшим изменениям структуры графа или признаков вершин, способным существенно изменить предсказание модели, что породило отдельное направление исследований по устойчивости и защите графовых моделей.

Применения

• Химия и науки о материалах — предсказание физико-химических свойств молекул и поиск новых соединений на основе их графового представления (атомы — вершины, связи — рёбра)^[1].
• Структурная биология — GNN-подобные архитектуры, оперирующие графами атомов и остатков и обучающиеся на парных взаимодействиях, стали важной частью системы AlphaFold, позволившей резко повысить точность предсказания трёхмерной структуры белков^[1].
• Рекомендательные системы — представление пользователей и товаров как двудольного графа и обучение их эмбеддингов свёрточными GNN легло в основу промышленной системы PinSAGE, применяемой в Pinterest^[1].
• Транспортные и дорожные сети — GNN, моделирующая дорожную сеть как граф, используется компанией Google для предсказания времени прибытия (ETA) в сервисе Google Maps^[1].
• Социальные сети и анализ графов знаний — классификация пользователей, обнаружение сообществ, предсказание связей и дополнение баз знаний.
• Компьютерное зрение и физика — распознавание сцен через графы объектов, моделирование физических систем частиц как взаимодействующих графов (Interaction Networks)^[1].

Современные направления

Среди активных направлений исследований последних лет — графовые трансформеры, объединяющие идеи механизма внимания без ограничения на локальное соседство; согласование GNN с большими языковыми моделями для работы с текстово-атрибутированными графами; и построение так называемых «графовых фундаментальных моделей» — предобученных на разнородных графах моделей, переносимых на новые предметные области без дообучения с нуля^[1].

См. также

• Искусственная нейронная сеть
• Глубокое обучение
• Свёрточная нейронная сеть
• Рекуррентная нейронная сеть
• Трансформер
• Механизм внимания
• Граф
• Тест Вейсфейлера — Лемана
• Эмбеддинг
• Обучение представлений
• Рекомендательная система
• Хемоинформатика
• AlphaFold
• Обучение с учителем

Примечания

Литература

• Scarselli F., Gori M., Tsoi A. C., Hagenbuchner M., Monfardini G. The Graph Neural Network Model // IEEE Transactions on Neural Networks. — 2009. — Т. 20. — № 1. — С. 61—80.
• Kipf T. N., Welling M. Semi-Supervised Classification with Graph Convolutional Networks // International Conference on Learning Representations (ICLR). — 2017.
• Hamilton W. L., Ying R., Leskovec J. Inductive Representation Learning on Large Graphs // Advances in Neural Information Processing Systems (NeurIPS). — 2017. — Т. 30.
• Veličković P., Cucurull G., Casanova A., Romero A., Liò P., Bengio Y. Graph Attention Networks // International Conference on Learning Representations (ICLR). — 2018.
• Gilmer J., Schoenholz S. S., Riley P. F., Vinyals O., Dahl G. E. Neural Message Passing for Quantum Chemistry // Proceedings of the 34th International Conference on Machine Learning (ICML), PMLR 70. — 2017. — С. 1263—1272.
• Xu K., Hu W., Leskovec J., Jegelka S. How Powerful are Graph Neural Networks? // International Conference on Learning Representations (ICLR). — 2019.
• Battaglia P. W., Hamrick J. B., Bapst V. и др. Relational inductive biases, deep learning, and graph networks // arXiv preprint. — 2018.
• Wu Z., Pan S., Chen F., Long G., Zhang C., Yu P. S. A Comprehensive Survey on Graph Neural Networks // IEEE Transactions on Neural Networks and Learning Systems. — 2021. — Т. 32. — № 1. — С. 4—24.
• Zhou J., Cui G., Hu S., Zhang Z., Yang C., Liu Z., Wang L., Li C., Sun M. Graph neural networks: A review of methods and applications // AI Open. — 2020. — Т. 1. — С. 57—81.
• Hamilton W. L. Graph Representation Learning. — Morgan & Claypool Publishers, 2020. — ISBN 978-1681739632
• Jumper J., Evans R., Pritzel A. и др. Highly accurate protein structure prediction with AlphaFold // Nature. — 2021. — Т. 596. — С. 583—589.
• Derrow-Pinion A., She J., Wong D. и др. ETA Prediction with Graph Neural Networks in Google Maps // Proceedings of the 30th ACM International Conference on Information & Knowledge Management (CIKM). — 2021. — С. 3767—3776.