График Attention Networks, объяснение статьи

или как предсказать белок-белковые взаимодействия?

В этой статье я собираюсь исследовать GraphML, тему, которой в последнее время уделяется много внимания. Хотя я далек от того, чтобы быть экспертом в этой области, я расскажу о некоторых основах и углублюсь в статью GAT (Graph Attention Networks) Петара Величковича, которая была опубликована в ICLR еще в 2018 году, до того, как он стал частью отличной DeepMind. команда.

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

Что такое графики?

График — это специальная структура данных, состоящая из узлов (или вершин), которые для простоты можно представить как точки на 2D-плоскости или в 3D-пространстве. и ребра, которые соединяют узлы друг с другом. Давайте рассмотрим несколько примеров, но, если вы уже знакомы с графиками, можете пропустить этот раздел.

Графы могут быть направленными (каждое ребро имеет свое направление) или неориентированными, иметь (или не иметь) циклы (цикл — это замкнутая цепочка из некоторого количества вершин, соединенных вместе). ), быть мультиграфами (допускается несколько ребер между двумя узлами) и т. д. Однако мы не будем заострять внимание на всех этих характеристиках в целях экономии времени, а смело присматриваемся самостоятельно.

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

Другое дело, что графы — довольно гибкие структуры. Например, разные узлы могут значительно различаться по количеству соседей (узлов, соединенных только одним ребром). Это затрудняет использование графиков в качестве входных данных для нейронных сетей, которые особенно хороши при обработке табличных или, по крайней мере, некоторых данных с фиксированной структурой.

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

Twitter использует Graph Networks для обнаружения фейковых новостей

GNN используются в Картах Google для более точного прогнозирования расчетного времени прибытия.

Что такое GraphML?

Теперь, когда мы знакомы с концепцией графа, давайте перейдем к теме этой статьи: Машинное обучение графов.

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

Но прежде чем приступить к изучению GAT (Graph Attention Networks), давайте обсудим методы, которые использовались еще до выхода статьи.

Спектральные и пространственные методы

Спектральные методы используют матрицу Лапласа, которую можно определить как

В Бруне и соавт. (2014), операция свертки определяется в области Фурье путем вычисления собственного разложения лапласиана графа, что приводит к потенциально интенсивным вычислениям и нелокализованным в пространстве фильтрам.

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

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

Пространственные методы оперируют и определяют свертки (так же, как в CNN, помните?) непосредственно на графике. В основном эти методы можно объяснить следующим образом:

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

В GraphSAGE, представленном в 2017 году Гамильтоном и др., представления узлов были обновлены путем агрегирования векторов признаков выборки фиксированного размера окрестности каждого узла. Это агрегирование может быть, например, средним значением.

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

Итак, давайте подытожим все, что у нас есть, прежде чем объяснять GAT:

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

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

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

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

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

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

Задача и наборы данных

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

Трансдуктивное обучение*

Набор данных Cora состоит из 2708 научных публикаций, отнесенных к одному из семи классов. Сеть цитирования состоит из 5429 ссылок. Каждая публикация в наборе данных описывается вектором слов со значениями 0/1, указывающим на отсутствие/наличие соответствующего слова в словаре. Словарь состоит из 1433 уникальных слов.

Набор данных CiteSeer состоит из 3312 научных публикаций, отнесенных к одному из шести классов. Сеть цитирования состоит из 4732 ссылок. Каждая публикация в наборе данных описывается вектором слов со значениями 0/1, указывающим на отсутствие/наличие соответствующего слова в словаре. Словарь состоит из 3703 уникальных слов.

Набор данных PubMed состоит из 19 717 научных публикаций из базы данных PubMed, касающихся диабета, отнесенного к одному из трех классов. Сеть цитирования состоит из 44338 ссылок. Каждая публикация в наборе данных описывается взвешенным вектором слов TF/IDF из словаря, состоящего из 500 уникальных слов.

Изучите набор данных здесь https://huggingface.co/datasets/pubmed

Индуктивное обучение*

