Sufficient instance networks for computing support in graph databases

Because displaying connections within the data via a graph is natural and intuitive for humans, graph databases have grown in popularity. A graph database can be made up of multiple smaller graphs or a single huge graph. Finding statistically significant subgraphs (also known as graph patterns) in graph databases is referred to as graph mining. The search process within the graph database and a specified support measure to assess the statistical importance of these graph patterns make up this task’s two components. Finding occurrences of graph patterns in the database, which is a computationally intensive process, is necessary for this support measure, which is frequently difficult to compute. We concentrate on the scenario of a single graph database in this paper. We demonstrate, using the relationship between support measures and flows in networks of pattern instances established in prior work, that the network of pattern instances may be successfully pruned to contain just particular kinds of subgraphs for any suitable support measure. This strategy decreases the size of the instance network, which can lower the effort required to compute a support measure. We demonstrate that any legitimate support measures in graph databases can use this trimming.