# Graph-Based Recommendation System

###### Abstract

In this work, we study recommendation systems modelled as contextual multi-
armed bandit (MAB) problems. We propose a graph-based recommendation system
that learns and exploits the geometry of the user space to create meaningful
clusters in the user domain. This reduces the dimensionality of the
recommendation problem while preserving the accuracy of MAB. We then study the
effect of graph sparsity and clusters size on the MAB performance and provide
exhaustive simulation results both in synthetic and in real-case datasets.
Simulation results show improvements with respect to state-of-the-art MAB
algorithms.

Index Terms—  Recommendation system, contextual multi-armed bandit, community
detection.

##  1 Introduction

Recommending products to users have been an essential function of commercial
websites as Amazon and Netflix, etc. [1]. The aim of a recommendation agent is
to propose to a user the product (or item) that will generate a positive
reaction: a product purchase in Amazon, a link click in ads website, etc. This
user response increases the agent payoff, which ultimately needs to be
maximized. The effectiveness of a recommendation system depends on the
knowledge of users’ preference: the deeper the knowledge, the more the
tailored is the recommended item. The challenge is that these preferences
usually are not known a priori and need to be built online by trial and error
for each user. This learning process can be formalised by multi-armed bandit
(MAB) framework[2, 3, 4, 5].

The performance of MAB learning strategies scales with the ambient dimension,
either linearly or as a square root [6], which makes the problem intractable
in scenarios with infinitely large strategy sets, as in recommendation
systems.

To overcome the dimensionality limitation, clustering techniques have been
proposed to properly quantize the context space (e.g., the user space) [7].
Users preference relationships can be encoded in a graph, where adjacent nodes
represents users with similar preferences [8, 9]. This graph can be known
a-priori or it can be inferred based on the past users’ feedbacks (past
payoffs). We are interested in this latter case and in recent works in which
the geometrical and irregular structure of the context have been considered
[9, 10, 11, 12, 13, 14, 15, 16]. In [10], authors proposed CLUB, an online
clustering strategy where $m$ clusters are optimized for $n$ ($>>m$) users,
where only one recommendation per cluster is optimized. In [14], a similar
idea has been implemented on both user and item side to propose COFIBA. In
both CLUB and COFIBA, an iterative graph learning process is considered with a
fully connected graph as starting point. At each recommendation opportunity,
edges are deleted if connecting users with different enough payoff. Any
connected component will then form a cluster. The leads to a very simple and
yet effective MAB problem, but with the limitation of a $i)$ limited
clustering strategy, $ii)$ no possibility of recovering from inaccurate payoff
estimate (edges can only be deleted from the known graph and they cannot be
added in case of edges wrongly deleted in the past), and $iii)$ a number of
clusters rapidly increasing with time, which we show not to be the best trend
for MABs. In contrast, DYnUCB [17] groups users via K-means assigning users
dynamically into clusters. However, it requires an input as a pre-defined
number of clusters. While theoretically $K$ can be optimized with iterative
solutions (e.g., elbow method), in practice, an appropriated cluster number is
typically unknown, hard to guess, and dynamic over time (as users might appear
or disappear).

To overcome these limitations, in this paper we propose SCLUB-CD, a novel
graph-based MAB problem that learns and exploits the geometry of the user
domain in an online fashion. Specifically, at each recommendation opportunity,
a user graph is constructed based on estimated user preference. Then, the
graph is divided into clusters based on the community detection algorithm
[18]. Our main contributions are:

  * •

to adopt graph clustering into MABs to propose a dynamic graph estimation
_and_ clustering.

  * •

to show that MABs are more efficient when the number of cluster remains
limited over time. Therefore, our proposed recommendation system keeps the
number of clusters limited over time, opposite behaviour with respect to CLUB.

  * •

to test the proposed algorithm in both synthetic and realist dataset, showing
improved performance with respect to LinUCB and CLUB state-of-the-art MAB
problems.

##  2 MAB for Recommendations

We now describe the basics on recommendation systems and how these problems,
when tackled as MAB algorithms, can benefit from context clustering.

Let each user $i\in\mathcal{I}$ be identified by its preferences
$\boldsymbol{u}_{i}\in\mathbf{R}^{l}$ , and let the product $k\in\mathcal{K}$
be identified by its own feature vector $\boldsymbol{x}_{k}\in\mathbf{R}^{d}$
(identifying information such as size, colour and price of the product), with
$l,d$ being the dimension of the user and product vector, respectively, and
$|\mathcal{I}|=N$. While $\boldsymbol{x}_{k}$ is known to the agent, the user
preference vectors $\boldsymbol{u}_{i}$ need to be learned on the fly. To this
effect, the agent makes sequential recommendation and observes the outcome
(appreciation of the recommended product). Formally, at each recommendation
opportunity $t=1,2,...,T$, the agent receives a user index
$i_{t}\in\mathcal{I}$ to serve content to, with $i_{t}$ selected uniformly at
random from $\mathcal{I}$. It also receives the set of possible products to
recommend $\mathcal{C}_{t}\subset\mathcal{K}$, with $|\mathcal{C}_{t}|=C$. The
agent then recommends one product out of the available ones to user $i_{t}$
and observe the user’s feedback in the form of instantaneous payoff $a_{t}$.
The payoff is assumed to be a linear function of the product features
$\boldsymbol{x}_{k}$ and user preference vector $\boldsymbol{u}_{i_{t}}$ with
a noise term $\epsilon\sim\mathcal{N}(0,\sigma^{2}_{\epsilon})$. [4]. Namely,

