# Pareto Frontier for the Performance-Complexity Trade-off in Beyond Diagonal
Reconfigurable Intelligent Surfaces

Matteo Nerini, , Bruno Clerckx M. Nerini is with the Department of Electrical
and Electronic Engineering, Imperial College London, London SW7 2AZ, U.K.
(e-mail: m.nerini20@imperial.ac.uk).B. Clerckx is with the Department of
Electrical and Electronic Engineering, Imperial College London, London SW7
2AZ, U.K., and with Silicon Austria Labs (SAL), Graz A-8010, Austria (e-mail:
b.clerckx@imperial.ac.uk).

###### Abstract

Reconfigurable intelligent surface (RIS) is an emerging technology allowing to
control the propagation environment in wireless communications. Recently,
beyond diagonal RIS (BD-RIS) has been proposed to reach higher performance
than conventional RIS, at the expense of higher circuit complexity. Multiple
BD-RIS architectures have been developed with the goal of reaching a favorable
trade-off between performance and circuit complexity. However, the fundamental
limits of this trade-off are still unexplored. In this paper, we fill this gap
by deriving the expression of the Pareto frontier for the performance-
complexity trade-off in BD-RIS. Additionally, we characterize the optimal BD-
RIS architectures reaching this Pareto frontier.

###### Index Terms:

Beyond diagonal reconfigurable intelligent surface (BD-RIS), Pareto frontier,
performance-complexity trade-off.

##  I Introduction

Reconfigurable intelligent surface (RIS) has recently gained a lot of
popularity as a technology able to make the propagation environment smart and
reconfigurable in wireless networks [1, 2, 3]. A RIS is composed of a large
number of electrically tunable reflective elements that can be controlled to
provide a passive beamforming gain. Due to its ultra-low power consumption,
low profile, and low cost, RIS is expected to efficiently enhance the
performance and coverage of future wireless communications.

In a conventional RIS architecture, also known as single-connected, each
element is independently controlled by a tunable impedance component [4]. This
results in conventional RIS having a diagonal scattering matrix, also commonly
known as a phase shift matrix. To improve the capabilities of RIS, beyond
diagonal RIS (BD-RIS) has been proposed as a generalization of conventional
RIS, in which the scattering matrix is not limited to being diagonal [5]. The
key novelty introduced in BD-RIS is the presence of tunable impedance
components interconnecting the RIS elements, adding further flexibility to the
RIS at the expense of additional circuit complexity. The single-connected RIS
architecture has been first generalized in [4]. By interconnecting some or all
the RIS elements to each other, group- and fully-connected RIS architectures
have been proposed, respectively [4]. Group- and fully-connected RISs have
been globally optimized in closed form assuming continuous reflection
coefficients in [6], while they have been optimized using discrete reflection
coefficients in [7]. Besides, BD-RIS have been modeled using graph theory in
[8], where BD-RIS architectures have been described through graphs capturing
the presence of tunable impedance components between the RIS elements. As a
result of this graph theoretical modeling, two low-complexity BD-RIS
architectures have been proposed, namely forest- and tree-connected RISs [8].

BD-RIS has been studied in several contexts showing significant performance
gains over conventional RIS. In [9], a BD-RIS model has been developed
unifying different BD-RIS working modes (reflective/transmissive/hybrid) and
different BD-RIS architectures (single/group/fully-connected). In [10], multi-
sector BD-RIS has been introduced to efficiently enable full-space coverage,
where the elements are divided into multiple sectors, each covering a narrow
region of space. Non-diagonal RIS [11] and dynamically group-connected RIS
[12] have been proposed to outperform conventional RIS and group-connected
RIS, respectively, thanks to their dynamic interconnections reconfigured on a
per channel realization basis. Additionally, BD-RIS has proved to enlarge the
coverage and improve the sum rate in rate splitting multiple access (RSMA)
systems [13, 14], and to improve communication capacity and sensing precision
in dual-function radar-communication (DFRC) systems [15].

When designing new BD-RIS architectures, the critical issue is the trade-off
between performance and circuit complexity, given by the number of tunable
impedance components in the BD-RIS architecture [8]. On the one hand, the
single-connected RIS is the architecture with the lowest circuit complexity
since there are no interconnections among the RIS elements. Due to its limited
flexibility, the single-connected RIS can only achieve a reduced performance.
On the other hand, the fully-connected RIS has the highest circuit complexity
since each RIS element is connected to all others through a tunable impedance
component, enabling the highest performance. Several BD-RIS architectures have
been proposed to trade performance and complexity. However, the fundamental
limits of this trade-off are still unexplored. To fill this gap, we
investigate how to optimally trade the achievable performance and the circuit
complexity in BD-RIS architectures.

The contribution of this letter is twofold. First, we derive the Pareto
frontier for the performance-complexity trade-off offered by BD-RIS in single-
input single-output (SISO) systems. Second, we characterize the optimal BD-RIS
architectures allowing to achieve this Pareto frontier.

##  II System Model

Consider a SISO communication system aided by an $N$-element RIS. The $N$
elements of the RIS are connected to a $N$-port reconfigurable impedance
network, with scattering matrix $\boldsymbol{\Theta}\in\mathbb{C}^{N\times
N}$. Defining $x\in\mathbb{C}$ as the transmitted signal and $y\in\mathbb{C}$
as the received signal, we have $y=hx+n$, where $h\in\mathbb{C}$ is the
wireless channel and $n\in\mathbb{C}$ is the additive white Gaussian noise
(AWGN) at the receiver. Assuming that the direct link between the transmitter
and the receiver is negligible compared to the RIS-aided link, the channel $h$
writes as

$h=\mathbf{h}_{R}\boldsymbol{\Theta}\mathbf{h}_{T},$ (1)

where $\mathbf{h}_{R}\in\mathbb{C}^{1\times N}$ and
$\mathbf{h}_{T}\in\mathbb{C}^{N\times 1}$ refer to the channels from the RIS
to the receiver and from the transmitter to the RIS, respectively [4]111Since
$\mathbf{h}_{R}\boldsymbol{\Theta}\mathbf{h}_{T}$ can always be co-phased with
the direct link, our conclusions are not impacted by the direct link. In the
case of a non-negligible direct link, the performance would merely be scaled
up, depending on its strength. Thus, we neglect the direct link to gain
fundamental insights not depending on its strength.. In this study, we assume
independent and identically distributed (i.i.d.) Rayleigh fading channels
$\mathbf{h}_{R}\sim\mathcal{CN}\left(\boldsymbol{0},\mathbf{I}\right)$ and
$\mathbf{h}_{T}\sim\mathcal{CN}\left(\boldsymbol{0},\mathbf{I}\right)$.

When reconfiguring a RIS, the scattering matrix $\boldsymbol{\Theta}$ is
typically optimized to maximize the performance given by the received signal
power

$P_{R}=P_{T}\left|\mathbf{h}_{R}\boldsymbol{\Theta}\mathbf{h}_{T}\right|^{2},$
(2)

where $P_{T}=\mathrm{E}[\left|x\right|^{2}]$ is the transmitted signal power.
Considering passive RISs with lossless and reciprocal impedance networks, the
matrix $\boldsymbol{\Theta}$ is in general subject to the constraints
$\boldsymbol{\Theta}^{H}\boldsymbol{\Theta}=\boldsymbol{\mathrm{I}}$ and
$\boldsymbol{\Theta}=\boldsymbol{\Theta}^{T}$ [16]. Furthermore, additional
constraints on $\boldsymbol{\Theta}$, limiting the received signal power, are
present depending on the BD-RIS architecture [4, 8].

##  III Problem Formulation

Conventional RIS, also known as single-connected RIS, is the least complex
architecture achieving the lowest performance, given by

$\bar{P}_{R}^{\mathrm{Single}}=P_{T}\left(\sum_{n=1}^{N}\left|\left[\mathbf{h}_{R}\right]_{n}\left[\mathbf{h}_{T}\right]_{n}\right|\right)^{2},$
(3)

since it includes only $N$ tunable impedance components [4]. In contrast,
tree-connected RIS is proved to be the least complex architecture achieving
the performance upper bound

