# ecoBLE: A Low-Computation Energy Consumption Prediction Framework for
Bluetooth Low Energy

Luisa Schuhmacher  0000-0003-3293-7933 Sofie Pollin  0000-0002-1470-2076 and
Hazem Sallouha

0000-0002-1288-1023 Department of Electrical Engineering (ESAT) - WaveCoRE, KU
Leuven  {luisa.schuhmacher, sofie.pollin<EMAIL_ADDRESS>
###### Abstract

Bluetooth Low Energy (BLE) is a de-facto technology for Internet of Things
(IoT) applications, promising very low energy consumption. However, this low
energy consumption accounts only for the radio part, and it overlooks the
energy consumption of other hardware and software components. Monitoring and
predicting the energy consumption of IoT nodes after deployment can
substantially aid in ensuring low energy consumption, calculating the
remaining battery lifetime, predicting needed energy for energy-harvesting
nodes, and detecting anomalies. In this paper, we introduce a Long Short-Term
Memory Projection (LSTMP)-based BLE energy consumption prediction framework
together with a dataset for a healthcare application scenario where BLE is
widely adopted. Unlike radio-focused theoretical energy models, our framework
provides a comprehensive energy consumption prediction, considering all
components of the IoT node, including the radio, sensor as well as
microcontroller unit (MCU). Our measurement-based results show that the
proposed framework predicts the energy consumption of different BLE nodes with
a Mean Absolute Percentage Error (MAPE) of up to 12%, giving comparable
accuracy to state-of-the-art energy consumption prediction with a five times
smaller prediction model size.

BLE

    Bluetooth Low Energy
IoT

    Internet of Things
ANNs

    Artificial Neural Networks
LSTM

    Long Short-Term Memory
LSTMP

    Long Short-Term Memory Projection
MAPE

    Mean Absolute Percentage Error
RNNs

    Recurrent Neural Networks
GRU

    Gated Recurrent Unit
SVR

    Support Vector Regression

##  1 Introduction

The increasing trend in the number of wirelessly connected devices triggers
considerable environmental and economic concerns, citing energy efficiency
[18] and sustainability of wireless networks [28, 1]. In fact, the ICT sector,
which is considerably driven by mobile networks and _ Internet of Things
(IoT)_, contributes to around 10% of the total energy consumption worldwide,
translating into 3% of worldwide carbon footprint [1]. With the rapid increase
of IoT networks and the belief that digitalization and wireless connectivity
will play a key role in decreasing carbon emissions, and therefore tackling
climate change [29], it is necessary to ensure low energy consumption of the
IoT network itself [18].

_Bluetooth Low Energy (BLE)_ is emerging as one of the main drivers of IoT
technologies, promising low-energy and low-cost solutions for a great variety
of short-range applications, including wearable devices, healthcare, and home
automation to name a few [15, 4]. However, despite the fact that the BLE
protocol is inherently designed to be energy efficient, this efficiency is
mostly focused on the radio frequency (RF) part of the IoT node and is not
necessarily guaranteed on the network level as it highly depends on the scale
of network deployment and traffic-demand, as well as the type of hardware used
[25, 27, 11].

Energy consumption monitoring and prediction are part of the main research
areas aiming at reducing wireless networks’ carbon footprint, which also
include areas focusing on energy-harvesting and battery-life monitoring.
Energy consumption prediction models can be broadly categorized into models
based on statistical approaches and models based on _ Artificial Neural
Networks (ANNs)_ [6, 26, 12]. Recent reports showed that approaches based on
ANNs outperform conventional statistical models in time-series problems [19,
17]. In particular, the _ Long Short-Term Memory (LSTM)_ [7] architecture is
leading in terms of accuracy when dealing with prediction tasks on time-series
datasets [12]. Nonetheless, a critical shortcoming of the LSTM architecture is
its complexity as it incorporates multiple matrix operations, resulting in
often large sequential model size. This makes it unsuitable for the current
trend in IoT, where machine learning models are implemented on
computationally-limited edge devices [8]. To address the complexity of the
conventional LSTM-based models, a modification to the LSTM architecture called
_ Long Short-Term Memory Projection (LSTMP)_ was introduced in [16]. The
authors showed that the LSTMP architecture could reduce the overall size of
the conventional LSTM without suffering from degraded accuracy.

In this paper, we aim to leverage the computationally- and memory-efficient
LSTMP architecture, advocating for Green AI option [20] by considering the
model size in performance evaluation. In particular, the contribution of this
paper is twofold. First, we conducted extensive measurements to collect an
energy consumption dataset from BLE nodes in a scenario resembling three
healthcare BLE sensors and a central BLE device acting as a gateway. The
dataset is made publicly available111https://doi.org/10.48804/XVOUAH. To the
best of our knowledge, such a dataset does not yet exist publicly. Secondly,
we introduce a novel, low-computation LSTMP-based energy consumption
prediction framework trained on the said dataset. The proposed framework is
five times smaller than its state-of-the-art counterpart [2] while staying on
par in terms of prediction accuracy, making it more suitable for energy-,
memory- and computation-restrained IoT edge devices. Our proposed framework is
made open-source222https://gitlab.kuleuven.be/networked-systems/public/energy-
consumption-prediction-for-ble, allowing it to act as a baseline for future
research.

The rest of this paper is organized as follows: Section 2 reviews related work
in the field of energy consumption prediction and energy consumption models
for BLE and beyond. We introduce our own energy consumption prediction
framework and our training procedure in Section 3. In Section 4, we state our
experimental setup for collecting the dataset used for training. Section 5
illustrates the results we got from our framework. We conclude our work in
Section 6.

##  2 Related Work

Several works in the literature have addressed energy prediction using
machine-learning-based models; however, most targeted households [6]. A survey
on general energy consumption models has been given in [6], where several
machine learning algorithms and their respective applications are summarized.
In methods based on ANNs, LSTM models often take the lead for energy
consumption prediction. Alonso et al. [2] proposed an LSTM-based framework and
tested it on residential households’ energy consumption data, outperforming
state-of-the-art models for this task. Their model is comparably complex [2]
but showed its capability to generalize to data from unseen households while
testing.

Regarding IoT networks, a few works have studied the energy prediction
problem. Jeddou et al. [10] studied the energy consumption prediction for the
MQTT and COAP protocols. They use a simple linear regression model and achieve
sufficient results. However, these results are only valid for data that follow
a linear trend. Theoretical energy consumption models like the concise energy
model for the BLE protocol developed by [11] can be used for energy
consumption prediction. However, to use this model, several fine-grained
measurements of the current drained as well as the duration of multiple parts
of a BLE application needs to be taken, which is specific to the used hardware
and the software used to program the node, making it therefore tedious to
adopt. Furthermore, it only comprises the radio, leaving software- and other
hardware-components out.

In summary, while several works in the literature have focused on the field of
energy consumption forecasting, the majority of them targeted households [6],
and only a few research reports have focused on energy consumption prediction
for IoT. To the best of our knowledge, particularly, the comprehensive energy
consumption prediction for BLE is still an open research question.

##  3 Proposed Framework and Training Procedure

In this section, we introduce our LSTMP-based prediction framework and detail
the training procedure we followed.

###  3.1 Proposed Framework

Our framework consists of an ANN with two layers of LSTMP, aiming to predict
the power consumption of BLE nodes. The architecture of our LSTMP-based ANN is
visualized in Figure 1 for input from time-steps $t$ and $t+1$.

Figure 1: Visualization of our two-layer LSTMP architecture. Subscript $t$
denotes the time-step, while superscript $(l)$ indicates the layer.
$h^{(l)}_{t}/h^{(l)}_{t+1}$ are depicted twice to indicate that they are fed
as input into the LSTMP framework at the next time-step and simultaneously act
as the final output of the current time-step. Note that the learnable
parameters are different for the two layers (vertical direction) but the same
for each time-step (horizontal direction).

The only difference between a conventional LSTM layer and an LSTMP layer is a
projection matrix $W_{hr}$ which reduces the size of the hidden state vector,
$h_{t}^{l}$ in Figure 1, from the hidden size to a predefined projection size.
We set the projection size to be the prediction length, directly decoding the
features gathered by the gates to the predicted energy consumption. Note that
like this, we erase the necessity for an additional linear layer after the
LSTMP to obtain the desired output. At the same time, the sizes of all the
matrices used to compute the hidden state become less compared to the
conventional LSTM architecture, leading to a decreased overall architecture
size.

In the next subsection, we will elaborate on the training procedure. We use
the symbols as described in Table 1.

Table 1: Symbols used throughout this paper. Symbol | Meaning in general |  Meaning in Fig. 1
---|---|---
$T$ | Length of sequence | $t\in\\{0,...T-1\\}$
| input vectors given to |
| the framework |
$H_{in}$ | Size of one input vector |  Size of $x_{t}$
| given to the framework |
$H_{cell}$ | Hidden size for cell |  Size of $c^{(l)}_{t},f^{(l)}_{t},$
| state and hidden state, | $i^{(l)}_{t},g^{(l)}_{t},o^{(l)}_{t}$
| output size of cell state |
$H_{out}$ | Output size of hidden |  Size of $h^{(l)}_{t}$
| state and actual output |

###  3.2 Training Procedure

In order to select the best performing LSTMP architecture, we trained multiple
two-layer LSTMP networks with different hidden sizes $H_{cell}$ and different
output sizes $H_{out}$. Our objective is to realize a model that can be
implemented directly on a sensor with limited computational power instead of
the cloud. An example case is predicting the energy an energy-harvesting node
will need in a given amount of time-steps in the future. As a result, we aim
at minimizing the size and the computation requirements of the proposed
framework. Therefore, we search through several values of $H_{cell}$ to
determine a small but accurate framework.

We further vary $H_{out}$ to let the framework predict the energy consumption
for different amounts of future time-steps. We want to investigate how far we
can let the framework predict without substantially degrading the target
accuracy. Table 2 shows the combinations of values for $H_{cell}$ and
$H_{out}$ used during training.

Table 2: Hidden sizes $H_{cell}$ and output sizes $H_{out}$ used in training. $H_{cell}$ | $H_{out}$
---|---
2 | 1
4 | 1
8 | 1
16 | 1
32 | 1, 2, 3, 10, 15, 50
64 | 1, 2, 3, 10, 15, 50
650 | 1

In order to evaluate how many time-steps of 1 ms in the future our framework
can predict, we started with the simplest task of predicting one step in the
future and evaluated the performance for the different values of $H_{cell}$.
Subsequently, we fixed $H_{cell}\in\\{32,64\\}$, as they yielded the best
prediction accuracy (cf. Section 5), without further improvement for bigger
$H_{cell}$, and subsequently, trained the models with different $H_{out}$.

##  4 Experimental Setup and Dataset Collection

This section presents the experimental setup used for the dataset collection
as well as the processing of the dataset.

###  4.1 Raw Dataset

To train and test our framework, we set up an experiment to build a dataset.
The experiment was designed to imitate a healthcare application where a
patient is equipped with three sensors, each of which has a BLE radio node
attached to provide wireless connectivity, sending information via BLE to a
central device. The first sensor, denoted by HR, reads the pulse of the
patient at 1000 samples per second (sps), and the attached BLE node then
calculates the heart rate and sends it to a central node every five seconds.
The second sensor, denoted by BT, reads the patient’s body temperature and
sends it via BLE to the central node every five minutes. The last sensor,
denoted by OS, reads the oxygen saturation in the patient’s blood, and the
corresponding BLE node sends it to the central node every second. Since the
actual data read by the sensor has no influence on the proposed framework, we
used dummy data generated by the boards’ MCU for HR and OS, while air
temperature sensor readings were used for BT in our dataset collection.

Figure 2: Experimental setup. Each BLE board is connected to and powered by a
Power Profiler, which sends the current measurements to a computer via cable.

In this experimental setup, we used Nordic’s nRF52 Development Kit [22] with
their nRF52832 System-on-Chip [23], running Nordic’s nRF Connect Software
Development Kit [21], which includes Zephyr RTOS [14]. The code we flashed the
nodes with is based on Zephyr’s code samples [13]. Each BLE node was also
connected to Nordic’s Power Profiler Kit II [24] to provide accurate current
measurements. We adapted an unofficial python API for the power profiler [9]
to automate the measurements of our experiment and collected current
measurements for three hours with a 100 kHz sampling rate for all four nodes.
Figure 2 shows our experimental setup. We let the experiments run in an office
with people entering and leaving and phones connected to WiFi to replicate, to
some extent, a hospital room environment. Besides timestamp and current, four
time-independent features are included, which are summarized in Table 3.

Table 3: Features aside from the current drained in our dataset. ”hr” denotes the heart rate sensor, ”bt” denotes the body temperature sensor, and ”os” denotes the oxygen saturation sensor. Name | Explanation/possible values
---|---
Role | ”master” or ”slave”
Nr. connections | # nodes this node is connected to
Transmission rate (pps) | # packets sent per second
Packet size (B) | # bytes sent in a transmission
Node | ”central”, ”hr”, ”bt” or ”os”

###  4.2 Dataset Preprocessing

To create the dataset with which we trained our framework, we down-sampled the
measurements by a hundredfold to 1 kHz by using the sums of the measurements
as well as the maximums. The motivation for down-sampling is, on the one hand,
to reduce the size of the dataset and, on the other hand, to decrease the
number of time-steps the LSTMP framework needs to process to gather meaningful
information about past connections of the BLE node. We selected the down-
sampling by a hundredfold and made sure to keep connection events visible in
the dataset without mixing with the sleeping events. By taking the sum as well
as the maximum values, we capture both long events and short peaks.

Figure 3 shows sample traces for each node, where they are compared to one of
our models’ predictions. The other features are time-invariant and do not
change for a given node, so down-sampling them is straightforward. The
structure of this down-sampled dataset can be seen in Table 4.

Table 4: Down-sampled dataset with timestamps, the sum of currents drained, maximum current drained, and time-independent features. Timestamp (µs) | Sum of currents (µA) | Max. of currents (µA) | Role | Nr. | Transm. | Packet | Node
---|---|---|---|---|---|---|---
|  |  |  | conn. | rate (pps) | size (B) |
1725600000 | 105453.918095073 | 4038.58944143533 | master | 3 | 0 | 0 | central
1725601000 | 91505.1027793711 | 2783.95385863702 | master | 3 | 0 | 0 | central
1725602000 | 264778.571039428 | 11329.6786862516 | master | 3 | 0 | 0 | central

##  5 Performance Evaluation

In this section, we introduce the evaluation metrics used in this work and
assess the performance of our framework on the preprocessed dataset. We use as
a baseline the state-of-the-art LSTM framework introduced in [2]. Both our
framework and the baseline framework are capable of predicting the energy
consumption for any of the BLE nodes considered in this work. As input, they
receive samples from our down-sampled dataset (Table 4). We use Pytorch
Lightning [5] for implementation and training. Moreover, we leverage Pytorch
Forecasting [3] for encoding the features in our dataset and creating a
Pytorch dataset for training. We use a 70-15-15 split of the dataset for
training, validating, and testing the frameworks, respectively. In particular,
we take the first 70% of the measurements of each node as a training set, the
next 15% of each node as a validation set, and the last 15% of each node as a
test set, ensuring that each set has the same amount of samples for each node.

###  5.1 Performance Metrics

To study the performance of our proposed framework, we investigate the model
accuracy and motivated by the spirit of Green AI, also the model size. To
evaluate the accuracy, we adopt the Mean Absolute Percentage Error (MAPE)
between the prediction $\hat{y}$ and the actual consumption $y$ on the test
set, which can be written as

$\text{MAPE}(y,\hat{y})=\frac{1}{n}\sum_{i=0}^{n}\frac{|y_{i}-\hat{y}_{i}|}{\max(\epsilon,|y_{i}|)},$

where $n$ is the number of samples, and $\epsilon$ is a very small, strictly
positive number (to prevent division by zero). MAPE is a well-established
metric in the time series prediction problems and can be used to compare
performances independent of the scaling or the dataset trained on. To assess
the model size, we report the number of parameters for our framework as well
as the baseline framework.

###  5.2 Results

This subsection presents the results of our framework training.

####  5.2.1 Hidden Size Search

First, we trained our proposed framework with different values of $H_{cell}$
to predict one time-step into the future. A sample trace from the dataset with
the prediction of a model trained from our framework can be seen in Figure 3.
It can be seen that the predictions are accurate for all four nodes considered
in this work, regardless of their type or role.

a) Central

