# In-processing User Constrained Dominant Sets for User-Oriented Fairness in
Recommender Systems

Zhongxuan Han  College of Computer Science and Technology, Zhejiang
UniversityHangzhou, China<EMAIL_ADDRESS>,  Chaochao Chen  College of
Computer Science and Technology, Zhejiang UniversityHangzhou, China
<EMAIL_ADDRESS>,  Xiaolin Zheng  College of Computer Science and
Technology, Zhejiang UniversityHangzhou, China<EMAIL_ADDRESS>,  Weiming
Liu  College of Computer Science and Technology, Zhejiang UniversityHangzhou,
China<EMAIL_ADDRESS>,  Jun Wang  OPPO Research InstituteShenzhen, China
<EMAIL_ADDRESS>,  Wenjie Cheng  College of Computer Science and
Technology, Zhejiang UniversityChina<EMAIL_ADDRESS>and  Yuyuan Li
College of Computer Science and Technology, Zhejiang UniversityHangzhou, China
<EMAIL_ADDRESS>
(2023; 2023)

###### Abstract.

Recommender systems are typically biased toward a small group of users,
leading to severe unfairness in recommendation performance, i.e., User-
Oriented Fairness (UOF) issue. The existing research on UOF is limited and
fails to deal with the root cause of the UOF issue: the learning process
between advantaged and disadvantaged users is unfair. To tackle this issue, we
propose an In-processing User Constrained Dominant Sets (In-UCDS) framework,
which is a general framework that can be applied to any backbone
recommendation model to achieve user-oriented fairness. We split In-UCDS into
two stages, i.e., the UCDS modeling stage and the in-processing training
stage. In the UCDS modeling stage, for each disadvantaged user, we extract a
constrained dominant set (a user cluster) containing some advantaged users
that are similar to it. In the in-processing training stage, we move the
representations of disadvantaged users closer to their corresponding cluster
by calculating a fairness loss. By combining the fairness loss with the
original backbone model loss, we address the UOF issue and maintain the
overall recommendation performance simultaneously. Comprehensive experiments
on three real-world datasets demonstrate that In-UCDS outperforms the state-
of-the-art methods, leading to a fairer model with better overall
recommendation performance.

Recommender System, Fairness, Dominant Sets

††copyright: acmcopyright††journalyear: 2023††doi:
XXXXXXX.XXXXXXX††conference: Make sure to enter the correct conference title
from your rights confirmation emai; June 03–05, 2018; Woodstock, NY††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06††journalyear: 2023††copyright:
acmlicensed††conference: Proceedings of the 31st ACM International Conference
on Multimedia; October 29-November 3, 2023; Ottawa, ON, Canada††booktitle:
Proceedings of the 31st ACM International Conference on Multimedia (MM ’23),
October 29-November 3, 2023, Ottawa, ON, Canada††price: 15.00††doi:
10.1145/3581783.3613831††isbn: 979-8-4007-0108-5/23/10††ccs: Information
systems Recommender systems

##  1\. Introduction

(a) Gradient Norm Distribution

(b) Performance Differences

Figure 1. (a) and (b) show the results obtained from experiments on Gowalla
(Liu et al., 2017) dataset. (a) visualizes the norm (i.e., $L_{2}-norm$ ) of
gradients coming from different users in a training epoch of NeuMF (He et al.,
2017). A bigger gradient norm indicates a bigger contribution to the updating
of the model. (b) shows the significant fairness issue between advantaged
users and disadvantaged users. Advantaged users can always get much better
recommendation results.

Nowadays, fairness has become an essential part of the machine learning
community (Dai et al., 2022; Mehrabi et al., 2021; Binns, 2018; Hutchinson and
Mitchell, 2019; Verma and Rubin, 2018), and is also widely studied in
Recommender Systems (RSs) (Deldjoo et al., 2022). RS is a complex field
involving frequent interactions between users and items (Burke, 2017; Han et
al., 2023; Liu et al., 2023; Zheng et al., 2022a). Fairness issues are common
on both the user’s side (Li et al., 2021; Rahmani et al., 2022) and the items’
side (Deldjoo et al., 2021a; Dash et al., 2021). In this paper, we consider
the fairness issues of the performance divergence regarding different user
groups.

Table 1. Percentage of users with different numbers of interactions ($n$). Dataset | $n\geq 30$ | $n\geq 50$ | $n\geq 80$ | $n\geq 100$
---|---|---|---|---
Epinion | 50.39% | 18.38% | 6.35% | 3.14%
MovieLens | 86.91% | 69.62% | 53.24% | 46.06%
Gowalla | 36.03% | 15.14% | 4.74% | 2.30%

The fairness issue about different groups of users is essential in RSs. RSs
are always biased toward a small group of users, leading to severe unfairness
in recommendation performance (Li et al., 2021; Rahmani et al., 2022; Hao et
al., 2021). We define these users with more satisfied recommendation results
as advantaged users and other users as disadvantaged users. According to (Li
et al., 2021; Rahmani et al., 2022), users’ different activity levels (e.g.,
interactions, total consumptions, and maximum consumption amount) will have
different impacts on the training process of the recommendation models, which
leads to unfair treatments. In this paper, we take users’ interaction numbers
as an example factor that leads to the fairness issue. According to Figure
1(a), advantaged users (mostly with more interactions) always contribute more
model updating when training a recommendation model. Thus, as shown in Figure
1(b), the model is biased towards or even dominated by those advantaged users,
leading to a significant fairness issue between advantaged and disadvantaged
users. What is more, the majority of users in a recommendation scenario are
always those disadvantaged users. As shown in Table 1, the percentage of users
who interact frequently (i.e., advantaged users) is relatively small. Thus the
above bias between advantaged and disadvantaged users will reduce overall user
satisfaction. Here, we call the unfair treatment between advantaged and
disadvantaged users as User-Oriented Fairness (UOF) (Li et al., 2021; Rahmani
et al., 2022) issue.

To date, the relevant work of UOF is quite limited. Basically, existing work
solving the fairness issue can be divided into pre-processing methods (solving
the bias in training data), in-processing methods (combing the model training
process with fairness consideration), and post-processing methods (directly
modifying the recommendation results to achieve fairness) (Dai et al., 2022).
Previous studies (Li et al., 2021; Rahmani et al., 2022) have examined the
issue of UOF and presented the User-oriented Fairness Re-ranking (UFR) method,
which serves as a post-processing solution for addressing UOF concerns. As
shown in Figure 2, UFR only modifies the recommendation result after model
training and fails to alleviate the training bias between advantaged and
disadvantaged users. Figure 1(a) illustrates that advantaged users always
contribute more to model training. Thus, the root cause of the UOF issue is
the bias between advantaged and disadvantaged users during model training,
which cannot be addressed by the post-processing UFR approach. The recent
S-DRO approach (Wen et al., 2022) proposed an in-processing solution to
mitigate loss for the disadvantaged user group. Nonetheless, achieving
substantial improvements is challenging due to the inherent limitations of
training data for this group. In essence, prior research cannot provide a
fundamental solution for addressing the UOF issue.

Figure 2. In-UCDS comparing with UFR. Recommender models always neglect more
disadvantaged users. In-UCDS let disadvantaged users learn from similar
advantaged users to enhance the learning process of disadvantaged users.

In this paper, we propose an In-processing User Constrained Dominant Sets (In-
UCDS) framework to give disadvantaged users a fairer learning result, to
better solve the UOF issue at the fundamental level. As shown in Figure 2,
different from UFR, by giving fair consideration during the model training, we
can solve the UOF issue in a deeper and more natural way, i.e., correcting the
bias between advantaged and disadvantaged users in the training process. The
fundamental concept behind In-UCDS is to identify a specific number of
advantaged users who share similarities with each disadvantaged user. This
approach enables disadvantaged users to learn from the well-trained advantaged
users during model training, rather than relying solely on their limited
training data, as UFR and S-DRO do. By doing so, the learning gaps between
these two user groups can be significantly reduced. To achieve this goal,
there are mainly two key problems: (1) how to find similar advantaged users
for each disadvantaged user; (2) how to design a method to let each
disadvantaged user learn from similar advantaged users.

In-UCDS consists of two stages, i.e., the UCDS modeling stage and the in-
processing training stage. Each stage is respectively devised for one of the
aforementioned problems. (1) In the UCDS modeling stage, we design a user
constrained dominant sets approach to find a set of similar advantaged users
for each disadvantaged user. Constrained dominant sets (Zemene and Pelillo,
2016; Alemu et al., 2019) can explore a cluster of the most similar nodes for
a particular node in a graph, which is naturally suitable for our task. Thus,
we treat the UCDS modeling stage as finding an advantaged user cluster with a
given disadvantaged user as a constraint. Specifically, for a given user-item
interaction graph, firstly, we build a user-user graph for each disadvantaged
user, which includes all advantaged users. To give an initial relationship
among these user nodes, we set the weight of each edge between two user nodes
as the number of items they both interact with. Thus a bigger weight indicates
a closer connection. Secondly, we treat each disadvantaged user as a target
user to find a constrained cluster in each graph so that we can find the most
similar advantaged user set for each disadvantaged user. (2) In the in-
processing training stage, we define a fairness loss that calculates the
representation difference between each disadvantaged user and users in its
constrained cluster. By minimizing the fairness loss, the representations of
each disadvantaged user will move closer to those of similar advantaged users,
leading to improved learning results during model training. Through the above
two stages, In-UCDS will narrow the representation gap between advantaged and
disadvantaged users. By incorporating the fairness loss with the loss of the
original backbone model, In-UCDS enhance fairness without sacrificing the
recommendation performance.

To evaluate the performance of our proposed In-UCDS framework, we conduct
extensive experiments on three real-world datasets based on four different
backbone recommendation models. Multiple evaluation metrics demonstrate that
In-UCDS outperforms the State-Of-The-Art (SOTA) models UFR and S-DRO in all
backbone recommendation models from various perspectives. In-UCDS can not only
mitigate fairness issues among users of different activity levels, but also
bring a much higher overall performance, proving that we can handle the UOF
issue more effectively.

We summarize our main contributions as follows: (1) We first propose an in-
processing framework In-UCDS to solve the fairness issues between advantaged
and disadvantaged users in RS. By doing so, we can alleviate the bias of RS
among users with different activity levels and bring better recommendation
performance. (2) We design a constrained dominant sets approach to find an
advantaged user cluster for each disadvantaged user to enhance its
representation during training. (3) We conduct extensive experiments on three
real-world datasets, demonstrating that In-UCDS outperforms the SOTA methods
from various perspectives.

##  2\. Related Work

###  2.1. Fairness in Machine Learning

Fairness has become one of the most important topics in machine learning.
According to (Mehrabi et al., 2021), fairness in a decision-making scenario
can be defined as the absence of any prejudice or favoritism toward an
individual or a group based on their inherent or acquired characteristics.
From different perspectives, research on fairness in machine learning can be
divided into different categories.

Regarding the groups affected by fairness issues, the research about fairness
can be divided into two aspects, i.e., group fairness and individual fairness
(Mehrabi et al., 2021; Dai et al., 2022). Group fairness aims to treat users
of different groups equally. Related work includes Equalized Odds (Hardt et
al., 2016), Equal Opportunity (Hardt et al., 2016), Conditional Statistical
Parity (Corbett-Davies et al., 2017), Demographic Parity (Kusner et al.,
2017), and Treatment Equality (Berk et al., 2021). Individual fairness aims to
give similar individuals similar recommendation results. Related work includes
Fairness Through Unawareness (Grgic-Hlaca et al., 2016), Fairness Through
Awareness (Dwork et al., 2012), and Counterfactual Fairness (Kusner et al.,
2017).

Regarding the fairness algorithms acting on the different stages of the
backbone model, the research about fairness can be divided into three aspects,
i.e., pre-processing methods, in-processing methods, and post-processing
methods (Mehrabi et al., 2021; Dai et al., 2022). Pre-processing methods try
to transform the training data so that the underlying discrimination can be
removed before training the model (d’Alessandro et al., 2017; Kang et al.,
2020). In-processing methods aim to add fairness consideration into the
training stage of the state-of-the-art model to remove discrimination during
the training (Dai and Wang, 2020; Bose and Hamilton, 2019). Post-processing
methods directly modify the recommendation results of a given model after
training (Li et al., 2021; Kang et al., 2020).

In this paper, we propose an in-processing framework to solve the rarely
studied user-oriented fairness problem, a kind of group fairness issue, in
recommender systems.

###  2.2. Fair Recommendation

A recommender system is a complex field with multiple stakeholders (Burke,
2017; Li et al., 2023; Zheng et al., 2022b; Chen et al., 2022). The fairness
issue is prevalent on providers’ side, items’ side, and users’ side,
introducing a trade-off among different roles.

For fairness on providers’ side. The length of time cooperating with different
providers (Gharahighehi et al., 2021; Ferraro, 2019), the correspondence
between providers and items (Boratto et al., 2021), and some characteristics
of providers (Shakespeare et al., 2020) are all factors that contribute to
fairness issues. For fairness on items’ side. Sensitive attributes (e.g.,
price, brand, and geographical area) (Deldjoo et al., 2021a; Burke et al.,
2018) and popularity (Wundervald, 2021; Sun et al., 2019)are key factors that
lead to fairness issues. For fairness on users’ side. The sensitive attributes
of users always affect the recommendation result, e.g., gender (Deldjoo et
al., 2021b; Melchiorre et al., 2021), age (Deldjoo et al., 2021b), and race
(Gorantla et al., 2021).

In this paper, we focus on the rarely studied fairness issue among users with
different activity levels, i.e., the UOF problem. Different from existing work
(Li et al., 2021; Rahmani et al., 2022; Wen et al., 2022), we propose an in-
processing method that enhances the training process of disadvantaged users to
narrow the learning gap between advantaged and disadvantaged user groups.

###  2.3. Dominant Sets

Dominant Sets (DS) (Pavan and Pelillo, 2006) is a kind of graph clustering
algorithm. Zemene et al. (Zemene and Pelillo, 2016) proposed a Constrained
Dominant Sets (CDS) approach to find a cluster restrict to contain several
given nodes in a graph. Recently, DS and CDS are widely used in computer
vision applications, proving their effectiveness in different kinds of
clustering jobs. Zemene et al. (Zemene et al., 2018) presented CDS with the
image segmentation task. Wang et al. (Wang et al., 2019b) combine the dominant
sets clustering process in a recursive manner to select representative images
from a collection of images for the 3D object recognition task. Alemu et al.
(Alemu et al., 2019) proposed an end-to-end constrained clustering scheme to
tackle the person re-identiﬁcation (reid) problem. Different from the above
methods which are widely utilized in computer vision tasks, to the best of our
knowledge, in this paper we are the first to introduce CDS to the user
clustering task in recommender systems.

##  3\. Preliminary

In this part, we first give the problem formulation and then generally
introduce dominant sets and constrained dominant sets as the technical
preparation for In-UCDS.

###  3.1. Problem Formulation

We use $\mathcal{U}$ and $\mathcal{I}$ to represent the user set and the item
set. We divide users into disadvantaged user group
$\mathcal{T}=\\{T_{1},T_{2},\dots,T_{M-1},T_{M}\\}$ and advantaged user group
$\mathcal{A}=\\{A_{1},A_{2},\dots,A_{N-1},A_{N}\\}$ based on their activity
levels, where M and N indicate the number of users in each group. According to
(Li et al., 2021; Rahmani et al., 2022), various behaviors (i.e.,
interactions, total consumption, and max trade price) can all reflect users’
activity levels. Since recommendation models are always trained directly based
on user-item interactions, without loss of generality, we choose users’
interaction numbers (users with more interactions are more likely to be
advantaged) to group users. In this paper, we aim to narrow the gap in the
recommendation performance between $\mathcal{T}$ and $\mathcal{A}$ to achieve
user-oriented fairness and maintain the overall recommendation performance
simultaneously.

User-oriented fairness is a kind of group fairness (Hardt et al., 2016; Dwork
et al., 2012). The principle of group fairness is to ensure groups of users
with different protected sensitive attributes should be comparably treated.
According to this idea, the definition of user-oriented fairness is defined as
follows (Li et al., 2021; Rahmani et al., 2022):

###### Definition 3.1 (User-Oriented Fairness (UOF)).

(1)
$\mathbb{E}[\mathcal{M(\mathcal{A})}]=\mathbb{E}[\mathcal{M(\mathcal{T})}].$

In the definition of UOF, $\mathcal{M}$ indicates a metric (e.g., NDCG and
F1-score) that can evaluate the recommendation performance. We use
$\mathcal{M}(u)$ to represent the recommendation performance of user $u$.

UOF aims to offer users with different activity levels the same recommendation
performance, which is usually impossible in real-world RS. Thus researchers
(Li et al., 2021; Rahmani et al., 2022) always calculate the difference in
average recommendation performance for different user groups to evaluate the
fairness of a model:

###### Definition 3.2 (The UOF matric ($\mathcal{M}_{UOF}$)).

(2)
$\mathcal{M}_{UOF}(\mathcal{T},\mathcal{A})=\bigg{|}\frac{1}{\lvert\mathcal{A}\rvert}\sum_{A_{i}\in\mathcal{A}}\mathcal{M}(A_{i})-\frac{1}{\lvert\mathcal{T}\rvert}\sum_{T_{i}\in\mathcal{T}}\mathcal{M}(T_{i})\bigg{|}.$

In this paper, we use the value of $\mathcal{M}_{UOF}$ to evaluate the
fairness of a recommendation model. A smaller $\mathcal{M}_{UOF}$ means a
fairer algorithm that tends to treat different activity groups of users
equally.

###  3.2. Technical Preparation