$a_{t}={\boldsymbol{u}_{i_{t}}}^{T}\boldsymbol{x}_{k}+\boldsymbol{\epsilon}_{i_{t}},\
\ \ \ k\in\mathcal{C}_{t}$ (1)

with $a_{t}\in[0,1]$, with $1$ being the highest appreciation and $0$ the
lowest, and $\boldsymbol{\epsilon}_{i_{t}}(\boldsymbol{x})$ being a random
Gaussian noise $\epsilon\sim\mathcal{N}(0,\sigma^{2}_{\epsilon})$.

Note that ${\boldsymbol{u}_{i_{t}}}^{T}\boldsymbol{x}$ is the expected payoff
received from user ${i_{t}}$ for $\boldsymbol{x}$, while $a_{t}$ is the
instantaneous one.

Let us assume that users are clustered in $M$ non overlapping clusters based
on their preferences, with $V_{j}$, $j=1,2,..,M$ being the $j$th cluster, and
$M$ be unknown a priori. Due to the linear payoff scenario, users in the same
clusters will experience similar payoff functions. It follows that rather than
having a preference vector per user, the agent can identify and learn a
preference vector per cluster. Therefore, the agent needs to learn only $M$
preferences vector rather than $N$, with $N\gg M$. This comes at the price of
an approximation in the estimation of the linear payoff, and therefore a
suboptimality in the recommendation. More formally, each user cluster $V_{j}$
has the preference vector $\boldsymbol{u}_{j}^{\text{c}}$ representing the
common parameter vector shared by users within the cluster, leading to an
_estimated_ mean payoff given by
${\boldsymbol{u}^{\text{c}}_{j(i_{t})}}^{T}\boldsymbol{x}_{k}+\boldsymbol{\epsilon}_{j(i_{t})},$
with $k\in\mathcal{C}_{t}$ and $j(i_{t})$ being the cluster index whose user
$i$ belongs to. Note that the actual payoff (per user) is given by (1), while
the agent will estimate the above one per cluster. From here the suboptimality
of the clustering-based recommendations.

The agent aims to minimise the cumulative regret $R_{T}$ over the time horizon
$T$ defined as $R_{T}=\sum^{T}_{t=1}r_{t},$ with $r_{t}$ being the regret at
time $t$, defined as the difference between the payoff incurred by the
algorithm and the optimal payoff. Formally,

$\displaystyle r_{t}$
$\displaystyle=\max_{k\in\mathcal{C}_{t}}\\{{\boldsymbol{u}_{i_{t}}^{T}\boldsymbol{x}}_{k}\\}-{\boldsymbol{u}_{i_{t}}}^{T}\boldsymbol{x}_{t}$
(2)

where, $r_{t}$ is the regret at time $t$. Following the MAB theory, the
cumulative regret is minimized if products are selected as follows

$k_{t}=\underset{k\in\mathcal{C}_{t}}{\arg\max}({\boldsymbol{u}}^{\text{c}}_{j(i_{t})}\boldsymbol{x}_{k})+CB_{j(i_{t})}(\boldsymbol{x}_{k})$
(3)

The quantity $CB_{j(i_{t})}$ is the upper confidence bound of each arm with
respect to cluster ${j(i_{t})}$. Basically, a product is selected if the
expected payoff is high and it is low the uncertainty on this estimated
payoff.

##  3 Graph-Based MAB

We now describe the proposed SCLUB-CD algorithm, depicted in Algorithm 1.

At the recommendation opportunity $t$, the agent estimates an unweighted and
undirected graph $G_{t}=(\mathcal{V},\mathcal{E}_{t},{W}_{t})$, with
$\mathcal{V}$ being the vertex set representing the $N$ users111Without loss
of generality, we assume the number of active users constant over time. with
$|\mathcal{V}|=N$, $\mathcal{E}_{t}$ and $W_{t}$ the edge sets and the
$N\times N$ adjacency matrix estimated at $t$, respectively.

The graph $G_{t}$ is obtained by following a 3 steps iterative method:

STEP 1. First an undirected and _weighted_ graph
$\tilde{G_{t}}=(\mathcal{V},\mathcal{E}_{t},\tilde{W}_{t})$ is estimated.
Given the current knowledge of the system, users preferences are estimated
minimizing the linear least-square estimate of $\boldsymbol{u}$ as

$\hat{\boldsymbol{u}}_{i,t}=M_{i,t}^{-1}\boldsymbol{b}_{i,t},\ \ i=1,2,...,N$
(4)

Then, the graph weights $\tilde{\mathbf{w}}_{t,i,j}$ in $\tilde{G_{t}}$ are
evaluated as the Gaussian RBF-distance between $\hat{\boldsymbol{u}}_{i,t}$
and $\hat{\boldsymbol{u}}_{j,t}$.

STEP 2. Then, the graph is converted in a sparse and unweighted graph.
Sparsity is motivated by the need to tune the dimensionality of the user
space, while the binary weights are introduced mainly to increase the
robustness of the algorithm to graph estimation errors. Both aspects will be
discussed in the results section.