b) HR

c) BT

d) OS

Figure 3: Traces of energy consumption from the test set (blue) for each node
and the prediction made by the same model, which takes 50 time-steps as input
sample and predicts one step in the future (orange). The time period we use to
calculate the energy consumption is 1 ms. Note that BT is the only node that
uses actual sensor readings and, therefore, also powers the sensor.

Figure 4 shows the MAPEs of the proposed LSTMP framework achieved on the test
set with different values $H_{cell}$. The figure illustrates that when
$H_{cell}\leq 16$, the LSTMP-based ANN shows poor performance, achieving only
a MAPE of around 30%. For the case with $H_{cell}=32$ and $H_{cell}=64$, the
MAPE falls under the 20% mark, to 16.13% and 12.96%, respectively, indicating
high prediction accuracy. Increasing $H_{cell}$ further does not yield any
improvement. Figure 4 also shows that a huge model with $H_{cell}=650$
achieved a MAPE of 14.38% as well, providing comparable performance to the
LSTMP-based models with $H_{cell}=32$ and $H_{cell}=64$.

Figure 4: MAPE in % for our framework with various hidden sizes $H_{cell}$. A
lower MAPE indicates better accuracy.

####  5.2.2 Prediction Length

Following the results from Figure 4, we subsequently explore how many steps in
the future our LSTMP-based models with $H_{cell}=32$ and $H_{cell}=64$ can
predict and compare it to the baseline LSTM. The different $H_{out}$’s used
and the meaning behind them in the context of our BLE application are stated
in Table 5.

Table 5: Output sizes $H_{out}$ and their meaning for the dataset. Output size | Meaning
---|---
1, 2 | Next step(s) of the connection / sleep
3 | Whole connection event
10 | Two connection events (central only)
15 | Three connection events (central only)
50 | Connection event and sleep

Note that only the central node has three connections. The sequence length
$T$, which the LSTMP models see in the past, is fixed at 50 time-steps,
translating into 50 ms. We chose $T=50$ empirically because 50 ms of former
energy consumption are needed to see the preceding connection with the
parameters we have set in our BLE application. Only with this information can
a prediction be made about when the next connection will occur.

The results from our performance evaluation are shown in Figures 5 and 6.
Figure 5 shows the performance in terms of the MAPE score. It can be seen that
our framework can predict up to 10 steps in the future without substantially
losing accuracy for both $H_{cell}$, exhibiting similar performance to the
baseline. When predicting 15 or 50 steps in the future, the MAPE for both our
framework and the baseline exhibits a noticeable jump to above 30%, indicating
that they do not predict accurately anymore.

Figure 5: MAPE in % for our framework with hidden size $H_{cell}=32$ and
$H_{cell}=64$ predicting various amounts of steps in the future in comparison
with the baseline LSTM model from [2]. A lower MAPE indicates better accuracy.

Figure 6, on the other hand, shows the number of parameters of the baseline
framework and our framework for different prediction lengths. It can be seen
that for the number of prediction steps with an acceptable MAPE, i.e., for a
prediction length $H_{out}\leq 10$, our framework with $H_{cell}=32$ is
substantially smaller than the baseline. For a one-step prediction, it has
about five times fewer parameters. It can also be seen, however, that the
model size increases quicker for longer prediction lengths than the baseline,
indicating that the baseline model is the better choice for prediction tasks
where a substantial amount of future steps need to be predicted at once.

Figure 6: Number of model parameters for our framework with hidden size
$H_{cell}=32$ and $H_{cell}=64$ predicting various amounts of steps in the
future in comparison with the baseline LSTM model from [2]. For the sake of
visualization, the number of parameters for our framework with $H_{cell}=64$
predicting 50 steps in the future cannot be seen.

Notice that we did not train our framework with $H_{cell}=32$ and $H_{out}=50$
because for an LSTMP, the constraint $H_{out}<H_{cell}$ must be satisfied.

####  5.2.3 Performance for each Node

Until now, we have only looked into our framework’s performance for all four
aggregated nodes with different roles. In the following, we investigate the
performance of a model from our framework with $H_{cell}=64$ and $H_{out}=1$.
Figure 3 shows sample traces with predictions from our model for all four
nodes. It can be seen in the figure that the model accurately adapts to the
different energy consumption values in the sleep phase and that it is also
able to predict the three connection events in the case of the central node,
while it only predicts one connection event for each of the other three nodes.
Moreover, we calculated the MAPEs for each node separately, as shown in Table
6.

Table 6: MAPEs achieved by a model on the current consumption data of each node separately. HR denotes the heart rate sensor, BT denotes the body temperature sensor, and OS denotes the oxygen saturation sensor. Node | Central | HR | BT | OS
---|---|---|---|---
MAPE | 22.66% | 12.36% | 3.08% | 13.72%

It can be seen that the performance for HR and OS with a MAPE of 12.36% and
13.72%, respectively, are about the same as the MAPE for the whole dataset,
which is 12.96%. For the central node, the performance drops to 22.66%, which
can be explained by the fact that thrice as many connection events happen as
for the other nodes. During the connection events, unpredictable peaks in the
current consumption occur, negatively affecting our model’s accuracy. An
example of this can be seen in Figure 3 a). On the BT data, however, the
performance increases to a MAPE of only 3.08%, indicating highly accurate
predictions for this specific node, which can be attributed to this node’s
relatively low transmission rate.

####  5.2.4 Positioning our Model with Respect to Simple Store and Copy

Since the dataset used in this paper is repetitive, we compared our model to a
simple store and copy approach. We chose a copying window of 50 ms,
representing the connection interval. Our experimental results showed that
copying provides better performance for all nodes combined. However, this
copying mechanism requires perfect knowledge of the exact value of the
connection interval. In order to position our model, we trained it with
different sequence lengths that are shorter and longer than the Connection
Interval, representing a case without knowledge of the exact connection
interval. Our experiments showed that using sequence lengths longer than the
Connection Interval does not impact the accuracy of our model, and for the
case of a shorter sequence length, the performance drops a few percentages to
22.08%. Further investigation is required with different training sequences,
which is left for future work.

##  6 Conclusion

We have introduced a fine-grained energy consumption dataset for a healthcare-
resembling application with four BLE nodes. The dataset entails multiple
features of the nodes and fine-grained current measurements and is made
publicly available. Moreover, an accurate energy consumption prediction
framework has been proposed. The proposed framework maintains an acceptable
prediction accuracy with MAPEs below 25%, comparable to a state-of-the-art
prediction model while reducing the model complexity to a fifth. In addition,
we showed that the proposed framework is able to predict 10 time-steps in the
future with a MAPE lower than 20%. Furthermore, we demonstrated that the
proposed framework keeps a MAPE lower than 25% when examined on BLE nodes
resembling a critical healthcare scenario separately, with different numbers
of connections and transmission intervals.