Dominant sets and constrained dominant sets are graph clustering methods.
Without loss of generality, we suppose a graph can be represented as
$G=(\mathcal{V},\mathcal{E},w)$, where $\mathcal{V}=\\{v1,v2,\dots,v_{z}\\}$
indicates the vertex set with $z$ represents the number of vertices.
$\mathcal{E}\in\mathcal{V}\times\mathcal{V}$ indicates the edge set.
$w:E\xrightarrow{}R_{+}^{*}$ is the positive weight function. The weight of an
edge reflects the similarities between the linked vertices. We represent the
graph $G$ with an weighted adjacency matrix $\mathbf{H}\in
R^{|\mathcal{V}|\times|\mathcal{V}|}$, which is non-negative and symmetric.
$\mathbf{H}_{ij}$ is defined as $w(i,j)$ if $(i,j)\in\mathcal{E}$, and $0$
otherwise. Note that there are no self-loops in $G$, thus all entries on the
main diagonal of $\mathbf{H}$ are zero.

Dominant Sets. Dominant sets is a graph clustering approach that generalizes
the concept of a maximal clique to construct clusters in an edge-weighted
graph. As proved in (Pavan and Pelillo, 2006), we can extract a node cluster
by solving the following linear-constrained quadratic optimization problem:

(3) $\begin{split}&\text{maximize}\ f(x)=x^{{}^{\prime}}\mathbf{H}x,\\\
&\text{subject to}\ x\in\bigtriangleup,\end{split}$

where $x^{{}^{\prime}}$ indicates the transpose of vector $x$.
$\bigtriangleup$ is the standard simplex of $R^{z}$:

(4) $\bigtriangleup=\\{x\in R^{z}:\sum_{i=1}^{z}x_{i}=1,\text{and}\ x_{i}\geq
0\ \text{for all}\ i=1,2,\dots,z\\}.$

According to $x$, we can extract how relevant a node is to the cluster. An
effective way to solve the optimization above is the so-called replicator
dynamics (Pavan and Pelillo, 2006), which is defined as follows:

(5)
$x_{i}^{t+1}=x_{i}^{t}\frac{(\mathbf{H}x^{t})_{i}}{(x^{t})^{{}^{\prime}}\mathbf{H}x^{t}}.$

Constrained Dominant Sets. Constrained dominant sets is an extension of
dominant sets. The key idea is that by choosing one or more nodes as
constraints, we can extract a cluster containing such user-selected elements.
The constrained dominant sets can also be defined as an optimization problem
as follows:

(6) $\begin{split}&\text{maximize}\
f_{\mathcal{S}}^{\alpha}(x)=x^{{}^{\prime}}(\mathbf{H}-\alpha\hat{\mathbf{I}}_{\mathcal{S}})x,\\\
&\text{subject to}\ x\in\bigtriangleup,\end{split}$

where $\mathcal{S}$ indicates the user-selected elements set.
$\hat{\mathbf{I}}_{\mathcal{S}}$ is the $z\times z$ diagonal matrix whose
element is set to $1$ in correspondence to the vertices contained in
$\mathcal{V}\backslash\mathcal{S}$ and $0$ otherwise. Note that if $\alpha=0$,
the above optimization problem will degenerate to dominant sets. Similar to
Equation (3), the optimization problem (6) can be solved as follows:

(7)
$x_{i}^{t+1}=x_{i}^{t}\frac{((\mathbf{H}-\alpha\hat{\mathbf{I}}_{\mathcal{S}})x^{t})_{i}}{(x^{t})^{{}^{\prime}}(\mathbf{H}-\alpha\hat{\mathbf{I}}_{\mathcal{S}})x^{t}}.$

##  4\. The Proposed Framework

In this part, we will first give an overview of the proposed In-UCDS
framework, then describe the detail of the UCDS modeling stage and the in-
processing training stage.

###  4.1. Overview

In this paper, we propose a novel In-processing User Constrained Dominant Sets
framework, namely In-UCDS, to better solve the user-oriented fairness issue in
recommendation tasks. In-UCDS is a general framework that can combine with any
recommendation models (i.e., backbone models) to achieve user-oriented
fairness. As shown in Figure 3, the overall framework is divided into two
stages, i.e., the UCDS modeling stage (shown in blue) and the in-processing
training stage (shown in green). (1) UCDS can be seen as a complementary model
for the backbone recommendation model. Before the training process begins, we
first extract a constrained cluster for each disadvantaged user preparing for
the following in-processing training stage. Note that the advantaged users in
each cluster are similar to the corresponding target disadvantaged user
identified by constrained dominant sets. (2) During the in-processing training
stage, we calculate the embedding difference between each disadvantaged user
and the users in its cluster and generate the fairness loss. We combine the
fairness loss with the backbone recommendation model loss to let disadvantaged
users learn from their similar advantaged users. Through the above two stages,
In-UCDS can solve the UOF issue during the model training.

In the following sections, we will introduce the detail of the UCDS modeling
stage and the in-processing training stage.

Figure 3. The overall framework. The input data and notations in this figure
are shown in orange. Note that the user-item interaction graph shown in the
graph is a toy example. There are many more disadvantaged users than
advantaged users in real-world recommender systems. The detailed modeling
stage of UCDS is shown in blue, where we take the disadvantaged user $T_{1}$
as an example to show how to find a constrained dominant set for it in deep
blue. In-processing training stage is shown in green. In each training epoch,
$L_{utility}$ and $L_{fairness}$ are combined to calculate the final loss.

###  4.2. UCDS Modeling Stage

The main idea of the UCDS modeling stage is to find a similar advantaged user
cluster for each disadvantaged user, papering for the following in-processing
training stage. Firstly, we will build a user-user graph containing all
advantaged users for each disadvantaged user to give a one-to-one similarity
relationship between each user pair. Then, we will construct an affinity
matrix for the graph to give the target disadvantaged user a constraint so
that we can extract a cluster containing the target user. Finally, we extract
a constrained dominant set for each disadvantaged user based on the affinity
matrix built above.

Build the User-User Graph. To explore advantaged user clusters for each
disadvantaged user, we need to build a user-user graph for each target
disadvantaged user first. According to the blue part of Figure 3, each user-
user graph contains one of the disadvantaged users and all advantaged users.
The graph is a complete graph with the weights of edges representing the
similarities between the linked nodes. To better find the correlations among
users, we set the weight between two user nodes as the number of the same
items they have interacted with. A higher weight means a higher similarity
since users who interact with the same items are likely to be similar.

Construct the Affinity Matrix. Given the advantaged user set $\mathcal{A}$ and
the disadvantaged user set $\mathcal{T}$, each time we will build a complete
user-user graph containing one of the users belonging to $\mathcal{T}$ (take
$T_{1}$ as an example) and all users in $\mathcal{A}$. We use $\mathbf{H}$ to
represent this graph’s adjacency matrix. To find a constrained cluster for
$T_{1}$, we build $\mathcal{U}=\\{T_{1}\\}$ as a constraint user set and
define the affinity matrix $\mathbf{B}$ as follows:

(8) $\mathbf{B}=(\mathbf{H}-\alpha\hat{\mathbf{I}}_{\mathcal{U}}).$

Note that the adjacency matrices for graphs built for each disadvantaged user
are always different. Thus, the value of $\alpha$ is not a constant. According
to (Zemene and Pelillo, 2016), by setting $\alpha$ as:

(9) $\alpha>\lambda_{max}(\mathbf{H}_{\mathcal{V}\backslash\mathcal{U}}),$

we can get a solution that necessarily contains elements of $\mathcal{U}$.
$\lambda_{max}$ indicates the largest eigenvalue of a matrix.

Extract the Constrained Cluster. After constructing the affinity matrix, we
can extract a constrained cluster for each disadvantaged user. To begin with,
we will introduce three steps to extract a constrained cluster. The three
steps give a clustering method from measuring the correlation of two users to
measuring the internal coherence of a user set. Then, we will give the
corresponding optimization problem for easy implementation.

Firstly, to extract a constrained dominant set, we need to measure the
similarity between two nodes in a graph. Given a user graph
$G=(\mathcal{V},\mathcal{E},w)$, we extract $\mathcal{S}\in\mathcal{V}$ as a
non-empty user set and define:

(10)
$\phi(\mathcal{S})(v_{i},v_{j})=w(i,j)-\frac{1}{|\mathcal{S}|}\sum_{k\in\mathcal{S}}w(i,k).$

Thus $\phi(\mathcal{S})$ measures the relative similarity between $v_{i}$ and
$v_{j}$, with respect to the average similarity between $v_{i}$ and its
neighbors in $\mathcal{S}$.

Secondly, to explore the importance of $v_{i}$ to $\mathcal{S}$, we define a
weight in a recursively way as follows:

(11) $w_{\mathcal{S}}(i)=\begin{cases}1,\ &\text{if}\ |\mathcal{S}|=1,\\\
\sum_{j\in\mathcal{S}\backslash\\{i\\}}\phi_{\mathcal{S}\backslash\\{i\\}}(j,i)w_{\mathcal{S}\backslash\\{i\\}}(j),\
&\text{otherwise.}\end{cases}$

A positive $w_{\mathcal{S}}(i)$ represents that adding $v_{i}$ into its
neighbors in $\mathcal{S}$ will increase the internal coherence of the set,
while a negative one will cause the overall coherence to be decreased.

