Автор: Шамиль Мамедов Редактура: Александр Наздрюхин

Введение

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

Рис. 1. Jazz Musicians Network, пример графового датасета [1]

Определение графа

Для начала давайте определим, что такое граф. Формально граф $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ определяется с помощью набора вершин $\mathcal{V}$ и набора ребер $\mathcal{E}$ между этими вершинами. Ребро, идущее из вершины $u \in \mathcal{V}$ к вершине $v \in \mathcal{V}$, обозначается как $(u, v) \in \mathcal{E}$.

Рис. 2. Пример графа с 5 вершинами и 5 ребрами

Ребра могут быть направленными и ненаправленными (как это показано на Рис. 3). Для простоты давайте считать, что все ребра ненаправленные.

Рис. 3. Примеры направленного и ненаправленного ребер

Матрица смежности $A \in \R^{|\mathcal{V}|\times|\mathcal{V} |}$ — удобный способ представления графов. Для ее построения мы упорядочиваем вершины в графе так, чтобы каждая из них индексировала определенную строку и столбец в матрице смежности. Затем мы представляем ребра как элементы этой матрицы: $A[u, v] = 1$ при $(u, v) \in \mathcal{E}$ и $A[u, v] = 0$ в противном случае. Если граф содержит только ненаправленные ребра, то матрица $A$ будет симметричной. Если же графы направленные — матрица $A$ не обязательно будет симметричной. Например, для графа на Рис. 2 матрица смежности выглядит следующим образом:

$$ A = \begin{bmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \end{bmatrix} $$

Примеры графов

Изображения как графы

Обычно мы представляем изображения как прямоугольные сетки с каналами изображения, описывая их в виде массивов (например, матрицы 244x244x3). Еще один способ — представление изображений в виде графа с регулярной структурой, где каждый пиксель является вершиной и соединяется через ребра с соседними пикселями (вершинами). Все пиксели, кроме граничных, имеют ровно 8 соседей. Информация, хранящаяся в каждой вершине, — трехмерный вектор, представляющий RGB-значение пикселя.

Рис. 4. Пример представления изображения в виде графа с регулярной структурой [Источник]

Текст как граф

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

Рис. 5. Пример представления текста в виде графа с регулярной структурой [Источник]

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