#  GNNUERS: Fairness Explanation in GNNs for Recommendation via Counterfactual
Reasoning

Giacomo Medda  0000-0002-1300-1876 University of CagliariVia Ospedale,
72CagliariItaly<EMAIL_ADDRESS>,  Francesco Fabbri
0000-0002-9631-1799 SpotifyBarcelonaSpain<EMAIL_ADDRESS>,  Mirko
Marras  0000-0003-1989-6057 University of CagliariVia Ospedale,
72CagliariItaly<EMAIL_ADDRESS>,  Ludovico Boratto  0000-0002-6053-3015
University of CagliariVia Ospedale, 72CagliariItaly<EMAIL_ADDRESS>and  Gianni Fenu  0000-0003-1989-6057 University of CagliariVia Ospedale,
72CagliariItaly<EMAIL_ADDRESS>
(2018; 20 February 2007; 12 March 2009; 5 June 2009)

###### Abstract.

Nowadays, research into personalization has been focusing on explainability
and fairness. Several approaches proposed in recent works are able to explain
individual recommendations in a post-hoc manner or by explanation paths.
However, explainability techniques applied to unfairness in recommendation
have been limited to finding user/item features mostly related to biased
recommendations. In this paper, we devised a novel algorithm that leverages
counterfactuality methods to discover user unfairness explanations in the form
of user-item interactions. In our counterfactual framework, interactions are
represented as edges in a bipartite graph, with users and items as nodes. Our
bipartite graph explainer perturbs the topological structure to find an
altered version that minimizes the disparity in utility between the protected
and unprotected demographic groups. Experiments on four real-world graphs
coming from various domains showed that our method can systematically explain
user unfairness on three state-of-the-art GNN-based recommendation models.
Moreover, an empirical evaluation of the perturbed network uncovered relevant
patterns that justify the nature of the unfairness discovered by the generated
explanations. The source code and the preprocessed data sets are available at
https://github.com/jackmedda/RS-BGExplainer.

Recommender Systems, User Fairness, Explanation, Graph Neural Networks,
Counterfactual Reasoning

††copyright: acmcopyright††journalyear: 2018††doi: XXXXXXX.XXXXXXX††journal:
JACM††journalvolume: 37††journalnumber: 4††article: 111††publicationmonth:
8††ccs: Information systems Recommender systems††ccs: Computing methodologies
Causal reasoning and diagnostics††ccs: Social and professional topics
Gender††ccs: Social and professional topics Age††ccs: Theory of computation
Graph algorithms analysis

Figure 1. GNNUERS updates the perturbation vector such that the removed user-
item interactions from the graph lead the trained GNN to generate fairer
recommendations. The perturbation vector represents the counterfactual
explanation of the prior unfairness across demographic groups.

figure description

##  1\. Introduction

Novel recommender systems have become more and more effective and
sophisticated, excelling in satisfying the users’ preferences. The complexity
of novel systems functioning has also increased dramatically, laying the
groundwork for worrying questions (Ghazimatin et al., 2020). Such issue comes
in addition with the prominent importance of preserving properties that go
beyond recommendation effectiveness, such as trustworthiness (Wang et al.,
2022d), fairness (Wang et al., 2022b), and explainability (Zhang and Chen,
2020). However, all these issues are usually treated by the modern literature
as independent perspectives, mostly tackled one at a time. Taking as an
example algorithmic fairness (which is also the main case study in our work),
while it is of uttermost importance to provide the end users and the content
providers with equitable recommendations, it is also important for service
providers (e.g., an online platform) to understand why the model behind their
platform is unfair. Hence, tackling algorithmic fairness in an explainable way
is a central yet under-explored area. The few existing approaches that explain
unfairness in recommendation exploit user and item features to characterize
the disparities generated by a model (Ge et al., 2022; Deldjoo et al., 2021).
Though their methods successfully uncover the features related to the model
disparities, the generated explanations are limited to those selected
features. The latter might be challenging to obtain, given that most
recommendation models work with user-item interaction data.

Shifting the focus to other areas within explainable artificial intelligence,
various techniques have been employed to determine the relevant data entities
that can serve as explanations for diverse tasks. Counterfactual methods have
recently emerged as an effective way to explain the predictions produced by
models based on Graph neural networks (GNNs) (Hamilton et al., 2017; Kipf and
Welling, 2017; Veličković et al., 2017; Zhang et al., 2022). GNNs have proven
to be effective in modeling graph data in several domains, such as information
retrieval (Cui et al., 2022), recommender systems (He et al., 2020; Ying et
al., 2018), natural language processing (Yao et al., 2019) and user profiling
(Chen et al., 2021, 2019; Yan et al., 2021). Approaches driven by
counterfactual reasoning have also been used to guarantee algorithmic fairness
in GNN-based models by manipulating the topological structure (Agarwal et al.,
2021; Ma et al., 2022; Wang et al., 2022a) under various downstream tasks.
However, to the best of our knowledge, no approach was ever proposed to
explain unfairness in GNN-based recommender systems. Filling this research gap
goes beyond a simple application of counterfactual explanations methods for
GNNs, so as to uncover unfairness in recommender systems. Indeed, the original
methods to explain the predictions in GNN-based models are applied to classic
graphs (Lucic et al., 2022; Kang et al., 2021; Chen et al., 2022a; Yuan et
al., 2020), while recommender systems are characterized by a bipartite nature,
since they bridge the interactions between two types of entities (nodes),
i.e., users and items. This leads to efficiency issues, uncovered in detail in
Section 4.

In this work, we propose a shift of paradigm, by presenting a framework, named
GNNUERS (GNN-based Unfairness Explainer in Recommender Systems), which
perturbs the original bipartite graph in order to identify a set of user-item
interactions leading to user unfairness in GNN-based recommender systems.
Thanks to our approach, user unfairness can be uncovered by the selected
edges, i.e. the user-item interactions. Their removal from the original graph
can result in fairer recommendations for the end users, thus globally
explaining under which conditions a model generates disparities. Concretely,
our approach is guided by the demographic parity principle, which ensures that
all demographic groups receive the same recommendation utility,  where the
utility of a recommendation denotes its usefulness for (a group of) users.
Under this paradigm, we propose a perturbation mechanism driven by
counterfactual reasoning. The goal is to alter the users’ recommendation by
assuming a set of edges is missing from the graph. In other words, the
original bipartite graph is modified under the assumption that certain users
have not interacted with the items associated with the selected edges (in the
counterfactual world), while the graph includes such edges in reality (in the
actual world). The selection process of the user-item interactions is driven
by a loss function that combines two terms: i) minimizing the disparity in
recommendation utility across demographic groups, and ii) minimizing the
number of perturbed edges. Specifically, the user-item interactions are
cherry-picked such that a model using a graph missing such interactions is
able to generate fairer recommendations during the inference phase.

It should be noted that the loss function guiding the perturbation mechanism
has access to the ground truth labels of the subset of data used for
evaluation. It follows that our approach is able to monitor the recommendation
utility measured on the evaluation set for all the demographic groups. This
aspect is crucial to select the specific user-item interactions that lead to
the utility disparity across demographic groups in the recommendations
generated by GNN-based systems. By leveraging the ground truth labels of the
evaluation subset of data, GNNUERS distinguishes itself from other recently
proposed procedures in the recommendation literature. While these procedures
aim at modifying the recommendations to mitigate the unfairness issue, our
method focuses on explaining it instead. Therefore, GNNUERS can generate
explanations of user unfairness at the model level, also denoted as global
explanations, that can support system designers and service providers with
insights on how to improve the model fairness. This claim is supported by the
experiments in Section 5, which prove our framework is able to systematically
explain user unfairness, and also to uncover existing patterns that justify
why unfairness was characterized.

Our contributions can be summarized as follows:

  * •

Based on the research gaps existing in the current literature (Section 2), we
formulate the problem of explaining unfairness in GNN-based recommender
systems (Section 3) and propose a framework to generate global counterfactual
explanations of unfairness (Section 4);

  * •

We validate our proposal on three state-of-the-art models under four data
sets, measuring key utility metrics (Section 5), and finally discussing the
implications of our work for future advances in this research area (Section
6).

##  2\. Related Work

Our study has the primary goal of explaining unfairness in recommender systems
based on graph neural networks, which is a naturally multidisciplinary topic.
Therefore, we first contextualize our study with respect to prior work that
aimed at describing and explaining global issues related to the whole system
(e.g., unfairness, instability) in recommendation or on graphs, and not the
single model predictions. We then outline the efforts directed by researchers
towards explainability and unfairness mitigation in recommendation. Finally,
we provide an overview of existing methods adopting counterfactual
explanations in graph neural networks.

###  2.1. Beyond Predictions Explanation in Recommendation and on Graphs

First attempts to explain aspects beyond predictions in recommendation, e.g.,
unfairness, were made in (Deldjoo et al., 2021; Ge et al., 2022). (Deldjoo et
al., 2021) aimed at estimating the dependency between data characteristics and
unfairness, (Ge et al., 2022) sought to finding the minimal perturbation to
user and item features that can reduce exposure unfairness. It should be noted
that these explanations are therefore based on pre-computed features and their
importance with respect to the unfairness. Conversely, GNNUERS touches on
user-item interactions, i.e. the main source of personalization for
collaborative filtering models, including the GNN-based ones. While we fully
acknowledge the fact that these two aspects are complementary, user-item
interactions are generally present in any dataset adopted in a recommendation
scenario, whereas user and item features (e.g., those in (Ge et al., 2022))
might not always be extracted from the available data. Furthermore, the
explanatory framework used by (Deldjoo et al., 2021) requires a significant
amount of simulations, impractical for models with significant training times,
and the discovered patterns are informative only twith respect to the limited
collection of selected data characteristics.

Unfairness was also explained in GNNs trained for node classification tasks
(Dong et al., 2023). The authors devised an efficient method to quantify to
what extent fairness is impacted by the removal of a single node from the
training set without re-training the GNN. In a recommendation scenario, such
technique could label some users or items as harmful, describing unfairness as
their mere presence in the graph. Conversely, GNNUERS addresses unfairness in
the more complex recommendation task by detecting the users’ behavior (user-
item interactions) causing biased recommendations.

Other researchers have investigated to what extent recommender systems are
sensitive to minimal input data perturbations. For instance, the method
proposed in (Oh et al., 2022) aims to find the minimal perturbation that
causes the highest instability in the recommendations, by analyzing the effect
of a perturbation over the interaction graph in a black-box setting. However,
such method is tailored to decrease recommendation stability and might be used
to merely explain such criterion. Conversely, GNNUERS can be adopted to
optimize different objectives, including unfairness explanation and
recommendation instability. For the sake of scope, our study in this paper
explores the former and leaves the latter as a future work.

###  2.2. Explainability and User Fairness in Recommendation

Recent work in the recommendation field put much emphasis on improving
explainability in recommendation (Chen et al., 2022b) by leveraging post-hoc
techniques (Brunot et al., 2022; Zhong and Negre, 2022), explanation paths
(Balloccu et al., 2022; Zhang et al., 2023), counterfactual reasoning
(Ghazimatin et al., 2021; Chen et al., 2022a; Tan et al., 2021). Nonetheless,
these methods are specifically designed to generate instance-level
explanations (Yuan et al., 2023), that is each of them describes why an item
was recommended to a user. On the other hand, GNNUERS provides explanations at
the model level (Yuan et al., 2023) due to unfairness being a concern within
the scope of the entire recommender system, rather than within the scope of
individual user-item interactions.  In more detail, a model-level explanation
could benefit the system designers to understand how the system affects the
user experience and how it could be improved. However, a global explanation
would not be informative at the level of an individual user. Indeed, a user
could not contextualize the explanation with their personal experience, given
that a global explanation is not personalized as local ones. Our method is
also different from the mitigation methods of the unfairness caused by
instance-level explanations (Wang et al., 2022c), where the goal is to
guarantee the explanations are not biased, e.g., with respect to the generated
text.

Also the attention to issues of unfairness, from both the user and provider
perspectives, has been increasing in recommendation. Most works focusing on
the end users have modeled fairness at a group level, with a primary focus on
gender- and age-based demographic groups, and often accompanied unfairness
assessments with technical contributions for mitigating it (Boratto et al.,
2022; Ekstrand et al., 2022, 2018; Burke et al., 2018; Frisch et al., 2021; Li
et al., 2021a, b; Wu et al., 2021, 2022). These methods however do not
consider algorithmic ways to explain the causes behind the detected
disparities, letting mitigation methods attempt to reduce such disparities by
optimizing a certain loss function. Although these mitigation methods usually
led to a decrease in unfairness, the underlying causes of unfairness remain
unclear, consequently preventing researchers and service providers from
devising more conceptually informed mitigation methods. We particularly
observed that it is generally hard to link the mitigation method logic to the
underlying aspects causing unfairness in a given domain. Compared to these
prior works, GNNUERS not only aims to identify prior user interactions that
potentially led the model to provide unfair recommendations, but also
investigates the structural characteristics of the perturbed interactions. It
follows that GNNUERS makes it possible to derive conceptual insights that
support a better understanding of the unfairness phenomenon, working to the
advantage of system designers and service providers.

###  2.3.  Explainability in GNNs

GNNs can be directly applied to graphs to provide an easy way to do node-
level, edge-level, and graph-level prediction tasks. A notable advantage of
GNNs is that they can capture the dependence of graphs via message passing
between the graph nodes. Unlike standard neural networks, GNNs retain a state
representing information from their neighbourhood with arbitrary depth.

Yet, the methods addressing explainability about unfairness in GNNs are
limited (Dong et al., 2023) (described in Section 2.1). On the other hand,
several prior works have proposed to mitigate unfairness in GNNs (Agarwal et
al., 2021; Ma et al., 2022; Wang et al., 2022a), specifically by manipulating
the graph topological structure. Such methods have never been investigated on
bipartite graphs adopted for recommendation, and their operationalization of
unfairness and their mitigation operation could not be extended to explain the
issue, as required in our case.  Meanwhile, model-level explainability methods
for GNNs (Yuan et al., 2020; Huang et al., 2023) have been limited to generate
graphs that explain how the models globally behave in graph classification
tasks. However, the classified graphs are much smaller than user-item
interaction networks adopted in recommendation, and the graph generation
process iteratively applies a single modification. This operation prevents the
existing methods from scaling to datasets commonly used in recommendation.

A relevant amount of works were devoted to leveraging counterfactual
techniques to explain GNN predictions (Lucic et al., 2022; Kang et al., 2021;
Chen et al., 2022a; Huang et al., 2023). These techniques aim to find the
minimal perturbation to the input (graph) data that makes the GNN change its
predictions. The goal of such approaches is related to adversarial attacks,
but the latter aim at degrading the model performance instead of generating
informative explanations (Lucic et al., 2022). Nevertheless, none of them
focused on explaining fairness, but merely addressed explanations of
individual predictions. Differently from them, GNNUERS leverages
counterfactual techniques to find the minimal perturbation to the input
(graph) data such that the unfairness of the recommendations produced by the
GNN-based model is reduced. Our method therefore differs from other existing
solutions from several perspectives. First, we target GNNs applied to
bipartite graphs, instead of focusing on more general graphs typically
considered in the machine learning field. Second, we adopted a different
notion of counterfactuality, which does not only require that the prediction
changes, but also that predictions lead to a certain property. Third, we go
beyond the mere creation of the counterfactual explanations at the instance
level, and investigate structural properties of the perturbed data at the
model level.

##  3\. Problem Formulation

Our paper aims to explain user unfairness in recommendations generated by
graph neural network models. Therefore, we first describe the recommendation
scenario from a graph perspective. We then formulate the target task, namely
user unfairness explanation. Finally, we introduce the definition of fairness
adopted in our study.

###  3.1. Recommendation Task

In recommendation, the goal of the preference model is typically predicting
whether or to what extent an (unseen) item would potentially be of interest
for a user. In a common scenario, the model uses past interactions between two
main entities, namely users $U$ and items $I$, to learn preference patterns.
Each user $u\in U$ is assumed to have interacted with a certain item $i\in I$
in case they rated, liked, or clicked on such item, depending on the
applicative scenario. The set of items $I_{u}$ a user interacted with is
referred to as the $u$’s history.

Graphs are structures that represent a set of entities (nodes) and their
relations (edges). GNNs operate on graphs to produce representations that can
be used in downstream tasks. In our case, user-item interactions can be
represented by means of an undirected bipartite graph $\mathcal{G}=(U,I,E)$,
where $E$ is the set of edges representing the interactions and $U\cup I$,
with $n=|U|+|I|$, is the set of nodes. No edge exists between nodes of the
same type, i.e. $E=\\{(u,i)\ |\;u\in U,i\in I\\}$. The recommendation problem
can be then solved by leveraging GNNs on a linking prediction task to predict
potentially interesting links between users $U$ and items $I$ in the bipartite
graph $\mathcal{G}$.

Let $f(A;W)\rightarrow\hat{R}$ be any GNN, where $A$ is an $n\times n$
adjacency matrix representing $\mathcal{G}$, $W$ is the learned weight matrix
of $f$, and $\hat{R}$ is a $|U|\times|I|$ user-item relevance matrix, with
$\hat{R}_{u,i}$ being the linking probability between user $u$ and item $i$.
In other words, $A$ is the input of $f$, and $f$ is parameterized by $W$. $f$
predicts the user-item relevance matrix $\hat{R}$ by combining the normalized
adjacency matrix $L=D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$, where
$D_{j,j}=\sum_{k}{A_{j,k}}$ are entries in the degree matrix $D$, and $W$ is
learnt according to the GNN implementation. Given $\hat{R}$ and a user $u$,
items in $I$ are sorted based on their decreasing relevance in $\hat{R}_{u}$,
and the top-$k$ items are recommended to user $u$. We refer to the list of
items recommended to user $u$ as $Q_{u}$ and to the set of all recommended
lists as $Q$.

###  3.2. Unfairness Explanation Task

An unfair algorithm is one whose decisions are skewed toward a particular
group of people (Mehrabi et al., 2021). In light of this, it follows that an
unfairness explanation process cannot be conducted for a single individual.
Hence, we aim to explain why a recommender system is unfair at the model level
(Yuan et al., 2023) to support designers and service providers with insights
on how to improve the model fairness. To do so, we decided to adopt
counterfactual reasoning techniques (Lucic et al., 2022; Kang et al., 2021).
In our context, we assume to model counterfactual explanations according to
the users’ history  and provide a formal definition.

######  Definition 0 (Counterfactual Explanation of Recommendation Unfairness
in GNNs).

Let $E$ be a set of user-item interactions represented as edges in an
adjacency matrix $A$. Let $f$ be a trained GNN. Let $\Phi(\cdot)\in[0,1]$ be a
fairness metric adopted on a set of recommendations, where $\Phi(f(A))=0$
denotes perfect fairness. Let the perturbation (e.g., deletion) of the edges
in $\tilde{E}\subseteq E$ result in the adjacency matrix $\tilde{A}$.
$\tilde{E}$ is a counterfactual explanation of the recommendation unfairness
if $\Phi(f(\tilde{A}))<\Phi(f(A))$.

Definition 3.1 introduces how to identify one of the possible sources of the
unfairness as a subset of edges included in $A$. The presence of the subset of
edges $\tilde{E}$ in $A$ leads a GNN to generate biased recommendations that
advantage a specific group of users. Hence, perturbing $\tilde{E}$ could make
the system fairer, which follows the logic of existing explainability
techniques for provider fairness (Ge et al., 2022).

However, Definition 3.1 does not address the amount of perturbed edges and the
extent to which the unfairness level was reduced. It follows that several
explanations could be identified as long as the recommendations generated by
the GNN with the perturbed graph are fairer, even if such explanations are not
informative enough of the recommendation unfairness. Therefore, we formulate
the problem of identifying an Optimal Counterfactual Explanation.

######  Problem 1 (Identification of an Optimal Counterfactual Explanation of
Recommendation Unfairness in GNNs).

Let $f$ be a GNN, $E$ be a set of edges represented in an adjacency matrix
$A$, and $\Phi(f(A))$ be the fairness level of the recommendations generated
by $f$ based on $A$. Our goal is to identify a counterfactual explanation
$\tilde{E}$ (with corresponding adjacency matrix $\tilde{A}$) that leads to
perfect fairness, i.e. $\Phi(f(\tilde{A}))=0$, by means of the lowest number
of perturbations, i.e. $|\tilde{E}|$ is minimal.

It follows that Problem 1 could be solved by identifying the minimal subset of
user-item interactions that make the recommendations perfectly fair when such
interactions are removed from the adjacency matrix. We denote such
interactions as an Optimal Counterfactual Explanation, which is formally
defined as follows:

######  Definition 0 (Optimal Counterfactual Explanation of Recommendation
Unfairness in GNNs).

Let $\tilde{\mathcal{E}}=\\{\tilde{E}_{1},\tilde{E}_{2},\dots\\}$ be a set of
counterfactual explanations of the unfairness estimated on the recommendations
generated by a GNN $f$. According to Definition 3.1,
$\Phi(f(\tilde{A}))<\Phi(f(A))$ is true
$\forall\tilde{E}\in\tilde{\mathcal{E}}$ used to perturb $A$ and generate
$\tilde{A}$. We define a counterfactual explanation $\tilde{E}_{j}$ as optimal
if:

$\displaystyle 1.$ $\displaystyle\Phi(f(\tilde{A}_{j}))=0$ $\displaystyle 2.$
$\displaystyle|\tilde{E}_{j}|\leq|\tilde{E}_{k}|,\forall
E_{k}\in\tilde{\mathcal{E}},j\neq k$ $\displaystyle 3.$
$\displaystyle\text{utility}(f(\tilde{A}_{j}))\approx\text{utility}(f(A))$

where $\tilde{A}_{j}$ is the adjacency matrix generated by perturbing
$\tilde{E}_{j}$ on $A$, $\text{utility}(\cdot)$ is a recommendation utility
metric.

Definition 3.2 adds a requirement to the previous discussion, stating that the
recommendation utility before and after the perturbation should be preserved
as much as possible. This requirement is essential to avoid scenarios that do
not reflect a proper unfairness explanation. For instance, if no user received
at least a relevant item, the recommendations would not exhibit any disparate
treatment, but the system would not be useful in practice.

We then remark our goal to identify an optimal counterfactual explanation of
recommendation unfairness, but underline that Definition 3.2 does not claim
such explanation is granted to exist. Therefore, our goal is approximated to
find a counterfactual explanation that is as close as possible to the optimal
one. This involves perturbing the minimal subset of edges that result in an
unfairness level as close as possible to zero and an utility level as close as
possible to the original one.

Algorithmic unfairness has been operationalized through numerous notions,
often dependent on the context and the application (Singh and Joachims, 2018).
It follows that there is no consensus in the recommender systems community on
a gold standard definition to apply. Motivated by its increasingly recognized
importance in prior work in top-$k$ recommendation (Boratto et al., 2022; Wu
et al., 2022), we decided to model fairness according to the notion of
demographic parity. Nonetheless, our formulation and method is flexible to
accommodate other notions of fairness. In the context of recommendations, a
model meets demographic parity when the recommendation utility estimates
across demographic groups are not systematically different.  Under this
demographic parity notion of fairness, our goal is to generate recommendation
lists with closer utility estimates across demographic groups than the
original recommendations $Q$. We pursue such goal by generating a perturbed
adjacency matrix $\tilde{A}$ that results in fairer recommendations when a
trained GNN uses $\tilde{A}$ instead of $A$ during inference. We also
constrain the number of perturbed edges with respect to the original adjacency
matrix $A$. Formally, we seek to minimize the following objective function:

(1)
$\mathcal{L}(A,\tilde{A})=\mathcal{L}_{fair}(A,f(\tilde{A};W))+\mathcal{L}_{dist}(A,\tilde{A})\vspace{2mm}$

where $\mathcal{L}_{fair}$ is the term monitoring fairness, operationalized
according to the notion of demographic parity, $\mathcal{L}_{dist}$ is the
term controlling the distance between the perturbed adjacency matrix
$\tilde{A}$ and the original one $A$. In the next section, we describe the way
$\tilde{A}$ is generated and how the objective function is translated into a
loss function to be minimized with our approach.

##  4\. Methodology: GNNUERS

In this section we present GNNUERS, a method able to explain unfairness in
graph-based recommenders, solving the problem introduced in Section 3.2. We
introduce the method by its main components: $(a)$ first, the perturbation
mechanism of the bipartite graph, which allows to alter the interactions
between users and items in a differentiable way, and $(b)$ the two-term loss
function that guide the selection of the edges to be perturbed.

###  4.1. Bipartite Graph Perturbation

Our graph perturbation approach is inspired by previous work on GNNs
explainability for binary classification on plain graphs (Lucic et al., 2022).
However, since GNNUERS aims to perturb a bipartite graph generated for
recommender systems, it presents several differences. In (Lucic et al., 2022),
a perturbation matrix $P$ is populated to then generate the perturbed matrix
$\tilde{A}=P\odot A$111$\odot$ denotes the Hadamard product.. Optimizing for
$P$ can eventually include indices for zero entries in $A$. While for plain
graphs this method results to be efficient, for bipartite graphs it can be
memory inefficient, mainly because it requires to store a perturbation value
also for the user-user and item-item links222 Given our focus on explaining
unfairness by means of user behavior, we decided not to consider user-user and
item-item links in GNNUERS. We leave this interesting perspective to its
future extensions., not present in bipartite graph per definitionem. To
overcome these limitations, the perturbation in GNNUERS is  driven by a vector
$p\in\mathbb{N}^{|\tilde{E}|}$, where $\tilde{E}\subseteq E$ is the subset of
edges selected for perturbation (as in Definition 3.1-3.2). In our
experiments, we consider all the edges of the training graph in the GNNUERS
perturbation process, i.e. $\tilde{E}$ includes all the pairs $(u,i)$ that
correspond to non-zero entries of $A$. Our method is memory efficient,
especially under sparse graphs, since it needs to store perturbation values
only for the non-zero entries of $A$.

Given our unfairness explanation task, we derive a perturbed matrix
$\tilde{A}$, resulting in fairer recommendations when a trained GNN uses
$\tilde{A}$ instead of $A$ during the inference phase.  The mechanism that
controls how the vector $p$ perturbs the edges included in $\tilde{E}$ is
determined by the relation $H=\\{(p_{j},\tilde{e}_{j})\;|\;1\leq
j\leq|\tilde{E}|,\tilde{e}_{j}\in\tilde{E}\\}$. In other words, an edge
$\tilde{e}_{j}$, i.e. a distinct non-zero entry $A_{u,i}$, is associated with
a specific entry $p_{j}$. An entry $p_{j}=0$ denotes the edge $A_{u,i}$ (i.e.
$\tilde{e}_{j}$) is deleted in the perturbed adjacency matrix, i.e.
$\tilde{A}_{u,i}=0$. Thus, the perturbed matrix $\tilde{A}$ is populated as
follows:

(2)
$\displaystyle\tilde{A}_{u,i}=\begin{cases}{p}_{j}&if\>(p_{j},\tilde{e}_{j})\in
H,\tilde{e}_{j}=(u,i)\\\ A_{u,i}&otherwise\end{cases}$

It should be noted that the way the relation $H$ is defined does not affect
the perturbation process. In particular, the perturbation is invariant of the
order defined for the edges in $\tilde{E}$ used to construct $H$.

Following (Lucic et al., 2022; Srinivas et al., 2017), we generate $p$ through
an optimization process that leverages a real valued vector $\hat{p}$. Once
optimized, we apply a sigmoid transformation. Then, entries are binarized such
that values  greater or equal than $0.5$ become 1, while values  smaller than
$0.5$ become 0, obtaining eventually $p$. The initialization of $\hat{p}$
should guarantee $\tilde{A}=A$, i.e. a real-valued $\alpha$ is selected to
initialize $\hat{p}$, such that $p_{j}=1,\forall j\in[0,B)$. In all the
experiments in Section 5 we set $\alpha=0$, leaving the analysis of other
initialization values as a future work.

###  4.2. Perturbed Graph Generation

Based on the protocol described above, GNNUERS modifies the adjacency matrix
edges by means of the perturbation vector $p$. The decision process of which
edges will be deleted is performed by the counterfactual model $\tilde{f}$.
$\tilde{f}(A,W;\hat{p})\rightarrow\tilde{R}$ extends the GNN-based recommender
system $f$ using $\hat{p}$ as parameter and the frozen weights $W$ learnt by
$f$ as additional input.  $\tilde{f}$ predicts the altered relevance matrix
$\tilde{R}$ similarly to $f$. In detail, $\tilde{f}$ combines the normalized
version of the perturbed adjacency matrix
$\tilde{L}=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$, where
$\tilde{D}_{u,u}=\sum_{i}{\tilde{A}_{u,i}}$, with $W$ according to the
implementation of the original model $f$. Therefore, $\tilde{f}$ learns only
$\hat{p}$, while the weights $W$, already optimized by $f$ to maximize the
recommendation utility, remain constant.

As explained in Section 4.1, $p$ is generated from $\hat{p}$, whose values get
updated during the learning process. At different steps of the latter, the
values of $\hat{p}$ could oscillate close to the threshold that determines if
$p$ will be 0 or 1 at the respective indices. Considering aspects such as
floating-point errors or dropout layers, the oscillation could negatively
affect the update of $\hat{p}$, due to previously perturbed edges being
restored, or vice versa. To counter this phenomenon, the perturbation
algorithm is constrained by the usage of a policy that prevents a deleted edge
from being restored, such that the number of perturbed edges follows a
monotonic trend.

In order to properly explain unfairness, the edges removed by GNNUERS should
maintain the recommendation properties other than unfairness as similar as
possible as they were before perturbing the graph. In light of this
perspective, a deletion cost $\lambda$ could be defined for each edge
$\tilde{e}\in\tilde{E}$, such that deleting an edge could have a greater
impact over deleting another edge. For instance, the cost of an edge should be
high if removing it would significantly alter the overall recommendation
utility. In this version, GNNUERS does not apply any cost to edges, which
corresponds to assuming that all edges have the same deletion cost. The cost
of removing an edge is implicitly determined in a data-driven way by the model
during the optimization process. We leave the analysis of explicit costs as a
future work.

###  4.3. Loss Function Optimization

The previous section introduced $\tilde{f}$, the counterfactual model
responsible of the generation of the perturbed adjacency matrix $\tilde{A}$.
The optimization of the perturbation vector $\hat{p}$ is guided by the loss
function defined in (1), where $\mathcal{L}_{fair}$ is based on Demographic
Parity (DP), the fairness notion described in Section 3.2. Recent works
(Boratto et al., 2022; Wu et al., 2022) operationalized DP as the mean of the
absolute pair-wise utility difference across all demographic groups. Formally:

(3) $\mathcal{L}_{fair}(A,\tilde{R})=\frac{1}{\binom{|G|}{2}}\sum_{1\leq
i<j\leq|G|}{\left\|S(\tilde{R}^{G_{i}},A^{G_{i}})-S(\tilde{R}^{G_{j}},A^{G_{j}})\right\|^{2}_{2}}$

where $S$ is a recommendation utility metric, $G$ is the set of considered
demographic groups, $\tilde{R}^{G_{i}}$ ($\tilde{R}^{G_{j}}$) and $A^{G_{i}}$
($A^{G_{j}}$) denote, respectively, the altered relevance sub-matrix and the
adjacency sub-matrix with respect to the users in $U^{G_{i}}$ ($U^{G_{j}}$).
Thus, $\mathcal{L}_{fair}$ is equivalent to $\Phi$ in Definition 3.1-3.2.

Following works that proposed methods to mitigate or explain unfairness in
recommendation (Li et al., 2021a; Ashokan and Haas, 2021; Kamishima et al.,
2018; Ge et al., 2022), we focus on a binary setting, with sensitive
attributes comprised of two demographic groups. For instance, given
$G=\\{males(M),females(F)\\}$, $\mathcal{L}_{fair}$ aims at minimizing the
utility disparity between males and females, with the optimal result being:

$\left\|S(\tilde{R}^{M},A^{M})-S(\tilde{R}^{F},A^{F})\right\|^{2}_{2}=0$

We denote the group with higher (lower) utility on the evaluation set as
_unprotected_ (_protected_). This enables the reader to better contextualize
the approach with respect to fairness.

In our experiments, the recommendation utility metric $S$ was monitored
through the Normalized Discounted Cumulative Gain (NDCG) (Järvelin and
Kekäläinen, 2002). This metric measures the utility of a recommended list
based on the position where the relevant items are placed. However, due to the
non-differentiability of the sorting operation performed to compute NDCG, we
adopt an approximated version (Wu et al., 2022; Qin et al., 2010), which we
refer as _NDCGApproxLoss_ :

(4) $\displaystyle NDCGApproxLoss(r,a)=$
$\displaystyle\>-\frac{1}{DCG(a,a)}\sum_{i}{\frac{2^{a_{i}}-1}{log_{2}(1+z_{i})}}$
$\displaystyle\text{s.t.}\quad z_{i}=$ $\displaystyle\>1+\sum_{j\neq
i}{\sigma\left(\frac{r_{j}-r_{i}}{\gamma}\right)}$

where DCG is the Discounted Cumulative Gain, $r$ is the item relevance score
produced by the recommender system, $\sigma$ is a sigmoid function, and
$\gamma$ is a scaling constant. We fix $\gamma=0.1$ for the experiments in
Section 5, being the default value in the TensorFlow Ranking implementation.
_NDCGApproxLoss_ is adopted only when constructing the fairness objective in
Equation (3), while the original NDCG is used in the evaluation phase. Given
our unfairness explanation task, the ground truth labels used to measure
_NDCGApproxLoss_ during the GNNUERS learning process are taken from the
evaluation set. Such approach is justified by the explanation task of the
recommendation unfairness measured on the evaluation set itself, while for
other tasks, e.g., mitigation ones, having access to the ground truth labels
is a less realistic assumption (Rahmani et al., 2022).

Any differentiable distance function can be adopted as the distance loss
$\mathcal{L}_{dist}$ (Lucic et al., 2022). In GNNUERS, it is based on the
absolute element-wise difference between $\tilde{A}$ and $A$, defined as
follows:

(5)
$\mathcal{L}_{dist}(A,\tilde{A})=\beta\frac{1}{2}\sigma\left(\sum_{i,j}{\left\|\tilde{A}_{i,j}-A_{i,j}\right\|^{2}_{2}}\right)$

A sigmoid function is used to bound the distance loss to the same range of
$\mathcal{L}_{fair}$, i.e. [0,1]. We used $\sigma(x)=|x|/(1+|x|)$, which needs
a higher number of perturbed edges to reach 1 compared with the popular
logistic function, hence covering a wider range of values. $\beta$ is a
parameter that balances the two losses, due to the trend of
$\mathcal{L}_{fair}$ to report values  much smaller than $0.5$, while
$\mathcal{L}_{dist}$ gets rapidly close to 1 as more edges are perturbed. We
tested several values of $\beta$ in the range $[0.001,2.0]$ and the best value
for each model was selected for the experiments in Section 5.

###  4.4. Gradient Deactivation

The optimization of (3) takes into account the approximate NDCG measured on
the predicted recommendations for the protected and unprotected group. The
update of the real-valued perturbation vector $\hat{p}$ is then affected from
the viewpoint of both demographic groups. In particular, GNNUERS selects edges
that could simultaneously optimize two objectives: increasing utility for the
protected group and decreasing it for the unprotected one. However, the edges
that are going to be perturbed for one of the objectives could negatively
affect the other one, and vice versa. To this end, we perform a gradient
_deactivation_ on the recommendations generated for the protected group, i.e.
the back-propagation updates the perturbation vector only from the unprotected
group viewpoint. This procedure is applied only on the protected group, such
that the GNNUERS objective is to delete the edges leading the unprotected
group to enjoy a higher level of recommendation utility.

Deactivating the gradient does not limit the group of edges that can be
perturbed because the optimization does not involve only the user nodes, but
also the item ones. Hence, GNNUERS could delete all the edges connected to an
item node, both coming from user nodes of the unprotected and protected group.
For conciseness, we will use the terms _deactivated_ and _activated_ to
characterize a group associated with inactive and active gradient
respectively.

###  4.5. Resources Usage

In this section, the two phases of the GNNUERS pipeline are examined in terms
of memory footprint and execution time complexity. The first phase regards the
generation of the perturbed matrix $\tilde{A}$ at each step of the learning
process by means of (2), which requires to store only the real-valued
perturbation vector $\hat{p}$. Leveraging a sparse representation of $A$ and
$\tilde{A}$, the perturbation time complexity is dependent on the number of
edges selected for perturbation $|\tilde{E}|$, i.e.,
$\mathcal{O}(|\tilde{E})|$. The second phase, that is the optimization process
directed towards learning $p$ (Sections 4.2-4.3), has no memory footprint and
is executed for $C$ iterations.  The iterations timing is dependent on the
cardinality of the user set and the number of user batches taken in input by
GNNUERS. Hence, given  $\Lambda$ the execution time for the inference step of
the extended GNN-based recommender system $\tilde{f}$ and $\Psi$ the execution
time of (1), $\mathcal{O}({\color[rgb]{0,0,0}\Lambda}\Psi C|\tilde{E}|)$ is
the time complexity of the perturbed graph generation.

##  5\. Evaluation

In this section, we examine the GNNUERS explanations with experiments aimed at
answering the following research questions:

  * •

RQ1: Can the perturbation of the graph topological structure explain
recommendation utility unfairness under the operationalised fairness notion?

  * •

RQ2: Can the perturbation minimally affect the recommendation utility of the
protected group while reducing the unprotected group one?

  * •

RQ3: Can the categorization of user nodes through topological graph properties
reveal the nature of unfairness?

The data manipulation, training and assessment of the GNN-based recommender
systems were built upon the framework Recbole (Zhao et al., 2021). The
experiments were ran on a A100 GPU machine with 80GB VRAM and 90GB RAM.

###  5.1. Graph Topological Properties

GNNUERS identifies explanations in the form of user-item interactions that
made a GNN-based recommender system generate unfair outcomes. Each edge
deleted from the graph unlinks a user and an item node, modifying the network
topological structure and affecting the properties characterizing all the
nodes, e.g., degree. GNNUERS edges selection process can then be described by
the properties of the nodes that constitute the removed edges.

To this end, we selected three properties that reflect different networks
topological aspects and their relation to properties examined in recommender
systems, e.g., popularity bias. Let $z\in Z$ be a generic node of
$\mathcal{G}$, i.e. $Z\subset U$ if $z$ is a user or $Z\subset V$ if $z$ is an
item, the nodes properties are:

  * •

Degree (DEG): the number of edges connected to each node. For a user node $u$
it represents the history length, i.e. $|I_{u}|$, for item nodes it represents
their popularity.

  * •

Density (DY): it represents the tendency of a node to be connected to high-
degree nodes. For user nodes it represents the tendency to interact with
popular items, for item nodes it describes the interest of their peers, where
users’ interest is greater as their histories length is longer. Formally,
given $\mathcal{N}_{z}$ the neighbors set of a node $z$:

(6)
$DY_{z}=\frac{\sum_{i=1}^{|\mathcal{N}_{z}|}{\frac{|\\{z^{\prime}\;|\;(\bar{z}_{i},\;z^{\prime})\;\in\;E\;\land\;\bar{z}_{i}\;\in\;\mathcal{N}_{z}\\}|}{|Z|}}}{|\mathcal{N}_{z}|}$

  * •

Intra-Group Distance (IGD): it represents how a node $z$ is close to the other
nodes $z^{\prime}\in Z/\\{z\\}$. Given the bipartite nature of recommender
systems networks, we consider two users (items) being distant $n$ if the
shortest path that connects them include $n$ items (users). IGD is the average
of the number of nodes of the same type of $z$ normalized by their distance to
$z$. Formally, given $N$ the graph diameter:

(7)
$IGD_{z}=\frac{\sum_{n=1}^{N}{\frac{|\\{z^{\prime}\;|\;\Gamma(z,\;z^{\prime})\;=\;n\\}|}{n}}}{|Z|}$

where $\Gamma$ measures the shortest path length between two nodes of the same
type.

The selected properties can describe the context on which GNNUERS operates,
i.e. the GNN-based recommender systems. Moreover, insights on the unfairness
can be uncovered by the variance of such properties across demographic groups,
due to the intrinsic relationship between the given context and the
unfairness. In detail, the degree (DEG) of a user node represents the interest
towards the available items and the amount of information that the GNN can
leverage in the aggregation step, the density (DY) of a user node captures the
inclination to engage with popular items, the intra-group distance (IGD) of a
user node indicates the propensity to interact with items valued by fellow
users within the same demographic group. Moreover, the properties DEG and DY
reflect the GNN ability to propagate information across the user nodes using
the message passing mechanism, given that DEG and DY regard the nodes amount
at the 1- and 2-hop distance respectively.

Our properties present similarities with assortativity mixing (Newman, 2003),
which estimates the propensity of nodes of the same group, e.g., females, to
connect to each other. This definition is mostly connected with IGD, given
that it intrinsically leverages the groups information to discover how close
fellow users are. Nonetheless, assortativity mixing addresses only direct
connections between nodes. Conversely, IGD captures also the information about
the distance among nodes of the same group, where such distance accounts for
the bipartite nature of the network.

###  5.2. Data Preparation

Table 1. Statistics of the four data sets used in our experimental protocol.
_Repr._ stands for _Representation_ , _Min._ for _Minimum_. _G_ stands for
Gender, _A_ for Age, _Gini_ for the Gini coefficient applied over the values
of the graph properties for each group. The line over the graph properties
denotes their average.

|  | ML-1M (Harper and Konstan, 2016) | FENG333https://www.kaggle.com/datasets/chiranjivdas09/ta-feng-grocery-dataset | LFM-1K (Celma, 2010) | INS444https://www.kaggle.com/datasets/mrmorj/insurance-recommendation
---|---|---|---|---|---
# Users | 6,040 | 25,741 | 268 | 346
# Items | 3,706 | 23,643 | 51,609 | 20
# Interactions | 1,000,209 | 708,919 | 200,586 | 1,879
Min. User DEG | 20 | 5 | 21 | 5
Domain | Movie | Grocery | Music | Insurance
Repr. | A | O : 43.4%; Y : 56.6% | O : 45.5% ; Y : 54.5% | O : 42.2%; Y : 57.8% | O : 49.4%; Y : 50.6%
G | F : 28.3%; M : 71.7% | NA | F : 42.2%; M : 57.8% | F : 23.4%; M : 76.6%
$\overline{\text{User DEG}}$ | A | O : 106.1; Y : 124.9 | O : 20.7; Y : 19.6 | O : 657.5; Y : 428.0 | O : 4.3; Y : 4.5
G | F : 101.8; M : 122.7 | NA | F : 496.7; M : 545.3 | F : 4.2; M : 4.5
Gini User DEG | A | O : 0.53; Y : 0.52 | O : 0.45; Y : 0.44 | O : 0.43; Y : 0.43 | O : 0.06; Y : 0.08
G | F : 0.53; M : 0.52 | NA | F : 0.42; M : 0.45 | F : 0.05; M : 0.08
$\overline{\text{User DY}}$ | A | O : 0.07; Y : 0.07 | O : 0.00; Y : 0.00 | O : 0.03; Y : 0.03 | O : 0.40; Y : 0.38
G | F : 0.07; M : 0.07 | NA | F : 0.04; M : 0.04 | F : 0.40; M : 0.39
Gini User DY | A | O : 0.12; Y : 0.11 | O : 0.45; Y : 0.42 | O : 0.22; Y : 0.18 | O : 0.12; Y : 0.14
G | F : 0.12; M : 0.12 | NA | F : 0.15; M : 0.23 | F : 0.14; M : 0.13
$\overline{\text{User IGD}}$ | A | O : 0.95; Y : 0.96 | O : 0.57; Y : 0.56 | O : 0.99; Y : 0.99 | O : 0.97; Y : 0.97
G | F : 0.95; M : 0.96 | NA | F : 0.99; M : 0.99 | F : 0.97; M : 0.97
Gini User IGD | A | O : 0.03; Y : 0.02 | O : 0.05; Y : 0.05 | O : 0.01; Y : 0.01 | O : 0.01; Y : 0.01
G | F : 0.03; M : 0.02 | NA | F : 0.00; M : 0.01 | F : 0.01; M : 0.01

Extensive research in user fairness in recommender systems is challenging due
to the limited datasets including users’ sensitive information. We relied on
the artifacts of a recent work accounting unfairness issues in recommendation
(Boratto et al., 2022), which performed a fairness assessment on two corpora:
MovieLens 1M (ML-1M), on the movie domain, and Last.FM 1K (LFM-1K), on the
music domain. The time information of the users’ interaction in LFM-1K was
missing. Hence, given that the interactions of each user are grouped by artist
and considered as a single interaction, we set the timestamp of the last
interaction with an artist to be the timestamp of the relative user-artist
pair in LFM-1K. We extended the set of datasets by including Insurance (INS),
on the insurance domain, and Ta Feng (FENG), on the grocery domain555Yelp
(Mansoury et al., 2019) was also considered to include the business domain,
but the users’ gender information was predicted by their name, making
questionable analyses on this dataset.. All datasets include age and gender
(except FENG) information for all users and their statistics are listed in
Table 1, where the graph properties values regard only the training set. The
Gini coefficient for each property was measured as in (Fabbri et al., 2022).

User nodes in INS and FENG were filtered by their number of interactions, i.e.
their degree, so as to take into account users with histories made up of at
least 5 items. Duplicated interactions, e.g., users buying the same product
twice in FENG, were removed. On the basis of the binary setting mentioned in
Section 4.3 and as done in (Boratto et al., 2022), INS and FENG age labels
were binarized as _Younger (Y)_ and _Older (O)_ , such that the _Younger_
group is more represented than the _Older_ one for consistency with ML-1M and
LFM-1K. Gender labels were already binary, as _Males (M)_ and _Females (F)_.

We also adopted the splitting strategy used in (Boratto et al., 2022) for each
dataset: per each user, 20% (the most recent if a timestamp is available,
randomly sampled otherwise) of the interactions forms the test set; the
remaining interactions are split again, such that 10% (selected in the same
way) of this interactions subset forms the validation set, and the remaining
70% forms the train set. The validation set was used to select the training
epoch where the model reported the best recommendation utility on the
adjacency matrix $A$. Given the goal of finding the edges causing unfairness
in the test set, the truth ground labels of the latter were extracted to
optimize the fairness loss in $\eqref{eq:fairloss}$.

###  5.3. Models

Recently, novel GNNs have been devised to solve the top-$k$ recommendation
task. We relied on Recbole, which includes different families of GNN-based
recommender systems. GNNUERS was adopted on the following models:

  * •

GCMC (van den Berg et al., 2017): this method is comprised of two components:
a graph auto-encoder, which produces a node embedding matrix, and a decoder
model, which predicts the relevance of the missing entries in the adjacency
matrix from the node embedding matrix.

  * •

