1178 Research

# Offsetting Perceptual Bias in Visual Clustering: The Role of Point Size
Adjustment in Variable Display Sizes

Taehyun Yang e-mail<EMAIL_ADDRESS>Hyeon Jeon e-mail<EMAIL_ADDRESS>Jinwook Seo e-mail<EMAIL_ADDRESS>
###### Abstract

Scatterplots are frequently shared across different displays in collaborative
and communicative visual analytics. However, variations in displays diversify
scatterplot sizes. Such variations can influence the perception of clustering
patterns, introducing potential biases leading to misinterpretations in
cluster analysis. In this research, we explore how scatterplot size affects
cluster assignment and investigate how we can offset such bias. We first
conduct a controlled study asking participants to perform visual clustering on
scatterplots of varying sizes. We found that changes in scatterplot size
significantly alter cluster perception in three key features. In our
subsequent experiment, we examine how adjusting point sizes can mitigate this
bias. As a result, we verify that adjusting point size can effectively
counteract the perceptual biases caused by varying scatterplot sizes. We wrap
up our research by discussing the necessity and applicability of our findings
in real-world applications.

###### keywords:

Cluster Perception, Visual Clustering, Perceptual Bias, Cluster Analysis,
Scatterplot, Visual Encoding, Quantitative user study

##  1 Introduction

Scatterplot is one of the most widely used visual idioms. Using scatterplots,
users can readily grasp complex patterns and trends within datasets [28]. Due
to its importance, several research works investigated how visual perception
is affected by the design of scatterplots [1, 11, 9].

Scatterplots are commonly shared across different displays with various sizes
and resolutions for collaborative visual analytics and data communication [16,
18]. For example, instructors often use scatterplots to present data to
students. Similarly, scatterplots can be used to share data analytics results
with stakeholders or domain experts. Here, to present scatterplots in various
displays, visualization designers or analysts commonly scale up the
scatterplot or point sizes to fit into the new screen size and resolution [4].
However, such naive scaling incurs biases in perceiving data patterns [25],
leading to inconsistencies in data analysis.

Figure 1: Illustration of our research motivation: the perceptual bias in
visual clustering due to scatterplot sizes. In communicative or collaborative
analytics environments (e.g., classrooms), users often view the same
scatterplots on different displays. These displays present scatterplots in
various sizes, which can lead to different interpretations in visual
clustering analysis.

Previous research works have investigated how human perception is influenced
by different scatterplot features, including point color [22, 24], mark types
[13, 8], and aspect ratio [26, 7]. These findings guide designers and analysts
in optimizing scatterplot design to meet specific needs. In terms of point
size and scatterplot size, Wei et al. [25] identified potential biases in the
visual task of assessing (1) which scatterplot has more points (numerosity),
(2) which scatterplot shows stronger correlation (correlation), (3) which
scatterplot exhibit more obvious separation between two different colored
classes (class separation). Furthermore, the study also stated that biases in
these three tasks could be partially corrected by changing the point size.
However, to the best of our knowledge, no prior study has quantitatively
investigated how scatterplot size affects cluster perception or visual
clustering and whether adjusting point sizes can help maintain consistent
clustering perception across varying monochrome scatterplot sizes.

Our research fills this research gap by providing (1) empirical evidence to
identify the perceptual biases that occur when scatterplot sizes change and
(2) verification that point sizes can be adjusted to alleviate the perceptual
biases identified in (1). This enables a more accurate and consistent cluster
perception across various display environments, which is essential for
reliable data analysis and decision-making processes.

To do so, we first conduct a preliminary study investigating how visual
clustering results vary by scatterplot size. The results indicate that the
cluster perception is significantly affected by scatterplot size. Larger
scatterplots showed a smaller number of clusters, more points within each
cluster, and a higher relative area for each cluster. Subsequently, in our
main study, we systematically adjust point sizes across 20 randomly sized
monochrome scatterplots and measure how these modifications affect
participants’ cluster perception. As a result, we found that adjusting point
sizes can substantially mitigate perceptual bias caused by varying scatterplot
size.

To demonstrate the effectiveness of the research, we discuss the potential
future works and applications of our findings. Specifically, our findings can
ground the development of a mathematical model to calibrate each scatterplot
to the display size of different devices, ensuring that all participants have
a consistent view of the data. Such model can also be integrated into software
tools used by data analysts and scientists, allowing for automatic adjustments
of visual encodings to ensure consistent representation of data clusters
regardless of window sizes.

In summary, our study provides the following contributions:

  1. 1.

Initial findings on how cluster assignments vary between large and small
scatterplots.

  2. 2.

Verification that adjustments to scatterplot point sizes effectively
counteract perceptual biases caused by scatterplot dimensions.

  3. 3.

Proposal of potential applications of our findings in collaborative
environments and responsive visualization.

##  2 Related Work

###  2.1 Visual Clustering in Scatterplots

Visual clustering, the task of grouping similar data points visually, is
crucial for exploring and understanding various data patterns [18, 11].
Sarikaya et al. [19] described visual clustering as a high-level data
summarization task defined as the ability to identify groups of similar items.

Given the importance of visual clustering, several previous works have
concentrated on understanding how human visual perception influences
clustering in scatterplots [5, 23, 13]. Xia et al. [27] extended these
observations by constructing a large dataset of scatterplots used to predict
the influence of human visual perception on clustering outcomes. ScatterNet, a
deep learning model, captures perceptual similarities between scatterplots to
emulate human clustering decisions [15]. Furthermore, ClustMe used visual
quality measures (VQM) to model human judgments to rank scatterplots [2].
Recently, CLAMS introduced a VQM that measures ambiguity in cluster perception
while performing visual clustering [11]. Comprehensively, Sedlmair et al. [21]
proposed a taxonomy which showed scatterplot features such as scale, shape,
and density impact perceived cluster separation differently from preexisting
VQM. However, existing studies have mainly focused on visual clustering when
scatterplot and point sizes are fixed. In our research, we aim to investigate
how visual clustering changes when scatterplot and point sizes are varied.

###  2.2 Effect of Scatterplot Size and Cluster Perception

The necessity for analyzing data on different displays have increased with the
development of display devices [10]. e.g., tabletop displays or smartphones.
Liao et al. [14] introduced a cluster-based technique to improve scatterplot
analysis and visualization on various displays. Recently, Christopher et al.
[3] noted that display sizes strongly affect the usability of scatterplots.
Researchers have further studied the effect of display sizes on design
decisions of scatterplots, such as interactions on mobile phones, clustering
perception on large displays, and data visualization in 3d environments [12].

Recently, Wei et al. [25] proposed that geometric scaling in scatterplots
creates significant perceptual bias. The research highlights that scaling up
scatterplots, such as from a laptop screen to a projector, leads to perceptual
biases when users compare correlations, estimate the number of points in a
class, and assess class separability in two-color scatterplots. Wet et al.
also showed that changing the point size can partially mitigate biases in
these tasks. However, to the best of our knowledge, there is no prior work
that investigates the effect of scatterplot and point sizes on visual
clustering. To fill this gap, we clarify that scatterplot size also affects
visual clustering in scatterplots, and point sizes can be used to mitigate
such perceptual bias.

##  3 User Study

We designed our user study in two stages: (1) a preliminary study to identify
the perceptual biases in visual clustering when scatterplot size is changed;
and (2) a main experiment to test whether changing point size can mitigate the
perceptual bias identified in (1). Based on the study results, we verify that
point size can be adjusted to offset the perceptual bias caused by scatterplot
size

###  3.1 Preliminary Study

####  3.1.1 Objectives and Design

We want to identify the perceptual bias in visual clustering caused by
scatterplot size. To do so, we asked participants to perform visual clustering
in small (50px) and large (350px) monochrome scatterplots. These sizes were
chosen to simulate scatterplot dimensions as displayed on a mobile device and
a large desktop monitor [25]. We asked participants to lasso the clusters they
identified in scatterplots, investigating how visual clustering results vary
by the size of the scatterplots.

Generating stimuli. We sampled our scatterplot stimuli from the corpus of
scatterplots generated by the ClustMe study [2]. We used ClustMe scatterplots
as they are already used to evaluate ClustMe, a VQM that models human
perception of cluster patterns. This aligns with our goal of modeling human
perception in visual clustering.

We first wanted to exclude scatterplots that are too simple or too complex for
visual clustering task over scatterplots [17]. Subsequently, we filtered out
scatterplots with more than 12 clusters and less than 3 clusters from the
corpus. We counted the number of clusters using Gaussian Mixture Models while
using the Bayesian inference criterion to determine the optimal number of
clusters, following Jeon et al. [11]. We then randomly sampled 20 scatterplots
from the filtered corpus as our final set of stimuli, which we denote as
$\mathcal{S}=\\{S_{1},S_{2},\cdots,S_{20}\\}$

Procedure. We conducted the experiment in-person, where one experimenter
guided the entire study. After signing a consent form, participants underwent
a brief tutorial on using the lasso tool. The participants received
instructions to use the lasso tool to label any clusters. The definition of a
cluster was vaguely provided as ”groupings of similar data points” [19]. The
tutorial lasted at most five minutes.

We then asked participants to lasso clusters in all 20 scatterplots, one at a
time. For half of the participants, we made $S_{1}\sim S_{10}$ and $S_{11}\sim
S_{20}$ to be displayed as small and large-size scatterplots, respectively.
For another half, we set the scatterplot size oppositely. Note that we fixed
all other properties of scatterplots. We displayed data points as black
circled dots on a white background and set the size of the point as 8px.

To alleviate the ordering effect, we randomize the order of scatterplots. To
further mitigate potential biases beyond scatterplot size, a blank screen was
placed between each scatterplot presentation. [6].

After the trials, we asked participants to fill out a short questionnaire to
gather qualitative data on their experience. Each participant’s entire session
lasted approximately 35 minutes. As a result, we collected 20 X 20 = 400
responses.

Participants We recruited 20 participants for our preliminary study,
comprising students and faculty members from a local university (aged from 20
to 53 years, 26$\pm$ 2.4). None of the participants reported visual or
physical disabilities that would impair their ability to view scatterplots or
use a keyboard and mouse. Experience with scatterplot analysis varied among
participants: 9 had some experience, 4 had extensive experience, and 2 had
little or no experience. Participants were compensated upon completion of
their tasks.

Figure 2: Cluster assignment on small (50px) vs large (350px) scatterplots
made by the participants of our user study. Smaller scatterplots lead
participants to identify less number of clusters with lower density and bigger
cluster area.

Apparatus. We developed a website in which participants could see scatterplots
and complete their tasks with a traditional wireless mouse. Given the
significance of consistent scatterplot size and viewing conditions, we
conducted the experiment in the same room for all participants. We positioned
a 21:9 2K monitor approximately $40\text{\,}\mathrm{c}\mathrm{m}$ away from
the participants’ eyes. Furthermore, we displayed the website on fullscreen so
that the scatterplot position and size were consistent. Keyboards were
disabled in case any erroneous input caused the website window to be minimized
or changed.