$\bar{P}_{R}^{\mathrm{Tree}}=P_{T}\left\|\mathbf{h}_{R}\right\|^{2}\left\|\mathbf{h}_{T}\right\|^{2},$
(4)

with $2N-1$ tunable impedance components [8]. In this letter, our goal is to
determine the maximum performance achievable by BD-RIS architectures with
circuit complexity $C\in[N,2N-1]$, representing the number of tunable
components222In our analysis, we preclude BD-RISs with dynamic
interconnections, since they require switches and hence additional circuit
complexity.. Furthermore, we are interested in which BD-RIS architectures
allow us to reach such a maximum performance, denoted as “optimal” BD-RIS
architectures in the following.

We begin by characterizing the maximum received signal power achievable by a
given BD-RIS architecture. To this end, we consider the modeling of BD-RIS
based on graph theory developed in [8]. According to [8], each BD-RIS
architecture can be described through a graph $\mathcal{G}$ capturing the
presence of tunable impedance components between its RIS elements. We denote
as $G$ the number of connected components of such a graph $\mathcal{G}$, where
a connected component of a graph is defined as a connected subgraph that is
not part of any larger connected subgraph [17]. Besides, $N_{g}\geq 1$ is the
number of RIS elements included in the $g$th component, with
$\sum_{g=1}^{G}N_{g}=N$. In agreement with previous work on BD-RIS [4]-[12],
we refer to the connected components of $\mathcal{G}$ as the “groups” of the
corresponding BD-RIS architecture. According to [8], the maximum received
signal power obtained by the BD-RIS associated with $\mathcal{G}$ is given by

$\bar{P}_{R}=P_{T}\left(\sum_{g=1}^{G}\left\|\mathbf{h}_{R,g}\right\|\left\|\mathbf{h}_{T,g}\right\|\right)^{2},$
(5)

where $\mathbf{h}_{R,g}\in\mathbb{C}^{1\times N_{g}}$ and
$\mathbf{h}_{T,g}\in\mathbb{C}^{N_{g}\times 1}$ contain the $N_{g}$ elements
of $\mathbf{h}_{R}$ and $\mathbf{h}_{T}$ corresponding to the $N_{g}$ RIS
elements included into the $g$th group, respectively. In the case of i.i.d.
fading channels, we can assume that each group includes adjacent RIS elements
with no loss of generality, such that
$\mathbf{h}_{R}=[\mathbf{h}_{R,1},\ldots,\mathbf{h}_{R,G}]$ and
$\mathbf{h}_{T}=[\mathbf{h}_{T,1}^{T},\ldots,\mathbf{h}_{T,G}^{T}]^{T}$. Thus,
the maximum received signal power $\bar{P}_{R}$ achievable by a given BD-RIS
architecture solely depends on $G$ and the group sizes $N_{1},\ldots,N_{G}$.

To express the maximum received signal power $\bar{P}_{R}$ achievable with a
circuit complexity $C$ as a function of $C$, we introduce the following three
results. First, we characterize the optimal BD-RIS architectures through the
following lemma.

######  Lemma 1.

All the optimal BD-RIS architectures have a corresponding graph being acyclic,
also known as a forest.

###### Proof.

Please refer to Appendix A. ∎

In other words, a BD-RIS architecture can be optimal only if its graph does
not contain any cycle, i.e., a finite sequence of distinct edges joining a
sequence of vertices, where only the first and last vertices are equal [17].
Second, we use the following result from graph theory [17].

######  Lemma 2.

If a graph $\mathcal{G}$ is a forest, then it has $G=N-L$ connected
components, where $N$ is the number of vertices and $L$ is the number of
edges.

###### Proof.

Please refer to Appendix B. ∎

Third, by using Lemma 1 and Lemma 2, we can derive the following proposition.

######  Proposition 1.

An optimal BD-RIS architecture with $N$ elements and circuit complexity $C$,
with $C\in[N,2N-1]$, has a corresponding graph with $G=2N-C$ connected
components.

###### Proof.

Please refer to Appendix C. ∎

According to Proposition 1, given a circuit complexity $C$, the number of
groups $G$ in the corresponding optimal BD-RIS is fixed. Thus, our problem is
to find the group sizes $N_{1},\ldots,N_{G}$ of the BD-RIS architecture that
maximize the performance $\mathrm{E}\left[\bar{P}_{R}\right]$, with fixed $G$.
The corresponding optimization problem is given by

$\displaystyle\underset{N_{1},\ldots,N_{G}}{\mathsf{\mathrm{max}}}\;\;$
$\displaystyle\mathrm{E}\left[\bar{P}_{R}\right]$ (6)
$\displaystyle\mathsf{\mathrm{s.t.}}\;\;\;$ $\displaystyle N_{g}\geq
1,\>\forall g,\>\>\sum_{g=1}^{G}N_{g}=N,$ (7)

where $G=2N-C$ is fixed depending on the circuit complexity $C$.

##  IV Pareto Frontier

To solve problem (6)-(7), we assume $P_{T}=1$ with no loss of generality and,
making use of the i.i.d. channels assumption, we write the average received
signal power (5) as

$\mathrm{E}\left[\bar{P}_{R}\right]=\sum_{g=1}^{G}\mathrm{E}\left[\left\|\mathbf{h}_{R,g}\right\|^{2}\right]^{2}\\\
+\sum_{g_{1}\neq
g_{2}}\mathrm{E}\left[\left\|\mathbf{h}_{R,g_{1}}\right\|\right]^{2}\mathrm{E}\left[\left\|\mathbf{h}_{R,g_{2}}\right\|\right]^{2}.$
(8)

Using the moment of the $\chi_{2N_{g}}$ distribution, we have that
$\mathrm{E}[\|\mathbf{h}_{R,g}\|]=\Gamma(N_{g}+1/2)/\Gamma(N_{g})$ and
$\mathrm{E}[\|\mathbf{h}_{R,g}\|^{2}]=N_{g}$, for $g=1,\ldots,G$, where
$\Gamma(\cdot)$ refers to the gamma function. Thus, we can write

$\mathrm{E}\left[\bar{P}_{R}\right]=\sum_{g=1}^{G}N_{g}^{2}\\\
+\sum_{g_{1}\neq
g_{2}}\left(\frac{\Gamma\left(N_{g_{1}}+1/2\right)}{\Gamma\left(N_{g_{1}}\right)}\right)^{2}\left(\frac{\Gamma\left(N_{g_{2}}+1/2\right)}{\Gamma\left(N_{g_{2}}\right)}\right)^{2}.$
(9)

Figure 1: Relative error $\delta$ for the first 10 positive integers $M$.

The expression of $\mathrm{E}\left[\bar{P}_{R}\right]$ in (9) can be now
simplified by using the relationship

$\left(\frac{\Gamma\left(M+1/2\right)}{\Gamma\left(M\right)}\right)^{2}=M-\frac{1}{4}+\frac{1}{32M}+\mathcal{O}\left(\left(\frac{1}{M}\right)^{2}\right),$
(10)

given by the Laurent series expansion at $M=\infty$ [18]. Remarkably, the
function $(\Gamma(M+1/2)/\Gamma(M))^{2}$ is well approximated by
$M-1/4+1/(32M)$ for any positive integer $M$, despite the series being
computed at $M=\infty$. To show this, in Fig. 1, we report the relative error

$\delta=\frac{\left(\frac{\Gamma\left(M+1/2\right)}{\Gamma\left(M\right)}\right)^{2}-\left(M-\frac{1}{4}+\frac{1}{32M}\right)}{\left(\frac{\Gamma\left(M+1/2\right)}{\Gamma\left(M\right)}\right)^{2}},$
(11)

for the first positive integers. Since $\delta$ is significantly small for any
positive integer $M$, we can approximate (9) as

$\mathrm{E}\left[\bar{P}_{R}\right]=\sum_{g=1}^{G}N_{g}^{2}\\\
+\sum_{g_{1}\neq
g_{2}}\left(N_{g_{1}}-\frac{1}{4}+\frac{1}{32N_{g_{1}}}\right)\left(N_{g_{2}}-\frac{1}{4}+\frac{1}{32N_{g_{2}}}\right).$
(12)

