# How Graph Convolutions Amplify Popularity Bias for Recommendation?

Jiajia CHEN  Jiancan WU  Jiawei CHEN  Xin XIN  Yong LI  School of Information
Science and Technology, University of Science and Technology of China, Hefei
230026, China  School of Computer Science and Technology, Zhejiang University,
Hangzhou 310058, China  School of Computer Science and Technology, Shandong
University, Qingdao 250100, China  Department of Electronic Engineering,
Tsinghua University, Beijing 100084, China

###### Abstract

Graph convolutional networks (GCNs) have become prevalent in recommender
system (RS) due to their superiority in modeling collaborative patterns.
Although improving the overall accuracy, GCNs unfortunately amplify popularity
bias — tail items are less likely to be recommended. This effect prevents the
GCN-based RS from making precise and fair recommendations, decreasing the
effectiveness of recommender systems in the long run.

In this paper, we investigate how graph convolutions amplify the popularity
bias in RS. Through theoretical analyses, we identify two fundamental factors:
(1) with graph convolution (i.e., neighborhood aggregation), popular items
exert larger influence than tail items on neighbor users, making the users
move towards popular items in the representation space; (2) after multiple
times of graph convolution, popular items would affect more high-order
neighbors and become more influential. The two points make popular items get
closer to almost users and thus being recommended more frequently. To rectify
this, we propose to estimate the amplified effect of popular nodes on each
node’s representation, and intervene the effect after each graph convolution.
Specifically, we adopt clustering to discover highly-influential nodes and
estimate the amplification effect of each node, then remove the effect from
the node embeddings at each graph convolution layer. Our method is simple and
generic — it can be used in the inference stage to correct existing models
rather than training a new model from scratch, and can be applied to various
GCN models. We demonstrate our method on two representative GCN backbones
LightGCN and UltraGCN, verifying its ability in improving the recommendations
of tail items without sacrificing the performance of popular items. Codes are
open-sourced 111https://github.com/MEICRS/DAP.

###### keywords:

Recommendation, Graph Convolution Networks, Popularity Bias

[1]Xiangnan HE received = month dd, yyyy, accepted = month dd, yyyy, corr-
email =<EMAIL_ADDRESS>
##  1 Introduction

Recommender system (RS) has become a key tool for personalization in today’s
Web, and also a research hotpot [1, 2]. Recently, methods based on GCN have
become prevalent in RS since they can effectively encode collaborative
filtering signal [3, 4, 5, 6, 7]. Though GCNs can improve the overall
recommendation accuracy, we find a downside is they amplify the popularity
bias — popular items are more frequently recommended than tail items222We
treat the most 20% popular items in the dataset as popular items, and the rest
are tail items., which means the tail items are not fairly treated by the
algorithm, and the issue would be exacerbated in practical RSs due to the
user-system feedback loop.

Figure 1 provides an evidence that GCNs intensify the popularity bias as the
number of graph convolution layers increases. The backbone model is LightGCN
[6] using BPR loss [8], a representative and competitive GCN-based
recommender. With the increasing of graph convolution layers, the overall
accuracy metric (i.e., Recall@20) gradually increases, but the ratio of
recommending tail items (i.e., TR@20) drops significantly. This means the
improvements of performing graph convolutions is at the expense of tail items,
pointing to the amplified popularity bias issue of GCNs [9]. Although there
has been recent work in alleviating the popularity bias in RS [10, 9, 11],
they do not reveal how GCN amplifies the bias (i.e., the mechanism) and their
solutions are generally applied to RS models rather than tailored for GCNs.

Figure 1: Performance change of LightGCN with different graph convolution
layers on Gowalla. Recall@20 and TR@20 stand for the overall recall score and
the ratio of tail items in the top-20 recommendation list, respectively.

In this work, we aim to answer the unsolved questions ”How do graph
convolutions amplify popularity bias in RS?” and ”How to address the issue
with minimum changes on the training progress?” To reveal the mechanism of
GCNs amplifying the bias, we conduct theoretical studies by analyzing how
popular items influence other nodes. The main findings are twofold: (1) with
graph convolution, popular items have a greater impact than tail items on
neighbor users, making the users position closer to popular items in the
representation space; (2) after multiple times of graph convolution, popular
items become more influential by affecting more high-order neighbor users. The
theoretical analyses confirm the inherent defect of GCNs in over-recommending
popular items.

To alleviate the popularity bias in RS, two lines of research work have been
conducted. The first is intervening the training process to eliminate the bias
effect. For example, propensity-based methods [12] impose lower weights on
popular items in training loss and causal methods [10, 9] model the causal
effect of the bias on the model training. Those methods need to retrain the
backbone model, making the solutions costly to use in practical RSs especially
to correct the already-deployed GCN models. In contrast, another line is
revising the inference stage in a post-hoc way. For example, [13] performs
personalized re-ranking on the generated candidates of the RS model to
suppress popular items. However, both lines work on the general issue of
popularity bias in recommendation, leaving how GCN model suffers from and
amplifies the popularity bias untouched.

Towards the research gap, we propose a new problem to solve — rectifying the
popularity bias of GCN model in the inference stage. Such a solution can be
used to revise already-trained GCNs, thus is easier to deploy in practice than
training a new model. Given a GCN model, we first cluster the node
representations to automatically discover the highly-influential nodes. Then,
the amplification of popularity bias for each node within its cluster is
estimated based on the prior theoretical analyses. Thereafter, the
amplification effect in the node representation can be intervened to control
the bias. This post-hoc method can be easily deployed in practice to correct
existing GCN models and promote the recommendations of tail items without
sacrificing the performance of popular items. To summarize, this work makes
the following contributions:

  * •

Providing in-depth theoretical analyses to interpret the popularity bias
amplification problem in GCN-based recommenders;

  * •

Developing a new method working at each graph convolution layer in the
inference stage to correct the popularity bias for GCN;

  * •

Conducting extensive experiments on three real datasets to demonstrate the
effectiveness of our method on LightGCN and UltraGCN backbones.

##  2 Preliminaries

Table 1: Main notations used in the paper. $\mathcal{U}$, $\mathcal{I}$ | User set, item set
---|---
$\mathcal{N}_{u}$, $\mathcal{N}_{i}$ | The one-order neighbors of user $u$ or item $i$
$d_{u}$, $d_{i}$ | The degree of user $u$ or item $i$
$\mathbf{e}_{u}^{(l)}$, $\mathbf{e}_{i}^{(l)}$ |  The embedding of user $u$ or item $i$ at the $l$-th graph convolution layer
$\mathcal{L}^{ui}$ | The individual loss term of an interaction $(u,i)$
$\mathcal{C}^{(l)}_{p}$ |  A set of nodes in the $p$-th cluster obtained by using Kmeans given the embeddings $\mathbf{E}^{(l)}$
$\mathbb{H}_{v}^{(l)}$ | A set of nodes $\\{j\in\mathcal{C}^{(l)}_{p},d_{j}>d_{v}|v\in\mathcal{C}^{(l)}_{p}\\}$
$\mathbb{L}_{v}^{(l)}$ | A set of nodes $\\{j\in\mathcal{C}^{(l)}_{p},d_{j}<d_{v}|v\in\mathcal{C}^{(l)}_{p}\\}$
$\hat{\boldsymbol{\vartheta}}_{H_{v}}^{(l)}$ |  The pooling representations after normalization of $\mathbb{H}_{v}^{(l)}$
$\hat{\boldsymbol{\vartheta}}_{L_{v}}^{(l)}$ |  The pooling representations after normalization of $\mathbb{L}_{v}^{(l)}$

Suppose that there are a set of users and a set of items
$\mathcal{U}=\\{u_{1},u_{2},\cdots,u_{M}\\}$,
$\mathcal{I}=\\{i_{1},i_{2},\cdots,i_{N}\\}$ in a dataset $D$. Let $y_{ui}=1$
be the positive label if the user $u$ has interacted with the item $i$,
otherwise $y_{ui}=0$. We can construct a user-item bipartite graph
$\mathcal{B}=(\mathcal{V},\mathcal{E})$ based on the interaction history,
where $\mathcal{V}$ consists of the set of user and item nodes, and
$\mathcal{E}$ denotes the set of edges. If $y_{ui}=1$, there is an edge
between the user $u$ and the item $i$.

Recently, many studies opt for powerful GCNs to learn user and item node
representations [14, 15]. Particularly, we introduce LightGCN [6], which is
neat and well represents the GCN-based recommenders. One graph convolution
block of LightGCN can be expressed as:

$\textbf{e}_{u}^{(l)}=\sum\limits_{i\in\mathcal{N}_{u}}\frac{1}{\sqrt{d_{u}}\sqrt{d_{i}}}\textbf{e}_{i}^{(l-1)},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\textbf{e}_{i}^{(l)}=\sum\limits_{u\in\mathcal{N}_{i}}\frac{1}{\sqrt{d_{i}}\sqrt{d_{u}}}\textbf{e}_{u}^{(l-1)},$
(1)

where $d_{u}$ ($d_{i}$) is the degree of user $u$ (item $i$) in the graph
$\mathcal{B}$, $\mathcal{N}_{u}$ ($\mathcal{N}_{i}$) is the one-order neighbor
nodes of the user $u$ (item $i$), $\textbf{e}^{(0)}$ is an ID embedding of a
user or an item. After stacking several graph convolution layers, LightGCN
combines the embeddings obtained at each layer to form the final
representation $\mathbf{e}$ of a node. Thereafter, the model prediction is
defined as the inner product of user and item final representations, i.e.,
$\hat{y}_{ui}=\textbf{e}_{u}^{\top}\textbf{e}_{i}$. Another representative
work is UltraGCN [14] which skips infinite layers of graph convolution. We
also conduct experiments on this model to verify the generality of our method.

To optimize model parameters, prior work usually frames it as a supervised
learning task, and utilize a pointwise or a pairwise loss for model training,
which can be summarized by the following formula: $\mathcal{L}=\sum_{(u,i)\in
D}\mathcal{L}^{ui}$, where $\mathcal{L}^{ui}$ is the individual loss term of
an interaction $(u,i)$. Without loss of generality, we investigate the
popularity bias amplification problem in GCNs based on BCE loss [16] in the
next section. The formal formulation of BCE loss is

$\mathcal{L}^{ui}=-[y_{ui}\ln\sigma(\hat{y}_{ui})+(1-y_{ui})\ln(1-\sigma(\hat{y}_{ui}))].$
(2)

##  3 METHODOLOGY

In this part, we attempt to analyze and resolve the amplified popularity bias
of GCNs.

###  3.1 Popularity Bias Amplification in GCNs

To understand why GCNs amplify the popularity bias, we conduct theoretical
analyses and empirical experiments on GCNs: (1) we start with defining the
influence between nodes based on the training loss; (2) we prove that popular
items with higher degrees exert larger influence on neighbor users than tail
items with lower-degrees; (3) we reveal that popular items commonly have
higher probabilities of being recommended by users after representation
updating and graph convolution in GCNs.

Concisely, we take the $\textbf{e}=\textbf{e}^{(L)}$ at $L$-th graph
convolution layer in Eq. (1) as the final representation of each node. Next,
we give the definition of the influence of a user-item pair loss on their
neighbors exploiting the concept of influence functions [17, 18, 19]:

Definition 1 (Influence of an observed interaction on a node’s representation
learning): Suppose that $(u,i)$ is an observed interaction, i.e., there is an
edge between node $u$ and node $i$, some other node $k$ is reachable from node
$u$ or $i$, then the influence of an interaction $(u,i)$ on node $k$ is
defined as $\frac{\partial\mathcal{L}^{ui}}{\partial\mathbf{e}_{k}}$.

Without loss of generality, we mainly consider $y_{ui}=1$ in BCE loss and have

$\displaystyle\frac{\partial\mathcal{L}^{ui}}{\partial\mathbf{e}_{k}}$
$\displaystyle=-\frac{\partial\ln\sigma(\hat{y}_{ui})}{\partial\mathbf{e}_{k}}=-\frac{\ln\sigma(\hat{y}_{ui})}{\partial\sigma(\hat{y}_{ui})}\cdot\frac{\partial\sigma(\hat{y}_{ui})}{\partial\hat{y}_{ui}}\cdot\frac{\partial\hat{y}_{ui}}{\partial\mathbf{e}_{k}}$
(3)
$\displaystyle=-\frac{1}{\sigma(\hat{y}_{ui})}\cdot\sigma(\hat{y}_{ui})(1-\sigma(\hat{y}_{ui}))\cdot\frac{\partial\hat{y}_{ui}}{\partial\mathbf{e}_{k}}$
$\displaystyle=-[1-\sigma(\hat{y}_{ui})]\frac{\partial\hat{y}_{ui}}{\partial\mathbf{e}_{k}}$
$\displaystyle=-\lambda_{ui}\frac{\partial\hat{y}_{ui}}{\partial\mathbf{e}_{k}},$

where $\hat{y}_{ui}$ is the prediction between the user $u$ and the item $i$
and $0<\lambda_{ui}<1$.

Definition 2 (Influence of a node on another node’s representation learning):
Suppose that a node $i$ can reach a neighbor node $k$ on a graph333Without
loss of generality, we ignore whether a node is a user or an item.. The
influence of the loss for the target node $i$ on the node $k$ is defined as
$\frac{\partial\mathcal{L}_{i}}{\partial\mathbf{e}_{k}}$, where
$\mathcal{L}_{i}=\sum_{j\in\mathcal{N}_{i}}\mathcal{L}^{ij}$.

In fact, the influence provides a fine-grained scrutiny of updating
information of each node at the lens of gradient derivation. We then have the
following lemma.

######  Lemma 3.1.

If node $i$ with degree $d_{i}$ can reach node $k$ after stacking $L$ layers
of graph convolution, then the influence of node $i$ on node $k$ follows

$\mathbb{E}\left(\frac{\partial\mathcal{L}_{i}}{\partial\textbf{e}_{k}}\right)\propto-
d_{i}^{\frac{3}{2}}\boldsymbol{\vartheta}_{i},$ (4)

where $\mathbb{E}(\cdot)$ is the expectation,
$\boldsymbol{\vartheta}_{i}=\mathbb{E}\left(\sum\limits_{p=1}^{\Phi_{j}}\prod\limits_{l=L-1}^{1}\frac{1}{\sqrt{d_{p^{l}}}}\textbf{e}_{j}\right)$
represents the expectation on paths starting from a neighbor node $j$ of the
node $i$ to the node $k$, $\Phi_{j}$ is the set of all $(L-1)$-length paths
from the node $j$ to the node $k$, $p^{L-1}$ and $p^{1}$ are the node $j$ and
the node $k$, respectively.

######  Proof 3.2.

According to Eq. (3) and Eq. (1), we obtain

$\displaystyle\frac{\partial\mathcal{L}_{i}}{\partial\mathbf{e}_{k}}$
$\displaystyle=\sum\limits_{j\in\mathcal{N}_{i}}\frac{\partial\mathcal{L}^{ij}}{\partial\mathbf{e}_{k}}=-\sum\limits_{j\in\mathcal{N}_{i}}\lambda_{ij}\frac{\partial\hat{y}_{ij}}{\partial\mathbf{e}_{k}}=-\sum\limits_{j\in\mathcal{N}_{i}}\lambda_{ij}\frac{\partial\mathbf{e}_{i}}{\partial\mathbf{e}_{k}}\mathbf{e}_{j}$
(5)
$\displaystyle=-\sum\limits_{j\in\mathcal{N}_{i}}\lambda_{ij}\sum\limits_{p=1}^{\Phi}\prod\limits_{l=L}^{1}\frac{1}{\sqrt{d_{p^{l}}}}\mathbf{e}_{j},$

where $p^{L}$ is the node $i$, $\Phi$ is the set of all $L$-length random
paths on the graph from nodes $i$ to $k$, and we omit the transpose symbol of
the partial derivative for brevity. Further, we have

$\displaystyle\mathbb{E}\left(\frac{\partial\mathcal{L}_{i}}{\partial\textbf{e}_{k}}\right)$
$\displaystyle=-\mathbb{E}\left(\sum\limits_{j\in\mathcal{N}_{i}}\lambda_{ij}\sum\limits_{p=1}^{\Phi}\prod\limits_{l=L}^{1}\frac{1}{\sqrt{d_{p^{l}}}}\mathbf{e}_{j}\right)$
(6)
$\displaystyle\propto-\sqrt{d_{i}}\mathbb{E}\left(\sum\limits_{j\in\mathcal{N}_{i}}\sum\limits_{p=1}^{\Phi_{j}}\prod\limits_{l=L-1}^{1}\frac{1}{\sqrt{d_{p^{l}}}}\textbf{e}_{j}\right)$
$\displaystyle\approx-
d_{i}^{\frac{3}{2}}\mathbb{E}\left(\sum\limits_{p=1}^{\Phi_{j}}\prod\limits_{l=L-1}^{1}\frac{1}{\sqrt{d_{p^{l}}}}\textbf{e}_{j}\right)=-d_{i}^{\frac{3}{2}}\boldsymbol{\vartheta}_{i}.$