####  3.1.2 Results and Discussion

We conducted paired t-tests across 20 datasets to compare measurements between
small and large scatterplots. We identify three key changes between these
scatterplots: number of clusters, point density, and relative cluster area.

  * •

Number of Clusters: Paired t-tests revealed that there was a statistically
significant difference in the number of clusters, with larger scatterplots
generally exhibiting more clusters.($t=2.45,p<0.05$);

  * •

Point Density: Paired t-test revealed that there was a statistically
significant difference in point density, with larger scatterplots exhibiting
lower density. Cluster density is calculated by
$P_{density}=\frac{\text{Number of Points in Clusters}}{\text{Total Points}}$.
($t=2.10,p<0.05$).

  * •

Relative Cluster Area: Paired t-test revealed that there was a statistically
significant difference in relative cluster area, with larger scatterplots
exhibiting smaller relative area. This area is calculated by
$A_{relative}=\frac{\text{Area Covered by Clusters}}{\text{Scatterplot
Area}}$. ($t=1.98,p<0.05$).

The results confirm our hypothesis that changes in the size of monochrome
scatterplots significantly affect visual clustering results. The increase in
the number of clusters identified in larger scatterplots suggests that
participants may perceive more distinct groupings. Conversely, the higher
point density in clusters observed in smaller scatterplots might reflect a
tendency to group data points more tightly. Overall, the cluster assignments
in smaller scatterplots were more coarse-grained, resulting in denser and less
defined clusters. Meanwhile, cluster assignments in larger scatterplots were
more fine-grained, leading to sparser and more defined clusters.

The qualitative feedback from participants demonstrates awareness of
perceptual biases, with 14 out of 20 respondents acknowledging that they
perceived some form of bias during their clustering activity. Such variation
highlights the importance of educational tools or models that can make the
perception of clusters consistent across varying scatterplots.

###  3.2 Main Experiment

####  3.2.1 Objectives and Design

We want to explore whether adjusting the point size in scatterplots can
counteract perceptual biases caused by changes of scatterplot size. We do this
by investing in adjusting point sizes to ensure visual clustering to be
maintained consistently against different scatterplot sizes.

To do so, we showed scatterplot stimuli multiple times with different
scatterplot and point sizes and checked whether adjusting point sizes and
mitigating differences in scatterplot sizes. This time, we asked participants
to count the number of clusters. We selected a number of clusters among three
key differences we identified from the preliminary study (subsubsection 3.1.2)
as it is one of the least difficult tasks in visual clustering, thus reducing
the total running time of the experiment.

Our main assumption here is that increasing point size can mitigate the
perceptual bias of visual clustering incurred by the increment of scatterplot
size, and vice versa. Our assumptions build upon Wei’s finding [25] that the
increment/decrement of point size can remove perceptual bias in correlation,
density, and class separation tasks due to the increment/decrease of
scatterplot size.

The detailed study design is as follows.

Stimuli. We generated stimuli with the same methodology we used for the
preliminary study (subsection 3.1). Note that as we randomly sampled
scatterplots, the resulting set of stimuli is different from the previous
experiment. We again denote these scatterplots as
$\mathcal{S}=\\{S_{1},\cdots,S_{20}\\}$.

Procedure. As with the preliminary experiment (subsection 3.1), we conducted
the experiment in person. After participants signed a consent form, we gave
same instruction to participants with the preliminary experiment, except that
the task is to count the number of clusters.

We then showed participants a series of scatterplots with different point and
scatterplot sizes, and asked participants to count the number of clusters. For
each trial, we first randomly sample a single stimulus $S_{i}$ from
$\mathcal{S}$. Then, if $S_{i}$ has never been shown to the participant, we
randomly set the scatterplot size from 50px to 350px. If it is the second
appearance of $S_{i}$, we randomized the scatterplot size from 50px to 350px
but ensured the difference with the scatterplot size of the first appearance
to be bigger than 120px. This is to identify whether perceptual bias occurred
from changing the scatterplot size. For more than a third appearance of
$S_{i}$, we maintained the scatterplot size from the second appearance but
adjusted point size depending on the previous cluster count report. If cluster
count is reported to be bigger than the initial cluster count, then the point
size is increased by 1px. Otherwise, the point size is decreased by 1px. If
the cluster count is the same as the initial cluster count, $S_{i}$ is
reported as success and removed from $\mathcal{S}$ so that it would not appear
afterward. If the point size reaches 0px or 20px, $S_{i}$ is marked as a
failure and also removed from $\mathcal{S}$. This adjustment procedure was
established to verify whether point size can offset the perceptual bias made
by the alter of scatterplot size.

There was no wrap-up interview for this experiment.

Participants and Appratus. We recruited 20 new participants (aged from 21 to
35 years, 24$\pm$ 2.1). The participants’ experience with analyzing
scatterplots varied: 11 had some experience, 7 had extensive experience, and 2
had little or no experience. The viewing conditions and apparatus remained
consistent with those used in the preliminary experiment.

####  3.2.2 Results and Discussions

We first investigated how the success rate increased by step number. To do so,
we first removed 34 cases where the number of clusters did not change between
step 0 and step 1. We then computed the individual and cumulative success
rates of each step. As a result (Figure 3), we found that the success rate
gradually increased, resulting in 70.7% at last (Step 6). However, the
increase eventually slows down between Steps 5 and 6.

Then, we calculated the mean error rate at each step. Formally, the mean error
rate is defined as:

$\text{Mean Error Rate}=\frac{\left|\text{Initial Cluster \\#}-\text{Perceived
Cluster \\#}\right|}{\text{Initial Cluster \\#}}.$

As seen in Figure 4, mean error rates gradually decrease as the steps in
increase from 2 to 6.

Such results clearly indicate that adjusting point size can mitigate
perceptual bias on visual clustering occurred due to scatterplot size changes.
However, the fact that the increment of success rate becomes gradual as step
number increases informs that there still remains bias that can hardly be
offsetted by just changing point size.

Figure 3: The cumulative and individual step success rates in our main
experiment. An increase from each step number indicates that the point change
successfully offset the perceptual bias resulting from changes in scatterplot
size. Figure 4: Mean error rate for failed attempts to offset perceptual bias
in our main experiment. The decrease in mean error rates indicates that the
perceived cluster count progressively converged towards the initial cluster
count. The line denotes the 95% confidence interval.

##  4 Discussions

In this research, we found that scatterplot size can alter cluster perception
and verified that adjusting point sizes can mitigate such perceptual bias. Our
limitation is that we lack a grounded, automatic methodology that guides us in
determining the most appropriate scatterplot and point sizes.

To resolve this remaining challenge, we further aim to develop a mathematical
model that can predict the most appropriate point size for a given scatterplot
pattern and size. To this end, we aim to conduct a large-scale study that can
cover diverse cluster features (e.g., data distribution, number of clusters,
density).

We believe that the model will substantially aid visual analytics by enabling
the following applications:

Communicative/collaborative analytics environments. In communicative and
collaborative environments, people may see the same scatterplot with different
devices. We can think about a situation in which the lecturer is explaining
data science techniques using scatterplots (Figure 2). By utilizing the model
to adjust scatterplot size and point size, we can make cluster perception
consistent across different analysts.

Responsive visualization. We can also apply the model to make visualizations
responsively adjust their visual encoding, reacting to the changes in display
(e.g., foldable devices [20]) or window size. This will help analysts or
stakeholders to consistently maintain their perception of the scatterplots,
thus potentially reducing confusion while making decisions based on the
scatterplots.

##  5 Conclusion

Data analysis can be conducted using various displays, such as smartphones,
desktop computers, and tabletop displays. Consequently, the size of
scatterplots may vary due to these differences. In this research, we reveal
that such changes in scatterplot sizes can alter visual clustering and verify
that adjusting point sizes can mitigate such perceptual bias. Our work opens
up the opportunity to build automated systems that adjust the visual encoding
of scatterplots in various displays to make visual perception consistent over
time and space.

## References

  * [1] M. M. Abbas, M. Aupetit, M. Sedlmair, and H. Bensmail.  Clustme: A visual quality measure for ranking monochrome scatterplots based on cluster patterns.  Computer Graphics Forum, 38(3):225–236, 2019. doi: 10 . 1111/cgf . 13684
  * [2] M. M. Abbas, M. Aupetit, M. Sedlmair, and H. Bensmail.  Clustme: A visual quality measure for ranking monochrome scatterplots based on cluster patterns.  In Computer Graphics Forum, vol. 38, pp. 225–236. Wiley Online Library, 2019.
  * [3] C. Andrews, A. Endert, B. Yost, and C. North.  Information visualization on large, high-resolution displays: issues, challenges, and opportunities.  Information Visualization, 10(4):341–355, oct 2011. doi: 10 . 1177/1473871611415997
  * [4] W. Cleveland and R. McGill.  The many faces of a scatterplot.  Journal of the American Statistical Association, 79:807–822, 1984. doi: 10 . 1080/01621459 . 1984 . 10477098
  * [5] W. S. Cleveland and R. McGill.  The many faces of a scatterplot.  Journal of the American Statistical Association, 79(388):807–822, 1984.
  * [6] C. Healey and J. Enns.  Attention and visual memory in visualization and computer graphics.  IEEE transactions on visualization and computer graphics, 18(7):1170–1188, 2011.
  * [7] J. Heer and M. Agrawala.  Multi-scale banking to 45 degrees.  IEEE Transactions on Visualization and Computer Graphics, 12(5):701–708, 2006. doi: 10 . 1109/TVCG . 2006 . 163
  * [8] J. Heer and M. Bostock.  Crowdsourcing graphical perception: using mechanical turk to assess visualization design.  CHI ’10. Association for Computing Machinery, New York, NY, USA, 2010. doi: 10 . 1145/1753326 . 1753357
  * [9] M.-H. Hong, J. K. Witt, and D. A. Szafir.  The weighted average illusion: Biases in perceived mean position in scatterplots.  IEEE Transactions on Visualization and Computer Graphics, 28(1):987–997, 2022. doi: 10 . 1109/TVCG . 2021 . 3114783
  * [10] M. R. Jakobsen and K. Hornbæk.  Interactive visualizations on large and small displays: The interrelation of display size, information space, and scale.  IEEE Transactions on Visualization and Computer Graphics, 19:2336–2345, 2013. doi: 10 . 1109/TVCG . 2013 . 170
  * [11] H. Jeon, G. J. Quadri, H. Lee, P. Rosen, D. A. Szafir, and J. Seo.  Clams: A cluster ambiguity measure for estimating perceptual variability in visual clustering.  IEEE Transactions on Visualization and Computer Graphics, 30(1):770–780, 2024. doi: 10 . 1109/TVCG . 2023 . 3327201
  * [12] M. Kraus, N. Weiler, D. Oelke, J. Kehrer, D. Keim, and J. Fuchs.  The impact of immersion on cluster identification tasks.  IEEE Transactions on Visualization and Computer Graphics, 26:525–535, 2020. doi: 10 . 1109/TVCG . 2019 . 2934395
  * [13] S. Lewandowsky and I. Spence.  Discriminating strata in scatterplots.  Journal of the American Statistical Association, 84(407):682–688, 1989.
  * [14] H. Liao, Y. Wu, L. Chen, and W. Chen.  Cluster-based visual abstraction for multivariate scatterplots.  IEEE Transactions on Visualization and Computer Graphics, 24:2531–2545, 2018. doi: 10 . 1109/TVCG . 2017 . 2754480
  * [15] Y. Ma, A. K. Tung, W. Wang, X. Gao, Z. Pan, and W. Chen.  Scatternet: A deep subjective similarity model for visual analysis of scatterplots.  IEEE transactions on visualization and computer graphics, 26(3):1562–1576, 2018.
  * [16] Q. V. Nguyen, N. Miller, D. Arness, W. Huang, M. L. Huang, and S. Simoff.  Evaluation on interactive visualization data with scatterplots.  Visual Informatics, 4(4):1–10, 2020. doi: 10 . 1016/j . visinf . 2020 . 09 . 004
  * [17] G. J. Quadri and P. Rosen.  Modeling the influence of visual density on cluster perception in scatterplots using topology.  IEEE Transactions on Visualization and Computer Graphics, 27(2):1829–1839, 2020.
  * [18] A. Sarikaya and M. Gleicher.  Scatterplots: Tasks, data, and designs.  IEEE Transactions on Visualization and Computer Graphics, 24(1):402–412, 2018. doi: 10 . 1109/TVCG . 2017 . 2744184
  * [19] A. Sarikaya, M. Gleicher, and D. A. Szafir.  Design factors for summary visualization in visual analytics.  In Computer Graphics Forum, vol. 37, pp. 145–156. Wiley Online Library, 2018.
  * [20] S. Schirra and C. Barta.  Foldables and 2-in-1s: Understanding and supporting the needs of hybrid device users.  In Proceedings of the 2021 ACM International Conference on Interactive Media Experiences, IMX ’21, p. 237–240. Association for Computing Machinery, New York, NY, USA, 2021. doi: 10 . 1145/3452918 . 3465503
  * [21] M. Sedlmair, A. Tatu, T. Munzner, and M. Tory.  A taxonomy of visual cluster separation factors.  Computer Graphics Forum, 31(3pt4):1335–1344, 2012. doi: 10 . 1111/j . 1467-8659 . 2012 . 03125 . x
  * [22] D. A. Szafir.  Modeling color difference for visualization design.  IEEE Transactions on Visualization and Computer Graphics, 24(1):392–401, 2018. doi: 10 . 1109/TVCG . 2017 . 2744359
  * [23] L. Tremmel.  The visual separability of plotting symbols in scatterplots.  Journal of Computational and Graphical Statistics, 4(2):101–112, 1995.
  * [24] C. Ware.  Information Visualization: Perception for Design: Second Edition.  04 2004.
  * [25] Y. Wei, H. Mei, Y. Zhao, S. Zhou, B. Lin, H. Jiang, and W. Chen.  Evaluating perceptual bias during geometric scaling of scatterplots.  IEEE Transactions on Visualization and Computer Graphics, 26(1):321–331, Jan. 2020. doi: 10 . 1109/tvcg . 2019 . 2934208
  * [26] M. E. M. William S. Cleveland and R. McGill.  The shape parameter of a two-variable graph.  Journal of the American Statistical Association, 83(402):289–300, 1988. doi: 10 . 1080/01621459 . 1988 . 10478598
  * [27] J. Xia, W. Lin, G. Jiang, Y. Wang, W. Chen, and T. Schreck.  Visual clustering factors in scatterplots.  IEEE Computer Graphics and Applications, 41(5):79–89, 2021.
  * [28] M. Ziefle.  Effects of display resolution on visual performance.  Human factors, 40:554–68, 01 1999. doi: 10 . 1518/001872098779649355


# Graph neural networks with configuration cross-attention for tensor
compilers

Dmitrii Khizbullin
King Abdullah University of Science and Technology (KAUST)
Thuwal, Saudi Arabia
<EMAIL_ADDRESS>
Eduardo Rocha de Andrade
Sprout.ai
London, UK
&Thanh Hau Nguyen
Sprout.ai
London, UK
&Matheus Pedroza Ferreira
Sprout.ai
London, UK
David R. Pugh
KAUST
Thuwal, Saudi Arabia
<EMAIL_ADDRESS>
Corresponding Author<EMAIL_ADDRESS>
###### Abstract

With the recent popularity of neural networks comes the need for efficient
serving of inference workloads. A neural network inference workload can be
represented as a computational graph with nodes as operators transforming
multidimensional tensors. The tensors can be transposed and/or tiled in a
combinatorially large number of ways, some configurations leading to
accelerated inference. We propose TGraph, a neural graph architecture that
allows screening for fast configurations of the target computational graph,
thus representing an artificial intelligence (AI) tensor compiler in contrast
to the traditional heuristics-based compilers. The proposed solution improves
mean Kendall’s $\tau$ across layout collections of TpuGraphs from 29.8% of the
reliable baseline to 67.4% of TGraph. We estimate the potential CO2 emission
reduction associated with our work to be equivalent to over 50% of the total
household emissions in the areas hosting AI-oriented data centers.

https://github.com/thanhhau097/google_fast_or_slow.

##  1 Introduction

Machine learning (ML) continues to gain popularity in solving engineering
tasks, including Large Language Models for natural language processing,
convolutional and transformer models for computer vision, recommendation
models in online services, etc. The majority of the computation associated
with ML goes into serving the ML models for inference rather than training
them. The need to reduce monetary costs as well as the CO2 footprint of
inference workloads leads to significant efforts in the optimization of
computations. Typically, ML workloads are launched on specialized accelerators
(GPUs, TPUs), which do not provide the same level of on-chip real-time
optimization as CPUs do. Consequently, the complexity of optimization of
computations for ML accelerators is shifted towards the compiler.
Implementation of an enormous quantity of specialized kernels supporting the
full matrix formed by a variety of accelerators times a variety of ML models
is intangible. One solution to this problem is to employ ML-based tensor
compilers.

###  1.1 Related work

Several attempts have been made to build a highly efficient tensor compiler in
recent years. Tensorflow [1] has a rule-based tensor program optimization
engine XLA [18] that was studied by [19]. TVM [5] introduces Python-based
meta-language to describe the computation and its execution schedule
separately, allowing a range of automated optimizations mostly limited to one
operator and avoiding operator (kernel) fusion. AutoTVM [6] introduces
optimization of tensor programs based on gradient-boosted trees and TreeGRU
and uses the ranking loss for model training rather than element-wise losses
like MSE. PyTorch [14], being a framework built with the imperative paradigm
in mind, in its recent version, supports TorchScript, a just-in-time (JIT)
compiled for the annotated functions and classes. JAX [3] as a functional
meta-language natively supports JIT.

TASO [9] performs equivalent graph substitution as a way to fuse kernels. PET
[21] then builds on top of TASO [9] to expand the search space to non-
equivalent transformations and apply automatically generated correction
kernels. DeepCuts [11], Ansor [24], and TensorComp [20] rely on heuristics to
solve the problem of efficient execution of a computational graph. NN-Meter
[23] presents a latency prediction model based on a combination of heuristics
to account for the effects of kernel fusion and a random forest for single-
operator latency prediction.

All the aforementioned works mostly rely on heuristics and rules to compile a
tensor program. While the compilation time of a heuristics-based algorithm may
be very small, it fails to achieve the absolute minimum of program runtime. In
this work, we propose an algorithm based on machine learning to optimize a
tensor program that is represented as a computational graph. The closest work
to ours are Phothilimthana, 2020 [15] and Xu, 2023 [22] that use the same
dataset and a benchmark TpuGraphs [16]. Graph Segment Training (GST) [4] uses
TpuGraphs as well but reports another metric, OPA, and does not provide a
breakdown across the collections.

###  1.2 Contribution summary

Our contributions can be summarized as follows:

  * •

We propose TGraph, a graph neural network (GNN) architecture with cross-
channel and cross-configuration attention that achieves state-of-the-art on
the TpuGraphs benchmark.

  * •

We show very efficient training and inference by applying non-configurable
node pruning, configuration de-duplication, and compression.

###  1.3 Societal impact

We perform a case study to highlight the importance of data center AI workload
optimization. According to our estimates the potential impact of this work can
be reduction of CO2 emissions equivalent to 50% (or higher) of household
emissions in areas similar to North Virginia, VA. The details can be found in
Section A.1.

###  1.4 Dataset and benchmark details

The only publicly available dataset for the large-scale compiler configuration
search is TpuGraphs [16]. TpuGraphs contains execution times of an XLA’s HLO
graph with a specific compiler configuration on a Tensor Processing Unit (TPU
v3). TpuGraphs focuses on optimizing tensor layouts and tensor tiling as
compiler configurations. Tensor layout optimization dataset comprises 4
collections organized in a matrix shown in Table 1. The two groups of network
architectures (xla and nlp) represent two distinct categories of workloads:
xla \- predominantly computer vision loads, while nlp \- exclusively
transformer-based natural language processing loads. Each architecture has up
to 100’000 different tensor layout configurations and the associated runtimes
recorded. Another dimension across which the layout dataset is organized is
the utilized configuration search strategy: random or genetic-algorithm-based
(GA-based, denoted as Default). Even though the final goal is to be able to
predict configurations’ runtimes, during the dataset creation, some sort of
bootstrapping search must be used. Random search gives very wide coverage
across all the possible runtimes, whereas the GA-based search focuses more on
sampling runtimes in the vicinity of the fastest runtime, making the task of
runtime prediction harder and very challenging for the predictive model.

Table 1: The matrix of the 4 Layout collections |  | Configuration sampling strategy
---|---|---
|  |  Random (uniform) |  Default (GA-based)
Group of graphs |  XLA (CV, NLP and other) |  layout-xla-random |  layout-xla-default
NLP (Transformers) |  layout-nlp-random |  layout-nlp-default

##  2 TGraph runtime ranking architecture

###  2.1 Problem specification

We are looking to find the configuration $\tilde{c}$ that minimizes the tensor
program runtime $R(c)$ across the configuration space $C$.

$\displaystyle\tilde{c}=\underset{c\in C}{\text{argmin}}\left(R(c)\right)$ (1)

As we have only partial knowledge of R(c) in the form of benchmarked data, we
are looking for a solution as an approximation $R_{neural}(c)$ of the
underlying true $R(c)$.

###  2.2 Data pre-processing

####  2.2.1 Graph pruning

For layout collections, only Convolution, Dot, and Reshape nodes are
configurable. Also, in most cases, the majority of nodes are identical across
the configuration set. Thus, we adopt the following pruning strategy: for each
graph, we only keep the nodes that are either configurable nodes themselves or
are connected to a configurable node, i.e., input or output to a configurable
node. By doing this, we transform a single graph into multiple (possibly
disconnected) sub-graphs. The possibly disconnected graph does not pose a
problem since TGraph has a global graph pooling layer as one of the final
layers that fuses the sub-graph information. This way of graph pruning reduces
the vRAM usage 4 times and speeds up training by a factor of 5 in some cases.
An example of graph pruning is shown on Figure 1

Figure 1:  An example of node pruning. Nodes that are not connected to
configurable nodes are removed (red nodes on the diagram). Two disconnected
subgraphs are left after pruning.

####  2.2.2 Configuration deduplication

Most of the configuration sets for layout collections contain a lot of
duplication. The runtime for the duplicated configuration sets can vary up to
0.4% of the mean value. Training on the same configuration sets but different
runtime targets makes loss noisy and the training process less stable. Thus,
we remove all the duplicated configuration sets for layout collections and
leave the smallest runtime value for determinism.

####  2.2.3 Lossless configuration compression

Even with pruning and de-duplication, the RAM usage to load all configurations
to the system memory for NLP collections is beyond the RAM capacity. We
circumvent that issue by compressing node_config_feat beforehand and only
decompressing it on the fly in the data loader after configuration sampling.
This allows us to load all data to memory at the beginning of training, which
reduces IO/CPU bottlenecks considerably and allows us to train faster. The
compression is implemented based on the fact that each node_config_feat 6-dim
vector (input, output, and kernel) can only have 7 possible values (-1, 0, 1,
2, 3, 4, 5) and, thus, can be represented by a single integer in base-7 (from
0 to $7^{6}-1$).

####  2.2.4 Changing the pad value in node_feat

The features in node_feat are 0-padded. Whilst this is not a problem for most
features, for others like layout_minor_to_major_*, this can be ambiguous since
0 is a valid axis index. Also, the node_config_feat are -1 padded, which makes
it incompatible with layout_minor_to_major_* from node_feat. With that in
mind, we re-generate node_feat with -1 padded, and this allows us to use a
single embedding matrix for both node_feat[134:] and node_config_feat.

####  2.2.5 Data normalization, embedding and batching

For layout, the node features are formed as a 140-dimensional vector node_feat
that represents various fields in an XLA’s HLO instruction (a node in an HLO
graph) either as they are, or as categorical values using one-hot encoding. We
split node_feat into node_feat[:134] containing numerical and one-hot-encoded
values and node_feat[134:] that contains the tensor index permutation of the
output tensor layout (layout_minor_to_major_*). The former is normalized to
element-wise 0-mean and unit standard deviation (StandardScaler on Figure 2),
while the latter, along with node_config_feat, is fed into a learned embedding
matrix (4 channels). We find that the normalization is essential since
node_feat has features like *_sum and *_product that can be very high in
values compared to the rest of the features and, consequently, disrupt the
optimization. Further, we find that the natural way to encode the permutation
vectors is to embed them into a low-dimensional vector. For node_opcode, we
also use a separate embedding layer with 16 channels. The input to the network
is the concatenation of all aforementioned features. For each graph, we sample
on the fly a batch of 64 (for default collections) or 128 (for random
collections) configurations to form the input batch. For tile, on the other
hand, we opt to use late fusion to integrate config_feat into the network.

###  2.3 Architecture details

Following the reasoning laid out by [15], we employ GraphSAGE [7] as a basis
of a graph convolutional block. GraphSage operation can be expressed as

$\displaystyle
S_{i}^{k}(\varepsilon)=N_{L2}\left(f_{2}^{k}\left(\text{concat}\left(\varepsilon_{i},\sum_{j\in\text{neighbors}(i)}f_{1}^{k}\left(\varepsilon_{j}\right)\right)\right)\right)$
(2)

where $i$ is the index of a node, $k$ is the index of the layer,
$f_{1...2}^{k}$ \- feedforward layers at the specific depth $k$, $N_{L2}$ \-
$L_{2}$ normalization, $neighbours(i)$ \- a set of immediate neighbours of
node $i$.

We construct the graph convolutional block that can be expressed in the
following way.

$\displaystyle
B_{i}^{k}(\varepsilon)=\varepsilon+a\left(\text{concat}\left(\eta_{i},A_{cross}(\eta_{i})\right)\right)$
(3)

where $a$ is GELU activation, $A_{cross}$ \- configuration cross-attention
operation, and $\eta_{i}(\varepsilon)$ is expressed as:

$\displaystyle\eta_{i}(\varepsilon)=A_{self}\left(S_{i}^{k}\left(N_{instance}\left(\varepsilon\right)\right)\right)$
(4)

Here $A_{self}$ is the self-attention operation described below,
$N_{instance}$ is instance normalization.

####  2.3.1 Channel-wise self-attention

Inspired by the idea of Squeeze-and-Excitation [8], we add a channel-wise
self-attention layer as a part of the graph convolutional block. We first
apply a Linear layer to bottleneck the channel dimensions (8x reduction),
followed by ReLU. Then, we apply a second linear layer to increase the
channels again to the original value, followed by sigmoid. We finish by
applying element-wise multiplication to the obtained feature map and the
original input. The idea behind channel-wise self-attention is to capture the
correlations between channels and use them to suppress less useful ones while
enhancing the important ones.

$\displaystyle
A_{self}(\varepsilon)=\varepsilon\circ\sigma\left(f_{squeeze}\left(\text{ReLU}\left(f_{excitation}(\varepsilon)\right)\right)\right)$
(5)

Here $\circ$ denotes element-wise multiplication.

####  2.3.2 Cross-Configuration Attention

Another dimension in which we apply the attention mechanism is the batch
dimension: across the sampled configurations. We design the cross-
configuration attention block that allows the model to explicitly compare each
configuration against the others throughout the network. We find this method
to be much superior to letting the model infer for each configuration
individually and only compare them implicitly via the loss function
(PairwiseHingeLoss in this paper). The cross-configuration attention
expression comes as follows:

$\displaystyle
A_{cross}(\varepsilon)=\varepsilon_{i}^{b}\circ\underset{b}{\text{Softmax}}\left(\varepsilon_{i}^{b}/T\right)$
(6)

Here $i$ is the node index, $b$ is the configuration index across the batch
dimension, $T$ is a learnable temperature parameter.

By applying the cross-configuration attention layer after the channel-wise
self-attention at every block of the network, we observe a significant
improvement of the target metric (Kendall’s $\tau$), especially for default
collections.

####  2.3.3 Entire architecture

The full architecture of TGraph is shown in Figure 2. After feature
concatenation, we apply a fully-connected layer, then we apply a stack of 2
graph convolutional blocks $B_{i}^{k}$, $k\in 1..2$, then we perform global
average pooling over the node dimension indexed by $i$, and finally, we apply
another linear layer to eliminate the feature dimension and get the vector of
scores $s_{c}$ where $c$ is the index across the configuration dimension.

The entire network prediction can be expressed as:

$\displaystyle
R_{neural}(X)=f_{out}\left(Pool_{global}\left(B_{2}\left(B_{1}\left(f_{in}\left(X\right)\right)\right)\right)\right)$
(7)

where $X$ is the input feature vector, $f_{in}$ \- a 2-layer MLP with {256,
256} features and GELU activation, $f_{out}$ \- linear layer with a single
feature and no activation, $Pool_{global}$ \- global average pooling across
nodes.

Figure 2:  Architecture diagram of TGraph. $n_{configs}$ is the number of
configurations sampled into a batch. $n_{nodes}$ is the number of nodes in the
sampled graph after pruning.

###  2.4 Training and inference procedures

####  2.4.1 Loss function

We use the Pairwise Hinge Loss (PairwiseHingeLoss, [10], [2]) loss function
for training the model.

$\displaystyle\mathcal{L}(\\{r\\},\\{s\\})=\sum_{i}\sum_{j}I[r_{i}>r_{j}]\max(0,1-(s_{i}-s_{j}))$
(8)

where $r_{i}$ \- are the ground truth runtimes, $s_{i}$ \- are the scores
predicted by the model.

It is important that the predicted scores $s_{i}=R_{neural}(c_{i})$ do not
correspond to the absolute values of runtimes $r_{i}=R(c_{i})$. The applied
loss function is a ranking loss function. It trains the model to order (rank)
the predicted values in the same way as they are ordered by $R(c)$. The
correct ordering is enough to satisfy Equation 1.

####  2.4.2 Training details

We train separate model instances for all collections. We’ve identified that
separate models perform better than a joint model trained on all collections
or models that were trained on all-xla or all-nlp combinations as well as all-
random or all-default.

We use Adam [12] optimizer (specifically AdamW version) with the learning rate
of 1e-3, 0.05 of the total number of epochs as linear warm-up, a single-cycle
(lifted cosine) learning rate schedule, and weight decay of 1e-5 for non-bias
parameters. We apply gradient norm clipping at value 1.0.

We train the tile-xla collection for 17.5 epochs, whereas layout-nlp
collections for 1000 epochs and layout-xla collections for 750 epochs.

Training wall-clock time is 2.5 hours per fold per collection measured on
RTX4090 with 24 GB RAM. Training one set of models for all collections
produces 13.45 kg CO2 as per [13].

####  2.4.3 Data splits

Whereas the official training/validation split is reasonably designed, we,
however, employ K-fold cross-validation with $K=20$ on the merged
train/validation data splits. We train the first 5 folds to limit the training
compute. We then pick the top-4 folds by the validation score to combat the
instability of training. This choice comes from the slight instability of
training: in rare cases, the training process for a specific fold may get
stuck at a local minimum or experience partial parameter corruption due to
gradient explosion. In addition, we choose not to split configurations of the
same graph into train/validation since it would introduce a train-to-
validation leak due to the very high correlation of configuration runtimes
within the same graph.

###  2.5 Benchmark results

####  2.5.1 Evaluation splits

TpuGraphs [16] dataset does not provide public test data annotations. Hence,
we report the cross-validation score according to the Section 2.4.3.

####  2.5.2 Evaluation metrics

Kendall’s $\tau$ (Kendall’s rank correlation coefficient) is used as the
metric for layout collections:

$\displaystyle\tau=\frac{2}{n(n-1)}\sum_{i<j}\text{sgn}(s_{i}-s_{j})\text{sgn}(r_{i}-r_{j})$
(9)

where $s$ are the predicted scores, $r$ are the ground truth runtimes, $n$ is
the batch size.

For the tile collection, the metric is set as:

$\displaystyle M_{tile}=1-\left(\frac{\text{The best runtime of the top-$k$
predictions}}{\text{The best runtime of all
configurations}}-1\right)=2-\frac{\min_{i\in K}r_{i}}{\min_{i\in A}r_{i}}$
(10)

where $K=5$.

####  2.5.3 Details of the inference mode

For inference, we use the batch size of 128. However, since the prediction
depends on the batch, we leverage the batch further by applying test-time
augmentation (TTA) to generate N (10) permutations of the configurations and
average the result after sorting it back to the original order. We average the
scores of models trained on different folds.

The single-batch wall clock time is 60 ms on average for 1 fold and 240 ms on
average for all 4 folds per collection.

####  2.5.4 Experimental results

Table 2: Experimental results |  | Validation score
---|---|---
Collection | Metric | TpuGraphs [16] | Xu 2023 [22] | TGraph (ours)
layout:xla:random | Kendall’s $\tau$ | 0.19 | 0.5285 |  0.6840 $\pm$ 0.0110
layout:xla:default | Kendall’s $\tau$ | 0.12 | 0.5887 | 0.4785 $\pm$ 0.0031
layout:nlp:random | Kendall’s $\tau$ | 0.58 | 0.8387 |  0.9713 $\pm$ 0.0008
layout:nlp:default | Kendall’s $\tau$ | 0.30 | 0.4841 |  0.5628 $\pm$ 0.0027
mean across layout | Kendall’s $\tau$ | 0.298 | 0.610 | 0.674
tile:xla | $M_{tile}$ | - | 0.8622 |  0.9694 $\pm$ 0.0021

Our experimental results are summarized in the Table 2. The confidence ranges
are reported as 1-sigma. We demonstrate state-of-the-art performance in 4 out
of 5 collections. On xla-default Xu 2021 [22] show better results than our
work; however, their results may contain an error since xla-default collection
is harder than xla-random due to closer and harder-to-distinguish runtime
annotations (the pattern is also followed by the results of TpuGraphs [16]),
but the score of [22] for xla-default is higher than for xla-random which is
very implausible.

##  3 Conclusion

The proposed novel TGraph neural network architecture establishes a state-of-
the-art on the TpuGraphs dataset. A significant contribution to the
performance comes from channel-wise self-attention and cross-configuration
attention operations. The latter acts as one of the batch normalization
techniques, allowing the exchange of information between individual samples,
which improves performance in ranking problems.

In general, more efficient ML-based tensor compilation methods have a very
positive societal impact. Firstly, they decrease energy consumption and CO2
emissions of data centers, consequently helping to fight climate change.
Secondly, they help to free software engineers from the tedious labor of re-
implementing lots of highly specialized computational kernels for the constant
flow of hardware releases. Even though it may seem that it is a case of "AI
taking over people’s jobs", in fact, the achieved extreme efficiency of
digital infrastructure like data centers may cover the needs of people to the
extent that they do not need to work or can opt to dedicate themselves to more
human-centered activities.

##  4 Limitations

The proposed neural network architecture is limited to predicting the runtimes
of a static tensor program that can be represented as a computational graph.
Another limitation is that the proposed method is not able to learn the
behavior of the tensor program if the behavior is dependent on the values of
input or intermediate data. As a machine learning algorithm, the proposed
method requires a substantial amount of training data. In the absence of a
diverse sample of benchmarked architectures, the domain gap between the
training graphs and the unknown test graphs may be big enough, and the model
is not able to generalize to it. The proposed method does not provide any
guidance on how to choose the graphs for the creation of the training dataset.
The proposed method does not generalize to unknown operators. New graphs with
the new operator must be added to the training data in order for the model to
learn the information about its contribution to the runtime. An ML model
trained on one hardware (TPU) does not necessarily generalize to other
hardware (GPU, CPU, etc) and must be re-trained for other hardware. Lastly,
the proposed solution addresses two compilation sub-problems: tensor layout
selection and tensor tiling selection, whereas there are more sub-problems to
be solved by tensor compilers.

## Acknowledgments and Disclosure of Funding

This work was supported by the SDAIA-KAUST Center of Excellence in Data
Science and Artificial Intelligence (SDAIA-KAUST AI).

This work was supported by the prizes of the 1st and the 2nd winning places of
"Google - Fast or Slow? Predict AI Model Runtime" Kaggle competition.

## References

  * [1] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, and Xiaoqiang Zhang.  Tensorflow: A system for large-scale machine learning.  12th USENIX Symposium on Operating Systems Design and Implementation (OSDI ’16), May 2016.
  * [2] Aman Agarwal, Kenta Takatsu, Ivan Zaitsev, and Thorsten Joachims.  A general framework for counterfactual learning-to-rank.  In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR’19, page 5–14, New York, NY, USA, 2019. Association for Computing Machinery.
  * [3] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang.  JAX: composable transformations of Python+NumPy programs, 2018.
  * [4] Kaidi Cao, Phitchaya Mangpo Phothilimthana, Sami Abu-El-Haija, Dustin Zelle, Yanqi Zhou, Charith Mendis, Jure Leskovec, and Bryan Perozzi.  Learning large graph property prediction via graph segment training.  ArXiv, abs/2305.12322, 2023.
  * [5] Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Haichen Shen, Meghan Cowan, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy.  TVM: An automated End-to-End optimizing compiler for deep learning.  In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18), pages 578–594, Carlsbad, CA, October 2018. USENIX Association.
  * [6] Tianqi Chen, Lianmin Zheng, Eddie Yan, Ziheng Jiang, Thierry Moreau, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy.  Learning to optimize tensor programs.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
  * [7] William Hamilton, Rex Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  31st Conference on Neural Information Processing Systems (NIPS 2017), June 2017.
  * [8] Jie Hu, Li Shen, and Gang Sun.  Squeeze-and-excitation networks.  In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7132–7141, 2018.
  * [9] Zhihao Jia, Oded Padon, James Thomas, Todd Warszawski, Matei Zaharia, and Alex Aiken.  Taso: optimizing deep learning computation with automatic generation of graph substitutions.  SOSP ’19, page 47–62, New York, NY, USA, 2019. Association for Computing Machinery.
  * [10] Thorsten Joachims.  Optimizing search engines using clickthrough data.  In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’02, page 133–142, New York, NY, USA, 2002. Association for Computing Machinery.
  * [11] Wookeun Jung, Thanh Tuan Dao, and Jaejin Lee.  Deepcuts: a deep learning optimization framework for versatile gpu workloads.  In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2021, page 190–205, New York, NY, USA, 2021. Association for Computing Machinery.
  * [12] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [13] Alexandre Lacoste, Alexandra Sasha Luccioni, Victor Schmidt, and Thomas Dandres.  Quantifying the carbon emissions of machine learning.  ArXiv, abs/1910.09700, 2019.
  * [14] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [15] Mangpo Phothilimthana, Mike Burrows, Sam Kaufman, and Yanqi Zhou.  A learned performance model for the tensor processing unit.  Technical report, 2020.
  * [16] Phitchaya Mangpo Phothilimthana, Sami Abu-El-Haija, Kaidi Cao, Bahare Fatemi, Michael Burrows, Charith Mendis, and Bryan Perozzi.  Tpugraphs: A performance prediction dataset on large tensor computational graphs.  In Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023.
  * [17] Phitchaya Mangpo Phothilimthana, Amit Sabne, Nikhil Sarda, Karthik Srinivasa Murthy, Yanqi Zhou, Christof Angermueller, Mike Burrows, Sudip Roy, Ketan Mandke, Rezsa Farahani, Yu Emma Wang, Berkin Ilbeyi, Blake A. Hechtman, Bjarke Hammersholt Roune, Shen Wang, Yuanzhong Xu, and Samuel J. Kaufman.  A flexible approach to autotuning multi-pass machine learning compilers.  2021 30th International Conference on Parallel Architectures and Compilation Techniques (PACT), pages 1–16, 2021.
  * [18] Amit Sabne.  Xla: Compiling machine learning for peak performance, 2020.
  * [19] Danielle Snider and Ruofan Liang.  Operator fusion in xla: Analysis and evaluation.  ArXiv, abs/2301.13062, 2023.
  * [20] Nicolas Vasilache, Oleksandr Zinenko, Theodoros Theodoridis, Priya Goyal, Zachary DeVito, William Moses, Sven Verdoolaege, Andrew Adams, and Albert Cohen.  Tensor comprehensions: Framework-agnostic high-performance machine learning abstractions.  Facebook AI Research Technical Report., 2018.
  * [21] Haojie Wang, Jidong Zhai, Mingyu Gao, Zixuan Ma, Shizhi Tang, Liyan Zheng, Yuanzhi Li, Kaiyuan Rong, Yuanyong Chen, and Zhihao Jia.  PET: Optimizing tensor programs with partially equivalent transformations and automated corrections.  In 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI 21), pages 37–54. USENIX Association, July 2021.
  * [22] Jingyu Xu, Linying Pan, Qiang Zeng, Wenjian Sun, and Weixiang Wan.  Based on tpugraphs predicting model runtimes using graph neural networks.  Frontiers in Computing and Intelligent Systems, 6:66–69, November 2023.
  * [23] Li Lyna Zhang, Shihao Han, Jianyu Wei, Ningxin Zheng, Ting Cao, Yuqing Yang, and Yunxin Liu.  nn-meter: Towards accurate latency prediction of deep-learning model inference on diverse edge devices.  In Proceedings of the 19th Annual International Conference on Mobile Systems, Applications, and Services, page 81–93, New York, NY, USA, 2021. ACM.
  * [24] Lianmin Zheng, Chengfan Jia, Minmin Sun, Zhao Wu, Cody Hao Yu, Ameer Haj-Ali, Yida Wang, Jun Yang, Danyang Zhuo, Koushik Sen, Joseph E. Gonzalez, and Ion Stoica.  Ansor: generating high-performance tensor programs for deep learning.  In Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation, OSDI’20, USA, 2020. USENIX Association.