By developing the product and reorganizing the terms, we get

$\mathrm{E}\left[\bar{P}_{R}\right]=\sum_{g=1}^{G}N_{g}^{2}+\sum_{g_{1}\neq
g_{2}}\left(N_{g_{1}}N_{g_{2}}+\frac{1}{16}-\frac{N_{g_{1}}}{4}-\frac{N_{g_{2}}}{4}\right.\\\
+\left.\frac{N_{g_{1}}}{32N_{g_{2}}}+\frac{N_{g_{2}}}{32N_{g_{1}}}-\frac{1}{128N_{g_{1}}}-\frac{1}{128N_{g_{2}}}+\frac{1}{1024N_{g_{1}}N_{g_{2}}}\right).$
(13)

Recalling that $N_{g}\geq 1$, $\forall g$, the term
$1/(1024N_{g_{1}}N_{g_{2}})$ in (13) is negligible since it is at least 1024
times smaller than the term $N_{g_{1}}N_{g_{2}}$. Thus, omitting
$1/(1024N_{g_{1}}N_{g_{2}})$ and completing the computations, we obtain

$\mathrm{E}\left[\bar{P}_{R}\right]=N^{2}+\frac{G\left(G-1\right)}{16}-\frac{N\left(G-1\right)}{2}\\\
+\sum_{g_{1}\neq
g_{2}}\left(\frac{N_{g_{1}}}{32N_{g_{2}}}+\frac{N_{g_{2}}}{32N_{g_{1}}}-\frac{1}{128N_{g_{1}}}-\frac{1}{128N_{g_{2}}}\right).$
(14)

Observing that

$\displaystyle\sum_{g_{1}\neq
g_{2}}\frac{N_{g_{1}}}{32N_{g_{2}}}=\sum_{g_{1}\neq
g_{2}}\frac{N_{g_{2}}}{32N_{g_{1}}}=\sum_{g=1}^{G}\frac{N-N_{g}}{32N_{g}},$
(15) $\displaystyle\sum_{g_{1}\neq
g_{2}}\frac{1}{128N_{g_{1}}}=\sum_{g_{1}\neq
g_{2}}\frac{1}{128N_{g_{2}}}=\sum_{g=1}^{G}\frac{G-1}{128N_{g}},$ (16)

we can eventually rewrite $\mathrm{E}\left[\bar{P}_{R}\right]$ as

$\mathrm{E}\left[\bar{P}_{R}\right]=N^{2}+\frac{G-1}{16}\left(G-8N\right)\\\
-\frac{G}{16}+\frac{4N-G+1}{64}\sum_{g=1}^{G}\frac{1}{N_{g}}.$ (17)

Figure 2: Pareto frontier for the performance-complexity trade-off achieved by
BD-RISs, with $N=64$.

We notice from (17) that maximizing $\mathrm{E}\left[\bar{P}_{R}\right]$ is
equivalent to maximize $\sum_{g=1}^{G}1/N_{g}$. Thus, problem (6)-(7) can be
equivalently expressed as

$\displaystyle\underset{N_{1},\ldots,N_{G}}{\mathsf{\mathrm{max}}}\;\;$
$\displaystyle\sum_{g=1}^{G}\frac{1}{N_{g}}$ (18)
$\displaystyle\mathsf{\mathrm{s.t.}}\;\;\;$ $\displaystyle N_{g}\geq
1,\>\forall g,\>\>\sum_{g=1}^{G}N_{g}=N,$ (19)

which is solved in the following proposition.

######  Proposition 2.

The solution to problem (18)-(19) is given by

$\displaystyle N_{1}=N_{2}=\ldots=N_{G-1}=1,$ (20) $\displaystyle
N_{G}=N-G+1,$ (21)

up to a permutation of the group sizes.

###### Proof.

Please refer to Appendix D. ∎

Given the optimal group sizes $N_{1},\ldots,N_{G}$ provided by Proposition 2,
we can derive in closed form the expression of the desired Pareto frontier.
Specifically, plugging (20) and (21) into (9), we obtain

$\mathrm{E}\left[\bar{P}_{R}\right]=G-1+\left(N-G+1\right)^{2}+\left(G-1\right)\left(G-2\right)\Gamma\left(3/2\right)^{4}\\\
+2\left(G-1\right)\left(\frac{\Gamma\left(N-G+3/2\right)\Gamma\left(3/2\right)}{\Gamma\left(N-G+1\right)}\right)^{2},$
(22)

giving the maximum performance achievable with a BD-RIS architecture having
$G$ groups. Finally, recalling that $G=2N-C$, the expression of the maximum
performance achievable with a circuit complexity $C\in[N,2N-1]$ is given by

$\mathrm{E}\left[\bar{P}_{R}\right]=\left(C-N\right)^{2}+C\\\
+\left(2N-C-1\right)\left(2N-C-2\right)\Gamma\left(3/2\right)^{4}\\\
+2\left(2N-C-1\right)\left(\frac{\Gamma\left(C-N+3/2\right)\Gamma\left(3/2\right)}{\Gamma\left(C-N+1\right)}\right)^{2},$
(23)

representing the Pareto frontier of the performance-complexity trade-off
offered by BD-RISs.

##  V Numerical Results

In Fig. 2, we report the Pareto frontier given by (23), delimiting the region
of feasible BD-RIS architectures with $N=64$ elements. This frontier is
compared with the performance-complexity trade-off achieved by the BD-RIS
architectures recently proposed [4, 8]. More precisely, we report group- and
forest-connected RISs, both achieving a performance

$\mathrm{E}\left[\bar{P}_{R}^{\mathrm{Group}}\right]=\frac{N^{2}}{G}+G\left(G-1\right)\left(\frac{\Gamma\left(N/G+1/2\right)}{\Gamma\left(N/G\right)}\right)^{4},$
(24)

and with complexity $C^{\mathrm{Group}}=N(N/G+1)/2$ and
$C^{\mathrm{Forest}}=2N-G$, respectively. Note that (24) is obtained by
setting $N_{g}=N/G$, $\forall g$, in (9). The forest-connected RISs in Fig. 2
have group sizes 2, 4, 8, and 16, while the group-connected RISs have group
sizes 4, 8, and 16 since forest- and group-connected RISs with group sizes 2
are equivalent. Besides, we report fully- and tree-connected RISs, both
achieving

$\mathrm{E}\left[\bar{P}_{R}^{\mathrm{Fully}}\right]=N^{2},$ (25)

and with complexity $C^{\mathrm{Fully}}=N(N+1)/2$ and
$C^{\mathrm{Tree}}=2N-1$, respectively, where (25) is derived by setting $G=1$
in (24). Finally, we report the single-connected RIS architecture, achieving a
performance given by

$\mathrm{E}\left[\bar{P}_{R}^{\mathrm{Single}}\right]=N+N\left(N-1\right)\Gamma\left(3/2\right)^{4},$
(26)

and with complexity $C^{\mathrm{Single}}=N$, where (26) is derived by setting
$G=N$ in (24).

We make the following remarks. First, on the one hand, the single-connected
RIS is the least complex architecture, achieving the lowest performance due to
its limited architecture. On the other hand, the tree-connected RIS allows us
to reach the performance upper bound, with the lowest possible complexity.
Second, forest-connected RISs approach the Pareto frontier, but they are
slightly suboptimal. This is because the groups in forest-connected RISs are
equally sized, i.e., they all have group size $N/G$. However, the optimal
group sizes are not all equal, as given by (20)-(21). Third, the fully-
connected (resp. group-connected) RIS achieves the same performance as the
tree-connected (resp. forest-connected) RIS, but with higher circuit
complexity. Thus, in SISO systems, fully- and group-connected RISs are highly
suboptimal. Note that the exact shape of the Pareto frontier depends on the
channel distribution. Specifically, with Rician or correlated channels, the
gain of the tree-connected over the single-connected RIS decreases, and less
complex BD-RIS architectures are expected to approach the performance upper
bound [4, 7].

