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

P.s. У меня огромные проблемы с вычиткой текста, поэтому если вы увидете опечатку/ошибку - просьба сообщить. Спасибо!

Что такое граф?

Вам, наверно, знакомо слово граф (~~Монте-Кристо~~) и что он из себя представляет. Но для читателей, кто не в курсе или забыл, напишу пару слов. Граф - математическая структура, представляющая собой набор вершин (узлов), соединенных ребрами (гранями). Вершины графа могут представлять сущности, а ребра - отношения или связи между этими сущностями. Простой пример: у вас есть страничка в социальной сети (вы вершина), есть другие люди в этой социальной сети (тоже вершины). С некоторыми людьми вы дружите (вы соединены ребрами), также ваши друзья дружат с другими людьми (они соединены с ними ребрами) и так далее. Думаю, понятно.

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

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

Но что такое графы в контексте визуальных и текстовых данных? И картинки, и текст можно представить в виде графов. Например, когда мы рассматриваем изображение, мы можем представить его как граф, где каждый пиксель соединен с соседним. Текст также можно представить как последовательный граф, где каждое слово соединено с предыдущим и последующим.

Есть три основных типа задач, которые могут быть решены с использованием графовых нейронных сетей:

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

Как хранить граф?

В виде матрицы смежности. Но есть недостаток, что матрица может быть разрежена, когда данные не сильно связаны (а это затраты на память). Второй недостаток, что для одной и той же связности есть разные матрицы смежности и нет гарантии, что они будут давать одинаковые результаты, хотя должны.
Более экономичный вариант - хранить информацию о ребре, которое соединяет вершины (i, j) в списке.

Обработка графовых данных в GNN

Рассмотрим простую GNN (графовую нейронную сеть, запомните это сокращение!) без изменения связности. На вход мы получаем эмбеддинги вершин и пропускаем их через MLP слой, на выходе получаем измененные эмбеддинги для вершин. Также делаем для ребер и эмбеддинга целого графа. В итоге мы получаем граф с таким же размером списка смежности ребер.

Классификацию на уровне вершин

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

Классификация на уровне ребер

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

Работа с большими графами

Чтобы учитывать больше информации, можно собирать информацию с соседних вершин, получая их эмбеддинги и применяя некоторую функцию (например, сумму). Или, например, делать сначала пуллинг, а затем передачу информации (passing message). При большом графе узлы, которые далеко друг от друга могут никогда не получить информацию друг о друге, даже если мы сделаем шаг passing message несколько раз, к тому же это очень вычислительно затратно. Чтобы решить эту проблему, можно использовать так называемый master node или contex vector, который состоит из всех эмбеддингов узлов и ребер. Это создает более информативное представление графа.

Перевод узла в низкоразмерное пространство графов

Хорошо, давайте порассуждаем. Допустим, у нас есть социальная сеть, где узлы представляют пользователей, а рёбра - связи между ними (например, дружба). Задача узнать интересы человека.

Как будем векторизовать узел? Один из первых методов встраивания узлов графа в низкоразмерное пространство - DeepWalk (есть другие методы, например, node2vec и так далее). Суть метода заключается в следующем: сначала выбираем случайного пользователя и начинаем случайное блуждание по сети, перемещаясь от пользователя к его случайному другу (случайному узлу, с которым он связан). Затем мы повторяем этот процесс много раз, создавая множество случайных блужданий по сети.

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

Ниже пару слов про алгоритм SkipGram, для тех, кто впервые слышит или забыл.

Суть алгоритма заключается в предсказании контекста по данному узлу. Он работает следующим образом:

Подготовка данных: Сначала текст разбивается на последовательность узлов графа, которые выступают в качестве обучающих примеров.
Создание обучающих пар: У нас есть набор, который мы получили с помощью DeepWalk.
Обучение модели: Обучающие пары передаются модели, которая обновляет векторные представления слов таким образом, чтобы минимизировать ошибку предсказания контекста по центральному слову. То есть минизации ошибки - друзей по пользователю.
Использование обученных векторов: После завершения обучения каждому узлу в графе присваивается свое векторный представления.

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

