Alex_TDS 5 июл в 15:16

Графовые сети в рекомендательных системах

10 мин

3.1K

Блог компании WBTECHАлгоритмы*Big Data*Машинное обучение*

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

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

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

Что такое сверточные графовые сети, их основные компоненты и принципы работы: подробно разберем модель на user-item графе, после перейдём к item-item графу;
Знакомство с моделью LightGCN: архитектура, процесс обучения, недостатки (медленная сходимость и смещение в популярное) и варианты их устранения;
А в конце посмотрим, как это всё применять на практике: обучим сетку на датасете Movielens-25m, замерим метрики, столкнёмся с проблемами LightGCN и вместе их решим! Ноутбук прилагается 🤓

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

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

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

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

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

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

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

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

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

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

В качестве функции $\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)}$ есть результат агрегирования эмбеддингов по окрестности вершины при помощи функции $\text{Agg}$ , $\text{CONCAT}({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}$ используют усреднение, взвешенную сумму, где веса представляют из себя выход слоя внимания, или полносвязный слой.

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

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

$\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

Модель 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,$

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

Функция $\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$ — матрица обучаемых эмбеддингов. Негативные примеры $\notin$ сэмплируются равномерно из множества $\setminus$ .

Недостатки 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)).$

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

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

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

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

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

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

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

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

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

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

Чтобы совсем уйти от смещения в популярное, нужно немного изменить функцию $\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)}.$

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

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

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

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

Переход к 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)}.$

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

${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 \geqslant 3$ граф получается довольно осмысленным.

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

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

объем данных: 25 млн оценок по 5-балльной шкале от 162 тыс. пользователей для 37 тыс. фильмов;
положительные взаимодействия = пользователь поставил оценку фильму не меньше 3.5;
бейзлайн = подход «рекомендовать популярное» (ТОП в таблице);
для оценки смещения в популярное в качестве топа возьмем 200 самых популярных фильмов ( процентиль по числу взаимодействий).

Открыть в Colab:

Google Colab

colab.research.google.com

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

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)$ — категория (жанр в случае фильмов), которой принадлежит объект . Эта метрика показывает среднее число категорий (жанров), к которым относятся объекты, рекомендуемые пользователям.

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. Там же делимся анонсами и полезным материалами от экспертов.

Источники

LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation [link]
Investigating Accuracy-Novelty Performance for Graph-based Collaborative Filtering [link]
Inductive Representation Learning on Large Graphs [link]
On the Effectiveness of Sampled Softmax Loss for Item Recommendation [link]

Теги:

Хабы: