# Gaussian-boson-sampling-enhanced dense subgraph finding shows
limited advantage over efficient classical algorithms

Naomi R. Solomons<EMAIL_ADDRESS>Quantum Engineering Centre for
Doctoral Training, Centre for Nanoscience and Quantum Information, University
of Bristol, Bristol BS8 1FD, United Kingdom  Quantum Engineering Technology
Labs, H. H. Wills Physics Laboratory and Department of Electrical and
Electronic Engineering, University of Bristol, Bristol BS8 1UB, United Kingdom
Oliver F. Thomas  Duality Quantum Photonics, 6 Lower Park Row, Bristol, United
Kingdom, BS1 5BJ  Dara P. S. McCutcheon  Quantum Engineering Technology Labs,
H. H. Wills Physics Laboratory and Department of Electrical and Electronic
Engineering, University of Bristol, Bristol BS8 1UB, United Kingdom  Duality
Quantum Photonics, 6 Lower Park Row, Bristol, United Kingdom, BS1 5BJ

###### Abstract

Recent claims of achieving exponential quantum advantage have attracted
attention to Gaussian boson sampling (GBS), a potential application of which
is dense subgraph finding. We investigate the effects of sources of error
including loss and spectral impurity on GBS applied to dense subgraph finding
algorithms. We find that the effectiveness of these algorithms is remarkably
robust to errors, to such an extent that there exist efficient classical
algorithms that can simulate the underlying GBS. These results imply that the
speedup of GBS-based algorithms for the dense subgraph problem over classical
approaches is at most polynomial, though this could be achieved on a quantum
device with dramatically less stringent requirements on loss and photon purity
than general GBS.

##  I Introduction

Gaussian boson sampling (GBS) is a non-universal model of quantum computation
which samples from the photon number distribution of Gaussian squeezed states
passed through a passive linear interferometer Hamilton  _et al._ (2017).
Unlike universal quantum computers, GBS can be realised by currently available
quantum devices at a scale which is not efficiently simulable by a classical
computer, and hence has been the subject of early claims of quantum advantage
Lund  _et al._ (2017); Zhong  _et al._ (2020); Madsen  _et al._ (2022),
challenging the extended Church-Turing thesis Shchesnovich (2014). Recent
proposals have suggested that GBS can be used for a number of different
applications Bromley  _et al._ (2020), several of which involve examining
properties of graphs. These include dense subgraph identification, a problem
which occurs in computing Kumar  _et al._ (1999), computational biology Hu
_et al._ (2005); Habibi  _et al._ (2010), and finance Arora  _et al._ (2010),
as well as being used to predict molecular docking configurations Banchi  _et
al._ (2020). Given the conjectured exponential complexity of simulating GBS,
there is the potential that GBS enables genuine useful quantum computing
applications offering exponential speedup.

However, current and near-term GBS experiments are likely to be significantly
affected by error, having an impact on the effectiveness of GBS-based
algorithms and the corresponding extent of any speedup over classical
approaches. For example, in the presence of sufficient photon
distinguishability and loss, GBS experiments can be efficiently classically
simulated Renema (2020); Qi  _et al._ (2020). On the other hand, accurately
modelling imperfect photon purity requires the simulation of multiple spectral
modes increasing the simulation complexity, and the impact of spectral
impurity is subsequently not well understood in the context of large scale
GBS.

This work uses methods for simulating GBS as described in Thomas  _et al._
(2021), applied to the stochastic densest $k$-subgraph (DkS) finding
algorithms in Bromley  _et al._ (2020); Arrazola and Bromley (2018). We
examine how effective GBS experiments are for this application, when including
the effects of spectrally impure sources and loss. The densest $k$-subgraph
problem is known to be NP-hard in general, and as such an efficient quantum
algorithm is unlikely (as it is widely thought that NP is not in BQP, the
class of problems solvable by a quantum computer, so NP-hard problems cannot
be efficiently solved by any quantum computer, let alone GBS). Nevertheless it
is important to know how errors will affect quantum approaches, and to
elucidate the origin of any speedups offered, polynomial or otherwise. We show
that the DkS finding algorithms are extremely robust to these sources of
errors, even in regimes that may be efficient to simulate classically. These
results suggest that GBS applied to the DkS problem is likely to offer only a
polynomial speedup over classical computing approaches at best, but that this
advantage does not impose challenging hardware requirements on loss and photon
purity, and could be realised more readily than a general GBS device. Given
the level or errors that can be tolerated for these algorithms, we speculate
whether any advantage offered on quantum devices should really be considered
‘quantum’, or if ‘analogue’ or ‘optical’ may be more fitting terminology.

##  II Background

###  II.1 Gaussian boson sampling

A Gaussian state is defined as a quantum state in which the Wigner function
$\mathcal{W}(\textbf{p},\textbf{q})$ is Gaussian, and thus an $m$-mode
Gaussian state can be completely defined by a $2m\times 2m$ covariance matrix
$\bm{\sigma}$, and a $2m$ displacement vector $\vec{D}$ Adesso  _et al._
(2014). In the following, we will assume $\vec{D}=\vec{0}$.

Gaussian boson sampling consists of measurements in the Fock basis of an input
Gaussian squeezed state passed through an interferometer. The measurement
probabilities for photon number resolving (PNR) detectors are given by
Hamilton  _et al._ (2017):

$P(S;\\{s_{i}\\})=\frac{2^{N}}{s_{1}!s_{2}!...s_{n}!\sqrt{|\sigma_{Q}|}}\text{Haf}(\mathcal{A}_{S}),$
(1)

in which $S$ is the subset of modes involved in the detection outcome, $s_{i}$
is the number of photons measured in mode $i$, $N=\sum_{i}s_{i}$, and
$\sigma_{Q}=\sigma+\mathds{1}$. Given the matrix
$\mathcal{A}=(X\otimes\mathds{1})(\mathds{1}-2\sigma_{Q}^{-1})$, we construct
$\mathcal{A}_{S}$ by repeating the $i$’th row and column of $\mathcal{A}$
according to $s_{i}$.

The difficulty of classically simulating GBS is a result of the difficulty of
calculating the matrix hafnian: $\text{Haf}(A)=\sum_{\mu\in
M}\left(\prod_{k=1}^{|S|}A_{\mu_{2k-1},\mu_{2k}}\right)$, where $M$ is the set
of perfect matchings of $S$, the different ways of ‘pairing’ the indices
(every permutation in which $\mu_{2k}<\mu_{2(k+1)}$ and
$\mu_{2k}<\mu_{2k+1}$). Each measurement carried out in a GBS experiment draws
a sample from the distribution described by Eq. 1. Generating samples
according to this distribution by direct calculation is $\\#$P-hard Deshpande
_et al._ (2022). In the ideal case, the best algorithm for simulating GBS
scales with the number of modes $m$ and the measured number of photons $N$ as
$O(mN^{3}2^{N/2})$ Quesada  _et al._ (2022). The complexity of drawing samples
from an experimental apparatus is linear in the number of samples, but
alongside the difficulties of physically constructing the device, there is the
initial computational overhead of calculating the correct interferometer
settings to produce the desired output. Matrix decompositions, e.g. Williamson
and Bloch-Messiah, are needed to find the transformations to generate the
correct state; these generally require $O(m^{3})$ time in practice Vasudevan
and Ramakrishna (2017).

###  II.2 Mapping graphs to Gaussian states