Thirdly, to measure the overall internal coherence of $\mathcal{S}$, we define
a total weight as follows:

(12) $W(\mathcal{S})=\sum_{i\in\mathcal{S}}w_{\mathcal{S}}(i).$

If the obtained $\mathcal{S}$ is a dominant set (i.e., a good user cluster),
it should satisfy two conditions.

  * •

Condition 1. $w_{\mathcal{S}}(i)>0,$ for all $i\in\mathcal{S}$, representing a
dominant set is internally coherent.

  * •

Condition 2. $w_{\mathcal{S}\cup\\{i\\}}(i)<0,$ for all $i\notin\mathcal{S}$,
representing that the internal coherence will be destroyed by the addition of
any vertex from outside.

The above three steps give us a method to extract a constrained dominant set
$\mathcal{S}$ from graph $\mathcal{G}$. Initially we set
$\mathcal{S}=\mathcal{V}$ and then drop all vertices $v_{i}$ with
$w_{\mathcal{S}}(i)<0$ and save all vertices $v_{j}$ with
$w_{\mathcal{S}}(j)>0$. We give a toy example in Appendix A to describe how we
extract a dominant set in detail.

Now, we give a corresponding optimization problem to effectively implement the
above steps and extract a constrained dominant set. As proved in (Pavan and
Pelillo, 2006), for a target disadvantaged user $T_{1}$, the optimization
problem is defined as:

(13) $\begin{split}&\text{maximize}\
f_{\mathcal{S}}^{\alpha}(x)=x^{{}^{\prime}}\mathbf{B}x,\\\ &\text{subject to}\
x\in\bigtriangleup.\end{split}$

To solve the optimization problem above, we just need to solve the replicator
dynamics problem following Equation (7). Then we can extract the final
constraint dominant set containing $T_{1}$ according to the final value of
$x$.

During the UCDS modeling stage, we will generate dominant sets
$\mathcal{C}_{1},\mathcal{C}_{2},\dots,\mathcal{C}_{M}$ for users
$T_{1},T_{2},\dots,T_{M}$, preparing for the following in-processing training
stage.

###  4.3. In-Processing Training Stage

The basic idea of the in-processing training stage is to let disadvantaged
users learn from advantaged users in their corresponding clusters. Thus we can
narrow the gap in the quality of learning results between advantaged and
disadvantaged users. To achieve this goal, as shown in the green part of
Figure 3, in each training epoch, we calculate the fairness loss
$L_{fairness}$ that reflects the difference between each disadvantaged user
and its advantaged user cluster. Then we combine $L_{fairness}$ with the
backbone model loss $L_{utility}$. Thus we can solve the UOF problem and
maintain the recommendation performance simultaneously.

Calculate the Fairness Loss. During each training epoch, we use the user
embeddings $\mathbf{E}$ of the backbone model to calculate the fairness loss.
For a disadvantaged user $T_{i}\in\mathcal{T}$, we define the representation
difference between it and its constrained cluster as:

(14)
$D_{T_{i}}=\parallel\mathbf{E}_{T_{i}}-mean({\mathbf{E}_{A_{j}}|A_{j}\in\mathcal{C}_{i}})\parallel^{2},$

where $mean$ indicates an operation to calculate the element-wise average of a
set of vectors. However, the number of advantaged users in each constrained
cluster is always different. To give fair treatment to each disadvantaged user
and find the effect of the number of users in the user cluster, we further
define a hyperparameter $k$ to select the $k$ most important users from each
cluster (i.e., $\mathcal{C}_{i}^{k}$). Note that the importance of each
advantaged user is reflected by the value of the corresponding element in $x$
in the result of Equation (7). Then we define the final $D_{i}$ as:

(15)
$D_{T_{i}}=\parallel\mathbf{E}_{T_{i}}-mean({\mathbf{E}_{A_{j}}|A_{j}\in\mathcal{C}_{i}^{k}})\parallel^{2}.$

Finally, we calculate $L_{fairness}$ as the average of $D_{T_{i}}$ for all
disadvantaged users to improve the quality of learning results for all
disadvantaged users:

(16)
$L_{fairness}=\frac{1}{|\mathcal{T}|}\sum_{T_{i}\in\mathcal{T}}D_{T_{i}}.$

Putting Together. In each training epoch, we combine the fairness loss
$L_{fairness}$ with the backbone model loss $L_{utility}$ to simultaneously
solve the UOF problem and maintain the overall recommendation performance:

(17) $L=L_{utility}+\beta L_{fairness},$

where $L_{utility}$ represents the loss function of the backbone
recommendation model, constraining the model to achieve a higher
recommendation accuracy, and $\beta$ is a hyperparameter that controls the
importance of $L_{fairness}$.

##  5\. Experiments And Analysis

Table 2. The statistics of datasets

Dataset | Users | Items | Interactions | Sparsity | Domain
---|---|---|---|---|---
Epinion | 2,677 | 2,060 | 103,567 | 98.12% | Opinion
MovieLens | 5,738 | 3,627 | 760,814 | 96.34% | Movie
Gowalla | 33,699 | 123,587 | 1,011,694 | 99.98% | POI

Table 3. Experimental result

| Epinion | MovieLens | Gowalla
---|---|---|---
| Overall | Adv. | Disadv. | $\mathcal{M}_{UOF}$ | Overall | Adv. | Disadv. | $\mathcal{M}_{UOF}$ | Overall | Adv. | Disadv. | $\mathcal{M}_{UOF}$
PMF | NDCG | Original | 0.3589 | 0.3793 | 0.3578 | 0.0215 | 0.4370 | 0.5097* | 0.4332 | 0.0765 | 0.3756 | 0.4826* | 0.3700 | 0.1126
S-DRO | 0.3529 | 0.3652 | 0.3523 | 0.0129 | 0.4379 | 0.4838 | 0.4355 | 0.0483 | 0.3753 | 0.4711 | 0.3703 | 0.1008
UFR | 0.3678 | 0.3811 | 0.3671 | 0.0140 | 0.4360 | 0.4901 | 0.4332 | 0.0569 | 0.3747 | 0.4658 | 0.3700 | 0.0958
In-UCDS |  0.3804* |  0.3861* |  0.3801* |  0.0060* |  0.4638* | 0.4809 |  0.4629* |  0.0180* |  0.3946* | 0.4816 |  0.3901* |  0.0915*
F1 | Original | 0.1050 | 0.1202 | 0.1042 | 0.0160 | 0.1293 | 0.1432* | 0.1286 | 0.0146 | 0.1105 | 0.1240* | 0.1098 | 0.0142
S-DRO | 0.1039 | 0.1141 | 0.1034 | 0.0107 | 0.1296 | 0.1388 | 0.1291 | 0.0097 | 0.1104 | 0.1201 | 0.1099 | 0.0102
UFR | 0.1055 | 0.1131 | 0.1051 | 0.0080 | 0.1256 | 0.1293 | 0.1254 | 0.0039 | 0.1059 | 0.1104 | 0.1056 | 0.0048
In-UCDS | 0.1156* |  0.1213* |  0.1153* |  0.0060* |  0.1380* | 0.1418 |  0.1378* |  0.0040* |  0.1147* | 0.1165 |  0.1146* |  0.0019*
VAECF | NDCG | Original | 0.3637 | 0.4000 | 0.3618 | 0.0382 | 0.4404 | 0.5185* | 0.4363 | 0.0822 | 0.4019 | 0.5246 | 0.3768 | 0.1478
S-DRO | 0.3623 | 0.3831 | 0.3612 | 0.0219 | 0.4405 | 0.5055 | 0.4371 | 0.0684 | 0.3967 | 0.5029 | 0.3911 | 0.1118
UFR | 0.3562 | 0.3786 | 0.3550 | 0.0236 | 0.4631 | 0.5124 | 0.4605 | 0.0519 | 0.4005 | 0.4891 | 0.3959 | 0.0932
In-UCDS |  0.3927* |  0.4012* |  0.3923* |  0.0089* |  0.4783* | 0.4858 |  0.4779* |  0.0079* |  0.4845* |  0.5522* |  0.4856* |  0.0666*
F1 | Original | 0.1077 | 0.1219* | 0.1070 | 0.0149 | 0.1319 | 0.1476 | 0.1311 | 0.0165 | 0.1157 | 0.1364* | 0.1148 | 0.0216
S-DRO | 0.1068 | 0.1200 | 0.1061 | 0.0139 | 0.1316 | 0.1451 | 0.1309 | 0.0142 | 0.1159 | 0.1301 | 0.1152 | 0.0149
UFR | 0.1038 | 0.1085 | 0.1036 | 0.0049 | 0.1367 | 0.1386 | 0.1366 | 0.0020 | 0.1109 | 0.1136 | 0.1107 | 0.0029
In-UCDS |  0.1154* | 0.1166 |  0.1153* |  0.0013* |  0.1476* |  0.1505* |  0.1474* |  0.0031* |  0.1315* | 0.1353 |  0.1313* |  0.0040*
NeuMF | NDCG | Original | 0.3606 | 0.3800 | 0.3596 | 0.0204 | 0.4459 | 0.5352 | 0.4412 | 0.0940 | 0.3938 | 0.4717* | 0.3897 | 0.0820
S-DRO | 0.3598 | 0.3681 | 0.3594 | 0.0087 | 0.4519 | 0.5155 | 0.4486 | 0.0669 | 0.3932 | 0.4529 | 0.3901 | 0.0628
UFR | 0.3607 | 0.3729 | 0.3600 | 0.0129 | 0.4445 | 0.5068 | 0.4412 | 0.0656 | 0.3935 | 0.4610 | 0.3899 | 0.0711
In-UCDS |  0.4017* |  0.4093* |  0.4013* |  0.0080* |  0.5043* |  0.5385* |  0.5025* |  0.0369* |  0.3984* | 0.4288 |  0.3968* |  0.0320*
F1 | Original | 0.1080 | 0.1167 | 0.1075 | 0.0092 | 0.1336 | 0.1432* | 0.1331 | 0.0101 | 0.1153 | 0.1263 | 0.1148 | 0.0115
S-DRO | 0.1075 | 0.1188 | 0.1069 | 0.0119 | 0.1339 | 0.1401 | 0.1336 | 0.0065 | 0.1149 | 0.1251 | 0.1144 | 0.0107
UFR | 0.1038 | 0.1085 | 0.1036 | 0.0049 | 0.1302 | 0.1331 | 0.1301 | 0.0030 | 0.1158 | 0.1206 | 0.1156 | 0.0050
In-UCDS |  0.1194* |  0.1213* |  0.1193* |  0.0020* |  0.1416* |  0.1432* |  0.1417* |  0.0015* |  0.1269* |  0.1307* |  0.1267* |  0.0040*
NGCF | NDCG | Original | 0.4200 | 0.4638* | 0.4177 | 0.0461 | 0.5157 | 0.5504* | 0.5139 | 0.0365 | 0.4134 | 0.5179* | 0.4079 | 0.1100
S-DRO | 0.4200 | 0.4552 | 0.4181 | 0.0371 | 0.5147 | 0.5479 | 0.5130 | 0.0349 | 0.4108 | 0.5022 | 0.4060 | 0.0962
UFR | 0.4196 | 0.4462 | 0.4182 | 0.0280 | 0.5221 | 0.5374 | 0.5213 | 0.0161 | 0.4090 | 0.4862 | 0.4049 | 0.0813
In-UCDS |  0.4339* | 0.4418 |  0.4335* |  0.0083* |  0.5370* | 0.5422 |  0.5368* |  0.0054* |  0.4597* | 0.5086 |  0.4533* |  0.0553*
F1 | Original | 0.1203 | 0.1285* | 0.1199 | 0.0086 | 0.1433 | 0.1461 | 0.1432 | 0.0029 | 0.1171 | 0.1333* | 0.1171 | 0.0162
S-DRO | 0.1204 | 0.1263 | 0.1201 | 0.0062 | 0.1431 | 0.1396 | 0.1433 | 0.0037 | 0.1166 | 0.1308 | 0.1159 | 0.0130
UFR | 0.1160 | 0.1208 | 0.1158 | 0.0050 | 0.1420 | 0.1447 | 0.1419 | 0.0028 | 0.1125 | 0.1169 | 0.1122 | 0.0047
In-UCDS |  0.1254* | 0.1259 |  0.1254* |  0.0005* |  0.1469* |  0.1472* |  0.1469* |  0.0003* |  0.1284* | 0.1322 |  0.1282* |  0.0040*

  * *

