Геометрические реализации Pytorch для основных задач с графами

Graph Neural Networks — это алгоритм машинного обучения, разработанный для графически структурированных данных, таких как социальные графы, сети в кибербезопасности или молекулярные представления. За последние несколько лет он быстро развивался и используется во многих различных приложениях. В этом сообщении блога мы рассмотрим его реализации кода для основных задач с графами, а также все основы GNN, включая его приложения и детали алгоритма.

Приложения графовых нейронных сетей

GNN можно использовать для решения различных задач машинного обучения, связанных с графами:

  • Классификация узлов
    Прогнозирование классов или меток узлов. Например, обнаружение мошеннических объектов в сети в области кибербезопасности может быть проблемой классификации узлов.
  • Прогнозирование связи
    Прогнозирование наличия потенциальных связей (ребер) между узлами. Например, служба социальной сети предлагает возможные связи друзей на основе сетевых данных.
  • Классификация графиков
    Классификация самого графика по различным категориям. Примером является определение того, является ли химическое соединение токсичным или нетоксичным, по структуре его графика.
  • Обнаружение сообщества
    Разбиение узлов на кластеры. Примером может служить поиск различных сообществ в социальном графе.
  • Обнаружение аномалий
    Поиск узлов-выбросов на графике без присмотра. Этот подход можно использовать, если у вас нет меток на вашей цели.

В этом сообщении блога мы рассмотрим реализации кода для классификации узлов, прогнозирования ссылок и обнаружения аномалий.

Свертка графа — интуиция

Графовые нейронные сети быстро развивались за последние несколько лет, и было изобретено множество их вариантов (более подробную информацию вы можете найти в этом обзоре). В этих вариантах GNN Graph Convolutional Networks может быть самым популярным и основным алгоритмом. В этом разделе мы рассмотрим введение высокого уровня в его алгоритм.

Свертка графа — это эффективный способ извлечения/обобщения информации об узлах на основе структуры графа. Это вариант операции свертки от Convolutional Neural Networks, который обычно используется для задач с изображениями.

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

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

На изображении ниже показаны более подробные сведения об операции свертки графа. Характеристики узлов из соседних узлов (синие) вместе с целевыми узлами (красные) усредняются. А затем он умножается на вектор весов (W), и его выходные данные обновляют характеристики узла целевого узла (обновленные значения узлов также называются вложениями узлов).

Для тех, кому интересно, признаки узлов нормализуются с использованием обратной матрицы степеней, а затем агрегируются в исходной статье вместо простого усреднения (уравнение (8) в статье).

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

Cora — набор данных эталонных графиков

В следующих нескольких разделах мы рассмотрим реализации кода GCN. Прежде чем мы углубимся в них, давайте познакомимся с набором данных, который мы собираемся использовать. Cora dataset — это сеть данных бумажного цитирования, состоящая из 2708 научных публикаций. Каждый узел в графе представляет каждую публикацию, а пара узлов соединена ребром, если одна статья цитирует другую.

В этой статье мы используем PyG (Pytorch Geometric) для реализации GCN, которая является одной из популярных библиотек GNN. Набор данных Cora также можно загрузить с помощью модуля PyG:

Набор данных Cora, полученный от Pytorch Geometric, изначально взят из статьи Автоматизация построения интернет-порталов с помощью машинного обучения.

Функции узлов и информация о ребрах выглядят так, как показано ниже. Признаками узла являются 1433 вектора слов, указывающих на отсутствие (0) или наличие (1) слов в каждой публикации. Ребра представлены в списках смежности.

Каждый узел имеет один из семи классов, который будет нашей целью/меткой модели.

Данные графика можно визуализировать с помощью библиотеки NetworkX. Цвета узлов представляют классы узлов.

Классификация узлов

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

Обратите внимание, что разделение данных записывается в атрибуты mask в объекте графика (см. изображение ниже) вместо разделения самого графика. Эти маски используются для расчета потерь при обучении и оценки модели, тогда как свертки графа используют все данные графа.

Базовая модель (MLP) по классификации узлов

Прежде чем построить GCN, мы обучаем MLP (многоуровневый персептрон, то есть нейронные сети с прямой связью), используя только функции узла, чтобы установить базовую производительность. Модель игнорирует соединения узлов (или структуру графа) и пытается классифицировать метки узлов только с использованием векторов слов. Класс модели выглядит следующим образом. Он имеет два скрытых слоя (Linear) с активациями ReLU, за которыми следует выходной слой.

Мы определяем функции обучения и оценки с помощью обычной настройки Pytorch train/eval.

Точность теста этой модели составляет 73,2%.

GCN по классификации узлов

Далее мы обучаем GCN и сравниваем его производительность с MLP. Мы используем очень простую модель с двумя слоями свертки графа и активацией ReLU между ними. Эта настройка аналогична исходной статье GCN (уравнение 9).

Точность набора тестов для этой модели составляет 88,0 %. Мы добились повышения точности примерно на 15% по сравнению с MLP.