###### Contents

  1. 1 Introduction
    1. 1.1 Related work
    2. 1.2 Contribution summary
    3. 1.3 Societal impact
    4. 1.4 Dataset and benchmark details
  2. 2 TGraph runtime ranking architecture
    1. 2.1 Problem specification
    2. 2.2 Data pre-processing
      1. 2.2.1 Graph pruning
      2. 2.2.2 Configuration deduplication
      3. 2.2.3 Lossless configuration compression
      4. 2.2.4 Changing the pad value in node_feat
      5. 2.2.5 Data normalization, embedding and batching
    3. 2.3 Architecture details
      1. 2.3.1 Channel-wise self-attention
      2. 2.3.2 Cross-Configuration Attention
      3. 2.3.3 Entire architecture
    4. 2.4 Training and inference procedures
      1. 2.4.1 Loss function
      2. 2.4.2 Training details
      3. 2.4.3 Data splits
    5. 2.5 Benchmark results
      1. 2.5.1 Evaluation splits
      2. 2.5.2 Evaluation metrics
      3. 2.5.3 Details of the inference mode
      4. 2.5.4 Experimental results
  3. 3 Conclusion
  4. 4 Limitations
  5. A Appendix / supplemental material
    1. A.1 Environmental impact case study

##  Appendix A Appendix / supplemental material