Note that the italic text indicates the result of UFR. The bold text indicates
the result of our proposed In-UCDS framework. The best results are marked with
*.

To fully evaluate the proposed In-UCDS model. We conduct extensive experiments
on three real-world datasets to answer the following questions: Q1: How does
In-UCDS help the backbone recommendation model deal with the user-oriented
fairness issue and enhance the recommendation performance? Q2: Can In-UCDS
better deal with the fairness issue and improve the recommendation performance
than existing methods? Q3: Can In-UCDS narrow the gap in the quality of the
learned representations between advantaged and disadvantaged users? Q4: How do
important hyperparameters affect In-UCDS? Q5: How the UCDS approach
contributes to the performance improvement of our proposed framework?

###  5.1. Datasets and Experimental Settings

Dataset Description. We choose three real-world datasets Epinion (Massa and
Avesani, 2007), MovieLens (Harper and Konstan, 2015), and Gowalla (Liu et al.,
2017) from different domains to fully evaluate the performance of the In-UCDS
framework. The above three datasets have been popularly used (Rahmani et al.,
2022) to prove the performance of models that solve the user-oriented fairness
issue. We list the statistics of the datasets in Table 2. Overall, we select
these three datasets for three specific reasons in order to demonstrate the
scalability, efficiency, and effectiveness of In-UCDS. Firstly, the datasets
originate from three distinct domains, including Opinion, Movie, and Point of
Interest (POI). Secondly, the sparsity levels of these datasets vary, which is
an important factor that directly impacts the issue of user-oriented fairness,
since it determines the activity of users. Lastly, the three datasets differ
in terms of size.

Baseline and Backbone Models. We compare In-UCDS with the state-of-the-art
methods UFR (Li et al., 2021) and S-DRO (Wen et al., 2022). (1) UFR introduces
a post-processing re-rank method to directly modify the recommendation results
of a given backbone recommendation model. (2) S-DRO provides an in-processing
solution that simply minimizes the value of the loss function of disadvantaged
users during model training.

To fully evaluate the performance of In-UCDS, UFR, and S-DRO, we choose four
different backbone recommendation models, including a traditional matrix
factorization method (PMF), two deep-learning-based methods (VAECF, NeuMF),
and a graph neural network-based method (NGCF). (1) PMF (Mnih and
Salakhutdinov, 2007): Probabilistic Matrix Factorization algorithm adds the
Gaussian prior into the user and item latent factors distribution to enhance
the recommendation performance. (2) VAECF (Liang et al., 2018): Variational
Autoencoders for Collaborative Filtering proposes a generative model with
multinomial likelihood and uses bayesian inference for parameter estimation.
(3) NeuMF (He et al., 2017): Neural Collaborative Filtering introduces a deep
neural network with non-linear activation functions to train a user and item
matching function. (4) NGCF (Wang et al., 2019a): Neural Graph Collaborative
Filtering proposes a graph neural network-based framework to explore the high-
order correlations among users and items.

Evaluation Protocols and Parameter Settings. We utilize the widely-used Leave-
One-Out (LOO) (Chen et al., 2020; He et al., 2017; Hu et al., 2018) strategy
to split the train set, tune set, and test set. Following (Li et al., 2021;
Rahmani et al., 2022), we adopt Normalized Discounted Cumulative Gain (NDCG)
and F1-score to evaluate the performance of each model. A higher value means a
better recommendation performance for these two metrics and the predicted cut-
off is set as $topK=10$ (Li et al., 2021; Rahmani et al., 2022). Besides, we
utilize $\mathcal{M}_{UOF}$ to evaluate the recommendation performance gap
between advantaged users and disadvantaged users (Li et al., 2021; Rahmani et
al., 2022). A smaller $\mathcal{M}_{UOF}$ means a fairer recommendation
performance. We run each model 5 times in each dataset and save the average
performance. Due to space limitations, we introduce the detailed evaluation
protocols and parameter settings in Appendix B.1 and B.2.

###  5.2. Overall Comparison (Q1, Q2)

We conduct extensive experiments on three datasets based on four backbone
models. The results are reported in Table 3.

Answer to Q1. In all these three datasets, models combined with In-UCDS
framework significantly outperform the original models. Overall, by combining
the backbone model with our In-UCDS framework, we can not only solve the user-
oriented fairness issue but also improve the overall recommendation
performance.

Firstly, In-UCDS can solve the user-oriented fairness issue in the
recommendation system. The $\mathcal{M}_{UOF}$ of NDCG and F1 both
significantly drop by combining backbone models with In-UCDS framework,
proving In-UCDS can narrow the recommendation performance gap between
advantaged and disadvantaged users. We attribute the improvement mainly to the
embedding update strategy of In-UCDS. To give disadvantaged users a better
learning result in the training process, we extract similar advantaged users
for each disadvantaged user by constrained dominant sets approach. Then, in
the training process, we let each disadvantaged user’s embedding move closer
to the embeddings of advantaged users in the constrained cluster it
corresponds to. Thus disadvantaged users can learn from advantaged users, and
the recommendation gap between them is narrowed, leading to a drop in
$\mathcal{M}_{UOF}$.

Secondly, In-UCDS can improve the overall recommendation performance of the
backbone model. Disadvantaged users are typically the majority group in a
recommender system. Enhancing the recommendation results for these users can
greatly improve overall performance. Although the recommendation results for
advantaged users can be negatively impacted in some cases, the overall
performance is still improved since the percentage of these users is
relatively small. For instance, when applying the NGCF model combined with In-
UCDS to Epinion, the NDCG of advantaged users drops from 0.4638 to 0.4418,
while the overall NDCG improves from 0.42 to 0.4339.

