Graph Neural Networks для рекомендаций

2019. Pinterest. 3 миллиарда рёбер. Матричная факторизация видит каждый пин отдельно. Граф видит: этот пин за два шага ведёт к тому пину. PinSage захватил эту структуру - и engagement рекомендаций вырос на 30%. Не за счёт больших данных. За счёт правильной математики: propagation through graph topology.

• Pinterest PinSage: 300M пинов, GraphSAGE с random walk sampling, +30% engagement в продакшне против предыдущей системы
• Alibaba GATNE: multi-relational граф (покупки, просмотры, клики) как отдельные типы рёбер, Graph Attention Networks - +10% CTR на Taobao
• YouTube DNN + граф: user-item взаимодействия смоделированы как граф для co-watch матрицы, два этапа retrieval + ranking
• Microsoft Azure Recommendations: LightGCN в облачном пайплайне для B2B рекомендаций, заменил ALS при меньшей latency

Предварительные знания

• Модели последовательных рекомендаций и эмбеддинги
• Графы и смежность: узлы, рёбра, соседи
• Message passing как повторяющаяся агрегация по соседям

• Последовательные рекомендации

PinSage, NGCF и LightGCN: графы выходят на веб-масштаб

В 2018 году Rex Ying с коллегами из Pinterest и Стэнфорда опубликовал PinSage - первую графовую свёрточную сеть, развёрнутую в веб-масштабе. Она работала на графе из трёх миллиардов узлов с помощью random-walk sampling, поэтому соседство не требовалось держать в памяти, и подняла engagement в продакшне. В 2019 году Xiang Wang с коллегами представил NGCF, явно распространяющий коллаборативный сигнал через двудольный граф «пользователь-товар». В 2020 году Xiangnan He с коллегами показал на примере LightGCN, что преобразования признаков и нелинейности, унаследованные NGCF от обычных GCN, на самом деле вредят точности рекомендаций; их удаление оставило только агрегацию по соседям и дало более простую, сильную и быструю модель, ставшую стандартным baseline.

User-item граф: структура, которую теряет матрица

2019 год. Pinterest. 300 миллионов пинов, 3 миллиарда рёбер в графе. Пользователь сохранил пин "DIY деревянная полка" - и через два шага в графе находится пин "скандинавский интерьер". Матричная факторизация видит два пина как два независимых вектора. Граф видит связь.

Биpartite граф рекомендаций - это двудольный граф $G = (U, V, E)$, где $U$ - пользователи, $V$ - айтемы, $E$ - взаимодействия. Ребро $(u, i) \in E$ означает: пользователь $u$ взаимодействовал с айтемом $i$. Никаких рёбер user-user или item-item - только кросс-связи.

Почему граф лучше матрицы? Матрица $R \in \mathbb{R}^{|U| \times |V|}$ хранит только прямые взаимодействия. Граф позволяет распространять сигнал через многошаговые пути: пользователь A лайкнул айтем X, айтем X лайкнул пользователь B, B лайкнул айтем Y - значит A может понравиться Y. Это называется high-order connectivity, и именно её матричная факторизация теряет.

Нормализация $D^{-1/2} A D^{-1/2}$ критична. Без неё узлы с высокой степенью (популярные айтемы) доминируют агрегацию и гасят сигнал от нишевых пинов. После нормализации вклад каждого соседа масштабируется обратно пропорционально корню его степени.

Реальные масштабы: Pinterest - 300M узлов, 3B рёбер. Матрица 300M x 300M плотностью 0.00001% - за пределами любой RAM. Для хранения используется sparse COO или CSR формат. PyTorch Geometric и DGL специализированы именно на таких разреженных графах.

LightGCN: GCN без лишней математики

He et al., 2020. Оригинальный NGCF добавил в GNN трансформации признаков и нелинейности - по аналогии с классическими GCN. Авторы LightGCN задались вопросом: а зачем? Эксперимент показал: убери трансформации - станет лучше. Убери нелинейности - станет ещё лучше. Остался чистый message passing на биpartite графе.

LightGCN - это итеративная агрегация соседей без весовых матриц и без активаций. На каждом слое $k$: $e_u^{(k)} = \sum_{i \in N_u} \frac{1}{\sqrt{|N_u||N_i|}} e_i^{(k-1)}$ для пользователей и симметрично для айтемов. Финальный эмбеддинг - взвешенная сумма по всем слоям: $e_u = \sum_{k=0}^{K} \alpha_k e_u^{(k)}$.

Слой $k=0$: только собственный эмбеддинг (id embedding). Слой $k=1$: среднее соседей первого порядка (айтемы, с которыми взаимодействовал). Слой $k=2$: пользователи, которые взаимодействовали с теми же айтемами - похожие пользователи. Слой $k=3$: айтемы похожих пользователей - классический item-item CF через 3 шага графа.

