Рекомендательные системы с GNN в PyG

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

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

Потеря BPR для одного пользователя uсоставляет:

И окончательная потеря BPR:

Чтобы эффективно оценить потери BPR и оптимизировать f_theta, мы обучаем модель путем выборки мини-пакетов. Для каждого мини-пакета мы выбираем набор пользователей и для каждого пользователя выбираем один положительный элемент (элемент из положительного ребра, содержащего рассматриваемого пользователя) и один отрицательный элемент.

Затем потери BPR для каждой мини-партии можно уменьшить до:

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

Графовые нейронные сети (GNN)

Графовые нейронные сети (GNN) предназначены для изучения структурных и семантических паттернов во входных графах, относящихся к различным целевым функциям, аналогично другим областям глубокого обучения. Они работают, передавая сообщения между узлами вдоль своих ребер и объединяя их для каждого узла для обновления. Это происходит итеративно (отсюда и «глубокое» обучение), что позволяет отдельным узлам собирать информацию от соседей с несколькими переходами и делать выводы о структурных особенностях вокруг них. Этот метод достигает современного состояния с его многочисленными вариантами и приложениями на графиках социальных сетей, графиках химических соединений, графиках трафика и, среди многих других, графиках рекомендательных систем.

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

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

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

Однако GNN также должны соответствовать еще двум требованиям: 1) инвариантность перестановок и 2) эквивалентность перестановок.

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

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

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

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

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

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

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

Как использовать GNN для задачи рекомендации

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

Традиционно CF моделируется с использованием матричной факторизации. Как описано ранее, эта простая модель использует score(u,v) = f_theta(u, v)в качестве функции оценки, чтобы указать, насколько вероятно, что кому-то понравится рекомендация. Хотя эта модель является хорошим первым шагом к пониманию того, как разрабатывать более сложные модели рекомендаций, она явно не собирает достаточно информации. В частности, матричная факторизация не может собирать информацию о структуре графа, такую ​​как пути K-hop между двумя узлами, которые являются информацией, которая может быть получена с использованием подходов глубокой нейронной сети. Давайте посмотрим, как мы можем использовать модели на основе GNN с более сложным выбором функции f для сбора этой информации.

Глубокие подходы с использованием GNN могут явно фиксировать локальную структуру графа, а также структуру графа высокого порядка. Оба эти компонента важны для системы рекомендаций, чтобы успешно генерировать вложения узлов пользователей и элементов. Наиболее полезным свойством GNN является передача сообщений, которая позволяет распространять вложения по краям узла. В результате для GNN, использующих K слоев, каждый узел знает о структуре графа, которая составляет K. -отскакивает. Другой способ подумать об этом — рассмотреть, как пользовательский узел может просматривать интересующие его элементы, находить пользовательские узлы, которые также проявляют интерес к тем же элементам, и получать информацию от других пользовательских узлов для обновления своего собственного внедрения. Точно так же узел элемента может посмотреть, что интересует пользователей, и найти другие элементы, которые интересуют пользователей, чтобы создать вложение элемента на основе этих других элементов. Это позволяет пользователям со схожими интересами, а также элементам, в которых заинтересованы похожие пользователи, иметь вложения, сходящиеся друг к другу, и оптимизировать функцию оценки для рекомендации.

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

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

где l — количество слоев в сети.

Совместная фильтрация нейронных графов (NGCF)

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

Давайте разберем эти функции, в частности, взглянув на них с точки зрения внедрения пользователя (e_u).

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

Функция сообщения реализована в PyG следующим образом:

def message(self, x_j, x_i, norm):
     return norm.view(-1, 1) * (self.lin_1(x_j) + self.lin_2(x_j * x_i))

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

def aggregate(self, x, messages, index):
     out = torch_scatter.scatter(messages, index, self.node_dim, reduce="sum")
     return out

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

def forward(self, x, edge_index):
     norm = compute_normalization(x, edge_index)
     out = self.propagate(edge_index, x=(x, x), norm=norm)
     # Update step
     out += self.lin_1(x)
     out = F.dropout(out, self.dropout, self.training)
     return F.leaky_relu(out)

Объединив эти функции сообщения и переадресации, мы можем создать класс PyG MessagePassing для описания одного уровня NGCF:

class NGCFConv(MessagePassing):
     def __init__(self, latent_dim, dropout, bias=True, **kwargs):
          super(NGCFConv, self).__init__(aggr='add', **kwargs)
          self.dropout = dropout
          self.lin_1 = nn.Linear(latent_dim, latent_dim, bias=bias)
          self.lin_2 = nn.Linear(latent_dim, latent_dim, bias=bias)
          self.init_parameters()

     def init_parameters(self):
          nn.init.xavier_uniform_(self.lin_1.weight)
          nn.init.xavier_uniform_(self.lin_2.weight)

     def forward(self, x, edge_index):
          # Compute normalization
          from_, to_ = edge_index
          deg = degree(to_, x.size(0), dtype=x.dtype)
          deg_inv_sqrt = deg.pow(-0.5)
          deg_inv_sqrt[deg_inv_sqrt == float('inf')] = 0
          norm = deg_inv_sqrt[from_] * deg_inv_sqrt[to_]
          # Start propagating messages
          out = self.propagate(edge_index, x=(x, x), norm=norm)
          out += self.lin_1(x)
          out = F.dropout(out, self.dropout, self.training)
          return F.leaky_relu(out)

     def message(self, x_j, x_i, norm):
          return norm.view(-1, 1) * (self.lin_1(x_j) + self.lin_2(x_j * x_i))

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