Finish the proof.

We visualize the results of $d^{\frac{3}{2}}\|\boldsymbol{\vartheta}\|$ and
$\|\boldsymbol{\vartheta}\|$ in log scale in Figure 2. Items are evenly
divided into several groups in ascending order of their degrees. For each item
group, we show its average $\ln(d^{\frac{3}{2}}\|\boldsymbol{\vartheta}\|)$
and $\ln(\|\boldsymbol{\vartheta}\|)$ in terms of the two-hop neighbor nodes
(i.e., $L=2$ in Lemma 3.1) when training LightGCN. As we see,
$\ln(d^{\frac{3}{2}}\|\boldsymbol{\vartheta}\|)$ enlarges as degree increases.
Compared to $\ln(d^{\frac{3}{2}}\|\boldsymbol{\vartheta}\|)$,
$\ln(\|\boldsymbol{\vartheta}\|)$ is relatively smaller and flat across at
different degrees. This illustrates that the degree of nodes plays a crucial
role in the influence. Following the assumption in [19], we posit
$\|\boldsymbol{\vartheta}_{i}\|=\phi$ for any node $i$.

Conclusion 1: If nodes $r$ and $s$ with $d_{r}>d_{s}$ both can reach node $t$
after $L$-hop neighborhood aggregation in a graph, we could have

$\left\|\mathbb{E}\left(\frac{\partial\mathcal{L}_{r}}{\partial\textbf{e}_{t}}\right)\right\|>\left\|\mathbb{E}\left(\frac{\partial\mathcal{L}_{s}}{\partial\textbf{e}_{t}}\right)\right\|.$
(7)

It suggests that the nodes with higher degrees exert larger influence on L-hop
neighbor nodes than lower-degree nodes in the training stage of GCN-based
models. In other words, the popular items dominate the updating information of
neighbor users. As a result, popular items would make reachable users get
closer to them in the representation space. Based on the results in the
upcoming lemma, we further prove that the popular items tend to have higher
probabilities of being recommended by users.

Figure 2: Average $\|\boldsymbol{\theta}\|$ and
$d^{\frac{3}{2}}\|\boldsymbol{\theta}\|$ in each items group. Items are sorted
into groups in ascending order of their degrees. Figure 3: The average
aggregation weight of one-order neighbor users in each items group. Items are
sorted into groups in ascending order of their degrees.

######  Lemma 3.3.

Suppose that the items $r$ and $s$ could reach the user $t$ by stacking $L$
layers of graph convolution, and $d_{r}>d_{s}$. After $L-1$ rounds of graph
convolution, the expectation of prediction difference between the two items
with regard to the user $t$ is
$\mathbb{E}\left[\mathbf{e}_{t}^{\top}(\mathbf{e}_{r}-\mathbf{e}_{s})\right]$.
By performing the $L$-th graph convolution and after the representation of
user $t$ updates the gradients
$\left(\frac{\partial\mathcal{L}_{r}}{\partial\mathbf{e}_{t}}+\frac{\partial
L_{s}}{\partial\mathbf{e}_{t}}\right)$, the prediction difference becomes
larger, i.e.,

$\mathbb{E}\left\\{\left[\mathbf{e}_{t}-\left(\frac{\partial\mathcal{L}_{r}}{\partial\mathbf{e}_{t}}+\frac{\partial\mathcal{L}_{s}}{\partial\mathbf{e}_{t}}\right)\right]^{\top}(\mathbf{e}_{r}-\mathbf{e}_{s})\right\\}\geq\mathbb{E}\left[\mathbf{e}_{t}^{\top}(\mathbf{e}_{r}-\mathbf{e}_{s})\right].$
(8)

Further, after $e_{r}$ and $e_{s}$ updates, the prediction difference
continues to enlarge,

$\displaystyle\mathbb{E}\left\\{\left[\mathbf{e}_{t}-\left(\frac{\partial\mathcal{L}_{r}}{\partial\mathbf{e}_{t}}+\frac{\partial\mathcal{L}_{s}}{\partial\mathbf{e}_{t}}\right)\right]^{\top}(\mathbf{e}^{\prime}_{r}-\mathbf{e}^{\prime}_{s})\right\\}$
(9)
$\displaystyle\geq\mathbb{E}\left\\{\left[\mathbf{e}_{t}-\left(\frac{\partial\mathcal{L}_{r}}{\partial\mathbf{e}_{t}}+\frac{\partial\mathcal{L}_{s}}{\partial\mathbf{e}_{t}}\right)\right]^{\top}(\mathbf{e}_{r}-\mathbf{e}_{s})\right\\}.$

where $\mathbf{e}^{\prime}_{r}$ and $\mathbf{e}^{\prime}_{s}$ are the
representations of the items $r$ and $s$ after aggregating the user $t$,
respectively.

######  Proof 3.4.

After the influence of the items $r$ and $s$ propagate to the user $t$ by
stacking $L$ graph convolution layers, this changes the representation of user
$t$ from $\mathbf{e}_{t}$ to
$\mathbf{e}_{t}-\left(\frac{\partial\mathcal{L}_{r}}{\partial\mathbf{e}_{t}}+\frac{\partial\mathcal{L}_{s}}{\partial\mathbf{e}_{t}}\right)$.
Assume that the influence
$\mathbb{E}\left(\frac{\partial\mathcal{L}_{r}}{\partial\mathbf{e}_{t}}\right)=-\upsilon_{1}d_{r}^{\frac{3}{2}}\boldsymbol{\vartheta}_{r}$
($\upsilon_{1}>0$) and
$\frac{\boldsymbol{\vartheta}_{r}}{\|\boldsymbol{\vartheta}_{r}\|}=\upsilon_{2}\frac{\mathbf{e}_{r}}{\|\mathbf{e}_{r}\|}$
($\upsilon_{2}>0$ for the local homogeneity), likewise,
$\mathbb{E}\left(\frac{\partial\mathcal{L}_{s}}{\partial\mathbf{e}_{t}}\right)=-\upsilon_{1}d_{s}^{\frac{3}{2}}\boldsymbol{\vartheta}_{s}$
and
$\frac{\boldsymbol{\vartheta}_{s}}{\|\boldsymbol{\vartheta}_{s}\|}=\upsilon_{2}\frac{\mathbf{e}_{s}}{\|\mathbf{e}_{s}\|}$.
Now we calculate the prediction difference between the items $r$ and $s$ on
the user $t$,

$\displaystyle\mathbb{E}\left\\{\left[\mathbf{e}_{t}-\left(\frac{\partial\mathcal{L}_{r}}{\partial\mathbf{e}_{t}}+\frac{\partial\mathcal{L}_{s}}{\partial\mathbf{e}_{t}}\right)\right]^{\top}(\mathbf{e}_{r}-\mathbf{e}_{s})\right\\}$
(10) $\displaystyle=$
$\displaystyle\mathbb{E}[\mathbf{e}_{t}^{\top}(\mathbf{e}_{r}-\mathbf{e}_{s})]$
$\displaystyle+\upsilon_{1}\mathbb{E}\left[d_{r}^{\frac{3}{2}}\boldsymbol{\vartheta}_{r}^{\top}\mathbf{e}_{r}-d_{r}^{\frac{3}{2}}\boldsymbol{\vartheta}_{r}^{\top}\mathbf{e}_{s}+d_{s}^{\frac{3}{2}}\boldsymbol{\vartheta}_{s}^{\top}\mathbf{e}_{r}-d_{s}^{\frac{3}{2}}\boldsymbol{\vartheta}_{s}^{\top}\mathbf{e}_{s}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}[\mathbf{e}_{t}^{\top}(\mathbf{e}_{r}-\mathbf{e}_{s})]+\upsilon_{1}\upsilon_{2}\mathbb{E}\left[d_{r}^{\frac{3}{2}}\frac{\|\boldsymbol{\vartheta}_{r}\|}{\|\mathbf{e}_{r}\|}\mathbf{e}_{r}^{\top}\mathbf{e}_{r}-d_{r}^{\frac{3}{2}}\frac{\|\boldsymbol{\vartheta}_{r}\|}{\|\mathbf{e}_{r}\|}\mathbf{e}_{r}^{\top}\mathbf{e}_{s}\right.$
$\displaystyle\left.+d_{s}^{\frac{3}{2}}\frac{\|\boldsymbol{\vartheta}_{s}\|}{\|\mathbf{e}_{s}\|}\mathbf{e}_{s}^{\top}\mathbf{e}_{r}-d_{s}^{\frac{3}{2}}\frac{\|\boldsymbol{\vartheta}_{s}\|}{\|\mathbf{e}_{s}\|}\mathbf{e}_{s}^{\top}\mathbf{e}_{s}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}[\mathbf{e}_{z}^{\top}(\mathbf{e}_{r}-\mathbf{e}_{s})]$
$\displaystyle+\upsilon_{1}\upsilon_{2}\phi\mathbb{E}\left[d_{r}^{\frac{3}{2}}(\|\mathbf{e}_{r}\|-\frac{\rho}{\|\mathbf{e}_{r}\|})-d_{s}^{\frac{3}{2}}(\|\mathbf{e}_{s}\|-\frac{\rho}{\|\mathbf{e}_{s}\|})\right],$