NGCF (Wang et al., 2019): this state-of-the-art GNN-based recommender system
propagates embeddings in the user-item graph structure. In particular, it
leverages high-order connectivities in the user-item integration graph,
injecting the collaborative signal into the embeddings explicitly.

  * •

LigthGCN (He et al., 2020): it is a simplification of a GCN, including only
the most essential components for collaborative filtering, i.e. the
neighborhood aggregation. It uses a single embedding as the weighted sum of
the user and item embeddings propagated at all layers in the graph.

The GNNs were trained with the default and model-specific hyper-parameters
defined by Recbole.

###  5.4. Explanation Baseline Methods

As mentioned in Section 4.2, GNNUERS in its base form applies a policy that
prevents the algorithm from restoring previously deleted edges. Additionally,
we examined an extension of GNNUERS by applying another policy, _Connected
Nodes (CN)_. It limits the perturbation to the edges connected to the
unprotected user nodes to investigate whether recommendation unfairness is
only due to the interactions performed by the unprotected group. Therefore,
GNNUERS+CN guides the learning process to select the users’ actions of the
unprotected group that made $f$ favor them.

The literature does not include baselines that explain unfairness in the form
of user-item edges as GNNUERS. The works proposing unfairness explainability
methods in recommendation (Deldjoo et al., 2021; Ge et al., 2022) select
relevant user/item features as explanations, which cannot be compared with the
ones generated by our framework. Approaches proposed to explain unfairness in
GNNs (Dong et al., 2023) were devised for classification tasks. Although it is
not clear if such methods could be extended to recommendation tasks, such an
engineering adaptation goes beyond the goal of our work.  The alternative
counterfactual explainability algorithms in GNNs present limitations as well.
Specifically, methods that generate explanations at the model level (Huang et
al., 2023) present computational and memory footprint limitations that prevent
their extension from small graphs, e.g., molecules, to the typically larger
networks of user-item interactions. The methods that generate explanations at
the instance level (Lucic et al., 2022; Kang et al., 2021) cannot be trivially
adapted to envision the unfairness task at the model level.

To this end, we adopted CASPER (Oh et al., 2022) for comparison, a model-
agnostic method that causes the highest instability in the recommendations by
perturbing a single interaction, i.e. an edge of the graph. The instability
induced by CASPER could alter the recommendations, and, as a result, re-
distributing the utility levels over the demographic groups and positively
affecting unfairness. At inference step, our models generate the
recommendation lists by using the training network perturbed by CASPER, then
fairness and utility metrics are measured. CASPER uses the timestamp of each
interaction to generate a directed acyclic graph of the interactions of each
user. INS does not include the time information, so CASPER was not applied on
this dataset.

We also introduce RND-P as sanity check, a baseline algorithm that at each
iteration randomly perturbs edges with a probability $\rho$, such that it
mimics the GNNUERS edges selection process, but based on a random choice.
Given the size diversity of our evaluation datasets, we set
$\rho=1/(|E_{train}|/100)$, where $E_{train}$ is the set of training edges, as
the value that works best across the selected epochs. As a consequence, RND-P
perturbs edges depending on the network size to prevent the random sampling
from deleting all the edges in a few iterations.

The explanation methods were executed on all the models and datasets over 800
epochs adopting an early stopping method when $\mathcal{L}_{fair}$ does not
improve with a delta higher than 0.001 for at least 15 consecutive epochs. The
best hyperparameters (learning rate, $\beta$, batch size) can be found in the
source code repository.  In order to preserve the recommendation scenario
described by the original adjacency matrix, GNNUERS stops if all the
interactions of a user or item are deleted. Nonetheless, this constraint was
never triggered in our experiments.

The following experiments employ the selected datasets and models to assess
the ability of GNNUERS of explaining unfairness in GNN-based recommendation.
In view of this goal, we expect our method to be used in scenarios where
models exhibit a certain degree of unfairness, which is determined by the
context and the requirements imposed by platform owners and policy makers.
Therefore, in our experiments, we assume the recommendations generated by the
selected models to be unfair to some extent, even subtly, on the target
datasets.

###  5.5. RQ1: Unfairness Explainability Benchmark

---
|
ML-1M | FENG
|
LFM-1K | INS

Figure 2. Distribution of $\Delta$NDCG between younger and older users
subgroups, randomly sampled 100 times. A Wilcoxon signed-rank test is
performed between each pair of boxes and the respective p-value is shown if it
is lower than $\frac{0.05}{m}$ according to the Bonferroni correction, where
$m$ is the number of pairwise comparisons performed for each model.

---
|
ML-1M | LFM-1K
INS

Figure 3. Distribution of $\Delta$NDCG between males and females users
subgroups, randomly sampled 100 times. A Wilcoxon signed-rank test is
performed between each pair of boxes and the respective p-value is shown if it
is lower than $\frac{0.05}{m}$ according to the Bonferroni correction, where
$m$ is the number of pairwise comparisons performed for each model.

We first investigated the capability of GNNUERS to select counterfactual
explanations that effectively optimize (3). The GNNUERS learning process
selects users coming from both demographic groups, stores them in fixed-size
batches according to their distribution in the dataset, and optimizes the loss
to minimize disparity in NDCG@10 (average) between the protected and
unprotected group. The evaluation phase follows an analogous process: we
randomly sample 100 subgroups with the same demographic groups distribution of
the batches and with sample size equal to the batch size. This choice is also
due to reduce the sampling bias present in the datasets, i.e. the evaluation
is not affected by the different sample size of unprotected and protected
groups. The batch size for each dataset is selected such that it splits the
users in at least five partitions, guaranteeing a low probability of picking
the same users in the randomly sampled subgroups. We measure the differences
in each subgroup with $\Delta$NDCG, which corresponds to the difference in
performance between the two user groups. $\Delta$NDCG is then related to the
unfairness level measured by (3) (without the modulus operator), and the
function $\Phi$ used in Definition 3.1-3.2. We compare our proposed solution
with CASPER, RND-P and the original $\Delta$NDCG values,  denoted as NP.

Age. Figure 2 shows the $\Delta$NDCG distribution across the subgroups defined
by the attribute ”age”. We adopt the Wilcoxon signed-rank test and report, on
top of each boxplot, the p-value significance of the difference between the
means of each distributions pair (it is reported IFF the p-values are lower
than $\frac{0.05}{m}$ according to the Bonferroni correction, where $m$ is the
number of pairwise comparisons performed for each model). On the bottom of the
plots, we include the NDCG@10 after the perturbation and the percentage of
deleted edges. First, we can see how in ML-1M and FENG our methods
significantly narrow the $\Delta$NDCG distribution of the age subgroups
compared with NP, by perturbing just 1% of the edges in some settings. The
single edge deleted by CASPER minimally affects the recommendations of all the
experiments, with more prominent effects on GCMC under several datasets, e.g.,
ML-1M, FENG. On the other hand, the perturbation applied by RND-P, in some
cases, can generate a decrease in unfairness, but the early stopping prevents
it from removing too many edges, which highlights its inefficiency in reducing
$\Delta$NDCG along the epochs. Among our methods, GNNUERS+CN reports the least
perturbations and generates competitive decreases in $\Delta$NDCG. On INS, no
explanation method is consistent in reducing $\Delta$NDCG. This means that the
difference in performance between the groups derived from ”age” are not
affected by the perturbation of individual interactions, but other aspects
(e.g., specific nodes) possibly caused the original disparity.

Generally, GNNUERS and GNNUERS+CN are able to significantly reduce
$\Delta$NDCG in most of the settings, selecting small subsets of deleted
edges. Interestingly, in some cases, the NDCG@10 drops significantly (LFM-1K
and FENG), while in others remains consistent (ML-1M). This means that our
algorithms are able to generate explanations of the unfairness by detecting
edges that contribute significantly to increasing unfairness and to improving
performance for only one subgroup.

Gender. GNNUERS generates a significant decrease in $\Delta$NDCG also for the
subgroups generated by the attribute ”gender”, as shown in Figure 3. In ML-1M
and LFM-1K, GNNUERS significantly explains unfairness for all the models,
reducing $\Delta$NDCG by a relatively lower amount compared to the same
experiments on age groups (e.g., on LFM-1K). While our method has proven to be
effective regardless of the sensitive attribute, perturbing a single edge
(CASPER) or more in a random way (RND-P) does not decrease $\Delta$NDCG in
these cases (except for GCMC on LFM-1K). On INS, differently from what seen
before, GNNUERS can reduce unfairness between gender groups, by deleting a
relevant higher number of edges compared to other experiments. This result
emphasizes how the users’ splitting in groups could result in different types
of unfairness.

RQ1.  Except extreme cases, GNNUERS selects edges that systematically and
significantly explain unfairness, regardless of the data, models and user
groups on which is applied.

As shown in both demographic groups, NDCG is not always drastically impacted
globally. For this reason, we run a more thorough analysis of the impact on
utility.

###  5.6. RQ2: Impact on Recommendation Utility

Table 2. For both protected and unprotected groups, each column includes the
value of NDCG after applying GNNUERS and in the brackets its relative change
from the original NDCG. Unproctected group values are highlighted and in bold.

|  |  | Age | Gender
---|---|---|---|---
| Model | Policy | Younger | Older | Males | Females
ML-1M | GCMC | GNNUERS | 0.11* (-21.6%) | 0.11* (-11.6%) | 0.10* (-24.2%) | 0.10* (-14.6%)
GNNUERS+CN | 0.12* (-14.0%) | 0.11* (-06.7%) | 0.11* (-16.3%) | 0.10* (-10.2%)
LightGCN | GNNUERS | 0.11* (-21.6%) | 0.10* (-15.4%) | 0.10* (-22.8%) | 0.09* (-17.6%)
GNNUERS+CN | 0.11* (-16.7%) | 0.10* (-10.6%) | 0.11* (-19.4%) | 0.09* (-14.1%)
NGCF | GNNUERS | 0.12* (-11.6%) | 0.11* (-02.7%) | 0.13* (-07.8%) | 0.11* (-01.8%)
GNNUERS+CN | 0.13* (-09.2%) | 0.12 (-00.4%) | 0.13* (-07.1%) | 0.11 (-01.0%)
FENG | GCMC | GNNUERS | 0.01* (-67.0%) | 0.01* (-78.9%) | - | -
GNNUERS+CN | 0.02* (-62.4%) | 0.01* (-77.6%) | - | -
LightGCN | GNNUERS | 0.02* (-51.3%) | 0.02* (-61.2%) | - | -
GNNUERS+CN | 0.03* (-36.7%) | 0.03* (-51.2%) | - | -
NGCF | GNNUERS | 0.04* (-10.4%) | 0.04* (-28.1%) | - | -
GNNUERS+CN | 0.04* (-01.9%) | 0.05* (-13.2%) | - | -
LFM-1K | GCMC | GNNUERS | 0.27* (-22.8%) | 0.26* (-40.4%) | 0.33* (-12.0%) | 0.31* (-26.4%)
GNNUERS+CN | 0.32* (-08.0%) | 0.36* (-16.4%) | 0.35* (-05.9%) | 0.35* (-17.4%)
LightGCN | GNNUERS | 0.34* (-05.9%) | 0.37* (-15.5%) | 0.34* (-07.9%) | 0.37* (-16.7%)
GNNUERS+CN | 0.33* (-09.5%) | 0.37* (-15.8%) | 0.35* (-07.4%) | 0.38* (-13.9%)
NGCF | GNNUERS | 0.35* (-01.5%) | 0.39* (-09.6%) | 0.36 (-00.9%) | 0.38* (-12.4%)
GNNUERS+CN | 0.35 ( 00.2%) | 0.40* (-05.9%) | 0.37* ( 02.5%) | 0.42* (-04.1%)
INS | GCMC | GNNUERS | 0.37* (-52.7%) | 0.33* (-56.8%) | 0.62* (-20.0%) | 0.60* (-13.3%)
GNNUERS+CN | 0.69* (-10.6%) | 0.70* (-08.0%) | 0.68* (-12.4%) | 0.67* (-02.7%)
LightGCN | GNNUERS | 0.71* (-09.9%) | 0.71* (-08.4%) | 0.69* (-12.8%) | 0.69* (-05.2%)
GNNUERS+CN | 0.79 ( 00.1%) | 0.78 ( 00.3%) | 0.74* (-06.7%) | 0.73* ( 01.5%)
NGCF | GNNUERS | 0.78 (-00.3%) | 0.77* (-02.4%) | 0.72* (-09.6%) | 0.73* (-01.2%)
GNNUERS+CN | 0.77* (-01.1%) | 0.76* (-03.8%) | 0.73* (-08.7%) | 0.74 ( 00.7%)

Our unfairness explanation task aims to identify the user-item interactions
that made the recommender system advantage a demographic group, i.e. the
unprotected group. Given that the same user-item interactions represent the
main source of information for recommender systems, we expect the edges
deletion process of GNNUERS to negatively affect the recommendation utility to
find a proper explanation. To this end, GNNUERS is devised to minimize the gap
in recommendation utility between the demographic groups, but without or
minimally affecting the utility for the protected group.  This perspective is
related to Definition 3.2, such that a faithful explanation would properly
uncover the interactions that advantaged the unprotected group. We empirically
evaluate this aspect, by examining the edges deletion impact on the utility
for each group. The NDCG@10 was measured individually for each user to then
averaging it across demographic groups. The impact on recommendation utility
was measured as the change in utility after applying the perturbation. To
estimate this change significance, we first leveraged the 100 subgroups used
in Section 5.5. Then, for each subgroup, we gathered the NDCG@10 average
measured on the recommendations altered from each explanation method and the
average generated from the non-perturbed network. Finally, a Wilcoxon signed-
rank test was performed between the averages resulting from the non-perturbed
network and from each explanation method. For this analysis, we consider
GNNUERS and GNNUERS+CN.

Table 2 shows the average utility (highlighted for the unprotected group)
after perturbing the edges and its relative change from the original one
between brackets. For each value, the symbol (*) denotes the significance of
the statistical test with the 95% of confidence interval. We can see how, for
any dataset and model, the NDCG change for the unprotected group is greater
than the protected group one. This confirms that our algorithms can select the
edges responsible for an higher utility for the unprotected group. However,
also the NDCG for the protected group is affected in most of the experiments.
This is because the results are model dependent, and removing edges reduces
the connectivity, and then the information propagation through the GNN. Also,
higher NDCG losses for the unprotected groups reflect a better unfairness
explanation, as seen for all the models in FENG666GNNUERS learning process
could be stopped once a desired level of fairness or utility is reached for
the explanation, depending on the application requirements.. Based on this
observation, since GNNUERS perturbations for NGCF result in the least faithful
unfairness explanation w.r.t. the other models in the previous RQ, for the
same model it reports the lowest loss in utility for both demographic groups.
As a matter of fact, not only for NGCF the NDCG for the protected group is
minimally affected, but it also increases in some settings, e.g., for males
users in LFM-1K. The GNNUERS+CN policy enforces this behavior more than
GNNUERS by a slight amount, except for FENG. Indeed, in FENG the NDCG is equal
between demographic groups, but GNNUERS reports an additional 10% loss in
utility. Using GNNUERS+CN edges selection is then beneficial to reduce the
impact on the NDCG for the protected group.

RQ2.  GNNUERS and GNNUERS+CN reduce the utility for unprotected groups,
detecting edges that led to a disparity in performance, while reporting a
negligible loss for the protected ones.

###  5.7. RQ3: Edges Selection Process

The findings of the first two research questions regard the GNNUERS
performance in explaining the unfairness and its impact on the recommendation
utility of each demographic group. Despite the edges selected by GNNUERS
represent themselves a counterfactual explanation of the utility disparity
across demographic groups, the edges taken as they are do not provide
sufficient information to fully understand the graph features that contribute
to the unfairness. To this purpose, we leverage the user nodes connected to
such edges and categorize them by the properties defined in Section 5.1.
Specifically, user nodes were distinguished by demographic groups (_Males_ ,
_Females_ , _Younger_ , _Older_) and the nodes in each group were partitioned
in quartiles. The order of the data points was defined by the value of each
graph property that characterizes the users in each quartile, e.g., low-DEG
nodes (Q1). Thus, the graph properties were individually measured for each
demographic group by defining the subgroups _Males_ , _Females_ , _Younger_ ,
_Older_ as the set $Z$ one at a time. For instance, if $Z$ is the subgroup of
_Males_ , $IGD_{z}$ represents how the male $z\in Z$ is close to the other
males $z^{\prime}\in Z/\\{z\\}$.

For each demographic group and each quartile, the number of perturbed edges
was taken and normalized by the total number of edges perturbed in each
experiment. Therefore, the perturbed edges can be categorized as well based on
the extent such edges are distributed over the quartiles for each graph
property. A higher distribution over nodes with low or high DEG, DY, IGD
levels would highlight the aspects that drove our explanation method to
perturb the given edges, and, therefore, highlight the aspects that led to the
unfairness in the original recommendations.

GNNUERS+CN was not included in the following experiments because the edges
deletion constraint could only reflect the distribution over quartiles defined
for the unprotected group. RQ1 reported FENG, ML-1M, LFM-1K as the datasets on
which our method consistently explain unfairness by reducing the disparity in
NDCG between the demographic groups derived by both ”gender” and ”age”. RQ2
highlighted NGCF as the model where GNNUERS can explain unfairness while
affecting the recommendation utility of the protected group the least. GNNUERS
selection process will be analyzed only on the experiments with these
settings, as they would better reflect the properties characterizing biased
recommendations.

Age. For each graph property, Figure 4 reports the distribution of the edges
deleted by GNNUERS over the quartiles, which are defined for each demographic
group derived from ”age”. Except for LFM-1K, the distribution of deleted edges
is significantly higher for the unprotected groups (ML-1M: Younger, FENG:
Older), which highlights that the unfair recommendations are highly dependent
on the unprotected users’ interactions. On ML-1M, the over-representation
(Table 1) and over-DEG of the unprotected group is enough to deviate the
recommendations in their favor. No relevant pattern is reported across
quartiles. Hence, also with regard to the unbalanced groups’ representation,
the nodes themselves could be related to the unfairness, given that GNNUERS
explains it by consistently pruning more their edges compared to the protected
group ones. For both FENG and LFM-1K, GNNUERS deletes more edges connected to
high-DEG (Q4) and high-IGD (Q4) unprotected users (LFM-1K: Younger, FENG:
Older), which represent those unprotected users with the most interactions and
the closest ones to other unprotected user nodes. According to Table 1, Older
users in FENG are less represented, but their higher average DEG and IGD
reflects the observations derived from Figure 4.  On LFM-1K, the gap in DY
between the protected and unprotected user nodes gets larger as the tendency
to consume more popular (Q3-Q4) artists (items) increases. Hence, the edges
deleted by GNNUERS highlight a possible connection between popularity bias and
unfairness across age groups. This subgroup (high DEG, DY, IGD) of Younger
users may have contributed to the increased popularity of certain artists.
This phenomenon may have hindered the personalization power of the system for
Younger users in lower quartiles, leading to recommendations with lower
overall utility.

Figure 4. Deleted edges distribution (_Del Edges Distribution_) over the
quartiles (Q1-Q2-Q3-Q4) defined for each _age_ group through sorting the nodes
by each graph property. The edges were deleted applying GNNUERS on NGCF.

Figure 5. Deleted edges distribution (_Del Edges Distribution_) over the
quartiles (Q1-Q2-Q3-Q4) defined for each _gender_ group through sorting the
nodes by each graph property. The edges were deleted applying GNNUERS on NGCF.

Gender. Figure 5 reports the distribution of the deleted edges over the graph
properties quartiles, defined for each gender group. FENG does not include
gender labels, so it could not be included in this figure. On ML-1M, the
significant difference of deleted edges between Males and Females underlines
the unfairness may be affected by an over-representation of the unprotected
group (Males) in terms of nodes and edges, i.e. over-DEG (according to Table
1). Instead, the trend observed in the distribution of deleted edges over DEG
and IGD suggests that unfairness may be influenced by the interactions of low-
DEG and -IGD (Q1) Males. Hence, we conjecture that GNNUERS identifies the
interactions of isolated (low IGD) Males who watched fewer movies (low DEG) as
a factor that may have led NGCF to favor this gender group. Moreover, the
deleted edges distribution over Males is slightly higher towards the lowest
(DY Q1) and highest (DY Q4) popularity levels, restricting the GNNUERS edges
selection to isolated Males connected with just a few of mostly niche or
mainstream movies. On LFM-1K, GNNUERS perturbes the interactions applying a
dual effect. Except for DY, lower values (Q1) of the graph properties report a
higher amount of deleted edges connected to the unprotected (Females) nodes,
while the nodes with higher values (Q4) that lost more edges are the protected
(Males) ones. Unfairness explanation is then accomplished by the simultaneous
perturbation of low-DEG, low-IGD Females and high-DEG, high-IGD Males.
Removing the interactions of isolated (low IGD) Females listening to a few
artists (low DEG) may have drastically affected the fairness levels, causing
GNNUERS to inevitably perturb edges connected to nodes with the opposite
properties (high-IGD, high-DEG Males) to restore fairness. The fact that Males
report a higher Gini on DY compared to Females suggests the former tend more
to interact with artists of diverse popularity, which emphasizes how the
modification of the artists’ popularity impacts the recommendations.

RQ3.  GNNUERS edges selection process is significantly affected by the dataset
domain. Experiments uncovered an unfairness mainly related to differences
between demographic groups in interest (DEG) and closeness (IGD).

##  6\. Discussion and Conclusions

In this work, we introduced GNNUERS, a framework to explain unfairness in GNN-
based recommender systems. GNNUERS aims to find the set of edges generating
unfairness in GNNs recommendations through counterfactuality (Section 4). We
proved the effectiveness of our method on three state-of-the-art GNN-based
recommender systems and evaluated it on four real-world datasets, focusing on
the disparity in recommendation utility between gender and age groups (Section
5). In this section, we discuss the GNNUERS explanations interpretation,
limitations and future extensions.

###  6.1. Interpretation of Unfairness Explanations

The counterfactual explanations generated by GNNUERS aim to support system
designers and service providers to improve the fairness of recommendation
models outcomes. However, differently from other model-level explanations
methods in GNNs (Yuan et al., 2020; Huang et al., 2023), user-item interaction
networks generally consist of a significantly high number of nodes and edges,
e.g., the graphs used in our experiments.  Moreover, edge-level explanations
generated at a local scope (Lucic et al., 2022; Kang et al., 2021) can be
easily visualized as an edge mask over a node’s ego-graph, which is
significantly smaller than the entire network. It follows that visualizing the
original graphs with the application of the edges mask selected by GNNUERS
does not convey sufficient information to interpret the aspects affecting the
prior unfairness. Analyzing the edges as they are is therefore challenging and
it is crucial to account for other features and properties of the nodes
connected to such edges.

In the previous section, we leveraged the graph properties introduced in
Section 5.1 to characterize the edges identified by GNNUERS as a possible
source of the user unfairness. The selected properties reflect different
aspects of the GNNs architecture and of the recommendation scenario: DEG
represents the users’ interest in the items and the available nodes for the
GNNs aggregation step, DY represents the users’ tendency to interact with
popular items, IGD represents the users’ closeness in the network. It follows
that the insights provided by the nodes categorization of the unfairness
explanations by means of the selected properties could be synthesized in a
more compact and user-friendly form, e.g., a textual description. We
implicitly performed such a synthesis in Section 5.7 when we stated that _“
GNNUERS identifies the interactions of isolated (low IGD) Males who watched
fewer movies (low DEG) as a factor that may have led NGCF to favor this gender
group”_ for ML-1M, and that _“unfairness explanation is then accomplished by
the simultaneous perturbation of low-DEG, low-IGD Females and high-DEG, high-
IGD Males”_ for LFM-1K. Despite these statements highlight relevant aspects of
the prior user unfairness in the recommendations, they could be extended by
accounting for other user and item features, e.g., the movie (ML-1M) and the
songs (LFM-1K) genres. However, not all datasets include additional user/item
features (e.g., INS). Hence, a more thorough and comprehensive investigation
could provide more informative findings and it will be one of the main
objectives in our future works.

###  6.2. Limitations and Future Works

Table 3. GNNUERS execution timings. _1/ $C$ Iter. Time_ stands for the timings
after 1 and $C$ iterations.

| ML-1M | FENG | LFM-1K | INS
---|---|---|---|---
| 1/$C$ Iter. Time | 1/$C$ Iter. Time | 1/$C$ Iter. Time | 1/$C$ Iter. Time
GCMC |  $\sim$15s/$\sim$300s |  $\sim$40s/$\sim$1,800s |  $\sim$10s/$\sim$120s |  $\sim$1s/$\sim$10s
LightGCN |  $\sim$15s/$\sim$300s |  $\sim$30s/$\sim$2,700s |  $\sim$2s/$\sim$60s |  $\sim$1s/$\sim$30s
NGCF |  $\sim$40s/$\sim$2,400s |  $\sim$30s/$\sim$600s |  $\sim$2s/$\sim$120s |  $\sim$1s/$\sim$15s

GNNUERS is the first step towards explaining unfairness in GNN-based
recommender systems through counterfactuality, that is finding which
interactions of the sensitive groups led to unfairness. GNNUERS reduces the
unfairness in recommendations, but with the purpose of explaining the issue,
not mitigating it. Indeed, we devised our method to seek for edges to
eliminate from the original graph because of our objective of finding one of
the possible sources of the unfairness, represented as the users’ behavior
(interactions) affecting the model outcomes. As shown through the experiments,
this procedure might lead to reduced recommendation utility for the
unprotected groups, due to the fact that their interactions are deleted and
identified by GNNUERS as compromising the recommendation fairness. We plan to
extend GNNUERS in the future to augment the original graph, i.e. adding edges
and/or nodes, as an explanation tool, but also as a procedure to mitigate the
unfairness without loss in accuracy.

GNNUERS represents a powerful solution to generate explanations of unfairness
issues on the consumer side of recommender systems. In order to spotlight our
framework as a valuable tool to perform the targeted task under different
experimental protocols, we focus on the resources usage introduced in Section
4.5 and discuss in depth the time requirements of GNNUERS. Table 3 reports the
graph generation timings after 1 and $C$ iterations on the datasets and models
used in our experiments. The generation process of the perturbed graph
monitors the fairness level of the demographic groups, marking an iteration as
complete when the recommendation utility for each user is measured.
Consequently, a higher number of users results in slower execution times per
iteration, particularly notable in datasets including a high number of users,
e.g., FENG. Results also emphasize nuances across models, influenced by the
diverse characteristics of each dataset. For instance, GCMC timings per epoch
could be affected by the larger item set of FENG and LFM-1K, while the feature
transformation performed in the graph convolution operation of NGCF could be
slowed by the denser adjacency matrix of ML-1M. The overall timings varied
more, since $C$, i.e., the total amount of iterations, increases until the
early stopping is triggered, which reflects the generation process will result
in a more accurate unfairness explanation.

Given that the main component affecting the execution times is the cardinality
of the user set, processing larger batches of users can significantly reduce
the time needed by GNNUERS to reach convergence. Moreover, the global nature
of the unfairness explanations requires GNNUERS to be run just once for each
sensitive attribute, in contrast with local explanations that are generated
for each user. In light of these observations, GNNUERS linearly scale as the
number of users increases. Instead, the computational time on datasets with a
large amount of interactions could only be influenced by the GNN backbone used
to run GNNUERS, not by the graph generation process itself.

GNNUERS was used to explain recommendation utility unfairness among
demographic subgroups in a binary setting. Having only two subgroups better
highlights the edges selection performed by our framework and offers a clearer
overview of the GNNUERS explainability power. Even if we considered protected
attributes as binary features, they are by no means binary and the age labels
binarization was performed according only to the desired final groups
distribution, without any discriminatory intentions against users’ age.
Nonetheless, we plan to extend GNNUERS in settings presenting more subgroups
for each sensitive attribute, and also with different subgroups cardinality.

Moreover, given the flexibility of the framework, GNNUERS can be also extended
to other GNN-based architectures, with different aggregation methods or GNN-
layers, e.g., GAT.