A graph $G$ is defined by a collection of vertices $V$ and connecting edges
$E$, and is characterised by an adjacency matrix $A$. Here we restrict
ourselves to equal-weight, undirected graphs, although all graphs can be
represented as Gaussian states Walschaers  _et al._ (2018). To find this state
we use the procedure defined in Ref. Bromley  _et al._ (2020). Firstly, the
adjacency matrix $A$ is diagonalised find the eigenvalues $\\{\lambda\\}$.
Next we pick the scaling parameter $c$ such that $c<\lambda_{\max}^{-1}$. We
then construct $\mathcal{A}=c(A\oplus A)$, and the covariance matrix can be
found using

$\bm{\sigma}=2(\mathds{1}-X\mathcal{A})^{-1}-\mathds{1,}\qquad\mathrm{with}\qquad
X=\begin{pmatrix}0&\mathds{1}\\\ \mathds{1}&0\end{pmatrix}.$ (2)

This means that the probability of sampled outcomes will be proportional to
$|\text{Haf}(A)|^{2}$ (as $\text{Haf}(A\oplus A)=|\text{Haf}(A)|^{2}$). The
scaling parameter ($c$) ensures $\bm{\sigma}$ corresponds to physical
squeezing values, and can be chosen to optimise the photon number distribution
Banchi  _et al._ (2020). In principle the expected photon number can be
arbitrarily high, but in practice this is limited by the amount of squeezing
possible. The largest eigenvalue of the adjacency matrix is bounded above by
the largest vertex degree in the graph, hence more well-connected graphs are
likely to require greater squeezing levels Minc (1974).

The algorithms described in the next section are intended for use in the
collision-free regime, which means that any outcomes containing multiple
photons in one mode have negligible probability and can be ignored. For this
reason we consider the use of threshold detectors which do not distinguish
between photon numbers greater than zero. However, higher values of $c$, which
result in more collisions, tend to favour more samples being drawn in the
preferred photon number or click subspace for D$k$S, and hence improve the
efficiency of the algorithm. As the size of the graphs increases, the
probability of collisions decreases, hence allowing data collected in this
work to use higher values of $c$.

###  II.3 Dense subgraph identification

We will consider densest $k$-subgraph identification, the problem of finding
the subgraph of $k$ vertices with the largest density within the input graph
$G$. The density of $G$ is given by:
$\rho(G)=\frac{2\absolutevalue{E(G)}}{\absolutevalue{V(G)}(\absolutevalue{V(G)}-1)},$
in which $\absolutevalue{V(G)}$ and $\absolutevalue{E(G)}$ represent the
number of vertices and edges in the graph, respectively. The maximum possible
density of a graph is therefore $1$, for a fully connected graph (a clique).
The D$k$S problem is NP-hard Bhaskara  _et al._ (2010), although solutions to
variations on this problem can be found in polynomial time Gallo  _et al._
(1989); Tsourakakis (2015), as can approximate solutions Feige  _et al._
(2001).

Consider a GBS experiment, where the Gaussian state leaving the interferometer
has a covariance matrix as defined in Eq. 2 for some graph $G$. We can then
associate subsets $S$ of output modes, corresponding to measurement outcomes,
to subgraphs of $G$, where the modes in $S$ correspond to the vertices in the
subgraph. As shown in Arrazola and Bromley (2018), the number of perfect
matchings in the graph, and hence the size of the hafnian of the adjacency
matrix, is strongly correlated with the number of edges in a graph, and hence
more dense subgraphs are the most likely sampling results. GBS can therefore
used to seed algorithms that identify the densest subgraphs.

##  III Methods

###  III.1 Boson sampling generated subgraphs

Different classical and quantum-enhanced algorithms exist for the DkS problem.
In this work, we focus on the simplest approach, where the classical case
involves sampling from the uniform distribution of $k$-vertex subgraphs, and
the quantum-enhanced case takes samples using GBS and retains only those
subgraphs of the correct size (the random search algorithm in Arrazola and
Bromley (2018)), using these to select subgraphs. We tune the scaling
parameter $c$ to maximise the probability of click patterns of the correct
size. Our approach can therefore be considered a best-case scenario for the
GBS algorithm, where no overhead in required number of samples is incurred to
acquire $k$-vertex subgraphs. In the Supplementary Material we explore the
performance of the base (photon number varying) GBS algorithm, and also
compare to the performance of simulated annealing algorithms Arrazola and
Bromley (2018). We use as a benchmark a deterministic classical algorithm,
consisting of iteratively removing the lowest-degree vertex Asahiro  _et al._
(2000), which does not always find the densest subgraph, but is guaranteed to
find one of a density within a reasonable approximation ratio.

Our main text focuses on one representative, randomly generated graph, with
further examples (showing qualitatively similar results) considered in the
Supplementary Material. To create the graphs in this work, we use the Erdős-
Rényi form Erdős  _et al._ (1959) for generating a random graph $G(M,\rho)$,
of size $M$ with density $\rho$, as described in the Supplementary Material.
The quantum Gaussian optics emulator used to model outcome statistics is
available online Duality Quantum Photonics .

###  III.2 Modelling spectral impurities

We introduce a new method for inserting internal degrees of freedom into a
Gaussian state which represents a specific graph. Our method is general enough
to work for any physical states, and can be thought of as replacing the
idealised single (spectral) mode squeezers used to generate the state with
more physical sources which have imperfections. The procedure to substitute in
imperfect sources is as follows:

  1. 1.

Construct a graph $G$ with adjacency matrix $A$.

  2. 2.

Choose a scaling value, $c$, and construct a quantum state, $\bm{\sigma}$,
from the graph, according to Eq. 2.

  3. 3.

Perform the Williamson decomposition to find the symplectic transformation
that generates the state $\bm{\sigma}=\bm{M}\mathds{1}\bm{M}^{\dagger}$,
$\bm{M}=\bm{\sigma}^{1/2}$ (for a pure state).

  4. 4.

Perform the Bloch-Messiah decomposition on the symplectic matrix to get the
unitaries and single mode squeezers,
$\bm{M}=\bm{U}\bm{M}^{D}\bm{V}^{\dagger}$.

  5. 5.

Replace the unitaries $\bm{U}$ and $\bm{V}$ with the full sized versions
including spectral modes, $\mathcal{U}=\bm{U}\otimes\mathds{1}_{N_{F}}$,
$\mathcal{V}^{\dagger}=\bm{V}^{\dagger}\otimes\mathds{1}_{N_{F}}$ (in which
$N_{F}$ is the number of spectral modes).

  6. 6.

Replace the set of single mode squeezers with a set of single spatial mode but
multiple spectral mode squeezers $\bm{M}^{D}\mapsto\mathcal{M}^{D}$. These
multiple spectral mode squeezers are normalised to the same amount of
squeezing as the single spectral mode. Detectors are used that trace over the
spectral modes, i.e. non-frequency resolving detectors.

  7. 7.

The multimode state can then be constructed using
$\mathbb{\bm{\sigma}}=\mathcal{M}\mathcal{M}^{\dagger}$, where
$\mathcal{M}=\mathcal{U}\mathcal{M}^{D}\mathcal{V}^{\dagger}$. To measure
photons in the multimode formalism, we follow Thomas  _et al._ (2021).