We introduce the hyperparameter $n$, such that the top $n$, $n\ll N$, largest
weights in $w_{t,i,j},j=1,2,...,N$ are encoded as 1, the remaining are 0. The
result graph is $G_{t}$. Note that we do not impose sparsity by setting to
zero all weights below a given threshold value (more common approach) but we
introduce $n$ instead. This is to better control the number of clusters, that
needs to remain low for an efficient learning.

STEP 3. Once the graph $G_{t}$ is estimated, the clusters
$\hat{V}_{1,t}$,$\hat{V}_{2,t}$,…,$\hat{V}_{M,t}$ are derived via community
detection applying the Louvain Method [18]. Preferences per cluster are then
estimated (as shown in Algorithm 1) and the algorithm selects the product
$k_{t}$ at opportunity $t$ following the UCB method, i.e., following the
minimization in (3). Once the product indexed by $k_{t}$ with feature
$\boldsymbol{x}_{k_{t}}$ is recommended, $\boldsymbol{x}_{k_{t}}$ is used to
update $\hat{\boldsymbol{u}}_{i,t}$ along with the received payoff $a_{t}$ via
a standard linear least-square approximation of $\boldsymbol{u}_{i_{t}}$ (as
shown in Algorithm 1) and a new loop starts.

Initial: $b_{i,0}=\mathbf{0}\in\mathbf{R}^{d}$,
$M_{i,0}=\boldsymbol{I}\in\mathbf{R}^{d\times d}$,
$\hat{\boldsymbol{u}}_{i,0}=\mathbf{0}\in\mathbf{R}^{d}$, $i\in[1,N]$;

Input: Edge deletion parameter $n\in(0,N]$;

for  _$t=1,2,...,T$_ do

Set
$\hat{\boldsymbol{u}}_{i,t-1}=M_{i,t-1}^{-1}\boldsymbol{b}_{i,t-1},i=1,2,...,N$;

Find $G_{t-1,weighted}$: Calculate pairwise Gaussian RBF-distance
$\tilde{\mathbf{w}}_{t-1,i,j}$ between $\hat{u}_{t-1,i}$ and
$\hat{u}_{t-1,j}$, $i,j=1,2,...,N$;

Find $G_{t-1}$: Set the largest $n$ values of
$\tilde{\mathbf{w}}_{t-1,i,j},j=1,2,..,N$ as 1; Set the remaining to 0;

Find $\hat{V}_{\hat{j}_{t},t-1}$: Apply Louvain Method on $G_{t}$;

Set
$\bar{M}_{\hat{j}_{t,t-1}}=\boldsymbol{I}+\sum_{i\in\hat{V}_{\hat{j}_{t},t-1}}(M_{i,t-1}-\boldsymbol{I})$
$\bar{\boldsymbol{b}}_{\hat{j}_{t},t-1}=\sum_{i\in\hat{V}_{\hat{j}_{t},t-1}}\boldsymbol{b}_{i,t-1},\bar{\boldsymbol{u}}_{\hat{j}_{t},t-1}=\bar{M}_{\hat{j}_{t},t-1}^{-1}\bar{\boldsymbol{b}}_{\hat{j}_{t},t-1}$
Find $k_{t}=\underset{k\in
1,...,C}{\arg\max}(\bar{\boldsymbol{u}}_{j(i_{t-1})}\boldsymbol{x}_{t,k})+CB_{\hat{j}_{t-1}}(\boldsymbol{x}_{t,k})$
$CB_{\hat{j}_{t-1}}(\boldsymbol{x})=\alpha\sqrt{\boldsymbol{x}^{T}\bar{M}_{\hat{j}_{t},t-1}\boldsymbol{x}\log{(t+1)}}$
Receive $a_{t}\in[0,1]$.

Update:
$M_{i_{t},t}=M_{i_{t},t-1}+\boldsymbol{x}_{t}\boldsymbol{x}_{t}^{T},\boldsymbol{b_{i_{t},t}}=\boldsymbol{b_{i_{t},t-1}}+a_{t}\boldsymbol{x}_{t}$
$M_{i,t}=M_{i,t-1},\ \boldsymbol{b_{i,t}}=\boldsymbol{b_{i,t-1}},i\neq i_{t}$

end for

Algorithm 1 SCLUB-CD Algorithm

##  4 Simulation Results

###  4.1 Simulations Setup

We carried out results both in a synthetic and a realistic dataset. The
synthetic case allows us to simulate a scenario in which we can actually
control the similarity among users, while the realistic dataset has been
implemented to validate our algorithm in real recommendation problems. In the
synthetic case, $N=100$ users are clustered in $M=5$ clusters and
$|\mathcal{K}|=1000$ products are considered. Out of these $1000$ products, at
each trial $t$, a smaller pool $C$ with size $C=25$ is chosen uniformly at
random from $\mathcal{K}$ as candidate for the recommendation222This is a
common assumption in recommendation systems, therefore we apply it in both
synthetic and realistic scenarios.. We set the dimension of both the users and
product features vectors to $l=d=25$. To control the similarity among users
within a cluster, intra-cluster noise $\sigma_{\text{c}}$ is introduced. For
each user $i$ belonging to $V_{j}$, $\boldsymbol{u}_{i}$ is created by
perturbing the $\boldsymbol{u}_{j(i)}^{\text{c}}$ with a white noise term
drawn uniformly at random across from a zero mean normal distrbution with
variance $\sigma_{\text{c}}^{2}$. The lower $\sigma_{\text{c}}^{2}$ the more
compact the clusters. In the following simulation results, we consider both
$\sigma_{\text{c}}$ and $\sigma_{\epsilon}$ to be in the range $[0.25,0.5]$,
where we recall that $\sigma_{\epsilon}$ is the standard deviation of the
payoff.

