Всем привет! Меня зовут Александр Тришин, я работаю DS в команде персональных рекомендаций Wildberries и занимаюсь графовыми нейросетями. Мы ведем Telegram-канал @WildRecSys, где пишем статьи по нашим подходам к построению рекомендаций.

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

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

  • Что такое сверточные графовые сети, их основные компоненты и принципы работы: подробно разберем модель на user-item графе, после перейдём к item-item графу;

  • Знакомство с моделью LightGCN: архитектура, процесс обучения, недостатки (медленная сходимость и смещение в популярное) и варианты их устранения;

  • А в конце посмотрим, как это всё применять на практике: обучим сетку на датасете Movielens-25m, замерим метрики, столкнёмся с проблемами LightGCN и вместе их решим! Ноутбук прилагается ?

Что такое сверточные графовые нейросети?

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

  • взвешенным: каждому ребру поставлено в соответствие некое значение — вес ребра. Например, вес ребра может быть оценкой, которую пользователь поставил этому товару.

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

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

Разберем пример с user-item графом G := (U \sqcup I,E), где U— множество вершин, соответствующих пользователям, I — множество вершин, соотв. товарам, E — множество ребер графа.

Рассмотрим пользователя uи множество товаров N_u, с которыми он взаимодействовал. В терминах графа Nᵤ есть 1-окрестность вершины u. Агрегация информации задается функцией Agg:

\text{Agg} = \text{Agg}(\{{e}_i^{(l-1)}: i \in N_u\}),

где {e}_i^{(l-1)} — эмбеддинг товара i на (l-1) слое нашей сетки. Аналогично агрегируется информация для вершин, соответствующих товарам: если N_i — множество пользователей, которые взаимодействовали с товаром i, то

\text{Agg} = \text{Agg}(\{{e}_u^{(l-1)}: u \in N_i\}),

где {e}_i^{(l-1)} — эмбеддинг пользователя u на (l-1) слое.

В качестве функции \text{Agg} используют как несложные преобразования, такие как среднее, взвешенная сумма и конкатенация эмбеддингов, так и более сложные, такие как LSTM.

После агрегирования информации по окрестности вершины происходит обновление эмбеддинга этой вершины согласно функции \text{Comb}, которая комбинирует эту информацию и эмбеддинг вершины с предыдущего слоя:

{e}_u^{(l)} = \text{Comb}\left({e}_u^{(l-1)}, \text{Agg}\left(\{{e}_i^{(l-1)}: i \in N_u\}\right)\right), \\ {e}_i^{(l)} = \text{Comb}\left({e}_i^{(l-1)}, \text{Agg}\left(\{{e}_u^{(l-1)}: u \in N_i\}\right)\right).

Функция \text{Comb} может не зависеть от эмбеддинга самой вершины на предыдущем слое и просто возвращать результат функции \text{Agg}, может содержать обучаемые параметры и иметь вид:

\text{Comb}({e}_u^{(l-1)}, {h}_{\text{Agg}}^{(l-1)}) = \sigma({W}^l \cdot \text{CONCAT}({e}_u^{(l-1)}, {h}_{\text{Agg}}^{(l-1)})),

где {h}_{\text{Agg}}^{(l-1)} есть результат агрегирования эмбеддингов по окрестности вершины u при помощи функции \text{Agg}, \text{CONCAT}({x}, {y}) — конкатенация векторов {x} и {y}, \sigma(\cdot) — сигмоидная функция.

После последовательного применения нескольких сверток для каждой из вершин получаем набор её эмбеддингов с каждого слоя \{{e}_{\text{node}}^{(l)} : l \in \overline{0, L}\}, L — число слоёв сети. Финальный эмбеддинг каждой из вершин получается при помощи функции \text{ReadOut}, которая зависит от эмбеддингов вершины на слоях:

{e}_{\text{node}} = \text{ReadOut}\left(\{{e}_{\text{node}}^{(l)} : l \in \overline{0, L}\}\right)

В качестве функции \text{ReadOut} используют усреднение, взвешенную сумму, где веса представляют из себя выход слоя внимания, или полносвязный слой.

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

Р
Р

Имея эмбеддинги вершин-пользователей и вершин-товаров для данного пользователя можем подсчитать меру сходства его с эмбеддинга с эмбеддингов каждого из товаров:

\hat{y}_{ui} = \hat{y}({e}_u, {e}_i).

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

Обучение

