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

Люблю соцсети. Вместо того чтобы бегать по округе в поисках кого-то, кто будет готов меня выслушать, я могу докопаться до всех вас сразу, не вставая из кресла. Здорово, правда?

Сегодня я принесла вам немного графовых нейронных сетей (GNNs). Чтобы сформировать общее представление, я воспользуюсь этой замечательной статьей. Переписывать ее целиком я, конечно, не собираюсь, так что за подробностями смело обращайтесь туда. Статья написана очень хорошим языком, с примерами и иллюстрациями.

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

Скажем, у нас есть два человека: A и B. Да, они круглые и синие, и мы не будем их осуждать.

Если A и B дружат в соцсети, между ними проводится ребро – связь.

Все, у нас теперь есть граф.

Строго говоря, существует такая вещь, как «пустой граф» (empty graph), у которого нет ребер, так что наши A и B уже сами по себе граф.

Еще строже говоря, существует «нулевой граф» (null graph) без вершин (следовательно, и без ребер). То есть, даже до появления A и B у нас уже был граф. У нас всегда есть граф (вспоминайте об этом, когда грустите из-за того, чего у вас нет – у вас всегда есть граф).

Иногда термины «нулевой граф» и «пустой граф» используют как взаимозаменяемые, но это не лучшая практика, она может вызвать путаницу. В поисках дополнительной информации я на Stackexchange наткнулась на статью «Is the null-graph a pointless concept?» («Является ли нулевой граф бессмысленной концепцией?»). Текст бесплатно не доступен, но аннотации написано: «Однозначного вывода нет». Пустой граф бессмысленной концепцией не является, так что лучше их не путать.

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

Предположим, A подписан на B, а B на A – нет. Получается односторонняя связь, которую можно изобразить с помощью направленного ребра.

Граф с направленными ребрами – это направленный граф.

Иногда ребра выходят из одной вершины в несколько и сходятся из нескольких в одну. Иногда есть циклы, тогда граф циклический. Нет циклов – ациклический. Ничего сложного.

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

Нашли?

Правильный ответ – E → B → F и B → D → B. Вершины можно перечислить начиная с любой, поэтому – B → F → E и F → E → B – тот же цикл, что и E → B → F.

Вершины A, C и B цикла не образуют из-за направления ребер. Будь ребра ненаправленными, из A, C и B тоже получился бы цикл.

Здесь вы уже, наверное, поняли, что граф – удобное представление почти чего угодно. Из популярного в виде графов представляют связи в социальных сетях, химические структуры, научное или патентное цитирование.Есть три типа задач, которые можно решать на графах:

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

На уровне отдельных вершин задача состоит в том, чтобы предсказать недостающий узел и / или его свойства. Например, у нас есть набор белков, которые взаимодействуют друг с другом определенным известным нам образом. Каждый белок – это вершина большого графа. Ребра – это взаимодействия между белками. Имея информацию о конкретном белке и наборе других белков, с которыми он взаимодействует, мы можем попробовать предсказать его характеристики.

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

Отлично.

Теперь следующий вопрос: как засунуть граф в нейросеть? Нейросеть принимает на вход матрицы, следовательно, нам нужно превратить графы в матрицы. Есть парочка вариантов, один из наиболее удобных – список смежности (adjacency list). Такой список хранит информацию о связанных узлах и весах ребер, если они есть. Сейчас объясню.

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

Статьи института A сослались на 3 статьи института B. Получился направленный взвешенный граф с двумя вершинами и одним направленным взвешенным ребром. «Вес» в данном случае – это число цитирований. Список смежности для этого графа будет иметь следующий вид:

A: {B, 3},

что значит «из A в B направлено ребро с весом 3».

Если хотите узнать больше про списки смежности, обратитесь к этому материалу, там все очень понятно и подробно написано.А я пойду дальше и расскажу про нейросеть.

Насколько мне известно, первая статья о GNN – «A new neural network model for graph processing» («Новая нейронная сеть для обработки графов») [1]. На нее ссылаются другие публикации, например статья «Graph Neural Networks for Ranking Web Pages» («Графовые нейронные сети для ранжирования веб-страниц») 2005 года.

Сам текст первоисточника мне почему-то найти не удалось, зато нашлась более поздняя работа тех же авторов – «The graph neural network model» («Графовая нейронная сеть»). Там GNN определяется так:

Чтобы понять, что все это значит, снова обратимся к нашему графу с институтами и добавим туда еще один узел, чтобы было с чем работать.Пускай есть институт A, который опубликовал 1 статью, институт B, который опубликовал 2 статьи, и институт C, который опубликовал 3 статьи. Статья института A цитирует 2 работы института B, а статьи института B цитируют 1 работу института C. Тогда получится вот такой граф:

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

Теперь нужно отобразить полученный граф в m-мерное евклидово пространство.

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

«Отобразить в m-мерное пространство» значит превратить в векторы размера m, где m – натуральное число (1, 2, 3, 4…). Сделать это можно разными способами, в зависимости от того, что нам важно и какую информацию мы хотим сохранить. Например, мы считаем, что цитирование работ института в работах других институтов что-то о нем говорит. Мы отразим эту информацию следующим образом:

Каждую вершину мы превратили в число, то есть, отобразили в одномерное пространство (m=1).

Можно пойти дальше и добавить второе измерение (m=2). Например, можно записать и информацию о цитированиях, и число собственных статей:

A = [1, 0] → одна статья, цитирований нет.

B = [2, 2] → две статьи, два цитирования.

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

Кажется, на сегодня достаточно. Предлагаю переварить полученную информацию, а в одном из следующих постов я вам расскажу про то, где и как графовые нейронные сети применяются в реальной жизни и почему они такие замечательные.
[1] Полная ссылка: F. Scarselli, A. C. Tsoi, M. Gori, M. Hagenbuchner. A new neural network model for graph processing. Technical Report DII 01/05, Dept. of Information Engineering, University of Siena, 2005