Recomendational System using Graph Neural Networks with Pytorch Geometric for DSKReG implementation

Creators

Ilia Mistiurin, i.mistiurin@innopolis.university

Mintimer Karimov, m.karimov@innopolis.university

Arthur Gubaidullin, a.gubaidullin@innopolis.university

(Duplication for easy finding the notebook) You can see our code in this jupyter notebook

Table of Contents

• Introduction
• What is DSKReG
• Dataset Exploration
• Dataset Preparation
  • Initial Graph and Feature Preprocessing
  • PyG Dataset Construction
• DSKReG Model
  • Differentiable Sampling
  • Preference Aware Aggregation
  • Creating Loss
  • Model Training
• Results

Introduction

Recomendation Systems or RecSys play a crucial role in our world - mostly each digital product uses it in some way. You defenetly had experiance of interacting with RecSys: your moives and snacks recomendation generated by RecSys. chances are you’ve experienced both its successes and failures. For example, a recommendation engine might suggest a genre of movies you dislike (e.g., horror films, when you only watch sci-fi). Therefore, creation of great RecSys become an essential step for businesses in today’s digital world.

RecSys algorithms (or models) have both: advanteges and disadvantages. With Graph Neural Networks (GNNs) emerged a powerful approach to recommendation systems, with capability of modeling complex relationships and dependencies between users, items, and their attributes. DSKReG (Differentiable Sampling on Knowledge Graph for Recommendation with Relational GNN) is one such advanced method that uses Graph Neural Networks to improve recommendations, and we’ll see how we can implement it using PyTorch Geometric.

You can see our code in this jupyter notebook For a more detailed explanation, you can check out the paper Differentiable Sampling on Knowledge Graph for Recommendation with Relational GNN.

What is DSKReG

DSKReG is an approach to recommendation systems that integrates graph-based models with relational data. It specifically focuses on knowledge graphs (KG), which represent relationships between different entities (such as users, items, and their interactions). The model utilizes Graph Neural Networks (GNNs), which are designed to learn representations of graph-structured data, to process the relationships between entities and generate recommendations.

The main advantage of DSKReG lies in its ability to differentiate sampling within knowledge graphs. By doing so, it can handle complex relationships between users and items, thereby improving the quality of the recommendations.

The authors of the paper highlight two key features of DSKReG:

1. Differentiable Sampling: This means the model can be trained end-to-end, which is not possible with traditional graph-based models that require non-differentiable components.
2. Relational GNN: The model uses a relational version of GNNs, meaning it can take into account various types of relations in the graph, which is crucial for recommendation tasks that involve multiple different types of interactions.

Dataset Exploration

For our demonstration, we’ve chosen the anime dataset, a popular dataset in recommendation system research. This dataset contains information about various anime titles, users who rated them, and their corresponding ratings.

Dataset has following usefull information:

• User-Anime Interaction information: table of user_id, anime_id and rating from 0 to 10 if user rated the anime title or -1 otherwise
• Anime Information: genres and type (Movie, TV)

Dataset Preparation

Import all needed packages and read the dataset:

pip install numpy, torch, torch-geometric, torch-scatter, networkx, matplotlib, jupyter, pandas, scipy

import torch_geometric
import torch

import networkx as nx

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

# Load dataset
anime = pd.read_csv("../data/anime.csv")
rating = pd.read_csv("../data/rating.csv")

Initial Graph and Feature Preprocessing

We will convert the graph to NetworkX graph initially, after this step we will transform graph using "Relational Neighborhood Construction" approach, then to the Pytorch Geometric dataframe.

The NetworkX has quite understandable function naming, therefore we won't explain basic actions with it.

As we discussed earlier, our graph has connections, such as "User-Anime", "Anime-Entity". Let's create this graph:

def get_graph(anime: pd.DataFrame, rating: pd.DataFrame) -> nx.Graph:
    # Get copies of dataframes, so we won't corrupt original ones, clean NaNs
    anime = anime.copy()
    rating = rating.copy()
    anime['genre'] = anime['genre'].str.split(', ')
    anime = anime.drop(columns=['name', 'members'])
    anime = anime.dropna()
    rating = rating.dropna()

    # Data extaction for graph creation
    anime_id = set(anime['anime_id'])
    genre = anime.explode('genre')

    rating = [(f'user_{i}', f'anime_{j}', r) for i, j, r in zip(rating['user_id'], rating['anime_id'], rating['rating']) if j in anime_id]
    genre = [(f'anime_{i}', f'genre_{j}') for i, j in zip(genre['anime_id'], genre['genre'])]
    tp = [(f'anime_{i}', f'type_{j}') for i, j in zip(anime['anime_id'], anime['type'])]

    user_id = list(set(i for i, j, r in rating))
    anime_id = list(set(j for i, j, r in rating))
    genres = list(set(j for i, j in genre))
    types = list(set(j for i, j in tp))

    # Adding data to graph
    G = nx.Graph()

    G.add_nodes_from(user_id, node_type="user")
    G.add_nodes_from(anime_id, node_type="anime")
    G.add_nodes_from(genres, node_type="entity")
    G.add_nodes_from(types, node_type="entity")

    G.add_weighted_edges_from(rating)
    G.add_edges_from(genre)
    G.add_edges_from(tp)

    return G

Now our graph is in following format:

Relational Neighborhood Construction

Graph Convolutions

Graph Convolution is an operation used in Graph Neural Networks (GNNs) to process and analyze graph-structured data. It generalizes the concept of convolution in image processing to graphs. The key idea is to aggregate information from a node’s neighbors and itself to update the node’s representation. Developrt states the depth of convolution: in dense graphs even the depth of 3 might traverse whole graph, wile in spare once it could be needed in order highr, like depth of 10, so it highly dependent of the graph structure.

Idea behind Relational Neighborhood Construction

For exploration and data aggregation on our graph, we need to make at least 3 convolutions:

1. User-Anime
2. Anime-Entity
3. Entity-Anime

(Optionally) It could be assumed to find anime suggestion based on interaction of user with similar 'behavior', but for this we need to make two mode convolutions:

4. Anime-User
5. User-Anime

Let's break these cases. Firstly, Entity nodes store some information and help to connect Anime nodes for prediction of new Anime titles for user. Secondly, we have huge number of connections between User-Anime node categories, so following the 'optional' approach could lead to exploring all nodes in the graph, which is not optimal.

How we could overcome these limitation?

1. Eliminate Entity node type with no information loss
2. Using limited number of neighbours to choose from during convolutions

DSKReG has a way to close the first issue, by interconnecting Anime/Item nodes that share same Entity neighbors. You can see below has this is done:

With one problem solved, we gain new issue: the number of edges increased (for our case it's approximatly in quadratic way), therefore it become harder to process graph. The increase in edges highly depend on the Item-Entity initial relation of second-order neighbors for one entity: we have about 11k Anime nodes with only ~50 Entity nodes, so for our case increase is significant: we got about 40 million edges.

• For simplicity we will cut anime-titles with member's number less than $500000$.
• We use straightforward preprocessing (it could be optimised with saving some data on local drive during computations)

Implementation

Here is our straightforward implementation of Relational Neighborhood Construction

def relational_neighborhood_construction(graph: nx.Graph):
    users = [node for node in graph.nodes if node.startswith("user")]
    anime = [node for node in graph.nodes if node.startswith("anime")]
    types = [node for node in graph.nodes if node.startswith("type")]
    genre = [node for node in graph.nodes if node.startswith("genre")]

    # Map indeces
    mp = {j: i for i, j in mp.items()}
    anime2idx = {j: i for i, j in enumerate(anime)}
    users2idx = {j: len(anime2idx) + i for i, j in enumerate(users)}
    mapping = {mp[int(i[6:])]: j for i, j in anime2idx.items()}


    data = HeteroData()
    data["user"].node_id = torch.tensor(list(users2idx.values()))
    data["anime"].node_id = torch.tensor(list(anime2idx.values()))

    # Adding User-Anime relation
    edges = set()
    for user in users:
        for anm in graph.neighbors(user):
            edges.add((user, anm))
    data["user", "watched", "anime"].edge_index = torch.tensor(
        [(users2idx[i], anime2idx[j]) for i, j in edges]
    ).T

    # Adding Anime-Entity(Genre)
    edges = set()
    for gnr in genre:
        anm = sorted(graph.neighbors(gnr))
        for i in range(len(anm)):
            for j in range(i + 1, len(anm)):
                edges.add((anm[i], anm[j]))

    data["anime", "genre", "anime"].edge_index = torch.tensor(
        [(anime2idx[i], anime2idx[j]) for i, j in edges]
    ).T

    # Adding Anime-Entity(Type)
    edges = set()
    for tp in types:
        anm = sorted(graph.neighbors(tp))
        for i in range(len(anm)):
            for j in range(i + 1, len(anm)):
                edges.add((anm[i], anm[j]))

    data["anime", "type", "anime"].edge_index = torch.tensor(
        [(anime2idx[i], anime2idx[j]) for i, j in edges]
    ).T

    return data, mapping

Now we constructed HeteroData - which is placeholder for heterogeneous graphs with different node types and their relations. The 'data["anime", "genre", "anime"]' created in a way "node type 1" -> "relation" -> "node type 2", for which we could store information about the graph: edge index and any additional data we need to store. 'edge_index' represented in COO format, in another words it is tensor of shape [2, num_edges], representing two arrays, that contain starting and ending nodes in a graph.

Train Test split

def train_test_split(data, test_size=0.2):
    train, test = data.clone(), data.clone()
    users = [i.item() for i in data["user"].node_id]
    shuffle(users)

    idx = int(len(users) * test_size)
    train_idx = {j: i + data["anime"].num_nodes for i, j in enumerate(users[idx:])}
    test_idx = {j: i + data["anime"].num_nodes for i, j in enumerate(users[:idx])}

    train["user"].node_id = torch.tensor([train_idx[i] for i in users[idx:]])
    test["user"].node_id = torch.tensor([test_idx[i] for i in users[:idx]])
    train_edges, test_edges = [], []

    edges = data["user", "watched", "anime"].edge_index.cpu().detach().numpy()
    for i in range(edges.shape[-1]):
        if edges[0][i] in train_idx:
            train_edges.append((train_idx[edges[0][i]], edges[1][i]))
        else:
            test_edges.append((test_idx[edges[0][i]], edges[1][i]))
    train["user", "watched", "anime"].edge_index = torch.tensor(train_edges).T
    test["user", "watched", "anime"].edge_index = torch.tensor(test_edges).T
    return train, test

DSKReG Model

DSKReG model consist of two main parts: Differentiable Sampling and Preference Aware Aggregation. PyG greatly help us. Let's declare our model:

from torch_geometric.nn import SAGEConv
from torch.nn import functional as F


class DSKReG(torch.nn.Module):
    def __init__(self, user_num, anime_num, hidden_channels, hidden_layers=2, dropout=0.5):
        super().__init__()
        self.user_num = user_num
        self.anime_num = anime_num

        self.dropout = nn.Dropout(dropout)

        self.watched = nn.ModuleList(
            [SAGEConv(1, hidden_channels)] + [SAGEConv(hidden_channels, hidden_channels) for _ in
                                              range(hidden_layers - 1)])
        self.genre = nn.ModuleList([SAGEConv(hidden_channels, hidden_channels) for _ in range(hidden_layers)])
        self.tp = nn.ModuleList([SAGEConv(hidden_channels, hidden_channels) for _ in range(hidden_layers)])

        self.user_linear = nn.Linear(hidden_channels, hidden_channels)
        self.anime_linear = nn.Linear(hidden_channels, hidden_channels)

    def cat(self, user, anime):
        return torch.cat((user, anime))

    def uncat(self, nodes):
        return nodes[:-self.anime_num], nodes[-self.anime_num:]

    def forward(self, data):
        user = data['user'].node_id
        anime = data['anime'].node_id

        user = torch.ones_like(user)[:, None].float()
        anime = torch.ones_like(anime)[:, None].float()

        nodes = self.cat(user, anime)
        for watched, genre, tp in zip(self.watched, self.genre, self.tp):
            nodes = self.dropout(nodes)

            nodes = watched(nodes, data['user', 'watched', 'anime'].edge_index)
            nodes = F.relu(nodes)

            user, anime = self.uncat(nodes)

            anime = genre(anime, data['anime', 'genre', 'anime'].edge_index)
            anime = F.relu(anime)

            anime = tp(anime, data['anime', 'type', 'anime'].edge_index)
            anime = F.relu(anime)

            nodes = self.cat(user, anime)

        user, anime = self.uncat(nodes)

        user = self.user_linear(user)
        anime = self.anime_linear(anime)

        user_idx = (torch.ones((data['anime'].num_nodes, 1)).int() * torch.arange(data['user'].num_nodes)).T.reshape(-1)
        anime_idx = (torch.ones((data['user'].num_nodes, 1)).int() * torch.arange(data['anime'].num_nodes)).reshape(-1)

        user = user[user_idx]
        anime = anime[anime_idx]

        return (user * anime).sum(-1)

Creating Loss

We use the dot-product to generate the preference score of user $u$ to item $i$ with the inferred user/item embeddings $\hat{\mathbf{e}}{u}$ and $\hat{\mathbf{e}}{i}$, respectively.

The prediction is calculated as follows: $\hat{y}{ui} = \sigma(\hat{\mathbf{e}}{u}^{\intercal} \hat{\mathbf{e}}_{i}) $

DSKReG uses BPR loss to optimize top-N recommendation, which is defined as follows:

$ \mathcal{L}{bpr} = \sum{(u,l,j) \in \mathcal{D}} -\text{log} \sigma \left( \hat{y}(u,l) - \hat{y}(u,j) \right) + \lambda ||\Theta||^{2}_{2} $

def loss(self, user_emb, pos_item_emb, neg_item_emb, reg_lambda=0.001):
	pos_scores = (user_emb * pos_item_emb).sum(dim=-1)
	neg_scores = (user_emb * neg_item_emb).sum(dim=-1)

	bpr_loss = -torch.log(torch.sigmoid(pos_scores - neg_scores)).mean()
	
	l2_norm = (
		user_emb.norm(2).pow(2)
		+ pos_item_emb.norm(2).pow(2)
		+ neg_item_emb.norm(2).pow(2)
	)

	return bpr_loss + reg_lambda * l2_norm

For loss calculation during training model gets negative examples, witch are items user $u$ has never interacted with.

Model Training

We have quite simple training procidure:

def accuracy(pred, labels):
	pred = torch.where(pred > 0, torch.ones_like(pred), torch.zeros_like(pred))
	return (pred == labels).sum() / len(pred)

model = DSKReG(data["user"].num_nodes, data["anime"].num_nodes, 64, 4)
loss_fn = nn.BCEWithLogitsLoss()
optim = torch.optim.Adam(model.parameters())
best = 1
  
for epoch in range(25):
	print(f"Epoch {epoch + 1}...")
	model.train()
	
	Loss = []
	for _ in range(5):
		input = get_data(train)
		output = all_edges(train)
		out = model(input)
		
		loss = loss_fn(out, output)
		Loss.append(loss.item())
		
		optim.zero_grad()
		loss.backward()
		optim.step()
		
	print(f"Train loss: {sum(Loss) / len(Loss)}")
		
		
	model.eval()
	input = get_data(test)
	output = all_edges(test)
	out = model(input)
	loss = loss_fn(out, output)
	print(f"Test loss: {loss.item()}")
	
	print(accuracy(out, output))

Results

We tried to implement DSKReG approach, but it didn’t worked as we hoped: model approach of Differentiable Sampling turned out quite hard to implement into existing PyG MessagePassing class.

For our used model: our improvised to the issues model learns, but because of Differentiable Sampling non existence (We tried to use similar approach as Graph Sage, since they actually have similar ideas in mind) we faced issue of hard-to-learn model, stopping in some plato.