Обучается сетка с использованием Pairwise Loss. За этим стоит следующая идея: эмбеддинги объектов, схожих в привычном понимании (ботинки и туфли), должны быть ближе в смысле функции \hat{y}, чем эмбеддинги непохожих объектов (ботинки и наушники). Таким образом, обучающая выборка формируется из троек (anchor, positive, negative), где anchor и positive — схожие объекты, в то время как anchor и negative — нет. Например, в случае user-item графа, в качестве anchor берется пользователь, в качестве positive — товар, с которым он взаимодействовал, в качестве negative — товар, с которым не взаимодействовал.

Однако pairwise loss можно получить и из других соображений. Пусть модель учится отличать позитивы от негативов — задача бинарной классификации. Дальше немного математики, сдобрить формулой Байеса и получится Sampled Softmax Loss:

L_{\text{SSM}} ({E}^0) = - \sum\limits_{(u, i) \in \text{Batch}} \log \left( \frac{\exp(\hat{y}_{ui})}{\exp(\hat{y}_{ui}) + \sum\limits_{j \in N} \exp(\hat{y}_{uj})} \right).

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

Итак, сверточная графовая нейросеть определяется сверткой (комбинацией \text{Agg} и \text{Comb}), функцией получения финальных эмбеддингов (\text{ReadOut}), функцией схожести (\hat{y}). Также возможны различные методы построения графа (user-item, item-item) и генерации негативных взаимодействий.

Рассмотрим теперь модель LightGCN (Light Graph Convolutional Network). Она проста в обучении и хорошо показала себя на практике.

Модель LightGCN

Архитектура Light Graph Convolution
Архитектура Light Graph Convolution

Модель LightGCN относится к сверточным графовым нейросетям. В архитектуре модели используется Light Graph Convolution, которая устроена так: в качестве функции агрегации используется взвешенная сумма:

\text{Agg}(u) = \sum\limits_{i \in N_u} \frac{1}{\sqrt{|N_u| \cdot |N_i|}} {e}_i^k, \ \ \ \ \text{Agg}(i) = \sum\limits_{u \in N_i} \frac{1}{\sqrt{|N_u| \cdot |N_i|}} {e}_u^k,

где k — номер слоя, N_u — множество товаров, с которыми взаимодействовал пользователь u, N_i — множество пользователей, которые взаимодействовали с товаром iЗаметим, что N_u, N_i — непосредственные окрестности вершин u и i, а |N_u|, |N_i| — степени этих вершин.

Функция \text{Comb} есть тождественно результат \text{Agg}:​

{e}_u^{(l)} = \text{Comb}\left({e}_u^{(l-1)}, \text{Agg}(u)\right) = \text{Agg}(u), \\ {e}_i^{(l)} = \text{Comb}\left({e}_i^{(l-1)}, \text{Agg}(i)\right) = \text{Agg}(i).

Стоит отметить, что Light Convolution не содержит обучаемых параметров (отсюда и “Light” в названии).

В качестве функции \text{ReadOut} используется усреднение:

{e}_u = \frac{1}{L+1} \sum\limits_{k=0}^L {e}_u^k, \ \ \ \ \ \ \ \ \ \  {e}_i = \frac{1}{L+1} \sum\limits_{k=0}^L {e}_i^k, \ \ \forall i \in I, u \in U.

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

\hat{y}_{ui} = {e}_u^T {e}_i.

В качестве функции потерь берется BPR Loss:

L_{\text{BPR}}({E}^0) = - \sum\limits_{u \in U} \sum\limits_{i \in N_u} \sum\limits_{j \notin N_u} \ln \sigma(\hat{y}_{ui} - \hat{y}_{uj}) + \lambda \|{E}^0\|_2^2 \rightarrow \min\limits_{{E}^0},

где {E}^0 — матрица обучаемых эмбеддингов. Негативные примеры j \notin N_u сэмплируются равномерно из множества I \setminus N_u.

Недостатки LightGCN и как их решать

Модель LightGCN имеет несколько недостатков: большое смещение в популярное и медленную сходимость при большом словаре.

Медленная сходимость

Модель обучается на BPR Loss. Продифференцируем по параметрам (эмбеддингам):

\frac{\partial L_{\text{BPR}}}{\partial {E}^0} = \sum\limits_{(u, i, j)} (1 - \sigma (\hat{y}(u, i) - \hat{y}(u, j))) \frac{\partial (\hat{y}(u, i) - \hat{y}(u, j))}{\partial {E}^0},

и рассмотрим множитель:

\Delta_{uij} := 1 - \sigma(\hat{y}(u, i) - \hat{y}(u, j)).