##  VI Conclusion

We derive the Pareto frontier for the performance-complexity trade-off in BD-
RISs. This frontier provides the BD-RIS architectures that can be optimally
used to bridge between the single-connected RIS and the tree-connected RIS.
The presented fundamental results are expected to drive the development of
novel BD-RIS architectures in future works.

## Appendix

###  VI-A Proof of Lemma 1

Consider a BD-RIS with circuit complexity $C$ with a corresponding graph
$\mathcal{G}$ that is not a forest, i.e., it has at least one cycle [17].
According to (5), the received signal power achievable by a BD-RIS
architecture solely depends on its number of groups $G$, and their sizes
$N_{1},\ldots,N_{G}$. Thus, by removing one edge from a cycle in
$\mathcal{G}$, the resulting BD-RIS architecture has complexity $C-1$ but
achieves the same performance as the original one since its graph still has
$G$ connected components with sizes $N_{1},\ldots,N_{G}$. Thus, the original
BD-RIS architecture is not optimal.

###  VI-B Proof of Lemma 2

Assume a graph $\mathcal{G}$ to be a forest with $G$ connected components,
with the $g$th component including $N_{g}$ vertices, with
$\sum_{g=1}^{G}N_{g}=N$. Since $\mathcal{G}$ is a forest, each connected
component is a tree and the $g$th component includes $N_{g}-1$ edges [17].
Thus, the number of edges in $\mathcal{G}$ is given by

$L=\sum_{g=1}^{G}\left(N_{g}-1\right)=N-G,$ (27)

proving that $G=N-L$.

###  VI-C Proof of Proposition 1

A BD-RIS architecture with $N$ elements and $C$ tunable impedance components
has a graph with $L=C-N$ edges since $N$ tunable impedance components connect
each RIS element to ground [8]. Besides, we know from Lemma 1 and Lemma 2 that
the graph of the optimal BD-RIS architecture with $N$ elements and complexity
$C$ is a forest, having $G=N-L$ connected components. This proves that
$G=2N-C$.

###  VI-D Proof of Proposition 2

The proof is conducted by induction on the number of groups $G$. As the base
case, we consider $G=2$, where problem (18)-(19) boils down to

$\displaystyle\underset{N_{1},N_{2}}{\mathsf{\mathrm{min}}}\;\;$
$\displaystyle N_{1}N_{2}$ (28) $\displaystyle\mathsf{\mathrm{s.t.}}\;\;\;$
$\displaystyle N_{1}\geq 1,\>N_{2}\geq 1,\>N_{1}+N_{2}=N.$ (29)

The solution to this problem is clearly given by $N_{1}=1$ and $N_{2}=N-1$, or
vice versa. The proposition is consequently verified for the case $G=2$.

As the induction step, we prove that if the proposition is valid for $G-1$
groups, it also holds for $G$ groups. To this end, we rewrite problem
(18)-(19) as

$\displaystyle\underset{N_{1},\ldots,N_{G}}{\mathsf{\mathrm{max}}}\;\;$
$\displaystyle\sum_{g=1}^{G-1}\frac{1}{N_{g}}+\frac{1}{N_{G}}$ (30)
$\displaystyle\mathsf{\mathrm{s.t.}}\;\;\;$ $\displaystyle N_{g}\geq
1,\>\forall g,\>\>\sum_{g=1}^{G-1}N_{g}=N-N_{G}.$ (31)

By the induction hypothesis, we have

$\displaystyle N_{1}=N_{2}=\ldots=N_{G-2}=1,$ (32) $\displaystyle
N_{G-1}=N-N_{G}-G+2.$ (33)

Using (32) and (33), problem (30)-(31) can be simplified as

$\displaystyle\underset{N_{G-1},N_{G}}{\mathsf{\mathrm{min}}}\;\;$
$\displaystyle N_{G-1}N_{G}$ (34) $\displaystyle\mathsf{\mathrm{s.t.}}\;\;\;$
$\displaystyle N_{G-1}\geq 1,\>N_{G}\geq 1,$ (35) $\displaystyle
N_{G-1}+N_{G}=N-G+2,$ (36)

where the only unknown are $N_{G-1}$ and $N_{G}$. By solving this problem as
done for the base case, we obtain $N_{G-1}=1$ and $N_{G}=N-G+1$, proving the
induction step.

## References

  * [1] E. Basar, M. Di Renzo, J. De Rosny, M. Debbah, M.-S. Alouini, and R. Zhang, “Wireless communications through reconfigurable intelligent surfaces,” _IEEE Access_ , vol. 7, pp. 116 753–116 773, 2019.
  * [2] Q. Wu and R. Zhang, “Towards smart and reconfigurable environment: Intelligent reflecting surface aided wireless network,” _IEEE Commun. Mag._ , vol. 58, no. 1, pp. 106–112, 2020.
  * [3] Q. Wu, S. Zhang, B. Zheng, C. You, and R. Zhang, “Intelligent reflecting surface-aided wireless communications: A tutorial,” _IEEE Trans. Commun._ , vol. 69, no. 5, pp. 3313–3351, 2021.
  * [4] S. Shen, B. Clerckx, and R. Murch, “Modeling and architecture design of reconfigurable intelligent surfaces using scattering parameter network analysis,” _IEEE Trans. Wireless Commun._ , vol. 21, no. 2, pp. 1229–1243, 2022.
  * [5] H. Li, S. Shen, M. Nerini, and B. Clerckx, “Reconfigurable intelligent surfaces 2.0: Beyond diagonal phase shift matrices,” _arXiv preprint arXiv:2301.03288_ , 2023.
  * [6] M. Nerini, S. Shen, and B. Clerckx, “Optimal group and fully connected design for beyond diagonal reconfigurable intelligent surfaces,” _arXiv preprint arXiv:2211.06117_ , 2022.
  * [7] ——, “Discrete-value group and fully connected architectures for beyond diagonal reconfigurable intelligent surfaces,” _arXiv preprint arXiv:2110.00077_ , 2021.
  * [8] M. Nerini, S. Shen, H. Li, and B. Clerckx, “Beyond diagonal reconfigurable intelligent surfaces utilizing graph theory: Modeling, architecture design, and optimization,” _arXiv preprint arXiv:2305.05013_ , 2023.
  * [9] H. Li, S. Shen, and B. Clerckx, “Beyond diagonal reconfigurable intelligent surfaces: From transmitting and reflecting modes to single-, group-, and fully-connected architectures,” _IEEE Trans. Wireless Commun._ , vol. 22, no. 4, pp. 2311–2324, 2023.
  * [10] ——, “Beyond diagonal reconfigurable intelligent surfaces: A multi-sector mode enabling highly directional full-space wireless coverage,” _arXiv preprint arXiv:2209.00301_ , 2022.
  * [11] Q. Li, M. El-Hajjar, I. Hemadeh, A. Shojaeifard, A. A. M. Mourad, B. Clerckx, and L. Hanzo, “Reconfigurable intelligent surfaces relying on non-diagonal phase shift matrices,” _IEEE Trans. Veh. Technol._ , vol. 71, no. 6, pp. 6367–6383, 2022.
  * [12] H. Li, S. Shen, and B. Clerckx, “A dynamic grouping strategy for beyond diagonal reconfigurable intelligent surfaces with hybrid transmitting and reflecting mode,” _arXiv preprint arXiv:2210.02499_ , 2022.
  * [13] T. Fang, Y. Mao, S. Shen, Z. Zhu, and B. Clerckx, “Fully connected reconfigurable intelligent surface aided rate-splitting multiple access for multi-user multi-antenna transmission,” in _2022 IEEE ICC Workshops_ , 2022, pp. 675–680.
  * [14] H. Li, S. Shen, and B. Clerckx, “Synergizing beyond diagonal reconfigurable intelligent surface and rate-splitting multiple access,” _arXiv preprint arXiv:2303.06912_ , 2023.
  * [15] B. Wang, H. Li, Z. Cheng, S. Shen, and B. Clerckx, “A dual-function radar-communication system empowered by beyond diagonal reconfigurable intelligent surface,” _arXiv preprint arXiv:2301.03286_ , 2023.
  * [16] D. M. Pozar, _Microwave engineering_. John wiley & sons, 2011.
  * [17] J. A. Bondy and U. S. R. Murty, _Graph theory with applications_. Macmillan London, 1976.
  * [18] L. V. Ahlfors, _Complex analysis: An introduction to the theory of analytic functions of one complex variable_. McGraw-Hill, 1953.


* Sarzi et al. (2007b) Sarzi, M., Shields, J. C., Pogge, R. W., & Martini, P. 2007b, in Astronomical Society of the Pacific Conference Series, Vol. 373, The Central Engine of Active Galactic Nuclei, ed. L. C. Ho & J. W. Wang, 643
  * Schartmann et al. (2010) Schartmann, M., Burkert, A., Krause, M., et al. 2010, MNRAS, 403, 1801
  * Schartmann et al. (2009) Schartmann, M., Meisenheimer, K., Klahr, H., et al. 2009, MNRAS, 393, 759
  * Schawinski et al. (2015) Schawinski, K., Koss, M., Berney, S., & Sartori, L. F. 2015, MNRAS, 451, 2517
  * Schipani et al. (2020) Schipani, P., Campana, S., Claudi, R., et al. 2020, in Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, Vol. 11447, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, 1144709
  * Schnorr-Müller et al. (2016) Schnorr-Müller, A., Davies, R. I., Korista, K. T., et al. 2016, MNRAS, 462, 3570
  * Schulze et al. (2019) Schulze, A., Silverman, J. D., Daddi, E., et al. 2019, MNRAS, 488, 1180
  * Scoville et al. (1983) Scoville, N. Z., Becklin, E. E., Young, J. S., & Capps, R. W. 1983, ApJ, 271, 512
  * Shangguan et al. (2020) Shangguan, J., Ho, L. C., Bauer, F. E., Wang, R., & Treister, E. 2020, ApJ, 899, 112
  * Shimizu et al. (2019) Shimizu, T. T., Davies, R. I., Lutz, D., et al. 2019, MNRAS, 2449
  * Siebenmorgen et al. (2004) Siebenmorgen, R., Krügel, E., & Spoon, H. W. W. 2004, A&A, 414, 123
  * Silverman et al. (2009) Silverman, J. D., Lamareille, F., Maier, C., et al. 2009, ApJ, 696, 396
  * Simões Lopes et al. (2007) Simões Lopes, R. D., Storchi-Bergmann, T., de Fátima Saraiva, M., & Martini, P. 2007, ApJ, 655, 718
  * Smette et al. (2015) Smette, A., Sana, H., Noll, S., et al. 2015, A&A, 576, A77
  * Smith et al. (2007) Smith, J. D. T., Draine, B. T., Dale, D. A., et al. 2007, ApJ, 656, 770
  * Somerville et al. (2008) Somerville, R. S., Hopkins, P. F., Cox, T. J., Robertson, B. E., & Hernquist, L. 2008, MNRAS, 391, 481
  * Speagle et al. (2014) Speagle, J. S., Steinhardt, C. L., Capak, P. L., & Silverman, J. D. 2014, ApJS, 214, 15
  * Stasińska et al. (2008) Stasińska, G., Vale Asari, N., Cid Fernandes, R., et al. 2008, MNRAS, 391, L29
  * Storchi-Bergmann et al. (2000) Storchi-Bergmann, T., Raimann, D., Bica, E. L. D., & Fraquelli, H. A. 2000, ApJ, 544, 747
  * Storchi-Bergmann et al. (2012) Storchi-Bergmann, T., Riffel, R. A., Riffel, R., et al. 2012, ApJ, 755, 87
  * Su et al. (2019) Su, K.-Y., Hopkins, P. F., Hayward, C. C., et al. 2019, MNRAS, 487, 4393
  * Terlevich et al. (1990) Terlevich, E., Diaz, A. I., & Terlevich, R. 1990, MNRAS, 242, 271
  * Thompson et al. (2005) Thompson, T. A., Quataert, E., & Murray, N. 2005, ApJ, 630, 167
  * Tran (1995) Tran, H. D. 1995, ApJ, 440, 597
  * Treister et al. (2012) Treister, E., Schawinski, K., Urry, C. M., & Simmons, B. D. 2012, ApJ, 758, L39
  * Vale Asari et al. (2009) Vale Asari, N., Stasińska, G., Cid Fernandes, R., et al. 2009, MNRAS, 396, L71
  * Vazdekis et al. (2016) Vazdekis, A., Koleva, M., Ricciardelli, E., Röck, B., & Falcón-Barroso, J. 2016, MNRAS, 463, 3409
  * Veilleux & Osterbrock (1987) Veilleux, S. & Osterbrock, D. E. 1987, ApJS, 63, 295
  * Vernet et al. (2011) Vernet, J., Dekker, H., D’Odorico, S., et al. 2011, A&A, 536, A105
  * Vernet & Mason (2009) Vernet, J. & Mason, E. 2009, X-shooter User Manual, 2nd edn., ESO, Karl-Schwarzschild-Str. 2, 85748 Garching bei München, Germany
  * Véron-Cetty & Véron (2010) Véron-Cetty, M. & Véron, P. 2010, A&A, 518, A10+
  * Vogelsberger et al. (2014) Vogelsberger, M., Genel, S., Springel, V., et al. 2014, MNRAS, 444, 1518
  * Vollmer et al. (2008) Vollmer, B., Beckert, T., & Davies, R. I. 2008, A&A, 491, 441
  * Vollmer & Davies (2013) Vollmer, B. & Davies, R. I. 2013, A&A, 556, A31
  * Volonteri et al. (2015) Volonteri, M., Capelo, P. R., Netzer, H., et al. 2015, MNRAS, 449, 1470
  * Wada & Norman (2002) Wada, K. & Norman, C. A. 2002, ApJ, 566, L21
  * Wada et al. (2009) Wada, K., Papadopoulos, P. P., & Spaans, M. 2009, ApJ, 702, 63
  * Wegner et al. (2003) Wegner, G., Bernardi, M., Willmer, C. N. A., et al. 2003, AJ, 126, 2268
  * Wild et al. (2011) Wild, V., Groves, B., Heckman, T., et al. 2011, MNRAS, 410, 1593
  * Xue et al. (2010) Xue, Y. Q., Brandt, W. N., Luo, B., et al. 2010, ApJ, 720, 368
  * Yesuf & Ho (2020) Yesuf, H. M. & Ho, L. C. 2020, ApJ, 901, 42
  * Yuan et al. (2013) Yuan, T. T., Kewley, L. J., & Richard, J. 2013, ApJ, 763, 9
  * Zahid et al. (2011) Zahid, H. J., Kewley, L. J., & Bresolin, F. 2011, ApJ, 730, 137
  * Zhuang et al. (2021) Zhuang, M.-Y., Ho, L. C., & Shangguan, J. 2021, ApJ, 906, 38
  * Zinn et al. (2013) Zinn, P. C., Middelberg, E., Norris, R. P., & Dettmar, R. J. 2013, ApJ, 774, 66
  * Zubovas et al. (2013) Zubovas, K., Nayakshin, S., King, A., & Wilkinson, M. 2013, MNRAS, 433, 3079


EXPERIMENTAL RESULTSsec:experiments Datasets

We evaluate our model on two datasets: a controlled synthetic dataset and a
real-world dataset. We discuss the details of each data preprocessing next.

Table : Post preprocessing datasets statistics

!  Dataset #users #items #actions avg. actions/user Density Synthetic 8,192
2,000 5.8M 710 0.10 Nielsen 12,800 1,302 15.1M 1,179 0.21

Data Synthesis: Verifying a novel method for capturing item-item relationships
in an empirical setting is challenging due to the lack of ground truth. Often
these relationships are not known and could vary drastically from user to
user. Owing to these issues, most studies primarily evaluate the face validity
of the model [kang2018self, chen2018sequential]. The synthetic data allows us
to test various effects and evaluate our model under a controlled environment.
We start by examining our proposed model on synthetic data, comparing it to
benchmarks, and evaluating the characteristics of the model (e.g.,
personalized and universal item-item relationships). Retail market basket data
is one of the well-studied areas [bordalo2013salience]. We follow common
practice in synthesizing sessions to recreate heterogeneous user behaviors and
various item-item relationships [gabel2019p2v, manchanda1999shopping]. We
extract personalized user behaviors from our model using only the basket data,
withholding any information regarding items’ relations or user choice models.
We compare the extracted user behaviors to that of known values in our
simulation. The simulation results validate the model hypothesis and provide
an additional basis for performance under empirical data, where results are
similar and consistently outperform state-of-the-art models. To the best of
our knowledge, no proposed sequential recommender model provides a validated
study on personalized item-item relationship. We next discuss the data
generation schema. The simulation of baskets is as follows: for a basket,
$S^{u}_{t}$, with size $n^{u}_{t}$ purchased by user $u$ at time $t$, first
the user chooses $n^{u}_{t}$ categories from a set of available categories.
Then from each chosen category the user chooses a product $j$. A category $c$
is a set of similar items (e.g., various types of cereal, milk) and categories
are disjoint. For simplicity, each basket can contain at most one item from a
category and not all categories need to be purchased in a single basket. We
use the multivariate normal distribution for simulating category choice model
to capture various types of category-category relationships (e.g., complements
vs. substitutes):

$p^{u}_{ct}=\alpha_{c}+\epsilon^{u}_{ct}$ (1)

where $p^{u}_{ct}$ is probability of purchasing from category $c$ by user $u$
at time $t$, $\alpha_{c}$ is a constant category specific utility, and
$\epsilon^{u}_{ct}\sim\mathcal{N}(0,\Sigma)$. The user chooses $n^{u}_{t}$
categories with highest probability to purchase from at time $t$. Next, we use
multinomial probit model [greene2003econometric] to simulate product choice
within each category, explained in Appendix LABEL:sec:syn_detail. A positive
value in the covariance matrix $\Sigma$ indicates two categories are purchased
together frequently (e.g., milk and cereal), while a negative value represents
contrary of that (e.g., fresh vs. frozen meat). We manually chose a block
diagonal form for the covariance matrix $\Sigma$. Each block represents
categories that have relations, while categories from separate blocks are
independent of each other. We chose various sizes for different blocks (2-3-4)
to represent low-mid-high order relationships between categories. For off-
diagonal values of each block, we manually chose various
positive/zero/negative values to represent
complementary/coincidence/substitute product relationships. Further, we divide
users into multiple disjoint groups. Each group follows a different $\Sigma$
to illustrate a deterministic user heterogeneity on top of the unknown user
specific choice error terms. Heatmaps of $\Sigma$ are illustrated in Fig. . We
synthesize a less dense dataset compared to the real-world data with 8,192
users, 2,000 items, and 5.8M million user-item interactions. Data statistics
are summarized in Table . Further details of parameter values are presented in
Appendix LABEL:sec:syn_detail. Empirical: We use the Nielsen Consumer
Panel111https://www.chicagobooth.edu/research/kilts/datasets/nielseniq-nielsen
dataset. The dataset comprises a representative panel of households. It
includes all household purchases (from any outlet) intended for personal and
at-home use [nielsen]. This is a particularly challenging dataset in terms of
sequential recommendation. Households are geographically dispersed over all
states and demographically balanced to accurately represent the market in each
area. The sessions are from different retailers. Over 4.3 million products in
the dataset cover a variety of items including groceries, health and beauty
aids, and alcohol. The majority of sequential recommenders evaluate their
models on a limited set of users (e.g., within a state), a single retailer
(e.g., a clothing retail or content provider), and a related set of items
(e.g., all movies, or all clothing). We use data from 2014~2019 and randomly
select 12,800 actively participating users with 15M+ user-item interactions
from 50,000+ retailers. The products are grouped into hierarchical categories:
10 departments $\rightarrow$ 118 groups $\rightarrow$ 1,305 modules
$\rightarrow$ 4.3+ million UPCs. We use _Module_ level as items in our
experiment to reduce the sparsity of purchase patterns, and will refer to it
as products in the rest of the paper. We keep one copy of the same item
purchased in multiple quantities in each basket. We exclude items and users
that have less than 10 records in the entire dataset. The statistics of data
are summarized in Table .

###  Experimental Setup

The optimal architecture of PARSRec includes $N=1$ attention layer with $h=2$
heads. We observe that adding extra attention layers does not increase the
performance significantly, presumably because the session lengths are short
and a single transformer is able to induce all the necessary relationships
within a session. Item and user embeddings are the size of $d_{v}=d_{u}=128$.
We initialize the item and user embedding matrices with uniform distributions
of range $[-\frac{1}{\sqrt{|V|}},\frac{1}{\sqrt{|V|}}]$ and
$[-\frac{1}{\sqrt{|U|}},\frac{1}{\sqrt{|U|}}]$, respectively. Other matrix
parameters with size $n\times m$ are initialized with
$\sim\mathcal{N}(0,\frac{2}{n+m})$. Dropout rate is set to 0.1 and mini-batch
size is 256. We used Adam and Sparse Adam optimizers with learning rate 0.001,
$\beta_{1}=0.9$, and $\beta_{2}=0.999$. The gradient is clipped at 30. We use
PyTorch=v1.10.1 to implement the model222Codes for PARSRec:
https://github.com/ehgh/PARSRec.

###  Evaluation Metrics

We use users’ most recent session $S^{u}_{t_{|S_{u}|}}$ for testing, their
second to last session $S^{u}_{t_{|S_{u}|}-1}$ for validation, and the rest
for training. Note that the test set will have validation in its historical
data as well. We predict items in the user’s test basket sequentially (basket
size ¿ 1). For consistency, we adopt a similar strategy to [kang2018self,
sun2019bert4rec, he2017neural, tang2018personalized], where they use a set of
randomly sampled negative items plus ground truth item for evaluation
purposes. We use a set of 100 randomly sampled items (negative and positive)
plus ground truth items and rank these items to get the highest
recommendations for the next item. Negative sampling is suitable in
applications where users are less likely to interact with an item more than
once (e.g., watching movies). However, in applications where users frequently
interact with an item (e.g., grocery shopping, listening to music), evaluating
the model on a pool of negative items (items that the user never interacts
with) would make the prediction task more trivial. We observe that in the
real-world dataset, about 81% of test basket items also appear in the user’s
purchase history. We include positive items in the sampling to resolve this
issue. For evaluation metrics, we report common top-N metrics [kang2018self,
sun2019bert4rec]: Hit Ratio (HR@k) and Normalized Discounted Cumulative Gain
(NDCG@k) with $k\in\\{1,5,10\\}$. NDCG is a rank-aware metric that penalizes
the lower-ranked recommendations. Note that NDCG@1 equals HR@1. Additionally,
we report another metric for session-level evaluation: session precision
(Sess-Prec@k), the average ratio of items predicted accurately within a
session:

$session\ precision=\frac{|\\{{\hat{v}_{j}|\hat{v}_{j}\in
S^{u}_{t}}\\}|}{|S^{u}_{t}|}$ (2)

In other words, session precision is the number of items that are recommended
accurately normalized by the basket size.

###  Benchmarks

To validate the effectiveness of our proposed model, we benchmark it against
the following baselines:

  * •

POPRec: A basic benchmark that recommends items based on their frequency of
interactions by users.

  * •

SASRec [kang2018self]: It uses one-directional transformers for sequential
recommendation. We modified negative sampling to sampling explained in Section
for fair comparison.

  * •

BERT4Rec [sun2019bert4rec]: It applies bi-directional transformers with Cloze
objective to sequential recommendation, and achieves state-of-the-art
performance on many datasets.

