Subgraph Query Matching in Multi-Graphs Based on Node Embedding

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Subgraph Query Matching in Multi-Graphs Based on Node Embedding

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Subgraph Query Matching in Multi-Graphs Based on Node Embedding

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2022

Kód důvěrnosti údajů

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

Název periodika

Mathematics

ISSN

2227-7390

e-ISSN

2227-7390

Svazek periodika

10

Číslo periodika v rámci svazku

24

Stát vydavatele periodika

CH - Švýcarská konfederace

Počet stran výsledku

22

Strana od-do

nestrankovano

Kód UT WoS článku

000903342300001

EID výsledku v databázi Scopus

—