=Paper=
{{Paper
|id=Vol-3727/abstract2
|storemode=property
|title=Towards quantum-based graph matching for IoT systems (extended abstract)
|pdfUrl=https://ceur-ws.org/Vol-3727/abstract2.pdf
|volume=Vol-3727
|authors=Felix Gemeinhardt,Daniel Lehner,Manuel Wimmer
|dblpUrl=https://dblp.org/rec/conf/staf/GemeinhardtLW24
}}
==Towards quantum-based graph matching for IoT systems (extended abstract)==
https://ceur-ws.org/Vol-3727/abstract2.pdf
Towards quantum-based graph matching for IoT
systems (extended abstract)
Felix Gemeinhardt1 , Daniel Lehner1 and Manuel Wimmer1
1
Johannes Kepler University Linz, Altenberger Strasse 69, 4040 Linz, Austria
Context. Heterogeneous, large, and complex federations of Internet of Things (IoT) systems
pose ever-increasing challenges to current computing paradigms. Especially the continuous
changes in the system structure make planning tedious. Taking a smart city as an example, the
system experiences (de-)activations of individual devices and subsystems, device roaming, the
movement of people and infrastructure, and volatile traffic and communication scenarios due
to mass events (e.g., concerts).
Graph-based Representation. It is common to abstract large Cyber-Physical System (CPS)
and IoT federations, such as smart cities, logistics management systems, and large production
plants, as heterogeneous graphs, whose nodes and edges can be added, altered, and removed
dynamically at runtime. This dynamic adaptability requires several computational problems to
be addressed, among others, the so-called graph isomorphism problem, or its generalization, the
Sub-Graph Isomorphism (SGI) problem [1]. The latter refers to the task of finding occurrences
of a smaller template graph in a larger target graph. The SGI problem (a.k.a. graph (pattern)
matching) is known to be NP-complete.
Quantum Computing for Graph Isomorphism. Recently, quantum algorithms have
also been proposed to tackle the SGI problem suggesting significant advantages in terms
of computational speed-up. Specifically, implementations of such algorithms in prominent
quantum programming languages have been suggested for homogeneous graphs πΊ = (π , πΈ),
where π denotes the finite set of vertices and πΈ denotes the finite set of edges (see [2] and
references therein). They require as input the adjacency matrices of the respective graphs
and directly enable the use of Quantum Computing (QC) to tackle the SGI problem and, thus,
real-world problems related to dynamic adaptations of complex systems such as IoT systems.
Vehicle Platooning Use Case. To make us of the advantages of QC-based (sub-)graph
matching for IoT systems, we suggest using common MDE techniques such as abstraction,
graph transformation and code generation to extract the necessary graph structure. One direct
use case would be in applications where all nodes represent the same object type. For instance,
in logistics we may use SGI to identify potential for vehicle platooning. For this, a global road
network view might identify vehicles (e.g., trucks) and suggest their joining. Similar applications
can be used for identifying certain subgroups (e.g., people, devices) in smart cities.
Extension to Heterogeneous Models. The drawback of the current quantum SGI is its
limitation to homogeneous graphs. In CPS and IoT contexts, models usually contain typed
MeSS 2024: 4th International Workshop on MDE for Smart IoT Systems, July 10, 2024, Enschede, Netherlands
Envelope-Open felix.gemeinhardt@jku.at (F. Gemeinhardt); daniel.lehner@jku.at (D. Lehner); manuel.wimmer@jku.at
(M. Wimmer)
Orcid 0000-0001-7589-8263 (F. Gemeinhardt); 0000-0001-8840-8040 (D. Lehner); 0000-0002-1124-7098 (M. Wimmer)
Β© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
nodes and edges, thus requiring heterogeneous graphs that support node types and edge labels.
We thus propose using a transformation method to encode the information of a heterogeneous
graph πΊβππ‘ = (π , πΈ, πΏπ , πΏπΈ ) in a specific form of a homogeneous graph, thus, enabling the use
of QC for solving the SGI problem. Here, πΏπ denotes the finite set of vertex type labels and πΏπΈ
denotes the finite set of edge labels. To encode the information of πΏπΈ , we propose a mapping
to the integer weights of the edges connecting the respective nodes, i.e., πΉπΈ βΆ πΏπΈ β β>π . The
encoding for πΏπ is less straightforward. First, we propose to introduce a new label node. Thus,
the number of nodes in the generated homogeneous graph is |πβππ | = |π | + 1, where π denotes
the set of vertices of the heterogeneous graph. Next, we propose a mapping between πΏπ and
the weights of the edges that connect the original nodes in π and the new label node. To further
be able to discriminate the label node in the homogeneous graph, the edge weights have to
be adapted. Our proposal enables different strategies, e.g., working with negative numbers or
shifting the integer weights by a non-integer constant (e.g., 0.5).
Note, that these mappings are in general injective and may even be bijective in cases where
|πΏπΈ | and |πΏπ | can be restricted a-priori, i.e., when domain knowledge allows limiting the number
of occurring labels in advance. Furthermore, |πΏπΈ | and |πΏπ | are usually much smaller than |π | and
|πΈ|, thus, no focus is laid on the semantic distances of the labels in the original transformation.
However, setting and adjusting scaling factors for the edge weights and working with pre-
defined orders of labels also allows encoding this information qualitatively in the generated
homogeneous graphs.
From the resulting homogeneous graphs, adjacency matrices can be generated as input for
the quantum algorithms as stated above. The quantum algorithm [2] outputs the permutation of
the adjacency matrix of the target graph such that the similarity between the top-left submatrix
and the adjacency matrix of the template graph is maximized. This permutation represents a
bijective mapping for the target graph vertices which is transformed back to the heterogeneous
graph model.
Vision. Overall, our approach foresees the following steps: (1) extraction of a heterogeneous
domain model, (2) model transformation to support a homogeneous graph representation, (3)
generation of quantum algorithm code that can be run on modern QC frameworks, and (4)
backtransformation of the QC results into the modeling framework.
Based on the vision outlined here, our next steps include the development of a prototypical
implementation and performing a set of benchmarking experiments to prove the validity of our
approach and highlight the potential for advantages.
References
[1] G. Engel, T. Greiner, S. Seifert, Semantic subgraph isomorphism for enabling physical adapt-
ability of cyber-physical production systems, in: 2016 IEEE 21st International Conference
on Emerging Technologies and Factory Automation (ETFA), IEEE, 2016, pp. 1β8.
[2] N. Mariella, A. Simonetto, A quantum algorithm for the sub-graph isomorphism problem,
ACM Transactions on Quantum Computing 4 (2023) 1β34.