Node2Vec + Random Walk Graph RecSys

Graph RecSys

Мотивация

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

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

Концепция

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

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

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

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

Примеры:

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

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

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

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

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

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

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

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

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

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

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

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

И в рамках случайного блуждания у нас есть два параметра 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

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

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

Сначала мы суммируем по каждой вершине 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. Если две вершины не должны быть связаны, мы хотим, чтобы модель видела это как маловероятное. Мы снова берем скалярное произведение векторов признаков, но на этот раз для вершины и случайно выбранной вершины, которая, как мы предполагаем, с ней не связана. Мы хотим, чтобы сигмоида этого произведения была маленьким числом, поэтому когда мы берем логарифм, он становится отрицательным. Этот отрицательный вклад уменьшает общую функцию потерь.

Code

Project Tree

├── .venv/                          # Виртуальное окружение Python
├── dataset/                        # Папка с данными
│   └── ml-100k/                    # Датасет MovieLens 100k
│       ├── allbut.pl
│       ├── mku.sh
│       ├── README
│       ├── u.data                  # Основной файл с данными
│       ├── u.genre
│       ├── u.info
│       ├── u.item
│       ├── u.occupation
│       ├── u.user
│       ├── u1.base
│       ├── u1.test
│       ├── u2.base
│       ├── u2.test
│       ├── u3.base
│       ├── u3.test
│       ├── u4.base
│       ├── u4.test
│       ├── u5.base
│       ├── u5.test
│       ├── ua.base
│       ├── ua.test
│       ├── ub.base
│       └── ub.test
├── node2vec_model.emb              # Файл с эмбеддингами, полученными с помощью Node2Vec
└── node2vec_script.py              # Python-скрипт для выполнения Node2Vec

node2vec_script.py

import pandas as pd
import networkx as nx
from node2vec import Node2Vec
from gensim.models import KeyedVectors
import os

# Загрузка данных и создание графа
def load_graph(file_path):
    data = pd.read_csv(file_path, sep='\t', names=['user_id', 'item_id', 'rating', 'timestamp'])
    G = nx.Graph()
    for _, row in data.iterrows():
        G.add_edge(row['user_id'], row['item_id'])
    return G, data

# Загрузка информации о фильмах
def load_item_info(file_path):
    item_info = pd.read_csv(file_path, sep='|', encoding='latin-1', header=None, 
                            names=['item_id', 'title', 'release_date', 'video_release_date', 'IMDb_URL', 
                                   'unknown', 'Action', 'Adventure', 'Animation', "Children's", 'Comedy', 
                                   'Crime', 'Documentary', 'Drama', 'Fantasy', 'Film-Noir', 'Horror', 
                                   'Musical', 'Mystery', 'Romance', 'Sci-Fi', 'Thriller', 'War', 'Western'])
    return item_info

# Основная функция для выполнения node2vec
def run_node2vec(file_path, dimensions=64, walk_length=30, num_walks=200, workers=4):
    G, data = load_graph(file_path)
    
    # Инициализация node2vec
    node2vec = Node2Vec(G, dimensions=dimensions, walk_length=walk_length, num_walks=num_walks, workers=workers)
    
    # Обучение модели
    model = node2vec.fit(window=10, min_count=1, batch_words=4)
    
    return model, data

# Функция для получения топ-10 предсказаний для пользователя
def get_top_10_recommendations(model, user_id, data, item_info):
    user_items = data[data['user_id'] == user_id]['item_id'].tolist()
    recommendations = model.most_similar(user_items, topn=10)
    
    # Получение названий фильмов и жанров
    recommendations_info = [(item_info[item_info['item_id'] == int(item)]['title'].values[0], 
                             item_info[item_info['item_id'] == int(item)].iloc[:, 5:].idxmax(axis=1).values[0]) 
                            for item, _ in recommendations]
    
    # Получение реальных взаимодействий пользователя
    user_interactions = [(item_info[item_info['item_id'] == item]['title'].values[0], 
                          item_info[item_info['item_id'] == item].iloc[:, 5:].idxmax(axis=1).values[0]) 
                         for item in user_items]
    
    return recommendations_info, user_interactions

# Пример использования
if __name__ == "__main__":
    file_path = 'dataset/ml-100k/u.data'  # Укажите путь к вашему файлу данных
    item_info_path = 'dataset/ml-100k/u.item'  # Укажите путь к файлу с информацией о фильмах
    model_path = "node2vec_model.emb"
    
    if os.path.exists(model_path):
        model = KeyedVectors.load_word2vec_format(model_path)
        _, data = load_graph(file_path)
    else:
        model, data = run_node2vec(file_path)
        model.wv.save_word2vec_format(model_path)
    
    item_info = load_item_info(item_info_path)
    
    # Получение топ-10 предсказаний для пользователя
    user_id = 1  # Укажите ID пользователя
    recommendations, user_interactions = get_top_10_recommendations(model, user_id, data, item_info)
    
    print(f"Топ-10 рекомендаций для пользователя {user_id}:")
    for title, genre in recommendations:
        print(f"{title} ({genre})")
    
    print("\nРеальные взаимодействия пользователя:")
    for title, genre in user_interactions[:10]:
        print(f"{title} ({genre})")
        
# OUTPUT:
# Топ-10 рекомендаций для пользователя 1:
# Brazil (1985) (Sci-Fi)
# Get Shorty (1995) (Action)
# Sound of Music, The (1965) (Musical)        
# Unforgiven (1992) (Western)
# This Is Spinal Tap (1984) (Comedy)
# Monty Python's Life of Brian (1979) (Comedy)
# Batman (1989) (Action)
# Heathers (1989) (Comedy)
# Philadelphia (1993) (Drama)
# Citizen Kane (1941) (Drama)

# Реальные взаимодействия пользователя:
# Three Colors: White (1994) (Drama)
# Grand Day Out, A (1992) (Animation)
# Desperado (1995) (Action)
# Glengarry Glen Ross (1992) (Drama)
# Angels and Insects (1995) (Drama)
# Groundhog Day (1993) (Comedy)
# Delicatessen (1991) (Comedy)
# Hunt for Red October, The (1990) (Action)
# Dirty Dancing (1987) (Musical)
# Rock, The (1996) (Action)

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

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

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

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

PreviousMODELS NextMatrix factorization

Last updated 1 year ago

Node2Vec + Random Walk Graph RecSys

Graph RecSys

Мотивация