###  A.1 Environmental impact case study

According to {1} the total data center AI workload consumption in Northern
Virginia, VA (NV), the US was 2132 MW in 2023. Thus, the annual data center
energy consumption can be estimated as 18.6 million MWh. Considering the
carbon footprint of energy production in NV of 0.3 tonne CO2 per MWh as per
{2} the total annual CO2 emissions of NV data centers can be assessed as 5.58
mln tonnes CO2. From the authors of XTAT [17] we take 5% as a reference number
for the runtime speed-up across a diverse dataset of 150 neural architectures.
Speeding up AI workloads by 5% with the more efficient execution would reduce
CO2 emissions by 275’000 tonnes CO2 yearly in NV alone. This is equivalent to
the annual emissions of 36’000 households (approximately 50% of all NV
households). Even though it is yet to be determined how to estimate the real
acceleration of computation based on the values of Kendall’s $\tau$, we expect
the effect to be similar or superior to XTAT [17].

{1} Angus Loten. Rising Data Center Costs Linked to AI Demands, 2023.
(www.wsj.com)

{2} Power sector carbon intensity in the United States in 2022, by state,
2022. (www.statista.com)


# Deep Reinforcement Learning for Dynamic Spectrum Sharing of LTE and NR

Ursula Challita and David Sandberg
Ericsson Research, Stockholm, Sweden
Email: {ursula.challita and<EMAIL_ADDRESS>
###### Abstract

In this paper, a proactive dynamic spectrum sharing scheme between 4G and 5G
systems is proposed. In particular, a controller decides on the resource split
between NR and LTE every subframe while accounting for future network states
such as high interference subframes and multimedia broadcast single frequency
network (MBSFN) subframes. To solve this problem, a deep reinforcement
learning (RL) algorithm based on Monte Carlo Tree Search (MCTS) is proposed.
The introduced deep RL architecture is trained offline whereby the controller
predicts a sequence of future states of the wireless access network by
simulating hypothetical bandwidth splits over time starting from the current
network state. The action sequence resulting in the best reward is then
assigned. This is realized by predicting the quantities most directly relevant
to planning, i.e., the reward, the action probabilities, and the value for
each network state. Simulation results show that the proposed scheme is able
to take actions while accounting for future states instead of being greedy in
each subframe. The results also show that the proposed framework improves
system-level performance.

##  I Introduction

Dynamic spectrum sharing (DSS) has emerged as an effective solution for a
smooth transition from 4G to 5G by introducing 5G systems in existing 4G bands
without hard/static refarming spectrum [1]. Using DSS, 4G LTE [2] and 5G NR
[3] can operate in the same frequency band where a controller distributes the
available spectrum resources dynamically over time between the two radio
access technologies (RATs). For instance, in LTE-NR downlink (DL) sharing, LTE
scheduler loans resources during a certain time to NR and NR avoids symbols
used in LTE for cell specific signals. Moreover, DSS helps ease the transition
from non-standalone 5G networks to standalone 5G. That said, it is important
to investigate an effective scheme for the bandwidth (BW) split between LTE
and NR to reap the benefits of DSS.

While some literature has recently studied the problem of spectrum sharing
between LTE and WiFi (i.e., LTE-unlicensed) [4], NR and WiFi (i.e., NR-
unlicensed) [5], aerial and ground networks [6], and radars and communication
systems [7], the performance analysis of 4G/5G DSS remains relatively scarce
[8]. For instance, an instant spectrum sharing technique at subframe time
scale has been proposed [8]. The proposed scheme takes into account several
information about the cell, such as the amount of data in the buffer, thus
splitting the BW between 4G and 5G in every transmission time internal (TTI).
Despite the promising results, this work considers a reactive spectrum sharing
approach that does not account for the future network states and thus
resulting in performance degradation. On the other hand, in a proactive
approach, rather than reactively splitting the BW based on incoming demands
and serving them when requested, the network takes into account future states
for 4G/5G spectrum sharing thus improving the overall system level
performance.

The main contribution of this paper is to introduce a novel model-based deep
reinforcement learning (RL) based algorithm for DSS between LTE and NR. The
main scope of the proposed scheme is planning in the time domain whereby the
controller distributes the communication resources dynamically over time and
frequency between LTE and NR at a subframe level while accounting for future
network states over a specific time horizon. To enable an efficient planning,
we propose a deep RL technique based on Monte Carlo Tree Search (MCTS) [9].
When a model of the environment is available, algorithms like AlphaZero [10]
have been used with great success. However, in the case of DSS, the LTE and NR
schedulers are part of the environment, and these are not easily modelled.
Inspired by the MuZero work [11], we use a learned model of the environment
for planning in the time domain. When applied iteratively, the proposed
solution predicts the quantities most directly relevant to planning, i.e., the
reward, the action probabilities, and the value for each state. This in turn
enables the controller to predict a sequence of future states of the wireless
network by simulating hypothetical communication resource assignments over
time starting from the current network state and evaluating a reward function
for each hypothetical communication resource assignment over the time window.
As such, the communication resources in the current subframe are assigned
based on the simulated hypothetical BW split action associated with maximized
reward over the time window. To our best knowledge, this is the first work
that exploits the framework of deep RL for DSS between 4G and 5G systems.
Simulation results show that the proposed approach improves quality of service
in terms of latency. Results also show that the proposed algorithm results in
gain in different scenarios by accounting for several features while planning
in the time domain, such as multimedia broadcast single frequency network
(MBSFN) subframes and diverse user service requirements.

The rest of this paper is organized as follows. Section II presents the system
model. Section III describes the proposed deep RL algorithm. In Section IV,
simulation results are analyzed. Finally, conclusions are drawn in Section V.

##  II System Model

Consider the downlink of a wireless cellular system composed of a co-located
cell operating over NR and LTE serving a set $\mathcal{J}$ of $J$ users. NR
and LTE are assumed to operate in the 3.5 GHz frequency band and apply FDD as
the duplexing method. We consider a 15 kHz NR numerology and that LTE and NR
subframes are aligned in time and frequency. Each RAT, $s$, serves a set of
$K_{s}\subseteq J$ of UEs. The total system bandwidth, $B$, is divided into a
set $\mathcal{C}$ of $C$ resource blocks (RBs). Each RAT, $s$, is allocated a
set $C_{s}\subseteq C$ of RBs, and each UE $j\in K_{s}$ is allocated a set
$C_{j,s}\subseteq C_{s}$ of $C_{j,s}$ RBs by its serving RAT $s$.

For an efficient spectrum sharing model of LTE and RAT, one must design a
mechanism for dividing the available bandwidth for data and control
transmission for each of the RATs. For the control region, we consider the
following:

  * •

LTE PDCCH is restricted to symbols #0 and #1 (if NR PDCCH is present).

  * •

NR has no signals/channels in symbols #0 and #1.

  * •

NR PDCCH is limited to symbol 2, assuming that the UE only supports type-A
scheduling (no mini-slots).

  * •

In LTE subframes where no NR PDCCH is transmitted in the overlapped NR slots,
LTE PDCCH could span 3 symbols.

For data transmission, a controller decides on the resource split, $C_{s}$,
between NR and LTE every subframe.

###  II-A Channel Model

We assume the 3GPP Urban Macro propagation model [12] with Rayleigh fading.
The path loss between UE $j$ at location $a$ and its serving BS $s$,
$\xi_{j,s,a}$, is given by Model1 [13], considering 3.5 GHz frequency band:

$\xi_{j,s,a}=20.4+37.6\times\textrm{log}_{10}(d),$ (1)

where d is the distance between the UE and the BS in meters. The signal-to-
noise ratio (SNR), $\Gamma_{j,s,c,a}$ of the UE-BS link between UE $j$ at
location $a$ served by RAT $s$ over RB $c$ will be:

$\Gamma_{j,s,c,a}=\frac{P_{j,s,c,a}h_{j,s,c,a}}{B_{c}N_{0}},$ (2)

where $P_{j,s,c,a}=\overline{P}_{j,s,a}/C{j,s}$ is the transmit power of
BS/RAT $s$ to UE $j$ at location $a$ over RB $c$ and $\overline{P}_{j,s,a}$ is
the total transmit power of BS/RAT $s$ to UE $j$ location $a$. Here, the total
transmit power of RAT $s$ is assumed to be distributed uniformly among all of
its associated RBs. $h_{j,s,c,a}=g_{j,s,c,a}10^{-\xi_{j,s,a}/10}$ is the
channel gain between UE $j$ and BS/RAT $s$ on RB $c$ at location $a$ where
$g_{j,s,c,a}$ is the Rayleigh fading complex channel coefficient. $N_{0}$ is
the noise power spectral density and $B_{c}$ is the bandwidth of an RB $c$.
Therefore, the achievable data rate of UE $j$ at location $a$ associated with
RAT $s$ can be defined as:

$R_{j,s,a}=\sum_{c=1}^{C_{j,s}}B_{c}\textrm{log}_{2}(1+\Gamma_{j,s,c,a}),$ (3)

###  II-B Traffic Model

We assume a periodic traffic arrival rate per UE $j$ with a fixed periodicity
$\lambda_{j}$ and a fixed packet size $\beta_{j}$. Time domain scheduling is
typically governed by a scheduling weight whereby a high weight corresponds to
a high priority for scheduling that particular UE. We adopt a similar
mechanism for measuring the quality of bandwidth splits between LTE and NR
where a UE not fulfilling its QoS is associated with a high weight. The weight
for user $j$ in subframe $p$ can be calculated as:

$w_{p,j}(t)=\begin{cases}\alpha_{j}t&t<\delta_{j},\\\
\alpha_{j}t+\eta_{j}&t\geq\delta_{j}.\end{cases}\vspace{-0.1cm}$ (4)

where $t$ is the time the oldest packet has been waiting in the buffer,
$\delta_{j}$ and $\eta_{j}$ correspond to the step delay and step weight of
the delay weight function of user $j$, respectively and $\alpha_{j}$ is a
small positive factor that makes the weight non-zero when there is data in the
buffer. Note that a UE with zero weight will not be scheduled. Here, the step
delay corresponds to the maximum tolerable delay in order to maintain QoS. If
a packet remains in the buffer for a time period larger than $\delta_{j}$, the
weight for user $j$ increases by $\eta_{j}$.

Given this system model, next, we develop an effective spectrum sharing scheme
that can allocate the appropriate bandwidth to each RAT, at a subframe time
scale, while accounting for future network states.

##  III Deep Reinforcement Learning for Dynamic Spectrum Sharing

In this section, we propose a proactive approach for DSS enabling LTE and NR
to operate on the same BW simultaneously. In this regard, we propose a deep RL
framework that enables the controller to learn the BW split between LTE and NR
during subframe $t$ while accounting for future network states over a time
window $T$. To realize that, first, we propose the adopted RL algorithm for
training the controller to learn the optimal policy for BW split. Then, we
introduce the RL architecture and components for the DSS problem.

###  III-A Deep RL Algorithm

To enable a proactive BW split between LTE and NR, we adopt in this paper the
MuZero algorithm [11]. One of the main challenges of the proposed solution
technique is that it requires a model for the individual schedulers for LTE
and NR, which is hard to devise. Instead, we propose in this paper to learn
the scheduling dynamics via a model-based reinforcement learning algorithm
that aims to address this issue by simultaneously learning a model of the
environment’s dynamics and planning with respect to the learned model [11].
This approach is more data efficient compared to model-free methods where
current state-of-the-art algorithms may require millions of samples before any
near-optimal policy is learned.

During the training phase of the proposed algorithm, the prediction comprises
performing a MCTS over the action space and over the time window $T$ to find
the sequence of actions that maximizes the reward function. MCTS iteratively
explores the action space, gradually biasing the exploration towards regions
of states and actions where an optimal policy might exist. To enable our model
to learn the best explored sequence of actions for each network state, we
define three neural networks - the representation function ($h$), dynamics
function ($g$), and prediction function ($f$). The motivation for
incorporating each of these neural networks in the proposed algorithm is
described as follows:

  * •

_A representation function ( $h$)_ encodes the observation in subframe $p$
into an initial hidden state ($s_{0}$).

  * •

_A dynamics function ( $g$)_ computes a new hidden state ($s_{i+1}$) and
reward ($r_{i+1}$) given the current state ($s_{i}$) and an action
($a_{i+1}$).

  * •

_A prediction function ( $f$)_ outputs a policy ($p_{i}$) and a value
($v_{i}$) from a hidden state ($s_{i}$).

During the training phase, the model predicts the quantities most directly
relevant to planning, i.e., the reward, the action probabilities and the value
for each state. The proposed training algorithm is summarized in Algorithm 1
and the main steps are given as follows:

  * •

_Step 1_ : The model receives the observation of the network state as an input
and transforms it into a hidden state ($s_{0}$).

  * •

_Step 2_ : The prediction function ($f$), is then used to predict the value
$v_{i}$ and policy vector $p_{i}$ for the current hidden state $s_{i}$.

  * •

_Step 3_ : The hidden state is then updated iteratively to a next hidden state
$s_{i+1}$ by a recurrent process consisting of $N_{\textrm{unroll}}$ steps,
using the dynamics function ($g$), with an input representing the previous
hidden state $s_{i}$ and a hypothetical next action $a_{i+1}$, i.e., a
communications resource assignment selected from the action space comprising
allowable bandwidth splits between LTE and NR.

  * •

_Step 4_ : Having defined a policy target, reward and value, the
representation function ($h$), dynamics function ($g$), and prediction
function ($f$) are trained jointly, end-to-end by backpropagation-through-time
(BPTT).

Meanwhile, the testing algorithm refers to the actual execution of the
algorithm after which the weights of ($h$), ($g$), and ($f$) have been
optimized and is implemented for execution during run time. Given that DSS is
performed on a 1 ms basis, it is too demanding to run MCTS online. As such, we
use the representation ($h$) and prediction ($f$) functions only during test
time. The main steps performed by the controller at test time are summarized
in Algorithm 2.

Algorithm 1 Training phase

Input: Representation ($h$), dynamics ($g$) and prediction ($f$) functions.

for $i$ = 0 … $N_{\textrm{iter}}-1$ do

Data Generation

Step 1: Sample $N_{\textrm{episode}}$ environments ($\mathscr{E}$) with random
parameters.

for ($env$ $\in$ $\mathscr{E}$) do

for $p$ = 0 … $N_{\textrm{timestep}}-1$ do

Step 2: Encode the observation $o_{p}$ into an initial hidden state, $s_{0}$.

Step 3: Run $N_{\textrm{mcts}}$ MCTS simulations from this state using ($g$)
and ($f$).

Step 4: Sample an action to take in the environment.

Step 5: Store the policy ($\pi$) and reward ($u$) in the replay buffer
($\mathscr{R}$).

end for

end for

Neural Network Training

for $p$ = 0 … $N_{\textrm{step}}-1$ do

Step 6: Sample a batch of sequences from the replay buffer $\mathscr{R}$.

Step 7: Compute the total discounted reward ($z$) over each sequence.

Step 8: Take a training step using BPTT to make $p$ $\approx$ $\pi$, $v$
$\approx$ $z$, $r$ $\approx$ $u$.

end for

end for

Algorithm 2 Execution phase

Input: Representation ($h$) and prediction ($f$) functions.

for $n$ = 0 … $N_{\textrm{timestep}}-1$ do

Step 1: Encode the observation into an initial hidden state, $s_{0}$.

Step 2: Calculate the action probabilities using ($f$) and select the best
action.

Step 3: Find the BW split to use and send that to the schedulers.

end for

###  III-B Deep RL Components

In this subsection, we define the RL framework components, namely the
observations, actions, and rewards.

  * •

Action space: BW split between LTE and NR for DL transmission for subframe
$p$, denoted as $a_{p}=\\{a_{1},a_{2},...a_{N}\\}$ where $N$ is the size of
the action space. Here, an action corresponds to a horizontal line splitting
the BW on one side to LTE and the other side to NR. The possible BW splits are
chosen by grouping a set of multiple RBs thereby resulting in a quantized
action set. This would in turn reduce the action space size and is valid due
to the fact that the gain between bandwidth splits from consecutive RBs is
negligible.

  * •

Observation: the observation for subframe $p$, denoted as $o_{p}$, is divided
into two parts, where the first part, ($o_{p,1}$), consists of components with
size $(J\textrm{x}1)$ whereas the second part, ($o_{p,2}$), consists of
components with size $(J\textrm{x}T)$, where $T$ is the time window consisting
of a set of future subframes. The different observations components are
summarized as follows:

    * –

NR support: a vector with $J$x1 elements that indicates if a user $j$ is NR
user or not.

    * –

Buffer state: a vector with $J$x1 elements containing the number of bits in
the buffer of user $j$.

    * –

MBSFN subframe: a matrix with $J$x$T$ elements that indicates for each
subframe $p$, $p\in T$, if a UE is configured with MBSFN or not. By
configuring LTE UEs with MBSFN subframes, some broadcast signalling can be
avoided at the cost of decreased scheduling flexibility.

    * –

Predicted number of bits per PRB and TTI for each UE $j$: a matrix with
$J$x$T$ elements, where each element contains the estimated number of the
average bits that can be transmitted for user $j$ in subframe $p$, taking into
account the estimated channel quality of user $j$ during subframe $p$, $p\in
T$.

    * –

Predicted packet arrivals: a matrix with $J$x$T$ elements indicating the
number of bits that will arrive in the buffer for each user $j$ over a set of
future subframes $T$.

  * •

Reward function: the reward function is modelled as a summation of the
exponential of the most delayed packet per user and can be expressed as:

$r_{p}=e^{-\sum_{j=1}^{J}w_{p,j}},$ (5)

where $w_{p,j}$ is the delay weight function of user $j$ in subframe $p$, as
described in (4). The intuition behind this reward function is that high total
weight is penalized with a low reward in subframe $p$. Meanwhile, if the
controller manages to keep the user buffers empty, the reward per subframe
will be one. If a highly prioritized UE is queued for several subframes, its
weight will increase and thus the reward will approach zero.

Figure 1: A schematic illustration of the proposed setup summarizing the
connection between the controller, network state, and LTE and NR schedulers.

Figure 1 summarizes the relationship between the network state, controller,
and LTE and NR schedulers. At each subframe, the LTE scheduler, NR scheduler,
and controller receive the network state information. This information is then
used by the controller to generate observations and thus take an action for
the BW split between LTE and NR. This action is then conveyed to the LTE and
NR schedulers. Given the network state information and the corresponding BW
split, each of the schedulers allocates their respective users to the
corresponding BW portion for the current subframe. Finally, the weights for
the users are fed to the controller and used as an input for the calculation
of the reward. Next, we provide simulation results and analysis for the
proposed RL framework.

Table I: Simulation parameters for the radio environment. Parameter | Value
---|---
Frequency | 3.5 GHz
Bandwidth | 25 PRBs (5 MHz)
Traffic Model | Periodic
UE speed | 3 m/s
Transmit power | 0.8W/PRB
Noise power ($N_{0}$) | 112.5 dBm/PRB
Antenna config | 1 Tx, 2 Rx

##  IV Simulation Results and Analysis

In this section, we provide simulation results and analysis for the
performance of the proposed algorithm under four different scenarios where
planning in the time domain for dynamic spectrum sharing is relevant. Tables I
and II provide a summary of the main simulation parameters.

Figure 2: Neural network architectures for a) the representation function, b)
the dynamics function and c) the prediction function.