Распределение популярности товаров имеет тяжелые хвосты. Поэтому при равномерном сэмплинге негативных товаров намного более вероятно, что для положительного товара i в качестве негативного будет взят такой негатив j, что разность \hat{y}_{ui} - \hat{y}_{uj} будет велика и, как следствие, величина \Delta_{uij} будет близка к нулю. Это приводит к затуханию градиентов и медленной сходимости.

Смещение в популярное

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

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

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

И что прикажете делать?

Решение первой проблемы напрашивается само собой из постановки — нужно менять метод сэмплирования негативов. Будем сэмплировать негативы пропорционально корню n-ой степени из их популярности:

\mathbb{P}\{\text{sample item } j \text{ as negative} \} \sim \sqrt[n]{|\{u \in U: (u, j) \in G\}|}.

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

Негативное сэмплирование на основе популярности
Негативное сэмплирование на основе популярности

Чтобы совсем уйти от смещения в популярное, нужно немного изменить функцию \text{Agg}, чтобы эмбеддинги популярных товаров вносили меньший вклад. В методе r-AdjNormпредлагается поменять нормировочный коэффициент:

{e}_u^{(k)} = \sum\limits_{i \in N_u} \frac{1}{|N_u|^r |N_i|^{1-r}} {e}_i^{(k-1)},  \\ {e}_i^{(k)} = \sum\limits_{u \in N_i} \frac{1}{|N_i|^r |N_u|^{1-r}} {e}_u^{(k-1)}.

При r=0.5 получим исходный метод LightGCN, но варьируя r > 0 можно дополнительно уменьшать коэффициент при эмбеддингах популярных товаров.

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

Пример выдачи для пользователя-мужчины
Пример выдачи для пользователя-мужчины
Пример выдачи для пользователя-женщины
Пример выдачи для пользователя-женщины

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

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

Переход к item-item графу

Отказаться от обучения эмбеддингов пользователей можно, если от user-item графа (рассмотрели ранее) перейти к item-item графу. Но как же построить этот item-item граф, если на момент начала обучения у нас нет информации, какие из товаров похожи, а какие — нет?

Посмотрим внимательнее на функцию \text{Agg}:

{e}_u^{(k)} = \sum\limits_{i \in N_u} \frac{1}{|N_u|^r |N_i|^{1-r}} {e}_i^{(k-1)},  \\ {e}_i^{(k)} = \sum\limits_{u \in N_i} \frac{1}{|N_i|^r |N_u|^{1-r}} {e}_u^{(k-1)}.

Эмбеддинг товара на k-ом слое зависит только от эмбеддингов пользователей на (k-1)-ом слое, которые в свою очередь зависят только от эмбеддингов товаров на (k-2)-ом слое. Подставим одно в другое:

{e}_i^{(k)} = \sum\limits_{u \in N_i} \frac{1}{|N_i|^r |N_u|^{1-r}} {e}_u^{(k-1)} = \sum\limits_{u \in N_i} \frac{1}{|N_i|^r |N_u|^{1-r}} \left( \sum\limits_{i \in N_u} \frac{1}{|N_u|^r |N_i|^{1-r}} {e}_i^{(k-2)} \right).

Получим выражение, которое описывает обновление эмбеддингов товаров, минуя эмбеддинги пользователей. Такая функция \text{Agg} соответствует item-item графу, в котором товары соединены ребром, если существует хотя бы один пользователь, который взаимодействовал с обоими товарами, а вес ребра — число таких пользователей. Легко записать матрицу смежности такого графа. Если R \in \mathbb{R}^{M \times N} — матрица взаимодействий пользователей с товарами, то матрица смежности item-item графа будет R^TR \in \mathbb{R}^{N \times N}.

Тем не менее, такой подход дает граф, в котором много «шумных» ребер: даже если всего один пользователь купил товары вместе, то они будут соединены ребром. Предлагается проводить ребро только между теми товарами, которые были куплены вместе не менее чем Cпользователями. Уже при C \geqslant 3граф получается довольно осмысленным.

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

А теперь применим описанное выше в реальном бою: обучим LightGCN и её модифицированную версию на датасете Movielens-25m. Основные параметры работы с ним:

  • объем данных: 25 млн оценок по 5-балльной шкале от 162 тыс. пользователей для 37 тыс. фильмов;

  • положительные взаимодействия = пользователь поставил оценку фильму не меньше 3.5;

  • бейзлайн = подход «рекомендовать популярное» (ТОП в таблице);

  • для оценки смещения в популярное в качестве топа возьмем 200 самых популярных фильмов (99.45 процентиль по числу взаимодействий).

Открыть в Colab:

Замерять будем следующие метрики:

  • HitRate@K