На Amazon-Book: LightGCN Recall@20 = 0.0411 vs NGCF = 0.0344 (+19%). На Yelp2018: LightGCN = 0.0649 vs NGCF = 0.0579 (+12%). Все gains достигнуты удалением компонентов. Урок для практики: прежде чем добавлять сложность - проверь, не мешает ли она.

PinSage: GraphSAGE на 3 миллиардах рёбер

2019. Pinterest. LightGCN работает на полном графе - но что если граф не помещается в память? PinSage (Ying et al., 2018) - это GraphSAGE для индустриального масштаба. Вместо работы с полной матрицей смежности: выборочная агрегация соседей (sampling), чтобы каждый узел обрабатывал фиксированное число соседей. Engagement от рекомендаций вырос на 30% - просто потому что "похожий пин" теперь означает "связан через 2 шага в графе".

Ключевая идея GraphSAGE: выбираем фиксированное число соседей $S$ для каждого узла, агрегируем их признаки, конкатенируем с собственным вектором, применяем линейную трансформацию. PinSage добавляет: importance sampling через random walks - соседи выбираются пропорционально числу посещений за random walk, а не равномерно. Это emphasizes структурно важных соседей.

PinSage vs LightGCN в продакшне: LightGCN требует полную нормализованную матрицу смежности в памяти - невозможно для Pinterest. PinSage сэмплирует соседей на лету через random walks по Kafka-стриму взаимодействий. Каждый пин имеет multi-modal признаки: изображение (ResNet-50, 2048 dim), текст (word2vec, 256 dim), метаданные. GraphSAGE агрегирует эти rich features - LightGCN работает только с ID-эмбеддингами.

Curriculum training в PinSage: сначала лёгкие negative примеры (случайные пины), потом hard negatives (пины из топ-1000 по косинусному сходству, но без взаимодействия). Без этой стратегии модель учится различать заведомо разные пины и плохо работает на похожих.

Inference на Pinterest: ежесуточный batch-пересчёт всех 300M pin эмбеддингов на MapReduce кластере. Новые пины добавляются через inductive inference - модель видела только признаки, а не ID - значит может выдать эмбеддинг пина без переобучения. Это принципиальное преимущество PinSage над трансдуктивным LightGCN.

Ключевые идеи

• **Биpartite граф** $G=(U,V,E)$ кодирует user-item взаимодействия. High-order connectivity через $k$ шагов - то, что матричная факторизация теряет. Нормализация $D^{-1/2}AD^{-1/2}$ выравнивает вклад популярных и нишевых узлов.
• **LightGCN** (2020): pure message passing без весовых матриц и нелинейностей. Финальный эмбеддинг = среднее по K слоям. Превосходит NGCF на +12-19% при меньшем числе параметров. Применим когда граф помещается в память.
• **PinSage** (2018): GraphSAGE для промышленного масштаба. Importance sampling через random walks, multi-modal признаки (изображение + текст), curriculum training с hard negatives. Индуктивный - новые пины без переобучения.
• **Трансдуктивный vs индуктивный**: LightGCN работает с ID-эмбеддингами (нужен весь граф), PinSage с признаками (можно инференсить новые узлы). Выбор определяется production constraints, а не только качеством.

Связанные темы

GNN-рекомендации объединяют теорию графов, глубокое обучение и задачи ранжирования:

• Graph Neural Networks — LightGCN и PinSage реализуют GCN и GraphSAGE из общей теории GNN для биpartite графов
• Коллаборативная фильтрация — GNN-подход развивает CF: user-item матрица становится графом, MF заменяется graph propagation
• Neural Collaborative Filtering — NCF и Two-Tower - трансдуктивные предшественники; GNN добавляет structural signal поверх ID-эмбеддингов
• Метрики оценки моделей — Recall@K, NDCG@K, MRR - стандартные метрики для сравнения LightGCN и PinSage на бенчмарках

Вопросы для размышления

• LightGCN усредняет эмбеддинги всех K слоёв с равными весами (alpha_k = 1/(K+1)). Что если взаимодействия пользователя неравномерны - есть несколько очень популярных айтемов и много нишевых? Как это повлияет на финальный эмбеддинг и что можно сделать?
• PinSage использует inductive inference через признаки пина (изображение + текст). Но для пользователей в Pinterest нет аналогичных multi-modal признаков - только история взаимодействий. Как обработать нового пользователя без истории?
• LightGCN работает только с binary взаимодействиями (лайкнул/не лайкнул). Как расширить модель для учёта implicit feedback разной силы: просмотр, клик, покупка, повторная покупка?

Связанные уроки

• rec-01 — GNN строятся поверх user-item эмбеддингов коллаборативной фильтрации
• rec-04 — Neural CF и Two-Tower - предшественники GNN-рекомендаций
• dl-08 — LightGCN и PinSage используют те же GNN-примитивы, что и граф для молекул или соцсетей
• rec-05 — GNN - альтернатива к sequential-моделям: структура графа вместо временного порядка
• ml-05-evaluation — NDCG@K и Recall@K - стандартные метрики для оценки GNN-рекомендаций
• ml-01