# Deep Rating Elicitation for New Users in Collaborative Filtering

Wonbin Kweon, SeongKu Kang, Junyoung Hwang, Hwanjo Yu  Pohang University of
Science and Technology, South Korea {kwb4453, seongku, jyhwang,
<EMAIL_ADDRESS>
(2020)

###### Abstract.

Recent recommender systems started to use rating elicitation, which asks new
users to rate a small seed itemset for inferring their preferences, to improve
the quality of initial recommendations. The key challenge of the rating
elicitation is to choose the seed items which can best infer the new users’
preference. This paper proposes a novel end-to-end Deep learning framework for
Rating Elicitation (DRE), that chooses all the seed items at a time with
consideration of the non-linear interactions. To this end, it first defines
categorical distributions to sample seed items from the entire itemset, then
it trains both the categorical distributions and a neural reconstruction
network to infer users’ preferences on the remaining items from CF information
of the sampled seed items. Through the end-to-end training, the categorical
distributions are learned to select the most representative seed items while
reflecting the complex non-linear interactions. Experimental results show that
DRE outperforms the state-of-the-art approaches in the recommendation quality
by accurately inferring the new users’ preferences and its seed itemset better
represents the latent space than the seed itemset obtained by the other
methods.

Recommender System, Initial Recommendation, Cold Start

††journalyear: 2020††copyright: iw3c2w3††conference: Proceedings of The Web
Conference 2020; April 20–24, 2020; Taipei, Taiwan††booktitle: Proceedings of
The Web Conference 2020 (WWW ’20), April 20–24, 2020, Taipei, Taiwan††doi:
10.1145/3366423.3380042††isbn: 978-1-4503-7023-3/20/04††ccs: Information
systems Collaborative filtering††ccs: Computing methodologies Learning from
implicit feedback††ccs: Computing methodologies Active learning settings

##  1\. Introduction

Making accurate initial recommendations for newly joined users (so-called
cold-start users) has remained a long-standing problem in recommender systems
(RS) (Schein et al., 2002). To infer the preferences of new users who have not
interacted with any item yet, most methods have resorted to user side
information such as demographic profiles (e.g., age, gender, and profession)
(Zhang et al., 2014) and social relationships (Lin et al., 2013; Sedhain et
al., 2017). Nowadays, however, collecting personal information is challenging
due to privacy issues, and a large number of users are reluctant to provide
their private information to the website (Antón et al., 2002).

Figure 1. Rating elicitation of Netflix. When a new user signs up, Netflix
shows 78 seed items to the new user.222It is captured on Oct. 10, 2019

To overcome this limitation, a few recent work have focused on rating
elicitation (Rashid et al., 2008; Liu et al., 2011; Fonarev et al., 2016;
Rashid et al., 2002), which asks new users to rate a small seed itemset, to
infer their preferences without using any personal information. In Figure 2,
for example, Netflix initially shows some seed items to newly joined users and
asks them to choose their favorite items. Afterward, Netflix provides
personalized recommendations based on the chosen items by each user. Since RS
should keep the size of seed itemset small not to bother new users, the key
challenge is to find small seed itemset that can provide enough information to
infer new users’ preferences.

Early methods for selecting the seed itemset (Rashid et al., 2002; Rashid et
al., 2008) have focused on the statistic-based scoring strategy that measures
how representative each item is and selects top-$k$ items as the seed set.
They design score function based on items’ popularity or variance (or entropy)
of ratings. However, those methods do not consider the interactions between
the seed items, which might result in redundant selection and further poor
recommendation accuracy.

To tackle this challenge, several recent work (Liu et al., 2011; Fonarev et
al., 2016) focus on the maximal-volume approach which finds the most
representative combination of item latent vectors. Specifically, they first
define the amount of the representativeness as the volume of the
parallelepiped spanned by the linear combination of selected latent vectors.
Then, they adopt a greedy fashion that adds representative items into the set
one by one. After finding the seed itemset, they predict new users’
preferences for the remaining items by linearly aggregating their feedback on
the seed items. This approach achieves state-of-the-art recommendation
performance on the rating elicitation task.

Despite their effectiveness, we argue that the existing methods are not
sufficient to yield satisfactory performance for the following reasons. First,
they only consider the linear interactions between the items both for finding
the seed itemset and inferring the new users’ preferences, which may not be
sufficient to capture the complex structure of the collaborative filtering
(CF) information (i.e., the user-item interactions). Second, they adopt the
greedy approach that makes use of the best short-term choice at each step,
which cannot take into account the interactions of the whole seed items at a
time, and may further degrade the quality of recommendation.

In this paper, we propose a novel end-to-end Deep learning framework for
Rating Elicitation (DRE) that chooses all the seed items at a time with
consideration of the non-linear interactions between the items. To this end,
DRE first defines the same number of categorical distributions as the number
of seed items, and samples each seed item from each distribution. DRE then
trains both the categorical distributions and a neural reconstruction network
to infer the users’ preferences on the remaining items from CF information of
the sampled seed items. Through the end-to-end training, the categorical
distributions are learned to select the most representative set of items while
reflecting the non-linear interactions of the seed items. Lastly, DRE provides
personalized initial recommendations for new users by using the trained
reconstruction network and their feedback on the seed itemset.

However, sampling the seed items is a non-differentiable operation which would
block the gradient flow and disable the end-to-end training. DRE uses a
continuous relaxation of discrete distribution, Gumbel-Softmax (Jang et al.,
2016) whose parameter gradients can be computed via the reparameterization
trick and trained by the backpropagation. With the relaxation, DRE
successfully incorporates the non-differentiable operation into the network
and takes the benefits of the end-to-end training.

Our extensive experiments demonstrate that DRE outperforms all other
baselines. DRE finds the seed itemset that best infers the preference of new
users, and provides more accurate initial recommendations based on their
feedbacks than the state-of-the-art method does. Furthermore, we qualitatively
show that the seed itemset obtained by DRE is capable of better representing
the latent space without the redundancy compared to the other methods. We
provide the source code of DRE for
reproducibility.333https://github.com/WonbinKweon/DRE_WWW2020

##  2\. Problem Formulation

Let the set of users and items be denoted as $U=\\{u_{1},u_{2},...,u_{n}\\}$
and $V=\\{v_{1},v_{2},...,v_{m}\\}$ where $n$ and $m$ are the number of users
and items, respectively. Let $R$ $\in\mathbb{R}^{n\times m}$ denote the user-
item rating matrix. As we focus on implicit feedback, each element of $R$ has
a binary value indicating whether a user has interacted with an item or not.
Let $r^{(u)}$ $\in\mathbb{R}^{m}$ denote the user rating vector (i.e., $u$-th
row of $R$). We define seed itemset as a set of items that we ask new users to
rate when they sign up for the recommender system. The set of indices of the
seed items is denoted as $S$ with $\lvert S\rvert=k$. We also define candidate
items as all items except the seed items.

Rating elicitation can be divided into three steps: (1) Select the seed
itemset $S$ with rating history of training users (2) Elicit ratings
$z^{(u)}\in\mathbb{R}^{k}$ on $S$ from a new user (3) Predict the ratings of
the new user on the candidate items and provide initial recommendations. Thus,
we are interested in finding the optimal seed itemset $S$ and a reconstruction
function $f_{\theta}(\cdot)$ by solving below optimization problem.

(1)
$\operatorname*{min}_{S,\theta}\frac{1}{2}\|R-f_{\theta}(R[:,S])\|^{2}_{F}.$

Note that $R[:,S]\in\mathbb{R}^{n\times k}$ is in the numpy indexing
notation444https://docs.scipy.org/doc/numpy-1.13.0/reference/arrays.indexing.html,
which means we take a submatrix of $R$ by taking only $k$ columns with the
indices in $S$. Thus, $R[:,S]$ is the rating matrix of the seed itemset $S$.
Then the reconstruction function $f_{\theta}(\cdot)$ predicts the ratings of
the candidate items by reconstructing $R$ from $R[:,S]$. In this paper, we
call the reconstruction function $f_{\theta}(\cdot)$ a decoder.

##  3\. Preliminaries

In this section, we introduce existing maximal-volume approaches for selecting
the seed itemset (Section 3.1) and the Gumbel-Softmax which allows the
sampling process of DRE to be differentiable for the backpropagation (Section
3.2).

###  3.1. Maximal-Volume Approaches

The state-of-the-art maximal-volume approaches (Liu et al., 2011; Fonarev et
al., 2016) are proposed to find the seed itemset with consideration of the
linear interactions between the seed items. They find the seed itemset and the
decoder by solving the following optimization problem

(2) $\displaystyle\min_{S,X}$ $\displaystyle\frac{1}{2}\|R-R[:,S]X\|^{2}_{F},$

where $X\in\mathbb{R}^{k\times m}$ corresponds to the decoder. They first
reduce the dimensionality of column space of $R$ from $n$ to $k$ by using the
rank-$k$ Singular Value Decomposition (SVD)

(3) $R=UV^{T},\quad\text{where }U\in\mathbb{R}^{n\times k}\text{ and
}V^{T}\in\mathbb{R}^{k\times m}.$

Then they select $k$ representative columns (i.e., the items) of $V^{T}$ that
can represent all the remaining columns. To this end, they adopt Maxvol
algorithm (Goreinov et al., 2010) which searches for the columns that maximize
the volume of the parallelepiped spanned by the linear combination of them. To
maximize the volume, the columns should have large norms and should be evenly
distributed to prevent linear dependency. Maxvol algorithm adds representative
items into $S$ one by one in a greedy fashion, because finding the globally
optimal $S$ and $X$ is NP-hard (Fonarev et al., 2016). After finding $S$, they
compute the decoder $X$ with pseudo-inverse of $R[:,S]$ as
$X=(R[:,S]^{T}R[:,S])^{-1}R[:,S]^{T}R$. Lastly, they predict a rating vector
of a new user based on the elicited feedback $z^{(u)}$ and the decoder $X$ by
$\hat{r}^{(u)}=z^{(u)}X$. By sorting the predicted ratings on the candidate
items, they provide initial recommendations to the new user.

Overall, the maximal-volume approaches have two intrinsic flaws. First, they
cannot capture the non-linear interactions among the seed items, because both
Maxvol algorithm and the decoder $X$ only consider the linear interactions of
the column vectors. It may not be sufficient to capture the complex structure
of the CF information. Second, they adopt the greedy search that incrementally
increases the seed itemset, which cannot consider the interactions of the
whole seed items at a time. As a result, they may fall into the local optimum
and fail to provide accurate recommendations.

###  3.2. Gumbel-Softmax

Gumbel-Softmax (Jang et al., 2016) is a continuous distribution on the simplex
that can approximate samples from a categorical distribution. If there is a
categorical distribution with class probability
$\pi=[\pi_{1},\pi_{2},...,\pi_{m}]$ for $m$ classes, we can express a
categorical sample as a $m$-dimensional one-hot vector. Gumbel-Max trick
(Maddison et al., 2014) introduces a simple way to draw a sample $y$ from the
categorical distribution with class probability $\pi$:

(4)
$y=\textrm{one\\_hot}\left(\operatorname*{arg\,max}_{j}[g_{j}+\textrm{log}\pi_{j}]\right),$

where $g_{j}$ is i.i.d drawn from Gumbel distribution with $\mu=0$,
$\beta=1$555$g_{j}=-\text{log}(-\text{log}(u))$, where $u$ is sampled from
$Uniform(0,1)$. Gumbel-Softmax uses the softmax function as a continuous
approximation of $\operatorname*{arg\,max}$ operation, and get the
approximated one-hot representation of the sample $y$:

(5)
$y_{j}=\frac{\textrm{exp}((\textrm{log}\pi_{j}+g_{j})/\tau)}{\Sigma_{l=1}^{m}\textrm{exp}((\textrm{log}\pi_{l}+g_{l})/\tau)}\quad\textrm{for
}j=1,...,m,$

where $\tau$ is a hyper-parameter for the temperature of the softmax. If we
take very small $\tau$, $y\in\mathbb{R}^{m}$ will become one-hot and Gumbel-
Softmax distribution becomes identical to the categorical distribution. In
this paper, we want to sample $k$ seed items from $k$ different categorical
distributions. Therefore, we extend $\pi$ and $y$ to the 2-dimensional matrix
from the 1-dimensional vector. Then we have $\Pi\in\mathbb{R}^{k\times m}$ and
$Y\in\mathbb{R}^{k\times m}$. Each row of $\Pi$ represents the class
probability of a categorical distribution and each row of $Y$ represents the
approximated one-hot representation from each categorical distribution.

##  4\. Method

Our proposed end-to-end Deep learning framework for Rating Elicitation (DRE)
chooses all the seed items at a time while considering non-linear interactions
of the items. DRE consists of two modules: an encoder and a decoder, as
illustrated in Figure 2. The encoder is a module for selecting the seed
itemset and the decoder is a module for predicting the ratings for the
candidate items by reconstructing the user rating vector $r^{(u)}$ from the
feedback on the seed itemset $z^{(u)}$.

Figure 2. The architecture of DRE. $r^{(u)}$ is a user rating vector, $\Pi$
and $Y$ are introduced in Section 3.2. In the Figure, $Y\in\mathbb{R}^{2\times
4}$ is a concatenation of two one-hot vectors $[0,0,1,0]$ and $[1,0,0,0]$ from
Gumbel-Softmax of $\Pi$ and $g$. After multiplying $Y$ and $r^{(u)}$,
$z^{(u)}$ has the third and the first values of $r^{(u)}$, which are the green
circle and the red circle.

###  4.1. Encoder

The encoder samples $k$ seed items with a matrix $\Pi\in\mathbb{R}^{k\times
m}$ which consists of $k$ trainable categorical distributions. Each row
$\Pi_{i}$ represents the class probability of a $m$-dimensional categorical
distribution. We sample one item from each row $\Pi_{i}$, so that we draw $k$
items in total. However, the sampling process is non-differentiable, which
would block the gradient flow and disable the end-to-end training. We adopt a
continuous relaxation of the discrete distribution by using Gumbel-Softmax.
With the relaxation, the categorical distributions $\Pi$ can be trained by the
backpropagation.

We get $Y\in\mathbb{R}^{k\times m}$ from $\Pi$ and $g$ by using Gumbel-Softmax
as

(6)
$Y_{ij}=\frac{\textrm{exp}((\textrm{log}\Pi_{ij}+g_{ij})/\tau)}{\Sigma_{l=1}^{m}\textrm{exp}((\textrm{log}\Pi_{il}+g_{il})/\tau)}\quad\textrm{for
i}=1,...,k,\textrm{ j}=1,...,m.$

With small $\tau$, $Y_{i}\in\mathbb{R}^{m}$ is an approximation of an
$m$-dimensional one-hot vector sampled from the categorical distribution with
class probability $\Pi_{i}$. In the same manner, $Y\in\mathbb{R}^{k\times m}$
consists of $k$ approximated one-hot vectors. Then we get
$z^{(u)}\in\mathbb{R}^{k}$ by multiplying $Y$ and $r^{(u)}$

(7) $z^{(u)}=Y\cdot r^{(u)}.$

Note that $z^{(u)}$ has the $k$ elements of $r^{(u)}$, because each row of $Y$
is a one-hot vector. Therefore, we can treat $z^{(u)}$ as ratings on the seed
items.

###  4.2. Decoder

The decoder $f_{\theta}(\cdot)$ reconstructs user rating vector $r^{(u)}$ from
the feedback $z^{(u)}$ by using the non-linear interactions between the seed
items. To this end, we use the fully-connected neural network that is widely
used in autoencoder-based CF methods to reconstruct user rating vectors
(Sedhain et al., 2015; Wu et al., 2016; Li and She, 2017; Liang et al., 2018).

In this paper, we reconstruct $r^{(u)}$ with a 2-layer fully-connected network

(8) $\begin{split}h^{(u)}=\sigma(W_{1}^{T}z^{(u)}+b_{1})\in\mathbb{R}^{d}\\\
\hat{r}^{(u)}=\sigma(W_{2}^{T}h^{(u)}+b_{2})\in\mathbb{R}^{m},\end{split}$

where $\sigma$ is the sigmoid function, $W_{1}\in\mathbb{R}^{k\times d}$ and
$W_{2}\in\mathbb{R}^{d\times m}$ are weight matrices, $b_{1}\in\mathbb{R}^{d}$
and $b_{2}\in\mathbb{R}^{m}$ are biases for the fully-connected layers, $k$ is
the size of the seed itemset, $d$ is the dimension of the hidden layer and $m$
is the number of all items.

###  4.3. Model Training

After the decoder reconstructs the user rating vector, we compute Mean Squared
Error (MSE) loss for the end-to-end training of DRE.

(9)
$\operatorname*{min}_{\Pi,\theta}\mathcal{L}=\frac{1}{|U_{T}|}\displaystyle\sum_{u\in
U_{T}}\|r^{(u)}-\hat{r}^{(u)}\|^{2}_{F},$

where $\Pi$ represents the categorical distributions of the encoder, $\theta$
denotes all parameters of the decoder, and $U_{T}$ is a set of training users.
Note that $\Pi$ and $\theta$ are trained together in the end-to-end manner
with the backpropagation. Through the end-to-end training, $\Pi$ is learned to
select the most representative set of items while reflecting the non-linear
interactions of the items.

Since we have to deal with thousands of items, we use simple exponential
annealing for $\tau$ as $\tau=T_{0}(\frac{T_{E}}{T_{0}})^{\frac{e}{E}}$, where
$e$ is the current epoch, $E$ is the number of training epochs, $T_{0}$ is
initial temperature and $T_{E}$ is the last temperature $(T_{0}>>T_{E})$. With
a large $\tau$ the model can explore the combinations of the whole itemset,
with annealed small $\tau$ the model can select seed itemset.

After the training is done, we re-train the decoder with the fixed encoder for
small epochs. Finally, we can extract the seed itemset from the trained $\Pi$.
Since $\Pi_{i}$ represents the class probability of an $m$-dimensional
categorical distribution, we can extract the final seed items by taking the
index with the maximal probability from each distribution

(10)
$S_{i}=\operatorname*{arg\,max}_{j\in\\{1,...,m\\}}\Pi_{ij}\quad\textrm{for
i}=1,...,k,$

where $S_{i}$ is the $i$-th seed item.

###  4.4. Recommendation for New Users

When a new user $u$ signs up for the recommender system, we ask the new user
to rate the seed itemset $S$. After getting feedback $z^{(u)}$ on the seed
itemset, we predict the ratings for the candidate items by using the trained
decoder $f_{\theta}(\cdot)$

(11) $\hat{r}^{(u)}=f_{\theta}(z^{(u)})\in\mathbb{R}^{m}.$

Finally, we provide a top-N recommendation by sorting $\hat{r}^{(u)}$ in a
descending order.

##  5\. Experiments

In this section, we present experimental results supporting that DRE
outperforms state-of-the-art approaches in various aspects.

###  5.1. Datasets

We use four real-world datasets of MovieLens
1M666https://grouplens.org/datasets/movielens/, CiteULike (Wang et al., 2013),
Yelp (He et al., 2016) and MovieLens 20M. For the explicit feedback datasets,
we convert the ratings over 3.5 to 1 and otherwise to 0 as done in (Hsieh et
al., 2017; Rendle et al., 2009). Also, we only keep users who have at least
five ratings for MovieLens 1M and CiteULike, twenty ratings for Yelp and
MovieLens 20M. Data statistics after the preprocessing are presented in Table
1. For each dataset, we split all users into the training set (80%) and the
test set (20%). We also take 10% of the training users for validation.

###  5.2. Metrics

As we focus on the top-N recommendation task based on implicit feedback, we
evaluate the performance of each method by using two ranking metrics:
Precision (P@N) (Li et al., 2016) and Normalized Discounted Cumulative Gain
(NDCG@N) (Järvelin and Kekäläinen, 2002). P@N measures how many items in top-N
are actually interacted with the test user, NDCG@N assigns higher weights on
the upper ranked items. For each test user $u$, we get the ranked item list
$\omega^{(u)}$ as described in Section 4.4. Formally, we define
$\omega^{(u)}_{n}$ as the item at rank $n$, $\mathbb{I}[\cdot]$ as the
indicator function, and $V^{(u)}$ as the set of candidate items that user $u$
interacted with (i.e., the ground-truth items). P@N for user $u$ is defined as

(12)
$\text{P@N}(\omega^{(u)},V^{(u)})=\frac{1}{N}\sum_{n=1}^{N}\mathbb{I}[\omega^{(u)}_{n}\in
V^{(u)}].$

DCG@N for user $u$ is defined as

(13)
$\text{DCG@N}(\omega^{(u)},V^{(u)})=\displaystyle\sum_{n=1}^{N}\frac{\mathbb{I}[\omega^{(u)}_{n}\in
V^{(u)}]}{log(n+1)}.$

NDCG@N is the normalized DCG@N after dividing by the best possible DCG@N,
where all the ground-truth items are ranked at the top. We compute the above
metrics for each test user, then report the average score. We conduct
experiments for N=10, 20, 50, 100 and report the results only for N=10, 20 due
to the lack of space. The improvements (%) are similar across different Ns.

Table 1. Data Statistics after the preprocessing Dataset | #Users | #Items | #Ratings | Sparsity
---|---|---|---|---
MovieLens 1M | 6,028 | 3,533 | 575,242 | 97.30%
CiteULike | 6,315 | 25,385 | 136,268 | 99.91%
Yelp | 25,658 | 8,612 | 570,455 | 99.74%
MovieLens 20M | 99,220 | 20,660 | 9,478,902 | 99.54%
Table 2. Experiment results with $k$=50. Results of DRE and the best baseline are in bold face. Improv. denotes the improvement of DRE over the best baseline. $*$, $**$, and $***$ indicate $p\leq$ 0.05, $p\leq$ 0.01, and $p\leq$ 0.005 for the paired t-test of DRE vs. the best baseline. Dataset | Metrics | MOSTPOP | RAN++ | POP++ | RBMF | RBMF++ | RMVA | RMVA++ | DRE | Improv.
---|---|---|---|---|---|---|---|---|---|---
MovieLens 1M | P@10 | 0.3733 | 0.4267 | 0.4011 | 0.5047 | 0.5027 | 0.5063 | 0.5033 | 0.5396 | 6.56%***
P@20 | 0.3331 | 0.3880 | 0.3557 | 0.4373 | 0.4366 | 0.4363 | 0.4325 | 0.4734 | 8.25%***
NDCG@10 | 0.3921 | 0.4439 | 0.4235 | 0.5359 | 0.5365 | 0.5387 | 0.5357 | 0.5688 | 5.59%***
NDCG@20 | 0.3629 | 0.4146 | 0.3935 | 0.4871 | 0.4883 | 0.4887 | 0.4852 | 0.5197 | 6.34%***
CiteULike | P@10 | 0.0073 | 0.0146 | 0.0365 | 0.0465 | 0.0528 | 0.0498 | 0.0581 | 0.0701 | 20.69%***
P@20 | 0.0049 | 0.0136 | 0.0304 | 0.0366 | 0.0392 | 0.0380 | 0.0410 | 0.0471 | 14.90%***
NDCG@10 | 0.0121 | 0.0159 | 0.0431 | 0.0590 | 0.0649 | 0.0610 | 0.0691 | 0.0912 | 31.98%***
NDCG@20 | 0.0130 | 0.0181 | 0.0430 | 0.0569 | 0.0611 | 0.0582 | 0.0652 | 0.0842 | 29.14%***
Yelp | P@10 | 0.0424 | 0.0496 | 0.0478 | 0.0602 | 0.0591 | 0.0608 | 0.0609 | 0.0633 | 4.01%**
P@20 | 0.0371 | 0.0429 | 0.0393 | 0.0499 | 0.0498 | 0.0503 | 0.0505 | 0.0524 | 3.76%*
NDCG@10 | 0.0461 | 0.0542 | 0.0525 | 0.0692 | 0.0674 | 0.0694 | 0.0690 | 0.0705 | 1.56%
NDCG@20 | 0.0477 | 0.0548 | 0.0531 | 0.0679 | 0.0673 | 0.0681 | 0.0684 | 0.0696 | 1.75%
MovieLens 20M | P@10 | 0.3853 | 0.4007 | 0.4063 | 0.5064 | 0.5049 | 0.5116 | 0.5113 | 0.5712 | 11.65%***
P@20 | 0.3276 | 0.3575 | 0.3585 | 0.4312 | 0.4316 | 0.4382 | 0.4382 | 0.4875 | 11.24%***
NDCG@10 | 0.4071 | 0.4196 | 0.4253 | 0.5414 | 0.5401 | 0.5444 | 0.5434 | 0.6077 | 11.62%***
NDCG@20 | 0.3596 | 0.3826 | 0.3899 | 0.4806 | 0.4806 | 0.4851 | 0.4846 | 0.5373 | 10.76%***

###  5.3. Baselines

To show the superiority of the proposed model, we use three groups of baseline
methods: non-elicitation method, statistic-based methods, and maximal-volume
approaches. Note that the methods with ‘++’ use the non-linear decoder that
has the same structure of that of DRE (i.e., the fully-connected network).

The first group is the non-elicitation method, which does not use rating
elicitation and produces non-personalized initial recommendations.

  * •

MOSTPOP: Without the rating elicitation process, it produces a ranked list of
candidate items by sorting their popularity (#ratings). The candidate items
are the same as those of DRE.

The second group is the statistic-based methods, which do not consider the
interactions between the seed items.

  * •

RAN++ (Rashid et al., 2002) : Randomly select $k$ seed items from the entire
itemset.

  * •

POP++ (Rashid et al., 2002) : Select the most popular $k$ items as a seed
itemset.

The last group includes the state-of-the-art maximal-volume approaches. These
methods select the seed itemset in a greedy fashion with consideration of the
linear interactions of items. Also, we include two variants that use the non-
linear decoder to verify the effectiveness of the end-to-end training.

  * •

RBMF (Liu et al., 2011) : Representative Base Matrix Factorization method for
rating elicitation, which is introduced in Section 3.1.

  * •

RBMF++ : A variant of RBMF. After finding the seed itemset, it uses the non-
linear decoder.

  * •

RMVA (Fonarev et al., 2016) : Our main competitor which is the state-of-the-
art method for rating elicitation. It alleviates the squareness of RBMF by
introducing the rectangular matrix volume which is a generalization of the
usual determinant.

  * •

RMVA++ : A variant of RMVA. After finding the seed itemset, it uses the non-
linear decoder.

Note that we do not compare DRE with personalized rating elicitation methods,
because they use users’ rating history (Rashid et al., 2002; Elahi et al.,
2014) or side information (Elahi et al., 2013). DRE is for new users without
any rating history and side information.

###  5.4. Implementation Details

We use PyTorch (Paszke et al., 2019) and Adam optimizer (Kingma and Ba, 2014)
for the proposed model and all baselines. For each dataset, hyper-parameters
are tuned by using grid searches on the validation set. The learning rate for
the Adam optimizer is chosen from $\\{$0.1, 0.05, 0.01, 0.005, 0.004, 0.003,
0.002, 0.001$\\}$. We use a 2-layer fully-connected network as the decoder of
DRE. It has the shape of $[k\rightarrow d\rightarrow m]$. The dimension of the
hidden layer $d$ is chosen from $\\{$200, 300, 500$\\}$. For the temperature
annealing, $T_{0}$ is chosen from $\\{1,10,20,50\\}$ and $T_{E}$ is chosen
from $\\{$0.01, 0.1, 0.5, 1, $T_{0}$$\\}$. We find the best epoch in
$\\{200,400,1000,2000\\}$. For RMVA, we tune the decomposition rank of SVD for
every possible number (i.e., any smaller number than $k$). Lastly, we report
the average value of five iterations for all methods.

(a) MovieLens 1M

(b) CiteULike

(c) Yelp

(d) MovieLens 20M

Figure 3. P@20 of DRE and baselines with different $k$ on four datasets.

(a) DRE

(b) RMVA

(c) RBMF

Figure 4. Location of the seed itemset on MovieLens 1M with $k$=40. Blue dots
are latent vector of users and items, the red circles are the seed items.

###  5.5. Comparing with baselines

We evaluate the top-N recommendation performance of DRE and baseline methods
in two ranking metrics. Table 2 shows the quantitative results and Figure 3
shows the result with the different sizes of the seed itemset $k$. In summary,
the proposed model achieves the best results in all the metrics, especially on
CiteULike dataset (by up to 31.98% improvement for NDCG@10 compared to the
best baseline). Also, DRE outperforms all the baselines with different $k$ in
Figure 3. We analyze the results from various perspectives.

Effectiveness of rating elicitation: We observe that MOSTPOP produces the
worst performance among all the baselines. Since MOSTPOP does not employ
rating elicitation, it provides a mere non-personalized recommendation to all
new users. As a result, the performance of MOSTPOP is even worse than RAN++.
With the rating elicitation, we can capture the preference of new users so
that we can make personalized initial recommendations for them.

Importance of the interactions between seed items: We observe that the
performance of the statistic-based methods (i.e., RAN++ and POP++) is
significantly worse than the other approaches which consider the interactions
between the seed items. With the consideration of inter-item interactions, we
can find more representative seed itemset by avoiding the redundant selection.

Importance of non-linear interactions and end-to-end training: We observe that
DRE outperforms the state-of-the-art competitor (i.e., RMVA) on all the
datasets, especially on the CiteULike dataset. Also, we find that the non-
linear decoder is not always beneficial to improve the performance of the
baselines (RBMF vs. RBMF++ and RMVA vs. RMVA++). As described in Section 3.1,
the maximal-volume based methods only consider the linear interactions of the
items both for finding the seed itemset and for reconstructing the user rating
vector. Although the decoder of RBMF++ and RMVA++ has a capability to capture
the non-linearity, the performance is not always improved because the seed
itemsets of them are not selected with the consideration of the non-linear
interactions. Unlike the existing approaches, DRE optimizes the seed itemset
and the non-linear decoder together through the end-to-end training, which
enables the proposed framework to fully capture the complex structures of the
CF information.

Deficiency of greedy selection: In Figure 3, we observe that the performance
of DRE is more consistently improved on three datasets, compared to the
maximal-volume approaches as the size of the seed itemset increases. Because
the greedy selection of the maximal-volume approaches cannot consider the
interactions of the entire seed items at once, they may have limited
capability of finding the most representative item combination. As a result,
they cannot fully take advantage of the larger seed itemset. However, DRE can
choose all the seed items at a time while considering non-linear interactions
among them. This result again verifies the superiority of the proposed
framework.

Table 3. Effect of $\tau$ on P@20 on MovieLens 1M. The best result is in bold face. |  | $T_{0}$
---|---|---
1 | 10 | 20 | 50
$T_{E}$ | 0.5 | 0.5324 | 0.5348 | 0.5336 | 0.5332
0.1 | 0.5315 | 0.5396 | 0.5352 | 0.5281
0.01 | 0.5105 | 0.5325 | 0.5374 | 0.5263
$T_{0}$ | 0.5158 | 0.4798 | 0.4502 | 0.4503

###  5.6. Seed itemset Analysis

For the qualitative comparison, we visualize the locations of the seed items
in the latent space, where users’ preferences on items are encoded, by using
t-SNE (Maaten and Hinton, 2008). We train the latent vectors of users and
items on MovieLens 1M with the state-of-the-art CF method for implicit
feedback (Hsieh et al., 2017). In Figure 4, we plot the latent vectors of
users and items as blue dots on two-dimensional plane, and we mark the seed
items with red translucent circles. We can clearly see that the seed items
obtained by DRE are more scattered around the plane than those of RMVA and
RBMF. Most seed items of RMVA and RBMF are densely located at the left-center
of the plane. This result supports our argument that DRE can select the better
seed itemset compared to the maximal-volume approaches which may select
redundant items in terms of non-linear dependency.

###  5.7. Hyperparameter Analysis

In this section, we analyze the effect of the hyperparameter $\tau$ with the
result in Table 3. With the large $\tau$, the output of Gumbel-Softmax is
smooth so that DRE can explore the various combinations of items. With the
annealed small $\tau$, the output of Gumbel-Softmax becomes one-hot so that
DRE can select the seed itemset concretely. Note that the last row of Table 3
shows the result when $T_{E}=T_{0}$ (i.e., no temperature annealing). We
observe that the temperature annealing is significantly beneficial to improve
model performance.

##  6\. Conclusion

We review the existing methods for the rating elicitation and point out two
major flaws of them. Solving those two flaws, we propose DRE, a novel deep
learning framework that selects the seed itemset at a time with consideration
of the non-linear interactions of the items. To this end, DRE first defines
the categorical distributions to sample seed items, then trains both the
categorical distributions and a non-linear decoder in the end-to-end manner.
After selecting the seed itemset, DRE can provide personalized recommendation
for a new user by using the trained decoder and the feedback on the seed
itemset. With our extensive experiments, we show that DRE outperforms all
state-of-the-art methods in terms of two ranking metrics on four real-world
datasets. Also, we conduct a qualitative experiment to support our arguments
about the superiority of DRE.

## Acknowledgements

This research was supported by the MSIT(Ministry of Science and ICT), Korea,
under the ICT Consilience Creative program(IITP-2019-2011-1-00783) supervised
by the IITP(Institute for Information & communications Technology Planning &
Evaluation).

## References

  * (1)
  * Antón et al. (2002) Annie I Antón, Julia Brande Earp, and Angela Reese. 2002\.  Analyzing website privacy requirements using a privacy goal taxonomy. In _Proceedings IEEE Joint International Conference on Requirements Engineering_.
  * Elahi et al. (2013) Mehdi Elahi, Matthias Braunhofer, Francesco Ricci, and Marko Tkalcic. 2013.  Personality-based active learning for collaborative filtering recommender systems. In _Congress of the Italian Association for Artificial Intelligence_. Springer, 360–371.
  * Elahi et al. (2014) Mehdi Elahi, Francesco Ricci, and Neil Rubens. 2014\.  Active learning strategies for rating elicitation in collaborative filtering: A system-wide perspective.  _ACM Transactions on Intelligent Systems and Technology (TIST)_ 5, 1 (2014), 1–33.
  * Fonarev et al. (2016) Alexander Fonarev, Alexander Mikhalev, Pavel Serdyukov, Gleb Gusev, and Ivan Oseledets. 2016\.  Efficient rectangular maximal-volume algorithm for rating elicitation in collaborative filtering. In _ICDM_.
  * Goreinov et al. (2010) Sergei A Goreinov, Ivan V Oseledets, Dimitry V Savostyanov, Eugene E Tyrtyshnikov, and Nikolay L Zamarashkin. 2010.  How to find a good submatrix.  In _Matrix Methods: Theory, Algorithms And Applications: Dedicated to the Memory of Gene Golub_. World Scientific.
  * He et al. (2016) Xiangnan He, Hanwang Zhang, Min-Yen Kan, and Tat-Seng Chua. 2016.  Fast matrix factorization for online recommendation with implicit feedback. In _SIGIR_.
  * Hsieh et al. (2017) Cheng-Kang Hsieh, Longqi Yang, Yin Cui, Tsung-Yi Lin, Serge Belongie, and Deborah Estrin. 2017\.  Collaborative metric learning. In _WWW_.
  * Jang et al. (2016) Eric Jang, Shixiang Gu, and Ben Poole. 2016.  Categorical reparameterization with gumbel-softmax.  _arXiv preprint arXiv:1611.01144_ (2016).
  * Järvelin and Kekäläinen (2002) Kalervo Järvelin and Jaana Kekäläinen. 2002.  Cumulated gain-based evaluation of IR techniques.  _ACM Transactions on Information Systems (TOIS)_ (2002).
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ (2014).
  * Li et al. (2016) Huayu Li, Richang Hong, Defu Lian, Zhiang Wu, Meng Wang, and Yong Ge. 2016\.  A Relaxed Ranking-Based Factor Model for Recommender System from Implicit Feedback.. In _IJCAI_.
  * Li and She (2017) Xiaopeng Li and James She. 2017.  Collaborative variational autoencoder for recommender systems. In _SIGKDD_.
  * Liang et al. (2018) Dawen Liang, Rahul G Krishnan, Matthew D Hoffman, and Tony Jebara. 2018.  Variational autoencoders for collaborative filtering. In _WWW_.
  * Lin et al. (2013) Jovian Lin, Kazunari Sugiyama, Min-Yen Kan, and Tat-Seng Chua. 2013.  Addressing cold-start in app recommendation: latent user models constructed from twitter followers. In _SIGIR_.
  * Liu et al. (2011) Nathan N Liu, Xiangrui Meng, Chao Liu, and Qiang Yang. 2011\.  Wisdom of the better few: cold start recommendation via representative based rating elicitation. In _RecSys_.
  * Maaten and Hinton (2008) Laurens van der Maaten and Geoffrey Hinton. 2008.  Visualizing data using t-SNE.  _JMLR_ (2008).
  * Maddison et al. (2014) Chris J Maddison, Daniel Tarlow, and Tom Minka. 2014.  A* sampling. In _NeurIPS_.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019\.  PyTorch: An imperative style, high-performance deep learning library. In _NeurIPS_.
  * Rashid et al. (2002) Al Mamunur Rashid, Istvan Albert, Dan Cosley, Shyong K Lam, Sean M McNee, Joseph A Konstan, and John Riedl. 2002.  Getting to know you: learning new user preferences in recommender systems. In _Proceedings of the 7th international conference on Intelligent user interfaces_.
  * Rashid et al. (2008) Al Mamunur Rashid, George Karypis, and John Riedl. 2008\.  Learning preferences of new users in recommender systems: an information theoretic approach.  _Acm Sigkdd Explorations Newsletter_ (2008).
  * Rendle et al. (2009) Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. 2009.  BPR: Bayesian personalized ranking from implicit feedback. In _UAI_.
  * Schein et al. (2002) Andrew I Schein, Alexandrin Popescul, Lyle H Ungar, and David M Pennock. 2002.  Methods and metrics for cold-start recommendations. In _SIGIR_.
  * Sedhain et al. (2015) Suvash Sedhain, Aditya Krishna Menon, Scott Sanner, and Lexing Xie. 2015.  Autorec: Autoencoders meet collaborative filtering. In _WWW_.
  * Sedhain et al. (2017) Suvash Sedhain, Aditya Krishna Menon, Scott Sanner, Lexing Xie, and Darius Braziunas. 2017\.  Low-rank linear cold-start recommendation from social data. In _AAAI_.
  * Wang et al. (2013) Hao Wang, Binyi Chen, and Wu-Jun Li. 2013.  Collaborative topic regression with social regularization for tag recommendation. In _IJCAI_.
  * Wu et al. (2016) Yao Wu, Christopher DuBois, Alice X Zheng, and Martin Ester. 2016.  Collaborative denoising auto-encoders for top-n recommender systems. In _WSDM_.
  * Zhang et al. (2014) Mi Zhang, Jie Tang, Xuchen Zhang, and Xiangyang Xue. 2014\.  Addressing cold start in recommender systems: A semi-supervised co-training algorithm. In _SIGIR_.


# Insights from the Design Space Exploration of Flow-Guided Nanoscale
Localization

Filip Lemic1, Gerard Calvo Bartra2, Arnau Brosa López2, Jorge Torres Gómez3,
Jakob Struye4,
Falko Dressler3, Sergi Abadal2, Xavier Costa Perez156  1AI-Driven Systems Lab,
i2Cat Foundation, Spain  2NaNoNetworking Center in Catalunya, Polytechnic
University of Catalonia, Spain  3Telecommunications Networks Group, Technische
Universität Berlin, Germany  4Internet and Data Lab, University of Antwerp -
imec, Belgium  5NEC Laboratories Europe GmbH, Germany  6ICREA, Spain
Email<EMAIL_ADDRESS>
###### Abstract

Nanodevices with Terahertz (THz)-based wireless communication capabilities are
providing a primer for flow-guided localization within the human bloodstreams.
Such localization is allowing for assigning the locations of sensed events
with the events themselves, providing benefits in precision medicine along the
lines of early and precise diagnostics, and reduced costs and invasiveness.
Flow-guided localization is still in a rudimentary phase, with only a handful
of works targeting the problem. Nonetheless, the performance assessments of
the proposed solutions are already carried out in a non-standardized way,
usually along a single performance metric, and ignoring various aspects that
are relevant at such a scale (e.g., nanodevices’ limited energy) and for such
a challenging environment (e.g., extreme attenuation of in-body THz
propagation). As such, these assessments feature low levels of realism and
cannot be compared in an objective way. Toward addressing this issue, we
account for the environmental and scale-related peculiarities of the scenario
and assess the performance of two state-of-the-art flow-guided localization
approaches along a set of heterogeneous performance metrics such as the
accuracy and reliability of localization.

##  I Introduction

Advancements in nanotechnology have paved the way for nanoscale devices that
integrate sensing, computing, and data and energy storage capabilities [1].
These nanodevices are expected to enable various applications in precision
medicine [2]. Some of these applications involve deploying nanodevices in
patients’ bloodstreams, which necessitates the nanodevice’s size to be
comparable to that of red blood cells (i.e., smaller than 5 microns). Due to
their small physical size, these nanodevices can only rely on scavenging
environmental energy, such as from heartbeats or ultrasound-based power
transfer, using nanoscale energy-harvesting entities like Zinc Oxide (ZnO)
nanowires [1]. Consequently, these devices are expected to be passively
flowing within the bloodstreams.

Recent advancements in advanced materials, particularly graphene and its
derivatives [3], have opened up possibilities for nanoscale wireless
communication in the Terahertz (THz) frequencies (i.e., 0.1-10 THz) [4].
Wireless communication capabilities enable two-way communication between
nanodevices and the external world [5]. Integrated nanodevices with
communication capabilities are enabling sensing-based applications like oxygen
sensing in the bloodstream for hypoxia detection (a biomarker for cancer
diagnosis), as well as actuation-based applications like non-invasive targeted
drug delivery for cancer treatment. Nanodevices with communication
capabilities also provide a primer for flow-guided localization within the
bloodstream [4]. Flow-guided localization would allow associating the location
of an event detected by a nanodevice, offering benefits along the lines of
non-invasiveness, early and precise diagnostics, and reduced costs [6, 7, 8].

Performance evaluations of existing flow-guided localization approaches,
specifically those described in [6] and [7], have been conducted in a
simplified manner, focusing primarily on the mobility of nanodevices.
Consequently, these assessments overlook various potential effects of THz
wireless communication, such as interference, as well as energy-related
constraints arising from energy-harvesting and intermittent operation of the
nanodevices. It is also worth noting that [8] performed a limited performance
evaluation, examining the number of nanodevices required for localizing a
nanodevice at any location in the body through multi-hopping. As such, current
evaluations provide only rough indications due to their limited realism and
subjective evaluation methodologies.

In this article, we aim to enhance the realism of such assessments by
considering multiple factors simultaneously. This includes accounting for the
mobility of the nanodevices, in-body nanoscale THz communication between the
nanodevices and the external world, and various energy-related and
technological constraints, such as pulse-based modulation, that impact
nanodevices’ performance. By incorporating these elements through the
utilization of a simulator for objective and standardized performance
evaluation of flow-guided nanoscale localization [9], we seek to provide a
more comprehensive and realistic understanding of the performance of flow-
guided localization. To the best of our knowledge, this article represents the
first attempt at objective and realistic performance assessment of different
flow-guided localization approaches across a set of standardized heterogeneous
metrics including point and region estimation accuracies, as well as the
reliability of localization. Our approach is inspired by established
approaches targeting objective evaluation and benchmarking of more traditional
indoor localization approaches stemming from efforts such as NIST PerfLoc
[10], EU EVARILOS [11], and Microsoft/IPSN indoor localization competition
[12].

##  II Flow-guided Nanoscale Localization

###  II-A Flow-guided Nanoscale Localization Fundamentals

Flow-guided nanoscale localization aims to detect and locate a target event
using nanodevices, without requiring the nanodevices to necessarily determine
their own location. The concept presented in [8] supports this type of
scenario and falls within this category. However, the notable representatives
of this localization approach are [6] and [7]. In these studies, Machine
Learning (ML) models are employed to differentiate the regions through which
each nanodevice passes during a single circulation through the bloodstream.
The authors in [7] achieve this by tracking the distances covered by a
nanodevice during its circulation using a nanoscale Inertial Measurement Unit
(IMU). However, this poses challenges in terms of the limited resources
available for storing and processing IMU-generated data at the nanodevice
level, as well as the accuracy of IMU readings being affected by the blood’s
vortex flow. On the other hand, the authors in [6] address these challenges by
tracking the time required for each circulation through the bloodstream. The
captured distance or time information is then transmitted to a beaconing
anchor located near the heart using short-range THz-based backscattering at
the nanodevice level.

These localization approaches, unlike [8], are not specifically designed to
provide precise point localization of the target. Despite the potential
benefits of achieving point localization for healthcare diagnostics, these
methods focus on detecting the body region through which the nanodevice has
passed. Furthermore, the accuracy and reliability of region detection can be
improved by increasing the number of circulations the nanodevices make through
the bloodstream. However, this increase would result in higher energy
consumption for the localization procedure. Thus, performance metrics such as
point and region accuracies and reliability should and will be evaluated in
relation to the application-specific delay allowed for localizing events,
according to [9].

###  II-B Localization Solution 1

The first flow-guided localization solution we consider is presented in [6].
The authors assume that, due to the physiology of the bloodstream, the
nanodevices travel in closed loops. They further assume that the nanodevices
feature an internal counter that increases its value periodically and restarts
in each passage through the heart. The final counter value is reported to an
external gateway located at the heart proximity, before resetting the counter.
The counter value is used as an input to a ML model to predict the traveling
loop for each nanodevice. The utilized ML model is a Neural Network (NN) that
implements two fully connected layers, a ReLU activation function for the
first and a SoftMax function for the second layer. The model is trained to
classify 24 different circuits with traveling times as reported by the
simulator (more details in the following section). The optimization algorithm
to evaluate the NN hyperparameters is the Limited Memory
Broyden–Fletcher–Goldfarb–Shanno (L-BFGS) algorithm that minimizes the cross-
entropy between predictions and labels.

###  II-C Localization Solution 2

The second considered approach is an in-house NN solution that implements
three fully-connected layers, with PReLU activation function for the first two
layers and log-softmax for the last one. The first and second layers feature a
dropout for regularization, as well as batch normalization for stabilizing the
learning process. The hidden layer’s size is 512 and the model is trained to
classify 25 classes (in contrast to Solution 1 that is by-design unable to
detect event in the heart). We use the Negative Log Likelihood loss due to its
ability to handle unbalanced datasets. Finally, we use the Adam optimizer as
it adjusts the learning rate dynamically and it is known to operate well with
relatively simple fine-tuning of the hyperparameters.

##  III Evaluation Setup

This section presents the setup and parameters used in the evaluation.
Specifically, we first outline the utilized simulator and its main features,
followed by the considered scenarios and parameters defining our design space,
and finalized with the utilized performance metrics.

We employ a simulator from [9] to assess the performance of the considered
flow-guided localization solutions. The simulator assumes that implementing a
flow-guided localization in the bloodstream requires at least one anchor
attached to the patient’s body. Approaches in [6] and [7] can be enabled with
a single anchor positioned near the heart, as the heart is the only body
region with guarantees that each nanodevice will pass through it in every
iteration. The anchor is envisioned as a static entity powered by reliable
sources such as batteries, hence it is assumed to be continuously operational.
The role of the anchor is to transmit beacons and receive backscattered
responses from the nanodevices.

Figure 1: Nanodevice mobility in the BloodVoyagerS [13]

The nanodevices are energy-harvesting entities that can move passively in the
bloodstream. To model their mobility, the utilized simulator features the
integration with BloodVoyagerS [13]. BloodVoyagerS provides a simplified model
of the bloodstream, including 94 vessels and organs, with the coordinate
system centered in the heart. All organs have the same spatial depth, with a
reference thickness of 4 cm resembling the depth of a kidney. This results in
the z-coordinates of the nanodevices ranging from 2 to -2 cm, as illustrated
in Figure 1. The simulator assumes that arteries and veins are positioned
anterior and posterior, respectively. Transitions between arteries and veins
occur in the organs, limbs, and head. In the heart, blood transitions from
veins to arteries (i.e., posterior to anterior). The flow rate is modeled
based on the relationship between pressure difference and flow resistance,
resulting in average blood speeds of 20 cm/sec in the aorta, 10 cm/sec in
arteries, and 2-4 cm/sec in veins. Transitions between arteries and veins are
simplified by assuming a constant velocity of 1 cm/sec.

In the simulator, the nanodevices are assumed to have capacitors for energy
storage and utilize ZnO nanowires for energy harvesting. The charging of
capacitors is modeled as an exponential process that considers the energy-
harvesting rate and interval (e.g., 6 pJ per sec and per 20 ms for harvesting
from heartbeats and ultrasound-based power transfer, respectively [1]), as
well as the storage capacity of the capacitors. The nanodevices exhibit
intermittent behavior due to constraints related to energy harvesting and
storage. This behavior is modeled through a _Turn ON_ threshold, where a
nanodevice turns on if its current energy level exceeds the threshold. Once
the energy is fully depleted, the nanodevice turns off and turns back on when
its energy increases above the threshold.

When the nanodevices are turned on, they periodically perform sensing or
actuation tasks at a given sampling frequency or granularity. Each execution
consumes a constant amount of energy, meaning that more frequent tasks result
in higher energy consumption for each nanodevice. The location of the event to
be detected is assumed to be hard-coded by the experimenter. A nanodevice is
considered to detect an event if it is turned on and the Euclidean distance
between its location at the time of task execution and the location of the
event is smaller than a predefined event detection threshold.

In the communication between the anchor and a nanodevice, the anchor transmits
beacons at a constant frequency and transmit power. The nanodevices passively
receive the beacons and actively backscatter a response, which consumes
energy. The backscattered packets from the nanodevices contain two pieces of
information: the time elapsed since their last passage through the heart and
an event bit. These raw data points are then used by a flow-guided
localization approach to localize an event. Whenever a nanodevice passes
through the heart, the time elapsed since the last passage is envisioned to be
reset to avoid accumulating multiple circulation periods. The event bit is set
to logical ”1” if a target event is successfully detected, and is envisaged to
be reset in each passage through the heart.

The THz channel is modeled by calculating the receive power for each pair of
communicating devices and scheduling the invocation of the _ReceivePacket()_
method based on the corresponding propagation time. The channel model takes
into account in-body path-loss and Doppler effects. The path-loss is
determined by considering the attenuation and thickness parameters of the
vessels, tissues, and skin. The Doppler effect is incorporated by evaluating
the changes in relative positions between the nanodevices and the anchor over
time. The _ReceivePacket()_ method checks for potential collisions by
calculating the Signal to Interference and Noise Ratio (SINR) and discards the
packet if the SINR falls below a predefined threshold for reception, known as
the receiver sensitivity.

Our aim is to explore several aspects of the design space of flow-guided
localization. To this end, we identify the parameters most worth exploring and
leave the others fixed to one value. Table I outlines the fixed parameters.
Then, the parameters constituting the considered design space are (i) the
number of administered nanodevices, (ii) event sampling frequency or
granularity, and (iii) distance threshold for event detection. Table II shows
their baseline value and other values considered within the design space. In
each scenario, we vary one parameter, while keeping the others at their
baseline values, allowing us to isolate the effects of a single parameter on
the overall performance of the considered solutions.

Following guidelines from [9], we utilize three metrics for characterizing the
performance of the evaluated solutions. The first one is the region detection
accuracy, which characterizes the level of correctness of estimating a body
region containing an event. Then, point accuracy represents the Euclidean
distance between the true location of an event and its estimated location as
yielded by a flow-guided localization solution. Finally, the reliability of
localization characterizes the capability of the solution to provide a
location estimate (regardless of its correctness) after a certain period of
time.

To obtain the performance metrics, we first trained both localization
solutions. The training was carried out by specifying the location of an event
in the centroid of each of the 25 body regions covered by BloodVoyagerS (i.e.,
organs, head, and extremities, with regions indicated with gray rounded
rectangles in Figure 1). The raw training data for each event location was
then generated by running the simulations for 5000 sec, and fed in both of the
considered solutions. This was followed by generating a set of testing
datasets for capturing the outlined design space. The testing dataset for each
scenario contained 25 different event locations, one in each region, selected
randomly within the region. The intuition for such a selection is that an
event of interest can be located in any part of the considered region. Given
that the considered solutions are by-design unable to provide a point estimate
but solely an estimated region, the point estimate was obtained as the
centroid location of the estimated region.

Our results in Figures 2, 3 and 4 are depicted in a way that each data point
on the x-axis (e.g., each box-plot in the point accuracy plot) shows the
performance of a solution averaged over the 25 evaluation points. Such
depiction of the results allows for reporting the average performance of the
solutions for the entire environment, encapsulating the performance
variability in different environmental regions.

TABLE I: Simulation parameters Parameter | Value
---|---
Generator voltage $V_{g}$ [V] | 0.42
Energy consumed in pulse reception $E_{R_{Xpulse}}$ [pJ] | 0.0
Energy consumed in pulse transmission $E_{T_{Xpulse}}$ [pJ] | 1.0
Maximum energy storage capacity [pJ] | 800
Turn ON/OFF thresholds [pJ] | 10/0
Harvesting cycle duration [ms] | 20
Harvested charge per cycle [pC] | 6
Transmit power $P_{T_{X}}$ [dBm] | -20
Operational bandwidth [GHz] | 10
Receiver sensitivity [dBm] | -110
Operational frequency [THz] | 1
Simulation time [sec] | 1100
Number of anchors | 1
TABLE II: Design space parameters Parameter |  Baseline | Design space
---|---|---
Number of nanodevices |  64 | [32, 64, 128]
Event sampling granularity [1/sec] |  3 | [2, 3, 5, 10]
Event detection threshold [cm] |  1 | [0.5, 1, 2, 3]

##  IV Evaluation Results

Figure 2 depicts the performance achieved by the two solutions as a function
of the number of administered nanodevices. As visible from the figure,
Solution 2 generally outperforms Solution 1 in regard to the point accuracy
metric. For example, in the scenario assuming 128 nanodevices deployed within
the bloodstream, Solution 2 yields the median localization error of around 25
cm throughout the duration of the simulation run. In contrast, for Solution 1
this error is roughly 40 cm throughout the simulation. The same observation
can be confirmed by the results depicted in Figures 3 and 4 demonstrating the
influence of the event sampling granularity and event detection threshold of
the performance of the considered solutions, respectively. Similar conclusion
can be made when observing the region detection accuracy, although in this
case the improvements yielded by Solution 2 are less pronounced and in the
range of several percent. The reason for such a behavior comes from the fact
that Solution 1 is an of-the-shelf flow-guided localization approach. As such,
its hyperparameters have not been fine-tuned for the raw datasets utilized in
this study, which is in contrast to the in-house made and finely-tuned
Solution 2.

(a) Solution 1

(b) Solution 2

Figure 2: Number of nanodevices

Moreover, Figure 2 depicts that point and region estimation accuracies
increase either rather slightly or not at all with the increase in the
duration of a simulation runtime. For example and considering Solution 2 with
the assumption of 64 nanodevices being deployed in the bloodstream, the median
localization error characterizing the point accuracy is decreased from around
30 to 20 cm if the duration of raw data collection is extended from 120 to 960
sec. At the same time, the region estimation accuracy is increased from around
20 to 25%. Interestingly, for the scenario assuming 128 deployed nanodevices,
the point and regions detection accuracies are effectively unchanged
throughout the simulation run. The main reason for such a behavior stems from
two aspects distinctively affecting the performance of the considered
solutions. First and arguably more intuitive reason comes from the fact that
ML models generally improve their performance with the increase in the amount
of raw data fed into them for making predictions. Obviously, an increase in
the duration of a simulation run results in an increase in the amount of raw
input data for the considered solutions, benefiting the accuracy of
estimation. However, one should also account for the fact that THz
communication between the nanonodes and the anchor is challenging for several
reasons including high in-body attenuation, high mobility of the nanonodes,
and self-interference between different nanonodes trying to communicate with
the anchor simultaneously. For these reasons, the communication is unreliable,
which can result in the anchor not receiving the raw data by some nanonodes at
certain time instances. More problematically, these nanonodes in such cases do
not reset their iteration times and event bits. Once the data is eventually
reported to the anchor, the reported iteration times are the compounds of
multiple iterations, while the event bit might be erroneous (i.e., the event
was detected in one of the iterations, yet propagated through multiple
iterations, some of them not featuring the event). In addition, the energy-
harvesting nature of a nanodevice, and consequently its intermittent
operation, might result in the nanodevice missing to detect the event as it
was turned off, although it went through the region of the bloodstream that
contained such an event. More details on the features of the raw data can be
found in [9]. The outlined behavior results in the fact that, although more
data inputted into the models should increase the accuracy of estimation, its
highly erroneous nature balances out these improvements, resulting in the
“flat” performance in terms of region and point detection accuracy for both of
the considered solutions.

(a) Solution 1

(b) Solution 2

Figure 3: Event sampling granularity

Observing Figures 2, 3, and 4, one can see that the region estimation accuracy
respectively converges towards the values of roughly 20 and 25% for Solutions
1 and 2, although the rate of convergence differs across scenarios. The
converging values represent the achievable performance of the models, which is
in contrast to the significantly better performance reported by state-of-the-
art works proposing the considered models (e.g., [6]). The reason for the
unsatisfactory accuracy of the models is the result of by-design difference in
the raw data utilized for their training and evaluation. Specifically, the raw
input data generated in these works did not account for the energy-harvesting
nature of the nanodevices, as well as for unreliable communication between the
nanodevices and the anchor resulting from various phenomena such as self-
interference between the nanodevices, high-attenuation of in-body THz
communication, etc. In addition, these models are by-design unable to
distinguish between left and right hand sides of the body given that in such
cases the iteration times are the same. Future efforts should consider new and
more powerful ML tools, with primary candidates stemming from the Graph Neural
Networks (GNN) family due to their intrinsic ability to handle complex graph-
structured data, capture non-linear relationships between different data
points (i.e., nodes), and generalize to unseen data. In addition, future
efforts should consider introducing additional anchors at strategic locations
of the body (primarily hand and leg wrists) to support the ascertaining left
and right hand side of different body regions.

(a) Solution 1

(b) Solution 2

Figure 4: Detection distance threshold

In terms of the design space of the considered solutions, Figure 2 depicts the
effects of an increasing number of administered nanodevices on the accuracy
and reliability-related metrics. As visible, an increase in the number of
nanodevices increases the point and region estimation accuracies of both
solutions. As an example, when increasing the nanodevices’ number from 32 to
128, and considering an entire simulation run with the duration of 960 sec,
the 3rd quartile of localization error for Solution 2 is decreased from more
than 75 to less than 40 cm. This improvement is a direct result of more raw
data being produced by the system as a result of introducing additional
nanodevices. However, at the same time the region accuracy is only minorly
affected, which can be contributed to the fact that the more data is
generated, the more erroneous instances it features, eventually resulting in
poor region detection accuracy. The introduction of additional nanodevices
benefits the rate of reliability increase, although eventually the reliability
of producing location estimates across solutions and scenarios converges
toward 100%. Optimizing the reliability increase will be of interest for
applications that feature latency requirements, e.g., targeted drug delivery.

Figures 3 and 4 depict the effects of the event sampling frequency and
detection distance threshold on the performance of the solutions,
respectively. As visible from the figures, the variations in these parameters
have only slight effects on the considered metrics. The sampling granularity
only affects the rate at which the events can be detected. As such, it is
expected that, the more frequent the sampling, the higher is the convergence
rate toward the region detection accuracy achievable by the models. In
addition, the energy consumed in sampling is small compared to the
nanodevices’ overall energy. In other words, even the fastest sampling of 10
samples/sec is insufficient to deplete the energy of the nanodevices, hence
the reliability of producing estimates is not significantly affected by the
granularity. In more general terms, the selection of sampling frequency should
be considered in relation to the blood speeds and available energy at the
nanonode level. For the considered regions in which the blood speeds are 1
cm/sec and with the event detection threshold of 1 cm, there is no need for
increasing the sampling frequency beyond 1 sample/sec, as this will solely
result in increased energy consumption.

As visible in Figure 4, an increase in the distance threshold for event
detection has a negative effect on the point accuracy. This is because an
increased detection distance results in detecting events that are farther away
from the nanodevices. For certain regions, such as the ones in the torso, this
increase is sufficient to detect events in regions through which a nanodevice
did not pass, eventually resulting in some estimates featuring large errors.
Thus, the distribution of localization errors depicted in each point accuracy
box-plot gets visibly larger when the threshold is increased beyond 1 cm.

##  V Conclusion

We have followed a standardized methodology for assessing the performance of
two contemporary flow-guided localization solutions. The followed assessment
methodology allowed us to explore the design space of the solutions in an
objective way and along heterogeneous metrics. The high level of realism was
guaranteed by utilizing a state-of-the-art simulation environment that is able
to capture the peculiarities of nanodevices, Terahertz (THz) wireless
nanocommunication, and the harsh environment that the human bloodstream
represents.

Our results reveal relatively poor performance of the solutions, which can be
attributed to the unreliable nature of THz communication between the in-body
nanodevices and the outside world, and the inability of the solutions to deal
with the high complexity and erroneous nature of the input data. Future work
will aim at enhancing the accuracy of localization by considering different ML
models, primarily the ones from the Graph Neural Networks (GNN) family, and
introducing additional anchors at strategic locations on the body.

## References

  * [1] Josep Miquel Jornet  “Joint energy harvesting and communication analysis for perpetual wireless nanosensor networks in the THz band”  In _IEEE Trans. on Nanotechnology_ 11.3 IEEE, 2012, pp. 570–580
  * [2] Qammer H Abbasi  “Nano-communication for biomedical applications: A review on the state-of-the-art from physical layers to novel networking concepts”  In _IEEE Access_ 4 IEEE, 2016, pp. 3920–3935
  * [3] Sergi Abadal  “Time-domain analysis of graphene-based miniaturized antennas for ultra-short-range impulse radio communications”  In _IEEE Trans. on Communications_ 63.4 IEEE, 2015, pp. 1470–1482
  * [4] Filip Lemic  “Survey on terahertz nanocommunication and networking: A top-down perspective”  In _IEEE J. on Selected Areas in Communications_ 39.6 IEEE, 2021, pp. 1506–1543
  * [5] Falko Dressler  “Connecting in-body nano communication with body area networks: Challenges and opportunities of the Internet of Nano Things”  In _Nano Comm. Networks_ 6.2 Elsevier, 2015, pp. 29–38
  * [6] Jorge Torres Gómez  “Nanosensor Location Estimation in the Human Circulatory System Using Machine Learning”  In _IEEE Trans. on Nanotechnology_ 21 IEEE, 2022, pp. 663–673
  * [7] Jennifer Simonjan  “In-body bionanosensor localization for anomaly detection via inertial positioning and THz backscattering”  In _IEEE Trans. on NanoBioscience_ 21.2 IEEE, 2021, pp. 216–225
  * [8] Filip Lemic  “Toward location-aware in-body terahertz nanonetworks with energy harvesting”  In _ACM NANOCOM_ , 2022, pp. 1–6
  * [9] Arnau Brosa López  “Toward Standardized Performance Evaluation of Flow-guided Nanoscale Localization”  In _arXiv:2303.07804_ , 2023
  * [10] Nader Moayeri  “PerfLoc (Part 1): An extensive data repository for development of smartphone indoor localization apps”  In _Personal, Indoor, and Mobile Radio Communications_ , 2016, pp. 1–7  IEEE
  * [11] Tom Van Haute  “Platform for benchmarking of RF-based indoor localization solutions”  In _IEEE Communications Magazine_ 53.9 IEEE, 2015, pp. 126–133
  * [12] Dimitrios Lymberopoulos  “A realistic evaluation and comparison of indoor location technologies: Experiences and lessons learned”  In _Information processing in sensor networks_ , 2015, pp. 178–189
  * [13] Regine Geyer  “BloodVoyagerS: Simulation of the work environment of medical nanobots”  In _ACM NANOCOM_ , 2018, pp. 1–6

  *[THz]: Terahertz
  *[ZnO]: Zinc Oxide
  *[ML]: Machine Learning
  *[IMU]: Inertial Measurement Unit
  *[NN]: Neural Network
  *[SINR]: Signal to Interference and Noise Ratio
  *[GNN]: Graph Neural Networks