##  7 Acknowledgment

The present work has received funding from the European Union’s Horizon 2020
Marie Skłodowska Curie Innovative Training Network Greenedge (GA. No. 953775).
The work of Hazem Sallouha was funded by the Research Foundation – Flanders
(FWO), Postdoctoral Fellowship No. 12ZE222N.

## References

  * [1] Making the ict sector energy efficient.
https://www.theparliamentmagazine.eu/news/article/energy-efficient-and-energy-
smart. [online] accessed on: July 2022.

  * [2] A. M. Alonso, F. J. Nogales, and C. Ruiz.  A single scalable LSTM model for short-term forecasting of massive electricity time series.  Energies, 2020.
  * [3] J. Beitner.  PyTorch Forecasting, 2020.
  * [4] Q. Chen and L. Tang.  A wearable blood oxygen saturation monitoring system based on bluetooth low energy technology.  Computer Communications, 2020.
  * [5] W. Falcon and The PyTorch Lightning team.  PyTorch Lightning, 3 2019.
  * [6] U. Farouk, M. Asante, and J. Ben.  A survey of machine learning’s electricity consumption models.  Communications on Applied Electronics, 2018.
  * [7] S. Hochreiter and J. Schmidhuber.  Long short-term memory.  Neural Computation, 1997.
  * [8] C. Hu, W. Bao, D. Wang, and F. Liu.  Dynamic adaptive DNN surgery for inference acceleration on the edge.  In IEEE Conference on Computer Communications, 2019.
  * [9] IRNAS.  Power profiling kit 2 unofficial python api.
https://www.zephyrproject.org/. [online] accessed on: October 2022.

  * [10] S. Jeddou, A. Baina, N. Abdallah, and H. El Alami.  Power consumption prediction of IoT application protocols based on Linear Regression.  International Journal of Artificial Intelligence and Machine Learning, 2021.
  * [11] P. H. Kindt, D. Yunge, R. Diemer, and S. Chakraborty.  Energy modeling for the Bluetooth Low Energy protocol.  ACM Transactions on Embedded Computing Systems, 2020.
  * [12] W. Kong, Z. Y. Dong, Y. Jia, D. J. Hill, Y. Xu, and Y. Zhang.  Short-term residential load forecasting based on LSTM recurrent neural network.  IEEE Transactions on Smart Grid, 2019.
  * [13] Z. Project.  Bluetooth samples.
https://docs.zephyrproject.org/latest/samples/bluetooth/bluetooth.html
readme.html. [online] accessed on: October 2022.

  * [14] Z. Project.  Zephyr project.
https://www.zephyrproject.org/. [online] accessed on: October 2022.

  * [15] S. Raza, P. Misra, Z. He, and T. Voigt.  Bluetooth smart: An enabling technology for the internet of things.  In IEEE 11th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), 2015.
  * [16] H. Sak, A. Senior, and F. Beaufays.  Long short-term memory based recurrent neural network architectures for large vocabulary speech recognition.  arXiv, 2014.
  * [17] H. Sallouha, A. Chiumento, and S. Pollin.  Aerial vehicles tracking using noncoherent crowdsourced wireless networks.  IEEE Transactions on Vehicular Technology, 2021.
  * [18] H. Sallouha, B. Van den Bergh, Q. Wang, and S. Pollin.  ulora: Ultra low-power, low-cost and open platform for the lora networks.  In Proceedings of the 4th ACM Workshop on Hot Topics in Wireless, 2017.
  * [19] M. Savi and F. Olivadese.  Short-term energy consumption forecasting at the edge: A federated learning approach.  IEEE Access, 2021.
  * [20] R. Schwartz, J. Dodge, N. A. Smith, and O. Etzioni.  Green AI.  arXiv, 2019.
  * [21] N. Semiconductor.  nrf connect sdk.
https://www.nordicsemi.com/products/development-software/nrf-connect-sdk.
[online] accessed on: October 2022.

  * [22] N. Semiconductor.  nrf52 dk.
https://www.nordicsemi.com/products/development-hardware/nrf52-dk. [online]
accessed on: October 2022.

  * [23] N. Semiconductor.  nrf52832.
https://www.nordicsemi.com/products/nrf52832. [online] accessed on: October
2022.

  * [24] N. Semiconductor.  Power profiler kit ii.
https://www.nordicsemi.com/products/development-hardware/power-profiler-kit-2.
[online] accessed on: October 2022.

  * [25] G. Shan, S.-y. Im, and B.-h. Roh.  Optimal AdvInterval for BLE scanning in different number of BLE devices environment.  In IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), 2016.
  * [26] M. Shao, X. Wang, Z. Bu, X. Chen, and Y. Wang.  Prediction of energy consumption in hotel buildings via support vector machines.  Sustainable Cities and Society, 2020.
  * [27] M. Siekkinen, M. Hiienkari, J. K. Nurminen, and J. Nieminen.  How low energy is bluetooth low energy? Comparative measurements with ZigBee/802.15.4.  In IEEE Wireless Communications and Networking Conference Workshops (WCNCW), 2012.
  * [28] J. Wang, M. K. Lim, C. Wang, and M.-L. Tseng.  The evolution of the internet of things (iot) over the past 20 years.  Computers & Industrial Engineering, 2021.
  * [29] J. Ye.  Using digitalization to achieve decarbonization goals.  Center for Climate and Energy Solutions, 2021.

  *[IoT]: Internet of Things
  *[BLE]: Bluetooth Low Energy
  *[ANNs]: Artificial Neural Networks
  *[LSTM]: Long Short-Term Memory
  *[LSTMP]: Long Short-Term Memory Projection
  *[MAPE]: Mean Absolute Percentage Error


Sunil KumarKopparapu AshishPanda

# A cost minimization approach to fix the vocabulary size in a tokenizer for
an End-to-End ASR system

###### Abstract

Unlike hybrid speech recognition systems where the use of tokens was
restricted to phones, biphones or triphones the choice of tokens in the end-
to-end ASR systems is derived from the text corpus of the training data. The
use of tokenization algorithms like Byte Pair Encoding (BPE) and WordPiece is
popular in identifying the tokens that are used in the overall training
process of the speech recognition system. Popular toolkits, like ESPNet use a
pre-defined vocabulary size (number of tokens) for these tokenization
algorithms, but there is no discussion on how vocabulary size was derived. In
this paper, we build a cost function, assuming the tokenization process to be
a black-box to enable choosing the number of tokens which might most benefit
building an end-to-end ASR. We show through experiments on LibriSpeech 100
hour set that the performance of an end-to-end ASR system improves when the
number of tokens are chosen carefully.

###### keywords:

sub-word tokenization, speech recognition, sentencepiece, byte pair encoding

##  1 Introduction

It was a standard practise to choose mono-phones, bi-phones, tri-phones as the
tokens to train a hybrid automatic speech recognition (ASR) system [1]. The
tokens to be trained was dependent on the prominent sounds in that language
and the training data required the phonetic transcription of the training
speech corpus. However, with the advent of end-to-end systems and the
availability of phonetic transcripts, the move has been on automatically
identifying the tokens from the text data of the training corpus. As a result,
most current ASR systems model tokens derived from the training text rather
than use unit which have relevance to the language or pronunciation.

Several tokenization algorithms, such as Byte Pair Encoding (BPE) [2],
WordPiece [3], or unigram language model tokenization [4] have been
researched. These algorithms, broadly work on the principle of iteratively
merging frequently occurring pairs of characters or tokens to create a
vocabulary of tokens that can represent the language's vocabulary efficiently.
The difference among these tokenization algorithms lies in the way characters
are paired. BPE uses a pre-tokenizer to split the training data into words and
creates a set of base vocabulary consisting of all symbols that occur in the
set of unique words. After this, BPE learns the merge rules to create a new
symbol from two symbols of the base vocabulary. This process goes on till the
desired number of symbols (or tokens) are created. While BPE chooses the most
frequent symbol pairs to merge, WordPiece merges the symbol pair that
maximizes the likelihood of the training data until the desired number of
symbols have been obtained. In contrast to BPE and WordPiece, Unigram language
model tokenization starts from a large set of symbols and trims down each
symbol to obtain a smaller set of symbols. SentencePiece [5] is a popular
language independent sub-word tokenizer and detokenizer for Neural Text
Processing. It does not need a pre-tokenizer unlike BPE and hence it is
suitable for languages such as Japanese and Chinese. While the above
tokenization algorithms work on training text, various efforts have been made
to bring in acoustic perspective into the tokenization process. Pronunciation
Assisted Subword Modeling (PASM) [6], Acoustic Data Driven Subword Modeling
(ADSM) and Phonetically Induced Subwords [7] are examples of such efforts.

Most ASR systems that use sub-word tokens for training fix the number of
tokens (vocabulary size) and use one of the above tokenizers to generate the
tokens from the training text data. To the best of our knowledge there has
been no discussion on the criteria used for determining the optimal number of
tokens and they are fixed empirically. In this paper, we explore a formulation
that can help identify the number of tokens best suited for ASR training. We
set about the task assuming the availability of a sub-word tokenizer and use
it as a black box.

We first formulate a cost function which when minimized results in an optimal
number of sub-word tokens for a given training text data. We specifically use
an off-the-shelf tokenizer for the purposes of demonstration but it should be
kept in mind that the formulation should work for any tokenizer. We then
evaluate the performance of a standard deep architecture ASR to validate the
choice of the number of sub-word tokens. The main contribution of this paper
is in (a) formulating a framework to identify the number of sub-word tokens
and (b) building a cost function to enable identifying the optimal number of
sub-word tokens and (c) evaluating the performance on a ASR to validate the
need for formal identification of the number of sub-word tokens required to
train an ASR system.

The rest of the paper is organized as follows. We describe the formulation of
the cost function to allow identification of the optimal number of tokens
given a training text corpus in Section 2. In Section 3 we experiment with
LibriSpeech 100 hours training data set to first identify the optimal number
of tokens and then use the tokens to evaluate the performance of an end-to-end
ASR. We conclude in Section 5.

##  2 Problem Setup

Let ${\cal S}$ be a text corpus consisting of ${{\cal
S}}=\\{{s}_{1},{s}_{2},\cdots,{s}_{{k}}\\}$ ${k}$ sentences associated with
training data which consists of ${w}$ words (${w}_{u}$, unique). For
simplicity, we will assume the text to be English so that blank spaces
represent word boundaries and newlines identify sentences. Let ${\cal T}$ be a
tokenization routine (for example, byte pair encoding [8]) which takes as
input a variable $n$ and operates on ${\cal S}$ to produce a set of tokens
$T_{n}$, namely,

${\cal T}(n,{\cal S})=T_{n}$ (1)

where $T_{n}=\\{t_{1},t_{2},\cdots,t_{n}\\}$, $|T_{n}|=n$ is the number of
tokens, $t_{i}$ is the $i^{th}$ token, and $t_{i}\neq t_{j}$ for $\forall
i\neq j$. Let ${enc^{{\cal T}}}$ and ${dec^{{\cal T}}}$ be a pair of functions
associated with ${\cal T}$ such that

${enc^{{\cal T}}}({s}_{i})=\bigcup_{l=1}^{\beta_{i}}\tau_{l}$

acts on a sentence ${s}_{i}$ in the corpus ${\cal S}$ and represents it using
$\beta_{i}$ tokens $\\{\tau_{l}\\}_{l=1}^{\beta_{i}}\in T$, and ${dec^{{\cal
T}}}$ function

${dec^{{\cal T}}}\left(\bigcup_{l=1}^{\beta_{i}}\tau_{l}\right)={s}_{i}$