We omit comparison with some other benchmarks like GRU4Rec
[hidasi2015session], GRU4Rec+ [hidasi2018recurrent], BPR [rendle2012bpr],
NCF[he2017neural], and FPMC [rendle2010factorizing] that have been
outperformed by above methods on various real-world datasets [kang2018self,
sun2019bert4rec]. We use the code provided by the corresponding authors for
benchmark models. We consider latent dimension sizes
$d_{v}\in\\{16,32,64,128,256\\}$ for methods that include embeddings. The
dropout rate is chosen from $\\{0,0.1,...,0.5\\}$. We set $N=820$ (full
sequence length) for synthetic dataset and $N=1000$ ($\sim$median of sequence
length) for Nielsen dataset in SASRec and BERT4Rec that require setting
sequence length. We either tuned all hyper-parameters on the validation set or
referred to benchmarks’ authors suggestions for optimal values. The reported
results are under their optimal set of hyper-parameter values.

Table : Performance comparison of all benchmarks. Boldface and underlined
values in each row represent the best and second best performances,
respectively. Improvements of best to second best model are presented in the
last column.

!  Dataset Metric POPRec SASRec BERT4Rec PARSRec Improvement 8*Synthetic HR@1
0.0005 0.1816 0.1963 0.2136 8.8% HR@5 0.0028 0.3919 0.4150 0.4791 15.4% HR@10
0.0066 0.5133 0.5441 0.5825 7.0% NDCG@5 0.0013 0.2872 0.3061 0.3489 13.9%
NDCG@10 0.0026 0.3253 0.3426 0.3800 10.9% Sess-Prec@1 0.0005 0.1826 0.1974
0.2249 13.9% Sess-Prec@5 0.0029 0.3931 0.4163 0.4784 14.9% Sess-Prec@10 0.0068
0.5151 0.5357 0.5792 8.1% 8*Nielsen HR@1 0.0008 0.1663 0.1761 0.2444 38.8%
HR@5 0.0921 0.4235 0.4833 0.5934 22.7% HR@10 0.1620 0.5771 0.6580 0.7355 11.7%
NDCG@5 0.0454 0.2991 0.3290 0.4208 27.9% NDCG@10 0.0680 0.3497 0.3987 0.4632
16.1% Sess-Prec@1 0.0008 0.1669 0.1856 0.2753 48.3% Sess-Prec@5 0.0919 0.4197
0.4790 0.6093 27.2% Sess-Prec@10 0.1632 0.5729 0.6344 0.7439 17.2%

[t].4 [width=]images/cov_avg_mat_synthetic_data.pdf Covariance matrix of
category purchases [t].4 [width=]images/cov1_mat_synthetic_data.pdf A
submatrix of covariance matrix for user group one [t].4
[width=]images/cov2_mat_synthetic_data.pdf A submatrix of covariance matrix
for user group two [t].4 [width=]images/cov_diff_mat_synthetic_data.pdf
Difference in the subset of covariance matrix between two user groups [t].4
[width=]images/heatmap_50.pdf Category attention weights difference of two
user groups [t].4 [width=]images/attention_layer_0_top_5.pdf Average category
attention weights learned by ParsRec [t].4
[width=]images/attention_layer_0_grp_1_top_5.pdf Attention weights of
categories of user group one [t].4
[width=]images/attention_layer_0_grp_2_top_5.pdf Attention weights of
categories of user group two [t].4
[width=]images/attention_layer_0_grp1-2_top_5.pdf Category attention weights
difference of two user groups [t].4 [width=]images/sample.pdf Attention
weights of sample items in empirical data

Figure : Average category purchase covariance matrix $\Sigma$ of all users
Figure : A submatrix of $\Sigma_{A}$ of user group $A$ Figure : A submatrix of
$\Sigma_{B}$ of user group $B$ Figure : $\Sigma_{A}-\Sigma_{B}$, difference of
user groups $A$ and $B$ Figure : Item embeddings self-dot product heatmap
($\textbf{E}^{V}\cdot{\textbf{E}^{V^{T}}}$) Figure : Average category
attention weights learned by PARSRec Figure : Attention weights of
corresponding categories in () of user group $A$ Figure : Attention weights of
corresponding categories in () of user group $B$ Figure : Category attention
weights difference of user groups $A$ and $B$ Figure : Empirical data: Average
attention weights of items for users with babies Figure : Simulation and
empirical heatmaps: (a) Average covariance matrix $\Sigma$ of category
purchases $p^{u}_{ct}\sim\mathcal{N}(\alpha_{c},\Sigma)$ in data synthesis. A
positive value in $\Sigma$ indicates two categories are purchased together
frequently (e.g. milk and cereal), while a negative value represents contrary
of that. (b, c) A subset of covariance matrix for user groups $A$ and $B$, (d)
difference of (b) and (c), (e) Item embedding self-dot-product shows embedding
has learned global item categories and relationships. (f) Average category
attention weights learned by the model. Higher values correspond to positive
values in (a) while lower values correspond to zero/negative values in (a),
(g, h) Category attention weights for selected categories in (b, c), the
matching of (b¡-¿g) and (c¡-¿h) illustrates that model can learn personalized
attention. Values ¡ 0.05 are filtered for clarity, (i) difference between (g)
and (h). The high values matches Fig. (d). (j) Attention weights of sample
products in empirical data for a group of users with babies. The network
learns correct relations without prior knowledge of users or products (Color
represents sign and intensity represents value. Annotations in (a) and (f) are
scaled by 10 for readability. All other annotations illustrate the true values
of the cell. Figure best viewed in color. Axis label colors are for
readability)

Performance Comparison: Table  summarizes the recommendation performance of
all benchmarks as well as our proposed model on synthetic and Nielsen
datasets. The last column shows the statistically significant improvements of
the best model to the second-best model. We observe that POPRec has the lowest
performance, presumably because it does not look into user-specific behaviors.
SASRec uses transformers and performs lower than BERT4Rec because it only
looks at item relationships from left to right. BERT4Rec also uses
transformers but in a bidirectional setting that allows learning from both
right and left. PARSRec performs consistently better than all methods on both
datasets. It is likely because PARSRec differentiates between interactions
within a session and interactions in the past sessions by using RNN blocks. It
also uses explicit user queries in its attention blocks to learn personalized
item-item relationships which is explained more in detail in Section . PARSRec
gains an average of 19.1% HR@5, 20.9% NDCG@5, and 21.1% Sess-Prec@5
improvement over the second-best benchmark.

###  Discussion

The key deliverable of our study was to develop a personalized recommendation
system that accounted for patterns of individual preferences over time and
item relationships. The model developed here can be applied to multiple
scenarios, from populating song lists to basket completion exercises. The
model’s success hinges on its ability to address two key questions: (1) how
does PARSRec capture personalized item-item relationships? and (2) how does
learning personalized item-item relationships affect the recommendation?

####  Extracting Personalized Item Relationships

Recommender systems follow one of the two common methods to capture
heterogeneous user behaviors: _i)_ learn an explicit user representation based
on the user behavior [tang2018personalized, rendle2010factorizing]; _ii)_
implicitly represent users by aggregating the embeddings of user interacted
items [kang2018self, sun2019bert4rec, hidasi2015session, hidasi2018recurrent,
he2016fusing]. PARSRec takes the former approach by learning an explicit user
embedding. Recently, the attention layers of transformers in the state-of-the-
art recommender systems provide an explainable visual for item-item
relationships. These models (e.g., BERT4Rec [sun2019bert4rec], and SASRec
[kang2018self]) often use a self-attention layer where all key, value, and
query parameters consist of item embeddings (implicit user representation).
Hence, they learn global item-item relationships that differentiate users via
their purchase history. However, in PARSRec the query consists of explicit
user embeddings (plus user purchase history, if available). This allows for
the network to explicitly learn and visualize the personalized item-item
relationships. To validate this capability, we conduct a controlled simulation
on the synthetic dataset. We split users into various groups and each group
has a different category covariance matrix, $\Sigma$, during data synthesis.
fig:cov_full,fig:cov1,fig:cov2,fig:cov_diff illustrate the heatmaps (of a
subset) of $\Sigma$ for two different user groups $A$, and $B$ (along with
their average and difference). We then extract the highest attention weights
of each user at every step of the training phase (averaged on attention
heads). Note that we only extract weights of the valid non-padding items. We
aggregate the item-item attention weights to category level for ease of
comparison and readability. We perform row-wise sum followed by column-wise
average within each category, then row-wise normalization over all items for
each user individually. fig:att_full,fig:att1,fig:att2,fig:att_diff show the
heatmaps of the category level attention weights for two different user groups
$A$ and $B$, and their average and difference. Further, Figure  represents the
heatmap of dot-product of item embedding with itself
($\textbf{E}^{V}\cdot{\textbf{E}^{V^{T}}}$). We observe following traits from
the figures:

  * [noitemsep,topsep=0pt,leftmargin=*]

  * •