The structure of the representation, dynamics, and prediction neural networks
is depicted in Figure 2. All dense layers except for the output layer use 64
activations with ReLU activation. The representation outputs ($s$) use 10
activations with $tanh$ activation. The reward ($r$) and value ($v$) outputs
are scalar with linear activation, and the policy ($p$) has the same number of
activations as the number of actions with $softmax$ activation.

Table II: Simulation parameters for the RL framework. Parameter | Value
---|---
Number of MCTS simulations ($N_{\textrm{mcts}}$) | 64
Episode length ($N_{\textrm{timestep}}$) | 16 subframes
Discount factor ($\gamma$) | 0.99
Window size (T) | 10 subframes
Batch size | 32 examples
Number of unroll steps ($N_{\textrm{unroll}}$) | 3
Number of TD steps ($N_{\textrm{td}}$) | 16
Optimizer | Adam
Learning rate | $1*10^{-4}$
Number of episodes per iteration ($N_{\textrm{episode}}$) | 100
Representation size | 10
Algorithm 3 Baseline Algorithm

Input: Observation, $o_{t}$.

Output: Action, $a_{t}$.

Step 1: Calculate the weight of each user according to Eq 4.

Step 2: Sort the users in order of decreasing weight.

Step 3: Schedule users from the list until spectrum is full.