In order to characterise the sources, we first find the non-zero Schmidt
coefficients. To do this, we pick a set of basis functions, typically the
Hermite polynomials for integrated optics, although any complete set of
normalised functions is suitable. We then construct the vector of singular
values $\\{S\\}$, using a set of coefficients, $X=\\{x_{i}=s_{i}^{2}\\}$.
Remarkably, this allows a large number of geometric type distributions of the
set of $X$, which can be parameterised by only two numbers – here we use the
labels $l$, $b$. We define the set $X$ as
$X_{l,b}=\\{x_{1}\\}\cup\\{x_{i}=k_{l,b}(i)(1-x_{1}),2\leq i\leq l\\}\,,$ so
that by construction the normalisation condition on the values $k_{l,b}(i)$ is
satisfied, $\sum_{i}k_{l,b}(i)=1$. One useful form for the set $k_{l,b}$ is
the geometric scaling, $k_{l,b}(i)=b^{l-i}/(\sum_{j=1}^{l-1}b^{j-1}).$ Here
$l$ is the number of non-zero Schmidt coefficients and $b$ is the base which
sets the factor for the geometric scaling between the elements $x_{i}$. More
information on this procedure is given in the Supplementary Information.

##  IV Results

The first graph we consider has $n=24$ vertices and a density of 0.362. The
Supplementary Material also considers a graph with density 0.196, and a
modified version containing a clique. We run the algorithm searching for the
densest subgraph of $k=8$ vertices, which has density 0.714. Fig. 1 compares
the performance of the classical (purple) and quantum-enhanced random sampling
algorithms in the error free case (green). Shown also by the grey grid line is
the result of the deterministic classical algorithm. The number of steps on
the x-axis refers to the number of random subgraphs drawn from the target
$k$-click subspace, with the final density being the maximum. The results are
averaged over 1000 iterations. We can see that the quantum-enhanced algorithms
outperform the classical algorithms, similarly to Arrazola and Bromley (2018).
The deterministic algorithm performs well, but is quickly overtaken by the
quantum-enhanced algorithms. Shown also is the GBS algorithm including
different loss rates; Fig. 1 (top) as indicated. We do this by (after
constructing the multi-spectral mode state) applying uniform loss to all
modes. We also vary the spectral purity of the sources used in the GBS
emulation using the method described above, shown in Fig. 1 (bottom).
Interestingly, the quantum advantage offered by the GBS algorithm appears to
be remarkably robust to loss and spectral impurity errors.

Figure 1: Performance of the classical (purple) and quantum-enhanced random
sampling algorithm (green), in the presence of varying amounts of loss (top)
and spectral impurity (bottom) as indicated. The grey line shows the
performance of the deterministic classical algorithm Asahiro  _et al._ (2000).
The final maximum (density) of sampled subgraphs is shown as a function of
sample batch size.

In order to see how the quantum advantage scales, we now investigate graphs of
different sizes, all generated using the Erdős-Rényi form Erdős  _et al._
(1959) with $\rho=0.4$. We draw samples corresponding to $k$-vertex subgraphs
where $k$ is the closest integer to $\sqrt{n}$, either from the uniform
distribution (for the classical case) or from a simulated GBS device. Fig. 2
compares the average densities of these subgraphs after drawing 1000 samples,
including with loss and spectral impurity. In the bottom plot, showing the
difference between the quantum samples drawn and the classical samples, we see
that the extent of the quantum advantage here appears to decrease with
increasing graph size with a potential plateau approached above $50$.

##  V Discussion

It is clear that the quantum-enhanced D$k$S algorithms are resilient against
the forms of error considered. A considerable speedup (compared to the
classical case) is shown by the examples with high levels of error (up to 60%
loss and sources with purity 0.4), with little difference between the
effectiveness of these and the simulations with no error. This can in part be
understood from Fig. 3, which shows the outcome probability distributions
within the 8-click space (the samples used in Fig. 1) in the presence of loss
and spectral impurity. Although some subtle differences can be seen in the
distributions, the overall structure appears unchanged – namely, that samples
with the high probabilities retain high probabilities. This gives some
intuition as to why the algorithms continue to select dense subgraphs in the
presence of errors.

Figure 2: Top: Average density of sampled $\sqrt{n}$-subgraphs as a function
of graph size $n$ with initial density $0.4$. The variance is shown (shaded
region) for the classical and quantum case with no error. Bottom: difference
between the average density of sampled subgraphs, in the quantum case,
compared to the classical case.

It is worth noting that we have considered the performance of the quantum-
enhanced algorithm when samples have been selected from the appropriate photon
number subspace. This reflects the fact that in realistic implementations,
samples drawn outside of this subspace can be manipulated into graphs of the
correct side, with minimal overheads (for example, by removing low degree
vertices, adding vertices by combining graphs from different samples). As such
the postselected implementation presented here effectively represents the
best-case scenario for the quantum algorithm. Without this postselection the
speedup remains but is reduced as more samples need to be drawn. This is
considered further in the Supplementary Material.

When varying the graph size $n$, we see that the same pattern holds, in which
simulations with loss and spectrally impure sources perform well. It also
seems that the speedup of the quantum algorithm is smaller with larger $n$,
and indicates a potential plateau at larger graph sizes. In addition, it can
be seen that low spectral impurity has less of an impact than increased levels
of loss. The variance of subgraph density in these samples is, in general,
lower than that for the case with loss. This suggests that the experiment in
this case may occasionally not be able to sample the densest subgraph, but
also avoids sampling very low density subgraphs.

Figure 3: Probability distribution within the 8-click subspace, in the ideal
case (purple) and with loss (green, top) and spectrally impure sources (green,
bottom).

GBS with a high level of photon distinguishability is known to be efficient to
simulate classically Renema (2020). Similarly, increasing the spectral
impurity approaches the limit of simulating thermal states, which are easier
to simulate Rahimi-Keshari  _et al._ (2015), and hence reduces the usefulness
of quantum resources. For a sufficient level of loss, GBS permits an efficient
classical simulation Qi  _et al._ (2020). Following the analysis of Ref. Qi
_et al._ (2020), with loss of at least 43.7%, the GBS simulated here is
efficiently classically simulable. In the present case as loss is increased,
we increase the squeezing to compensate in order to maximise the likelihood of
$k$-click events (as described in the Supplementary Material). This increases
the loss threshold above which the GBS is classically simulable, up to a
maximum of 47.3% for these parameters. As such, although the algorithms appear
robust to errors, the level of errors means that efficient classical
algorithms exist which perform the same underlying sampling task. We conclude
that the apparent quantum advantage of GBS applied to the DkS is at best
polynomial in run time.

The levels of loss and impurity tolerable suggest that these algorithms are
not fully exploiting truly quantum mechanical effects such as quantum
interference and entanglement. We note that it is not straightforward to
engineer a graph problem requiring such phenomena since not all Gaussian
states necessarily correspond to graphs in the manner described, i.e.
adjacency matrices with real entries. Our results suggest future work could
examine whether our findings are due to the structure of Gaussian states
described by graphs, and if, for example, this is due to the limited treewidth
of randomly produced graphs Oh  _et al._ (2022). Our investigations have found
no examples of graphs corresponding to Gaussian states that are not robust to
loss and impurity errors. The code used here is open source and can be run
with a variety of different graph types Duality Quantum Photonics .

##  VI Conclusion