## References

  * (1)
  * Agarwal et al. (2021) Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. 2021\.  Towards a unified framework for fair and stable graph representation learning. In _Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, UAI 2021_ , Vol. 161. AUAI Press, 2114–2124.
  * Ashokan and Haas (2021) Ashwathy Ashokan and Christian Haas. 2021.  Fairness metrics and bias mitigation strategies for rating predictions.  _Inf. Process. Manag._ 58, 5 (2021), 102646.  https://doi.org/10.1016/j.ipm.2021.102646
  * Balloccu et al. (2022) Giacomo Balloccu, Ludovico Boratto, Gianni Fenu, and Mirko Marras. 2022.  Post Processing Recommender Systems with Knowledge Graphs for Recency, Popularity, and Diversity of Explanations. In _SIGIR ’22: The 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, Madrid, Spain, July 11 - 15, 2022_. ACM, 646–656.  https://doi.org/10.1145/3477495.3532041
  * Boratto et al. (2022) Ludovico Boratto, Gianni Fenu, Mirko Marras, and Giacomo Medda. 2022.  Consumer Fairness in Recommender Systems: Contextualizing Definitions and Mitigations. In _Advances in Information Retrieval_. Springer International Publishing, Cham, 552–566.
  * Brunot et al. (2022) Léo Brunot, Nicolas Canovas, Alexandre Chanson, Nicolas Labroche, and Willeme Verdeaux. 2022\.  Preference-based and local post-hoc explanations for recommender systems.  _Inf. Syst._ 108 (2022), 102021.  https://doi.org/10.1016/j.is.2022.102021
  * 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, FAT 2018_ , Vol. 81. PMLR, 202–214.  http://proceedings.mlr.press/v81/burke18a.html
  * Celma (2010) Òscar Celma. 2010\.  _Music Recommendation and Discovery - The Long Tail, Long Fail, and Long Play in the Digital Music Space_.  Springer.  https://doi.org/10.1007/978-3-642-13287-2
  * Chen et al. (2021) Weijian Chen, Fuli Feng, Qifan Wang, Xiangnan He, Chonggang Song, Guohui Ling, and Yongdong Zhang. 2021.  CatGCN: Graph Convolutional Networks with Categorical Node Features.  _IEEE Transactions on Knowledge and Data Engineering_ (2021).
  * Chen et al. (2019) Weijian Chen, Yulong Gu, Zhaochun Ren, Xiangnan He, Hongtao Xie, Tong Guo, Dawei Yin, and Yongdong Zhang. 2019\.  Semi-supervised user profiling with heterogeneous graph attention networks. In _Proceedings of the 28th International Joint Conference on Artificial Intelligence_. 2116–2122.
  * Chen et al. (2022b) Xu Chen, Yongfeng Zhang, and Ji-Rong Wen. 2022b.  Measuring ”Why” in Recommender Systems: a Comprehensive Survey on the Evaluation of Explainable Recommendation.  _CoRR_ abs/2202.06466 (2022).  arXiv:2202.06466 https://arxiv.org/abs/2202.06466
  * Chen et al. (2022a) Ziheng Chen, Fabrizio Silvestri, Jia Wang, Yongfeng Zhang, Zhenhua Huang, Hongshik Ahn, and Gabriele Tolomei. 2022a.  GREASE: Generate Factual and Counterfactual Explanations for GNN-based Recommendations.  _CoRR_ abs/2208.04222 (2022).  arXiv:2208.04222 https://doi.org/10.48550/arXiv.2208.04222
  * Cui et al. (2022) Hejie Cui, Jiaying Lu, Yao Ge, and Carl Yang. 2022\.  How Can Graph Neural Networks Help Document Retrieval: A Case Study on CORD19 with Concept Map Generation. In _European Conference on Information Retrieval_. Springer, 75–83.
  * Deldjoo et al. (2021) Yashar Deldjoo, Alejandro Bellogín, and Tommaso Di Noia. 2021\.  Explaining recommender systems fairness and accuracy through the lens of data characteristics.  _Inf. Process. Manag._ 58, 5 (2021), 102662.  https://doi.org/10.1016/j.ipm.2021.102662
  * Dong et al. (2023) Yushun Dong, Song Wang, Jing Ma, Ninghao Liu, and Jundong Li. 2023.  Interpreting Unfairness in Graph Neural Networks via Training Node Attribution. In _Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI 2023, Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence, IAAI 2023, Thirteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023_. 7441–7449.  https://ojs.aaai.org/index.php/AAAI/article/view/25905
  * Ekstrand et al. (2022) Michael D. Ekstrand, Anubrata Das, Robin Burke, and Fernando Diaz. 2022.  Fairness in Information Access Systems.  _Found. Trends Inf. Retr._ 16, 1-2 (2022), 1–177.  https://doi.org/10.1561/1500000079
  * Ekstrand et al. (2018) Michael D. Ekstrand, Mucun Tian, Ion Madrazo Azpiazu, Jennifer D. Ekstrand, Oghenemaro Anuyah, David McNeill, and Maria Soledad Pera. 2018\.  All The Cool Kids, How Do They Fit In?: Popularity and Demographic Biases in Recommender Evaluation and Effectiveness. In _Conference on Fairness, Accountability and Transparency, FAT 2018_ , Vol. 81. PMLR, 172–186.  http://proceedings.mlr.press/v81/ekstrand18b.html
  * Fabbri et al. (2022) Francesco Fabbri, Maria Luisa Croci, Francesco Bonchi, and Carlos Castillo. 2022.  Exposure Inequality in People Recommender Systems: The Long-Term Effects. In _Proceedings of the Sixteenth International AAAI Conference on Web and Social Media, ICWSM 2022_. AAAI Press, 194–204.
  * Frisch et al. (2021) Gabriel Frisch, Jean-Benoist Léger, and Yves Grandvalet. 2021.  Stereotype-aware collaborative filtering. In _Proceedings of the 16th Conference on Computer Science and Intelligence Systems, Online, September 2-5, 2021_. 69–79.  https://doi.org/10.15439/2021F117
  * Ge et al. (2022) Yingqiang Ge, Juntao Tan, Yan Zhu, Yinglong Xia, Jiebo Luo, Shuchang Liu, Zuohui Fu, Shijie Geng, Zelong Li, and Yongfeng Zhang. 2022\.  Explainable Fairness in Recommendation. In _SIGIR ’22: The 45th International ACM SIGIR Conference on Research and Development in Information Retrieval_. ACM, 681–691.  https://doi.org/10.1145/3477495.3531973
  * Ghazimatin et al. (2020) Azin Ghazimatin, Oana Balalau, Rishiraj Saha Roy, and Gerhard Weikum. 2020.  PRINCE: Provider-side Interpretability with Counterfactual Explanations in Recommender Systems. In _WSDM ’20: The Thirteenth ACM International Conference on Web Search and Data Mining_. ACM, 196–204.
  * Ghazimatin et al. (2021) Azin Ghazimatin, Soumajit Pramanik, Rishiraj Saha Roy, and Gerhard Weikum. 2021.  ELIXIR: Learning from User Feedback on Explanations to Improve Recommender Models. In _WWW ’21: The Web Conference 2021_. ACM / IW3C2.
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017\.  Inductive representation learning on large graphs.  _Advances in neural information processing systems_ 30 (2017).
  * Harper and Konstan (2016) F. Maxwell Harper and Joseph A. Konstan. 2016.  The MovieLens Datasets: History and Context.  _ACM Trans. Interact. Intell. Syst._ 5, 4 (2016), 19:1–19:19.  https://doi.org/10.1145/2827872
  * He et al. (2020) Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yong-Dong Zhang, and Meng Wang. 2020\.  LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation. In _Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, SIGIR 2020, Virtual Event, China, July 25-30, 2020_. ACM, 639–648.  https://doi.org/10.1145/3397271.3401063
  * Huang et al. (2023) Zexi Huang, Mert Kosan, Sourav Medya, Sayan Ranu, and Ambuj K. Singh. 2023.  Global Counterfactual Explainer for Graph Neural Networks. In _Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, WSDM 2023, Singapore, 27 February 2023 - 3 March 2023_ , Tat-Seng Chua, Hady W. Lauw, Luo Si, Evimaria Terzi, and Panayiotis Tsaparas (Eds.). ACM, 141–149.  https://doi.org/10.1145/3539597.3570376
  * Järvelin and Kekäläinen (2002) Kalervo Järvelin and Jaana Kekäläinen. 2002\.  Cumulated gain-based evaluation of IR techniques.  _ACM Trans. Inf. Syst._ 20, 4 (2002), 422–446.  https://doi.org/10.1145/582415.582418
  * Kamishima et al. (2018) Toshihiro Kamishima, Shotaro Akaho, Hideki Asoh, and Jun Sakuma. 2018.  Recommendation Independence. In _Conference on Fairness, Accountability and Transparency, FAT 2018_ , Vol. 81. PMLR, 187–201.
  * Kang et al. (2021) Bo Kang, Jefrey Lijffijt, and Tijl De Bie. 2021.  Explanations for Network Embedding-Based Link Predictions. In _Machine Learning and Principles and Practice of Knowledge Discovery in Databases - International Workshops of ECML PKDD 2021_ , Vol. 1524. Springer, 473–488.
  * Kipf and Welling (2017) Thomas N. Kipf and Max Welling. 2017.  Semi-Supervised Classification with Graph Convolutional Networks. In _5th International Conference on Learning Representations, ICLR 2017, Conference Track Proceedings_.
  * Li et al. (2021a) Yunqi Li, Hanxiong Chen, Zuohui Fu, Yingqiang Ge, and Yongfeng Zhang. 2021a.  User-oriented Fairness in Recommendation. In _WWW ’21: The Web Conference 2021_. ACM / IW3C2, 624–632.  https://doi.org/10.1145/3442381.3449866
  * Li et al. (2021b) Yunqi Li, Hanxiong Chen, Shuyuan Xu, Yingqiang Ge, and Yongfeng Zhang. 2021b.  Towards Personalized Fairness based on Causal Notion. In _SIGIR ’21: The 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_. ACM, 1054–1063.
  * Lucic et al. (2022) Ana Lucic, Maartje A. ter Hoeve, Gabriele Tolomei, Maarten de Rijke, and Fabrizio Silvestri. 2022\.  CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks. In _International Conference on Artificial Intelligence and Statistics, AISTATS 2022_ , Vol. 151. PMLR, 4499–4511.
  * Ma et al. (2022) Jing Ma, Ruocheng Guo, Mengting Wan, Longqi Yang, Aidong Zhang, and Jundong Li. 2022\.  Learning Fair Node Representations with Graph Counterfactual Fairness. In _WSDM ’22: The Fifteenth ACM International Conference on Web Search and Data Mining_. ACM, 695–703.
  * Mansoury et al. (2019) Masoud Mansoury, Bamshad Mobasher, Robin Burke, and Mykola Pechenizkiy. 2019.  Bias Disparity in Collaborative Recommendation: Algorithmic Evaluation and Comparison. In _Proceedings of the Workshop on Recommendation in Multi-stakeholder Environments co-located with the 13th ACM Conference on Recommender Systems (RecSys 2019)_ _(CEUR Workshop Proceedings, Vol. 2440)_. CEUR-WS.org.
  * 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 Comput. Surv._ 54, 6 (2021), 115:1–115:35.  https://doi.org/10.1145/3457607
  * Newman (2003) M. E. J. Newman. 2003\.  Mixing patterns in networks.  _Phys. Rev. E_ 67 (Feb 2003), 026126.  Issue 2. https://doi.org/10.1103/PhysRevE.67.026126
  * Oh et al. (2022) Sejoon Oh, Berk Ustun, Julian J. McAuley, and Srijan Kumar. 2022\.  Rank List Sensitivity of Recommender Systems to Interaction Perturbations. In _Proceedings of the 31st ACM International Conference on Information & Knowledge Management_. ACM, 1584–1594.
  * Qin et al. (2010) Tao Qin, Tie-Yan Liu, and Hang Li. 2010.  A general approximation framework for direct optimization of information retrieval measures.  _Inf. Retr._ 13, 4 (2010), 375–397.  https://doi.org/10.1007/s10791-009-9124-x
  * 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. In _SIGIR ’22: The 45th International ACM SIGIR Conference on Research and Development in Information Retrieval_. ACM, 2755–2764.  https://doi.org/10.1145/3477495.3531718
  * Singh and Joachims (2018) Ashudeep Singh and Thorsten Joachims. 2018.  Fairness of Exposure in Rankings. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018_. ACM, 2219–2228.
  * Srinivas et al. (2017) Suraj Srinivas, Akshayvarun Subramanya, and R. Venkatesh Babu. 2017.  Training Sparse Neural Networks. In _2017 IEEE Conference on Computer Vision and Pattern Recognition Workshops, CVPR Workshops 2017_. IEEE Computer Society, 455–462.  https://doi.org/10.1109/CVPRW.2017.61
  * Tan et al. (2021) Juntao Tan, Shuyuan Xu, Yingqiang Ge, Yunqi Li, Xu Chen, and Yongfeng Zhang. 2021\.  Counterfactual Explainable Recommendation. In _CIKM ’21: The 30th ACM International Conference on Information and Knowledge Management, Virtual Event, Queensland, Australia, November 1 - 5, 2021_ , Gianluca Demartini, Guido Zuccon, J. Shane Culpepper, Zi Huang, and Hanghang Tong (Eds.). ACM, 1784–1793.  https://doi.org/10.1145/3459637.3482420
  * van den Berg et al. (2017) Rianne van den Berg, Thomas N. Kipf, and Max Welling. 2017\.  Graph Convolutional Matrix Completion.  _CoRR_ abs/1706.02263 (2017).  arXiv:1706.02263
  * Veličković et al. (2017) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2017.  Graph Attention Networks. In _International Conference on Learning Representations_.
  * Wang et al. (2022a) Nan Wang, Lu Lin, Jundong Li, and Hongning Wang. 2022a.  Unbiased Graph Embedding with Biased Graph Observations. In _WWW ’22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 - 29, 2022_. ACM, 1423–1433.
  * Wang et al. (2022c) Nan Wang, Shaoliang Nie, Qifan Wang, Yi-Chia Wang, Maziar Sanjabi, Jingzhou Liu, Hamed Firooz, and Hongning Wang. 2022c.  COFFEE: Counterfactual Fairness for Personalized Text Generation in Explainable Recommendation.  _CoRR_ abs/2210.15500 (2022).  https://doi.org/10.48550/arXiv.2210.15500 arXiv:2210.15500
  * Wang et al. (2022d) Shoujin Wang, Xiuzhen Zhang, Yan Wang, Huan Liu, and Francesco Ricci. 2022d.  Trustworthy Recommender Systems.  _CoRR_ abs/2208.06265 (2022).
  * Wang et al. (2019) Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. 2019.  Neural Graph Collaborative Filtering. In _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2019, Paris, France, July 21-25, 2019_. ACM.
  * Wang et al. (2022b) Yifan Wang, Weizhi Ma, Min Zhang, Yiqun Liu, and Shaoping Ma. 2022b.  A Survey on the Fairness of Recommender Systems.  _ACM Trans. Inf. Syst._ (jul 2022).  https://doi.org/10.1145/3547333 Just Accepted.
  * Wu et al. (2021) Chuhan Wu, Fangzhao Wu, Xiting Wang, Yongfeng Huang, and Xing Xie. 2021.  Fairness-aware News Recommendation with Decomposed Adversarial Learning. In _Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021_. AAAI Press, 4462–4469.
  * Wu et al. (2022) Haolun Wu, Chen Ma, Bhaskar Mitra, Fernando Diaz, and Xue Liu. 2022.  A Multi-Objective Optimization Framework for Multi-Stakeholder Fairness-Aware Recommendation.  _ACM Trans. Inf. Syst._ (aug 2022).  https://doi.org/10.1145/3564285 Just Accepted.
  * Yan et al. (2021) Qilong Yan, Yufeng Zhang, Qiang Liu, Shu Wu, and Liang Wang. 2021.  Relation-aware Heterogeneous Graph for User Profiling. In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_. Association for Computing Machinery, New York, NY, USA.
  * Yao et al. (2019) Liang Yao, Chengsheng Mao, and Yuan Luo. 2019.  Graph convolutional networks for text classification. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 33. 7370–7377.
  * Ying et al. (2018) Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. 2018\.  Graph convolutional neural networks for web-scale recommender systems. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 974–983.
  * Yuan et al. (2020) Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. 2020\.  XGNN: Towards Model-Level Explanations of Graph Neural Networks. In _KDD ’20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020_. ACM, 430–438.
  * Yuan et al. (2023) Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. 2023\.  Explainability in Graph Neural Networks: A Taxonomic Survey.  _IEEE Trans. Pattern Anal. Mach. Intell._ 45, 5 (2023), 5782–5799.  https://doi.org/10.1109/TPAMI.2022.3204236
  * Zhang et al. (2023) Shichang Zhang, Jiani Zhang, Xiang Song, Soji Adeshina, Da Zheng, Christos Faloutsos, and Yizhou Sun. 2023.  PaGE-Link: Path-based Graph Neural Network Explanation for Heterogeneous Link Prediction. In _Proceedings of the ACM Web Conference 2023, WWW 2023, Austin, TX, USA, 30 April 2023 - 4 May 2023_ , Ying Ding, Jie Tang, Juan F. Sequeda, Lora Aroyo, Carlos Castillo, and Geert-Jan Houben (Eds.). ACM, 3784–3793.  https://doi.org/10.1145/3543507.3583511
  * Zhang and Chen (2020) Yongfeng Zhang and Xu Chen. 2020.  Explainable Recommendation: A Survey and New Perspectives.  _Found. Trends Inf. Retr._ 14, 1 (mar 2020), 1–101.
  * Zhang et al. (2022) Ziwei Zhang, Peng Cui, and Wenwu Zhu. 2022.  Deep Learning on Graphs: A Survey.  _IEEE Transactions on Knowledge and Data Engineering_ 34, 1 (2022), 249–270.
  * Zhao et al. (2021) Wayne Xin Zhao, Shanlei Mu, Yupeng Hou, Zihan Lin, Yushuo Chen, Xingyu Pan, Kaiyuan Li, Yujie Lu, Hui Wang, Changxin Tian, Yingqian Min, Zhichao Feng, Xinyan Fan, Xu Chen, Pengfei Wang, Wendi Ji, Yaliang Li, Xiaoling Wang, and Ji-Rong Wen. 2021.  RecBole: Towards a Unified, Comprehensive and Efficient Framework for Recommendation Algorithms. In _CIKM ’21: The 30th ACM International Conference on Information and Knowledge Management_. ACM, 4653–4664.
  * Zhong and Negre (2022) Jinfeng Zhong and Elsa Negre. 2022.  Shap-enhanced counterfactual explanations for recommendations. In _SAC ’22: The 37th ACM/SIGAPP Symposium on Applied Computing, Virtual Event, April 25 - 29, 2022_ , Jiman Hong, Miroslav Bures, Juw Won Park, and Tomás Cerný (Eds.). ACM, 1365–1372.  https://doi.org/10.1145/3477314.3507029