Step 4: Check how many PRBs are needed for NR and LTE users.

Step 5: Select the action, $a_{t}$, that splits the BW proportionally between
the RATs.

Next, we provide a detailed description for the simulation results and
analysis of each of the four studied scenarios. Note that in all of the
scenarios, the episode length is 16 and thus the evaluation score for a
perfectly solved scenario is also 16. Moreover, we assume that LTE users (if
any) are scheduled on the lower part of the spectrum band and NR users (if
any) are scheduled on the high part of the band. As for the baseline, we split
the available spectrum proportionally to the number of required RBs between
LTE and NR users, as summarized in Algorithm 3. We also compare the
performance of the proposed algorithm to equal BW split and alternating BW
between LTE and NR. The user weight is calculated using Eq. 4, with
$\eta_{j}=5$ and $\alpha_{j}=10^{-5}$ for all users. The step delay,
$\delta_{j}$, is set appropriately for the different users in the different
scenarios as specified below.

###  IV-A Scenario 1: MBSFN subframes

LTE requires CRSes to enable demodulation of data. Therefore, if only NR UEs
are scheduled, the CRSes are not needed and are hence an overhead. If there is
a lot of NR traffic to be scheduled, LTE can be configured with so called
MBSFN subframes. In these subframes, no CRSes are transmitted and it is
therefore not possible to schedule LTE users but this can result in improved
efficiency for NR users. This scenario aims to investigate if the controller
can learn to account for MBSFN subframes during planning thus enabling time
critical LTE traffic to be served before MBSFN subframes.