\text{HitRate}@K = \frac{1}{|U|}\sum\limits_{u \in |U|} \mathbb{I}\{|\text{Rec}_u \cap \text{GT}_u| > 0\}

Величина HitRate@K — доля пользователей, для которых верно предсказали хотя бы одно взаимодействие.

  • Recall@K

\text{Recall}@K = \frac{1}{|U|} \sum\limits_{u \in U} \frac{|\text{Rec}_u \cap \text{GT}_u|}{|\text{Rec}_u \cap \text{GT}_u| + |(I \setminus \text{Rec}_u) \cap \text{GT}_u|}

Величина Recall@K интерпретируется как доля релевантных объектов, попавших в рекомендации.

  • NDCG@K

\text{DCG}_u@K = \sum\limits_{i=1}^{\min (K, |\text{Rec}_u|)} \frac{\mathbb{I}\{\text{Rec}_{ui} = \text{GT}_{ui}\}}{\log_2 (i+1)}, \\ \text{IDCG}_u@K = \sum\limits_{i=1}^{\min(K, |\text{GT}_u|)} \frac{1}{\log_2(i+1)}, \\ \text{NDCG}@K = \frac{1}{|U|} \sum\limits_{u \in U} \frac{\text{DCG}_u@K}{\text{IDCG}_u@K}
  • AIRTS

\text{AIRTS}@K = \frac{1}{|U|} \sum\limits_{u \in U} \frac{|\text{Rec}_u \cap Top|}{|\text{Rec}_u|}

Величина AIRTS — средняя доля топа в рекомендациях.

  • IntraListDiversity@K

\text{IntraListDiversity} = \frac{1}{|U|} \sum\limits_{u \in U} \left| \{\text{Subj}(i): i \in \text{Rec}_u\} \right|,

где \text{Subj}(i) — категория (жанр в случае фильмов), которой принадлежит объект i. Эта метрика показывает среднее число категорий (жанров), к которым относятся объекты, рекомендуемые пользователям.

  • AggregatedDiversity@K

\text{AggregatedDiversity} = \left|\bigcup\limits_{u \in U} \text{Rec}_u \right|

Величина Aggregated Diversity показывает количество уникальных объектов, порекомендованных всем пользователям.

Метрики с учетом взаимодействий пользователей с ТОП-ом:

Model

HitRate@50

Recall@50

NDCG@50

AIRTS

IntrLstDvrst@50

AggDiversity@50

Top

0.63

0.09

0.06

1.00

6.0

50

LightGCN

0.69

0.12

0.09

0.99

8.0

150

r-AdjNorm + pop sampling

0.67

0.12

0.07

0.46

7.9

27038

Однако топ продаж — очень коварная вещь с точки зрения метрик. Действительно, по самому своему определению топ продаж — это товары, с которыми взаимодействуют больше всего. Как следствие, подход “рекомендовать популярное” получает очень хорошие метрики (см. “Top” в таблице выше). При этом такая выдача однообразна и не учитывает индвидуальных предпочтений пользователей. Чтобы убедиться, что модель не “завышает” метрики путём смещения в популярное, удалим из тестовой части выборки взаимодействия с топом и замерим метрики на полученном тесте. Получим следующий результат:

Model

HitRate@50

Recall@50

NDCG@50

AIRTS

IntrLstDvrst@50

AggDiversity@50

Top

0

0

0

1.00

6.0

50

LightGCN

0

0

0

0.99

8.0

150

r-AdjNorm + pop sampling

0.4

0.07

0.04

0.46

7.9

27038

Видим, что если не учитывать ТОП, то классификационные и ранжирующие метрики LightGCN обнуляются. Это значит, что модель могла правильно предсказывать только ТОП. И зачем нам такая модель, если можно сразу рекомендовать популярное…

Модифицированный подход r-AdjNorm + pop sampling показал почти такие же метрики, если учитывать ТОП. При этом из второй таблицы видно, что такая модель способна правильно предсказывать не только топ, но и хвост распределения.

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

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


Эта и другие статьи про рекомендации в Wildberries выходят в Telegram-канале @wildrecsys. Подписывайтесь, чтобы не пропустить новые публикации!

А больше о том, как при помощи ML мы делаем маркетплейс лучше для продавцов и покупателей, рассказываем в Telegram-канале @wb_space. Там же делимся анонсами и полезным материалами от экспертов.


Источники

  1. LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation [link]

  2. Investigating Accuracy-Novelty Performance for Graph-based Collaborative Filtering [link]

  3. Inductive Representation Learning on Large Graphs [link]

  4. On the Effectiveness of Sampled Softmax Loss for Item Recommendation [link]

Комментарии (0)