Графы в рекомендательных системах [часть 1] / forpes.ru

Главная
Графы в рекомендательных системах [часть 1]

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

01.07.2024 16:30

odmin227 3 2900 Источник

Мотивация

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

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

Концепция

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

Составляющие графа:

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

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

Примеры:

Человек-паук и его друзья: Помните мем где три человека-паука? Каждый из человеков пауков указывает на соседнего, но и соседний указывает на него. В таком случае такой граф назывался бы ненаправленным или неориентированный.

За орду или за альянс?

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

Представьте себе, что вы в мире World of Warcraft. Все фанаты Орды скорее всего тусуются вместе, так же как и поклонники Альянса. Это явление не случайно — оно подкрепляется как личными предпочтениями, так и структурными факторами.

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

Но что, если мы посмотрим на противоположное явление? Гетерофилия, или любовь к различному, — это тенденция людей собираться в разнообразные группы. Представьте, что на вечеринке World of Warcraft все фанаты смешиваются и знакомятся с новыми, непохожими на них игроками. Это противоположность гомофилии, и она тоже важна. Гетерофилия помогает создавать разнообразные и инновационные коллективы, особенно на работе. Разные точки зрения и подходы могут приводить к более креативным и эффективным решениям.

И на самом деле графы оперируют этими понятиями. По сути это и есть базовые функции графа мы либо смотрим на объекты рядом в одной группе, либо идешь дальше смотреть на соседнии.

Случайное блуждание

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

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

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

Поиск в ширину и глубину

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

p — параметр возврата, который управляет вероятностью повторного посещения предыдущего узла.
q — параметр, который управляет вероятностью исследовать узлы дальше или ближе к предыдущему узлу.

Поиск в ширину (Breadth-First Search, BFS): Этот метод начинается с исходного узла и исследует всех его непосредственных соседей (на картинке это показано красными линиями). Затем алгоритм переходит к соседям этих узлов и так далее, пока не достигнет нужной глубины или не закончатся узлы. Поиск в ширину полезен для определения структурной эквивалентности узлов, то есть для понимания их места и роли в локальной сетевой структуре.

Поиск в глубину (Depth-First Search, DFS): Все так же начинается с исходного узла и идет как можно глубже по одному пути, прежде чем отступить и следовать другому пути (на картинке это синие линии). Это полезно для выявления общих паттернов связности, таких как принадлежность к определенному сообществу или кластеру внутри графа.

Рассмотрим конкретный кейс

Представим, что блуждание только что перешло от узла t к узлу v и теперь оценивает следующий шаг из узла v. Метки на рёбрах указывают на смещения поиска $\alpha$ . Это означает, что алгоритм использует эти метки для принятия решения о том, в какой узел перейти дальше, основываясь на предыдущем узле t и текущем узле v, чтобы сохранить структурную целостность блуждания, учитывая различные типы связей в графе. $d_{tx}$ представляет собой кратчайшее расстояние между узлами t и x.

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

Конкретные формулы:

$\alpha = \frac{1}{p}$ , если предыдущий шаг был возвращением назад, что уменьшает вероятность повторного возвращения.
$\alpha = 1$ , если следующий узел — непосредственный сосед текущего узла, что обеспечивает стандартное случайное блуждание.
$\alpha = \frac{1}{q}$ , если следующий узел находится дальше по графу, что увеличивает вероятность исследовать дальние узлы.

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

Обучение

Лосс функция

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

$\text{Loss} = \sum\limits_{u\in V} \sum\limits_{v\in N_{R}(u)} - \log{ \frac{exp(z_u^T z_v)}{\sum_{n \in V \exp{(z_u^T z_n)}}}}$

? На первый взгляд формула выглядит сложной, но давайте разберём её по частям!

Сначала представьте, что V — это все вершины в нашем графе. Это как если бы мы взяли все города на карте. N_R(u) — это все соседние вершины для вершины u. Представьте, что это ближайшие города к каждому городу. z_u и z_v — это векторы, представляющие наши города в новом пространстве. Эти векторы помогают нам понять, как города связаны друг с другом.

