Предупреждение и радостная весть: статья рассчитана в том числе на тех, кто видит математику впервые в жизни. 

Введение: графы и дата-примеры графов

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

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

Графом — называется пара (N, E), где N — nodes, множество вершин, называемых также узлами, а E — edges множество ребер, называемых также связями. 

В чем отличие этого определения от 2D-мира? Как пример то, что множество N может являться семейством множеств. 

Графов определено много разных видов, но для нас важно то, что некоторые объекты мира и, соответственно, данные, представимы в виде графа.

Дата-примеры:

1) Множество вершин — каждый сотрудник, множество связей — факт добавлены ли сотрудники друг у друга в друзья

2) Множество вершин — множество статей, множество связей — ссылки между статьями (научные статьи часто ссылаются на результаты друг-друга)

3) Множество вершин — частные атомы органического соединения, множество связей — наличие и сила связи между атомами(см. картинку)

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

Что же это?

Базовый ответ — графовая НС это НС, принимающая граф в качестве набора данных и именно такую формулировку вы, наверное, встречали в туториалах до. 

Но ответ с точки зрения математики:

Графовая нейронная сеть — это система, основанная на контролируемом (supervised, a.k.a обучение с учителем) обучении, определяемая следующим набором:

где

— граф, определяющийся множествами N (nodes, вершин) и E (edges, связей), . 

— множество пар , где — вершина из множества N , целевая переменная, связанная с этой вершиной.

Модель и разрешимость модели

Интуитивная идея и отличие графовых нейронных сетей заключается в том, что вместо двух множеств X и Y, у нас одно из множеств само представлено множествами. Звучит, конечно, как прыжок с переподвыподвертом, но в четко прописанном виде выглядит проще:

Вместо .

Как это решать? 

Обратимся к визуальному представлению графа (рис. 2). Справедливо, что каждая вершина не плавает в облаке данных сама по себе (иначе мы бы свелись к задаче обучения на просто векторах-признаках), а естественным образом связывается со своими соседями. 

Исходя из этого предположения выберем вершину на рисунке 2 вершину

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

Получим структуру (1):

где параметры это

— вектора признаков вершины n,
— вектора, описывающий связи вершины с её соседями
— множества состояний соседей вершины n
– векторы, описывающие соседей вершины n

параметры это

— состояние вершины n
— вектор, описывающий вершину n

Где граф?

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

То есть, грубо говоря, агрегирует информацию отсюда:

Почему это работает?

На деле, определив структуру (1), мы не так далеко находимся от привычной нейронной сети, которая принимает X на вход, и отдаёт Y на выход. Она в совершенстве внизу ().

Немой вопрос встаёт в моменте — как определить и найти верхнюю функцию достаточно корректно и не потеряв информацию.

Здесь в дело вступает математематика. 

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

Отображение называется сжимающим, если существует число такое что для любых двух точек пространства выполняется неравенство:

то есть, когда мы действуем отображением на элементы, мы в непрямом смысле уменьшаем расстояние между ними. 

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

Неподвижной точкой сжимающего отображения А называется точка, удовлетворяющая равенству:

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

у сжимающего отображения существует единственная неподвижная точка.

 Что это значит для нас?

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

Соответственно, обучение GNN выглядит так:

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

Вот так. Такая красота и такая базовая история математики GNN!

Надеюсь вам понравился пост. Постепенно буду дублировать в канал посты из своего блога в телеграм (https://t.me/jdata_blog), так что скоро тут появится теория вероятностей и некоторые обзоры на статьи. 

Удачных вам применений этой красоты в работах!
Ваш дата-автор. 

P.S. Если у вас есть что конструктивно дополнить — буду только рада! Для меня важно, чтобы время, потраченное на пост каждый провёл с пользой. 

Сноски и примечания

Соседство и определение :

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

Важно о метрике расстояния:

Из школы можно помнить, что расстояние между векторами определяется по формуле для векторов x, y

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

Интересные ссылки:

1. Релиз первых моделей GNN https://ro.uow.edu.au/cgi/viewcontent.cgi?article=10501&context=infopapers

2. Кейс ВШЭ из области химии c применением GNN

3. Пост на Towards Data Science, также с объяснением графовых НС, только на другом языке и чуть иначе: https://towardsdatascience.com/graph-neural-networks-a-learning-journey-since-2008-part-1-7df897834df9 

Классические датасеты:

1. Cora

2. CiteSerr

3. Pubmed. 

Загрузить любой из них можно, применив класс Planetoid из модуля torch_geometric https://pytorch-geometric.readthedocs.io/en/latest/_modules/torch_geometric/datasets/planetoid.html