We have used new methods of simulating Gaussian boson sampling to show that
quantum-enhanced dense subgraph finding is particularly robust to spectral
error and loss. This suggests that efficient classical methods exist that can
implement the same algorithm as the quantum device, albeit with a potential
polynomial overhead from simulating drawing samples. The implication is that a
quantum device with modest requirements on loss and spectral purity could be
used for the dense subgraph problem with little loss in performance, though
this in itself raises questions as to whether the advantage gained can be said
to be ‘quantum’ in the sense that it is generally understood when applied to
algorithms. This work has focused on studying Erdős-Rényi random graphs, and
further work could be done to generalise these results to different graphs
with potentially more elaborate structures. Furthermore, more study is needed
into the Gaussian states generated from graphs, and whether the conclusions
drawn here apply to other applications of GBS. These results favor ongoing
speculation as to the possibility of efficiently simulating GBS within certain
regimes, in particular whether it is possible to efficiently calculate
hafnians of matrices with all positive values.

##  VII Acknowledgements

We would like to thank Patrick Yard and Anthony Laing for feedback on the
manuscript, and Ryan Mann for useful discussions. N.R.S. is supported by the
Quantum Engineering Centre for Doctoral Training, EPSRC grant EP/SO23607/1.

## References

  * Hamilton  _et al._ (2017) C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, Physical review letters 119, 170501 (2017).
  * Lund  _et al._ (2017) A. Lund, M. J. Bremner, and T. Ralph, npj Quantum Information 3, 1 (2017).
  * Zhong  _et al._ (2020) H.-S. Zhong, H. Wang, Y.-H. Deng, M.-C. Chen, L.-C. Peng, Y.-H. Luo, J. Qin, D. Wu, X. Ding, Y. Hu, _et al._ , Science 370, 1460 (2020).
  * Madsen  _et al._ (2022) L. S. Madsen, F. Laudenbach, M. F. Askarani, F. Rortais, T. Vincent, J. F. Bulmer, F. M. Miatto, L. Neuhaus, L. G. Helt, M. J. Collins, _et al._ , Nature 606, 75 (2022).
  * Shchesnovich (2014) V. Shchesnovich, arXiv preprint arXiv:1403.4459 (2014).
  * Bromley  _et al._ (2020) T. R. Bromley, J. M. Arrazola, S. Jahangiri, J. Izaac, N. Quesada, A. D. Gran, M. Schuld, J. Swinarton, Z. Zabaneh, and N. Killoran, Quantum Science and Technology 5, 034010 (2020).
  * Kumar  _et al._ (1999) R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins, Computer networks 31, 1481 (1999).
  * Hu  _et al._ (2005) H. Hu, X. Yan, Y. Huang, J. Han, and X. J. Zhou, Bioinformatics 21, i213 (2005).
  * Habibi  _et al._ (2010) M. Habibi, C. Eslahchi, and L. Wong, BMC systems biology 4, 1 (2010).
  * Arora  _et al._ (2010) S. Arora, B. Barak, M. Brunnermeier, and R. Ge, in  _ICS_ (2010) pp. 49–65.
  * Banchi  _et al._ (2020) L. Banchi, M. Fingerhuth, T. Babej, C. Ing, and J. M. Arrazola, Science advances 6, eaax1950 (2020).
  * Renema (2020) J. J. Renema, Physical Review A 101, 063840 (2020).
  * Qi  _et al._ (2020) H. Qi, D. J. Brod, N. Quesada, and R. García-Patrón, Physical review letters 124, 100502 (2020).
  * Thomas  _et al._ (2021) O. F. Thomas, W. McCutcheon, and D. P. S. McCutcheon, APL Photonics 6, 040801 (2021).
  * Arrazola and Bromley (2018) J. M. Arrazola and T. R. Bromley, Physical review letters 121, 030503 (2018).
  * Adesso  _et al._ (2014) G. Adesso, S. Ragy, and A. R. Lee, Open Systems & Information Dynamics 21, 1440001 (2014).
  * Deshpande  _et al._ (2022) A. Deshpande, A. Mehta, T. Vincent, N. Quesada, M. Hinsche, M. Ioannou, L. Madsen, J. Lavoie, H. Qi, J. Eisert, _et al._ , Science advances 8, eabi7894 (2022).
  * Quesada  _et al._ (2022) N. Quesada, R. S. Chadwick, B. A. Bell, J. M. Arrazola, T. Vincent, H. Qi, R. García, _et al._ , PRX Quantum 3, 010306 (2022).
  * Vasudevan and Ramakrishna (2017) V. Vasudevan and M. Ramakrishna, arXiv preprint arXiv:1710.02812 (2017).
  * Walschaers  _et al._ (2018) M. Walschaers, S. Sarkar, V. Parigi, and N. Treps, Physical review letters 121, 220501 (2018).
  * Minc (1974) H. Minc,  _Nonnegative Matrices_ (Technion-Israel Institute of Technology, Department of Mathematics, 1974).
  * Bhaskara  _et al._ (2010) A. Bhaskara, M. Charikar, E. Chlamtac, U. Feige, and A. Vijayaraghavan, in  _Proceedings of the forty-second ACM symposium on Theory of computing_ (2010) pp. 201–210.
  * Gallo  _et al._ (1989) G. Gallo, M. D. Grigoriadis, and R. E. Tarjan, SIAM Journal on Computing 18, 30 (1989).
  * Tsourakakis (2015) C. Tsourakakis, in  _Proceedings of the 24th international conference on world wide web_ (2015) pp. 1122–1132.
  * Feige  _et al._ (2001) U. Feige, D. Peleg, and G. Kortsarz, Algorithmica 29, 410 (2001).
  * Asahiro  _et al._ (2000) Y. Asahiro, K. Iwama, H. Tamaki, and T. Tokuyama, Journal of Algorithms 34, 203 (2000).
  * Erdős  _et al._ (1959) P. Erdős, A. Rényi, _et al._ , in  _On random graphs_ , Vol. 1 (1959) pp. 290–297.
  * (28) Duality Quantum Photonics, “Quantum Gaussian optics toolkit,” https://gitlab.com/dualityqp/qgot_public, accessed 2022-11-30.
  * Rahimi-Keshari  _et al._ (2015) S. Rahimi-Keshari, A. P. Lund, and T. C. Ralph, Physical review letters 114, 060501 (2015).
  * Oh  _et al._ (2022) C. Oh, Y. Lim, B. Fefferman, and L. Jiang, Physical Review Letters 128, 190501 (2022).
  * Martńez-Cifuentes  _et al._ (2022) J. Martńez-Cifuentes, K. Fonseca-Romero, and N. Quesada, arXiv preprint arXiv:2207.10058 (2022).
  * Sempere-Llagostera  _et al._ (2022) S. Sempere-Llagostera, R. Patel, I. Walmsley, and W. Kolthammer, arXiv preprint arXiv:2204.05254 (2022).
  * Erdős and Rényi (1960) P. Erdős and A. Rényi, Publ. Math. Inst. Hung. Acad. Sci 5, 17 (1960).
  * Arrazola  _et al._ (2018) J. M. Arrazola, T. R. Bromley, and P. Rebentrost, Physical Review A 98, 012322 (2018).
  * Aaronson and Arkhipov (2013) S. Aaronson and A. Arkhipov, arXiv preprint arXiv:1309.7460 (2013).

##  Appendix A Calculating the scaling parameter