reconstructs ${s}_{i}$ by concatenating (represented by $\bigcup$) a sequence
of tokens. Let

$\theta_{t}=\sum_{i=1}^{{k}}\beta_{i}$

denote the number of tokens required to span the corpus ${\cal S}$. As
mentioned earlier, $\beta_{i}$ represents the number of tokens required to
represent the sentence ${s}_{i}$. Let $\Gamma$ represent the set of all token
required to span the corpus ${\cal S}$, namely,

$\Gamma=\bigcup_{i=1}^{k}\left(\bigcup_{l=1}^{\beta_{i}}\tau_{l}\right)$

where the total number of tokens in $\Gamma$ is
$|\Gamma|=\sum_{i=1}^{k}\beta_{i}.$ We can compute the frequency of occurrence
of token $\tau\in T_{n}$ as

$f(\tau)=\sum_{i=1}^{|\Gamma|}[\Gamma_{i}=\tau].$

where $\tau\in T_{n}$ and $\Gamma_{i}\in\Gamma$ and $[\cdot]$ are the Iverson
brackets such that $[Q]$ is defined to be $1$ if $Q$ is true, and $0$ if it is
false. Further let $f^{+}$ and $f^{-}$ represent the average of top five most
frequently occurring tokens and the top five most infrequently occurring
tokens respectively. Note that (a) $\theta_{t}$, (b) ${f^{+}}$, and (c)
${f^{-}}$ are a function of $n$ as seen in (1).

We hypothesize that choosing the optimal number of tokens would be equivalent
to finding an $n^{*}$ which minimizes the cost function (3), namely,

$n^{*}=\min_{n}\left\\{{{C}}\right\\}$ (2)

where

${{C}}=\left\\{\alpha_{1}\overbrace{n}^{t_{1}}+\alpha_{2}\overbrace{\left(\frac{f^{+}}{f^{-}}-1\right)}^{t_{2}}+\alpha_{3}\overbrace{\left(\frac{\theta_{t}}{{w}}-1\right)}^{t_{3}}\right\\}$
(3)

is the cost function and $\alpha_{1,2,3}$ are weights which are chosen
heuristically.

The first term, $t_{1}$, in the cost function (3) is to ensure that the total
number of tokens used to represent the corpus ${\cal S}$ is small because a
large $n$ means not only training for a large number of tokens which in turn
requires a larger amount of training data but smaller number of tokens can
result in faster training and inference times for ASR systems. With fewer
tokens to model, the computational complexity of the ASR system can be
reduced, leading to quicker training convergence and real-time performance
during inference. The second term, $t_{2}$ ensures a balance between the most
frequently occurring and the least frequently occurring tokens, because an
imbalance in data can lead to bias during training [9]. Note that a perfectly
balanced training data would have $\left(\frac{f^{+}}{f^{-}}\right)=1$. And
the third terms, $t_{3}$ ensures that the number of tokens required to
represent the corpus ${\cal S}$ is close to the number of words ${w}$ in the
corpus. This constraint makes sure that the cost of compute is minimum,
because most major Gen AI portals charge for their services based on the
number of tokens required to represent the input and generate an output.

The construction of the cost function as mentioned in (3) to identify the
optimal number of tokens is one of the main contributions of this paper.

##  3 Experimental Setup

We use the LibriSpeech-100111https://www.openslr.org/resources/12/train-
clean-100.tar.gz (sentences:28537; words:990093) dataset in our experiments.
Note that the database consists of 100 hours of read English speech
accompanied by the textual transcript. The training data consists of
${k}=28538$ sentences and ${w}=990093$ words of which ${w}_{u}=33798$ are
unique. Our experimental evaluations, in this paper, are of two types. We make
use of the text transcript and determine the optimal number of tokens. We also
validate the usefulness of the obtained optimal number of tokens by ASR
systems using the same tokens. We report the performance obtained on the test-
clean222https://www.openslr.org/resources/12/test-clean.tar.gz
(sentences:2620; words: 52576) and test-
other333https://www.openslr.org/resources/12/test-other.tar.gz
(sentences:2939; words:52343) datasets.

We have used state-of-the-art conformer encoder-decoder architecture as the
ASR. The conformer model is implemented using an ESPNet toolkit [10] with
Librispeech 100 hours (low-resource) recipe. While we changed the number of
tokens in the original recipe, we used the rest if the model hyper-parameters
as described below:

The encoder of the conformer has $12$ layers and the decoder has $6$ layers.
The model dimension is $256$ while number of attention heads used is $4$.
Models were trained using Adam optimizer [11] with $\beta_{1}=0.9$,
$\beta_{2}=0.98$ and $\epsilon=10^{-9}$, which is along the lines of the
optimizer proposed in [12]. Warm up steps used is $25000$. The models are
trained for $100$ epochs and the batch size was $64$. A single Nvidia RTX 3090
GPU was used.

No language model has been used for shallow fusion in this work. The $n$
tokens extracted from the training text served as output units. Features used
for the model are log mel spectrograms with $80$ dimensions along with the
pitch (total $81$). $3$ way speed perturbation [13] with speed factors of
$0.9$, $1.0$ and $1.1$ and SpecAugment [14] was used in all the experiments.

##  4 Experimental Results

(a) SentencePiece-Unigram.

(b) SentencePiece-BPE.

Figure 1: $t_{1},t_{2},t_{3}$ in the cost function $C$ (3) for $n=30$ to
$1000$.

We computed the cost function ${{C}}$ (3) by varying $n$ between $30$ and
$1000$. We found that higher value of $n(>1000)$ always resulted in a higher
${{C}}$ and $n<30$ resulted in the number of tokens ($n$) being less than the
number of characters in the training text data. We trained the SentencePiece
[5], with unigram (–vocab_size=n, –model_type=unigram,
–split_by_whitespace=False) called SentencePiece-Unigram model and with BPE
(–vocab_size=n, –model_type=bpe, –split_by_whitespace=False) called
SentencePiece-BPE model. Figure 1 shows the plot of $t_{1},t_{2},t_{3}$ (3) as
a function of number of tokens (x-axis). In both Figure 1(a) (SentencePiece-
Unigram) and Figure 1(b) (SentencePiece-BPE) it can be observed that while
$t_{1}$ is linearly increasing and $t_{3}$ is exponentially decreasing;
$t_{2}$ exhibits a dip before linearly increasing as a function of $n$. Figure
2 (Figure 3) shows the plot of the cost function $C$, for SentencePiece-
Unigram (SentencePiece-BPE), for $n=1,\cdots,1000$ for $\alpha_{1,2,3}=1,0,0$
(Figure 2(a) (3(a))), $\alpha_{1,2,3}=0,1,0$ (Figure 2(b) (3(b))), and
$\alpha_{1,2,3}=0,0,1$ (Figure 2(c) (3(c))) with the $n^{*}$ (2) marked with a
red "*". Clearly the minimum value of ${{C}}$ (3) varies with different values
of $\alpha$'s. As expected, $n^{*}=30$ when the cost function is only a
function of the number of tokens for both SentencePiece-Unigram (Figure 2(a))
and SentencePiece-BPE (Figure 3(a)) and $n^{*}=1000$ when ${{C}}$ is a
function of only $t_{3}$ (see Figure 2(c) and 3(c)). The most interesting
aspect is observable for $t_{2}$ where the $n^{*}=145$ for SentencePiece-
Unigram (see Figure 2(b)) and $n^{*}=97$ for SentencePiece-BPE (see Figure
3(b)). Figure 4 shows the plot of the cost function ${{C}}$ for
$\alpha_{1,2,3}=1$. As shown in Figure 4(a) the minimum value of ${{C}}$
occurs for $n^{*}=61$ for SentencePiece-Unigram model while $n^{*}=70$ for
SentencePiece-BPE model.

(a) $\alpha_{1,2,3}=(1,0,0)$; $n^{*}=30$.

(b) $\alpha_{1,2,3}=(0,1,0)$; $n^{*}=145$.

(c) $\alpha_{1,2,3}=(0,0,1)$; $n^{*}=1000$.

Figure 2: SentencePiece-Unigram. $n^{*}$ marked with a red "*". x-axis shows
the number of tokens and y-axis the ${{C}}$.

(a) $\alpha_{1,2,3}=(1,0,0)$; $n^{*}=30$.

(b) $\alpha_{1,2,3}=(0,1,0)$; $n^{*}=97$.

(c) $\alpha_{1,2,3}=(0,0,1)$; $n^{*}=1000$.

Figure 3: SentencePiece-BPE. $n^{*}$ marked with a red "*". x-axis shows the
number of tokens and y-axis the ${{C}}$.

(a) SentencePiece-Unigram. $n^{*}=61$.

(b) SentencePiece-BPE. $n^{*}=70$.

Figure 4: Optimal number of tokens ($n^{*}$) for $\alpha_{1,2,3}=(1,1,1)$