Figure 4. The above results show the change in $L_{fairness}$ as the number of
training epochs increases. The result proves that In-UCDS can narrow the
learning gap between the advantaged user group and the disadvantaged user
group.

Answer to Q2. In-UCDS has a better performance in all three datasets compared
with UFR and S-DRO. The superiority of In-UCDS reflects in two aspects.

Firstly, a better solution to the user-oriented fairness issue. As shown in
Table 3, In-UCDS yields consistent best drop of $\mathcal{M}_{UOF}$ on all
datasets, proving In-UCDS can better mitigate the recommendation bias between
advantaged and disadvantaged users. Compared with the post-processing method
UFR, we not only consider directly offering a better recommendation
performance to disadvantaged users but also make an effort to narrow the bias
of the quality of learning results between advantaged and disadvantaged users.
So we can address the essential cause of the user-oriented fairness issue: the
learning process of advantaged and disadvantaged users is unfair. Thus, the
gap in the recommendation result between users of different activity levels
can be naturally narrowed since the quality of embeddings for disadvantaged
users is improved. In addition, when compared to S-DRO, which focuses on the
experience of the worst-case users, In-UCDS aims to enhance the recommendation
performance of the entire disadvantaged user group. This emphasis on group-
level improvement leads to a more substantial enhancement in fairness.

Secondly, a more significant improvement in overall recommendation
performance. UFR can only make a limited improvement in the overall
recommendation performance; sometimes, it even has a negative effect. The
reason is that UFR directly re-ranks the recommendation result to achieve
user-oriented fairness. However, without enhancing the backbone model’s
training process, the re-rank method’s result is unstable. The objective of
S-DRO is to minimize the loss for the worst-performing group. However, due to
the inherent limitations of the training data for disadvantaged users, it is
challenging to achieve significant improvement. In contrast to the
aforementioned methods, In-UCDS has the advantage of directly enhancing the
training process of disadvantaged users by leveraging the learning from
advantaged users. This approach is more intuitive and natural, ensuring a
positive impact on the model’s performance. Besides, the performance of
advantaged users is improved occasionally since they can also learn from
disadvantaged users who have stronger embeddings. For example, the NDCG of
advantaged users in Epinion for the PMF model improves from 0.3793 to 0.3861,
reflecting improved learning results.

Model Efficiency. Moreover, we compare the training time of the original
backbone models, UFR, S-DRO, and In-UCDS in Appendix B.3 to prove that In-UCDS
can keep the time cost at the same level as the original model.

###  5.3. The Change in $L_{fairness}$ (Q3)

In this part, we choose NeuMF as the example backbone model since it is widely
used to evaluate the user-oriented fairness model (Li et al., 2021; Rahmani et
al., 2022). To prove that In-UCDS can narrow the gap in the quality of learned
embeddings between disadvantaged users and advantaged users, we show the
change of $L_{fairness}$ with the number of training epochs increases in
Figure 4. Note that $L_{fairness}$ can directly reflect the difference between
embeddings of two user groups as Equation (16) shows. The experimental results
indicate that the model combined with In-UCDS can progressively narrow the
difference between disadvantaged and advantaged users, thus significantly
improving the learning process of the former by learning from similar
advantaged users.

###  5.4. Effect of Hyperparameters (Q4)

We show the effect of the most important hyperparameters $k$ (see Equation
(15)) and $\beta$ (see Equation (17)) of In-UCDS in Appendix B.4. Through the
experimental results, we set $k$ as 3 and $\beta$ as 0.00001.

###  5.5. Ablation Study (Q5)

Table 4. Ablation study

|  | Epinion | MovieLens | Gowalla
---|---|---|---|---
|  | Overall | $\mathcal{M}_{UOF}$ | Overall | $\mathcal{M}_{UOF}$ | Overall | $\mathcal{M}_{UOF}$
NDCG | In-Naive | 0.3783 | 0.0159 | 0.4799 | 0.0558 | 0.3932 | 0.0655
In-UCDS | 0.4017 | 0.0080 | 0.5043 | 0.0369 | 0.3984 | 0.0320
F1 | In-Naive | 0.1100 | 0.0051 | 0.1339 | 0.0047 | 0.1198 | 0.0088
In-UCDS | 0.1194 | 0.0020 | 0.1416 | 0.0015 | 0.1269 | 0.0040

In this section, we choose NeuMF as the example backbone model to perform
ablation experiments to demonstrate the efficiency of UCDS. We introduce a
simplified version called In-Naive for comparative analysis. Specifically, for
each disadvantaged user, we rank the advantaged users based on the number of
same interactions with him/her and extract the top-$k$ advantaged users. The
results presented in Table 4 demonstrate that In-UCDS consistently outperforms
In-Naive, which highlights the importance of incorporating UCDS into our
framework. This is because the number of similar interactions alone may not
accurately reflect the true similarity among users. A great deal of the same
interactions come from interactions with common items, which do not reflect
the characteristics and uniqueness of the user. In contrast to In-Naive, by
leveraging the graph structure, UCDS can uncover deep relevance and some high-
order correlations among users. The discovered user clusters are more
reflective of the uniqueness of each disadvantaged user, which helps prevent
disadvantaged users from overfitting to common items.

##  6\. Conclusion

In this paper, we focus on rarely studied User-Oriented Fairness (UOF) in
recommender systems, which aims to narrow the recommendation performance gap
between advantaged and disadvantaged users. We propose an In-processing User
Constrained Dominant Sets (In-UCDS) approach, which can be divided into two
stages, i.e., the UCDS modeling stage and the in-processing training stage.
Through the above two stages, we let disadvantaged users learn from their
similar advantaged users to narrow the recommendation performance gap between
these two groups of users. We conduct extensive experiments on three real-
world datasets based on four different backbone models. The experimental
results prove that In-UCDS can deal with the UOF issue better than the state-
of-the-art methods and provide a better overall recommendation performance.

###### Acknowledgements.

This work was supported in part by the National Natural Science Foundation of
China (No. 72192823), the “Ten Thousand Talents Program” of Zhejiang Province
for Leading Experts (No. 2021R52001).