Прогноз связи

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

  1. Кодер создает вложения узлов, обрабатывая граф с двумя слоями свертки.
  2. Мы случайным образом добавляем отрицательные ссылки в исходный график. Это делает двоичную классификацию задачи модели с положительными связями от исходных ребер и отрицательными связями с добавленными ребрами.
  3. Декодер делает предсказания ссылок (то есть двоичные классификации) на всех ребрах, включая отрицательные ссылки, используя вложения узлов. Он вычисляет скалярное произведение вложений узлов из пары узлов на каждом ребре. Затем он объединяет значения по измерению внедрения и создает одно значение для каждого ребра, которое представляет вероятность существования ребра.

Эта структура модели взята из исходной реализации предсказания ссылок в автокодировщиках вариационного графа. Код выглядит примерно так, как показано ниже. Это адаптировано из примера кода в репозитории PyG, который основан на реализации Graph Auto-Encoders.

Для этой задачи прогнозирования ссылок мы хотим случайным образом разделить ссылки/ребра на обучающие, действительные и тестовые данные. Для этого мы можем использовать модуль RandomLinkSplit из PyG.

Выходные данные выглядят примерно так, как показано ниже.

Есть несколько вещей, которые следует отметить в отношении этих выходных данных.

Во-первых, разделение выполняется на edge_index таким образом, что разделение обучения и проверки не включает ребра из разделения проверки и тестирования (т. е. имеют только ребра из разделения обучения), а разделение теста не включает ребра из тестовый раскол. Это связано с тем, что edge_index (и x) используется для кодировщика для создания вложений узлов, и эта настройка гарантирует отсутствие целевых утечек во вложениях узлов, когда он делает прогнозы для данных проверки/тестирования.

Во-вторых, к каждому разбиению данных добавляются два новых атрибута (edge_label и edge_label_index). Это метки ребер и индексы ребер, соответствующие каждому разбиению. edge_label_index будет использоваться декодером для прогнозирования, а edge_label будет использоваться для оценки модели.

В-третьих, отрицательные ссылки добавляются к val_data и test_data с тем же номером, что и положительные ссылки (neg_sampling_ratio=1.0). Они добавляются к атрибутам edge_label и edge_label_index, но не добавляются к edge_index, так как мы не хотим использовать отрицательные ссылки на кодировщике (или создании встраивания узла). Кроме того, здесь мы не добавляем отрицательные ссылки в тренировочный набор (путем настройкиadd_negative_train_samples=False), так как мы добавим их во время цикла обучения в train_link_predictor выше. Эта рандомизация во время обучения должна сделать модель более надежной.

На изображении ниже показано, как это разделение ребер выполняется для кодера и декодера (цветные ребра используются на каждом этапе).

Теперь мы можем обучить и оценить модель с помощью следующего кода.

Тестовый AUC этой модели составляет 92,5%.

Обнаружение аномалий

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

  • Структурный выброс
    Плотно связанные узлы в отличие от редко связанных обычных узлов
  • Контекстный выброс
    Узлы, атрибуты которых значительно отличаются от соседних узлов.

Для этой задачи обнаружения аномалий мы используем библиотеку PyGOD, которая представляет собой библиотеку обнаружения выбросов графа, построенную поверх PyG. Мы можем загрузить набор данных Cora с добавлением выбросов через модуль PyGOD.

В приведенном ниже коде показано распределение типов выбросов.

Выход: Counter({0: 2570, 1: 68, 2: 68, 3: 2})

Если вас интересует, как внедряются эти выбросы, вы можете посмотреть документацию PyGOD по модулям генератора выбросов, в которой объясняются детали операции. Обратите внимание, что метки y будут использоваться только для оценки модели и не будут использоваться для меток обучения, поскольку мы обучаем неконтролируемую модель.

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

  1. Сетевой кодировщик с атрибутамиобрабатывает входной граф с помощью трех слоев свертки графа, которые создают вложения узлов.
  2. Декодер реконструкции структурыреконструирует ребра исходного графа (т. е. матрицу смежности), используя изученные вложения узлов. Он вычисляет скалярное произведение вложений узлов из каждой возможной пары узлов, что создает оценку вероятности для каждой пары узлов, указывающую на существование ребра.
  3. Декодер реконструкции атрибутовреконструирует исходные атрибуты узлов, используя полученные вложения узлов. Он имеет слой свертки графа для прогнозирования значений атрибутов.
  4. На последнем этапе ошибки реконструкции от двух вышеупомянутых декодеров объединяются по средневзвешенному значению на каждом узле, и объединенные ошибки будут окончательными ошибками/потерями. Эти окончательные ошибки также являются оценками аномалий узлов.

Модель DOMINANT может быть легко реализована с помощью PyGOD, как вы можете видеть ниже.

AUC этой модели составляет 84,1%, тогда как ее средняя точность составляет 20,8%. Эта разница, скорее всего, связана с целевым дисбалансом. Поскольку это неконтролируемая модель, мы не можем ожидать очень точной модели, но вы можете видеть в исходной статье, что она по-прежнему превосходит любые другие популярные алгоритмы обнаружения аномалий.

Это все для этой статьи!

Если вам интересно, весь код доступен в Google Colab и репозитории GitHub ниже.



Google Colaboratory
реализации GNN с PyGcolab.research.google.com





gnn_pyg_implementations.ipynb на tomonori-masui/graph-neural-networks
реализации GNN с PyGgithub.com



Рекомендации