Subgraph Query Matching in Multi-Graphs Based on Node Embedding

Muhammad Anwar, Aboul Ella Hassanien, Václav Snás̃el and Sameh H. Basha ()
Additional contact information
Muhammad Anwar: Department of Mathematics, Faculty of Science, Cairo University, Giza 12613, Egypt
Aboul Ella Hassanien: Faculty of Computers and Information, Cairo University, Giza 12613, Egypt
Václav Snás̃el: Faculty of Electrical Engineering and Computer Science, VŠB-Technical University of Ostrava, 708 33 Ostrava, Czech Republic
Sameh H. Basha: Department of Mathematics, Faculty of Science, Cairo University, Giza 12613, Egypt

Mathematics, 2022, vol. 10, issue 24, 1-22

Abstract: 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’ 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’ 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’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.

Keywords: multigraph mining; pattern mining; matching problem; core number; KD-tree; node embedding (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/24/4830/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/24/4830/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:24:p:4830-:d:1008019

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().