  The Subgraph Matching (SM) problem consists of finding all the embeddings of
a given small graph, called the query, into a large graph, called the target.
The SM problem has been widely studied for simple graphs, i.e. graphs where
there is exactly one edge between two nodes and nodes have single labels, but
few approaches have been devised for labeled multigraphs, i.e. graphs having
possibly multiple labels on nodes in which pair of nodes may have multiple
labeled edges between them. Here we present MultiRI, a novel algorithm for the
Sub-Multigraph Matching (SMM) problem, i.e. subgraph matching in labeled
multigraphs. MultiRI improves on the state-of-the-art by computing
compatibility domains and symmetry breaking conditions on query nodes to filter
the search space of possible solutions. Empirically, we show that MultiRI
outperforms the state-of-the-art method for the SMM problem in both synthetic
and real graphs, with a multiplicative speedup between five and ten for large
graphs, by using a limited amount of memory.

Databases