Consider a large labeled graph (network), denoted the target. Subgraph matching is the problem of finding all instances of a small subgraph, denoted the query, in the target graph. Unlike the majority of existing methods that are restricted to graphs with labels solely on vertices, our proposed approach, named can effectively handle graphs with labels on both vertices and edges. ntroduces an efficient new vertex/edge domain data structure filtering procedure to speed up subgraph queries. The procedure, called path-based reduction, filters initial domains by scanning them for paths up to a specified length that appear in the query graph. Additionally, ncorporates existing techniques like variable ordering and parent selection, as well as adapting the core search process, to take advantage of the information within edge domains. Experiments in real scenarios such as protein–protein interaction graphs, co-authorship networks, and email networks, show that s faster than state-of-the-art systems varying the number of distinct vertex labels over the whole target graph and query sizes.

ArcMatch: high-performance subgraph matching for labeled graphs by exploiting edge domains / Bonnici, Vincenzo; Grasso, Roberto; Micale, Giovanni; Maria, Antonio di; Shasha, Dennis; Pulvirenti, Alfredo; Giugno, Rosalba. - In: DATA MINING AND KNOWLEDGE DISCOVERY. - ISSN 1384-5810. - (2024). [10.1007/s10618-024-01061-8]

ArcMatch: high-performance subgraph matching for labeled graphs by exploiting edge domains

Bonnici, Vincenzo
;
2024-01-01

Abstract

Consider a large labeled graph (network), denoted the target. Subgraph matching is the problem of finding all instances of a small subgraph, denoted the query, in the target graph. Unlike the majority of existing methods that are restricted to graphs with labels solely on vertices, our proposed approach, named can effectively handle graphs with labels on both vertices and edges. ntroduces an efficient new vertex/edge domain data structure filtering procedure to speed up subgraph queries. The procedure, called path-based reduction, filters initial domains by scanning them for paths up to a specified length that appear in the query graph. Additionally, ncorporates existing techniques like variable ordering and parent selection, as well as adapting the core search process, to take advantage of the information within edge domains. Experiments in real scenarios such as protein–protein interaction graphs, co-authorship networks, and email networks, show that s faster than state-of-the-art systems varying the number of distinct vertex labels over the whole target graph and query sizes.
2024
ArcMatch: high-performance subgraph matching for labeled graphs by exploiting edge domains / Bonnici, Vincenzo; Grasso, Roberto; Micale, Giovanni; Maria, Antonio di; Shasha, Dennis; Pulvirenti, Alfredo; Giugno, Rosalba. - In: DATA MINING AND KNOWLEDGE DISCOVERY. - ISSN 1384-5810. - (2024). [10.1007/s10618-024-01061-8]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11381/2992513
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact