Применение механизма свертки и внимания к графикам

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

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

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

Хватит разговоров, давайте начнем с основ!

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

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

Граф — это структура G, состоящая из узлов V, соединенных между собой ребрами E.

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

Ребра между узлами представляют отношения, а именно два узла связаны, если между ними есть отношения (вспомните концепцию follows в Instagram), и они могут быть ненаправленными, если отношения симметричны, или направленными, если отношения отношения не симметричны.

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

Введение в графовые нейронные сети

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

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

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

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

Поэтому исследователи задались вопросом: можно ли обобщить операцию свертки на графах?

Они вышли с двумя классами методов:

  • Спектральные методы: как вы можете догадаться из названия, они как-то связаны с частотной областью. Они сохраняют строгую концепцию свертки, но их немного сложно понять. Несмотря на то, что они более математически обоснованы, они редко используются из-за их вычислительной стоимости.
  • Пространственные методы: они представляют собой достойную аппроксимацию спектральных методов, несмотря на то, что они не столь математически строги. Проще понять, они основаны на концепции, согласно которой каждый узел должен собирать информацию о себе и своих соседях K-hop.

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

Начнем: граф сверточных сетей

Первый успешный пример применения глубокого обучения и свертки на графах был представлен на конференции Kipf & Welling, 2017, где были представлены Graph Convolutional Networks.

Основная идея их алгоритма заключается в следующем:

  • Вы применяете линейную проекцию ко всем векторам признаков ваших узлов.
  • Вы агрегируете их (среднее, сумма, concat…)
  • Вы комбинируете проекцию узла вместе с проекциями его соседей.

Вот процесс в формулах:

Уравнение 1 представляет собой математическое выражение перечисленных выше шагов. Вложение каждого узла получается путем проецирования каждого соседа в другое пространство, усреднения (но могут использоваться и другие виды агрегирования) и их объединения с проекцией самого узла. Последним шагом, как обычно в DL, является проход функции активации.

Это гениально, не так ли? Однако, пока я читал это, я был немного озадачен тем, как вы кодируете это. Хорошо, у меня есть граф, но как мне эффективно найти соседей каждого узла, чтобы объединить их функции? Легко, вы используете матрицу смежности A!

Матрица смежности A, размер которой составляет N² (N – количество узлов), описывает, как связаны узлы: A (v,u) = 1, если узлы v, u связаны.
Например, если вы просто хотите агрегировать характеристики всех соседей (узлов с 1 переходом) узла, вы просто делаете:

Теперь, если вы продолжите повторять этот процесс по k-шагам, вы агрегируете признаки от соседей по k-ходам, и вышеприведенное выражение может быть легко выражено следующим образом, где добавлена ​​линейная проекция:

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

Поэтому параметр k регулирует как количество слоев, так и количество прыжков, которые вы хотите изучить. Это что-то не супер очевидное и вполне умное! Но… как мне выбрать k?

Отличительной чертой GCN является то, что они обычно не являются глубокими сетями, а скорее очень мелкими (в большинстве случаев достаточно двух слоев!). На сегодняшний день непонятно, почему мелкие сети работают лучше, но за этим стоит некоторая интуиция:

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

Это круто, правда? Похоже, что несколько слоев (и, следовательно, параметров) делают свое дело! Ну да, но GCN обычно справляются с проблемами масштабируемости из-за размера графов. Подумайте о применении уравнения 3 к графу с миллионами узлов: матрица смежности будет огромной! К счастью, есть статьи, посвященные методам обучения на таких больших графах, например, GraphSAGE.

Что вы можете сделать с GCN?

После того, как вы построили свою сеть, все готово для решения таких задач, как:

  • классификация узлов, т. е. классификация каждого узла в графе.
  • классификация графа, т. е. классификация всего графа
  • прогнозирование связи, то есть прогнозирование того, соединены ли два узла.
  • кластеризация узлов, т. е. группировка наборов узлов на основе их характеристик и/или их связности.

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

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

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

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

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

Примеры успешных приложений GCN:

Механизм внимания в GCN: Graph Attention Networks

Как мы объясняли ранее, один из этапов обучения GCN состоит из сбора информации от соседей. Этот шаг агрегирования может быть взвешен таким образом, чтобы присвоить важность соседям, и это идея, лежащая в основе механизма внимания и Graph Attention Networks. сильный>.

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

Вот как работает слой внимания:

По сути, механизм внимания изучает вес для каждого края сети.

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

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

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

В формулах:

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

Заключение

Это все на данный момент. И пока только. Я рассчитываю просмотреть дополнительные ресурсы в ближайшие недели, так как есть еще методы, которые я еще недостаточно изучил или даже не видел.

Надеюсь, я убедил вас, что Graph Learning стоит вашего времени. Кто знает, может быть, это может быть возможным выбором для вашего следующего проекта. Мне потребовалось некоторое время, чтобы впитать все это, так как это не так знакомо, как другие темы DL, поэтому не вините себя, если не все кристально ясно в начале (но если это так, возможно, я хорошо поработал!) .

Спасибо за прочтение!

Все изображения, если не указано иное, принадлежат автору.

Посетите мою личную страницу или свяжитесь со мной в LinkedIn!