where $\rho=\mathbf{e}_{r}^{\top}\mathbf{e}_{s}$ and
$\rho\leq\|\mathbf{e}_{r}\|\|\mathbf{e}_{s}\|$. Since the magnitude of the
node representation increases as its degree increases [20], for $d_{r}>d_{s}$,
there is $\|\mathbf{e}_{r}\|>\|\mathbf{e}_{s}\|$ generally. Let
$\|\mathbf{e}_{r}\|=\kappa\|\mathbf{e}_{s}\|$ with $\kappa>1$. Therefore, we
have

$\displaystyle
d_{r}^{\frac{3}{2}}(\|\mathbf{e}_{r}\|-\frac{\rho}{\|\mathbf{e}_{r}\|})-d_{s}^{\frac{3}{2}}(\|\mathbf{e}_{s}\|-\frac{\rho}{\|\mathbf{e}_{s}\|})$
(11) $\displaystyle=$ $\displaystyle(d_{r}^{\frac{3}{2}}\kappa-
d_{s}^{\frac{3}{2}})\|\mathbf{e}_{s}\|-(d_{r}^{\frac{3}{2}}-d_{s}^{\frac{3}{2}}\kappa)\frac{\rho}{\|\mathbf{e}_{r}\|},$

since $d_{r}^{\frac{3}{2}}\kappa-
d_{s}^{\frac{3}{2}}>d_{r}^{\frac{3}{2}}-d_{s}^{\frac{3}{2}}\kappa$ and
$\|\mathbf{e}_{s}\|\geq\frac{\rho}{\|\mathbf{e}_{r}\|}$, thus Eq. (11) $>$ 0\.
Based on this, we derive the expression of (8).

Furthermore, after the items $r$ and $s$ aggregate the information of the user
$t$, we obtain

$\displaystyle\mathbf{e}^{\prime}_{r}$
$\displaystyle=\mathbf{e}_{r}+\omega_{rt}\left[\mathbf{e}_{t}-\left(\frac{\partial\mathcal{L}_{r}}{\partial\mathbf{e}_{t}}+\frac{\partial\mathcal{L}_{s}}{\partial\mathbf{e}_{t}}\right)\right]=\mathbf{e}_{r}+\omega_{rt}\tilde{\mathbf{e}}_{t},$
(12)

where $\omega_{rt}$ is the weight of aggregation. Likewise,

$\displaystyle\mathbf{e}^{\prime}_{s}$
$\displaystyle=\mathbf{e}_{s}+\omega_{st}\left[\mathbf{e}_{t}-\left(\frac{\partial\mathcal{L}_{r}}{\partial\mathbf{e}_{t}}+\frac{\partial\mathcal{L}_{s}}{\partial\mathbf{e}_{t}}\right)\right]=\mathbf{e}_{s}+\omega_{st}\tilde{\mathbf{e}}_{t}.$
(13)

Now we calculate the rating difference again,

$\displaystyle\mathbb{E}\left\\{\left[\mathbf{e}_{t}-\left(\frac{\partial\mathcal{L}_{r}}{\partial\mathbf{e}_{t}}+\frac{\partial\mathcal{L}_{s}}{\partial\mathbf{e}_{t}}\right)\right]^{\top}(\mathbf{e}^{\prime}_{r}-\mathbf{e}^{\prime}_{s})\right\\}$
(14) $\displaystyle=$
$\displaystyle\mathbb{E}\left\\{\tilde{\mathbf{e}}^{\top}_{t}[(\mathbf{e}_{t}-\mathbf{e}_{s})+(\omega_{rt}-\omega_{st})\tilde{\mathbf{e}}_{t}]\right\\}$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\tilde{\mathbf{e}}^{\top}_{t}(\mathbf{e}_{r}-\mathbf{e}_{s})+(\omega_{rt}-\omega_{st})\|\tilde{\mathbf{e}}_{t}\|^{2}\right],$

when $\omega_{rt}-\omega_{st}\geq 0$, the expression of (9) holds. We
visualize the average aggregation weight $\omega$ of one-order neighbor users
for each item groups when training LightGCN in Figure 3. From the results, it
can be observed that $\omega$ is larger as degree increases generally.
Therefore, the expectation of the rating difference would be enlarged for
$d_{r}>d_{s}$ after graph convolution. Finish the proof.

Conclusion 2: The theoretical analyses show that the gap of the prediction
scores between popular items and tail items w.r.t. users enlarges with deep
layers of graph convolution. It indicates that popular items would become more
influential by affecting more high-order neighbor users. As a consequence,
popular items are more likely be over-recommended as GCNs go deeper. It
reveals how GCN-based models amplify the popularity bias, providing
theoretical supports to the phenomenon shown in Figure 1.

###  3.2 Our Method — DAP

In this section, we propose our method DAP (Debias the Amplification of
Popularity) to alleviate the issue of the popularity bias amplification of GCN
in the inference stage.

From Lemma 3.3, the popularity bias amplification comes from the updating of
node representation and neighborhood aggregation after graph convolution when
training GCN backbone models. Taking LightGCN as an example, we can quantify
the bias after graph convolution at each layer in a unified form as

$\displaystyle\mathbf{e}^{(l)}_{v}$
$\displaystyle=\sum\limits_{j\in\mathcal{N}_{v}}\frac{1}{\sqrt{d_{v}}\sqrt{d_{j}}}\mathbf{e}^{(l-1)}_{j}$
(15)
$\displaystyle=\sum\limits_{j\in\mathcal{N}_{v}}\frac{1}{\sqrt{d_{v}}\sqrt{d_{j}}}(\hat{\mathbf{e}}^{(l-1)}_{j}+\alpha_{H_{j}}^{(l-1)}\boldsymbol{\vartheta}^{(l-1)}_{H_{j}}+\alpha_{L_{j}}^{(l-1)}\boldsymbol{\vartheta}^{(l-1)}_{L_{j}})$
$\displaystyle=\hat{\mathbf{e}}^{(l)}_{v}+\alpha_{H_{v}}^{(l)}\boldsymbol{\vartheta}^{(l)}_{H_{v}}+\alpha_{L_{v}}^{(l)}\boldsymbol{\vartheta}^{(l)}_{L_{v}},$

where $\hat{\mathbf{e}}^{(l)}_{v}$ is the ideal representation of the node $v$
at the $l$-th layer,
$\alpha_{H_{v}}^{(l)}\boldsymbol{\vartheta}^{(l)}_{H_{v}}$ and
$\alpha_{L_{v}}^{(l)}\boldsymbol{\vartheta}^{(l)}_{L_{v}}$ are the bias that
comes from higher-degree and lower-degree neighbors respectively.
Specifically, there are two amplification effects: (1) the higher-degree
neighbors have large influence and dominate the updating of the target node’s
representation. It is inclined to make the target node position close to the
higher-degree neighbors in the representation space; (2) for the lower-degree
neighbors, the representations of them are influenced by the target node,
leading to biased learning; after graph convolution, such bias would be
further aggregated into the target node. Those two amplification effects are
need to be estimated and intervened.

In addition, in order to estimate the bias of each node, we employ clustering
algorithms to group node representations into clusters. The clustering can
automatically discover the highly-influential nodes as they are close to each
other in the representation space. For each node, we estimate its
amplification effect within its cluster and then intervene the bias in the
representations. The specific debiasing process is as follows.

Given a well-trained GCN-based backbone model, we could obtain the 0-th layer
representations $\textbf{E}^{(0)}\in\mathbb{R}^{(M+N)\times D}$ (D is the
embedding size) of all nodes. Then, these representations are fed into the
next layer of graph convolution. As we discussed earlier, the bias appears
after graph convolution and nodes which in the same cluster are most possible
to affect each other. Thus, $Kmeans$ is employed to group nodes in the
representation space. For the $l$-th layer node representations
$\textbf{E}^{(l)}$ of all nodes, $Kmeans$ automatically divides them into $P$
clusters, i.e.,