Теперь давайте посмотрим на скалярное произведение z_u^T z_v . Оно помогает определить, насколько близки наши города в новом пространстве. Если два города имеют схожие соседние города, их скалярное произведение будет большим.

Формула включает сумму по всем вершинам u и их соседям v. Мы складываем значения для каждого города и его ближайших городов. Это помогает нам учитывать все связи в графе.

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

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

Negative Sampling

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

+ Чем выше значение k, тем более робастной становится оценка.
- Однако, чем выше значение k, тем больше смещение в сторону негативных примеров.

на практике k выбирается из диапазона от 5 до 20

Теперь посмотрим на формулу функции потерь:

$\text{Loss} = -\sum_{u \in V} \sum_{v \in N_R(u)} \left( \log \sigma \left( z_u^T z_v \right) - \sum_{n \in \text{sample\_neg}(v)} \log \sigma \left( z_u^T z_n \right) \right)$

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

Сначала мы суммируем по каждой вершине u в графе:

$-\sum_{u \in V}$

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

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

$\sum_{v \in N_R (u)}$

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

Теперь разберем вклад положительных примеров. Для каждой вершины u суммируем по всем соседним вершинам n, являющимся частью случайных блужданий из u:

$\log \sigma \left( z_u^T z_v \right)$

Здесь $\log \sigma \left( z_u^T z_v \right)$ представляет логарифм сигмоиды скалярного произведения векторов признаков вершин u и v. Если две вершины действительно связаны, мы хотим, чтобы модель увидела эту связь как что-то вероятное. Мы используем скалярное произведение их векторов признаков, чтобы измерить, насколько они похожи друг на друга, а затем преобразуем это число в вероятность с помощью функции сигмоида. Логарифм этой вероятности будет положительным вкладом в общую функцию потерь.

Теперь о вкладе отрицательных примеров. Для каждой вершины v суммируем по набору отрицательных примеров:

$-\sum_{n \in \text{sample\_neg}(v)} \log \sigma \left( z_u^T z_n \right)$

В этом случае $\log \sigma \left( z_u^T z_n \right)$ является логарифмом сигмоиды скалярного произведения векторов признаков вершины u и отрицательного примера вершины n. Если две вершины не должны быть связаны, мы хотим, чтобы модель видела это как маловероятное. Мы снова берем скалярное произведение векторов признаков, но на этот раз для вершины и случайно выбранной вершины, которая, как мы предполагаем, с ней не связана. Мы хотим, чтобы сигмоида этого произведения была маленьким числом, поэтому когда мы берем логарифм, он становится отрицательным. Этот отрицательный вклад уменьшает общую функцию потерь.

Дополнительный материал

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

Safreliy
01.07.2024 18:00
#26994074
+1
Спасибо за статью, это очень важный класс рекомендательных систем. Ещё хотелось бы почитать про диффузии на графах, которые относительно неплохо себя показывают и соревнуются с трансформерными моделями по качеству и скорости работы.
1. odmin227 Автор
  01.07.2024 18:00
  #26994196
  +1
  Я как раз про это и писал научную статью, так что надеюсь руки дойдут, ну из планов пока lgcn на днях выйдет и потом третья часть про pinnerformer, pinsage. Из интересных я читал про sheaf gnn, надеюсь им найдут применение в рексисе, а какие диффузии на графах вы знаете, которые я бы мог тоже включить в третью четвертую часть?
  1. Safreliy
    01.07.2024 18:00
    #26994262
    Вообще вот интересный метод: GiffCF - ребята сделали диффузию при помощи уравнения теплопроводности в первом приближении, выглядит интересно. Её менее изощренной предтечей была DiffRec, основанная на обычном добавлении гауссова шума в матрицу, но всё равно интересно поразбираться.
    
    И насчёт вашей научной статьи - было бы круто глянуть)