## References

  * (1)
  * Alemu et al. (2019) Leulseged Tesfaye Alemu, Marcello Pelillo, and Mubarak Shah. 2019\.  Deep constrained dominant sets for person re-identification. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 9855–9864.
  * Berk et al. (2021) Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth. 2021.  Fairness in criminal justice risk assessments: The state of the art.  _Sociological Methods & Research_ 50, 1 (2021), 3–44.
  * Binns (2018) Reuben Binns. 2018\.  Fairness in machine learning: Lessons from political philosophy. In _Conference on Fairness, Accountability and Transparency_. PMLR, 149–159.
  * Boratto et al. (2021) Ludovico Boratto, Gianni Fenu, and Mirko Marras. 2021\.  Interplay between upsampling and regularization for provider fairness in recommender systems.  _User Modeling and User-Adapted Interaction_ 31, 3 (2021), 421–455.
  * Bose and Hamilton (2019) Avishek Bose and William Hamilton. 2019.  Compositional fairness constraints for graph embeddings. In _International Conference on Machine Learning_. PMLR, 715–724.
  * Burke (2017) Robin Burke. 2017\.  Multisided fairness for recommendation.  _arXiv preprint arXiv:1707.00093_ (2017).
  * Burke et al. (2018) Robin Burke, Nasim Sonboli, and Aldo Ordonez-Gauger. 2018\.  Balanced neighborhoods for multi-sided fairness in recommendation. In _Conference on fairness, accountability and transparency_. PMLR, 202–214.
  * Chen et al. (2022) Chaochao Chen, Huiwen Wu, Jiajie Su, Lingjuan Lyu, Xiaolin Zheng, and Li Wang. 2022\.  Differential private knowledge transfer for privacy-preserving cross-domain recommendation. In _Proceedings of the ACM Web Conference 2022_. 1455–1465.
  * Chen et al. (2020) Xu Chen, Ya Zhang, Ivor Tsang, Yuangang Pan, and Jingchao Su. 2020.  Towards Equivalent Transformation of User Preferences in Cross Domain Recommendation.  _arXiv preprint arXiv:2009.06884_ (2020).
  * Corbett-Davies et al. (2017) Sam Corbett-Davies, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. 2017.  Algorithmic decision making and the cost of fairness. In _Proceedings of the 23rd acm sigkdd international conference on knowledge discovery and data mining_. 797–806.
  * Dai and Wang (2020) Enyan Dai and Suhang Wang. 2020.  Learning Fair Graph Neural Networks with Limited and Private Sensitive Attribute Information.  _arXiv preprint arXiv:2009.01454_ (2020).
  * Dai et al. (2022) Enyan Dai, Tianxiang Zhao, Huaisheng Zhu, Junjie Xu, Zhimeng Guo, Hui Liu, Jiliang Tang, and Suhang Wang. 2022\.  A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability.  _arXiv preprint arXiv:2204.08570_ (2022).
  * d’Alessandro et al. (2017) Brian d’Alessandro, Cathy O’Neil, and Tom LaGatta. 2017\.  Conscientious classification: A data scientist’s guide to discrimination-aware classification.  _Big data_ 5, 2 (2017), 120–134.
  * Dash et al. (2021) Abhisek Dash, Abhijnan Chakraborty, Saptarshi Ghosh, Animesh Mukherjee, and Krishna P Gummadi. 2021\.  When the umpire is also a player: Bias in private label product recommendations on e-commerce marketplaces. In _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_. 873–884.
  * Deldjoo et al. (2021a) Yashar Deldjoo, Vito Walter Anelli, Hamed Zamani, Alejandro Bellogin, and Tommaso Di Noia. 2021a.  A flexible framework for evaluating user and item fairness in recommender systems.  _User Modeling and User-Adapted Interaction_ 31, 3 (2021), 457–511.
  * Deldjoo et al. (2021b) Yashar Deldjoo, Alejandro Bellogin, and Tommaso Di Noia. 2021b.  Explaining recommender systems fairness and accuracy through the lens of data characteristics.  _Information Processing & Management_ 58, 5 (2021), 102662\.
  * Deldjoo et al. (2022) Yashar Deldjoo, Dietmar Jannach, Alejandro Bellogin, Alessandro Difonzo, and Dario Zanzonelli. 2022\.  A Survey of Research on Fair Recommender Systems.  _arXiv preprint arXiv:2205.11127_ (2022).
  * Dwork et al. (2012) Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. 2012.  Fairness through awareness. In _Proceedings of the 3rd innovations in theoretical computer science conference_. 214–226.
  * Ferraro (2019) Andres Ferraro. 2019\.  Music cold-start and long-tail recommendation: bias in deep representations. In _Proceedings of the 13th ACM Conference on Recommender Systems_. 586–590.
  * Gharahighehi et al. (2021) Alireza Gharahighehi, Celine Vens, and Konstantinos Pliakos. 2021\.  Fair multi-stakeholder news recommender system with hypergraph ranking.  _Information Processing & Management_ 58, 5 (2021), 102663\.
  * Gorantla et al. (2021) Sruthi Gorantla, Amit Deshpande, and Anand Louis. 2021\.  On the problem of underranking in group-fair ranking. In _International Conference on Machine Learning_. PMLR, 3777–3787.
  * Grgic-Hlaca et al. (2016) Nina Grgic-Hlaca, Muhammad Bilal Zafar, Krishna P Gummadi, and Adrian Weller. 2016.  The case for process fairness in learning: Feature selection for fair decision making. In _NIPS symposium on machine learning and the law_ , Vol. 1. Barcelona, Spain, 11.
  * Han et al. (2023) Zhongxuan Han, Xiaolin Zheng, Chaochao Chen, Wenjie Cheng, and Yang Yao. 2023.  Intra and Inter Domain HyperGraph Convolutional Network for Cross-Domain Recommendation. In _Proceedings of the ACM Web Conference 2023_ (Austin, TX, USA) _(WWW ’23)_. Association for Computing Machinery, New York, NY, USA, 449–459.  https://doi.org/10.1145/3543507.3583402
  * Hao et al. (2021) Qianxiu Hao, Qianqian Xu, Zhiyong Yang, and Qingming Huang. 2021\.  Pareto optimality for fairness-constrained collaborative filtering. In _Proceedings of the 29th ACM International Conference on Multimedia_. 5619–5627.
  * Hardt et al. (2016) Moritz Hardt, Eric Price, and Nati Srebro. 2016.  Equality of opportunity in supervised learning.  _Advances in neural information processing systems_ 29 (2016).
  * Harper and Konstan (2015) F Maxwell Harper and Joseph A Konstan. 2015.  The movielens datasets: History and context.  _Acm transactions on interactive intelligent systems (tiis)_ 5, 4 (2015), 1–19.
  * He et al. (2017) Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. 2017\.  Neural collaborative filtering. In _Proceedings of the 26th international conference on world wide web_. 173–182.
  * Hu et al. (2018) Guangneng Hu, Yu Zhang, and Qiang Yang. 2018.  Conet: Collaborative cross networks for cross-domain recommendation. In _Proceedings of the 27th ACM international conference on information and knowledge management_. 667–676.
  * Hutchinson and Mitchell (2019) Ben Hutchinson and Margaret Mitchell. 2019.  50 years of test (un) fairness: Lessons for machine learning. In _Proceedings of the conference on fairness, accountability, and transparency_. 49–58.
  * Kang et al. (2020) Jian Kang, Jingrui He, Ross Maciejewski, and Hanghang Tong. 2020\.  Inform: Individual fairness on graph mining. In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 379–389.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ (2014).
  * Kusner et al. (2017) Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. 2017.  Counterfactual fairness.  _Advances in neural information processing systems_ 30 (2017).
  * Li et al. (2023) Yuyuan Li, Chaochao Chen, Xiaolin Zheng, Yizhao Zhang, Biao Gong, and Jun Wang. 2023\.  Selective and Collaborative Influence Function for Efficient Recommendation Unlearning.  _arXiv preprint arXiv:2304.10199_ (2023).
  * Li et al. (2021) Yunqi Li, Hanxiong Chen, Zuohui Fu, Yingqiang Ge, and Yongfeng Zhang. 2021.  User-oriented fairness in recommendation. In _Proceedings of the Web Conference 2021_. 624–632.
  * Liang et al. (2018) Dawen Liang, Rahul G Krishnan, Matthew D Hoffman, and Tony Jebara. 2018.  Variational autoencoders for collaborative filtering. In _Proceedings of the 2018 world wide web conference_. 689–698.
  * Liu et al. (2023) Weiming Liu, Xiaolin Zheng, Chaochao Chen, Jiajie Su, Xinting Liao, Mengling Hu, and Yanchao Tan. 2023.  Joint Internal Multi-Interest Exploration and External Domain Alignment for Cross Domain Sequential Recommendation. In _Proceedings of the ACM Web Conference 2023_ (Austin, TX, USA) _(WWW ’23)_. Association for Computing Machinery, New York, NY, USA, 383–394.  https://doi.org/10.1145/3543507.3583366
  * Liu et al. (2017) Yiding Liu, Tuan-Anh Nguyen Pham, Gao Cong, and Quan Yuan. 2017.  An experimental evaluation of point-of-interest recommendation in location-based social networks.  _Proceedings of the VLDB Endowment_ 10, 10 (2017), 1010–1021.
  * Massa and Avesani (2007) Paolo Massa and Paolo Avesani. 2007.  Trust-aware recommender systems. In _Proceedings of the 2007 ACM conference on Recommender systems_. 17–24.
  * Mehrabi et al. (2021) Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. 2021\.  A survey on bias and fairness in machine learning.  _ACM Computing Surveys (CSUR)_ 54, 6 (2021), 1–35.
  * Melchiorre et al. (2021) Alessandro B Melchiorre, Navid Rekabsaz, Emilia Parada-Cabaleiro, Stefan Brandl, Oleg Lesota, and Markus Schedl. 2021.  Investigating gender fairness of recommendation algorithms in the music domain.  _Information Processing & Management_ 58, 5 (2021), 102666\.
  * Mnih and Salakhutdinov (2007) Andriy Mnih and Russ R Salakhutdinov. 2007.  Probabilistic matrix factorization.  _Advances in neural information processing systems_ 20 (2007).
  * Pavan and Pelillo (2006) Massimiliano Pavan and Marcello Pelillo. 2006.  Dominant sets and pairwise clustering.  _IEEE transactions on pattern analysis and machine intelligence_ 29, 1 (2006), 167–172.
  * Rahmani et al. (2022) Hossein A Rahmani, Mohammadmehdi Naghiaei, Mahdi Dehghan, and Mohammad Aliannejadi. 2022\.  Experiments on Generalizability of User-Oriented Fairness in Recommender Systems.  _arXiv preprint arXiv:2205.08289_ (2022).
  * Shakespeare et al. (2020) Dougal Shakespeare, Lorenzo Porcaro, Emilia Gómez, and Carlos Castillo. 2020.  Exploring artist gender bias in music recommendation.  _arXiv preprint arXiv:2009.01715_ (2020).
  * Sun et al. (2019) Wenlong Sun, Sami Khenissi, Olfa Nasraoui, and Patrick Shafto. 2019.  Debiasing the human-recommender system feedback loop in collaborative filtering. In _Companion Proceedings of The 2019 World Wide Web Conference_. 645–651.
  * Verma and Rubin (2018) Sahil Verma and Julia Rubin. 2018.  Fairness definitions explained. In _2018 ieee/acm international workshop on software fairness (fairware)_. IEEE, 1–7.
  * Wang et al. (2019b) Chu Wang, Marcello Pelillo, and Kaleem Siddiqi. 2019b.  Dominant set clustering and pooling for multi-view 3d object recognition.  _arXiv preprint arXiv:1906.01592_ (2019).
  * Wang et al. (2019a) Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. 2019a.  Neural graph collaborative filtering. In _Proceedings of the 42nd international ACM SIGIR conference on Research and development in Information Retrieval_. 165–174.
  * Wen et al. (2022) Hongyi Wen, Xinyang Yi, Tiansheng Yao, Jiaxi Tang, Lichan Hong, and Ed H. Chi. 2022\.  Distributionally-Robust Recommendations for Improving Worst-Case User Experience. In _Proceedings of the ACM Web Conference 2022_ (Virtual Event, Lyon, France) _(WWW ’22)_. Association for Computing Machinery, New York, NY, USA, 3606–3610.  https://doi.org/10.1145/3485447.3512255
  * Wundervald (2021) Bruna Wundervald. 2021\.  Cluster-based quotas for fairness improvements in music recommendation systems.  _International Journal of Multimedia Information Retrieval_ 10, 1 (2021), 25–32.
  * Zemene and Pelillo (2016) Eyasu Zemene and Marcello Pelillo. 2016.  Interactive image segmentation using constrained dominant sets. In _European Conference on Computer Vision_. Springer, 278–294.
  * Zemene et al. (2018) Eyasu Zemene Zemene, Leulseged Tesfaye Alemu, and Marcello Pelillo. 2018.  Dominant sets for “constrained” image segmentation.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 41, 10 (2018), 2438–2451.
  * Zheng et al. (2022a) Xiaolin Zheng, Jiajie Su, Weiming Liu, and Chaochao Chen. 2022a.  DDGHM: Dual Dynamic Graph with Hybrid Metric Training for Cross-Domain Sequential Recommendation. In _Proceedings of the 30th ACM International Conference on Multimedia_ (Lisboa, Portugal) _(MM ’22)_. Association for Computing Machinery, New York, NY, USA, 471–481.  https://doi.org/10.1145/3503161.3548072
  * Zheng et al. (2022b) Xiaolin Zheng, Rui Wu, Zhongxuan Han, Chaochao Chen, Linxun Chen, and Bing Han. 2022b.  Heterogeneous Information Crossing on Graphs for Session-Based Recommender Systems.  _ACM Trans. Web_ (dec 2022).  https://doi.org/10.1145/3572407 Just Accepted.

