Предупреждение и радостная весть: статья рассчитана в том числе на тех, кто видит математику впервые в жизни.
Введение: графы и дата-примеры графов
Думаю, многие встречали визуализацию с подписью “какой-то там граф”, где были изображены круги, соединенные либо палками, либо разнонаправленными стрелками. Так вот, очень сильно прошу вас сейчас выкинуть это отождествление из головы.
Да, встречаемые картинки являются визуализацией базовых графов и, кроме того, они являются полезным инструментом в жизни, но математика нежно обидется, если сказать или даже подумать – что граф принадлежит миру 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
однако, строго говоря, допустимо, что расстояние можно определить иным способом.
Интересные ссылки:
Релиз первых моделей GNN https://ro.uow.edu.au/cgi/viewcontent.cgi?article=10501&context=infopapers
Кейс ВШЭ из области химии c применением GNN
Пост на Towards Data Science, также с объяснением графовых НС, только на другом языке и чуть иначе: https://towardsdatascience.com/graph-neural-networks-a-learning-journey-since-2008-part-1-7df897834df9
Классические датасеты:
Cora
CiteSerr
Pubmed.
Загрузить любой из них можно, применив класс Planetoid из модуля torch_geometric https://pytorch-geometric.readthedocs.io/en/latest/_modules/torch_geometric/datasets/planetoid.html
Комментарии (9)
vovsenqq
07.11.2022 14:18история математики
Лишний пробел.
провёл пользой
"с" пропущена.
На втором рисунке тяжело читаются индексы.
Хорошая подача, очень интересно, но точно не для новичков)
sad__sabrina Автор
07.11.2022 14:19+1Благодарю за внимательное прочтение и фидбек!
Исправления внесу)
AzIdeaL
07.11.2022 20:14Из школы можно помнить, что расстояние между векторами определяется по формуле для векторов x, y
d(x, y) = \sqrt{(x1-y1)^22+(x2-y2)^2+.........(xn-yn)^2}
А что-то в этой формуле не сходится: у первого слагаемого подкоренного выражения вижу коэффициент, который в остальных пропал, -- непорядок)
sad__sabrina Автор
07.11.2022 21:47Здравствуйте!
Благодарю за внимательность! Коэффициента быть не должно.
Поправила)
manfredima
08.11.2022 06:31+1"это система, основанная на контролируемом"
Контролируемый - КТО? Все равно непонятно.
sad__sabrina Автор
08.11.2022 07:16Доброго времени!
Обучении, конечно, в скобках далее написано. Благодарю за внимательность, внесу)
vassabi
08.11.2022 12:37Предположим, что существует функция описывающая вершину вершину состоянием за счет информации в ней и её окрестности и функция , описывающая зависимость целевой переменной от выхода функции .
Получим структуру (1):
где параметры это
— вектора признаков вершины n,
— вектора, описывающий связи вершины с её соседями
— множества состояний соседей вершины n
– векторы, описывающие соседей вершины nпараметры это
— состояние вершины n
— вектор, описывающий вершину n....
вам бы еще показать пример этого всего - для графа из трех-четырех вершин - с рисунком и надписями - что где
Exchan-ge
И тут же:
Тут и для тех, кто изучал вышку 40 лет назад, надо бы вначале рассказать/напомнить о том что такое «граф» и для чего эти графы в принципе нужны.
А уже потом переходить к формулам и схемам.
(а для тех, кто и не изучал ее вовсе — граф, это граф Монте-Кристо :)
sad__sabrina Автор
Вы правы, «впервые в жизни» — здесь я гиперболизировала. Однако надеюсь, это, в случае непонимания, не помешает подсмотреть в поисковик или задать вопрос)