Кто знаком с NLP подумает о Word2Vec. По сути DeepWalk и Word2Vec являются аналогами в том смысле, что они оба используют нейронные сети для обучения векторных представлений.

Вычислительные модули

В графовых сетях есть 3 основных модулей, с помощью которых строится архитектура.

Propagation - агрегируем информацию с графа или заставляем нашу модель работать (грубо говоря метод forward)
Sampling
Pooling

Рассматрим каждый из них подробнее. Начнем с Propagation, можно использовать три типа операторов: сверточные, реккурентные и skip connection (пробрасываем информацию с предыдущих шагов вперед)

GCN - Graph Convolutional Networks

Задача - адаптировать свертки из других областей на графах.

Сверточные операции на графе впервы были представлены в работе “Semi-Supervised Classification with Graph Convolutional Networks" Томасом Кипфом и Максом Велленбергом в 2017 году.

В GCN операция свертки применяется к признакам узлов графа с учетом их структуры. Формально, GCN определяется следующим образом:

Итак, формула кажется непонятно, полностью поддерживаю. Попробуем разобраться, почему она именно такая?

Ã - Матрица смежности графа. Расширение матрицы смежности путем добавления единичной матрицы l позволяет учитывать информацию о собственном узле при агрегации соседей.
D~ - Диагональная матрица степеней узлов Ã, где каждый элемент D_ii равен сумме всех элементов i-ой строки матрицы Ã. Эта матрица используется для нормализации агрегированных признаков.
H^l - Матрица признаков узлов на l-ом слое, которая содержит признаки для каждого узла на данном уровне.
W^(l) - Матрица весов для свертки на l-ом слое, которая применяется к агрегированным признакам.

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

Отлично, вроде стало чуть понятнее, но не совсем. Почему умножение на D происходит два раза? Зачем D возводится в степени -½?

Давайте, для простоты выкинем H и W (тут понятно, все как в обычых нейронных сетях - веса умнжаем на признаки). Осталась нормализация, которая выражена умножением трех матриц.

Итак, поехали:

Матрица D~ возводится в степень -½, чтобы обратить степени узлов и выполнить нормализацию по строкам и столбцам. Это помогает уменьшить влияние узлов с большим количеством соседей и уменьшить вариативность весов. Слева умножение на матрицу Ã выполняется, чтобы нормализовать строки матрицы Ã (нормализация по строкам), а с правой стороны, чтобы нормализовать столбцы этого результата (нормализация по столбцам). Использование умножения слева и справа позволяет выполнить нормализацию по обеим направлениям. Это помогает учесть различные веса соседей узла и обеспечить стабильность и эффективность операции свертки.

GAT - Graph Attention Network

Модель графовых нейронных сетей, которая использует механизм внимания для эффективного агрегирования информации из соседних узлов в графе.

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

Скрытое состояние для узла h получается по следующей пугающей формуле:

α - вектор весов, который обучается вместе с моделью, [Wh_i ∣∣ Wh_j] - конкатенация векторов.

Спокойно! Все по порядку.

Сначала мы применяем матрицу обучаемых параметров W к векторным представлениям узлов h_i и h_j. Это позволяет модели обучиться находить более информативные представления узлов.
Далее мы конкатенируем две полученные матрицы, чтобы учитывать информацию о паре узлов i и j вместе. Это позволяет модели учитывать взаимодействия между этими узлами и использовать эту информацию при вычислении весов внимания.
Далее умножаем на вектор весов α. Это позволяет модели оценить важность связи между узлами i и j в графе.
Ну, а дальше LeakyReLU (функция активации) и эта двух этажная формула представляет из себя softmax.

Много букв! Давайте резюмировать:

Для двух узлов: узел умножаем на собственную матрицу весов (они обучаются) → объединяем полученную информацию для 2 узлов → умножаем на обучаемую матрицу важности связи этих двух пар → функция активации → softmax.

