Мотивация

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

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

Концепция

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

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

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

• Рёбра — линии, соединяющие вершины, показывающие отношения или связи между вершинами. Как правило это признак дружбы, подписки, покупки, лайка или любого другого взаимодействия.

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

Примеры:

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

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

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

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

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

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

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

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

Линейная алгебра

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

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

Матричная факторизация

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

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

Cross-Domain рекомендации

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

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

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

Длинные хвосты

Одной из задач в рекомендательных системах является оптимизация рекомендаций для "длинного хвоста" (long tail) — редких и менее популярных товаров или контента.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• , если предыдущий шаг был возвращением назад, что уменьшает вероятность повторного возвращения.

• , если следующий узел — непосредственный сосед текущего узла, что обеспечивает стандартное случайное блуждание.

• , если следующий узел находится дальше по графу, что увеличивает вероятность исследовать дальние узлы.

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

Обучение

Лосс функция

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

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

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

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

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

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

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

Negative Sampling

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

• + Чем выше значение k, тем более робастной становится оценка.

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

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

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

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

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

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

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

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

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

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

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

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

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

• https://arxiv.org/pdf/1607.00653.pdf

• https://www.youtube.com/watch?v=pS_POUVFXvk

• https://www.youtube.com/watch?v=dPNWMFUGgnI