For the real-world datasets, we consider LastFM, containing tags of artists
and record listened by users, and Delicious, including URLs bookmarked and
tags provided by users, [19]. While LastFM represents a scenario named “few-
hits” where users’ preference are coherent (therefore it is reasonable to
assume that users can be clustered), Delicious represents a “many-hits”
scenario in which users’ preferences are diverse (therefore the clustering is
a strong approximation). Simulation results are averaged over $10$ runs and
provided in the following.

LastFM and Delicious were processed following the same procedure in [12] which
we detail here. First, tags contains in datasets were breakdown into single
words by removing underscore, hyphens and apexes. Second, tags that appear
less than 10 times were removed. Third, all tags related to each specific item
was formed as a TF-IDF vector to represent the item feature. To reduce the
dimension, PCA was applied to TF-IDF vectors and only the top 25 principle
components were retained.

The proposed SCLUB-CD333Available at https://github.com/LASP-
UCL/KaigeYang/tree/graph-based-recommendation-system. is compared with respect
to the state-of-the-art algorithms, namely LinUCB [20], CLUB[10]. In the
synthetic dataset, we provide simulation results also for the SCLUB-CD in the
case in which user clusters is known, but user preference is unknown. We label
this method SCLUB-CD-Correct and it represents a lower bound in terms of
cumulative regret. To study the effect of the weigted and sparse graph, we
provide results also for two other baseline methods (modified version of the
proposed SCLUB-CD): SCLUB-CD-Weight performs the clustering based on
$\hat{G}_{t}$, while SCLUB-CD-Weight-Sparse keeps the top $n$ largest Gaussian
RBF-distance edges but preserving their weights.

###  4.2 Results

(a) $\sigma_{\text{c}}=0.25$, and $\sigma_{\epsilon}=0.25$.

(b) $\sigma_{\text{c}}=0.5$, and $\sigma_{\epsilon}=0.25$.

(c) $\sigma_{\text{c}}=0.25$, and $\sigma_{\epsilon}=0.5$.

(d) $\sigma_{\text{c}}=0.5$, and $\sigma_{\epsilon}=0.5$.

Fig. 1: Cumulative regret for the synthetic dataset.  Fig. 2: Sparsity and
regret

Fig. 1 shows the cumulative regret as a function of the recommendation
opportunities in the case of synthetic dataset and under various combinations
of reward noise and intra-cluster noise. In the long-term, SCLUB-CD
outperforms its competitors consistently over all scenarios, with a
substantial gap (in terms of cumulative regret) for lower intra-cluster noise
($\sigma_{\text{c}}=0.25$), Fig. 1(a) and Fig. 1(c). It is interesting to
observe that also when the intra-cluster noise increases (Fig. 1(b) and Fig.
1(d)), clustering the user space with the proposed approach still leads to a
system improvement. With respect to LinUCB, which does not cluster the users,
the gain is experienced because of the faster learning process: LinUCB learns
$N$ preference vector while SCLUB-CD learns $M$ ones. With respect to CLUB,
the gain is motivated by $i)$ the online learning estimation of the graph at
each time opportunity, $ii)$ the graph-based clustering not limited to
identify connected components, $iii)$ the binary and sparse modelling of the
graph. In Fig. 1(c), LinUCB might outperform SCLUB-CD for time horizon greater
than $50000$. However, we considered simulations with $N=100$, to have a fair
comparison with LinUCB. By increasing the dimensionality of the user space
this potential crossing point is shifted far away in time [21].

Finally, the gap between SCLUB-CD and SCLUB-CD-Correct shows the potential
room for improvement of the proposed algorithm, as discussed at the end of
this session. The comparison with SCLUB-CD-Weight and SCLUB-CD-Weight-Sparse
shows the gain in controlling the sparsity level (and therefore number of
clusters) in the proposed algorithm.

Fig. 2 shows the regret under different level of sparseness. The sparseness is
controlled by the tuneable parameter $n$. The cumulative regrets are shown in
the first subfigure. The second subfigure presents the clustering quality
measured by NMI (Normalised Mutual Information). The the subfigure presents
the corresponding modularity. It is clear that the pattern of regret mimics
that of NMI. The reason is straightforward that better clustering quality
(higher NMI) leads to better performance (lower regret). This result indicates
the importance of constructing the user graph with an appropriate level of
sparseness which leads to high clustering quality and therefore improves
performance.

(a) LastFM

(b) Delicious

(c) LastFM Clustering

(d) Delicious Clustering

Fig. 3: Cumulative regret for the real-world dataset.

Fig. 3 presents results on real world datasets. In LastFM, SCLUB-CD maintains
a leading margin, this is due to a better clustering methodology. In
particular, CLUB tends to indentify many clusters, while SCLUB-CD identifies
$M=3$ user clusters only with $n=300$, as shown in Fig.3(c). This means that
the proposed approach is able to find the right tradeoff between
dimensionality reduction and approximation in clustering users.

