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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: {{well|Статья написана с использованием LLM '''Claude Opus 4.7''' и проверена участником Участник:Dan-Кhaiaa Lakpazhap 20:16...)
 
Строка 1: Строка 1:
-
{{well|Статья написана с использованием LLM '''Claude Opus 4.7''' и проверена участником [[Участник:Dan-Кhaiaa Lakpazhap]] 20:16, 30 июня 2026 (MSD).
+
{{well|Статья написана с использованием LLM '''Claude Sonet 5''' и проверена участником [[Участник:Dan-Кhaiaa Lakpazhap]] 20:16, 30 июня 2026 (MSD).
-
Промпт приводится полностью в [[Обсуждение:Обобщённый автокодировщик на графах GraphEDM]].
+
Промпт приводится полностью в [[Обсуждение:Графовая нейронная сеть]].
}}
}}
{{TOCright}}
{{TOCright}}
Строка 68: Строка 68:
</tex>
</tex>
-
где <tex>W</tex> и <tex>a</tex> — обучаемые параметры, а <tex>\|</tex> — операция конкатенации. Итоговое представление вершины — взвешенная сумма представлений соседей с этими коэффициентами. Такой подход позволяет модели самой определять относительную значимость разных соседей, не завися от нормировки по степени вершины.
+
где <tex>W</tex> и <tex>a</tex> — обучаемые параметры, а <tex>\{|}</tex> — операция конкатенации. Итоговое представление вершины — взвешенная сумма представлений соседей с этими коэффициентами. Такой подход позволяет модели самой определять относительную значимость разных соседей, не завися от нормировки по степени вершины.
=== Сети передачи сообщений и графовая изоморфная сеть (GIN) ===
=== Сети передачи сообщений и графовая изоморфная сеть (GIN) ===

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

Статья написана с использованием LLM Claude Sonet 5 и проверена участником Участник: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].

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

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

Граф задаётся парой G = (V, E), где V — множество вершин, а E \subseteq V \times V — множество рёбер. Структуру связей часто удобно описывать матрицей смежности A размера |V| \times |V|, а признаки вершин — матрицей X \in \mathbb{R}^{|V| \times d}, где строка x_v — вектор признаков вершины v. Рёбра также могут иметь собственные признаки (например, тип связи или вес), а граф в целом может быть направленным, взвешенным, гетерогенным (с несколькими типами вершин и рёбер) или динамическим (меняющимся во времени)[1].

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

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

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

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

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

h_v^{(k)} = \text{UPDATE}^{(k)}\Big(h_v^{(k-1)},\; \text{AGGREGATE}^{(k)}\big(\{\,h_u^{(k-1)} : u \in \mathcal{N}(v)\,\}\big)\Big),

где \mathcal{N}(v) — множество соседей вершины v, \text{AGGREGATE} — некоторая функция агрегации, инвариантная к порядку элементов множества (например, сумма, среднее, максимум или обучаемая функция внимания), а \text{UPDATE} — обучаемая функция объединения (обычно однослойный перцептрон или рекуррентный блок). Начальное представление обычно полагают равным исходному вектору признаков: h_v^{(0)} = x_v. После K слоёв представление вершины отражает информацию из её K-окрестности (так называемое «рецептивное поле», по аналогии со свёрточными сетями).

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

h_G = \text{READOUT}\big(\{\,h_v^{(K)} : v \in V\,\}\big).

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

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

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

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

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

H^{(l+1)} = \sigma\Big(\tilde{D}^{-1/2}\,\tilde{A}\,\tilde{D}^{-1/2}\,H^{(l)}\,W^{(l)}\Big),

где \tilde{A} = A + I — матрица смежности с добавленными петлями (самопересылка), \tilde{D} — соответствующая ей диагональная матрица степеней, W^{(l)} — обучаемая матрица весов слоя, а \sigma — нелинейная функция активации (обычно ReLU). Эта модель, известная как GCN, стала одной из самых цитируемых работ в области и фактическим ориентиром для последующих архитектур благодаря простоте и хорошей масштабируемости[1].

GraphSAGE

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

h_v^{(k)} = \sigma\Big(W^{(k)} \cdot \text{CONCAT}\big(h_v^{(k-1)},\; \text{AGG}_k(\{h_u^{(k-1)} : u \in \mathcal{N}(v)\})\big)\Big).

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

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

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

\alpha_{ij} = \frac{\exp\big(\text{LeakyReLU}(a^{T}[Wh_i \,\|\, Wh_j])\big)}{\sum_{k \in \mathcal{N}(i)} \exp\big(\text{LeakyReLU}(a^{T}[Wh_i \,\|\, Wh_k])\big)},

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

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

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

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

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

которая при подходящем выборе \text{MLP} провably (доказуемо) достигает различающей способности, равной тесту Вейсфейлера — Лемана, то есть является максимально мощной в классе 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].

См. также

Примечания

Ошибка цитирования Входные данные недействительны, так как не предполагаются

Литература

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%93%D1%80%D0%B0%D1%84%D0%BE%D0%B2%D0%B0%D1%8F_%D0%BD%D0%B5%D0%B9%D1%80%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%B5%D1%82%D1%8C»
Личные инструменты