def forward(self, edge_index):
     emb0 = self.embedding.weight
     embs = [emb0]
     emb = emb0
     for conv in self.convs:
          emb = conv(x=emb, edge_index=edge_index)
          embs.append(emb)
          out = torch.cat(embs, dim=-1)
          return out

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

def bpr_loss(users_emb, pos_emb, neg_emb):
     pos_scores = torch.mul(users_emb, pos_emb).sum(dim=1)
     neg_scores = torch.mul(users_emb, neg_emb).sum(dim=1)
     bpr_loss = torch.mean(F.softplus(neg_scores - pos_scores))
     return bpr_loss

LightGCN

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

Более того, поскольку основная цель схем совместной фильтрации состоит в том, чтобы найти других похожих пользователей на основе их предпочтений, простого распространения вложений узлов по графу путем агрегирования соседей достаточно, чтобы получить информацию, необходимую для создания подходящих вложений для прогнозирования того, понравится ли пользователю. пункт. Простой способ визуализировать это представлен на следующем рисунке, где пользователи находятся слева, а элементы — справа, и мы видим, что встраивание выделенного узла зависит от узлов, удаленных на K-hops, в зависимости от того, сколько слоев используется в модели LightGCN.

Теперь мы рассмотрим различные компоненты модели LightGCN и ее реализацию в PyG.

Новые правила обновления для внедрений пользователей и элементов теперь описываются следующими двумя функциями.

Давайте разберем эти функции, в частности, взглянув на них с точки зрения внедрения пользователя (e_u).

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

Функция сообщения реализована в PyG следующим образом:

def message(self, x_j, norm):
     return norm.view(-1, 1) * x_j

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

def aggregate(self, x, messages, index):
     out = torch_scatter.scatter(messages, index, self.node_dim, reduce="sum")
     return out

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

Термин alpha_k обычно задается как 1/(K+1), что означает, что суммирование просто среднее значение выходных вложений всех слоев K, а также начальное входное вложение, которое изучено. Причина, по которой суммируются промежуточные вложения, заключается в следующем:

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

Объединив эти функции сообщения и переадресации, мы можем создать класс PyG MessagePassing для описания одного слоя LightGCN:

class LightGCNConv(MessagePassing):
      def __init__(self, **kwargs):
            super().__init__(aggr='add')

      def forward(self, x, edge_index):
            # Compute normalization
            from_, to_ = edge_index
            deg = degree(to_, x.size(0), dtype=x.dtype)
            deg_inv_sqrt = deg.pow(-0.5)
            deg_inv_sqrt[deg_inv_sqrt == float('inf')] = 0
            norm = deg_inv_sqrt[from_] * deg_inv_sqrt[to_]
            # Start propagating messages
            return self.propagate(edge_index, x=x, norm=norm)
      def message(self, x_j, norm):
           return norm.view(-1, 1) * x_j

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

def forward(self, edge_index):
      emb = self.embedding.weight
      embs = [self.embedding.weight]
      for conv in self.convs:
            emb = conv(x=emb, edge_index=edge_index)
            embs.append(emb)
      # perform weighted sum on output of all layers to yield final embedding
      embs = torch.stack(embs, dim=0)
      out = torch.mean(embs, dim=0)
      return out

Несмотря на то, что вложения LightGCN имеют размер, отличный от вложений, созданных NGCF (поскольку LightGCN использует взвешенную сумму вложений промежуточного уровня, а не объединяет их), мы можем использовать ту же реализацию потери BPR для одного мини-пакета.

Результаты и заключение

Теперь, когда мы реализовали LightGCN и NGCF в PyG, давайте посмотрим, какой из них лучше работает с набором данных MovieLens 100k!

Мы разделяем набор данных на 80/20 разбиение на поезд-тест и обучаем обе модели, используя процедуру мини-пакетирования, описанную выше. Удерживаемые ребра в тестовом наборе используются для оценки точности@K и отзыва@K после каждой эпохи обучения.

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

• Кривые точности @ 20 и полноты @ 20 для NGCF значительно менее гладкие, чем у LightGCN.
• Даже несмотря на то, что потери для NGCF продолжают снижаться, кривые точности@20 и отзыва@20 выходят на плато и колеблются.
• LightGCN работает лучше, чем NGCF, по обеим метрикам. В частности, LightGCN достигает показателя отзыва@20, равного 0,3535, по сравнению с 0,3136 для NGCF, что на 13% больше. Он также обеспечивает точность@20 0,2397 по сравнению с 0,2134, что на 12% больше.

Это означает, что мы можем воспроизвести один из ключевых результатов статьи LightGCN на новом наборе данных. По трем наборам данных авторы LightGCN обнаружили, что он превосходит NGCF с тем же отрывом, что и наши эксперименты с MovieLens 100k здесь.

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

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

Надеюсь, вы усвоили важный урок, чтобы не слишком усложнять свою модель, поскольку LightGCN на самом деле работает лучше, хотя и не так сложен, как NGCF. Или вы можете просто пойти по простому пути в следующий раз и позволить алгоритму выбрать фильм для вашей следующей вечеринки с просмотром Netflix ;)

Бумажные ссылки

1. Харпер, Ф. Максвелл, и Констан, Джозеф А. «Наборы данных MovieLens: история и контекст». Транзакции ACM в интерактивных интеллектуальных системах (TiiS) 5, 4. 2015.
2. Хэ, Сяннан и др. «LightGCN: упрощение и усиление сети свертки графов для рекомендаций». Материалы 43-й Международной конференции ACM SIGIR по исследованиям и разработкам в области информационного поиска. 2020.
3. Ван, Сян и др. «Совместная фильтрация нейронных графов». Материалы 42-й Международной конференции ACM SIGIR по исследованиям и разработкам в области информационного поиска. 2019.

Ссылки на изображения

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