Here we discuss how to calculate the optimal scaling parameter, $c$, in order
to maximise the probability of drawing samples in the $k$-click subspace. We
first eigendecompose the adjacency matrix $A=U\Lambda U^{T}$, with
$\Lambda=\text{diag}\\{|\lambda_{i}|\\}$, in which $\lambda_{i}$ are the
eigenvalues of $A$. We then rescale to give the diagonal matrix
$t_{D}=c\Lambda$ with $t_{D}=\mathrm{diag}\\{\tanh r_{i}\\}$ with $r_{i}$ the
squeezing in mode $i$. When using threshold detectors, the expected number of
‘clicks’ (detectors registering at least one photon during a measurement) is
given by

$\langle\hat{C}\rangle=M-\sum_{i=1}^{M}P_{\text{vac}}(i),$ (3)

where $M$ is the number of modes, and the vacuum probability in mode $i$,
$P_{\text{vac}}(i)$ is given by:

$P_{\text{vac}}(i)=\left(\left|\sum_{j}|U_{ij}|^{2}\left(\frac{1-lt_{D}^{2}}{1-t_{D}^{2}}\right)_{j}\right|^{2}-(1-l)^{2}\left|\sum_{j}U_{ij}^{2}\left(\frac{t_{D}}{1-t_{D}^{2}}\right)_{j}\right|^{2}\right)^{-1/2}.$
(4)

Increasing $c$ means increasing the squeezing parameter, and hence this
increases the likelihood of collision events, which makes the GBS experiment
more simulable Martńez-Cifuentes  _et al._ (2022). The effect of squeezing on
dense subgraph finding was investigated experimentally in Sempere-Llagostera
_et al._ (2022).

##  Appendix B Generating random subgraphs

Our implementation of the Erdős-Rényi model Erdős and Rényi (1960) is as
follows:

  1. 1.

Create a set of vertices $V$ of size $M$.

  2. 2.

Start at the first vertex $v_{i=1}$ in $V$.

  3. 3.

For every other vertex $\\{v_{j}\in V\setminus v_{i}\\}$, pick $r_{j}\in[0,1]$
from a uniform distribution.

  4. 4.

If $r_{j}<\rho/2$ then add an edge between $v_{i}$ and $v_{j}$.

  5. 5.

At the last vertex, $v_{i=M}$, stop, else move to the next vertex,
$v_{i}\leftarrow v_{i+1}$, and go to 3.

##  Appendix C Constructing arbitrary purity sources

We construct the vector of Schmidt coefficients $\\{S\\}$, such that they obey
the following normalisation and purity conditions (in which $P$ is purity):

$\displaystyle\sum_{i}S_{i}^{2}=1\,,\,\,\,\sum_{i}S_{i}^{4}=P:=\Tr[\hat{\rho}^{2}]\,.$
(5)

In order to simplify the two conditions in Eqs. 5 we construct a new set of
coefficients, $X=\\{x_{i}=s_{i}^{2}\\}$ which reduces the two conditions to:

$\displaystyle\sum_{i}x_{i}=1\,,\,\,\,\sum_{i}x_{i}^{2}=P\,.$ (6)

We define the set $X$ (which are the Schmidt coefficients squared) as,

$X_{l,b}=\\{x_{1}\\}\cup\\{x_{i}=k_{l,b}(i)(1-x_{1})|2\leq i\leq l\\}\,,$ (7)

so that, by construction, the normalisation condition is satisfied, where the
condition on the values $k_{l,b}(i)$ ensures that they are normalised to 1,
$\sum_{i}k_{l,b}(i)=1$. One useful form for the set $k_{l,b}$ is the geometric
scaling,

$k_{l,b}(i)=\frac{b^{l-i}}{\sum_{j=1}^{l-1}b^{j-1}}\,.$ (8)

Here $l$ is the number of non-zero Schmidt coefficients and $b$ is the base
which sets the factor for the geometric scaling between the elements $x_{i}$.
$i$ is the index of the element of the set of $X_{l,b}$ for the coefficient
value.

Using these definitions the purity condition Equation 6 is then,

$\begin{split}\sum_{i}x_{i}^{2}&=x_{1}^{2}+(k_{l,b}(2))^{2}(1-x_{1})^{2}+\dots\\\
&+(k_{l,b}(l))^{2}(1-x_{1})^{2}=P\,,\end{split}$ (9)

and grouping the terms by the order of $x_{1}$ we see it produces a quadratic
equation in $x_{1}$

$\begin{split}\left(1+\sum_{i=2}^{l}(k_{l,b}(i))^{2}\right)x_{1}^{2}&-2\left(\sum_{i=2}^{l}(k_{l,b}(i))^{2}\right)x_{1}+\left(\sum_{i=2}^{l}(k_{l,b}(i))^{2}\right)-P=0\,,\end{split}$
(10)

which is then straightforward to solve. Since all the elements of $S$ are
positive all the elements of $X$ are positive, and as such the positive root
can be taken. Lastly, we calculate the remaining $x_{i}$ by substituting
$x_{1}$ back in:

$x_{i}=k_{l,b}(i)(1-x_{1})\,,$ (11)

and the set $S$ is the (positive) square root of $X$,

$S=\\{\sqrt{x_{i}}|x_{i}\in X\\}\,.$ (12)

Due to the choice of the two parameters $l$ and $b$, for a particular set of
$S$ with the desired purity there are many distributions of Schmidt
coefficients that generate a source with the same purity. Also we note that
our construction does not generate all Schmidt distributions but it can be
used to generate a large class of distributions.

One interesting consequence of this particular form for $X$ is that for any
purity with $\frac{1}{2}\leq P\leq 1$ only two terms are needed. For quantum
information processing applications we are typically interested in sources
with purities close to $1$, and as such the majority of physically relevant or
interesting sources can be described with two Schmidt modes. This offers a
significant simplification when including a large number of spectral degrees
of freedom into a model. Although including spectral modes that are traced
over in the detection calculations only introduces a cubic overhead Thomas
_et al._ (2021), these factors are still large. Using this relation we can,
when required for speed, drastically reduce the number of spectral modes
modelled from some large $l$ to only 2.

##  Appendix D Further graph examples

(a) Initial graph has density 0.196.

(b) Initial graph has density 0.362 and contains a clique.

Figure 4: Comparison of performance of the classical (purple) and quantum
(green) enhanced random sampling algorithm, with different sources of error.
The grey line shows the performance of the deterministic classical algorithm
Asahiro  _et al._ (2000) (it is able to identify the clique). The inset
focuses on the region between 30 and 50 steps. Figure 5: We plot the average
density of subgraph found over 1000 samples, for different graph sizes, with
initial density approximately 0.4. The variance is shown for the classical and
quantum case with no error.

To check the generalisability of our results we carry out the same analysis as
in the main text but with with different graphs. We show the performance of
random sampling on two initial subgraphs, one of which is an Erdős-Rényi graph
with density 0.196, and one which is a modified version of the main graph from
our paper, with the same initial density, but containing a clique (this is
identified by the deterministic algorithm). Fig. 4 shows the impact of loss
and spectrally impure sources on dense subgraph finding applied to these
graphs. Fig. 5 shows the average density of graphs chosen by drawing samples
from a GBS distribution, or by randomly selecting in the classical case, over
1000 repetitions. As in Fig. 2, this is done for a range of graph sizes,
searching for subgraphs with size equal to the closest integer to $\sqrt{n}$.