$\\{\mathcal{C}_{1}^{(l)},\mathcal{C}_{2}^{(l)},\cdots,\mathcal{C}_{P}^{(l)}\\}=Kmeans(\textbf{E}^{(l)}),$
(16)

where $P$ is a hyper-parameter of $Kmeans$. For a node $v$, we can know the
cluster it belongs to. To intervene the amplified bias effect
$\textbf{b}_{v}^{(l)}$ after $l$-th graph convolution, we have the following
strategy: for the node $v$ with degree $d_{v}$ in the cluster
$\mathcal{C}^{(l)}_{p}$, we can obtain a set of higher-degree nodes
$\mathbb{H}_{v}^{(l)}=\\{j\in\mathcal{C}^{(l)}_{p},d_{j}>d_{v}\\}$, and a set
of lower-degree nodes
$\mathbb{L}_{v}^{(l)}=\\{j\in\mathcal{C}^{(l)}_{p},d_{j}<d_{v}\\}$. For the
two parts $\mathbb{H}_{v}^{(l)}$ and $\mathbb{L}_{v}^{(l)}$ of node $v$, their
pooling (e.g., mean pooling, weighted average pooling with degree)
representations after normalization $\
\hat{\boldsymbol{\vartheta}}_{H_{v}}^{(l)}\in\mathbb{R}^{1\times D}$ and
$\hat{\boldsymbol{\vartheta}}_{L_{v}}^{(l)}\in\mathbb{R}^{1\times D}$ can be
computed respectively. Thereafter, its amplification bias
$\textbf{b}_{v}^{(l)}$ after $l$-th layer graph convolution is estimated by

$\textbf{b}_{v}^{(l)}=\alpha\mathcal{M}(\textbf{e}^{(l)}_{v},\hat{\boldsymbol{\vartheta}}_{H_{v}}^{(l)})\hat{\boldsymbol{\vartheta}}_{H_{v}}^{(l)}+\beta\mathcal{M}(\textbf{e}^{(l)}_{v},\hat{\boldsymbol{\vartheta}}_{L_{v}}^{(l)})\hat{\boldsymbol{\vartheta}}_{L_{v}}^{(l)},$
(17)

where $\alpha$ and $\beta$ are hyper-parameters that intervene the effect of
bias in the final representation at the $l$-th layer since the popularity bias
may be not completely harmful [21]. The larger the values of $\alpha$ and
$\beta$, the greater the bias on the node. $\mathcal{M}$ is a similarity
calculation function (e.g., cosine similarity) for measuring how strongly the
node $v$ is affected by different parts.

After the above operations, we intervene the bias effect and revise the
representation of the node $v$ at $l$-th layer graph convolution, i.e.,

$\hat{\textbf{e}}_{v}^{(l)}=\textbf{e}_{v}^{(l)}-\textbf{b}_{v}^{(l)}.$ (18)

Then the revised representation $\hat{\textbf{e}}_{v}^{(l)}$ is fed into the
next layer in GCNs and we get the node representations at $(l+1)$-th layer
$\mathbf{E}^{(l+1)}$. In an iterative manner, we can obtain all the ideal
representations at each layer. For all representations rectified at different
layers, they are assembled in the manner as the original model does to get the
final representations.

##  4 Experiments

In this section, we conduct experiments to evaluate the performance of our
proposed DAP, aiming at answering the following research questions:

  * •

RQ1: Does DAP outperform other debiasing methods?

  * •

RQ2: How do higher-degree part, lower-degree part and the hyper-parameters
affect the recommendation performance?

  * •

RQ3: Can DAP mitigate the popularity bias?

###  4.1 Experiments Settings

Table 2: Dataset description

Dataset | #Users | #Items | #Interactions | Density
---|---|---|---|---
Gowalla | 29,858 | 40,981 | 1,027,370 | 0.00084
Yelp2018 | 31,668 | 38,048 | 1,561,406 | 0.00130
Amazon-book | 52,643 | 91,599 | 2,984,108 | 0.00062

Table 3: Performance comparison between our method DAP and other counterparts
on the Overall and Tail test sets. The ‘improve’ is the relative improvement
of LightGCN-DAP-o over LightGCN.

Dataset | Gowalla | Yelp2018 | Amazon-book
---|---|---|---
Models | Overall | Tail | Overall | Tail | Overall | Tail
Recall | NDCG | Recall | NDCG | Recall | NDCG | Recall | NDCG | Recall | NDCG | Recall | NDCG
LightGCN |  0.1820 |  0.1546 | 0.0434 | 0.0191 |  0.0627 |  0.0516 | 0.0091 | 0.0046 |  0.0414 |  0.0321 | 0.009 | 0.0051
BFGCN | 0.1083 | 0.0805 | 0.0468 | 0.0245 | 0.0389 | 0.0311 | 0.0124 | 0.0076 | 0.0276 | 0.0211 | 0.0097 | 0.0059
LightGCN-IPSCN | 0.1325 | 0.1132 | 0.0477 | 0.0213 | 0.0473 | 0.0391 | 0.0136 | 0.0077 | 0.0285 | 0.0221 | 0.0118 | 0.0069
LightGCN-CausE | 0.1334 | 0.1137 | 0.0485 | 0.0225 | 0.0492 | 0.0405 | 0.0141 | 0.0085 | 0.0299 | 0.0230 | 0.0127 | 0.0078
LightGCN-DICE | 0.1337 | 0.1138 | 0.0493 | 0.0241 | 0.0505 | 0.0409 | 0.0132 | 0.0073 | 0.0348 | 0.0264 | 0.0121 | 0.0074
LightGCN-MACR | 0.1188 | 0.0928 | 0.0478 | 0.0219 | 0.0343 | 0.027 | 0.0233 |  0.0126 | 0.0269 | 0.0204 | 0.0108 | 0.0065
LightGCN-Tail | 0.1647 | 0.1391 | 0.0628 | 0.0319 | 0.057 | 0.0466 | 0.0154 | 0.0095 | 0.0369 | 0.0283 | 0.0151 | 0.0094
LightGCN-BxQuAD | 0.1378 | 0.1130 |  0.0689 | 0.0360 | 0.0545 | 0.0431 | 0.0209 | 0.0123 | 0.0389 | 0.0304 |  0.0164 | 0.0108
LightGCN-DAP-o | 0.1834 | 0.1564 | 0.0538 | 0.0245 | 0.0634 | 0.0521 | 0.0137 | 0.0073 | 0.0436 | 0.0339 | 0.0134 | 0.0079
LightGCN-DAP-t | 0.1672 | 0.1427 | 0.0708 |  0.0354 | 0.0562 | 0.0461 |  0.0218 | 0.0129 | 0.0414 | 0.0328 | 0.0166 |  0.0102
improve | 0.77% | 1.16% | 23.96% | 28.27% | 1.12% | 0.97% | 50.55% | 58.70% | 4.83% | 5.61% | 48.89% | 54.90%

We conduct experiments on three real-world datasets, Table 2 lists the
statistics of three datasets. In order to guarantee a fair comparison, we
follow the settings of LightGCN [6] and randomly split the training set and
test set. The test set is called Overall. Since our DAP is expected to
mitigate the popularity bias and improve the performance on the tail items, we
specially split a subset of tail items from the whole test set, named Tail
test set, in contrast to the Overall counterpart. In addition, we randomly
split 20% data from the training set as the validation set for tuning the
hyper-parameters. Note that the same splitting strategy is applied to the
validation set.

####  4.1.1 Compared Methods

To evaluate the debiasing performance on recommendation, we implement our DAP
with the GCN-based recommender models LightGCN and UltraGCN to explore how our
DAP improves the recommendation performance for GCNs. In addition, three
methods for solving the popularity bias and two methods for improving tail
node representations are compared:

  * •

BFGCN [22]: This is a novel graph convolution filter for the user-item
bipartite network to improve long-tail node representations.

  * •

UltraGCN [14]: This is a state-of-the-art method that achieves the best
performance on the three datasets. It is an ultra-simplified formulation of
GCN which skips explicit message passing and directly approximate the limit of
infinite graph convolution layers.

  * •

IPSCN [23]: This method adds max-capping and normalization on IPS [24] value
to reduce the variance of IPS. IPS eliminates popularity bias by re-weighting
each item according to its popularity.

  * •