Набор данных о взаимодействии белок-белок состоит из 94359 ребер (включая собственные ребра), 20 обучающих графов, 2 проверочных графов и 2 тестовых графов. Всего PPI имеет 121 класс, и с каждым узлом может быть связано несколько классов, поэтому это набор данных классификации с несколькими метками. Каждый узел имеет 50 признаков, это комбинация наборов позиционных генов, наборов мотивных генов и иммунологических сигнатур.

* Transductive — у вас есть один график, вы разделяете некоторые узлы (но не график) на наборы train/val/test. Во время обучения вы будете использовать только метки из ваших учебных узлов. Но во время прямого распространения, из-за особенностей работы пространственных GNN, вы будете агрегировать векторы признаков от ваших соседей, и некоторые из них могут принадлежать val или даже тестовым наборам! Главное дело в том, что вы неиспользуете информацию об их ярлыках, а используете структурную информацию и их функции.

* Индуктивный — у вас есть набор обучающих графов, отдельный набор оценочных графов и, конечно же, отдельный набор тестовых графов.

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

Архитектура ГАТ

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

Ввод

Набор функций узла h

Имеется Nузлов, каждый из которых имеет F функций.

Выход

Набор различных узловых функций h’ потенциально разной кардинальности

Шаги (или метод .forward)

Линейное преобразование применяется к каждому узлу, теперь каждый узел описывается F’признаками.

2. Рассчитайте важность функций j для узла i, применяя общее самостоятельное вниманиеa. Важность описывается коэффициентами внимания

a — однослойная нейронная сеть с прямой связью, параметризованная весовым вектором и применяющая LeakyReLU с отрицательным наклоном 0,2.

3. Нормализация коэффициентов с помощью SoftMax

Конкатенация — это вектор 2F'признаков, левостороннее умножение на a дает нам скаляр, к которому мы сначала примените LeakyReLU, а затем SoftMax.

4. Агрегированные представления из окрестности узла с полученными коэффициентами

Авторы используют многоголовое внимание, усредняя K независимых механизмов внимания, поэтому окончательный результат вычисляется как

Чтобы построить саму сеть, мы просто складываем несколько слоев внимания графа.

Вы можете ознакомиться с реализацией PyTorch этой модели Алексы Гордич, которую порекомендовал сам Петар.

Эксперименты

Для трансдуктивных задач применялась двухуровневая модель GAT:

На первом уровне использовалось 8 головок внимания, каждая из которых вычисляла F’ = 8 признаков.
Второй уровень был одним уровнем внимания, который вычислял признаки C, где C — количество классов.
Регуляризация L2, а также отсев с p = 0,6 применялись к входам обоих слоев.

Для индуктивной задачи использовалась трехслойная модель GAT:

Оба первых двух слоя состоят из K = 4 головок внимания, вычисляющих F’ = 256 функций.
Последний слой используется для (многометочной) классификации: K = 6 головок внимания, вычисляющих по 121 признаку каждая, которые усредняются, после чего следует активация логистической сигмоиды.
Ни регуляризация L2, ни отсев не применялись, однако между промежуточными слоями использовались пропускные соединения.

Обе модели использовали инициализацию Adam SGD и Glorot (Xavier normal).

Полученные результаты

GAT превзошел Graph Convolutional Network на 2% с почти тем же стандартом. ценить

Модель GAT улучшила уровень техники в индуктивной настройке, ранее достигнутый GraphSAGE (об этом упоминалось ранее), на 20,5%. Он также улучшил ту же архитектуру GAT с механизмом постоянного внимания.

Выводы

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

Преимущества использования архитектуры, основанной на внимании:

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

А вот классная картинка, показывающая, как работает внимание в наборе данных Взаимодействие белок-белок.

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

Эта статья изначально была создана как часть моих университетских исследований и во многом вдохновлена Алексой Гордичем, так что не стесняйтесь следовать за ним :) https://gordicaleksa.medium.com/how-to- начало работы с графом машинного обучения afa53f6f963a