The experiments above provide the optimal values for number of tokens
corresponding to different values of $\alpha$'s. We now present the
performance of the ASR systems with the number of tokens obtained above,
namely $n^{*}=30,61,145,1000$ for SentencePiece-Unigram and
$n^{*}=30,97,70,1000$ for SentencePiece-BPE, in Table 1. We compare this with
the ESPNet recipe recommendation of using the number of tokens as 300 using
SentencePiece-Unigram language model. Using this value ($n=300$) results in an
average WERs of $13.8\%$ over the dev sets and $14.5\%$ over the test sets
(see Table 1). Using 30 tokens (which corresponds to $\alpha_{1,2,3}=(1,0,0)$,
the average WER over test sets reduces very slightly to $14.3\%$, however the
average WER over the dev sets increases slightly to $13.9\%$. Using $n^{*}=61$
tokens and 1000 tokens (corresponding to $\alpha_{1,2,3}=(0,1,0)$ and
$(0,0,1)$, respectively), did not improve the performance, with $n=1000$
tokens performing the worst. It suggests that blindly increasing the number of
tokens does not necessarily improve the performance of the ASR. When we
provide equal weight of $1$ to $t_{1},t_{2}$ and $t_{3}$ in the cost function,
we get the number of tokens as $n^{*}=145$ (SentencePiece-Unigram) and
$n^{*}=70$ (SentencePiece-BPE). This choice of $n$ for SentencePiece-Unigram
outperforms all the other systems resulting in an average WER of $13.2\%$ over
the dev sets and an average WER of $13.6\%$ over the test sets. We observe
similar improvement in ASR performance for SentencePiece-BPE . While the
recommended $n=300$ tokens with ASR result in an average WERs of $14.2\%$ and
$14.4\%$ with dev and test sets respectively, the choice of $n^{*}=70$ tokens,
which correspond to $\alpha_{1,2,3}=(1,1,1)$ show an improved performance of
$13.7\%$ and $14.2\%$ WER for dev and test sets respectively. What is
remarkable is that this improvement in ASR performance comes with reduced
computational cost when compared to the use of recommended $300$ tokens in
ESPNet recipe. This set of experiments again reinforces the earlier finding
that blindly increasing the number of tokens does not improve the performance
of the ASR system.

Table 1: WERs (in %) for various $n$ on Librispeech 100h. ``dev-avg": average
over dev-clean and dev-other. ``test-avg": average over test-clean and test-
other

SentencePiece-Unigram
---
$n(\alpha_{1,2,3})$ | dev-clean | dev-other | dev-avg | test-clean | test-other | test-avg
300 (-) | 7.7 | 20.0 | 13.8 | 8.3 | 20.8 | 14.5
30 (1, 0, 0) | 7.6 | 20.3 | 13.9 | 7.9 | 20.7 | 14.3
145 (0, 1, 0) | 8.6 | 20.8 | 14.7 | 9.0 | 21.0 | 15.0
1000 (0, 0, 1) | 11.0 | 21.0 | 16.0 | 11.5 | 23.0 | 17.2
61 (1, 1, 1) | 7.2 | 19.2 | 13.2 | 7.7 | 19.6 | 13.6
SentencePiece-BPE
$n(\alpha_{1,2,3})$ | dev-clean | dev-other | dev-avg | test-clean | test-other | test-avg
300 (-) | 8.1 | 20.4 | 14.2 | 8.5 | 20.4 | 14.4
30 (1, 0, 0) | 7.6 | 20.3 | 13.9 | 7.9 | 20.7 | 14.3
97 (0, 1, 0) | 7.7 | 20.1 | 13.9 | 8.2 | 20.4 | 14.3
1000 (0, 0, 1) | 7.9 | 20.0 | 13.9 | 8.0 | 20.6 | 14.3
70 (1, 1, 1) | 7.6 | 19.8 | 13.7 | 8.0 | 20.4 | 14.2

It is interesting to note that the best performance is obtained when
$\alpha_{1,2,3}=1$. This suggests that each of the terms $t_{1},t_{2},t_{3}$
in the cost function has a role to play in determining the number of tokens
optimal for the ASR performance. The number of tokens will change when the
training text changes or the tokenizer changes and hence the cost function
minimization should be performed once every time the training text or the
tokenizer changes.

##  5 Conclusions

In this paper we proposed a formulation based on construction of a cost
function that allows for the identification of an optimal vocabulary size for
the tokenizers used during the training of a speech recognition engine. The
formulated cost function is based on keeping a balance between the most
frequently and least frequently occurring training sub-word data to avoid bias
in training as well as making sure that the number of tokens required to
represent the data is minimal from the computing cost perspective. Using
Librispeech 100 hours training set, we showed the efficacy of the approach to
determining the vocabulary size of the tokenkinzer. In future, it would be
worthwhile to look into the cost function in more detail to include other
relevant factors. A robust approach to determining the values of $\alpha$'s
would improve the performance further.

## References

  * [1] T. Raissi, E. Beck, R. Schlüter, and H. Ney, ``Towards consistent hybrid hmm acoustic modeling,'' arXiv, 2021.
  * [2] R. Sennrich, B. Haddow, and A. Birch, ``Neural machine translation of rare words with subword units,'' in _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , K. Erk and N. A. Smith, Eds. Berlin, Germany: Association for Computational Linguistics, Aug. 2016, pp. 1715–1725. [Online]. Available: https://aclanthology.org/P16-1162
  * [3] M. Schuster and K. Nakajima, ``Japanese and korean voice search,'' in _2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2012, pp. 5149–5152.
  * [4] T. Kudo, ``Subword regularization: Improving neural network translation models with multiple subword candidates,'' in _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , I. Gurevych and Y. Miyao, Eds. Melbourne, Australia: Association for Computational Linguistics, Jul. 2018, pp. 66–75. [Online]. Available: https://aclanthology.org/P18-1007
  * [5] T. Kudo and J. Richardson, ``SentencePiece: A simple and language independent subword tokenizer and detokenizer for neural text processing,'' Brussels, Belgium, pp. 66–71, Nov. 2018. [Online]. Available: https://aclanthology.org/D18-2012
  * [6] H. Xu, S. Ding, and S. Watanabe, ``Improving end-to-end speech recognition with pronunciation-assisted sub-word modeling,'' in _ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2019, pp. 7110–7114.
  * [7] V. Papadourakis, M. Mueller, J. Liu, A. Mouchtaris, and M. Omologo, ``Phonetically induced subwords for end-to-end speech recognition,'' in _Interspeech 2021_ , 2021. [Online]. Available: https://www.amazon.science/publications/phonetically-induced-subwords-for-end-to-end-speech-recognition
  * [8] V. Zouhar, C. Meister, J. Gastaldi, L. Du, T. Vieira, M. Sachan, and R. Cotterell, ``A formal perspective on byte-pair encoding,'' in _Findings of the Association for Computational Linguistics: ACL 2023_ , A. Rogers, J. Boyd-Graber, and N. Okazaki, Eds. Toronto, Canada: Association for Computational Linguistics, Jul. 2023, pp. 598–614. [Online]. Available: https://aclanthology.org/2023.findings-acl.38
  * [9] D. Katare, D. S. Noguero, S. Park, N. Kourtellis, M. Janssen, and A. Y. Ding, ``Analyzing and mitigating bias for vulnerable classes: Towards balanced representation in dataset,'' arXiv, 2024.
  * [10] S. Watanabe, T. Hori, S. Karita, T. Hayashi, J. Nishitoba, Y. Unno, N. Enrique Yalta Soplin, J. Heymann, M. Wiesner, N. Chen, A. Renduchintala, and T. Ochiai, ``ESPnet: End-to-End Speech Processing Toolkit,'' in _Proc. Interspeech 2018_ , 2018, pp. 2207–2211.
  * [11] D. P. Kingma and J. Ba, ``Adam: A method for stochastic optimization,'' in _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , Y. Bengio and Y. LeCun, Eds., 2015. [Online]. Available: http://arxiv.org/abs/1412.6980
  * [12] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. u. Kaiser, and I. Polosukhin, ``Attention is all you need,'' in _Advances in Neural Information Processing Systems_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds., vol. 30. Curran Associates, Inc., 2017\. [Online]. Available: https://proceedings.neurips.cc/paper_files/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf
  * [13] T. Ko, V. Peddinti, D. Povey, and S. Khudanpur, ``Audio augmentation for speech recognition,'' in _Proc. Interspeech 2015_ , 2015, pp. 3586–3589.
  * [14] D. S. Park, W. Chan, Y. Zhang, C.-C. Chiu, B. Zoph, E. D. Cubuk, and Q. V. Le, ``SpecAugment: A Simple Data Augmentation Method for Automatic Speech Recognition,'' in _Proc. Interspeech 2019_ , 2019, pp. 2613–2617.


# On the relationship between variable Wiener index and variable Szeged index

Stijn Cambie Department of Mathematics, Radboud University Nijmegen, Postbus
9010, 6500 GL Nijmegen, The Netherlands. Email<EMAIL_ADDRESS>This work
has been supported by a Vidi Grant of the Netherlands Organization for
Scientific Research (NWO), grant number $639.032.614$. John Haslegrave
Mathematics Institute, University of Warwick, Coventry, UK. Email:
<EMAIL_ADDRESS>Supported by the UK Research and Innovation Future
Leaders Fellowship MR/S016325/1.

###### Abstract

We resolve two conjectures of Hriňáková, Knor and Škrekovski (2019) concerning
the relationship between the variable Wiener index and variable Szeged index
for a connected, non-complete graph, one of which would imply the other. The
strong conjecture is that for any such graph there is a critical exponent in
$(0,1]$, below which the variable Wiener index is larger and above which the
variable Szeged index is larger. The weak conjecture is that the variable
Szeged index is always larger for any exponent exceeding $1$. They proved the
weak conjecture for bipartite graphs, and the strong conjecture for trees.

In this note we disprove the strong conjecture, although we show that it is
true for almost all graphs, and for bipartite and block graphs. We also show
that the weak conjecture holds for all graphs by proving a majorization
relationship.

Keywords: variable Wiener index; variable Szeged index; topological indices.

MSC 2020: 05C09, 05C12, 05C35.

##  1 Introduction

Topological indices of graphs originate from chemical graph theory, and are
descriptors of organic molecules that depend only on the graph of atoms and
bonds and not on their physical arrangement. The oldest and most important of
these is the Wiener index, or total distance, which was introduced by Wiener
in 1947 and shown to accurately predict alkane boiling points [20]. Here, as
is usual, the index is applied to the unweighted graph of carbon-carbon bonds,
neglecting hydrogen atoms. Wiener subsequently established correlations
between the Wiener index and other physical quantities (see e.g. [21]). The
Wiener index was rediscovered by Rouvaray [19] in the 1970s, and applied to
more general chemical graphs. It was independently introduced to the
mathematics literature for trees by Zelinka [22], and subsequently extended to
general graphs by Entringer, Jackson and Snyder [4]. Since the late 1970s, it
has seen an explosion of interest in both fields; see e.g. the survey article
[2] from the mathematical side, and the collection [6] from the chemical side.
Its importance has led to the study of many other topological indices, such as
the Randić index [18], first and second Zagreb indices [8, 7], and the Hosoya
index [9].

Among topological indices, the Wiener index has a particularly simple and
natural definition: it is the sum, over all unordered pairs of vertices, of
the graph distance between those vertices (hence the alternative name of
“total distance”; it is linearly related to the average distance when the
order is fixed). We define the Wiener index only when the graph is connected,
so all distances are finite; this is certainly the case for molecular graphs.

As a special case of the alternative method to compute $W(G)$ by use of a
canonical metric representation of a graph, as defined in [12], it is well
known that for a tree $T$ one can compute the total distance as a sum of a
certain quantity over the edges instead of the sum of distances over all pairs
of vertices. For each edge $e=uv$, write $n_{u}(v)$ for the number of vertices
strictly closer to $u$ than to $v$ (including $u$ itself), and $n_{v}(u)$ for
the number strictly closer to $v$ than to $u$. Then

$W(T)=\sum_{uv\in E(T)}n_{x}(y)\cdot n_{y}(x).$ (1)

This fact, which follows from a simple double-counting, was observed by Wiener
in his original paper [20], where only trees were considered. However, (1)
fails to hold for most other graphs, owing to the fact that shortest paths are
typically not unique.

For a general graph $G$, the right-hand side of (1) denotes a different
topological index, introduced by Gutman [5] and subsequently called the Szeged
index:

$\operatorname{Sz}(G):=\sum_{uv\in E(G)}n_{u}(v)\cdot n_{v}(u).$

In general it is not necessarily true that $\operatorname{Sz}(G)=W(G)$, but
the inequality $\operatorname{Sz}(G)\geq W(G)$ holds for all connected graphs
[13]. The graphs where equality occurs were classified by Dobrynin and Gutman
[3]; these are precisely the block graphs (also known as clique trees), that
is, graphs where every maximal biconnected subgraph is complete. The
difference between the Szeged and Wiener indices can take any non-negative
integer value other than $1$ or $3$ [16].

The study of topological indices encompasses variable forms, which depend not
only on the graph $G$ but on a parameter often denoted $\alpha$; the terms
which make up the index in question are raised to the power $\alpha$ before
summing. This allows the sensitivity of the topological index to extreme
values to be altered. For example, the variable form of the Randić index was
introduced in [1], and the variable Zagreb indices in [15].

Hriňáková, Knor and Škrekovski [10] generalized the Wiener and Szeged indices
to analogous variable forms, and studied the relation between the variable
Wiener index and variable Szeged index. For a parameter $\alpha$, these two
graph parameters are defined as respectively

$W^{\alpha}(G):=\sum_{u,v\in
V}d(u,v)^{\alpha}\quad\text{and}\quad\operatorname{Sz}^{\alpha}(G):=\sum_{uv\in
E(G)}(n_{u}(v)\cdot n_{v}(u))^{\alpha}.$

They gave the following two conjectures (in these conjectures, and the rest of
this paper, graphs are tacitly assumed to be connected).

######  Conjecture 1.1 ([10, Conjecture 5]).

For every non-complete graph $G$ there is a constant $\alpha_{G}\in(0,1)$ such
that

$\displaystyle\operatorname{Sz}^{\alpha}(G)$
$\displaystyle>W^{\alpha}(G)\quad$ $\displaystyle\text{if }\alpha>\alpha_{G};$
$\displaystyle\operatorname{Sz}^{\alpha}(G)$
$\displaystyle=W^{\alpha}(G)\quad$ $\displaystyle\text{if }\alpha=\alpha_{G};$
$\displaystyle\operatorname{Sz}^{\alpha}(G)$
$\displaystyle<W^{\alpha}(G)\quad$ $\displaystyle\text{if }\alpha<\alpha_{G}.$

######  Conjecture 1.2 ([10, Conjecture 6]).

For every non-complete graph $G$ and every $\alpha>1$ we have
$\operatorname{Sz}^{\alpha}(G)>W^{\alpha}(G)$.

Note that Conjecture 1.1, since it requires $\alpha_{G}\leq 1$, implies
Conjecture 1.2. Complete graphs are excluded from the conjectures since if $G$
is complete we have
$\operatorname{Sz}^{\alpha}(G)=\binom{|G|}{2}=W^{\alpha}(G)$ for every
$\alpha$.

If we consider $(d(u,v))_{u,v\in V(G)}$ and $(n_{u}(v)\cdot n_{v}(u))_{uv\in
E(G)}$ as two sequences (of positive integers) $(x_{i})_{i}$ and $(y_{i})_{i}$
derived from a graph, then we are comparing the sums $\sum f(x_{i})$ and $\sum
f(y_{i})$ where $f(x)=x^{\alpha}$. A famous inequality related to such sums is
Karamata’s inequality [11], which is a generalization of the better known
inequality of Jensen. Hriňáková et al. [10] used Karamata’s inequality to
derive inequalities between $\operatorname{Sz}^{\alpha}(G)$ and
$W^{\alpha}(G)$ for trees and bipartite graphs (when $\alpha>1$), proving that
the strong conjecture holds for trees and the weak conjecture for bipartite
graphs.

In Section 2, we prove that the weak conjecture is indeed true by a small
adaptation of Karamata’s inequality combined with a majorization result. In
Section 4 we describe a family of counterexamples to the strong conjecture.
However, we are able to prove the strong conjecture for some special families
of graphs in Section 3. In particular we show that it is true for bipartite
graphs, block graphs, and all graphs in a moderately sparse regime. We show
that it is true for almost all graphs in a very strong sense: we prove that it
is true with high probability for the random graph $G(n,m)$ (that is, a
uniformly random choice from the set of all connected graphs with $n$ vertices
and $m=m(n)$ edges), even if $m$ is chosen adversarially.

##  2 Proof of the weak conjecture

###  2.1 An adaptation of Karamata’s inequality

Karamata’s inequality generalises Jensen’s inequality for convex functions to
majorizing sequences. In this article, we will find it convenient to define
the notion of majorizing sequences in a slightly more general way, in the
sense that the sequences do not need to have the same length or sum.
Throughout the whole article, a sequence will always be ordered (from largest
to smallest).

######  Definition 2.1 (majorizing sequences).

Let $(x_{i})_{1\leq i\leq n}$ and $(y_{i})_{1\leq i\leq m}$ be two sequences.
Then the sequence $(x_{i})_{i}$ majorizes $(y_{i})_{i}$ if for every positive
integer $k$ it is true that $\sum_{1\leq i\leq k}x_{i}\geq\sum_{1\leq i\leq
k}y_{i}$. In this summation $x_{i}$ and $y_{j}$ are taken to be zero if $i>n$
or $j>m$.

With this definition in place, Karamata’s inequality is as follows.

######  Theorem 2.2 (Karamata’s inequality).

Suppose $(x_{i})_{1\leq i\leq n}$ and $(y_{i})_{1\leq i\leq n}$ are decreasing
sequences of equal length, taking values in some interval $I$, with
$(x_{i})_{i}$ majorizing $(y_{i})_{i}$. Let $f:I\to\mathbb{R}$ be a convex
function. If either of the following conditions are satisfied:

  1. (i)

$\sum_{i=1}^{n}x_{i}=\sum_{i=1}^{n}y_{i}$ or

  2. (ii)

$f$ is increasing on $I$,

then $\sum_{i=1}^{n}f(x_{i})\geq\sum_{i=1}^{n}f(y_{i})$. Furthermore, provided
$f$ is strictly convex, we have equality only if the two sequences are
identical.

The inequality under condition (i) is Karamata’s original formulation [11];
the sufficiency of the alternative condition (ii) is well known and may be
proved in the same way (see, for example, [17, Theorem 12.7]).

As a corollary, we obtain the following modified version for integer
sequences.

######  Corollary 2.3.

Let $\vec{x}=(x_{i})_{1\leq i\leq n}$ and $\vec{y}=(y_{i})_{1\leq i\leq m}$ be
two sequences of nonnegative integers such that the former majorizes the
latter and let $t=\sum_{i}x_{i}-\sum_{i}y_{i}$. Let $f$ be a function
satisfying $f(0)=0,f(1)=1$ and $f^{\prime}(x),f"(x)\geq 0$ for all
$x\in\mathbb{R}^{+}$. Then

$\sum_{i}f(x_{i})\geq\sum_{i}f(y_{i})+t.$

If the two sequences are not equal (which is certainly the case when $t>0$)
and $f$ is strictly convex, the inequality is strict as well.

###### Proof.

We can extend the sequence $y_{i}$ with $t$ values equal to $1$ in the right
spot (i.e. such that the sequence is still ordered) and add zeros to one of
the two sequences to produce sequences $\vec{x}^{\prime},\vec{y}^{\prime}$ of
the same length. Suppose that $y_{k}$ is the last positive term of $\vec{y}$,
so that the $t$ extra terms become $y^{\prime}_{k+1},\ldots,y^{\prime}_{k+t}$.
Note that $\sum_{i=1}^{k}y^{\prime}_{i}\leq\sum_{i=1}^{k}x^{\prime}_{i}$, and
for $1\leq s\leq t$, we have
$\sum_{i=1}^{k+s}y^{\prime}_{i}=s+\sum_{i=1}^{k}y_{i}$. If
$x^{\prime}_{i+s}>0$ then we have $\sum_{i=1}^{k+s}x^{\prime}_{i}\geq
s+\sum_{i=1}^{k}x^{\prime}_{i}\geq\sum_{i=1}^{k+s}y^{\prime}_{i},$ and if not
we have $\sum_{i=1}^{k+s}x^{\prime}_{i}=\sum_{i\geq
1}x^{\prime}_{i}\geq\sum_{i=1}^{k+s}y^{\prime}_{i}.$ Consequently the updated
sequence $\vec{x}^{\prime}$ does majorize $\vec{y}^{\prime}$ and so Karamata’s
inequality (i) says that

$\sum_{i}f(x_{i})\geq\sum_{i}f(y_{i})+t.\qed$

###  2.2 A majorization relationship

As the reader may expect, the crucial fact we will need is the following
majorization between the two sequences derived from the graph. We will write
$m=|E(G)|$ and $N=\binom{|G|}{2}$ for the natural lengths of the two
sequences; we will frequently find it convenient to extend $(n_{e})_{e\in
E(G)}$ to a sequence of length $N$ by adding zero terms.

######  Proposition 2.4.

For every graph $G$, the sequence $(n_{u}(v)\cdot n_{v}(u))_{uv\in E(G)}$
majorizes the sequence $(d(u,v))_{u,v\in V}$.

###### Proof.

For every edge $uv$, let $n_{uv}=n_{u}(v)\cdot n_{v}(u)$. Let $(n_{i})_{1\leq
i\leq m}$ (where $m=\lvert E(G)\rvert$) be the ordered sequence (from largest
to smallest) of $(n_{e})_{e}$ and let $(d_{i})_{i}$ be the ordered sequence of
the distances $(d(u,v))_{u,v\in V}$. The following claim essentially gives the
intuition behind the majorization of the sequences, the property that the
$n_{i}$ are larger than $d_{i}$ in some structured way.

######  Claim 2.5.

For every pair of vertices $x$ and $y$ and every edge $e=uv$ on a shortest
path between $x$ and $y$, we have $d(x,y)\leq n_{e}.$

###### Proof.

Note that there are $d(x,y)+1$ vertices on a shortest path from $x$ and $y$,
all of them belonging to $N_{u}(v)$ or $N_{v}(u)$. Hence $d(x,y)+1\leq
n_{u}(e)+n_{v}(e)$, from which $d(x,y)\leq n_{u}(v)\cdot n_{v}(u)=n_{e}$
follows. ∎

This implies that $d(x,y)=\sum_{e\in P}\lambda_{e}n_{e}$, where $P$ is a
shortest path (containing $d(x,y)$ edges by definition) between $x$ and $y$
and $\lambda_{e}=\frac{1}{n_{e}}\leq\frac{1}{d(x,y)}$ (by Claim 2.5), so
$\sum_{e\in P}\lambda_{e}\leq 1.$

As a consequence, we have

$\displaystyle\sum_{i=1}^{k}d_{i}$ $\displaystyle=\sum_{i=1}^{k}\sum_{e\in
P_{i}}\lambda_{e}n_{e}$ $\displaystyle=\sum_{e\in E}\Lambda_{e}n_{e},$

where $P_{i}$ is the chosen shortest path corresponding to the distance
$d_{i}$. Here every $\Lambda_{e}$ equals the number of shortest paths $P_{i}$
through $e$ (so at most $n_{e}$) times $\lambda_{e}$, which is bounded by $1$.
Also we know $\sum_{e\in E}\Lambda_{e}=\sum_{i=1}^{k}\sum_{e\in
P_{i}}\lambda_{e}\leq k$. This implies $\sum_{e\in
E}\Lambda_{e}n_{e}\leq\sum_{i=1}^{k}n_{i}$. ∎

As a consequence, we note that Conjecture 1.2 is true in a slightly stronger
form.

######  Theorem 2.6.

For every $\alpha>1$ and graph $G$ which is not a complete graph, one has
$\operatorname{Sz}^{\alpha}(G)-W^{\alpha}(G)>\operatorname{Sz}(G)-W(G)\geq 0$.

###### Proof.

Since $\lvert E(G)\rvert\neq\binom{n}{2}$, the sequences $(n_{i})_{i}$ and
$(d_{i})_{i}$ are not equal. Let $t=\sum_{i}n_{i}-\sum_{i}d_{i}\geq 0$. Since
$f(x)=x^{\alpha}$ satisfies $f(0)=0$ and $f(1)=1$ and is a positive, strictly
convex increasing function for $x\geq 0$ and $\alpha>1$, by applying Corollary
2.3 we have $\operatorname{Sz}^{\alpha}(G)>W^{\alpha}(G)+t$. ∎

##  3 Graphs which satisfy the strong conjecture

In Section 2, we noted that Conjecture 1.2 was essentially an inequality for
majorizing sequences instead of an inequality on graphs, once one observes
Proposition 2.4 is true. This cannot be the case for Conjecture 1.1. One can
take the sequences $\vec{x}=\\{625,81,81,16\\}$ and compare with
$\vec{y}=\\{256,256,256,1\\}$, the first one majorizing the second, but $\sum
x_{i}^{\alpha}=\sum y_{i}^{\alpha}$ being true for $0,\frac{1}{4}$ and a
number close to $0.88$.

Fix a connected, non-complete graph $G$ with $n$ vertices and let
$h(\alpha)=\operatorname{Sz}^{\alpha}(G)-W^{\alpha}(G)$. Since $h(\alpha)$ is
a continuous function with $h(0)<0$ and $h(1)\geq 0$, by the intermediate
value theorem there is at least one value of $\alpha$ for which $h(\alpha)=0$
(and at least one such value lies in $(0,1]$); the strong conjecture is
therefore equivalent to $\alpha$ being unique. We therefore give a sufficient
condition, in terms of majorization, for this to be the case.

######  Theorem 3.1.

Let $\alpha$ be a value such that
$\operatorname{Sz}^{\alpha}(G)=W^{\alpha}(G)$ for a non-complete graph $G$. If
the sequence $(n_{i}^{\alpha})_{i}$ does majorize the sequence
$(d_{i}^{\alpha})_{i}$, then $\alpha$ is unique.

###### Proof.

Assume $\beta$ also satisfies $\operatorname{Sz}^{\beta}(G)=W^{\beta}(G)$. Let
$c=\frac{\beta}{\alpha}$; by [10, Proposition 8] we have $\alpha,\beta>0$ and
so $c>0$. Then

$\sum_{i}(n_{i}^{\alpha})^{c}=\sum_{i}(d_{i}^{\alpha})^{c},$ (2)

where we extend the former sum with zero terms to give sequences of equal
length. For $c>1$ the function $f(x)=x^{c}$ is strictly convex, while for
$c<1$ it is strictly concave. By Theorem 2.2 (i), in both cases (2) would not
be true, so this implies $c=1$ and hence $\alpha=\beta.$ ∎

Together with Proposition 2.4, this immediately gives the following.

######  Corollary 3.2.

If $G$ is a non-complete block graph then $G$ satisfies Conjecture 1.1 with
$\alpha_{G}=1$.

As further examples for the the applicability, let us note that either of the
following conditions on $G$ is sufficient (but not necessary) to conclude that
$(n_{i}^{\alpha})_{i}$ majorizes $(d_{i}^{\alpha})_{i}$, where $\alpha$
satisfies $h(\alpha)=0$.

  1. I

There exists some index $j$ such that $n_{i}\geq d_{i}$ if $i\leq j$ and
$n_{i}\leq d_{i}$ if $i>j$.

  2. II

For every $1\leq j\leq m$, it holds that
$\prod_{i=1}^{j}n_{i}\geq\prod_{i=1}^{j}d_{i}$.

To see that II is sufficient, note that it implies that $(\log n_{i})_{1\leq
i\leq m}$ majorizes $(\log d_{i})_{1\leq i\leq m}$, and hence (since
$f(x)=\exp(\alpha x)$ is increasing and convex) that $(n_{i}^{\alpha})_{1\leq
i\leq m}$ majorizes $(d_{i}^{\alpha})_{1\leq i\leq m}$. Since we also have
$\sum_{i=1}^{k}n_{i}^{\alpha}=\operatorname{Sz}^{\alpha}(G)=W^{\alpha}(G)\geq\sum_{i=1}^{k}d_{i}^{\alpha}$
for each $k>m$, we have the required majorization property.

For graphs satisfying I, much more is true.

######  Theorem 3.3.

If $G$ satisfies condition I above, then for every value of $\alpha>0$
satisfying $h(\alpha)\geq h(0)$ we have $h^{\prime}(\alpha)>0$.

This implies the strong conjecture holds for $G$, since there is some smallest
positive value $\alpha_{G}\leq 1$ for which $h(\alpha_{G})=0>h(0)$, and
thereafter the function is strictly increasing so strictly positive. Note that
Theorem 3.3 is best possible, in the sense that we may have $h^{\prime}(0)<0$
(and hence $h^{\prime}(\epsilon)<0$ with $h(\epsilon)$ arbitrarily close to
$h(0)$). For example, this is the case for stars with at least $8$ vertices.

###### Proof.

Set $\tilde{n}_{i}$ to be $1$ if $n_{i}=0$ and $n_{i}$ otherwise. Since
$d_{i}\geq 1$ for each index $i$, condition I still applies with $n_{i}$
replaced by $\tilde{n}_{i}$, and ensures that $\sum_{i\leq
k}(\tilde{n}_{i}^{\alpha}-d_{i}^{\alpha})$, considered as a function of $k$
for any fixed $\alpha>0$, is increasing for $k\leq j$ and decreasing
thereafter. Consequently, $(\tilde{n}_{i}^{\alpha})$ majorizes
$(d_{i}^{\alpha})$ provided

$\sum_{i=1}^{N}\tilde{n}_{i}^{\alpha}\geq\sum_{i=1}^{N}d_{i}^{\alpha},$

i.e. whenever $h(\alpha)+N-e(G)\geq 0$. Since $h(0)=e(G)-N$, this condition
becomes $h(\alpha)\geq h(0)$. Now provided $\alpha>0$ we have

$\displaystyle h^{\prime}(\alpha)$ $\displaystyle=\sum_{i=1}^{N}(\log
n_{i}\cdot n_{i}^{\alpha}-\log d_{i}\cdot d_{i}^{\alpha})$
$\displaystyle=\sum_{i=1}^{N}(\log\tilde{n}_{i}\cdot\tilde{n}_{i}^{\alpha}-\log
d_{i}\cdot d_{i}^{\alpha})$
$\displaystyle=\alpha^{-1}\biggl{(}\sum_{i=1}^{N}f(\tilde{n}_{i}^{\alpha})-\sum_{i=1}^{N}f(d_{i}^{\alpha})\biggr{)},$

where $f(x)=x\log x$ for $x\geq 1$. Since this is a strictly convex,
increasing function, and the two sequences are distinct (the fact that
$\sum_{i}\tilde{n}_{i}>\sum_{i}d_{i}$ implies there is some $i$ with
$\tilde{n}_{i}>d_{i}$), Theorem 2.2 (ii) gives
$\sum_{i=1}^{N}f(\tilde{n}_{i})>\sum_{i=1}^{N}f(d_{i})$, as required. ∎

In particular this implies the strong conjecture holds for several classes of
graphs.

######  Corollary 3.4.

The graph $G$ satisfies Conjecture 1.1 in any of the following cases:

  * •

$G$ is bipartite;

  * •

$G$ is edge-transitive;

  * •

$\operatorname{diam}(G)=2$; or

  * •

$\operatorname{diam}(G)=3$ and $m\leq N/2$.

###### Proof.

If $G$ is bipartite then for each edge $uv$, each vertex is strictly closer to
either $u$ or $v$, since equality would create an odd cycle. Thus
$n_{u}(v)\cdot n_{v}(u)\geq|G|-1\geq d(x,y)$, and I holds with $j=m$.

If $G$ is edge-transitive then every edge is on a diameter, meaning
$n_{i}\geq\operatorname{diam}(G)\geq d_{i}$ for $1\leq i\leq m$.

If $\operatorname{diam}(G)=2$ then $d_{i}\in\\{1,2\\}$ for each $i$. Take $j$
maximal such that $n_{i}\geq 2$. Then $n_{i}\geq d_{i}$ for $i\leq j$, and
$n_{i}\leq d_{i}$ for all $i>j$, as required. Finally, if
$\operatorname{diam}(G)=3$ and $m\leq N/2$ then we have $d_{i}\in\\{2,3\\}$
for each $i\leq m$, and taking $j$ maximal such that $n_{i}\geq 3$ gives the
required property. ∎

Another corollary of Theorem 3.1 is the case when the $n_{i}$ are “on average”
at least equal to the diameter, which can be stated more precisely as follows
with the use of the notion $\mu_{\alpha}$ for the power mean with exponent
$\alpha$, i.e. using $N=\binom{n}{2}$ we have

$\mu_{\alpha}(d_{1},d_{2},\ldots,d_{N})=\sqrt[\alpha]{\frac{\sum_{i=1}^{N}d_{i}^{\alpha}}{N}}.$

######  Corollary 3.5.

Let $\alpha$ be a value such that
$\operatorname{Sz}^{\alpha}(G)=W^{\alpha}(G)$ for a non-complete graph $G$. If

$\mu_{\alpha}(d_{1},d_{2},\ldots,d_{N})\geq\left(\frac{m}{N}\right)^{\frac{1}{\alpha}}\operatorname{diam}(G),$

then this value $\alpha$ is unique.

###### Proof.

By Theorem 3.1 it is sufficient to prove that $(n_{i}^{\alpha})_{i}$ majorizes
$(d_{i}^{\alpha})_{i}$, which is the case if for each $k\leq m$ the first $k$
terms of the first sequence are on average at least equal to the largest term
of the second, namely, $\operatorname{diam}(G)^{\alpha}$. As the sequence is
ordered, it is sufficient to prove this for $k=m$, i.e.

$\displaystyle\sum_{i=1}^{m}n_{i}^{\alpha}\geq
m\operatorname{diam}(G)^{\alpha}$
$\displaystyle\Longleftrightarrow\sum_{i=1}^{N}d_{i}^{\alpha}\geq
m\operatorname{diam}(G)^{\alpha}$
$\displaystyle\Longleftrightarrow\sqrt[\alpha]{\frac{\sum_{i=1}^{N}d_{i}^{\alpha}}{N}}\geq\sqrt[\alpha]{\frac{m}{N}}\operatorname{diam}(G).\qed$

Corollary 3.5 is sufficient to prove Conjecture 1.1 for all graphs lying in
some sparse regime. Intuitively if $N\gg m$, the $n_{i}$ are on average much
larger than the $d_{i}$ and so the majorization property will hold.

######  Theorem 3.6.

Conjecture 1.1 is true for graphs with $m$ edges and $n$ vertices whenever
$m\leq\frac{1}{4}(n^{4/3}-n^{1/3})$.

###### Proof.

By Corollary 3.5 we only need to prove that the inequality

$\mu_{\alpha}:=\mu_{\alpha}(d_{1},d_{2},\ldots,d_{N})\leq\left(\frac{m}{N}\right)^{\frac{1}{\alpha}}\operatorname{diam}(G)$

is impossible. So assume this is the case, i.e. we have
$\operatorname{diam}(G)\geq\left(\frac{N}{m}\right)^{\frac{1}{\alpha}}\mu_{\alpha}\geq(2n^{2/3})^{\frac{1}{\alpha}}\mu_{\alpha}$.
Note that for all edges in the middle of a diameter, the $n_{i}$ are large.

######  Claim 3.7.

Let $e_{1}e_{2}\ldots e_{\operatorname{diam}(G)}$ be the path between two
vertices $x$ and $y$ for which $d(x,y)=\operatorname{diam}(G)$. Then
$n_{e_{j}}\geq\frac{3}{16}\operatorname{diam}(G)^{2}$ when
$\frac{\operatorname{diam}(G)}{4}\leq
j\leq\frac{3\operatorname{diam}(G)}{4}+1.$

###### Proof.

Let $e_{j}=uv$ with $u=e_{j}\cap e_{j-1}$ and $v=e_{j}\cap e_{j+1}$. Then
$N_{u}(e_{j})$ contains at least the $j$ vertices on the path from $x$ to $u$,
and similarly $n_{v}(e_{j})\geq\operatorname{diam}(G)+1-j.$ Hence
$n_{u}(e_{j})n_{v}(e_{j})\geq
j(\operatorname{diam}(G)+1-j)\geq\frac{3}{16}\operatorname{diam}(G)^{2}$. ∎

Taking into account that $\alpha\leq 1$ and $\mu_{\alpha}\geq 1$, this implies

$\displaystyle\sum_{i}n_{i}^{\alpha}$
$\displaystyle\geq\frac{\operatorname{diam}(G)}{2}\left(\frac{3}{16}\operatorname{diam}(G)^{2}\right)^{\alpha}$
$\displaystyle\geq\frac{3}{32}\operatorname{diam}(G)^{3\alpha}$
$\displaystyle\geq\frac{3}{4}n^{2}\mu_{\alpha}^{\alpha}$
$\displaystyle>W^{\alpha}(G).$

This is the desired contradiction, so in the sparse regime Corollary 3.5 does
apply. ∎

As a consequence, Conjecture 1.1 is a.a.s. true for any random graph of the
form $G_{n,p}$ or $G_{n,m}$ (conditional on the graph being connected).

######  Corollary 3.8.

For any value of $m$ or $p$, conjecture 1.1 is a.a.s. true for any random
graph of the form $G_{n,p}$ or $G_{n,m}$ (conditional on the graph being
connected).

###### Proof.

By Theorem 3.6 the result is true in the sparse case, so we only have to
consider the dense case where $m>\frac{1}{4}(n^{4/3}-n^{1/3})$. By a result of
Klee and Larman [14], the diameter is a.a.s. at most $3$, and when
$m\geq\frac{N}{3}$ it is a.a.s. equal to $2$. Therefore Corollary 3.4 applies
in this regime. Finally, the result for $G(n,p)$ follows by conditioning on
the number of edges. ∎

##  4 Counterexamples to the strong conjecture

Let $G_{k,\ell}$ be a graph constructed as follows. Start with a clique
$K_{k}$ and remove a $k$-cycle $v_{1}v_{2}v_{3}\ldots v_{k}$ (a Hamiltonian
path) from the clique. Next connect all its vertices with one endvertex
$u_{1}$ of a path $u_{1}u_{2}\ldots u_{\ell+1}$ of length $\ell$ (i.e. of
order $\ell+1$). See Figure 1 for a small example.

Figure 1: The graph $G_{k,\ell}$ for $k=8$ and $\ell=5$.

Now we compute $W^{\alpha}(G_{k,\ell})$ and
$\operatorname{Sz}^{\alpha}(G_{k,\ell})$ (assuming $k\geq 6$).

###  4.1 Computation of $W^{\alpha}(G_{k,\ell})$ and
$\operatorname{Sz}^{\alpha}(G_{k,\ell})$

The number of edges of the graph equals $\binom{k}{2}+\ell$. There are $k$
pairs of vertices which are at distance $2$ in the clique. For each
$i\leq\ell+1$, there are $k$ pairs with one vertex from the clique together
with $u_{i}$ which are at distance $i$ from each other. There are also
$\ell+1-i$ pairs of vertices, both belonging to the path, which are at
distance $i$ from each other; these are $(u_{j},u_{j+i})$ for $1\leq
j\leq\ell+1-i.$

This implies that

$W^{\alpha}(G_{k,\ell})=\binom{k}{2}+\ell+(2k+\ell-1)2^{\alpha}+\sum_{i=3}^{\ell+1}(k+\ell+1-i)i^{\alpha}.$

Next, we compute $\operatorname{Sz}^{\alpha}(G_{k,\ell}).$

For every pair of vertices in the clique of the form $(v_{i},v_{i+2})$
(indices modulo $k$), we have $N_{v_{i}}(v_{i+2})=\\{v_{i},v_{i+3}\\}$ and
$N_{v_{i+2}}(v_{i})=\\{v_{i-1},v_{i+2}\\}$. So the corresponding value for
$n_{v_{i}v_{i+2}}=4$; there are $k$ such edges.

For every edge $v_{i}v_{j}$ with $\lvert i-j\rvert\not\equiv 2\pmod{k}$ we
have $N_{v_{i}}(v_{j})=\\{v_{i},v_{j-1},v_{j+1}\\}$ and
$N_{v_{j}}(v_{i})=\\{v_{j},v_{i-1},v_{i+1}\\},$ so $n_{v_{i}v_{j}}=9$. There
are $\binom{k}{2}-2k$ edges of this form.

For every edge $u_{1}v_{i}$, we have $N_{v_{i}}(u_{1}))=\\{v_{i}\\}$ and
$N_{u_{1}}(v_{i})$ contains all vertices from the path $P_{\ell}$, as well as
$v_{i-1}$ and $v_{i+1}$. So we have $k$ edges here for which
$n_{v_{i}u_{1}}=\ell+3.$