CausE [25]: It requires a large sample of biased data and a small sample of
unbiased data. CausE adds a regularizer term on the discrepancy between the
item vectors used to fit the biased sample and their counterpart
representations that fit the unbiased sample. Because there is no unbiased
data in our datasets, we adopt the sampling method in [10] and obtain 20%
unbiased data from the training set.

  * •

DICE [10]: DICE is a method to handle with the popularity bias problem by
learning causal embeddings. It is a framework with causal-specific data to
disentangle interest and popularity into two sets of embeddings.

  * •

MACR [9]: This is a state-of-the-art method to eliminate the popularity bias
by counterfactual reasoning. It performs counterfactual inference to remove
the effect of item popularity.

  * •

BxQuAD [13]: BxQuAD is a typical post-hoc method for improving tail item
recommendations. It suffers from the recommendation accuracy drop for
controlling popular items. In this paper, we adopt the Binary-xQuAD method of
the original paper and set the hyper-parameter $\lambda=0.9$.

  * •

Tail [26]: This method learns a neighborhood translation from head nodes,
which can be further transferred to tail nodes to enhance their
representations. It is devised for node classification and we transfer it to
the field of recommendation.

We report the all-ranking performance w.r.t. two metrics: Recall and NDCG cut
at 20.

Table 4: Performance comparison between our method DAP and other counterparts
on the Overall and Tail test sets. The ‘improve’ is the relative improvement
of UltraGCN-DAP-o over UltraGCN.

Dataset | Gowalla | Yelp2018 | Amazon-book
---|---|---|---
Models | Overall | Tail | Overall | Tail | Overall | Tail
Recall | NDCG | Recall | NDCG | Recall | NDCG | Recall | NDCG | Recall | NDCG | Recall | NDCG
UltraGCN | 0.1862 | 0.1579 | 0.0447 | 0.0213 | 0.0676 | 0.0554 | 0.0127 | 0.0074 | 0.0682 | 0.0556 | 0.0436 | 0.0297
UltraGCN-IPSCN | 0.1345 | 0.1123 | 0.0451 | 0.0208 | 0.0401 | 0.0324 | 0.0144 | 0.0087 | 0.0442 | 0.0356 | 0.0458 | 0.0317
UltraGCN-CausE | 0.1408 | 0.1177 | 0.0449 | 0.0209 | 0.0411 | 0.0329 | 0.0151 | 0.0096 | 0.0459 | 0.0369 | 0.0463 | 0.0320
UltraGCN-DICE | 0.1424 | 0.1201 | 0.0512 | 0.0247 | 0.0516 | 0.0417 | 0.0157 | 0.0096 | 0.0545 | 0.0423 | 0.0491 | 0.0343
UltraGCN-MACR | 0.1311 | 0.1078 | 0.0517 | 0.0252 | 0.0387 | 0.0323 | 0.0248 | 0.0141 | 0.0501 | 0.0398 | 0.0488 | 0.0335
UltraGCN-Tail | 0.1788 | 0.1521 | 0.0634 | 0.0321 | 0.0618 | 0.0501 | 0.0167 | 0.0102 | 0.0599 | 0.0499 | 0.0531 | 0.0378
UltraGCN-BxQuAD | 0.1482 | 0.1289 | 0.0694 | 0.0361 | 0.0591 | 0.0482 | 0.0218 | 0.0136 | 0.0623 | 0.0517 | 0.0547 | 0.0386
UltraGCN-DAP-o | 0.1868 | 0.1580 | 0.0551 | 0.0271 | 0.0678 | 0.0555 | 0.0135 | 0.0079 | 0.0688 | 0.0562 | 0.0462 | 0.0316
UltraGCN-DAP-t | 0.1701 | 0.1483 | 0.0714 | 0.0362 | 0.0607 | 0.0493 | 0.0237 | 0.0135 | 0.0625 | 0.0520 | 0.0543 | 0.0391
improve | 0.32% | 0.06% | 5.59% | 6.57% | 0.30% | 0.18% | 6.30% | 6.76% | 0.88% | 1.07% | 5.96% | 6.40%

####  4.1.2 Hyper-parameter Settings

For a fair comparison, all compared GCN-based models are implemented with 3
layers except for the UltraGCN. We optimize all models with Adam [27] with
batch size as 4096. For our method, the number of clusters $P$ is searched in
$\\{1,5,10,20,30,\cdots,70\\}$. Note that we keep the same $P$ in each layer
when operating $Kmeans$. The hyper-parameters $\alpha$ and $\beta$ in Eq. (17)
are tuned in the range of [0, 2.0] with step of 0.1.

###  4.2 Recommendation Performance (RQ1)

We compare all methods on the Overall and Tail test sets in Tables 3 and 4,
where the hyper-parameters of DAP-t and DAP-o are tuned to the best on the
Tail and Overall validation sets, respectively. The promotions reported in
Tables 3 and 4 are calculated by comparing LightGCN-DAP-o (UltraGCN-DAP-o)
with LightGCN (UltraGCN). In general, our DAP significantly boosts two GCN
methods on the Tail test set. The main observations are as follows:

  * •

In all cases, our DAP-o brings performance gain in Recall and NDCG for
LightGCN on the Overall and Tail test sets while other baselines only boost
LightGCN on the Tail test set. These comparison methods mainly rely on
suppressing popular items in exchange for the promotion of tail items.
However, our method revises the node representations by intervening the
popularity bias based on theoretical analyses on GCNs. It is more applicable
to GCN-based backbones.

  * •

In terms of the performance on the Tail test set, our DAP-t has a significant
improvement over LightGCN, the average improvements of
LightGCN-DAP-t over LightGCN on the three datasets are 95.71% on Recall and
121.92% on NDCG, respectively. In the same time, the performance on the
Overall test set only has a small drop. Although some competitive baselines
outperform DAP-t on some metrics, DAP demonstrates stronger comprehensive
abilities on different test sets.

  * •

In order to further verify the effectiveness of our method compared to
LightGCN, we show the performance comparison at each layer in Figure 4.
Overall, it can be seen that DAP boosts LightGCN stably layer by layer.
Particularly, on the Amazon-book, when LightGCN degrades the performance as
the graph convolution goes deeper, DAP has no accuracy drop. It indicates that
the effectiveness of our debiasing method for improving the representations of
nodes.

  * •

For the method UltraGCN, we implement our DAP on it. Because UltraGCN directly
uses infinite layers of graph convolution, we only can debias on its final
representations. In Table 4, compared with other baselines, our method shows a
similar trend to Table 3. It validates the effectiveness of our method. It
should be noted that the improvement is relatively small on the Tail test set
compared to that on LightGCN. This is mainly because we can not debias at each
layer of graph convolution and obtain the most ideal representations.

To conclude, DAP can effectively improve the performance of tail items for GCN
backbones and outperforms baselines in general.

Figure 4: Performance comparison between LightGCN and LightGCN-DAP with
different layers of graph convolution on the Overall test set.

Figure 5: Ablation study of DAP with different hyper-parameters $\alpha$ and
$\beta$ on the Overall test set.

###  4.3 Ablation Study (RQ2)

####  4.3.1 Performance of Variants.

To evaluate the amplification effect brought by higher-degree nodes and lower-
degree nodes, we design five variants of DAP implemented on LightGCN
including: (1) DAP-kh: this variant is derived by setting $\beta=0$ in Eq.
(17) which aims to evaluate the amplification effect of higher-degree nodes;
(2) DAP-kl: this variant is obtained by setting $\alpha=0$ for evaluating the
effect of lower-degree nodes; (3) DAP-nh: this variant treats one-order
neighbors of the target node as its cluster instead of using $Kmeans$ and sets
$\beta=0$ for exploring the effect of higher-degree neighbors; (4) DAP-nl:
this variant is the opposite of DAP-nh, using one-order lower-degree neighbors
(i.e., $\alpha=0$); (5) DAP-m: it is derived by removing the similarity
calculation function $\mathcal{M}$ in Eq. (17) and is without considering the
effect of the lower-degree part (i.e., $\beta=0$).

For each variant, we need only tune $\alpha$ or $\beta$. For example, we
adjust $\alpha$ for DAP-kh from 0 to 1 on the Gowalla dataset. Figure 5 shows
the results on the Overall test set and we have the following observations:
(1) on the three datasets, DAP-kh achieves the best performance. It reflects
that higher-degree nodes have the greater impact on other nodes than lower-
degree ones. (2) DAP-kh and DAP-kl have a better performance than DAP-nh and
DAP-nl on the three datasets. It indicates that estimating the amplified bias
among one-order neighbors is not enough and may introduce noise. $Kmeans$ can
automatically help discover the highly-influential nodes. In this way, we
would estimate the amplified bias more accurately. (3) Compared to the
performance of DAP-kh and DAP-m, it can be found that DAP-kh outperforms
DAP-m. It reflects that the similarity function $\mathcal{M}$ could capture
the relation strength among nodes and thus help estimate the amplified bias
well.