####  IV-A1 Scenario description

We consider two users, one NR user and one LTE user, both having a traffic
arrival periodicity of 4 ms and a step delay $\delta_{0}$=3ms. The packet size
is 45000 bits and 15000 bits for the NR and LTE users, respectively. The
system is configured with a repeating MBSFN pattern with a periodicity of 4
subframes, where the first two subframes are non-MBSFN (i.e., both LTE and NR
UEs can be scheduled) and the last two subframes in the pattern are MBSFN
subframes (i.e., only NR UEs can be scheduled).

####  IV-A2 Optimal bandwidth split

To solve this scenario optimally, both packets must be served within 3 ms. As
such, the LTE user should be served in the non-MBSFN subframes to make
resources available for the NR user later in the cycle. Therefore, the optimal
strategy is to start scheduling LTE such that its buffer is emptied before the
MBSFN subframes.

####  IV-A3 Results and analysis

From Figure 3, we can see that the proposed algorithm converges to the optimal
strategy in 12 iterations. Also, note that the performance of the proposed
scheme exceeds that of equal bandwidth split between LTE and NR and the case
where MBSFN subframes are allocated to the NR user and non-MBSFN subframes are
allocated to the LTE user. With this MBSFN configuration the amount of
overhead due to e.g. LTE CRSes can be minimized which results in improved
efficiency on network level. The controller can learn to account for the MBSFN
subframes by scheduling in such a way that maximizes the quality of service
despite the reduced scheduling flexibility due to the MBSFN subframes.

Figure 3: Evaluation score as a function of number of iterations for scenario
1 with MBSFN subframes.

###  IV-B Scenario 2: Periodic high interference

In this scenario, we investigate the controller’s ability to learn to account
for future high interference on one of the users during planning. Periodic
high interference can, for instance, occur in case a user is at the cell edge
and is interfered by another base station or in case of unsynchronized time
division duplexing scenarios.

####  IV-B1 Scenario description

We consider two users, one NR user and one LTE user, both having a traffic
arrival periodicity of 2 ms. We assume a larger packet size for NR user
compared to that of LTE so that we can observe the gain of NR benefiting from
the 2 extra symbols of LTE PDCCH if it is allocated the full bandwidth. Users
have a small weight value when the delay is less than 2 ms but then it
increases abruptly to 2 after 2 ms (i.e., $\delta=2ms$). Moreover, a periodic
high interference is observed on LTE user every 3 subframes. Here, the
periodic interference term is added artificially for analysis purposes.

####  IV-B2 Optimal bandwidth split

The optimal strategy for this scenario is to allocate the full bandwidth to NR
during subframes with high interference on the LTE user.

####  IV-B3 Results and analysis

From Figure 4, we can see that the proposed algorithm converges to the optimal
strategy in 18 and 28 iterations for the case of 2 and 3 action space,
respectively. The proposed approach outperforms the baseline algorithm, equal
bandwidth split, and alternating bandwidth split where the controller learns
to allocate the full bandwidth to NR during subframes with high interference
for the LTE user as opposed to taking actions based on buffer status only.
This allows the controller to split the bandwidth between LTE and NR such that
the impact of the interference level from neighboring cells is reduced thus
resulting in an improved system level performance.

Figure 4: Evaluation score as a function of number of iterations for scenario
2 with periodic high interference.

###  IV-C Scenario 3: Mixed services

In this scenario, we investigate the controller’s ability to handle users with
different delay requirements.

####  IV-C1 Scenario description

We consider two users, one high priority NR user ($\delta_{0}=5ms$) with 90000
bits, and one low priority LTE user ($\delta_{1}=10ms$) with 90000 bits. Data
arrives in subframe 1 for both users.

####  IV-C2 Optimal bandwidth split

The optimal strategy for this scenario is to postpone the scheduling of the
low priority LTE user in order to allow the high priority NR user to be
scheduled. When the buffer of the high priority users is emptied, the
controller can schedule the LTE user.

####  IV-C3 Results and analysis

From Figure 5, we can see that the proposed approach converges to the optimal
policy within 5 iterations. The controller learns to prioritize the NR user
with a tight delay requirement over the LTE user thus outperforming the
baseline algorithm as well as the equal BW split.

Figure 5: Evaluation score as a function of number of iterations for scenario
3 with mixed services.

###  IV-D Scenario 4: Time multiplexing

In this scenario, we investigate the controller’s ability to learn to do time
multiplexing (as opposed to frequency multiplexing) between LTE and NR. Time
multiplexing can result in two extra symbols for NR when no LTE is scheduled
due to the fact that no LTE PDCCH needs to be transmitted. This in turn
results in an increased efficiency when the RATs are scheduled in a time
multiplexed fashion.

####  IV-D1 Scenario description

We consider two users, one NR user and one LTE user, both having a traffic
arrival periodicity of 2 ms. The packet size for the NR user is larger (14000
bits) compared to that of the LTE user (10000 bits). Users have a small weight
when delay is less than 2 ms but then increases abruptly to 5 after 2 msec
(i.e. $\delta=2ms$).

####  IV-D2 Optimal bandwidth split

The optimal strategy for this scenario is to perform time multiplexing whereby
the full bandwidth is allocated to a particular RAT every other subframe. As
such, NR could benefit from the 2 extra symbols of LTE PDCCH when it is given
the full bandwidth. This results in a larger transport block size and thus the
large NR packet size can be served within one subframe.

####  IV-D3 Results and analysis

From Figure 6, we can see that the proposed approach converges to the optimal
action strategy within 14 and 15 iterations for the case of 3 and 4 actions,
respectively. The proposed approach outperforms the baseline algorithm, equal
BW split, and alternating BW split where the network learns to perform time
multiplexing between LTE and NR resulting in an increased spectrum efficiency.
For the studied scenario, when NR is scheduled alone, i.e. without overhead
from LTE PDCCH, the maximum transport block size is 14112 bits. On the other
hand, when LTE is scheduled with NR, there is an extra overhead for LTE PDCCH
and thus the maximum transport block size decreases to 12576 bits.
Consequently, the NR packet can be scheduled in one subframe given that NR is
scheduled alone during that subframe.

Figure 6: Evaluation score as a function of number of iterations for scenario
4 considering a time multiplexing scenario.

##  V Conclusion

In this paper, we have proposed a novel AI planning framework for dynamic
spectrum sharing of LTE and NR. Results have shown that the controller can
split the bandwidth between LTE and NR in an intelligent way while accounting
for future network states, such as MBSFN subframes and high interference
level, thus resulting in an improved system level performance. This gain comes
from the fact that the proposed algorithm uses knowledge (or beliefs) about
future network states to make decisions that perform well on a longer
timescale rather than being greedy in the current subframe. As part of future
work, we aim to further investigate if the suggested algorithm can learn to
account for uncertainties in the observations.

## References

  * [1] Ericsson, “Sharing for the best performance - stay ahead of the game with ericsson spectrum sharing,” _Ericsson white paper_ , 2019.
  * [2] E. Dahlman, S. Parkvall, and J. Skold, _4G: LTE/LTE-Advanced for Mobile Broadband_ , 1st ed. USA: Academic Press, Inc., 2011.
  * [3] E. Dahlman, S. Parkvall, and J. Skold, _5G NR: The Next Generation Wireless Access Technology_ , 1st ed. USA: Academic Press, Inc., 2018.
  * [4] U. Challita, L. Dong, and W. Saad, “Proactive resource management for LTE in unlicensed spectrum: A deep learning perspective,” _IEEE transactions on wireless communications_ , vol. 17, no. 7, pp. 4674–4689, July 2018.
  * [5] 3GPP TR 38.889, “Study on NR-based access to unlicensed spectrum.”
  * [6] U. Challita, W. Saad, and C. Bettstetter, “Interference management for cellular-connected UAVs: A deep reinforcement learning approach,” _IEEE Transactions on Wireless Communications_ , vol. 18, no. 4, pp. 2125–2140, March 2019.
  * [7] A. Khawar, A. Abdelhadi, and C. Clancy, _Spectrum Sharing Between Radars and Communication Systems_. Springer, 2018\.
  * [8] S. Kinney, “Dynamic spectrum sharing vs. static spectrum sharing,” _RCR wireless_ , March 2020.
  * [9] C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton, “A survey of monte carlo tree search methods,” _IEEE Transactions on Computational Intelligence and AI in Games_ , vol. 4, no. 1, pp. 1–43, 2012.
  * [10] D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, T. Lillicrap, K. Simonyan, and D. Hassabis, “Mastering chess and shogi by self-play with a general reinforcement learning algorithm,” 2017.
  * [11] J. Schrittwieser, I. Antonoglou, T. Hubert, K. Simonyan, L. Sifre, S. Schmitt, A. Guez, E. Lockhart, D. Hassabis, T. Graepel, T. Lillicrap, and D. Silver, “Mastering atari, go, chess and shogi by planning with a learned model,” _arXiv:1911.08265_ , Nov. 2019.
  * [12] 3GPP, “Study on channel model for frequencies from 0.5 GHz to 100 GHz,” _3GPP TR 38.901, V15.0.0_ , June 2018.
  * [13] 3GPP, “Evolved Universal Terrestrial Radio Access (E-UTRA); Further advancements for E-UTRA physical layer aspects,” 3rd Generation Partnership Project (3GPP), Technical Report (TR) 36.814, 03 2017, version 9.2.0.