Пробираясь через графовые нейронные сети

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

Темы

График и его мотивация
Свертки графа
Сети привлечения внимания
Нейронные сети с закрытым графом
Автокодировщики графиков
График SAGE
История GCN

График и его мотивация

Поскольку эра глубокого обучения продвинулась до сих пор, у нас есть много современных решений для наборов данных, таких как текст, изображения, видео и т. д. В основном эти алгоритмы состоят из MLP, RNN, CNN, преобразователей и т. д., которые превосходно работают с ранее упомянутые наборы данных. Однако мы также можем встретить некоторые неструктурированные наборы данных, подобные показанным ниже:

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

Давайте кратко разберемся, как выглядит график:

Граф G представлен двумя ключевыми элементами: {V, E}, где V – набор узлов, а E. strong> — это набор ребер, определенных среди его узлов. Графовая нейронная сеть имеет функции узлов и функции краев, где функции узлов представляют атрибуты отдельных элементов системы, а функции краев представляют отношения, взаимодействие или связность. среди элементов системы.

Возможности узла:

Пограничные функции:

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

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

Граф сверточных сетей

Таким образом, в задаче о графе нам дан граф G(V, E), и цель состоит в том, чтобы изучить представления узлов и ребер. Для каждой вершины iнужен вектор признаковVᵢ, а связь между узлами может быть представлена с помощью матрица смежности A.

GCN можно представить с помощью простой нейронной сети, математическое представление которой выглядит следующим образом:

где Hᵢˡ — вектор признаков узла i в lᵗʰ слой, Wˡ— матрица весов, используемая для слоя lᵗʰи >N(i) — набор узлов в окрестности узла i. Обратите внимание, что Hᵢ⁰=Vᵢ

Теперь, как вы можете видеть, веса являются общими для всех узлов в заданном слое, подобно обычным сверточным фильтрам, и вектор признаков узла вычисляется после выполнения некоторой математической операции (здесь взвешенная сумма с использованием параметра ребра) над его соседние узлы (что также похоже на CNN), мы придумали термин Graph Convolutional Network, и Wˡможно назвать фильтром в слойл.

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

Для решения первой проблемы применяется петля, а для решения второй используется нормализованная форма матрицы смежности, показанная ниже:

Самостоятельная петля: Â =A+I
Нормализация: Â = (D^(-1/2)) Â(D^(-1/2))

где I – единичная матрица формы A, а D – диагональная матрица, каждое диагональное значение которой соответствует степени соответствующего узла в матрице. В. На каждом уровне информация передается узлу из его окружения, поэтому этот процесс называется Передача сообщений.

Теперь поговорим о некоторых вариантах простой свертки графа, о которых мы говорили.

Графические сети внимания

Внимание не является чем-то новым в мире технологий. Он широко использовался с такими архитектурами, как LSTM, GRU, CNN и т. д. Теперь он даже может быть единственным и наиболее важным строительным блоком моделей на основе трансформаторов, таких как BERT и GPT. Итак, основная цель механизма внимания состоит в том, чтобы сосредоточить внимание на некоторых ключевых областях ввода, изучая для них веса в виде вероятностей. Давайте кратко посмотрим, как это работает, когда оно используется в графовой нейронной сети.

Слева представлено модифицированное уравнение для свертки графа. Разница заключается в термине:

Это не что иное, как веса внимания. Для каждого соседнего узла j узла i в lᵗʰузнается вес, который обозначает его важность при обновлении вектора признаков узла i. Поэтому вместо того, чтобы находить простую взвешенную сумму соседей, мы берем больше информации от узлов, чьи веса внимания больше, и меньше информации от узлов с меньшим весом.

Теперь эти веса можно узнать различными способами, такими как softmax или некоторые функции сквоша, как показано ниже:

Чтобы сделать вещи более интересными, мы также можем использовать подход с несколькими головками, который будет использовать Kголовок вместо одной и, наконец, брать среднее (или объединять) всех векторов признаков, полученных от голов K. Иллюстрацию можно найти на рисунке ниже:

Нейронные сети с закрытым графом

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

Состояния узлов и состояния сообщений аналогичны скрытым состояниям и состоянию ячейки в ячейке RNN. Приведенная ниже формула ясно объясняет теорию:

В приведенных уравнениях hˡᵢявляется состоянием узла узлаiin слояl иmˡᵢэто состояние сообщенияузла iв слоеl. Uи Mможно понимать как стандартные нейронные сети.

Автокодировщики графиков

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

Имея граф G(X, A), мы изучаем скрытое представление узлов, изучая распределение q(z|X, A) . Затем мы пытаемся восстановить матрицу смежности Â,изучая распределениеp(A|Z).

График SAGE

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

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

где hᵥᵏ — вектор признаков узла vв слоеk, A иBобучаемые веса. Агрегированная информация о соседстве и сам вектор признаков узла объединяются путем выполнения некоторого взвешивания, а затем передаются через нелинейную функцию σ, чтобы получить вектор признаков узла для следующего слоя. AGG — это функция-агрегатор, которая может иметь множество форм, таких как агрегатор среднего значения, пула или LSTM, как показано ниже:

Немного истории GCN

Во всех методах, которые мы обсуждали выше, использовались пространственные фильтры, но у нас есть и другой тип фильтров в графовых нейронных сетях, СПЕКТРАЛЬНЫЕ ФИЛЬТРЫ.

Использование спектральных фильтров требует, чтобы мы вошли в спектральную область (область Фурье), что также требует, чтобы мы вычислили разложение собственного вектора лапласиана графа L, которое является специальной нормализованной формой матрицы смежности графа G. >

L = I — Â

где Â — нормализованная матрица смежности, обсуждавшаяся в начале блога, а I — матрица идентичности.

L разлагается в виде L=VΛVᵀ, где V — матрица собственных векторов L, а Λ — диагональная матрица, диагональные значения которой соответствуют собственному значению L.

Уравнение для прямого прохода приведено ниже:

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

Аппроксимация свертки графа Чебышева, введенная Defferrard et al., NeurIPS, 2016, предотвратила разложение лапласиана за счет использования аппроксимации Чебышева и введения параметра K. Для K=1,мы передаемфункции узлов X⁽ˡ⁾в нашу модель GNN; дляK=2,переходимX⁽ˡ⁾, AX⁽ˡ⁾ ; для K=3мы передаем X⁽ˡ⁾, AX⁽ˡ⁾, A²X⁽ˡ⁾и аналогично для K=n мы передаем X⁽ˡ⁾, AX⁽ˡ⁾, A²X⁽ˡ⁾……..AⁿX⁽ˡ⁾ в модели GNN. После создания всех признаков из nпереходов мы объединяем все векторы признаков, а затем снова применяем GNN, чтобы получить окончательные векторы признаков для узлов. Процесс становится понятным из изображения, приведенного ниже:

Аппроксимация Чебышева позволяет избавиться от спектральной области, но тем не менее требует больших вычислительных ресурсов из-за итераций n (определено нами) прыжков в одном слое.

Дальнейшее приближение и трюк с перенормировкой

Поскольку увеличение значения K приводит к увеличению количества параметров модели, мы можем ограничить значение до K=2.

A, использованная на приведенном выше рисунке, представляет собой исходную матрицу смежности без принудительного применения замкнутого контура. Использование трюка или, скажем, аппроксимации назначения одного и того же θ для θ₀ и θ₁ приводит нас к трюку с перенормировкой которые мы уже обсуждали в части GCN (добавление петли). Таким образом, приближение дает нам наш уровень GCN, который работает для 1 и 2 переходов, и если нам нужно более 2 переходов, мы можем продолжать добавлять такие слои GCN.

Вывод

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

Пробираясь через графовые нейронные сети