####  4.3.2 Effect of Different Hyper-Parameters $\alpha$ and $\beta$.

Tuning $\alpha$ and $\beta$ is important for the performance at the inference
stage. We plot the performance under different $\alpha$ and $\beta$ settings
on the three datasets in Figure 5. It can be observed that the performance on
the Overall test set increases gradually and then decreases while LightGCN is
for $\alpha=0$ and $\beta=0$. This is to say, the popularity bias is not
completely harmful. Directly eliminating all the bias is not reasonable in
recommendation, which conforms with the finding of [21].

####  4.3.3 Effect of Different Hyper-Parameter $P$.

Table 5 reports our experimental results on the three datasets w.r.t. the
hyper-parameter $P$. As can be seen, the performance increases as $P$ becomes
large and then decreases. For different datasets, when $P$ is too small or
large, the popularity bias among nodes can not be captured accurately,
therefore the performance is unsatisfactory. $Kmeans$ is a simple tool for
clustering, other advanced unsupervised clustering tools can be explored for
improving the performance.

Table 5: Effect of $P$ over DAP for the three datasets on the Overall test
set.

Dataset | Gowalla | Yelp2018 | Amazon-book
---|---|---|---
P | Recall | NDCG | Recall | NDCG | Recall | NDCG
1 | 0.1819 | 0.1547 | 0.0629 | 0.0517 | 0.0423 | 0.0329
5 | 0.182 | 0.1548 | 0.063 | 0.0518 | 0.0436 | 0.0339
10 | 0.1823 | 0.1552 | 0.0633 | 0.0521 | 0.0435 | 0.0339
30 | 0.1831 | 0.1563 | 0.0628 | 0.0518 | 0.0435 | 0.0338
50 | 0.1834 | 0.1564 | 0.0626 | 0.0517 | 0.0428 | 0.0334
70 | 0.1833 | 0.1564 | 0.0623 | 0.0515 | 0.0426 | 0.0331

Figure 6: DAP can effectively alleviate the popularity bias.

###  4.4 Alleviating Popularity Bias (RQ3)

We already discuss that GCNs amplify the popularity bias in the introduction.
In this part, we would verify that our debiasing framework can mitigate the
amplification of popularity bias issue. The result of TR@20 (the ratio of
recommending tail items cut at 20) is shown in Figure 6. As can be seen, when
the TR@20 result of LightGCN significantly decreases with more graph
convolution layers, DAP could restraint continuous worsening of the popularity
bias and gradually improve the TR@20 on the three datasets. It means that the
tail items can be recommended more when GCNs go deeper, and thus the
popularity bias is effectively alleviated by DAP. In addition, combining
Figures 4 and 6 gives the conclusion that DAP can not only promote the overall
performance, but also can alleviate the popularity bias at each layer.

##  5 Related work

In this section, we review the research topics related to our work:
recommendation debiasing and GCNs debiasing in classification.

###  5.1 Recommendation Debiasing

Recommendation debiasing is a recently emerged research topic [chen2020bias]
focusing on various biases in recommendation, for example, popularity bias
[28][29][30], exposure bias [31], position bias [32], etc. Many methods have
been explored to analyze and alleviate the popularity bias in recommender
systems. For example, [12, 24] propose inverse propensity score (IPS) methods
that reweights the interactions to debias the popularity bias in the training
loss. However, these methods are difficult to tune because estimating the
propensity score is challenging. [33] proposes another method which combines
data imputation and IPS to jointly learn an unbiased recommender. However, it
is a brute manner for improving the long-tail items with a huge performance
drop on the recommendation accuracy. Other empirical approaches such as
adversarial learning [34], meta learning [35] and transfer learning [36] are
developed without estimating the propensity weight. Ranking adjustment is an
another line of research to solve the popularity bias issue [37, 13].

Recently, methods based on causal inference have been widely applied to solve
bias issues in recommendation, for example, MACR [9] and DICE [10]. And [11]
proposes a causal framework to leverage the popularity bias in recommendation.
Other causal methods for learning an unbiased recommender [38, 25, 39, 40, 41]
are proposed to takle various bias issues. We refer the readers to a system
survey for more details [2].

###  5.2 GCNs Debiasing in Classification

Recently, GCN-based models have demonstrated promising performance and
advancements on classification tasks. However, some recent studies also reveal
various issues of GCNs including over-smoothing, vulnerability and degree-
related biases [42, 43, 44, 45, 19]. The over-smoothing issue can be treated
as a kind of bias in GCNs, which means the node representations are inclined
to be distinguishable, and degrades the performance with many graph
convolution layers. Some methods are proposed to tackle this problem. [46]
proposes GCNII which extends the vanilla GCN model with initial residual
connection and identity mapping to prevent the over-smoothing. [45] proposes
two methods including adding a regularizer to the training objective and
optimizing the graph topology based on the model predictions. Nevertheless,
[47] argues that the over-smoothing issue only happens after a large number of
iterations and the current results with several layers of graph convolution
are relatively far from the ideal over-smoothing situation. For
recommendation, one node can reach all the other nodes by stacking 7 layers
[7]. In this regard, we could treat the nodes clustering issue with shallow
graph convolution layers and over-smoothing with a large number layers
differently.

Besides, [19] points out that GCNs are biased towards higher-degree nodes with
higher accuracy than those lower-degree nodes. The authors analyze this issue
and argue that nodes with low degrees tend to have very few labeled nodes,
which results in sub-optimal performance on low-degree nodes. Therefore, [19]
proposes a method exploiting pseudo labels to enhance the representations for
low-degree nodes. [48] also proposes a training algorithm adding confident
data with virtual labels to the labeled set to enlarge the training set based
on self-training. [26] proposes a method which learns a neighborhood
translation from head nodes to tail nodes. In this way, the representations of
tail nodes can be enhanced for improving the performance of tail nodes.

In this work, we analyze the bias existing in GCN-based recommenders that
high-degree nodes and low-degree nodes influence each other. It is different
from the bias in classification introduced in [19]. And our method is
different with these methods based on producing pseudo labels and translation.

##  6 Conclusion and future work

In this paper, we first theoretically analyzed how GCN-based recommenders
amplify the popularity bias. We show that popular items tend to dominate the
updating information of neighbor users in the training stage, which makes user
position closer to popular items. After multiple times of neighborhood
aggregation, popular items would become more influential by affecting more
high-order neighbor users. Based on the above insights, we propose a simple
yet generic debiasing framework DAP. Our method is implemented in each graph
convolution layer in the inference stage by intervening the amplification
effect on nodes in the representation space. Extensive experiments on the
three real-world datasets justify the effectiveness of DAP. Our method could
promote the recommendation performance on tail items and alleviate the
popularity bias for GCN backbone models.

In the future, we will explore and theoretically analyze more problems hidden
in graph-based recommendation methods. In addition, various biases also exist
in recommender systems that are harmful to users and need to be solved, such
as position bias and exposure bias. It will be meaningful to propose a
universal solution to solve various biases.

