Citation: Vanetik, N. Sufficient
Networks for Computing Support of
Graph Patterns. Information 2023, 14,
143. https://doi.org/10.3390/
info14030143
Academic Editors: Sławomir
Nowaczyk, Rita P. Ribeiro and
Grzegorz Nalepa
Received: 26 January 2023
Revised: 15 February 2023
Accepted: 19 February 2023
Published: 21 February 2023
Copyright: © 2023 by the author.
Licensee MDPI, Basel, Switzerland.
This article is an open access article
distributed under the terms and
conditions of the Creative Commons
Attribution (CC BY) license (https://
creativecommons.org/licenses/by/
4.0/).
Article
Sufficient Networks for Computing Support of Graph Patterns
Natalia Vanetik
Department of Software Engineering, Shamoon College of Engineering, Beer Sheva 84417, Israel;
natalyav@sce.ac.il; Tel.: +972-8-647-5015
Abstract:
Graph mining is the process of extracting and analyzing patterns from graph data. Graphs
are a data structure that consists of a set of nodes and a set of edges that connect these nodes. Graphs
are often used to represent real-world entities and the relationships between them. In a graph
database, the importance of a pattern (also known as support) must be quantified using a counting
function called a support measure. This function must adhere to several constraints, such as anti-
monotonicity that forbids a pattern to have support bigger than its sub-patterns. These constraints
make the tasks of defining and computing support measures highly non-trivial and computationally
expensive. In this paper, I use the previously discovered relationship between support measures in
graph databases and flows in networks of subgraph appearances to simplify the process of computing
support measures. I show that the network of pattern instances may be successfully pruned to contain
just particular kinds of patterns and prove that any legitimate computing support measures in graph
databases can adopt this strategy. When the suggested method is utilized, experimental evaluation
demonstrates that network size reduction is significant.
Keywords: data mining; graph mining; support measures; flows
1. Introduction
Graph mining is used in a variety of fields and applications. In social network analysis,
graph mining techniques are often used to analyze social media networks to understand
the relationships between users and identify key influencers [
1
]. Graphs can be used to
represent financial transactions for the task of fraud detection, and graph mining algorithms
can be used to identify suspicious patterns that may indicate fraudulent activity [
2
,
3
]. In
recommendation systems, graphs are used to represent the relationships between users and
items (e.g., products, articles), and graph mining algorithms can be used to recommend
items to users based on their relationships with other users and items [
4
,
5
]. Graphs can also
be used to represent networks of interconnected systems (e.g., transportation networks,
communication networks), and graph mining algorithms can be used to understand the
structure and function of these networks [
6
]. In bioinformatics, graphs are used to represent
biological networks (e.g., protein–protein interaction networks, gene regulatory networks),
and graph mining algorithms can be used to understand the relationships between the
elements in these networks [
7
,
8
]. In Natural Language Processing (NLP), graphs are used
extensively to represent relationships between words and concepts in natural language
texts, and graph mining algorithms can be used to understand the meaning and context of
the text [9,10].
Graphs are also used to describe various modern technologies such as wireless sensor
networks, neural networks, the Internet of Things (IOT), Global System For Mobile Com-
munication (GSM) networks, landscape connectivity and conservation planning, image
and signal processing, subway systems analysis, robotics, and more [11–13].
A frequent graph pattern is a subgraph (i.e., a subset of vertices and edges) that
appears frequently in a given graph database. Frequent graph patterns are often used to
discover interesting and meaningful patterns in graph data that may not be apparent when
looking at the graph as a whole.
Information 2023, 14, 143. https://doi.org/10.3390/info14030143 https://www.mdpi.com/journal/information