(a) User Graph Example

(b) $w_{\\{T_{1},A_{1},A_{2},A_{3}\\}}(A_{2})<0$

(c) $w_{\\{T_{1},A_{1},A_{3}\\}}(A_{3})>0$

(d) $w_{\\{T_{1},A_{1},A_{3}\\}}(A_{1})>0$

(e) $w_{\\{T_{1},A_{1},A_{3}\\}}(T_{1})>0$

(f) Coherent Cluster $\mathcal{S}$

Figure 5. A toy example to show how to construct a user-constrained cluster.
The example graph is extracted from Figure 3 in the main paper and the
disadvantaged user $T_{1}$ is the target user. The weight of each edge is set
as the number of the same items that linked two users have both interacted
with in the user-item interaction graph in Figure 3 in the main paper.  Figure
6. The training time of four original backbone models, models combined with
UFR, models combined with S-DRO, and models combined with In-UCDS in three
datasets. Figure 7. The effect of hyperparameters $k$ and $\beta$. We show the
fluctuations of NDCG and $\mathcal{M}_{UOF}$-NDCG with the value of $k$ and
$\beta$.

##  Appendix A Example of constructing a user-constrained dominant set

We give a toy example in Figure 5 to describe how we extract a dominant set in
detail. Given a user-user graph in Figure 5(a), adding $A_{2}$ to the user
sets will reduce the coherence, as Figure 5(b) shows. Thus, $A_{2}$ is removed
from $\mathcal{S}$. In Figure 5(c), 5(d), 5(e), since all users of
$\\{T_{1},A_{1},A_{3}\\}$ have a positive effect on the coherence of the
cluster, they are kept in the final cluster in Figure 5(f).

##  Appendix B More Experimental Details

###  B.1. Evaluation Protocols

According to the experiment results of (Li et al., 2021; Rahmani et al.,
2022), the number of interactions gives the most intuitive indication of which
group (i.e., advantaged or disadvantaged users) a user belongs to. Thus,
following (Li et al., 2021; Rahmani et al., 2022), we rank users in each
dataset according to their number of interactions and extract the top 5% users
as advantaged users, leaving other users as disadvantaged users.

How to divide the experimental datasets is important for user-oriented
fairness. Existing work (Li et al., 2021; Rahmani et al., 2022) always splits
each dataset as the train set of 80%, the validation set of 10%, and the test
set of 10%. They select 100 negative items for each user in the validation and
test process to calculate the rank result combined with their positive
samples. We claim that the gap in the recommendation performance of advantaged
users and disadvantaged users is artificially magnified by doing so. The
reason is that by splitting the datasets as described above, the number of
positive items of advantaged users is much larger than that of disadvantaged
users. Then, with the same number (100) of negative items, the proportion of
the positive samples in the test sets of advantage users is much larger than
that of disadvantaged users. In this situation, advantaged users are more
likely to get satisfied recommendation results. This is contrary to the real-
life situation where the number of negative samples in a recommender system is
much greater than the number of positive samples. To overcome such bias, we
utilize the widely-used Leave-One-Out (LOO) (Chen et al., 2020; He et al.,
2017; Hu et al., 2018) strategy to do the dataset splitting proces. In detail,
each validation set and test set for a user contains one randomly selected
positive item and 99 negative items.

Following (Li et al., 2021; Rahmani et al., 2022), we adopt Normalized
Discounted Cumulative Gain (NDCG) and F1-score to evaluate the performance of
each model. A higher value means a better recommendation performance for these
two metrics and the predicted cut-off is set as $topK=10$ (Li et al., 2021;
Rahmani et al., 2022). Besides, we utilize $\mathcal{M}_{UOF}$ to evaluate the
recommendation performance gap between advantaged users and disadvantaged
users (Li et al., 2021; Rahmani et al., 2022). A smaller $\mathcal{M}_{UOF}$
means a fairer recommendation performance. We run each model 5 times in each
dataset and save the average performance.

###  B.2. Parameter Settings

For In-UCDS, we set the hyperparameter $k$ as 3 and $\beta$ as 0.00001
according to the experimental result of hyperparameters. (see section 5.4 in
the main paper). We tune the value of $\alpha$ following Equation (9) in the
main paper for each dataset. For UFR, we use the code provided by authors and
leave the parameters as their default values. For S-DRO, we implement it by
ourselves. As recommended in (Wen et al., 2022), we set the dimension of
hidden layers as (128, 64) and temperature $\tau$ as 0.07. For backbone
models, we set the size of user and item embeddings to 64 for all of them, and
adopt their parameters as suggested in their original paper. We apply Adam
(Kingma and Ba, 2014) as the optimizer and set the learning rate to 0.0001. To
ensure the convergence of all models, we set the number of training epochs to
200.

###  B.3. Model Efficiency

In-processing methods always require additional operations to achieve
fairness, leading to potential impacts on the training time of the backbone
model. Therefore, it is necessary to evaluate the efficiency of the In-UCDS
method. To demonstrate this, we showcase the training time of the original
backbone model, the model combined with UFR, the model combined with S-DRO,
and the model combined with In-UCDS in Figure 6. To ensure consistency, we fix
the number of training epochs as 200 and calculate the average training times
of 5 runs for each model.

Overall, the In-UCDS method requires the longest training time compared to the
other methods, but we can keep the time cost at the same level as the original
model. In-UCDS needs to extract an advantaged user cluster for each
disadvantaged user before training the model, which is more complex than the
re-ranking goal of UFR and the simple optimization process of S-DRO, causing
it to be the most time-consuming method. However, the time cost of the UCDS
modeling stage is independent of the complexity of the backbone model and is
only relevant to the size of the dataset. Therefore, the time cost of In-UCDS
becomes more insignificant as the complexity of the backbone model increases.
For example, the proportion of extra time-consuming in NGCF is much smaller
than that in PMF.

###  B.4. Effect of Hyperparameters

In this part, we show the effect of the most important hyperparameters $k$
(see Equation (15)) and $\beta$ (see Equation (17)) of In-UCDS. We take NeuMF
as the example backbone model to show the experimental results in Figure 7.

Effect of $k$. Through the experimental results, we can find that when the
value of $k$ is 3, the model achieves a high level of both recommendation
performance and fairness. Such a phenomenon shows that by exploring 3 similar
advantaged users for each disadvantaged user, In-UCDS can enhance the learning
result of disadvantaged users and maintains their characteristics
simultaneously. It should be noticed that the performance and fairness of the
model both decrease when the value of $k$ is too large. The reason is that if
a constrained cluster contains too many users, the unique characteristics of a
cluster and its corresponding disadvantaged user will be neutralized,
negatively affecting the training process.

Effect of $\beta$. Overall, In-UCDS can achieve the best recommendation
performance and fairness when $\beta=0.00001$. It should be noticed that the
model’s recommendation performance and fairness follow the same trend as the
change in $\beta$ since they are both affected by the quality of the learning
results of disadvantaged users.