For every edge of the form $u_{i}u_{i+1}$ we have
$n_{u_{i}u_{i+1}}=(k+i)(\ell+1-i).$

Taking everything into account, we get

$\operatorname{Sz}^{\alpha}(G_{k,\ell})=k4^{\alpha}+\left(\binom{k}{2}-2k\right)9^{\alpha}+k(\ell+3)^{\alpha}+\sum_{i=1}^{\ell}((k+i)(\ell+1-i))^{\alpha}.$

###  4.2 Some explicit counterexamples

There are multiple graphs of the form $G_{k,\ell}$ which are counterexamples.
All we need is that $k$ is reasonably large, and then there are some
corresponding $\ell$ giving three values of $\alpha$ for which
$\operatorname{Sz}^{\alpha}(G_{k,\ell})-W^{\alpha}(G_{k,\ell})=0$. One example
is $k=520$ and $\ell=82$; part of the function $h(\alpha)$ showing that the
conjecture does not hold is plotted in Figure 2.

Figure 2: The function $h(\alpha)$ plotted for $G_{520,82}$.

We can actually prove that there are infinitely many counterexamples. Since
our construction is not a block graph, we know that $h(0)<0$ and $h(1)>0$. For
$k$ tending to infinity and $0<\epsilon<0.25$ fixed, $0\leq\alpha\leq 1$ and
$k^{0.5+\epsilon}<\ell<k^{1-\epsilon}$, we note that