In Delicious, SCLUB-CD still outperforms baseline algorithms, but the leading
margin is smaller. Results show it groups users into $M=11$ clusters with
$n=700$. Overall, delicious represents the “many-hits” scenario, in which each
user is interested in a small amount and quite dissimilar websites. This means
that each user will select few website only, therefore the agent can gather a
small amount of feedbacks per user, which translates in a limited training set
per user. Clustering users together allows to increase the dimension of the
training set. Therefore SCLUB-CD outperforms LinUCB and CLUB, however due to
the highly heterogenous scenario the approximation introduced by the
clustering is affecting more the overall system. This justifies the reduced
gain.

##  5 Conclusion

We proposed a graph-based bandit algorithm, which encodes users’ similarity in
preference by an undirected and unweighted graph and groups users into
clusters. The key aspects of the proposed algorithm are that $i)$ it adopts
graph-based clustering to extract meaningful clusters, $ii)$ the unweigted
graph makes the system more robust to weights estimation errors, $iii)$ the
proposed method keeps the number of clusters limited (through $n$), unlike
CLUB that has a number of clusters constantly increasing over time. All these
components lead to an overall gain in terms of cumulative regret with respect
to state-of-the-art algorithms. These results also opened new questions such
as “What is the sensitivity of the MAB algorithm to the cluster size?”, “Could
we adopt graph signal processing to further improve the graph knowledge
(exploiting also the smoothness of the reward function on the user graph)?” As
future works, we will be addressing these open questions.

## References

  * [1] “Amazon,” Https://www.amazon.co.uk/, accessed: 2018-04-15.
  * [2] H. Robbins, “Some aspects of the sequential design of experiments,” _Bulletin of the American Mathematical Society_ , vol. 58, no. 5, pp. 527–536, 1952.
  * [3] X. Chen, Z. Zheng, X. Liu, Z. Huang, and H. Sun, “Personalized qos-aware web service recommendation and visualization,” _IEEE Transactions on Services Computing_ , vol. 6, no. 1, pp. 35–47, 2013.
  * [4] J. Liu, P. Dolan, and E. R. Pedersen, “Personalized news recommendation based on click behavior,” in _Proceedings of the 15th international conference on Intelligent user interfaces_. ACM, 2010, pp. 31–40.
  * [5] H. K. Kim, J. K. Kim, and Y. U. Ryu, “Personalized recommendation over a customer network for ubiquitous shopping,” _IEEE Transactions on Services Computing_ , vol. 2, no. 2, pp. 140–151, 2009.
  * [6] S. Bubeck, N. Cesa-Bianchi _et al._ , “Regret analysis of stochastic and nonstochastic multi-armed bandit problems,” _Foundations and Trends® in Machine Learning_ , vol. 5, no. 1, pp. 1–122, 2012\.
  * [7] A. Slivkins, “Contextual bandits with similarity information.” _Journal of Machine Learning Research_ , vol. 15, no. 1, pp. 2533–2568, 2014.
  * [8] T. T. Nguyen and H. W. Lauw, “Dynamic clustering of contextual multi-armed bandits,” in _Proc. ACM Int. Conf. on Information and Knowledge Management_ , ser. CIKM ’14, 2014.
  * [9] F. Rezaeimehr, P. Moradi, S. Ahmadian, N. N. Qader, and M. Jalili, “Tcars: time-and community-aware recommendation system,” _Future Generation Computer Systems_ , vol. 78, pp. 419–429, 2018.
  * [10] C. Gentile, S. Li, and G. Zappella, “Online clustering of bandits,” _CoRR_ , vol. abs/1401.8257, 2014. [Online]. Available: http://arxiv.org/abs/1401.8257
  * [11] S. Li, C. Gentile, A. Karatzoglou, and G. Zappella, “Data-dependent clustering in exploration-exploitation algorithms,” _arXiv preprint arXiv:1502.03473_ , 2015.
  * [12] N. Cesa-Bianchi, C. Gentile, and G. Zappella, “A gang of bandits,” in _Advances in Neural Information Processing Systems_ , 2013, pp. 737–745.
  * [13] S. Li, C. Gentile, A. Karatzoglou, and G. Zappella, “Online context-dependent clustering in recommendations based on exploration-exploitation algorithms,” _ArXiv_ , vol. abs/1608.03544, 2016.
  * [14] S. Li, A. Karatzoglou, and C. Gentile, “Collaborative filtering bandits,” in _Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval_. ACM, 2016, pp. 539–548.
  * [15] N. Korda, B. Szorenyi, and S. Li, “Distributed clustering of linear bandits in peer to peer networks,” in _ICML_ , 2016.
  * [16] S. Caron, B. Kveton, M. Lelarge, and S. Bhagat, “Leveraging side observations in stochastic bandits,” _ArXiv_ , vol. abs/1210.4839, 2012.
  * [17] T. T. Nguyen and H. W. Lauw, “Dynamic clustering of contextual multi-armed bandits,” in _Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management_. ACM, 2014, pp. 1959–1962.
  * [18] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” _Journal of statistical mechanics: theory and experiment_ , vol. 2008, no. 10, p. P10008, 2008.
  * [19] I. Cantador, P. L. Brusilovsky, and T. Kuflik, _Second workshop on information heterogeneity and fusion in recommender systems (HetRec2011)_. ACM, 2011.
  * [20] L. Li, W. Chu, J. Langford, and R. E. Schapire, “A contextual-bandit approach to personalized news article recommendation,” in _Proceedings of the 19th international conference on World wide web_. ACM, 2010, pp. 661–670.
  * [21] K. Yang and L. Toni, “Graph-based recommendation systems,” _ArXiv_ , vol. submit/2313688, 2018.