These results suggest similar behaviour to the example discussed in the main
text, being very robust to error and showing a significant speedup in the
quantum case, even with high levels of loss and spectral impurity.

##  Appendix E Simulated annealing

We now employ the quantum-enhanced simulated annealing algorithm, as described
in Arrazola and Bromley (2018), for finding dense subgraphs in our main
example graphs (as introduced in the main text). Fig. 6 shows the impact of
loss (left) and impure sources (right). As in Arrazola and Bromley (2018),
this algorithm shows a smaller difference between the effectiveness of the
classical and quantum-enhanced algorithms. Nonetheless, as with our previous
results, this speedup remains even in the presence of significant levels of
error.

Figure 6: Comparison of performance of the classical and quantum enhanced
simulated annealing algorithm, in the presence of varying amounts of loss
(left) and with spectrally impure sources (right). The grey line shows the
performance of the deterministic classical algorithm Asahiro  _et al._ (2000).

Note that our implementation of the simulated annealing algorithm differs
slightly from that described in Arrazola and Bromley (2018). During the GBS-
Tweak subroutine, described in Arrazola  _et al._ (2018), a sample $T$ (in
this case corresponding to a subgraph) is drawn, that facilitates an
exploration of the search space, after drawing an initial sample $S$. We drew
the sample $T$ from the modes that are not included in $S$, as opposed to the
full set of modes. This was done to reduce run time while minimising impact on
the performance of the algorithm. Here, ‘number of steps’ (as indicated on the
$x$-axis) refers to the number of steps in the GBS-Tweak subroutine.

##  Appendix F Performance without postselection

Previous results have considered the ‘number of steps’ to only include
detection events with $k$ click events. However, unlike the Aaronson-Arkhipov
boson sampling scheme that uses single photons as input Aaronson and Arkhipov
(2013), GBS does not have a fixed photon number at the detection stage. By
choosing the scaling parameter $c$ appropriately, it is possible to bias the
output towards a particular photon number (or number of clicks when using
threshold detectors), but a spread of photon numbers will be observed in
practice.

In Fig. 7 we show the performance of the DkS random sampling algorithm, where
here ‘number of steps’ refers to the total number of samples drawn. We assume
that any samples with the incorrect click number are discarded (realistically,
these may be useful for local searches). We vary the loss parameter, and use
the optimal scaling parameter $c$ (using the method previously described) for
each different loss value (thus, we assume the error in the device is well
understood and the squeezing can be increased to compensate). For the
classical comparison, we repeat the previous method, and sample randomly
across only the $k$-vertex subgraphs. As before, we can see that increased
levels of loss do not have a significant impact on the performance of the
quantum-enhanced algorithm.

Figure 7: Performance of the classical and quantum-enhanced random sampling
algorithm for dense subgraph finding, without postselecting GBS samples from
the correct photon number subspace. The grey line shows the performance of the
deterministic classical algorithm.


# Spatially-Resolved Hyperlocal Weather Prediction and Anomaly Detection Using
IoT Sensor Networks and Machine Learning Techniques

###### Abstract

Accurate and timely hyperlocal weather predictions are essential for various
applications, ranging from agriculture to disaster management. In this paper,
we propose a novel approach that combines hyperlocal weather prediction and
anomaly detection using IoT sensor networks and advanced machine learning
techniques. Our approach leverages data from multiple spatially-distributed
yet relatively close locations and IoT sensors to create high-resolution
weather models capable of predicting short-term, localized weather conditions
such as temperature, pressure, and humidity. By monitoring changes in weather
parameters across these locations, our system is able to enhance the spatial
resolution of predictions and effectively detect anomalies in real-time.
Additionally, our system employs unsupervised learning algorithms to identify
unusual weather patterns, providing timely alerts. Our findings indicate that
this system has the potential to enhance decision-making.

Index Terms—  Hyperlocal weather prediction, Anomaly detection, IoT sensor
networks, Machine learning, Spatial resolution, Weather monitoring

##  1 Introduction

Hyperlocal weather prediction is an essential aspect of various applications,
such as agriculture, transportation, urban planning, and disaster management.
Accurate and timely predictions of localized weather conditions can
significantly impact decision-making processes, leading to better adaptation
strategies and improved public safety. Additionally, identifying and alerting
users to unusual weather events or patterns is crucial for preparedness and
mitigation efforts. Despite the availability of sophisticated weather models,
predicting hyperlocal weather conditions remains challenging due to the
complex interactions between various atmospheric parameters and the inherent
limitations in capturing fine-grained spatial and temporal variations.

Recent advancements in the Internet of Things (IoT) and machine learning
provide new opportunities for addressing these challenges. IoT sensor networks
enable the collection of high-resolution, real-time data from multiple
spatially-distributed yet relatively close locations. This rich dataset, when
combined with advanced machine learning techniques, can significantly improve
the accuracy and spatial resolution of weather predictions.

In this paper, we propose a novel approach that combines hyperlocal weather
prediction and anomaly detection using IoT sensor networks and advanced
machine learning techniques. Our approach leverages data from multiple
sources, including traditional weather stations, IoT sensors, and user-
generated reports, to create high-resolution weather models capable of
predicting short-term, localized weather conditions such as temperature,
precipitation, and wind. By monitoring changes in weather parameters across
these locations, our system is able to enhance the spatial resolution of
predictions and effectively detect anomalies in real-time. Furthermore, our
system employs unsupervised learning algorithms to identify unusual weather
events or patterns, providing timely alerts to users and relevant authorities.
This can be particularly beneficial in addressing the growing concerns of
extreme weather events and climate change, as early detection and response
play a crucial role in minimizing potential damages.

We evaluate the performance of our approach using real-world datasets and
compare it to existing methods, demonstrating significant improvements in
prediction accuracy, spatial resolution, and timeliness of anomaly detection.
Our findings indicate that the proposed system has the potential to enhance
decision-making and planning across various sectors, leading to better
adaptation strategies and improved public safety.

###  1.1 Related Works

The Internet of Things (IoT) has been widely used in various fields, including
weather prediction and anomaly detection. IoT devices can collect data from
spatially close places and provide real-time monitoring of environmental
factors such as temperature, humidity, and precipitation [11][12]. In this
literature review, we will discuss the research results related to weather
prediction and anomaly detection using LSTMs and Hierarchical Temporal Memory
(HTM) algorithm using a network of IoT devices.

LSTMs and HTM algorithms have been used in various fields for sequence
learning and prediction problems with streaming data [9][13]. In [13], four
different categories of computationally efficient deep learning models,
including CNN, LSTM, CNN-LSTM, and ConvLSTM, have been critically examined for
improved weather prediction. The authors have emphasized supervised learning
and feature engineering-based deep learning models for improved weather
prediction.

Anomaly detection is another important application of IoT devices. In [10],
the authors proposed an early detection model of IoT malware network activity
using machine learning techniques. The proposed model detects IoT malware
activity much before the actual attack, during the scanning/infection phase.
In [14], the authors proposed an ensemble-based spam detection model in smart
home IoT devices time series data using machine learning techniques. The
proposed model enhances the security level of the smart home IoT system by
detecting anomalies in the data.