## References

  * [1] Wu L, He X, Wang X, Zhang K, Wang M.  A survey on accuracy-oriented neural recommendation: From collaborative filtering to information-rich recommendation.  IEEE Transactions on Knowledge and Data Engineering, 2022, 1–1
  * [2] Chen J, Dong H, Wang X, Feng F, Wang M, He X.  Bias and debias in recommender system: A survey and future directions.  ACM Transactions on Information Systems, 2023, 41(3): 1–39
  * [3] Wang X, He X, Wang M, Feng F, Chua T S.  Neural graph collaborative filtering.  In: Proceedings of the 42nd international ACM SIGIR conference on Research and development in Information Retrieval.  2019, 165–174
  * [4] Wu L, Sun P, Fu Y, Hong R, Wang X, Wang M.  A neural influence diffusion model for social recommendation.  In: Proceedings of the 42nd international ACM SIGIR conference on research and development in information retrieval.  2019, 235–244
  * [5] Wu F, Souza A, Zhang T, Fifty C, Yu T, Weinberger K.  Simplifying graph convolutional networks.  In: International conference on machine learning.  2019, 6861–6871
  * [6] He X, Deng K, Wang X, Li Y, Zhang Y, Wang M.  Lightgcn: Simplifying and powering graph convolution network for recommendation.  In: Proceedings of the 43th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR.  2020
  * [7] Liu F, Cheng Z, Zhu L, Gao Z, Nie L.  Interest-aware message-passing gcn for recommendation.  In: Proceedings of the Web Conference 2021.  2021, 1296–1305
  * [8] Rendle S, Freudenthaler C, Gantner Z, Schmidt-Thieme L.  Bpr: Bayesian personalized ranking from implicit feedback.  In: Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence.  2009, 452–461
  * [9] Wei T, Feng F, Chen J, Wu Z, Yi J, He X.  Model-agnostic counterfactual reasoning for eliminating popularity bias in recommender system.  In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining.  2021, 1791–1800
  * [10] Zheng Y, Gao C, Li X, He X, Li Y, Jin D.  Disentangling user interest and conformity for recommendation with causal embedding.  In: Proceedings of the Web Conference 2021.  2021, 2980–2991
  * [11] Zhang Y, Feng F, He X, Wei T, Song C, Ling G, Zhang Y.  Causal intervention for leveraging popularity bias in recommendation.  In: Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval.  2021, 11–20
  * [12] Liang D, Charlin L, Blei D M.  Causal inference for recommendation.  In: Causation: Foundation to Application, Workshop at UAI.  2016
  * [13] Abdollahpouri H, Burke R, Mobasher B.  Managing popularity bias in recommender systems with personalized re-ranking.  In: The Thirty-second International Flairs Conference.  2019
  * [14] Mao K, Zhu J, Xiao X, Lu B, Wang Z, He X.  Ultragcn: ultra simplification of graph convolutional networks for recommendation.  In: Proceedings of the 30th ACM International Conference on Information & Knowledge Management.  2021, 1253–1262
  * [15] Kipf T N, Welling M.  Semi-supervised classification with graph convolutional networks.  In: International Conference on Learning Representations.  2017
  * [16] Johnson C.  Logistic matrix factorization for implicit feedback data.  In: Advances in Neural Information Processing Systems.  2014, 1–9
  * [17] Koh P W, Liang P.  Understanding black-box predictions via influence functions.  In: International Conference on Machine Learning.  2017, 1885–1894
  * [18] Xu K, Li C, Tian Y, Sonobe T, Kawarabayashi K i, Jegelka S.  Representation learning on graphs with jumping knowledge networks.  In: International Conference on Machine Learning.  2018, 5453–5462
  * [19] Tang X, Yao H, Sun Y, Wang Y, Tang J, Aggarwal C, Mitra P, Wang S.  Investigating and mitigating degree-related biases in graph convoltuional networks.  In: Proceedings of the 29th ACM International Conference on Information & Knowledge Management.  2020, 1435–1444
  * [20] Wu J, Wang X, Gao X, Chen J, Fu H, Qiu T, He X.  On the effectiveness of sampled softmax loss for item recommendation.  arXiv preprint arXiv:2201.02327, 2022
  * [21] Zhao Z, Chen J, Zhou S, He X, Cao X, Zhang F, Wu W.  Popularity bias is not always evil: Disentangling benign and harmful bias for recommendation.  IEEE Transactions on Knowledge & Data Engineering, 2022, (01): 1–13
  * [22] Zhao M, Deng Q, Wang K, Wu R, Tao J, Fan C, Chen L, Cui P.  Bilateral filtering graph convolutional network for multi-relational social recommendation in the power-law networks.  ACM Transactions on Information Systems (TOIS), 2021, 40(2): 1–24
  * [23] Gruson A, Chandar P, Charbuillet C, McInerney J, Hansen S, Tardieu D, Carterette B.  Offline evaluation to make decisions about playlistrecommendation algorithms.  In: Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining.  2019, 420–428
  * [24] Schnabel T, Swaminathan A, Singh A, Chandak N, Joachims T.  Recommendations as treatments: Debiasing learning and evaluation.  In: international conference on machine learning.  2016, 1670–1679
  * [25] Bonner S, Vasile F.  Causal embeddings for recommendation.  In: Proceedings of the 12th ACM conference on recommender systems.  2018, 104–112
  * [26] Liu Z, Nguyen T K, Fang Y.  Tail-gnn: Tail-node graph neural networks.  In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining.  2021, 1109–1119
  * [27] Kingma D P, Ba J.  Adam: A method for stochastic optimization.  In: International Conference on Learning Representations.  2015
  * [28] Zhu Z, He Y, Zhao X, Caverlee J.  Popularity bias in dynamic recommendation.  In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining.  2021, 2439–2449
  * [29] Xv G, Lin C, Li H, Su J, Ye W, Chen Y.  Neutralizing popularity bias in recommendation models.  In: Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval.  2022, 2623–2628
  * [30] Gupta P, Sharma A, Malhotra P, Vig L, Shroff G.  Causer: Causal session-based recommendations for handling popularity bias.  In: Proceedings of the 30th ACM International Conference on Information & Knowledge Management.  2021, 3048–3052
  * [31] Gupta S, Wang H, Lipton Z, Wang Y.  Correcting exposure bias for link recommendation.  In: International Conference on Machine Learning.  2021, 3953–3963
  * [32] Guo H, Yu J, Liu Q, Tang R, Zhang Y.  Pal: a position-bias aware learning framework for ctr prediction in live recommender systems.  In: Proceedings of the 13th ACM Conference on Recommender Systems.  2019, 452–456
  * [33] Dudík M, Langford J, Li L.  Doubly robust policy evaluation and learning.  In: Proceedings of the 28th International Conference on International Conference on Machine Learning.  2011, 1097–1104
  * [34] Krishnan A, Sharma A, Sankar A, Sundaram H.  An adversarial approach to improve long-tail performance in neural collaborative filtering.  In: Proceedings of the 27th ACM International Conference on Information and Knowledge Management.  2018, 1491–1494
  * [35] Chen J, Dong H, Qiu Y, He X, Xin X, Chen L, Lin G, Yang K.  Autodebias: Learning to debias for recommendation.  In: Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval.  2021, 21–30
  * [36] Zhang Y, Cheng D Z, Yao T, Yi X, Hong L, Chi E H.  A model of two tales: Dual transfer learning framework for improved long-tail item recommendation.  In: Proceedings of the Web Conference 2021.  2021, 2220–2231
  * [37] Abdollahpouri H, Burke R, Mobasher B.  Controlling popularity bias in learning-to-rank recommendation.  In: Proceedings of the eleventh ACM conference on recommender systems.  2017, 42–46
  * [38] Wang Y, Liang D, Charlin L, Blei D M.  The deconfounded recommender: A causal inference approach to recommendation.  CoRR, 2018, abs/1808.06581
  * [39] Sato M, Takemori S, Singh J, Ohkuma T.  Unbiased learning for the causal effect of recommendation.  In: Fourteenth ACM Conference on Recommender Systems.  2020, 378–387
  * [40] Qiu R, Wang S, Chen Z, Yin H, Huang Z.  Causalrec: Causal inference for visual debiasing in visually-aware recommendation.  In: Proceedings of the 29th ACM International Conference on Multimedia.  2021, 3844–3852
  * [41] Wang W, Feng F, He X, Wang X, Chua T S.  Deconfounded recommendation for alleviating bias amplification.  In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining.  2021, 1717–1725
  * [42] Dai H, Li H, Tian T, Huang X, Wang L, Zhu J, Song L.  Adversarial attack on graph structured data.  In: International conference on machine learning.  2018, 1115–1124
  * [43] Xu K, Hu W, Leskovec J, Jegelka S.  How powerful are graph neural networks?  In: International Conference on Learning Representations.  2018
  * [44] Li Q, Han Z, Wu X M.  Deeper insights into graph convolutional networks for semi-supervised learning.  In: Proceedings of the 32th AAAI Conference on Artificial Intelligence, AAAI.  2018
  * [45] Chen D, Lin Y, Li W, Li P, Zhou J, Sun X.  Measuring and relieving the over-smoothing problem for graph neural networks from the topological view.  In: Proceedings of the AAAI Conference on Artificial Intelligence.  2020, 3438–3445
  * [46] Chen M, Wei Z, Huang Z, Ding B, Li Y.  Simple and deep graph convolutional networks.  In: International Conference on Machine Learning.  2020, 1725–1735
  * [47] Liu M, Gao H, Ji S.  Towards deeper graph neural networks.  In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.  2020, 338–348
  * [48] Sun K, Lin Z, Zhu Z.  Multi-stage self-supervised learning for graph convolutional networks on graphs with few labeled nodes.  In: Proceedings of the AAAI Conference on Artificial Intelligence.  2020, 5892–5899