$216x^{3}+27y^{3}+216x^{2}+72x-721=0\hskip 56.9055pt(x,y\in\mathbb{N})$

can be put in the following form:

$(6x+2)^{3}+(3y)^{3}=9^{3}$

and hence it can be solved by Fermat’s last theorem, i.e. it has no solution
in $\mathbb{N}$ (and in fact it has no solution even in $\mathbb{Z}$).

  3. 3.

The following Diophantine equation:

$16x^{4}+81y^{4}=z^{4}\hskip 56.9055pt(x,y,z\in\mathbb{Z})$

can be written as:

$(2x)^{4}+(3y)^{4}=z^{4}$

and hence by Fermat’s last theorem we can conclude that it can have only
trivial solutions (i.e. solutions with $xyz=0$). This restriction on the
solutions should reduce the difficulty of searching for solutions
substantially.

  4. 4.

Consider the following system of Diophantine equations:

$y^{3}+3y^{2}-x^{2}+3y-z^{5}+z+1=0\hskip 42.67912pt\textrm{and}\hskip
42.67912ptx^{2}-y^{3}=0\hskip 56.9055pt(x,y,z\in\mathbb{Z})$

If we put the equations of this system in the following forms:

$(y+1)^{3}-x^{2}=z^{5}-z\hskip 42.67912pt\textrm{and}\hskip
42.67912ptx^{2}=y^{3}$

and substitute from the second equation into the first equation then we get:

$(y+1)^{3}-y^{3}=z^{5}-z$

Now, if we remember the rule that “the difference between two consecutive
cubes cannot be divisible by 5” and note that $z^{5}-z$ is divisible by 5 then
we can conclude that this system has no solution.

##  14 Other Recommendations

There are many other recommendations that should be considered when dealing
with Diophantine problems (noting that many of these recommendations usually
depend on the particular type of Diophantine equation/system of concern).
Examples of these recommendations are:

  1. 1.

Recall interesting theorems (such as Wilson’s theorem and Fermat’s little
theorem) possibly as part of modular arithmetic investigation and analysis to
the Diophantine equation. For example, Wilson’s theorem may be useful to
recall and use (within modularity investigation and analysis) when the
Diophantine problem involves factorials.

  2. 2.

Consider special (or limiting or obvious or eccentric or $\ldots$) cases and
instances such as when one (or more) of the variables is 0 or $\pm 1$ or goes
to infinity or becomes negative. Such considerations can give an insight in
the solution (or reduce the possibilities or organize the approach of solution
or give a clue to the solution or $\ldots$).

  3. 3.

Give special attention to the dominating terms in the equation(s) which can
(for instance) impose limits or determine the eventual tendency of the
equation(s).

  4. 4.

Consider reformulating the problem that is at the base of the given
Diophantine equation/system such that a solution can be obtained. For
instance, we may impose certain limits and restrictions on the domain of the
problem which enable us to obtain full solution.

  5. 5.

Consider obtaining partial (or tentative or conditional or $\ldots$) solutions
when full (or certain or unconditional or $\ldots$) solutions could not be
reached. Such “interim” solutions can form a basis for future attempts and
investigations to obtain final solutions.[27] [27] [27] This recommendation
(and the previous one) takes into consideration practical factors and issues.
In brief, we should not give up! Moreover, we should always try to make use of
what we could obtain and achieve (e.g. partial or conditional solution). This
helps to maintain confidence and high spirit which help us in our future
investigations of Diophantine problems. Such psychological factors are very
important for our success in solving Diophantine problems. In fact,
Diophantine equations is not an easy subject and hence without such confidence
and high spirit our ability to solve these equations will be reduced and
diminished.

##  15 Recommendations for Systems of Equations

Systems of Diophantine equations can be classified into two main categories:
linear (when all the equations of the system are linear) and non-linear (when
some or all of the equations of the system are non-linear). These two
categories will be investigated in the following two subsections. However,
before we go through this investigation we would like to draw the attention to
the following points:

  1. 1.

Many of the (previously discussed) recommendations related to individual
Diophantine equations applies equally or similarly to systems of Diophantine
equations as well (at least by considering the individual equations as part of
the system but not the system itself). In fact, we already indicated
(frequently) such system recommendations (at least within the given examples
for certain recommendations and guidelines).

  2. 2.

We should remind the reader of what we have said before (see $\S$ 1) that is:
there are two main methods for solving systems of Diophantine equations in
number theory. The first is based on using the traditional methods of solving
systems of multivariate equations (as investigated in algebra and linear
algebra for instance) such as by substitution or comparison or use of the
techniques of matrices, and the second is by solving the individual equations
separately (either by the general methods of algebra or by the special methods
and techniques of number theory) and selecting the solutions that satisfy the
system as a whole (i.e. by accepting only the solutions which are common to
all the equations).

###  15.1 Systems of Linear Equations

Systems of linear Diophantine equations can be easily solved by the well known
(and standard) methods of linear algebra where only the integer (or sub-
integer such as positive integer) solutions are accepted. Other methods
(including the methods used for solving systems of non-linear equations) are
also possible to use in general for solving systems of linear equations (as
will be discussed later).

###  15.2 Systems of Non-Linear Equations