In conclusion, LSTMs and HTM algorithms can be used for weather prediction and
anomaly detection. Deep learning models, including CNN, LSTM, CNN-LSTM, and
ConvLSTM, can be used for improved weather prediction. Anomaly detection
models can enhance the security level of the smart home IoT system by
detecting anomalies in the data. IoT devices can collect data from spatially
close places and provide real-time monitoring of environmental factors such as
temperature, humidity, and precipitation.

###  1.2 Major contributions

Our contributions toward the development of a hyperlocal weather prediction
and anomaly detection system using IoT sensor networks and machine learning
are as follows:

  * •

We propose a novel approach that integrates data from traditional weather
stations and IoT sensors reports to create high-resolution weather models
capable of predicting short-term, localized weather conditions;

  * •

We develop an anomaly detection system using the Hierarchical Temporal Memory
to identify unusual weather events or patterns, providing timely alerts to
users and relevant authorities

The rest of the paper is organised as follows: We elaborate on our proposal in
Section 2, present evaluation details in Section 4 and discuss our results in
5.

##  2 DATA COLLECTION AND PRE-PROCESSING

In this section, we describe the data collection process using a mesh of IoT
devices and the subsequent pre-processing steps applied to the collected data.

  * •

IoT Device and Sensor Configuration: We utilized a mesh of IoT devices,
specifically ESP-32 micro-controllers, to collect temperature, humidity, and
pressure measurements. These devices were equipped with BME280 sensors, which
use the I2C protocol to communicate with the ESP-32 micro-controllers. The IoT
devices were strategically placed across multiple spatially-distributed
locations to ensure adequate coverage for hyperlocal weather prediction.

  * •

Data Transmission and Storage: Data collected by the IoT devices was
transmitted to a cloud server using the Blynk.io platform at hourly intervals.
Our machine learning model was updated daily after accumulating 24 hours’
worth of data. The target variable for the model was the hourly temperature of
the following day in Goa.

  * •

Data Retrieval and Formatting: Using Blynk’s cloud API functions, the
collected data was retrieved and converted into a CSV file. Each row in the
file contained temperature, humidity, pressure, and sensor ID information,
which served as the input for our machine learning algorithms.

  * •

Data Pre-Processing: To ensure data quality and model reliability, we
performed the following preprocessing steps:

  * •

Duplicate Data Handling: In cases where identical data was recorded for more
than two consecutive hours, the corresponding data for that hour was removed.
This was done to account for potential IoT device malfunctions and maintain
the integrity of our dataset.

Fig. 1: Temperature and Humidity for 8 days from the Dataset.

##  3 MACHINE LEARNING MODEL FOR TIME-SERIES DATA

###  3.1 Weather prediction

In this section, we discuss the machine learning models employed to train on
the time-series data of hourly temperature, humidity, and pressure collected
from multiple sensors surrounding the target sensor. Our objective is to
predict the temperature at the target sensor. To ensure the robustness of the
model, the target sensor is randomly changed during the training process.

  * •

Model Selection and Rationale: We considered various machine learning models
suitable for time-series data, such as Autoregressive Integrated Moving
Average (ARIMA), Long Short-Term Memory (LSTM) networks, and Gated Recurrent
Units (GRUs). We ultimately selected LSTM networks for our study due to their
ability to effectively capture long-term dependencies and handle vanishing
gradient problems commonly encountered in time-series data.

  * •

Model Architecture: Our LSTM network architecture comprises an input layer,
multiple LSTM layers, and a dense output layer with a linear activation
function. The input layer is designed to accept data from multiple sensors,
including the target sensor, with features such as temperature, humidity, and
pressure. The LSTM layers capture temporal dependencies and patterns across
the input data. The dense output layer generates the predicted temperature
value for the target sensor.

  * •

Training Process: During the training process, we randomly change the target
sensor to ensure the robustness of our model. This approach prevents
overfitting to a specific sensor location and allows our model to generalize
better across various spatial configurations. We also employ techniques such
as cross-validation and early stopping to further improve the model’s
performance and mitigate overfitting.

  * •

Model Evaluation: To evaluate the performance of our LSTM model, we use
metrics such as Mean Absolute Error (MAE) and Root Mean Square Error (RMSE) to
quantify the difference between the predicted and actual temperature values.
Additionally, we compare our model’s performance to other time-series models
like ARIMA and GRUs to validate the effectiveness of our chosen architecture
in predicting temperature at the target sensor location.

###  3.2 Anomaly Detection with Hierarchical Temporal Memory Algorithm

In addition to predicting the temperature at the target sensor, our system
also incorporates anomaly detection to identify unusual weather patterns and
events. For this task, we employ the Hierarchical Temporal Memory (HTM)
algorithm, a biologically-inspired machine learning model specifically
designed for processing and detecting anomalies in time-series data.

The HTM algorithm uses a combination of spatial pooling and temporal memory to
learn and represent complex patterns in the input data. Spatial pooling
enables the model to learn spatial patterns and create a robust and stable
representation of the input data. Temporal memory allows the model to learn
and recognize sequences of patterns, capturing the temporal context and
dependencies within the time-series data.

We train the HTM model on our preprocessed dataset containing temperature,
humidity, and pressure values from multiple sensors. Once trained, the model
can detect anomalies by comparing the predicted and actual data points,
identifying significant deviations that may indicate unusual weather events or
patterns. The detected anomalies are then flagged and alerts are sent to users
and relevant authorities in real-time, allowing for timely response and
adaptation to potential weather-related risks.

##  4 Empirical Evaluation

Our evaluation aims to assess the effectiveness of our proposed approach in
balancing prediction accuracy, anomaly detection, and computational
efficiency. Specifically, we investigate the following hypotheses for
hyperlocal weather prediction and anomaly detection:

  * •

Our approach, leveraging IoT sensor networks and machine learning, constructs
more accurate and timely predictions and anomaly detection compared to
traditional methods;

  * •

The use of our proposed system doesn’t significantly compromise computational
efficiency compared to existing state-of-the-art methods or models of similar
complexity.

##  5 RESULTS

In this section, we present the results of our experiments, evaluating the
performance of our LSTM-based weather prediction model and the HTM-based
anomaly detection system. We compare the LSTM model with other time-series
models, such as ARIMA and GRUs, to demonstrate its effectiveness in predicting
temperature at the target sensor location. Additionally, we analyze the
ability of the HTM algorithm to detect weather anomalies in real-time.

###  5.1 Weather Prediction Results

To evaluate the performance of our LSTM-based weather prediction model, we
employed the Mean Absolute Error (MAE), Mean Squared Error (MSE), and Root
Mean Squared Error (RMSE) metrics. These metrics quantify the difference
between the predicted and actual temperature values at the target sensor
location.

Table 1: Performance comparison of LSTM, ARIMA, and GRU models Model | MSE | MAE | RMSE
---|---|---|---
LSTM | 0.0017 | 0.0304 | 0.0409
ARIMA | 0.0042 | 0.0570 | 0.0651
GRU | 0.0045 | 0.0782 | 0.0539

Our results show that the LSTM model outperforms the GRU model but is slightly
less accurate than the ARIMA model in terms of prediction accuracy. As shown
in Table 1, the LSTM model achieved an average MSE of 0.0017, an average MAE
of 0.0304, and an average RMSE of 0.0409. In comparison, the ARIMA model
obtained an average MAE of 0.0570, an average MSE of 0.0042, and an average
RMSE of 0.0651. The GRU model had an average MSE of 0.0045, an average MAE of
0.0782, and an average RMSE of 0.0539.

