Subgraph Query Matching in Multi-Graphs Based on Node Embedding

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F22%3A10251900" target="_blank" >RIV/61989100:27240/22:10251900 - isvavai.cz</a>

Result on the web

<a href="https://www.mdpi.com/2227-7390/10/24/4830" target="_blank" >https://www.mdpi.com/2227-7390/10/24/4830</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3390/math10244830" target="_blank" >10.3390/math10244830</a>

Result language

angličtina

Original language name

Subgraph Query Matching in Multi-Graphs Based on Node Embedding

Original language description

This paper presents an efficient algorithm for matching subgraph queries in a multi-graph based on features-based indexing techniques. The KD-tree data structure represents these nodes&apos; features, while the set-trie index data structure represents the multi-edges to make queries effectively. The vertex core number, triangle number, and vertex degree are the eight features&apos; main features. The densest vertex in the query graph is extracted based on these main features. The proposed model consists of two phases. The first phase&apos;s main idea is that, for the densest extracted vertex in the query graph, find the density similar neighborhood structure in the data graph. Then find the k-nearest neighborhood query to obtain the densest subgraph. The second phase for each layer graph, mapping the vertex to feature vector (Vertex Embedding), improves the proposed model. To reduce the node-embedding size to be efficient with the KD-tree, indexing a dimension reduction, the principal component analysis (PCA) method is used. Furthermore, symmetry-breaking conditions will remove the redundancy in the generated pattern matching with the query graph. In both phases, the filtering process is applied to minimize the number of candidate data nodes of the initiate query vertex. The filtering process is applied to minimize the number of candidate data nodes of the initiate query vertex. Finally, testing the effect of the concatenation of the structural features (orbits features) with the meta-features (summary of general, statistical, information-theoretic, etc.) for signatures of nodes on the model performance. The proposed model is tested over three real benchmarks, multi-graph datasets, and two randomly generated multi-graph datasets. The results agree with the theoretical study in both random cliques and Erdos random graph. The experiments showed that the time efficiency and the scalability results of the proposed model are acceptable.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10200 - Computer and information sciences

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2022

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Mathematics

ISSN

2227-7390

e-ISSN

2227-7390

Volume of the periodical

10

Issue of the periodical within the volume

24

Country of publishing house

CH - SWITZERLAND

Number of pages

22

Pages from-to

nestrankovano

UT code for WoS article

000903342300001

EID of the result in the Scopus database

—