Non-linear systems[28] [28] [28] “Non-linear systems” should be more accurate
than “systems of non-linear equations” if we consider systems that consist of
some linear and some non-linear equations (which should be classified as non-
linear systems although some of their equations are linear). of Diophantine
equations can be solved usually by the well known algebraic methods of solving
systems of equations (which are not restricted to Diophantine equations) such
as by substitution, elimination and comparison (see $\S$ 15.2.4) where only
integer (or sub-integer) solutions are accepted. However, it should be noted
that certain methods (which are mostly investigated in linear algebra) are not
applicable in solving non-linear Diophantine systems since these methods are
specific to linear systems. In the following sub-subsections we will
investigate briefly some of the common recommendations and guidelines (as well
as methods and techniques) for solving non-linear systems of Diophantine
equations. However, before that we would like to draw the attention to the
following useful remarks:

  1. 1.

It is recommended to test all the obtained (integer) solutions on the original
system of equations. This is because some of the algebraic manipulations which
are required during the process of solving systems of non-linear equations
(such as raising to powers or multiplication or division by a variable) can
introduce foreign solutions and hence by testing the obtained solutions we
make sure that no foreign solution is introduced during these manipulations.

  2. 2.

Systems of linear equations can be considered as a special type of systems of
non-linear equations and hence they can be solved by the methods of systems of
non-linear equations (when applicable) as well as by the methods and
techniques which are specific to systems of linear equations (such as by the
methods of matrices of linear algebra).

  3. 3.

Unlike systems of linear Diophantine equations, there is no standard (or
systematically applicable) method or technique for solving systems of non-
linear Diophantine equations and hence solving these systems is a mix of art
and science (where the art is required for selecting the main approach or
strategy for solving the system while the science is needed for employing and
applying the technicalities required by the selected approach).[29] [29] [29]
In fact, even solving individual Diophantine equations is mostly a mix of art
and science. Therefore, it is recommended to investigate various potential
methods or strategies before setting off and making the choice of the best (or
even applicable) strategy to use. Investing some time and effort in this
initial investigation can be very rewarding and beneficial and can save
considerable amount of time and effort in trying to solve the system in a
rather random approach and chaotic manner.

####  15.2.1 Initial Sensibility Checks

As indicated in $\S$ 2.6, initial sensibility checks are recommended (and even
required) as the first step in tackling and solving Diophantine systems as
well as in tackling and solving individual Diophantine equations. In many
cases, solving the given system of equations does not need more than these
initial sensibility checks since these checks can reveal that the system
either has no solution (e.g. because one of the equations has no solution due
to parity violation or modularity inconsistency or because some of the
equations require conditions that contradict the conditions required by the
other equations) or because the solution becomes so obvious by these initial
sensibility checks.

For example, initial sensibility checks should reveal that the following
system (where $x,y\in\mathbb{Z}$):

$3xy+x^{2}-5y=33$ | and | $5x^{3}+10xy+11y^{2}=23$ | and | $17x+4xy^{2}=147$ |
---|---|---|---|---|---

has no solution because the second equation has no solution (noting that in
modulo 5 this equation becomes $y^{2}\stackrel{{\scriptstyle 5}}{{=}}3$ which
has no solution since 3 is not a quadratic residue of 5).

On the other hand, initial sensibility checks (or inspection) should reveal
that the following system:

| $7^{x}-8^{y}=48$ | and | $3x^{2}-5y^{3}=12$ | $(x,y\in\mathbb{N}^{0})$ |
---|---|---|---|---|---

has (only) the obvious solution $(x,y)=(2,0)$. This is because according to
the first equation $y$ must be 0 (to avoid parity violation) and hence
$(x,y)=(2,0)$ is the only possible solution to this system.

Also see the examples given in $\S$ 2.6.

####  15.2.2 Graphic Investigation and Reasoning

Some systems can be easily solved by graphic investigation and reasoning
(which may or may not require plotting of actual graphs representing the
equations of the system). For example, the following system of Diophantine
equations:

| $x^{2}-2x+4+y=0$ | and | $x^{2}+y^{2}+6x-10y+30=0$ | ($x,y\in\mathbb{Z}$) |
---|---|---|---|---|---

was solved in $\S$ 3 by graphical reasoning without need for plotting any
graph. Many other systems can be similarly solved either graphically (by
plotting actual graphs) or by pure graphical reasoning (without plotting any
graph). So, it is recommended to consider graphic investigation when tackling
Diophantine systems (especially non-linear systems with two variables).

####  15.2.3 Test of Solutions of Known Equation

If the system of Diophantine equations contains an equation whose solution is
known (or can be obtained easily or more easily) then the best approach for
solving the system is to test the solutions of that equation on the other
equations where only the common solutions (if any) to all equations are
accepted. This is based on the obvious fact that the solution of the system is
the intersection of the solutions of the individual equations (see the
paragraph before the last of $\S$ 1) and hence the set of solutions of the
system cannot exceed the set of solutions of any one of the equations in the
system, i.e. the set of solutions of the system is a (proper or improper)
subset of the set of solutions of any one of the equations in the system. This
approach usually saves considerable amount of time and effort in trying to
solve the system by other methods. In fact, in some cases this can be the only
viable method for solving the system.