These results indicate that the LSTM model provides competitive performance in
predicting the temperature, with the ARIMA model showing slightly better
accuracy. However, the LSTM model demonstrates a significant advantage over
the GRU model in terms of prediction accuracy.

Fig. 2: True temperature and the predicted value for a sample data of 8 days
is shown above.

###  5.2 Weather Anomaly Detection Results

In this section, we present the results of our experiments evaluating the
performance of the HTM-based anomaly detection system. The goal of this system
is to detect unusual weather events or patterns in real-time, allowing for
timely alerts to users and relevant authorities.

To assess the performance of the HTM algorithm, we tested the model on a
dataset containing both normal and anomalous weather data. The anomalous data
included instances of sudden temperature changes, extreme humidity levels, and
unusual pressure variations that deviated significantly from typical weather
patterns.

We employed the following metrics to evaluate the HTM algorithm’s performance
in detecting weather anomalies:

  * •

True Positive Rate (TPR): The proportion of correctly identified anomalies
among all true anomalies.

  * •

False Positive Rate (FPR): The proportion of false alarms among all normal
data instances.

  * •

Precision: The proportion of true anomalies among all detected anomalies.

  * •

F1-Score: The harmonic mean of precision and recall (TPR), providing a
balanced measure of the model’s performance.

Table 2: Performance of the HTM-based anomaly detection system  Metric | TPR | FPR | Precision | F1-Score
---|---|---|---|---
HTM | 0.92 | 0.05 | 0.89 | 0.90

As shown in Table 2, the HTM algorithm achieved a TPR of 0.92, indicating that
it correctly identified 92% of the true anomalies present in the dataset. The
FPR was 0.05, suggesting a low rate of false alarms. The HTM model obtained a
precision of 0.89, which signifies that 89% of the detected anomalies were
true anomalies. The F1-Score, a balanced measure of the model’s performance,
was 0.90, demonstrating the effectiveness of the HTM algorithm in detecting
weather anomalies in real-time.

These results indicate that the proposed HTM-based anomaly detection system is
successful in identifying unusual weather patterns and events, providing
valuable information for users and authorities to take timely actions in
response to potential weather-related risks.

##  6 CONCLUSION

In this paper, we presented a novel approach to hyperlocal weather prediction
and anomaly detection using IoT sensor networks and machine learning
techniques. Our system leverages data from a mesh of IoT devices and
traditional weather stations to develop high-resolution weather models capable
of predicting short-term, localized weather conditions. We utilized LSTM
networks for weather prediction and the HTM algorithm for detecting unusual
weather patterns and events.

Our results demonstrate the effectiveness of the proposed system in accurately
predicting temperature at the target sensor location and identifying weather
anomalies in real-time. The integration of IoT devices and machine learning
models allows for improved granularity in weather forecasting and facilitates
timely response to potential weather-related risks.

The proposed system can be further enhanced by incorporating additional
environmental variables, such as wind speed and direction, and by expanding
the coverage of the IoT sensor network. Additionally, exploring other machine
learning techniques and architectures, such as attention mechanisms or deep
learning models, could potentially improve the accuracy and robustness of our
system.

In conclusion, our work contributes to the advancement of hyperlocal weather
prediction and anomaly detection systems, providing valuable insights for
future research and development in this area. By enabling accurate, real-time
detection of weather anomalies and localized forecasting, our system has the
potential to significantly impact various domains, such as agriculture,
disaster management, and smart city planning.

## References

  * [1] “EDIMA: Early Detection of IoT Malware Network Activity Using Machine Learning Techniques,”  in WF-IoT, 2019. [Online]. Available: https://doi.org/10.1109/wf-iot.2019.8767194.
  * [2] “The Internet of Things: Secure Distributed Inference,”  IEEE Signal Process. Mag., vol. 35, no. 5, pp. 64-75, 2018. [Online]. Available: https://doi.org/10.1109/msp.2018.2842097.
  * [3] “A Cloud-Based Real Time Weather Reporting System Using IoT,”  2023\. [Online]. Available: https://doi.org/10.3233/atde221326.
  * [4] “Internet of Things (IOT) Based Mini - Weather Station using Arduino,”  IJRASET, vol. 10, no. 6, pp. 3170-3174, 2022. [Online]. Available: https://doi.org/10.22214/ijraset.2022.44564.
  * [5] “Device Identification Interoperability in Heterogeneous IoT Platforms,”  Sensors, vol. 19, no. 6, p. 1433, 2019. [Online]. Available: https://doi.org/10.3390/s19061433.
  * [6] “Device Identification Interoperability in Heterogeneous IoT Platforms,”  Sensors, vol. 19, no. 6, p. 1433, 2019. [Online]. Available: https://doi.org/10.3390/s19061433.
  * [7] “IoT based climate prediction using ANN for green networking,”  IOP Conf. Ser.: Mater. Sci. Eng., vol. 993, no. 1, p. 012090, 2020. [Online]. Available: https://doi.org/10.1088/1757-899x/993/1/012090.
  * [8] “Ensemble-Based Spam Detection in Smart Home IoT Devices Time Series Data Using Machine Learning Techniques,”  Information, vol. 11, no. 7, p. 344, 2020. [Online]. Available: https://doi.org/10.3390/info11070344.
  * [9] “Continuous Online Sequence Learning with an Unsupervised Neural Network Model,”  Neural Computation, vol. 28, no. 11, pp. 2474-2504, 2016.
  * [10] “A deep learning approach to real-time parking occupancy prediction in transportation networks incorporating multiple spatio-temporal data sources,”  Transportation Research Part C: Emerging Technologies, vol. 107, pp. 248-265, 2019. [Online]. Available: https://doi.org/10.1016/j.trc.2019.08.010.
  * [11] “Short-Term Photovoltaic Power Forecasting Using an LSTM Neural Network and Synthetic Weather Forecast,”  IEEE Access, vol. 8, pp. 172524-172533, 2020. [Online]. Available: https://doi.org/10.1109/access.2020.3024901.
  * [12] “Forecasting and monitoring a subglacial eruption in Iceland,”  Eos Trans. AGU, vol. 86, no. 26, p. 245, 2005. [Online]. Available: https://doi.org/10.1029/2005eo260001.
  * [13] “Deep Learning for Feature Engineering-Based Improved Weather Prediction,”  pp. 195-217, 2021. [Online]. Available: https://doi.org/10.4018/978-1-7998-6659-6.ch011.
  * [14] “Making Use of Hidden Data: Towards a Database of Weather Predictors,”  JEA, vol. 15, no. 1, pp. 81-87, 2012. [Online]. Available: https://doi.org/10.5038/2162-4593.15.1.7.
  * [15] S. Hochreiter and J. Schmidhuber,  “Long Short-Term Memory,”  Neural Computation, vol. 9, no. 8, pp. 1735-1780, 1997. [Online]. Available: https://doi.org/10.1162/neco.1997.9.8.1735.
  * [16] G. E. P. Box and G. M. Jenkins,  Time series analysis: Forecasting and control. San Francisco: Holden-Day, 1976.
  * [17] K. Cho, B. Van Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio,  “Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation,”  arXiv preprint arXiv:1406.1078, 2014.
  * [18] S. Ahmad,  “Properties of Sparse Distributed Representations and their Application to Hierarchical Temporal Memory,”  arXiv preprint arXiv:1602.06074, 2016.