$W^{\alpha}(G_{k,\ell})=\binom{k}{2}\left(1+O\left(\frac{1}{k}\right)\right)+k\left(1+O\left(\frac{1}{k^{\epsilon}}\right)\right)\sum_{i=3}^{\ell+1}i^{\alpha}\sim\binom{k}{2}+k\frac{\ell^{\alpha+1}}{\alpha+1}$

and

$\operatorname{Sz}^{\alpha}(G_{k,\ell})=\binom{k}{2}\left(1+O\left(\frac{1}{k^{\epsilon}}\right)\right)9^{\alpha}+k^{\alpha}\left(1+O\left(\frac{1}{k^{\epsilon}}\right)\right)\sum_{i=1}^{\ell}i^{\alpha}\sim\binom{k}{2}9^{\alpha}+k^{\alpha}\frac{\ell^{\alpha+1}}{\alpha+1}.$

This implies that $h(\epsilon)\sim\binom{k}{2}(9^{\epsilon}-1)>0$ and
$h(1-\epsilon)\sim-k\frac{\ell^{2-\epsilon}}{2-\epsilon}<0$. By applying the
intermediate value theorem on $h(0)<0,h(\epsilon)>0,h(1-\epsilon)<0$ and
$h(1)>0$ we conclude that there are at least $3$ values $\alpha$ for which
$h(\alpha)=0$.