В графовых сетях также может применятся multi-head attention (грубо говоря, когда такую операцию для пары узлов мы проворачиваем N раз, где N - количество голов).

Recurrent operator

Реккурентный оператор аналогичен рекуррентным слоям в рекуррентных нейронных сетях (RNN), где информация обновляется постепенно и зависит от предыдущего состояния. Однако, в отличие от RNN, где последовательность определяется временем, в GNN последовательность определяется структурой графа.

Формально, оператор рекуррентного обновления для узла i и j на l-ом слое в GNN может быть выражен следующим образом:

Оператор рекуррентного обновления обновляет представление узла i путем агрегации представлений его соседей j и применения нелинейной функции активации.

~~Выглядит довольно просто!~~

Недастаток оператора состоит в том, что мы можем потерять информацию.

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

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

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

Skip connection

Большое количество слоев не всегда помогает улучшить качество нейронной сети. Информация теряется, добавляется много шума. Для решения этой проблеы придумали skip connection (вспомним ResNet). Идея заключается в добавлении коротких соединений, которые обходят один или несколько слоев нейронной сети, позволяя пропускать входные данные или их преобразованные версии напрямую к последующим слоям.

Так например, DeepGCNs взял идею из ResNet и DenseNet.

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

Формула подхода представлена ниже:

где T - гейт (функция), принимающая на вход вектор х ****и выполняющая преобразование с помощью параметров W_t (они обучаются)

H - функция, которая выполняет преобразования над х с помочью параметров W_h (тоже обучаются).

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

Левая часть формулы позволяет контролировать, какая часть информации будет обновлена с использованием параметров W_h, а какая останется без изменений.

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

Sampling modules

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

Node sampling. Суть в том, что мы выбираем подмножество соседей для каждого узла. GraphSAGE (модель) выбирает фиксированное количество соседей, обеспечивая от 2 до 50 соседей для каждого узла.
PinSage предлагает выборку на основе важности. Путем моделирования случайных блужданий, начиная с конечных узлов, этот подход выбирает Т узлов с наибольшим нормализованным числом посещений (количество посещений узла при блуждании делим на количество узлов в графе).
Layer sampling. На каждом слое сохраняем определенное количество узлов.
Subgraph sampling. Соответственно выбираем подграфы. Например, с помощью генерации подграфа (GraphSAINT)

Виды графа

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

Направленного графа. В его случае можно вести 2 вида весов - W_p и W_c для прямого и обратного направления соответсвенно.
Гетерогенные графы. Узлы могут представлять разные сущности, а рёбра - различные типы отношений между этими сущностями. Грубо говоря, у графа нет одного типа формата данных, в нем содержатся сложные отношения между различными объекта разной природы. Что же делать в таком случае? На помощь приходят метапути. Метапуть представляет собой последовательность узлов и рёбер, которые определяют путь или отношение между сущностями в графе. Метапуть фиксирует сходство двух узлов, которые могут быть не связаны напрямую. Благодаря такому подходу, мы получаем несколько гомогенных графов, с которыми уже умеем работать. Приведу пример из рекоменательных систем: пользователь - оценивает - фильм - жанр - фильм. Также существуют методы на снове ребер.
Динамический граф. Узлы, ребра меняются со временем. Structural-RNN и ST-GCN расширяют граф со временем, добавляя временные связи к измененному графу, после чего пользуются методами для работы с GNN. DCRNN и STGCN сначала собирают пространственную информацию, после чего скармливают ее модели sequence-to-sequence или RNN.

Инструменты

Перечислю пару библиотек для работы с графовыми сетями:

PyTorch Geometric
Deep Graph Library (DGL)
Graph Nets
Spektral

Литература

Наглядная статья про GNN. Советую!

Полезный конспект

GCN

Graph neural networks: A review of methods and applications (arxiv.org)

Графы в Computer Vision

Про библиотеки

Интересная статья с кодом (Habr)

Яндекс про GNN

Под капотом графовых сетей