Графические нейронные сети: учебный путь с 2008 года - часть 2

Вторая история о графовых нейронных сетях Скарселли. Сегодня давайте реализуем то, что мы узнали: GNN на Python

В первой части этой серии мы узнали теоретические основы графических нейронных сетей Скарселли. В частности, мы узнали:

• GNN подходит как для предсказаний на основе узлов, так и на основе графов. В первом случае нам нужны прогнозы для каждого узла в графе, во втором - прогнозы для всего графа.
• Каждый узел может быть представлен функцией перехода f𝓌 и функцией вывода g𝓌.
• Чтобы прийти к решению, функция перехода и выходная функция должны удовлетворять решению Банаха с фиксированной точкой.
• Многослойные перцептроны (MLP) действительно удовлетворяют требованиям Банаха, поэтому f𝓌 и g𝓌 могут быть реализованы как простые слои нейронной сети.

Помня об этих моментах, давайте шаг за шагом посмотрим, как мы можем реализовать эту структуру на Python и применить ее к простой задаче, называемой «Клуб карате».

Клуб Каратэ

В качестве примера возьмем проблему клуба карате Закари. Эта проблема восходит к статье Захари Модель информационного потока для конфликта и разделения в малых группах [29], где сеть клубов карате изучалась в течение трех лет (1970–1972). Сеть состоит из 34 членов, включая администратора клуба карате Джон А и инструктора Мистер Хай, а также связи между парами участников, которые взаимодействовали вне клуба (они собирались выпить пива, прогуляться…). После ссоры между администратором и инструктором клуб разделился на две половины, в результате чего были созданы две новые группы. Zachary’s правильно предсказал, как участники реорганизовали свою социальную сеть / решение каждого члена с помощью алгоритма Форда-Фулкерсона. Эта проблема привлекла внимание сообщества любителей графов и широко используется для тестирования GraphNN. В статье Скарселли, опубликованной в 2009 году, Нейронная сеть графов применяется для правильного прогнозирования решений членов клуба карате после разделения.

Репозиторий Github и установка

В этом репо хранятся основные скрипты:

Прежде чем продолжить, я рекомендую вам создать виртуальную среду в рабочем каталоге (просто введите в терминале python -m venv venv, и будет создана папка venv). Затем вы можете установить эти пакеты:

• dgl - Deep Graph Library, библиотека, специализирующаяся на вычислениях графиков. Мы будем использовать это для визуализации нашего графика на этапах обучения. Чтобы установить dgl, вставьте информацию об оборудовании на эту страницу: https://www.dgl.ai/pages/start.html (например, None CUDA, Pip(stable) Package, Mac Os и Python 3.8 версия, поэтому я могу установить dgl с следующая команда pip install dgl -f https://data.dgl.ai/wheels/repo.html). Если у вас возникли проблемы с pip, просто обновите pip install --upgrade pip, и все должно работать нормально.
• pip install torch
• pip install tensorflow
• pip install matplotlib
• pip install seaborn

Введение в скрипты и график

Как видите, в репозитории Github есть несколько скриптов. Вот краткое описание каждого из них:

• create_and_visualize.py позволяет создавать исходный график и рисовать график во время обучения
• prepare_edge_nodes_mat.py предоставляет функции ребер, меток и узлов. Создаются две матрицы: матрица Eedges и идентификатор графа, матрица характеристик N узлов и идентификатор графа.
• prepare_GNN.py преобразует матрицы E и N в качестве входных данных для нейронной сети графа. Результатом является inp матрица, которая имеет форму [source_node, destination_node, features of the source node, features of the destination node] и arcnode матрица, разреженная матрица с соединением ребер между узлами, например. [source_node, destination_node, 1 at source index position 0 otherwise]
• input_and_output_funcitons.py определяет нейронные сети f𝓌 и g𝓌, а также метрики проверки и потери
• GNN.py основной класс Graph Neural Network, в котором определяются условия обучения и проверка сходимости. Конечными выходными данными являются потери при обучении, предсказания узлов, положения узлов во время обучения и количество итераций до сходимости.
• karate.py - это основной скрипт, в котором создается набор данных карате и обучается GNN.

В качестве первого шага мы можем запустить create_and_visualize.py, чтобы визуализировать график клуба карате. Вы можете запустить этот сценарий в ipyhtonshell:

График создается с помощью dgl.DGLGraph() функции build_karate_club_graph(). visualize_karate_club() производит вывод путем преобразования входного графика to_networkx() (рис.2)

Графическое объяснение

Рис. 3 показывает графическое исследование вычислительных шагов. Из исходных графов создаются две матрицы: N-матрица характеристик узлов и матрица ребер E. Затем эти две матрицы преобразуются, чтобы быть входными данными для нейронных сетей графа. В частности, матрица E и признаки из матрицы N используются в качестве входных данных для функции перехода f𝓌. Выходные данные этой нейронной сети умножаются на матрицу горячего кодирования arcnode для обновления состояний узлов. Окончательный результат используется в качестве входных данных для функции g𝓌 для получения окончательных прогнозов.