() vs. (): We expect the attention weights in () to capture the average
category relations for all users corresponding to Figure (). We observe that
there is a correlation between attention weights and covariance matrices.
Higher attention weights correspond to larger positive covariance values, and
near-zero attention weights correspond to the negative covariance values. We
also observe that attention weights capture category independence in the form
of block diagonal matrices. Note that the network has no prior knowledge of
item categories, and user-item interactions are the only information
introduced to the network.

  * •

(, , ) vs. (, , ): We observe that PARSRec can learn user heterogeneity by
accurately extracting different user groups’ attention weights. We see a one-
to-one match between user groups’ covariance matrices in (, ) and their
corresponding attention weights in (, ). For easier comparison, we include
their differences in (). The cells with higher absolute values in Figure ()
match the differences in Figure (). Note that the network has no prior
knowledge of user groups and infers their difference via user behavior.

  * •

() vs. (): The global item-item similarity (i.e. dot-product) matches the
average relationships of items. We observe the similarity of items within each
category illustrated by blue colors. This is because in data synthesis, a user
interacts with at most one item per category during a session, and items
within a category are expected to have similar embedding. () also shows a
matching pattern with global category correlations where red cells match high
positive category covariance values and blue cells match low positive or
negative covariace values. Note that unlike attention weights, item embeddings
are learned relative to other item embeddings. E.g., categories 14 and 16 show
similarities in Figure () (blue color) even though they have a positive but
relatively lower correlation compared to category pairs 14-15 and 15-16 (red
color). However, attention weights of categories 14 and 16 are captured
positively in Figure (). () shows that the model learns the item similarities
globally to some extent. However, item representations alone cannot present
personalized item relationships like the attention layer does.

[t].49 [width=]images/prediction_sales.pdf estimating sales [t].49
[width=]images/mape.pdf Sales estimation MAPE

Figure : Sales estimation of different categories for user groups A and B
Figure : Sales estimation MAPE Figure : Estimating the influence of removing
category $C_{0}$ (present at training phase) from the assortment at testing
phase on sales of categories $C_{1}$ and $C_{2}$ for two user groups.
Cov($C_{0}$,$C_{2}$)=0.6 for user group A. Other covariances are zero. PARSRec
captures category spillover effects.

Empirical Attention Between Items: The empirical dataset lacks the ground
truth for user behavior. However, we can look into item relationships learned
by the network. Figure () shows the average of a subset of attention weights
between items for a group of users who have babies in the Nielsen dataset. We
observe that the network learns to separate different product groups related
to each other without prior knowledge of users or item categories. The network
also identifies subgroups of related items within a category (e.g., {baby bath
products, baby lotion} vs. {baby bottle, baby burp cloth, baby accessory})
even though they occur in the same sessions.

####  Effect of Personalized Recommendation

To investigate the importance of learning personalized item-item relationships
in making recommendations, we conduct a controlled simulation on the synthetic
dataset. We drop a product category from the pool of products and observe its
consequences on other categories’ sales. For example, it is observed when a
retailer discontinues tobacco and cigarettes, they face a cross-category
spillover effect on other products such as alcoholic beverages
[goli2021happens]. We mimic the real-world behavior in our simulation as
follows: 1) we assume the assortment contains all products during training and
validation phase, 2) we remove baskets that contain the dropped category
$C_{0}$ from the _test set_ and also from the pool of products _during testing
phase_ , and 3) we estimate the unit sales of two types of categories for two
user groups during testing phase using top 10 recommendations. Category
$C_{1}$ is independent of $C_{0}$ for both user groups. Category $C_{2}$ is
highly correlated with $C_{0}$ for user group $A$ (cov=0.6), but independent
of $C_{0}$ for user group $B$ (cov=0). Figure  shows the estimates of category
sales for each user group, and Figure  shows Mean Absolute Percentage Error
(MAPE) of sales. We observe that PARSRec accurately distinguishes the spill
over effect of $C_{0}$ removal on categories $C_{1}$ and $C_{2}$. PARSRec
estimates the cross-category drop in sales of category $C_{2}$ for user group
$A$ (MAPE=3.5%) and uninfluenced sales of $C_{2}$ for user group $B$
(MAPE=1%). It also accurately estimates the sales of the independent category
$C_{1}$ for both user groups (MAPE=3.8% and 3.7%). It is important to note
that all training/validation sets include category $C_{0}$ and only the test
set is subject to change. Without any prior training on category removal
effects, the proposed model can predict the user behavior by learning
personalized item-item relationships. This allows retailers to conduct
simulated experiments on assortment modifications and estimate their effect on
different customers without the costs of applied experiments.

##  1 Ablation Study

Table : Ablation analysis (NDCG@10 and Sess-Prec@10) of synthetic and
empirical dataset. An increase in performance from the default PARSRec setting
is emphasized in bold.

!  2*Architecture Synthetic Nielsen Sess-Prec@10 NDCG@10 Sess-Prec@10 NDCG@10
PARSRec default 0.5792 0.3800 0.7439 0.4632 Remove LN 0.5756 0.3746 0.6775
0.4183 Remove Dropout 0.5780 0.3775 0.7356 0.4553 Remove Q in LN 0.5643 0.3745
0.7400 0.4601 #Att Layers=2 0.5506 0.3622 0.7320 0.4543 #heads=1 0.5769 0.3781
0.7399 0.4602 #heads=4 0.5790 0.3799 0.7431 0.4628 FFN pre-RNN 0.5723 0.3775
0.7426 0.4637 FFN post-RNN 0.5009 0.3362 0.6900 0.4189 Extra Features - -
0.7591 0.4759

We conduct an ablation study to understand the impact of various components of
PARSRec and some variations in the design of the network. Table 1 summarizes
the performance of the optimal model and eight variants on both synthetic and
empirical datasets. All other hyper-parameters are unchanged. The variants are
as follows: (1,2) _Remove LN, Dropout_ : Including both components help
improve the performance, with LN being more prominent on empirical dataset.
(3) _Remove Q from LN_: Adding Q at LN increases the accuracy. It carries the
user history and is beneficial to add it to RNN input. (4) _Number of
Attention Layers_ : Stacking more attention layers achieves similar
performance on the empirical dataset but performs lower on the synthetic
dataset. Presumably, because the sessions are short and single layer attention
is sufficient to learn the relationship of items within a session. Longer
sequences might pose more complex patterns and require more layers. (5)
_Number of heads in Multi-Head Attention_ : The results show that increasing
the number of heads beyond two does not significantly boost performance,
presumably because of small session lengths. Longer sessions might benefit
from more number of heads. (6) _FFN pre-RNN input_ : We explore adding layers
of Feed-Forward Network right before the input of RNN. The results show that
the added FFN has a similar performance. It is likely that the projection
layer of the attention mechanism extracts the required features, and adding
extra layers is redundant. (7) _FFN post-RNN output_ : Adding FFN after RNN
output significantly decreases the performance, possibly due to overfitting.
The optimal dimension of RNN is satisfactory for output prediction. (8) _Extra
User Features_ : We explore adding extra user and session features from the
empirical dataset. We pass continuous features through a Multi-Layer
Perceptron and further concatenate them with the user and categorical
features’ embeddings to use as the initial hidden state. Features include
income, age, gender, location, retailer id, day of the week of session,
household size and composition, user education, marital status, and race.
These features contribute slightly to improving performance ($\sim$2%
increase). This confirms that the personalized model learns user features that
contribute to the recommendation task via user embedding.