It is not hard to see that the same analysis gives the same conclusion when a
matching instead of a cycle (for $k$ even) was removed from the $K_{k}$, or
any $r$-regular graph for fixed $r$ (and $k$ sufficiently large).

##  5 Conclusion

We have resolved both conjectures of [10]. We proved the weaker Conjecture 1.2
by showing majorization of the sequence $(n_{i})_{i}$ with respect to
$(d_{i})_{i}$. The stronger Conjecture 1.1 is not true in general, as there
are (infinitely many) sporadic counterexamples such as $G_{520,82}$, as
explained in Section 4.

Nevertheless, it is true in many important cases as proven in this note. The
conjecture is true for example for the following families:

  * •

block graphs;

  * •

graphs with diameter $2$;

  * •

any $n$-vertex graph with at most $\frac{1}{2n^{2/3}}\binom{n}{2}$ edges;

  * •

bipartite graphs;

  * •

edge-transitive graphs; and

  * •

the random graphs $G(n,p)$ and $G(n,m)$ a.a.s. (for the entire range of $p$ or
$m$).

## References

  * [1] B. Bollobás and P. Erdős.  Graphs of extremal weights.  Ars Combin., 50:225–233, 1998.
  * [2] A. Dobrynin, R. Entringer, and I. Gutman.  Wiener index of trees: theory and applications.  Acta Appl. Math., 66(3):211–249, 2001.
  * [3] A. Dobrynin and I. Gutman.  On a graph invariant related to the sum of all distances in a graph.  Publ. Inst. Math. (Beograd) (N.S.), 56(70):18–22, 1994.
  * [4] R. C. Entringer, D. E. Jackson, and D. A. Snyder.  Distance in graphs.  Czechoslovak Math. J., 26(101)(2):283–296, 1976.
  * [5] I. Gutman.  A formula for the Wiener number of trees and its extension to graphs containing cycles.  Graph Theory Notes N. Y., 27:9–15, 1994.
  * [6] I. Gutman, S. Klavžar, and B. Mohar, editors.  Fifty years of the Wiener index.  A. Kerber, Bayreuth, 1997.  Papers in celebration of the 50th anniversary of the appearance of “Structural determination of paraffin boiling points” [J. Amer. Chem. Soc. 69 (1947), no. 1, 17–20] by Harold Wiener, Match No. 35 (1997) (1997).
  * [7] I. Gutman, B. Ruščić, N. Trinajstić, and C. F. Wilcox.  Graph theory and molecular orbitals. XII. Acyclic polyenes.  J. Chem. Phys., 62:3399–3405, 1975.
  * [8] I. Gutman and N. Trinajstić.  Graph theory and molecular orbitals. Total $\pi$-electron energy of alternant hydrocarbons.  Chem. Phys. Lett., 17:535–538, 1972.
  * [9] H. Hosoya.  Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons.  Bull. Chem. Soc. Jpn., 44(9), 1971.
  * [10] K. Hriňáková, M. Knor, and R. Škrekovski.  An inequality between variable Wiener index and variable Szeged index.  Appl. Math. Comput., 362:124557, 6, 2019.
  * [11] J. Karamata.  Sur une inégalité rélative aux fonctions convexes.  Publ. Math. Univ. Belgrade, 1:145–148, 1932.
  * [12] S. Klavžar.  On the canonical metric representation, average distance, and partial Hamming graphs.  European J. Combin., 27(1):68–73, 2006.
  * [13] S. Klavžar, A. Rajapakse, and I. Gutman.  The Szeged and the Wiener index of graphs.  Appl. Math. Lett., 9(5):45–49, 1996.
  * [14] V. Klee and D. Larman.  Diameters of random graphs.  Canadian J. Math., 33(3):618–640, 1981.
  * [15] A. Miličević and S. Nikolić.  On variable Zagreb indices.  Croat. Chem. Acta, 77:97–101, 2004.
  * [16] M. J. Nadjafi-Arani, H. Khodashenas, and A. R. Ashrafi.  On the differences between Szeged and Wiener indices of graphs.  Discrete Math., 311(20):2233–2237, 2011.
  * [17] J. E. Pečarić, F. Proschan, and Y. L. Tong.  Convex functions, partial orderings, and statistical applications, volume 187 of Mathematics in Science and Engineering.  Academic Press, Inc., Boston, MA, 1992.
  * [18] M. Randić.  Characterization of molecular branching.  J. Amer. Chem. Soc., 97(23):6609–6615.
  * [19] D. H. Rouvray.  The value of topological indices in chemistry.  MATCH Commun. Math. Comput. Chem., 1:125–134, 1975.
  * [20] H. Wiener.  Structural determination of paraffin boiling points.  J. Amer. Chem. Soc., 69(1):17–20, 1947.
  * [21] H. Wiener.  Relation of the physical properties of the isomeric alkanes to molecular structure. Surface tension, specific dispersion, and critical solution temperature in aniline.  J. Phys. Colloid Chem., 52(6):1082–1089, 1948.
  * [22] B. Zelinka.  Medians and peripherians of trees.  Arch. Math. (Brno), 4:87–95, 1968.