1. Предварительная обработка входных данных: кромки, метки и элементы

prepare_edge_nodes_mat.py позволяет создавать две матрицы: матрицу краев E и матрицу характеристик узлов N.

Для создания ребер я предоставил входной файл в data/edges.txt:

Матрица ребер E создается из ввода ребер плюс последний столбец, который определяет graph_id. graph_id в данном случае равен 0, так как нам нужны предсказания, ориентированные на узлы. Если бы вы выполняли прогнозы на основе графиков, вы бы добавили graph_id.

Окончательное содержимое матрицы E равно [source_node, destination_node, graph_id]:

Характеристики узлов создаются как матрица с горячим кодированием с sp.eye(np.max(edges+1), dtype=np.float32).tocsr():

• sp.eye - это scipy.sparse матрица,
• np.max(edges+1) определяет индекс, в котором мы хотим иметь значение 1,
• tocsr() - сжатый формат разреженных строк

Объекты объединяются с graph_id, чтобы создать окончательную матрицу характеристик узлов N, содержание которой, таким образом, составляет [ node's features, graph_id], а размеры равны [number_of_nodes, number_of_nodes+1]:

В этом случае метки (0 или 1) назначаются как:

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

2. От матриц к входам GNN

prepare_GNN.py помогает создавать входные данные для нейронной сети из матриц E и N.

Первый результат - это inp матрица. Строки 22–36 показывают, как создать входную матрицу, которая представляет собой конкатенацию между матрицей ребер E и характеристиками узлов N. Конечным содержанием является[source_node, destination_node, source_features, destination_features]. Например, для первого края между узлами 0 и 1 содержимое inp:

Второй выход - arcnode, который кодирует информацию о краях в формате SparseMatrix, размеры которого равны [number_of_nodes, number_of_edges] (в данном случае 34x78). Разреженный формат позволяет экономить память и идентифицировать только пару индексов строка-столбец со значением 1, иначе 0.

3. Определите функцию ввода и вывода.

input_and_output_functions.py определяет базовые функции перехода и вывода как MLP. Основными функциями для class Net являются netSt и netOut, которые создают NN для f𝓌 и g𝓌 соответственно, что определяет двухуровневую нейронную сеть. netSt получает характеристики узлов, размерность которых составляет 70, и повторно отображает эти объекты с 3 скрытыми узлами с помощью tanh функции активации. netOut имеет аналогичную архитектуру, он получает двумерный ввод, который повторно отображается через 3 узла и возвращает окончательный результат прогноза после приложения softmax:

4. Почти готово к работе: основная GNN

Последний шаг - это GNN.py, где мы собираемся определить, как должна работать архитектура нейронной сети. Функции convergence, condition и Loop являются основными частями всей архитектуры, где обновляются состояния узлов.

Сеанс обучения начинается с строки 293, а функция Loop инкапсулируется в self.loss_op. В Loop tf.while_loop, строка 221 вызывается для запуска condition и convergence. Эта последняя функция обновляет текущее состояние узлов:

На рис.10 a[:,1] - это входная матрица inp[:,1], а именно все destination_nodeиндексы. tf.gather возвращает все значения old_state для каждого узла назначения, в результате получается матрица 78x2, значения которой являются нулями на первой итерации, поскольку old_state сначала инициируется как матрица нулей, np.zeros((ArcNode.dense_shape[0], self.state_dim)) (строка 261).

sl = a[:, 2:] возвращает все функции source_node и destination_node (размеры 78x68), которые затем объединяются как inp для функции переходной нейронной сети. Состояние выхода из f𝓌 обновляется соединением ребер посредством умножения матриц sparse_tensor_dense_matmul. Новое состояние передается обратно в Loop функцию (строка 237), а затем используется в качестве входных данных для функции вывода g𝓌: out=self.net.netOut(stf)

Клуб карате в действии

Теперь вы готовы к запуску karate.py !!!

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

Основная часть скрипта karate.py находится в строке 61, где выполняется шаг обучения. Вам решать, хотите ли вы сохранить окончательные результаты как gif и если вы хотите визуализировать результаты нейронной сети в tensorboard - здесь команда для открытия tensorboard с окончательным выводом:

venv/bin/tensorboard --logdir tmp/path/to/folder_with_out.tfevents

Подключите ваш браузер к http://localhost:PORT, где порт определяется как вывод в терминале, чтобы иметь полную работоспособность tensorboard

Основная форма вывода g.Train - loop_val. Эта переменная сообщает:

• Значения прогноза loop_val[0] узлов
• loop_val[1] количество итераций, выполненных для обновления состояний
• loop_val[2] текущие позиции узлов
• Особенности loop_val[3] узлов

На рис. 11 анимирован обучающий прогон, от первоначального предположения, когда нет прогнозов для узлов, до конца, когда существует линейное разделение между узлами.

Это все на сегодня! Следите за новостями о графиках и машинном обучении очень скоро !!!!

Если у вас возникнут вопросы или комментарии, присылайте мне электронное письмо по адресу [email protected] или прямо здесь, в Medium.