Краткое изложение способов заставить свои сети работать быстрее и с меньшим объемом памяти.

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

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

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

Анализ сложности платформы передачи сообщений

Структура передачи сообщений состоит из агрегирования информации от соседей узла вместе с информацией самого узла для создания представления узла.

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

Давайте вспомним, что каждый слой, добавленный в GNN, представляет собой еще один переход в сети.

Теперь, если мы посмотрим на архитектуру GraphSAGE [1], которая выбирает фиксированное количество соседей для каждого узла на каждом уровне, мы увидим, как потребление памяти начинает выходить из-под контроля.

Пусть F будет количеством объектов, которые у вас есть в наборе данных X сети, а L будет количеством слоев. Для начала у вас будет потребление памяти O(LF²) для хранения весовых матриц сети. Это само по себе не является большой проблемой.

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

Пусть b будет размером вашего пакета, а r будет количеством узлов, которые вы выбираете с помощью GraphSAGE. Предположим, вы выбираете одинаковое количество узлов на слой. В этом случае объем памяти, который вам понадобится, будет равен O(bFr^L). Более подробную информацию об этом расчете можно найти в [2]

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

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

Давайте теперь рассмотрим некоторые из тактик, которые исследователи использовали, чтобы попытаться решить проблему масштабируемости для GNN.

Методики выборки

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

Выборка узла

Это методология, реализованная GraphSAGE, которую мы только что видели. Идея состоит в том, что нам, возможно, не нужно рассматривать всю окрестность узла во время обучения, и вместо этого мы можем выбрать несколько узлов.

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

Выборка подграфа

Идея выборки подграфов заключается в том, что может быть способ разбить действительно большую сложную сеть на более мелкие компоненты, а затем объединить эти компоненты во время обучения. Эта методология имеет два основных примера: ClusterGCN [2] и GraphSAINT [3].

ClusterGCN применяет алгоритм кластеризации (или алгоритм обнаружения сообщества) к графу перед обучением. Таким образом, сгенерировав несколько кластеров (подграфов), можно получить готовую к использованию партию подграфов.

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

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

Выборка слоя

Стратегия выборки слоев состоит из выборки узлов, которые будут рассматриваться на каждом уровне. Обратите внимание, что это отличается от выборки узлов. При выборке узлов каждый узел проходит через каждый слой, просто вычисляя изменения соседей. При выборке слоев один слой может вообще не иметь одного узла.

Основным примером такой стратегии является FastGCN [4]. Архитектура предполагает независимость между узлами, а затем применяет некоторые приближения Монте-Карло для создания выборки.

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

Упрощение архитектуры с помощью предварительных вычислений

Другая категория стратегий масштабирования GNN — это упрощение архитектур. Идея такого рода стратегии состоит в том, чтобы сломать структуру передачи сообщений, определенную в классической статье GCN [5], в пользу другого типа архитектуры, которая лучше масштабируется за счет предварительного вычисления. Мы рассмотрим два примера такой архитектуры.

Упрощение сверточных нейронных сетей графа (SGC)

Эта архитектура [6] начинается с гипотезы о том, что хорошую производительность GNN обеспечивает агрегация соседей, а не нелинейность (ReLU и другие) между уровнями GNN.

Если вы удалите нелинейности, вы увидите, что вся GNN начинает выглядеть как последовательность матричных умножений. Возьмем, к примеру, трехслойную сеть:

Где S — нормализованная матрица смежности, X — вектор признаков, а P — весовые матрицы сетевых слоев.

Хорошо видно, что вся левая часть этих умножений не зависит от весов сети. Это означает, что мы можем умножить его перед обучением сети.

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

Масштабируемые нейронные сети начального графа (SIGN)

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

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

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

Заключение

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

[1] Гамильтон, Уильям и Ин, Рекс и Лесковец, Юре. (2017). Обучение индуктивному представлению на больших графиках.

[2] Чан, Вей-Линь и Лю, Сюаньцин и Си, Си и Ли, Ян и Бенжио, Сами и Се, Чо-Джуй. (2019). Cluster-GCN: эффективный алгоритм обучения сверточных сетей с глубокими и большими графами.

[3] Цзэн, Ханьцин и Чжоу, Хункуан и Шривастава, Аджитеш и Каннан, Раджгопал и Прасанна, Виктор. (2020). GraphSAINT: индуктивный метод обучения на основе графовой выборки.

[4] Чен, Цзе и Ма, Тэнфэй и Сяо, Цао. (2018). FastGCN: быстрое обучение с помощью графовых сверточных сетей с помощью выборки по важности. ICLR.

[5] Кипф, Томас и Веллинг, Макс. (2016). Полууправляемая классификация с использованием графовых сверточных сетей.

[6] Ву, Феликс и Чжан, Тяньи и Соуза, младший и Фифти, Кристофер и Ю, Тао и Вайнбергер, Килиан. (2019). Упрощение граф сверточных сетей.

[7] Росси, Эмануэле и Фраска, Фабрицио и Чемберлен, Бен и Эйнар, Давиде и Бронштейн, Майкл и Монти, Федерико. (2020). ЗНАК: Масштабируемые нейронные сети начального графа.