Задачи машинного обучения на графах
Введение
Графы окружают нас повсюду. Объекты реального мира часто определяются через их связи с другими объектами. Набор объектов и связи между ними выражаются в виде графа. Нейронные сети, работающие с графами, называются графовыми нейронными сетями. Они недавно показали многообещающие результаты в области поиска лекарств, физического моделирования, обнаружения фейковых новостей и систем рекомендаций. В этой статье мы познакомимся с графами и задачами машинного обучения на графах, что послужит фундаментом для работы с графовыми нейронными сетями.
Определение графа
Для начала давайте определим, что такое граф. Формально граф \( \mathcal{G} = (\mathcal{V}, \mathcal{E}) \) определяется с помощью набора вершин \( \mathcal{V} \) и набора ребер \( \mathcal{E} \) между этими вершинами. Ребро, идущее из вершины \( u \in \mathcal{V} \) к вершине \( v \in \mathcal{V} \), обозначается как \( (u, v) \in \mathcal{E} \).
Ребра могут быть направленными и ненаправленными (как это показано на Рис. 3). Для простоты давайте считать, что все ребра ненаправленные.
Матрица смежности
\( 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-значение пикселя.
Текст как граф
Мы можем цифровизировать текст: присваиваем индексы каждому символу, слову или токену и представляем текст в виде последовательности этих индексов. Так создается простой направленный граф, где каждый символ или индекс является вершиной и связывается ребром со следующей за ним вершиной.
Конечно, на практике изображения и текст обычно не кодируются таким образом: эти графовые представления избыточные, так как все изображения и весь текст имеют очень регулярные структуры. Например, у изображений матрица смежности имеет ленточную структуру, потому что все вершины (пиксели) соединены в сетке. Матрица смежности для текста представляет собой всего лишь диагональную линию, так как каждое слово связано только с предыдущим и следующим словами.
Молекулы как графы
Молекулы — строительные блоки вещества, которые состоят из атомов и электронов в трехмерном пространстве. Все частицы взаимодействуют, но когда пара атомов находится на стабильном друг от друга расстоянии, мы говорим, что она образует ковалентную связь. Различные пары атомов и связи имеют разные расстояния (например, одинарные связи, двойные связи). Очень удобной и распространенной абстракцией является описание этого трехмерного объекта как графа, где вершины — атомы, а ребра — ковалентные связи. Пример представления 3D молекулы в виде графа показан на Рис. 6.
Социальные сети как графы
Социальные сети — это не просто VK и Facebook. Это также инструменты для изучения закономерностей в коллективном поведении людей, институтов и организаций. Мы можем построить граф, представляющий группы людей, где отдельными индивидуумами будут вершины, а их отношения — ребрами. Например, на Рис. 7 показана матрица смежности графа, который моделирует социальную сеть пьесы Шекспира “Отелло”.
Задачи на графах
Мы описали некоторые примеры графов, представляющих реальные данные, но какие задачи мы хотим решать с этими данными? Существует три общих типа задач прогнозирования на графах: на уровне графа, вершин и ребер. Давайте рассмотрим каждую задачу по отдельности.
Задачи на уровне всего графа
В таких задачах нашей целью является прогнозирование свойства целого графа. Например, для молекулы, представленной в виде графа, мы можем предсказать ее запах или потенциальное взаимодействие с рецептором, связанным с заболеванием.
Эти задачи идентичны задачам классификации изображений с использованием MNIST и CIFAR, где мы хотим присвоить лейбл всему изображению. В случае текста, аналогичной задачей является анализ тональности, при котором мы определяем настроение или эмоцию всего предложения целиком.
Задачи на уровне вершин
Такие задачи связаны с прогнозированием свойств или роли каждой вершины в графе. Классическим примером задачи прогнозирования на уровне вершин является «Каратэ-клуб Зака«. Набор данных представляет собой единственный социальный сетевой граф, состоящий из лиц, которые присягнули на верность одному из двух каратэ-клубов после политического разлада. По легенде, конфликт между мистером Хай (инструктором) и Джоном А (администратором) вызвал раскол в каратэ-клубе. Вершины — это каратисты, а ребра — взаимодействия между этими каратистами за пределами каратэ. Задачей прогнозирования является классификация по тому, станет ли данный участник преданным мистеру Хай или Джону Х после конфликта. В данном случае расстояние от вершины до инструктора или администратора сильно коррелирует с этой меткой.
Следуя аналогии с компьютерным зрением, задачи прогнозирования на уровне вершин идентичны сегментации изображений, где мы пытаемся присвоить класс каждому пикселю на изображении. В случае текста, аналогичная задача — прогнозирование частей речи для каждого слова в предложении (например, существительное, глагол, наречие и т.д.).
Задачи на уровне ребер
Итак, у нас остался последний тип задач прогнозирования в графах — задачи на уровне ребер. В качестве примера можно отметить интерпретацию сцены на изображении. Помимо распознавания объектов модели глубокого обучения применяются для прогнозирования отношений между ними. Мы можем сформулировать это как классификацию на уровне ребер: учитываем вершины, представляющие объекты на изображении, и предсказываем, какие из этих вершин разделяют ребро или каково значение ребра. Если мы хотим обнаружить связи между объектами, мы можем рассматривать граф как полностью связанный и, исходя из предсказанного значения, обрезать ребра для получения разреженного графа. Пример интерпретации сцены показан на Рис. 10.
Другие задачи на графах
Согласование изображений (image matching) лежит в основе нескольких приложений в компьютерном зрении, включая восстановление 3D-структуры, одновременную локализацию и построение карты (SLAM), обнаружение изменений. Типичный пайплайн для решения этой задачи: извлечение набора ключевых точек из каждого изображения и создание дескрипторов для этих точек. Затем следует этап сопоставления. Он отвечает за установление соответствий между ключевыми точками двух изображений. Задачу сопоставления ключевых точек можно сформулировать как задачу сопоставления графов, для решения которой используются графовые нейронные сети [3].
Комбинаторная оптимизация часто используется для решения реальных задач в области логистики, экономики и энергетики. Например, к ней относится задача о назначениях. Многие задачи из этой области можно описать с помощью графов и также решить с использованием графовых нейронных сетей [4].
Трудности машинного обучения на графах
Как мы можем решить разные задачи на графах с помощью нейронных сетей? Давайте для начала определимся, как нам представить графы в формате, совместимом с нейронными сетями.
Модели машинного обучения обычно принимают входные данные в виде векторов или массивов. Поэтому самым очевидным способом было бы использование матрицы смежности, так как она легко преобразовывается в тензорный формат. Однако у этого представления есть несколько недостатков. Во-первых, количество вершин в графе может достигать миллионов, а количество ребер на узел значительно варьироваться. Часто это приводит к очень разреженным матрицам смежности, неэффективно использующим пространство. Во-вторых, существует много матриц смежности, которые могут кодировать одну и ту же связность, и нет гарантии, что эти разные матрицы будут давать одинаковый результат в глубокой нейронной сети (то есть они не инвариантны относительно перестановки).
Один из изящных и эффективных с точки зрения памяти способов представления разреженных матриц — это списки смежности. Они описывают связность ребра \( (i, j) \in \mathcal{E} \) между вершинами \( i \) и \( j \) как кортеж \( (𝑖,𝑗) \). Поскольку мы ожидаем, что количество ребер будет гораздо меньше количества записей в матрице смежности, мы избегаем вычисления и хранения для несвязанных частей графа.
Итоги
Итак, теперь мы знаем, какие данные естественным образом описываются в виде графов, какие задачи решают на графах и как эффективно представить графы для машинного обучения. Это значит, что мы готовы к знакомству с графовыми нейронными сетями. О них будет рассказано в следующей статье.
Ресурсы
[1] https://datarepository.wolframcloud.com/resources/Jazz-Musicians-Network
[2] https://distill.pub/2021/gnn-intro/
[3]https://openaccess.thecvf.com/content_cvpr_2018/papers/Zanfir_Deep_Learning_of_CVPR_2018_paper.pdf