For example, the following system of Diophantine equations (where
$x,y\in\mathbb{Z}$):
$15x+13xy-20y=0$ and $3x^{4}+2y^{3}+202=0$ and $7x^{5}-4y^{2}-9x^{3}y=484$
can be easily solved by testing the solutions of the first equation (assuming
we have these solutions or they can be obtained rather easily) which are:
$(x,y)=(2,-5)$, $(0,0)$, $(-10,-1)$
on the other equations in the system. By doing so we find out that only the
solution $(x,y)=(2,-5)$ satisfies all the equations of the system and hence
only this solution is acceptable as a solution to the system.

Similarly, the following system of Diophantine equations:

| $x^{2}-3y=19$ | and | $13y^{3}+6x=11$ | and | $x^{2}+y^{2}=17$ | ($x,y\in\mathbb{Z}$) |
---|---|---|---|---|---|---|---

can be easily solved by solving the last equation whose solutions[30] [30]
[30] The solutions of the last equation are: $(x,y)=(\pm 1,4)$, $(\pm 1,-4)$,
$(\pm 4,1)$ and $(\pm 4,-1)$. can be easily obtained (because there are only a
few possibilities for $x$ and $y$ to satisfy this equation) and testing these
solutions on the other two equations in the system. On doing so we find that
only the solution $(x,y)=(4,-1)$ satisfies the other two equations and hence
this is the only solution to the system.

####  15.2.4 Substitution, Elimination and Comparison

Substitution is one of the most common and straightforward methods for solving
systems of Diophantine equations (whether linear or non-linear). For example,
the following system:

$3x^{2}+4y=19$ | and |  $5x-2y=3$. | ($x,y\in\mathbb{Z}$) |
---|---|---|---|---

can be solved easily by substituting $2y=5x-3$ (which is obtained from the
second equation) into the first equation to get $3x^{2}+10x-25=0$ which is a
univariate quadratic equation in $x$. Solving this quadratic equation (e.g. by
the quadratic formula) will lead to the only solution of the system which is
$(x,y)=(-5,-14)$.

Sometimes this method may require some minor (extra) manipulation prior to
substitution (such as raising to power) to facilitate substitution. For
example, the following system:

| $\sqrt{x}-11y^{2}=8$ | and | $4xy-1033y^{2}=411$ |
---|---|---|---|---

can be solved by substituting $x=(11y^{2}+8)^{2}$ (which is obtained from the
first equation by squaring $\sqrt{x}$) into the second equation to get
$484y^{5}+704y^{3}-1033y^{2}+256y=411$ whose only integer solution is $y=1$
(i.e. $x=19^{2}=361$) and hence the only solution to the given system is
$(x,y)=(361,1)$.

The methods of elimination and comparison are very similar to the method of
substitution (in their technicalities as well as in their wide applicability)
and hence we do not need to investigate them.

##  16 Testing the Final Solutions

It is strongly recommended to test the obtained solutions (whether of
individual equations or of systems of equations) on the given equations and
systems, e.g. by substituting the values of the variables of these solutions
in the given equations and systems. This is particularly important in the
following cases:

$\bullet$ When the solutions are obtained with certain manipulations that can
introduce foreign solutions (see $\S$ 4).

$\bullet$ When the solutions are obtained by messy arguments and formulations
and hence it is likely that the solutions are wrong or they contain errors and
mistakes.

We may also consider using computational tools to do final checks, e.g. by
running a code to obtain the solutions (as we did in $\S$ 5) and compare them
to the already obtained solutions. In fact, we strongly recommend using such
computational tools (like coding or spreadsheets or software packages) to
check the final answer especially when we have some doubt or when the produced
argument (or proof or formulation or $\ldots$) is very messy and susceptible
to errors and mistakes. So, we recommend starting our investigation of
Diophantine problems by computational inspection to probe the solution and
form a general idea about it (see $\S$ 5), and terminating our investigation
by computational testing and checking of the obtained solution.

## References

  * [1] D.F. Mansfield.  Plimpton 322: A Study of Rectangles.  Foundations of Science, 26:977–1005, 2021.  DOI: https://doi.org/10.1007/s10699-021-09806-0.
  * [2] T. Sochi.  Notes and Problems in Number Theory.  Amazon Kindle Direct Publishing, first edition, 2023.  Volume I (ISBN: 9798865134893).
  * [3] T. Sochi.  Notes and Problems in Number Theory.  Amazon Kindle Direct Publishing, first edition, 2024.  Volume II (ISBN: 9798326442802).

## Nomenclature

In the following list, we define the common symbols, notations and
abbreviations which are used in the paper as a quick reference for the reader.

! | factorial
---|---
$\in$ | in (or belong to)
$\ni$ | (backward) in (or belong to)
$|a|$ | absolute value of $a$
Eq., Eqs. | Equation, Equations
LHS, RHS | left hand side, right hand side
$m\stackrel{{\scriptstyle k}}{{=}}n$ |  $m$ and $n$ are congruent modulo $k$
$m\stackrel{{\scriptstyle k}}{{\neq}}n$ |  $m$ and $n$ are not congruent modulo $k$
mod | modulo (or modulus)
$\mathbb{N}$ | the set of natural numbers (i.e. $1,2,3,\ldots$)
$\mathbb{N}^{0}$ | the set of non-negative integers (i.e. $0,1,2,3,\ldots$)
$O_{k}n$ | the order of integer $n$ (modulo $k$)
$p$ | prime number
$\mathbb{P}$ | the set of prime numbers
$\mathbb{Z}$ | the set of integers
$\Delta$ | discriminant of quadratic polynomial