# ReGAiN : Recommendation with Gaph Adversarial Nets

This project designed and implemeted an noval recommendation algorithm in social networks by combining the advantage of [**Graph Convolutional Networks (GCN)**](https://github.com/tkipf/gcn)) combined wth [**Generative Adversarial Network (GAN)**](https://en.wikipedia.org/wiki/Generative_adversarial_network).

The input to [ReGAiN](https://github.com/DongQing1996/ReGAiN) is a user-user graph, whose node attributes are information of interest to the user. The outputs of [ReGAiN](https://github.com/DongQing1996/ReGAiN) are newly generated node attributes as the recommendation. We compare our method with [four](#41-Experimental-Setup0) commonly used social recommendation techniques. The [experiements](#4-Experiments) show our methods achieves remarkable recommendation quality.

This projest is implemented by [Peng Dai](https://github.com/DesPeradoGoden), [Qing Dong](https://github.com/DongQing1996), [Diyi Hu](https://github.com/suesie), [Hanqing Zeng](https://github.com/ZimpleX) (equal contribution). The implementation can be found in [Github](https://github.com/DongQing1996/ReGAiN).

## 1 Introduction

### 1.1 Social recommendation

With the development of online social networks, personalized social recommendation has become an important approach to help people discover their potential interests. [Content-based (CB) filtering](http://recommender-systems.org/content-based-filtering/) and [Collaborative Filtering (CF)](https://en.wikipedia.org/wiki/Collaborative_filtering) utilize the users’ profile as well as items’ content to improve recommendation and achieved broad success. In the past decades, the complex structure and richcontents of social networks has inspired the exploration of deep learning methods on recommendation. Among them, graph representation learning (e.g., [Graph Convolutional Networks, GCNs](https://github.com/tkipf/gcn)) is one of leading approaches. Aiming at learning low-dimensional vector representations of the graph nodes, graph representation learning facilitates downstream applications such as node clustering and various recommendation.


Meanwhile, [Generative Adversarial Networks (GANs)](https://en.wikipedia.org/wiki/Generative_adversarial_network) also raises people’s attention in recommenda-tion systems (e.g. [IRGAN](https://arxiv.org/abs/1705.10513), [RecGAN](http://www.brianlim.net/wordpress/wp-content/uploads/2018/08/recsys2018-recgan-recommender.pdf)). Combining generative retrieval on predicting relevant items, and the discriminative retrieval on predicting relevancy a [minimax game](https://en.wikipedia.org/wiki/Minimax) is played to improve both of the generator and the discrimator.


Inspired by the success of the GCN and GAN on recommandation system, we propose an approach, **ReGAiN** (Recommendation with Graph Adversarial Nets) unifying the advantage of the two methods. Specifically, the generator utilize the original graph to produce new attributes for nodes (top-$k$ favorite item's attributes, which are used for recommendation in test phase). Then the generated attributes and original attributes are fed into the discriminator which tries to distinguish real and fake features.

<!-- The generator and discriminator are in constant battle throughout the training process. The generator is trained to produce attributes as real as possible to fool the discriminator while the discriminator is trained not to be fooled. After training, the generator is able to produce attributes imitating the original ones. Thus, we can use the generated attributes for recommendation. -->


## 3 Proposed Method: ReGAiN
The model consists two components: the generator and the discriminator. The generator generate new features for each user and the discrimintor try to distinguish real and generated features.

The training of **ReGAiN** requires a graph $G(V,E,U,I)$, where $U$ is the matrix whose each row represents the user' attributes of each node. $I$ is the top-$k$ favorite items' attributes for each user. For inference, the trained deep learning model takes the user's attribute $U$ as input and generate new attributes $I$ for the nodes (i.e. $I_{gen}$) for recommendation. To map the generated attributes to real items, we pick the nearest neighbor in the item attribute embedding space.

### 3.1 Generator


During the training phase, we randomly sampled a subgraph $G_s(V_s, E_s, U_s)$ as the input of generator. We use an encoder / decoder (two GCNs respectively) structure for the generation of $I_{gen}$. Then encoder (GCN₁) allows us to first embed the graph topology and user's attribute to a low-dimensional space (i.e. ***E***). The decoder (GCN₂) allows us to generate features in the items' embedding space with ***E*** and random noises.
### 3.2 Discriminator

For the discriminator, we adapt [differentiable pooling](https://arxiv.org/abs/1806.08804) to hierarchically abstract information from the graph and classify whether the item's attributes are real or fake. Note that the discriminator is not used in the inference pipeline.

## 4 Experiments

### 4.1 Experimental Setup

We implement **ReGAiN** by Tensorflow 1.12.0 and Adam optimizer. We run all experiments on an NVIDIA Tesla P100 GPU (16 GB of HBM2 memory). We evaluate **ReGAiN** on a public online music datasets [LastFM](https://grouplens.org/datasets/hetrec-2011/) which contains social networking, tagging, and music artist listening information.

We compare our method with four commonly used recommendation techniques [BPR](https://arxiv.org/abs/1205.2618), [PNMF](https://link.springer.com/chapter/10.1007/11499145_35), [RankSGD](https://dl.acm.org/citation.cfm?id=2365972), [SBPR](https://dl.acm.org/citation.cfm?id=2661998). We use [librec](https://www.librec.net/) (https://www.librec.net/) to measure the performance of baseline algorithm. We predict top-$10$ items for each user and evaluate the recommendation quality.

<!-- ### 4.2 Evaluation on Graph Embedding Quality

We implement a 2-layer GCN model to embed the LastFM graph. For evaluating the embedding
quality, we cast the problem into a supervised learning setting, by adding an additional node label
(representing the category of the favorite restaurant) to each of the Yelp graph node.

Figure 1 shows the comparison of the graph embedding quality among three GCN variants:ReGAiN
(blue curve), GraphSAGE [ 1 ] (red curve) and spectral GCN [ 4 ] (green curve). For all three models,
we use mean aggregator for forward propagation of the graph convolutional layers. The hidden
layer dimensions are set to 256. We observe thatReGAiNachieves highest accuracy (F1-micro) in
shortest training time. This demonstrates that the discriminator ofReGAiNcan capture accurate
low-dimensional representation of the high-dimensional input graph. Thus, we can further experiment
on the performance of the overall GAN architecture.

4.3 Evaluation on Recommendation Quality

This part is to be completed in the next two weeks. -->

### 4.2 Evaluation On Recommendation Quality

We randomly sample a subgraph $G_e(V_e, E_e, U_e)$ as input to Generator. And we conduct [KNN](https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm) on the output feature of Generator, to generate a ranked list of 10 music artists as recommendation for each user $V_e$, respectively. To evaluate the recommendation quality of ReGAiN, we use four commonly used evaluation metrics including [NDCG](https://en.wikipedia.org/wiki/Discounted_cumulative_gain) (Normalized Discounted Cumulative Gain), [AP](https://en.wikipedia.org/wiki/Evaluation_measures_(information_retrieval)#Mean_average_precision) (Average Precision), [Precision](https://en.wikipedia.org/wiki/Precision_and_recall), and [Recall](https://en.wikipedia.org/wiki/Precision_and_recall).

#### Training Curve

| | |
| -------- | -------- |
|  | 
|
| | |
|| |


The training curve of ReGAiN is shown above. The generator and the discriminator alternatively battle against each other to eventually reach equilibrium.

After hyper-parameter tuning, the architecture of ReGAiN is as follows:

* **Generator**:
* Encoding GCN1: 2 graph convolutional layers of dimension 256
* Decoding GCN2: 2 graph convolutional layers of dimension 256
* **Discriminator** (3 differential pooling levels):
* Level 1: 1 graph convolutional layer of dimension 128
* Level 2: 1 graph convolutional layer of dimension 128
* Level 3: 1 MLP layer of dimension 128

The other hyper-parameters are summarized as follows:

* Optimizer: RMSPropOptimizer
* Learning rate: 0.001
* Dimension of the added noise: 100
* Dropout rate: 0.0

#### Recommendation Evalation

The experiments show that ReGAiN achieves remarkable recommendation quality in terms of these four commonly used metircs. The performance is only slightly inferior to RNMF but significantly better than other three algorithms.
This shows that the graph embedding step of ReGAiN captures the link information of the social network to achieve better recommendation quality.

## 5. Future work
* We will test our model in various dataset including [Yelp](https://www.yelp.com/dataset), [Delicious Bookmarks](https://grouplens.org/datasets/hetrec-2011/), and [Gowalla](https://dawenl.github.io/data/gowalla_pro.zip). These datasets demonstrate various network connection characteristics and correspond to various recommendation tasks (e.g., restaurant recommendation, hotel recommendation). Thus, ReGAiN may need to integrate other model design techniques to achieve good performance on them.

* We will tune the model to achieve better recommendation quality. For larger graphs, we may need to perform sampling on the social network so that the training can proceed in the minibatch fashion.