#  MINE GRAPH RULE: A New Cypher-like Operator for Mining Association Rules on
Property Graphs

Francesco Cambria  Politecnico di MilanoVia Ponzio 34/5MilanoItaly20133
<EMAIL_ADDRESS>,  Francesco Invernici  0009-0002-5423-6978
Politecnico di MilanoVia Ponzio 34/5MilanoItaly20133
<EMAIL_ADDRESS>,  Anna Bernasconi  0000-0001-8016-5750
Politecnico di MilanoVia Ponzio 34/5MilanoItaly20133<EMAIL_ADDRESS>and  Stefano Ceri  0000-0003-0671-2415 Politecnico di MilanoVia Ponzio
34/5MilanoItaly20133<EMAIL_ADDRESS>
###### Abstract.

Mining information from graph databases is becoming overly important. To
approach this problem, current methods focus on identifying subgraphs with
specific topologies; as of today, no work has been focused on expressing
jointly the syntax and semantics of mining operations over rich property
graphs.

We define MINE GRAPH RULE, a new operator for mining association rules from
graph databases, by extending classical approaches used in relational
databases and exploited by recommending systems. We describe the syntax and
semantics of the operator, which is based on measuring the support and
confidence of each rule, and then we provide several examples of increasing
complexity on top of a realistic example; our operator embeds Cypher for
expressing the mining conditions.

MINE GRAPH RULE is implemented on top of Neo4j, the most successful graph
database system; it takes advantage of built-in optimizations of the Neo4j
engine, as well as optimizations that are defined in the context of relational
association rules. Our implementation is available as a portable Neo4j plugin.
At the end of our paper, we show the execution performance in a variety of
settings, by varying the operators, the size of the graph, the ratio between
node types, the method for creating relationships, and maximum support and
confidence.

PVLDB Reference Format:
PVLDB, 14(1): XXX-XXX, 2020.
doi:XX.XX/XXX.XX ††This work is licensed under the Creative Commons BY-NC-ND
4.0 International License. Visit https://creativecommons.org/licenses/by-nc-
nd/4.0/ to view a copy of this license. For any use beyond those covered by
this license, obtain permission by emailing<EMAIL_ADDRESS>Copyright is held
by the owner/author(s). Publication rights licensed to the VLDB Endowment.
Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097.
doi:XX.XX/XXX.XX

PVLDB Artifact Availability:
The source code, data, and/or other artifacts have been made available at
%leave␣empty␣if␣no␣availability␣url␣should␣be␣sethttps://github.com/FrInve/mine_graph_rule.

##  1\. Introduction

Association rules for relational datasets take the form $X\Rightarrow Y$,
where the left-hand side $X$ is denoted as body and the right-hand side $Y$ is
denoted as head, both are sets instantiated from the same underlying domain
(e.g., items), and their pairing within rules occur statistically more often
than “normal” in the context of certain groups of tuples within the same
relational dataset (e.g., all tuples referring to the same transaction)
(Agrawal et al., 1993, 1994; Srikant and Agrawal, 1997). Statistical
significance is measured by two indexes, called support and confidence; the
former is the probability of having both items $X$ and $Y$ within all
transactions, the latter is the probability of having the $Y$ item in the
transactions having the $X$ item.

Figure 1. Example of relational MINE RULE operator (Meo et al., 1996)

The classical interpretation of association rules in recommending systems
(Changchien and Lu, 2001; Lin et al., 2002; Osadchiy et al., 2019) is to
propose items that are often purchased in the same transaction, as an
indication that they are jointly chosen by customers who – in turn – may share
the same taste, although it is possible to have different interpretations of
association rules for many other contexts of applications, e.g., in the
medical domain symptoms of patients affected by the same disease (Stilou et
al., 2001; Nahar et al., 2013; Tandan et al., 2021), or in social networks
which interests are shared by the users (Si et al., 2019). Pattern languages
have been designed for extracting given rules based upon application needs,
e.g., focusing on given items in purchases (e.g., bread and butter), on given
habits/morbidities in patients (e.g., male smokers), and on given interests
among users (e.g., movies and music).

One such pattern language is the MINE RULE operator, defined thirty years ago
in (Meo et al., 1996) with the goal of extracting semantically meaningful
association rule patterns over a relational dataset. The operator uses the
expressive power of SQL and it consists of several parts mimicking an SQL
query. Typically, MINE RULE extracts quadruples [BODY, HEAD, SUPPORT,
CONFIDENCE ] from an underlying target table (constructed as an arbitrary SQL
Query Expression) with tuples arbitrarily grouped and further partitioned,
extracting all rules with minimum support and confidence, returned in a result
table. The “classical” application of finding all individual items purchased
in the same transaction with at most $n$ (e.g., 2) other items is expressed as
in Fig. 1; once computed on a given relational dataset, it may return tuples
such as [¡pants, socks¿, ¡jacket¿, 0.3, 0.3]. The result table can be used
within other queries.

Association rules satisfy a classical antimonotone property, stating that, for
any two rules $r_{1}:X_{1}\Rightarrow Y$ and $r_{2}:X_{2}\Rightarrow Y$, with
$X_{1}\supset X_{2}$ (e.g., $X_{1}$ properly contains all the items of
$X_{2}$), the support of $r_{1}$ is smaller than the support of $r_{2}$. The
antimonotone property and the constraint on minimum support allow, when the
support for a given association rule $r:X\Rightarrow Y$ is below the
threshold, to exclude also all rules whose body strictly includes $X$ (Vanetik
et al., 2006). This property is at the basis of efficient mining rule methods,
such as Apriori (Hegland, [n.d.]; Santoso, 2021) or Equivalence Class
Transformation Algorithm (ECLAT) (Zaki, 2000; Kaur et al., 2015), which
organize the search by arranging extracted bodies in a tree and cease
exploring descendants of nodes that are not supported.

In the digital age, vast amounts of data are being generated and collected at
an unprecedented pace (Aggarwal, 2011; Parviainen et al., 2017). Relational
databases are very effective in managing structured data, but they face
limitations when handling complex and interconnected data (Shanmugasundaram et
al., 1999; Moniruzzaman and Hossain, 2013); graph databases are emerging as
the leading data management technology for storing large knowledge graphs
(Vicknair et al., 2010; Robinson et al., 2015). Therefore, there is a strong
need for expressing association rules also in this context. In this work, we
present a new operator for graph databases, called MINE GRAPH RULE, which is
inspired by the relational MINE RULE operator. We illustrate the syntax and
semantics of the operator and then we demonstrate its expressive power through
several progressive examples, all built around a small but sufficiently
intricate motivating use case. We then describe how the MINE GRAPH RULE
operator can be deployed to a community-supported library, called _Awesome
Procedures on Cypher_ (APOC) (APOC Library, 2024), and run over Neo4j, one of
the most successful graph database system (Jouili and Vansteenberghe, 2013;
Fernandes et al., 2018; dbr, 2024).

Contributions. We present three significant contributions:

  * •

Syntax and semantics of a new operator for extracting association rules from
graph databases; the operator supports the orthogonal composition of several
features, including the extraction of many items in the body and in the head
by means of conjunctions of relationship chains of arbitrary length.

  * •

Optimized implementation as a portable plug-in for Neo4j, which takes
advantage of built-in optimizations of the Neo4j engine as well as
optimizations that mimic the Apriori algorithm defined for relational
databases.

  * •

Performance evaluation over artificially generated graphs that test a variety
of data mining patterns in the context of several settings (including variable
graph size, relationship density, and minimum support/confidence).

Outline. This article is organized as follows: Sec. 2 presents the related
work; Sec. 3 describes the syntax and semantics of the MINE GRAPH RULE
Operator and then illustrates several examples of increasing complexity, also
showing the operator’s output, produced as a set of tuples, one for each
association rule, listing body, head, support, and confidence. Sec. 4
describes the implementation and the generation of the example graph database,
and Sec. 5 describes the evaluation of our approach. Finally, Sec. 6 presents
the discussion and conclusion.

##  2\. Related Work

The main challenge when extending the broad work on relational association
rule mining to graph-based association rule mining is to move from a simple,
tabular data model, where associations are discovered within simple groups, to
a complex graph-based data model, where associations can be semantically
richer, and at the same time adapt the notions of support and confidence so as
to preserve the antimonotone property, guaranteeing good convergence of the
discovery methods.

To the best of our knowledge, an operator syntax and semantics have not yet
been introduced that define association rules in the context of graph
databases. Generally, in the works in which graph association rules are
studied, each specific example is evaluated in itself, without proposing a
structured framework that collectively defines graph association rules for
every possible instance.

A framework for Graph Pattern Association Rule Mining is defined in (Fan et
al., 2015), where the isomorphism of frequent subgraphs is mathematically
exploited to extract topological patterns that can be translated into rules.
Authors look for a frequent structure formed by a set of labeled nodes and
edges in the graph; a rule is defined as follows: when the frequent structure
is found, then also a specific edge is present, equipped with its values of
support and confidence. In addition, in (Fan et al., 2022) their approach for
the extraction association rules is enhanced by machine learning models and
graph sampling. Each example, however, is treated on its own and the rules are
not defined with a shared syntax. The work has been expanded in (Wang et al.,
2020), building up on the premise of searching rules guided by topological
isomorphism of subgraphs. Here, the authors divide the problem into two
different steps: 1) extraction of frequent patterns and 2) generation of the
rules. Taking advantage of a similar methodology, (Zhang et al., 2022)
develops an algorithm that acts as a predictor of missing/incorrect links in
Knowledge Graphs and (Priyadarshini and Mishra, 2010) compares a traditional
approach with a custom algorithm (based on the adjacent matrix) to extract
frequent subgraphs for graph mining.

A different approach consists of transforming graph-based data into relational
data and then searching for association rules. In (Raja and Balakrishnan,
2012), graph data is re-modeled into a transaction database, for which
association rules (with their support and confidence) are extracted.
Interesting case studies are reported in (Ciftçi et al., 2021) (evaluating
groups of artists appreciated by the same users) and in (Standl and Schlomske-
Bodenstein, 2021) (studying combinations of teaching methods that are more
effective than others). In both works, data is extracted from Neo4j and
structured in a way that the association rules are calculated thanks to
established Python packages (apy, 2019; Raschka, 2018). (Campi and Palese,
2021) implements a case study in Neo4j to find popular Twitter hashtags that
are posted together; here, authors evaluate the effect of pre-processing
techniques that enhance the performance of the rule mining algorithm. In (Sen
et al., 2021), an approach for a recommendation system of products is fully
developed in Neo4j. Lastly, (Tiwari et al., 2010) exploit graphs as a means to
more easily extract rules from a relational transaction dataset. Each
transaction is encoded in a graph with specific nodes and edges, and the rules
are extracted by exploiting graph query languages.

Note that all the mentioned works apply algorithms and the concepts of
association rules to graph data, without formalizing what a rule is and
without fully exploiting the richness given by the natural structure of
graphs.

##  3\. Operator Syntax and Semantics

The syntax of MINE GRAPH RULE is shown in Fig. 2; it is inspired by MINE RULE
operator (Meo et al., 1996) but it is significantly more complex in order to
exploit the many ways of building associations by using property graph
databases. It embeds some constructs of the Cypher query language (Francis et
al., 2018), so as to be easily translated to an APOC procedure for the Neo4j
system, and also to be more readable for graph database programmers.

Figure 2. MINE GRAPH RULE Syntax. Uppercase bold type is used for terminal
symbols. Lowercase is for non-terminal symbols; the bold ones are not
explained in the grammar, as their meaning is well-defined in the context of
property graphs. Note that square brackets are used to indicate optionality
([]) in the grammar; moreover, since Cypher language uses the symbols -[ and
]- for denoting relationships, square brackets are also used in bold-type to
enclose the three expressions of <relPattern>. Note as well that the $<$ and
$>$ symbols, used to delimitate non-terminal symbols, are also used -in larger
font size- to make comparisons in the pattern language: $>$ is used to denote
a ‘greater-than’ comparison in the support/confidence threshold definition and
in the <countRel> grammar production, $<$ is used to denote a ‘less-than’
comparison in the <anyRel> production.

The operator associates a <name> to the set of extracted association rules
that are built according to three expressions, respectively defining the
GROUPING, the rule’s BODY, and the rule’s HEAD. The grouping expression
defines, through the <anchorLabel>, the set of anchor nodes of the graph that
need to satisfy, when present, the WHERE condition. They provide the context
of evaluation of association rules; by analogy, the anchor acts as a pivot for
the set of rules in the same way the purchase transaction groups the basket of
items that are bought together. The BODY and HEAD expressions build
respectively the left and right parts of an association rule; they are both
defined by the <itemSet> production.

An itemSet is defined as a conjunction of expressions, each called <pattern>,
that extract the sets of items forming the head and body; the cardinality of
each <pattern> varies between 1 (the default case) and a value <n> (the
cardinality must be defined only if <n> is greater than 1). A <pattern>
generally consists of a linear path of relationships that starts from the
anchor nodes (i.e., the nodes defined in the grouping expression) and can
include an arbitrary number of relationship patterns (<relPattern>); recursion
is introduced by the <patternTail> production which can either close the
current recursion step with a final node or recursively include another
<patternTail>. Relationship patterns include three options (respectively
denoted as <singleRel>, <countRel>, and <anyRel>) whose explanation is
postponed to three specific subsections. Note that -for simplicity- we assume
that each relationship pattern is to be traversed from left to right.

The three expressions, GROUPING, BODY and HEAD, extract nodes that are
referenced by variables; these can be used both to build any Cypher-legal
predicate (<cypherPredicate>) for evaluating restricted parts of the graph
database or for adding other grouping conditions defined by the optional
IGNORE clause with a list of at least one <variable>. The operator syntax is
closed by setting two independent conditions for the minimum support <minsupp>
and minimum confidence <minconf> that must be satisfied by the extracted
rules.

For what concerns the semantics of association rules, we need to calculate
both support and confidence. We define $A$ as the set of anchor nodes; we
denote $A$’s cardinality as $C(A)$. Evaluating the body and head expression
associated with each anchor node in $A$ generates pairs $R_{i}=\langle
B_{i},H_{i}\rangle$, which are candidate association rules. We denote as
$C(B_{i})$ the cardinality of the set of anchor nodes that are paired to
$B_{i}$ and as $C(R_{i})$ the cardinality of anchor nodes that are paired to
both $B_{i}$ and $H_{i}$. Then, for a given rule $R_{i}$, its support is
$C(R_{i})/C(A)$ (by analogy: the fraction of transactions having both the body
and head items in the basket). Its confidence is $C(R_{i})/C(B_{i})$ (by
analogy: the fraction of transactions that have both the body and the head
over the transactions that have only the body). Finally, the operator extracts
those candidate association rules that satisfy minimal constraints on support
and confidence. Note that, in the search for association rules, it is
customary to exclude tautological rules, i.e., rules whose body and head are
identical. Similarly, in the evaluation of the MINE GRAPH RULE pattern, we
will exclude those rules whose body and head are identical.

We next proceed to illustrate the expressive power of the language by means of
examples, starting from the simple case that mimics the market basket analysis
and then progressively addressing more complex cases.

###  3.1. Running Example

Fig. 3 reports the schema of a property graph database, storing information
about people’s purchases that may reflect their social interactions; for
easing interpretation, nodes and relationships of the running example are
partitioned into subsets and each subset is associated with a specific label.
The PERSON nodes represent users of a social network, who can FOLLOW each
other and who can RECOMMEND certain products represented by ITEM nodes; the
BUY relationship indicates that given persons buy given products using an
electronic marketplace, whereas the OF relationship indicates a non-exclusive
CATEGORY which is assigned to each item by vendors on the basis of the
expected context of use of that item.

We also provide a super-small instance of the graph, shown in Fig. 4, in order
to progressively introduce examples of MINE GRAPH RULE applications. Every
node is uniquely identified by its Name and carries specific properties:
persons have Age and City, items have Color and Price.

Figure 3. Schema of the running example Figure 4. Instance of the running
example

###  3.2. Simple Association Rules

As a starting point, we show the most common application of association rules,
i.e., pairs of different items usually bought together by the same person.
These association rules are expressed by the Natural Language (NL) sentence:
”People who buy X, also buy Y”, where X and Y are different items. The MINE
GRAPH RULE operator extracting these rules is simply:

MINE GRAPH RULE SimpleAssociationRules GROUPING ON (p:Person) DEFINING BODY AS
(p)-[:BUY]-(X:Item) HEAD AS (p)-[:BUY]-(Y:Item) EXTRACTING RULES WITH SUPPORT
> 0.1 AND CONFIDENCE > 0.1

The operator looks for all nodes labeled as (:Person). Both body and head
expressions extract a single (:Item), connected by using the [:BUY]
relationship; hence the association rule combines the different items that are
bought by the same person. Once applied to the graph database instance of Fig.
4, the operator produces the result shown in Table 1. The table’s header has a
hierarchical structure; the top of the hierarchy has four fixed attributes,
respectively named Body, Head, Support, and Confidence. Below the Body and
Head, the header includes terms describing the role of each extracted instance
forming an association rule (in this case, BuyX and BuyY). The table’s content
includes one row for each association rule; Body and Head include the Names
describing the extracted Items.

Body | Head | Support | Confidence
---|---|---|---
BuyX | BuyY
Dress | Jeans | 0.25 | 0.5
Dress | Shoes | 0.5 | 1
Jeans | Dress | 0.25 | 0.5
Jeans | Shoes | 0.25 | 0.5
Shoes | Dress | 0.5 | 1
Shoes | Jeans | 0.25 | 0.5
Shorts | T-shirt | 0.25 | 1
T-shirt | Shorts | 0.25 | 1

Table 1. Output of SimpleAssociationRules

Let us consider the first row of the table, corresponding to the rule: ”People
who buy Dress, also buy Jeans”. For this row, $C(A)=4$, $C(B_{1})=2$,
$C(R_{1})=1$. The first counter reports the total number of people (anchor
node), the second the number of people who buy Dress (hence, Sofia and
Chiara), and the third the total number of people who buy both Dress and Jeans
(hence, just Sofia). Given these counters, the rule support is
$C(R_{1})/C(A)=0.25$, the rule confidence is $C(R_{1})/C(B_{1})=0.5$.

###  3.3. Association Rules with Many Items in the Body or Head

Next, we show association rules with many items in the body or head. Consider
the following MINE GRAPH RULE operator:

MINE GRAPH RULE SimpleAssociationRulesWithManyItems GROUPING ON (p:Person)
DEFINING BODY AS 1..2 (p)-[:BUY]-(X:Item) HEAD AS (p)-[:BUY]-(Y:Item)
EXTRACTING RULES WITH SUPPORT > 0.1 AND CONFIDENCE > 0.1

The operator extracts the association rules whose body consists of up to two
items, i.e., taking the form: ”People who buy X1 or X1 and X2, also buy Y”;
the body items are connected to the same anchor node person along the [:BUY]
relationship. The extracted association rules are reported in Table 2; note
that the header now includes two columns for the body, respectively denoted as
BuyX1 and BuyX2. The rows of the table also include the rules extracted by the
SimpleAssociationRules operator (with a missing entry for the BuyX2 column).
Three additional rows include two items in the body; among them, the rule of
the first row indicates that ”People who buy Dress and Jeans, also buy Shoes”.
Note that, for the first row, $C(A)=4$, $C(B_{1})=1$, $C(R_{1})=1$, hence the
rule has support 0.25 and confidence 1.

Body | Head | Support | Confidence
---|---|---|---
ItemsetB1 | ItemsetB2 | ItemsetH1
BuyX1 | BuyX2 | BuyY
Dress | Jeans | Shoes | 0.25 | 1
Dress | Shoes | Jeans | 0.25 | 0.5
Jeans | Shoes | Dress | 0.25 | 1
Dress | - | Jeans | 0.25 | 0.5
Dress | - | Shoes | 0.25 | 1
Jeans | - | Dress | 0.25 | 0.5
Jeans | - | Shoes | 0.25 | 0.5
Shoes | - | Dress | 0.5 | 1
Shoes | - | Jeans | 0.25 | 0.5
Shorts | - | T-shirt | 0.25 | 1
T-shirt | - | Shorts | 0.25 | 1

Table 2. Output of SimpleAssociationRulesWithManyItems

###  3.4. Association Rules with Where Conditions

The evaluation of association rules can be restricted by adding simple
predicates over the properties of variables defined in the MINE GRAH RULE
operator. For instance, it is possible to select the Person nodes by setting
their City to be “Rome”. Adding a condition does not change the structure of
the association rules, which are expressed as ”People (living in Rome) who buy
X, also buy Y”.

MINE GRAPH RULE ConditionedAssociationRules1 GROUPING ON (p:Person) WHERE
p.city = "Rome" DEFINING BODY AS (p)-[:BUY]-(X:Item) HEAD AS
(p)-[:BUY]-(Y:Item) EXTRACTING RULES WITH SUPPORT > 0.1 AND CONFIDENCE > 0.1

Clearly, the restriction may reduce the cardinality of the anchor nodes, and
thus produce different support and confidence for the extracted association
rules. In our simple instance, the predicate is satisfied by Sofia, Chiara,
and Fabio, hence $C(A)=3$. Table 3 reports the corresponding output.

Body | Head | Support | Confidence
---|---|---|---
BuyX | BuyY
Dress | Jeans | 0.33 | 0.5
Dress | Shoes | 0.67 | 1
Jeans | Dress | 0.33 | 1
Shoes | Dress | 0.67 | 1
Jeans | Shoes | 0.33 | 1
Shoes | Jeans | 0.33 | 0.5
Shorts | T-shirt | 0.33 | 1
T-shirt | Shorts | 0.33 | 1

Table 3. Output of ConditionedAssociationRules1

Similarly, it is possible to define simple predicates on the properties of
other variables of the body and head, for example by adding a restriction on
the items’ prices. The next example extracts the association rules: ”People
who buy X (with a price higher than 50), also buy Y (with a price higher than
50)”:

MINE GRAPH RULE ConditionedAssociationRules2 GROUPING ON (p:Person) DEFINING
BODY AS (p)-[:BUY]-(X:Item) HEAD AS (p)-[:BUY]-(Y:Item) WHERE X.Price > 50 and
Y.Price > 50 EXTRACTING RULES WITH SUPPORT > 0.1 AND CONFIDENCE > 0.1

###  3.5. Association Rules with CountRel

Next, we describe the use of the counting relations pattern, which is
introduced by the <countRel> non-terminal symbol in the grammar (Fig. 2). The
pattern allows setting a threshold on the number of times a type of
relationship should be present between any two nodes, in order to be selected
in the body or head of an association rule. The simplest example of
application is to impose, in the body of the rule, that a given item is
purchased several times. The operator should be used with a positive mincount
number to denote the threshold (<relType> > <mincount>). An example
application of the counting pattern is shown below:

MINE GRAPH RULE CountItemsAssociationRules GROUPING ON (p:Person) DEFINING
BODY AS (p)-[:BUY>1]-(X:Item) HEAD AS (p)-[:BUY]-(Y:Item) EXTRACTING RULES
WITH SUPPORT > 0.1 AND CONFIDENCE > 0.1

The association rules are expressed in the NL sentence: ”People who buy X more
than 1 time, also buy Y”. The corresponding output is shown in Table 4.

Body | Head | Support | Confidence
---|---|---|---
BuyMoreThan1X | BuyY
Dress | Jeans | 0.25 | 1
Dress | Shoes | 0.25 | 1
Shorts | T-shirt | 0.25 | 1

Table 4. Output of CountItemsAssociationRules

Considering the association rule in the third row: ”People who buy Shorts more
than 1 time, also buy T-shirt”, which associates people who buy the product
Shorts more than once with those who also buy T-shirt, Luca is the only person
satisfying both conditions. The relevant counters for this rule are: $C(A)=4$,
$C(B_{3})=1$, $C(R_{3})=1$, hence the rule has support 0.25 and confidence 1.

###  3.6. Association Rules with AnyRel

Next, we describe the use of the AnyRel pattern, which is introduced by the
<anyRel> non-terminal symbol in the grammar (Fig. 2). The pattern allows us to
connect a given node to any node reachable through any path (i.e., an
arbitrary sequence of relationships) within a maximum length. The simplest
example of application is to impose, in the body of the rule, that a given
item is reached through at most one link (more complex examples are shown
later). The operator should be used with a positive length number to denote
the path length. An example of the application is shown below:

MINE GRAPH RULE AnyPathAssociationRules GROUPING ON (p:Person) DEFINING BODY
AS (p)-[*<2]-(X:Item) HEAD AS (p)-[:BUY]-(Y:Item) EXTRACTING RULES WITH
SUPPORT > 0.1 AND CONFIDENCE > 0.1

Note that (:Item) nodes are reached from the (:Person) anchor nodes using
either the [:BUY] or the [:RECOMMEND] relationships; thus, in our scenario,
the NL sentence ”People with any link to X, also buy Y” can also be phrased as
”People who buy or recommend X, also buy Y”. The corresponding output is shown
in Table 5.

Body | Head | Support | Confidence
---|---|---|---
AnyLinkToX | BuyY
Dress | Jeans | 0.25 | 0.5
Dress | Shoes | 0.5 | 1
Jeans | Dress | 0.5 | 0.67
Jeans | Shoes | 0.5 | 0.67
Shoes | Dress | 0.5 | 0.67
Shoes | Jeans | 0.5 | 0.67
Shorts | Jeans | 0.25 | 0.5
Shorts | T-shirt | 0.25 | 0.5
T-shit | Shorts | 0.25 | 1

Table 5. Output of AnyPathAssociationRules

In order to better understand the output, consider the fourth association rule
of the table, i.e., ”People who buy or recommend Jeans, also buy Shoes”. As
usual, $C(A)=4$. Sofia, Chiara and Fabio buy or recommend Jeans, thus
$C(B_{4})=3$; out of them, just Sofia and Chiara buy Shoes, thus $C(R_{4})=2$.
Given these counters, the rule support is $C(R_{4})/C(A)=0.5$, the rule
confidence is $C(R_{4})/C(B_{4})=0.67$.

###  3.7. Association Rules with Relationships’ Chains

Next, we consider that <relPattern>s can be chained, in the body, in the head,
or in both of them; as the grammar has a recursive production (<patternTail>),
the length of the chain is not bound. We consider two simple examples, with
chains of length = 2.

####  3.7.1. First example

We consider a path in the body of the MINE GRAPH RULE operator, linking
purchased items to their categories, so as to include also categories in
resulting association rules. Consider the following operator:

MINE GRAPH RULE PathAssociationRules1 GROUPING ON (p:Person) DEFINING BODY AS
(p)-[:BUY]-(X:Item)-[:OF]-(C:Category) HEAD AS (p)-[:BUY]-(Y:Item) EXTRACTING
RULES WITH SUPPORT > 0.1 AND CONFIDENCE > 0.1

Note that the (:Category) nodes are reached from the (:Person) anchor nodes
along a chain of relationships, which uses the [:BUY] and [:OF] relationships;
the NL interpretation of the generated association rules is ”People who buy X
of category C, also buy Y”. The corresponding output is shown in Table 6.

Body | Head | Support | Confidence
---|---|---|---
ItemsetB1 | ItemsetH1
BuyX | CategoryC | BuyY
Dress | Casual | Jeans | 0.25 | 0.5
Dress | Casual | Shoes | 0.5 | 1
Jeans | Casual | Dress | 0.25 | 0.5
Shoes | Casual | Dress | 0.5 | 1
Shoes | Sportswear | Dress | 0.5 | 1
Shoes | Casual | Jeans | 0.25 | 0.5
Shoes | Sportswear | Jeans | 0.25 | 0.5
Shorts | Sportswear | T-shirt | 0.25 | 1
T-shirt | Sportswear | Shorts | 0.25 | 1

Table 6. Output of PathAssociationRules1

If we consider the first association rule, ”People who buy Dress of category
Casual also buy Jeans”, we note that Sofia and Chiara buy Dress of category
Casual but just Sofia buys Jeans; hence, with $C(A)=4$, we have $C(B_{1})=2$
and $C(R_{1})=1$. Given these the counters, the rule support is
$C(R_{1})/C(A)=0.25$, the rule confidence is $C(R_{1})/C(B_{1})=0.5$.

####  3.7.2. Second example

Exploiting the possibility of including where-clauses, we may select only
cases where the categories are different, perhaps the most interesting case
from an application perspective. This is expressed by the operator:

MINE GRAPH RULE PathAssociationRules2 GROUPING ON (p:Person) DEFINING BODY AS
(p)-[:BUY]-(X:Item)-[:OF]-(CX:Category) HEAD AS
(p)-[:BUY]-(Y:Item)-[:OF]-(CY:Category) WHERE CX <> CY EXTRACTING RULES WITH
SUPPORT > 0.1 AND CONFIDENCE > 0.1

The corresponding output is shown in Table 7.

Body | Head | Support | Confidence
---|---|---|---
ItemsetB1 | ItemsetH1
BuyX | CategoryCX | BuyY | CategoryCY
Dress | Casual | Shoes | Sportswear | 0.5 | 1
Jeans | Casual | Shoes | Sportswear | 0.25 | 0.5
Shoes | Sportswear | Dress | Casual | 0.5 | 1
Shoes | Sportswear | Jeans | Casual | 0.25 | 0.5

Table 7. Output of PathAssociationRules2

###  3.8. Association Rules with Ignore

The IGNORE construct designates a list of variables -i.e., nodes of the
pattern- that shall not be included in the body or head of the rule. We denote
as visible variables those appearing in the operator but not in the ignore
clause; only visible variables will appear in the body and head of association
rules.

For example, consider the following MINE GRAPH RULE operator:

MINE GRAPH RULE IgnoreAssociationRules GROUPING ON (p:Person) DEFINING BODY AS
(p)-[:BUY]-(X:Item)-[:OF]-(CX:Category) HEAD AS
(p)-[:BUY]-(Y:Item)-[:OF]-(CY:Category) IGNORE X,Y EXTRACTING RULES WITH
SUPPORT > 0.1 AND CONFIDENCE > 0.1

Extracted rules take the form ”People who buy items of category CX, also buy
items of category CY”. The corresponding output is shown in Table 8.

Body | Head | Support | Confidence
---|---|---|---
ItemsetB1 | ItemsetH1
BuyItemsOfCategoryCX | BuyItemsOfCategoryCY
Casual | Sportswear | 0.5 | 0.67
Sportswear | Casual | 0.5 | 0.67

Table 8. Output of IgnoreAssociationRules

Using IGNORE adds a second aggregation level to the normal procedure: in
particular, after having extracted the anchor nodes for body and head, they
are further grouped only with respect to the visible variables, thus hiding
the information of the ignored variables. Consider rule 1, ”People who buy
items of category Casual, also buy items of category Sportswear”. Sofia,
Chiara, and Fabio buy at least one item in the category Casual, resulting in
$C(B_{1})=3$, but Sofia and Chiara also buy items in the category Sportwear,
whereas Fabio does not buy any item in that category. As Fabio is not paired
to both the body and the head, Fabio is not a valid anchor for the association
rule, and $C(R_{1})=2$. As usual, with $C(A)=4$ the rule support is
$C(R_{1})/C(A)=0.5$, the rule confidence is $C(R_{1})/C(B_{1})=0.67$.

###  3.9. Association Rules with Conjunctions

Next, we consider that both the body and the head can have conjunctive
expressions, with an arbitrary number of conjuncts. We consider the body of
the MINE GRAPH RULE operator as a conjunction of two different <pattern>s.
Consider the following operator:

MINE GRAPH RULE ComplexBodyAssociationRules GROUPING ON (p:Person) DEFINING
BODY AS (p)-[:FOLLOW]-(X:Person) AND (p)-[:BUY]-(Y:Item) HEAD AS
(p)-[:BUY]-(Z:Item) EXTRACTING RULES WITH SUPPORT > 0.1 AND CONFIDENCE > 0.1

The association rules are interpreted in NL in this way: ”People who follow X
and buy Y, also buy Z”. The corresponding output is shown in Table 9.
Considering the first association rule, ”People who follow Sofia and buy
Dress, also buy Shoes”, we note that Chiara is the only one who both follows
Sofia and buys Dress, and she also buys Shoes; hence, with $C(A)=4$, we have
$C(B_{1})=1$ and $C(R_{1})=1$ and with these counters, the rule support is
$C(R_{1})/C(A)=0.25$ and the rule confidence is $C(R_{1})/C(B_{1})=1$.

Body | Head | Support | Confidence
---|---|---|---
ItemsetB1 | ItemsetB2 | ItemsetH1
FollowX | RecommendY | BuyZ
Sofia | Dress | Shoes | 0.25 | 1
Sofia | Shoes | Dress | 0.25 | 1
Sofia | Shorts | T-shirt | 0.25 | 1
Sofia | T-shirt | Shorts | 0.25 | 1
Chiara | Dress | Jeans | 0.25 | 1
Chiara | Dress | Shoes | 0.25 | 1
Chiara | Jeans | Dress | 0.25 | 1
Chiara | Jeans | Shoes | 0.25 | 1
Chiara | Shoes | Dress | 0.25 | 1
Chiara | Shoes | Jeans | 0.25 | 1
Chiara | Shorts | T-shirt | 0.25 | 1
Chiara | T-shirt | Shorts | 0.25 | 1
Fabio | Shorts | T-shirt | 0.25 | 1
Fabio | T-shirt | Shorts | 0.25 | 1

Table 9. Output of ComplexBodyAssociationRules

###  3.10. Other Complex Association Rules

####  3.10.1. First example.

We consider a body <pattern>, with two conjuncts both consisting of chains of
relationships. The following operator extracts rules whose NL interpretation
is ”People who follow more than two people who recommend products of category
CX and buy products of category CY, also buy Z”. The corresponding output is
shown in Table 10. Considering the first association rule, ”People who follow
more than two persons who recommend an item of category Sportswear and also
buy items of category Sportswear, also buy T-shirt”; we note that Luca is the
only one who both follows more than two persons -Chiara and Fabio-
recommending Shoes and Shorts of category Sportswear, and also buys items of
category Sportswear; therefore, with $C(A)=4$, we have $C(B_{1})=1$ and
$C(R_{1})=1$ and, with these counters, the rule support is
$C(R_{1})/C(A)=0.25$ and the rule confidence is $C(R_{1})/C(B_{1})=1$.

MINE GRAPH RULE MoreComplexBodyAssociationRules GROUPING ON (p:Person)
DEFINING BODY AS (p)-[:FOLLOW>2]-(PX:Person)
-[:RECOMMEND]-(X:Item)-[:OF]-(CX:Category) AND
(p)-[:BUY]-(Y:Item)-[:OF]-(CY:Category) HEAD AS (p)-[:BUY]-(Z:Item) IGNORE PX,
X, Y EXTRACTING RULES WITH SUPPORT > 0.1 AND CONFIDENCE > 0.1

Body | Head | Support | Confidence
---|---|---|---
ItemsetB1 | ItemsetB2 | ItemsetH1
FollowPersonRecommendItemOfCX | BuyItemOfCY | BuyZ
Sportswear | Sportswear | T-shirt | 0.25 | 1
Sportswear | Sportswear | Shorts | 0.25 | 1
Casual | Sportswear | T-shirt | 0.25 | 1
Casual | Sportswear | Shorts | 0.25 | 1

Table 10. Output of MoreComplexBodyAssociationRules

####  3.10.2. Second example.

Lastly, we consider a complex structure of the body <pattern> with WHERE
conditions on both anchors and nodes. The following operator extracts rules
whose NL interpretation is ”People who follow Chiara, who recommends items of
category CX, also buy items of the same category”. The corresponding output is
shown in Table 11. Considering the first association rule, ”People from Rome
who follow Chiara recommending items of category Casual, also buy Jeans, which
are of the same category Casual”, we note that there is only one person,
Sofia, who satisfies all these constraints, but also Luca follows Chiara
recommending Casual items; hence, with $C(A)=3$, we have $C(B_{1})=2$ and
$C(R_{1})=1$ and, with these counters, the rule support is
$C(R_{1})/C(A)=0.33$ and the rule confidence is $C(R_{1})/C(B_{1})=0.5$.

MINE GRAPH RULE VerifyInfluencerEffectivenessInRome GROUPING ON (p:Person)
WHERE p.city = "Rome" DEFINING BODY AS (p)-[:FOLLOW]-(PX:Person)
-[:RECOMMEND]-(X:Item)-[:OF]-(CX:Category) HEAD AS
(p)-[:BUY]-(Y:Item)-[:OF]-(CY:Category) WHERE PX.name = "Chiara" AND CX.name =
CY.name IGNORE PX, X EXTRACTING RULES WITH SUPPORT > 0.1 AND CONFIDENCE > 0.1

Body | Head | Support | Confidence
---|---|---|---
ItemsetB1 | ItemsetH1
FollowChiaraRecommendCX | BuyItem | CategoryCY
Casual | Jeans | Casual | 0.33 | 0.5
Casual | Dress | Casual | 0.33 | 0.5
Casual | Shoes | Casual | 0.33 | 0.5
Sportswear | Shoes | Sportswear | 0.33 | 0.5
Sportswear | T-shirt | Sportswear | 0.33 | 0.5
Sportswear | Shorts | Sportswear | 0.33 | 0.5

Table 11. Output of VerifyInfluencerEffectivenessInRome  Figure 5. Phases of
the MINE GRAPH RULE algorithm applied to a simple user-defined operator.
Phase(1) counts the anchor nodes with the label ‘Person’ $C(A)$. In Phase(2),
a query generating head and body for the operator is issued, and the query
results, which satisfy the minimum support threshold (expressed using absolute
counts), are entered into a table whose entries include the HEAD, the BODY,
and the rule cardinality $C(R_{i})$ In Phase(3), a query generating just the
body for the operator is issued and the query results are entered into a table
whose entries include the BODY and the BODY cardinality $C(B_{i})$. In the
final Phase(4) the output table is produced along a progression of five steps:
first, the two tables produced by phases 3 and 4 are joined on the BODY
columns; then, support and confidence for each record of the resulting table
are computed; then, rows that create tautologies or do not satisfy the minimum
confidence threshold are removed; then, the result is projected upon the
chosen schema; finally, resulting rows are streamed in output.

##  4\. Implementation

The MINE GRAPH RULE operator has been implemented in Java as a user-defined
Neo4j Procedure, mineGraphRule, and it is available as a portable Neo4j
plugin, like the other add-ons of the Awesome Procedures On Cypher (APOC)
library. We selected the Neo4j Graph database as a development platform since
it provides an easily expandable architecture. Still, our proposed algorithm
does not strictly depend on any specific Neo4j components and can be ported to
other openCypher-compatible databases.

Once the plugin is installed, the procedure can be invoked using its name
”apoc.mineGraphRule” in the Neo4j Cypher shell; it supports nine mandatory
parameters: the anchor’s variable, the anchor’s label, the conditions on the
anchor, a map structure for the HEAD itemSet, an identical structure for the
BODY itemSet, a list of predicates for the WHERE clause, a list of IGNOREd
variables, the minimum support threshold, and the minimum confidence
threshold. A detailed specification of the parameters’ format can be found in
the project’s repository (Invernici et al., 2024). Collectively, these nine
parameters provide a semi-structured version of the language of the MINE GRAPH
RULE operator.

Once executed, the procedure outputs a stream of records with a fixed format,
consisting of four fields; each record represents an association rule. The
fields are:

  * •

body a map of key-value pairs for the BODY columns. The keys are the names of
the columns and recall the structure of the pattern that they materialize,
while the values are the identifiers -i.e., properties- of the nodes of those
patterns;

  * •

head \- a map of key-value pairs for the HEAD columns with the same format of
the BODY;

  * •

support \- the support value in double floating-point precision;

  * •

confidence \- the confidence value in double floating-point precision.

The result can be transformed with the Cypher YIELD sub-clause(Neo4j Cypher
Manual, 2024), which can project the output record on some of its fields and
then apply any supported Cypher or APOC operation on them, such as reordering,
regrouping or string concatenation.

We next describe our algorithm by first considering a base case, where we do
not include conjunctions and multiple items in the BODY and in the HEAD. Then,
we consider the general case.

###  4.1. Algorithm for simple operators

In the translation of the operators we use a syntax-directed approach, in
which, for every production of the grammar, we generate an appropriate Cypher
expression. Therefore, chains are directly translated as MATCH blocks where
each link is translated to its appropriate Cypher expression (either a simple
relationship, or a relationship filtered on the basis of the number of edges,
or a bounded path with free-type relationships). In this way, our MINE GRAPH
RULE language, which includes a rich collection of orthogonal features, can be
expressed in a compact Cypher query, whose execution takes advantage of the
optimization capabilities of graph database engines. In this simple case, we
only need the following queries:

  * •

a query for retrieving the anchors’ cardinality $C(A)$ (see Sec. 3);

  * •

a query for retrieving HEAD, BODY, and rule’s cardinality $C(R_{i})$;

  * •

a query for retrieving BODY and body’s cardinality $C(B_{i})$.

The first query follows a simple structure and produces a variable counting
the number of anchors. The other two queries have a similar structure, which
is described as follows:

  1. (1)

MATCH subquery for anchors’ selection based on labels and on predicates that
are specific to anchors’ properties;

  2. (2)

MATCH on itemSets. All the patterns of HEAD and BODY are included in this
block, separated by commas;

  3. (3)

optional WHERE predicates, when operators include conditions on the variables;

  4. (4)

WITH clause to group by anchors and visible variables, to compute the rule
cardinality;

  5. (5)

WHERE predicate to guarantee minimum support;

  6. (6)

RETURN clause with the final names that are returned to the user at the end of
the procedure.

The difference from producing Cypher queries for rules and bodies is that, in
bodies, only elements from the body’s itemSets are included, while for rules
also elements from heads’ are included.

The actual association rules, with their support and confidence, are produced
after a final assembly of the results of the three described Cypher queries.
The complete flow of execution of the graph association rule mining algorithm
applied to a simple operator is shown in Fig. 5.

###  4.2. Algorithm for general operators

Figure 6. Phases of the MINE GRAPH RULE algorithm applied to an operator with
two patterns in conjunction in the body, each with many items, ranging
respectively from 1 to 3 and 1 to 2. This specific operator has been chosen to
explain how queries are expanded, queued, and possibly removed from the queue.
Phase(1) counts the anchor nodes with the label ‘Person’. Phase(2) generates
various nonredundant body-head pairs, named P1..P6, arranged in a directed
acyclic graph (DAG), each with a fixed number of items in the body’s
conjuncts; for each pair, the number of items of the body’s conjuncts are
highlighted (in red in the figure) - while descending along the DAG levels,
item numbers increase by 1, along the progression: [P1:(1,1)];
[P2:(2,1),P3:(1,2)]; [P4:(3,1),P5:(2,2)]; [P6(3,2)]. In Phase(3), the pairs
generated at Phase (2) are queued, by performing a breadth-first traversal of
the DAG; thus, the queue PQ: P1..P6 is generated. For each pair, a query
producing head and body is issued, and the query results are entered into a
table whose entries include the HEAD, the BODY, and the rule cardinality. As
explained in Fig. 5, Phase (2), only the rules that satisfy the minimum
support threshold are selected. At this stage, it is possible to remove some
pairs from the queue; if we assume that no rule extracted for pair P5
satisfies the constraint on the minimum support, then P5 can be removed from
the queue together with all the successors in the DAG (in this case, P6). In
Phase(4), for each remaining pair P1..P4, a query producing just the body for
that pair is generated, and the query results are entered into a table whose
entries include the BODY and the BODY cardinality. The final Phase(5) occurs
in the same way as described in Fig. 5, Phase (4).

We now consider general operators, i.e., those that include conjunctions and
multiple patterns in the BODY and/or in the HEAD. Inspired by the fast Apriori
algorithm implementation(Bodon, 2003), where the mining starts by exploring
the smaller and, thus, most common sets of frequent items and combines them
into bigger sets (while the minimum support threshold is met), our algorithm
starts by considering the operators with one pattern in the BODY and one in
the HEAD and then considers operators with more patterns, thus, performing a
body-head pair expansion. At each step, exactly one pattern is added either to
the BODY or to the HEAD, up to the maximum number of patterns in the input
operator. The body-head pairs are organized from the simplest to the most
complete one in a directed acyclic graph (DAG), as exemplified in Fig. 6,
Phase (2), for a particular example where the BODY has two patterns in
conjunction, where the first one ranges from 1 to 3 and the second one ranges
from 1 to 2.

Continuing our analogy with the Apriori algorithm, the objective of organizing
a DAG of pairs is to enable the early exclusion of pairs when their support
does not meet the minimum conditions set by the users. Thus, pairs are
considered in an order created by a breadth-first traversal of the DAG and, as
soon as one pair does not meet the threshold, the pair and all its descendants
are removed from the DAG. Each generation of queries corresponding to a given
pair is performed with the mechanism defined for simple input operators, as
illustrated in Fig. 5, Phases (3) and (4).

Note that tables HEAD+BODY and BODY accumulate the instances for all the
pairs. As discussed in Sec. 4.1, a final assembling step produces all the
association rules with their HEAD, BODY, support, and confidence.

Figure 7. Each graph reports the execution time required by a given MINE GRAPH
RULE operation over a graph generated with an increasing number of nodes; in
the graph generation, we use five different ratios (ranging from 0.5 to 0.9)
of the number of anchor nodes over the total nodes. By comparing graphs in
columns 1 and 2, we note that execution time increases in $O(nodes)$, with a
shorter execution time in case A1 (see Sec. 3.2, where just the BUY edges are
traversed) w.r.t. case A2 (see Sec. 3.6, requiring the traversal of both the
BUY and the RECOMMEND edges). In A1, A2, and A3, higher ratios are associated
with lower execution times, as a higher number of anchors corresponds to a
lower number of BUYs; for Scale-free graphs instead, when the ratio increases,
the number of BUYs follows the behavior described in the database generation
process; as a result, in B1 and B2 diagrams, graphs with a lower ratio of
anchor nodes have comparatively better performances. Lastly, A4, B4, and C4
plots vertically overlap significantly more than the others; this can be
explained by considering that the operator needs to evaluate the combination
of BUYs and FOLLOWs, which is more dependent on the dimension of the graph,
but less dependent on the ratio. When comparing Scale-free vs. Large Scale-
free graphs, performances associated with the former set seem to be slightly
improved, as, thanks to the higher relationship density, the latter extracts
more rules: at 50K nodes and 0.5 ratio, for B1 and B2 the operator extract
respectively 27,327 and 117,129 rules, whereas for C1 and C2 the numbers of
extracted rules increase to 111,174 and 290,234.

##  5\. Evaluation

To assess the performance of the MINE GRAPH RULE operator, we conducted a
series of evaluations over a combination of synthetic datasets and query
complexities of the operator.

##### Configuration

We run the experiments on our dedicated server machine with a 56-core Intel
E5-2660 v4 CPU and 384 GB of RAM. We deployed a Neo4j database instance from
its 5.15.0-community-bullseye Docker image. To avoid memory bottlenecks, we
configured the database with the following settings:

    server.memory.heap.initial_size=230G
    server.memory.heap.max_size=230G
    dbms.memory.pagecache.size=200G

###  5.1. Synthetic databases generation

For our evaluation tests, we generated synthetic datasets that adhere to the
same schema as the previously reported motivating example. We generated three
types of synthetic datasets:

  * •

The first one with a uniform distribution of all the edges between random
nodes of the graph, ensuring that relationships are evenly spread.

  * •

The second one, named scale-free, with a power-law distribution of the
relationship BUY, in order to better represent the real-case scenario of an
online shop; all the other relationships are generated with a uniform
distribution among all nodes.

  * •

The third one, named large scale-free, with the same distribution of
relationships as the scale-free graph, but with higher density of
relationships BUY.

For each type of synthetic dataset, we generated multiple versions varying the
total number of nodes of the graph to test the scalability performance
according to the dimensions of the graph. In addition, for each graph
instance, we also varied the ratio of anchor nodes (in our example, nodes with
label Person), which directly impacts the absolute count of BUY relationships
within a graph. In Uniform graphs, the total count of BUY is proportional to
the product of the number of Person nodes with the number of Item nodes, which
is maximum when the graph is evenly split between Persons and Items.
Therefore, increasing the ratio over 0.5 would produce less BUY relationships.
For Scale-free distribution instead, graphs have a fixed smaller portion of
Items that are way more likely to be bought, and increasing the percentage of
Persons results in a higher number of BUY relationships; therefore, in graphs
with Scale-free distribution, the ratio of anchor nodes has a nonlinear
relationship with the total count of BUY edges. Scale-free distributions mimic
the classical distribution of items’ purchases ((Mahanti et al., 2013; Fenner
et al., 2010)).

###  5.2. Experimental Result

We evaluated the scalability of our operator in multiple settings.

##### General Scalability

To assess the general scalability of the operator, we evaluated the execution
time of four different expressions: Simple, AnyRel, Ignore, and Conjunctions
referencing the examples respectively reported in Sec. 3.2, 3.6, 3.8 and 3.9.
In Fig. 7, we compared their performance with fixed values of support and
confidence (set to 0.0001) on different synthetic graphs, varying not only the
distribution of relationship BUY (respectively Uniform, Scale-free and Large
Scale-free) but also their dimensions (from 10K nodes to 100K nodes) and the
ratios between anchor and total number nodes (from 0.5 to 0.9).

##### Impact of Support Selection

To evaluate the effect of the support on the temporal performances of the
operator, in Fig. 8 we focused on two expressions of the operator, Simple and
Many Items (respectively reported in Sec. 3.2 and 3.3), testing them with
fixed values of confidence (0.0001) on synthetic graphs with different
distributions and increasingly large number of nodes (from 10K to 100K).

##### High Volume Scalability

Lastly, focusing on the operator Simple (see Sec. 3.2), we evaluated the high
volume scalability with a fixed value for support and confidence (both at
0.0001) and an increasing number of nodes (up to 500K). In Fig. 9, we compared
two different values of ratios of anchor nodes over item nodes (0.8 in blue
and 0.9 in green).

Figure 8. Each graph reports the execution time required by Simple (see Sec.
3.2 – blue color) and Many Items (see Sec. 3.3 – orange color) MINE GRAPH RULE
operations over graphs generated with increasing numbers of nodes, by fixing
the anchor nodes over the total nodes ratio (equal to 0.8). Each column
corresponds to increasing values of support (respectively 0.01, 0.001, and
0.0001); confidence is set at 0.0001. In A1, A2, and A3, the plots overlap,
suggesting that increasing the cardinality of the Items in the body does not
affect the performance; with a Uniform relationship distribution, no
association rules are extracted, with the exception of case A3, 30K nodes,
where instead four association rules are produced and thus required execution
time is slightly higher. In Scale-free graphs, having some Items with higher
probability to be bought results in extracting rules that activate the branch
of the algorithm that would perform additional queries for higher
cardinalities ultimately making the Many Items expression slower (see Sec.
4.2). For instance, in B3 at 50K nodes, Simple extracts 2,630 rules while Many
Items extracts 10,697 rules.  Figure 9. High Volume Scalability

##  6\. Conclusion

We presented a new operator for mining association rules from a graph
database. All the interactions with the database rely on a translation
mechanism that transforms any operator expression into a set of pure Cypher
queries, according to the topological, logical, and cardinality constraints
expressed by the operator. We exploit the pattern-matching capabilities of
Cypher for locating the relevant portions of the graph, taking advantage of
the optimizations provided by the database’s query-planning engine for any
arbitrary existing graph, without resorting to schema-dependant tuning or
heuristics, which are impossible to know at the tool’s compile time. Our
implementation embeds the Apriori approach at a set-oriented level, thereby
taking full advantage of the optimization provided by all commonly used graph
database engines.

Prospectively, we expect that the proposed operator will enable fast and fully
explainable association rules mining over production scale knowledge graphs in
several applied domains. Examples may include academic author-citation
networks (e.g., to investigate areas of collaboration or common patterns in
domains that are similar), actor-movie-director networks (e.g., to uncover
promising artistic collaborations that increase chances of prizes), customer-
order-product networks (e.g., to pinpoint complex customer behavior and
targeted marketing/discount policies), or playlist-song graphs (e.g., to
suggest favorable compilation combinations for users).

While the provided working implementation is specific for Neo4j, the
syntax/semantics of the operator are as general as possible; the principles
followed in the implementation can be applied to any graph database. Our
approach can be exploited to pave the way for standardizing the association
rules mining process in graph databases (making it as natural as it has become
for relational databases) along the guiding lines for graph analytics
indicated by the graph community (Sakr et al., 2021).

## Resources

The source code of the implementation of the mineGraphRule plugin for Neo4j,
examples of usage, and the scripts to generate the evaluation datasets are
available on GitHub (Invernici et al., 2024).

###### Acknowledgements.

Stefano Ceri is supported by the PNRR-PE-AI FAIR project, funded by the
NextGenerationEU program.

## References

  * (1)
  * apy (2019) 2019\.  Apyori.  https://github.com/ymoch/apyori.
  * dbr (2024) 2024\.  DB-Engines Ranking of Graph DBMS.  https://db-engines.com/en/ranking/graph+dbms.  Last accessed online: June 26th, 2024.
  * Aggarwal (2011) Charu C Aggarwal. 2011.  _An introduction to social network data analytics_.  Springer.
  * Agrawal et al. (1993) Rakesh Agrawal, Tomasz Imieliński, and Arun Swami. 1993.  Mining association rules between sets of items in large databases. In _Proceedings of the 1993 ACM SIGMOD international conference on Management of data_. 207–216.
  * Agrawal et al. (1994) Rakesh Agrawal, Ramakrishnan Srikant, et al. 1994\.  Fast algorithms for mining association rules. In _Proc. 20th int. conf. very large data bases, VLDB_ , Vol. 1215. Santiago, 487–499.
  * APOC Library (2024) APOC Library. 2024.  Awesome Procedures for Neo4j 5.18.x.  https://github.com/neo4j/apoc.  Last accessed online: June 26th, 2024.
  * Bodon (2003) Ferenc Bodon. 2003.  A fast APRIORI implementation. In _FIMI_ , Vol. 3. Citeseer, 63.
  * Campi and Palese (2021) Alessandro Campi and Corrado Palese. 2021.  Twitter Association Rule Mining using Clustering and Graph Databases. In _2021 the 5th International Conference on Information System and Data Mining_. 90–95.
  * Changchien and Lu (2001) S Wesley Changchien and Tzu-Chuen Lu. 2001.  Mining association rules procedure to support on-line recommendation by customers and products fragmentation.  _Expert systems with applications_ 20, 4 (2001), 325–335.
  * Ciftçi et al. (2021) Okan Ciftçi, Samet Tenekeci, et al. 2021\.  Artist recommendation based on association rule mining and community detection. In _Proceedings of the 13th International Joint Conference on Knowledge Discovery, Knowledge Engineering and Knowledge Management-KDIR_. SCITEPRESS.
  * Fan et al. (2022) Wenfei Fan, Wenzhi Fu, Ruochun Jin, Ping Lu, and Chao Tian. 2022.  Discovering association rules from big graphs.  _Proc. VLDB Endow._ 15, 7 (mar 2022), 1479–1492.
  * Fan et al. (2015) Wenfei Fan, Xin Wang, Yinghui Wu, and Jingbo Xu. 2015.  Association rules with graph patterns.  _Proceedings of the VLDB Endowment_ 8, 12 (2015), 1502–1513.
  * Fenner et al. (2010) Trevor Fenner, Mark Levene, and George Loizou. 2010.  Predicting the long tail of book sales: Unearthing the power-law exponent.  _Physica A: Statistical Mechanics and Its Applications_ 389, 12 (2010), 2416–2421.
  * Fernandes et al. (2018) Diogo Fernandes, Jorge Bernardino, et al. 2018\.  Graph Databases Comparison: AllegroGraph, ArangoDB, InfiniteGraph, Neo4J, and OrientDB.  _Data_ 10 (2018), 0006910203730380.
  * Francis et al. (2018) Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Petra Selmer, and Andrés Taylor. 2018.  Cypher: An evolving query language for property graphs. In _Proceedings of the 2018 International Conference on Management of Data_. Association for Computing Machinery, New York, NY, USA, 1433–1445.
  * Hegland ([n.d.]) Markus Hegland. [n.d.].  _The Apriori algorithm - A tutorial_.  209–262.  https://doi.org/10.1142/9789812709066_0006
  * Invernici et al. (2024) Francesco Invernici, Francesco Cambria, Anna Bernasconi, and Stefano Ceri. 2024.  GitHub repository of mineGraphRule.  https://github.com/FrInve/mine_graph_rule.  Last accessed online: June 26th, 2024.
  * Jouili and Vansteenberghe (2013) Salim Jouili and Valentin Vansteenberghe. 2013.  An empirical comparison of graph databases. In _2013 International Conference on Social Computing_. IEEE, 708–715.
  * Kaur et al. (2015) Manjit Kaur, Urvashi Garg, and Sarbjit Kaur. 2015.  Advanced eclat algorithm for frequent itemsets generation.  _International Journal of Applied Engineering Research_ 10, 9 (2015), 23263–23279.
  * Lin et al. (2002) Weiyang Lin, Sergio A Alvarez, and Carolina Ruiz. 2002.  Efficient adaptive-support association rule mining for recommender systems.  _Data mining and knowledge discovery_ 6 (2002), 83–105.
  * Mahanti et al. (2013) Aniket Mahanti, Niklas Carlsson, Anirban Mahanti, Martin Arlitt, and Carey Williamson. 2013.  A tale of the tails: Power-laws in internet measurements.  _IEEE Network_ 27, 1 (2013), 59–64.
  * Meo et al. (1996) Rosa Meo, Giuseppe Psaila, Stefano Ceri, et al. 1996\.  A new SQL-like operator for mining association rules. In _VLDB_ , Vol. 96. Citeseer, 122–133.
  * Moniruzzaman and Hossain (2013) ABM Moniruzzaman and Syed Akhter Hossain. 2013.  Nosql database: New era of databases for big data analytics-classification, characteristics and comparison.  _arXiv preprint arXiv:1307.0191_ (2013).
  * Nahar et al. (2013) Jesmin Nahar, Tasadduq Imam, Kevin S Tickle, and Yi-Ping Phoebe Chen. 2013.  Association rule mining to detect factors which contribute to heart disease in males and females.  _Expert systems with applications_ 40, 4 (2013), 1086–1093.
  * Neo4j Cypher Manual (2024) Neo4j Cypher Manual. 2024.  CALL Procedure.  https://neo4j.com/docs/cypher-manual/current/clauses/call.  Last accessed online: June 26th, 2024.
  * Osadchiy et al. (2019) Timur Osadchiy, Ivan Poliakov, Patrick Olivier, Maisie Rowland, and Emma Foster. 2019.  Recommender system based on pairwise association rules.  _Expert Systems with Applications_ 115 (2019), 535–542.
  * Parviainen et al. (2017) Päivi Parviainen, Maarit Tihinen, Jukka Kääriäinen, and Susanna Teppola. 2017.  Tackling the digitalization challenge: how to benefit from digitalization in practice.  _International journal of information systems and project management_ 5, 1 (2017), 63–77.
  * Priyadarshini and Mishra (2010) Sadhana Priyadarshini and Debahuti Mishra. 2010.  A hybridized graph mining approach. In _Information and Communication Technologies: International Conference, ICT 2010, Kochi, Kerala, India, September 7-9, 2010. Proceedings_. Springer, 356–361.
  * Raja and Balakrishnan (2012) N Balaji Raja and G Balakrishnan. 2012.  An Innovative Approach to Association Rule Mining Using Graph and Clusters. In _Advances in Computer Science and Information Technology. Computer Science and Information Technology: Second International Conference, CCSIT 2012, Bangalore, India, January 2-4, 2012. Proceedings, Part III 2_. Springer, 59–67.
  * Raschka (2018) Sebastian Raschka. 2018.  MLxtend: Providing machine learning and data science utilities and extensions to Python’s scientific computing stack.  _The Journal of Open Source Software_ 3, 24 (April 2018).  https://doi.org/10.21105/joss.00638
  * Robinson et al. (2015) Ian Robinson, Jim Webber, and Emil Eifrem. 2015.  _Graph databases: new opportunities for connected data_.  ”O’Reilly Media, Inc.”.
  * Sakr et al. (2021) Sherif Sakr, Angela Bonifati, Hannes Voigt, Alexandru Iosup, Khaled Ammar, Renzo Angles, Walid Aref, Marcelo Arenas, Maciej Besta, Peter A Boncz, et al. 2021\.  The future is big graphs: a community view on graph processing systems.  _Commun. ACM_ 64, 9 (2021), 62–71.
  * Santoso (2021) M Hamdani Santoso. 2021.  Application of Association Rule Method Using Apriori Algorithm to Find Sales Patterns Case Study of Indomaret Tanjung Anom.  _Brilliance: Research of Artificial Intelligence_ 1, 2 (2021), 54–66.
  * Sen et al. (2021) Sudipta Sen, Akash Mehta, Runa Ganguli, and Soumya Sen. 2021.  Recommendation of influenced products using association rule mining: Neo4j as a case study.  _SN Computer Science_ 2 (2021), 1–17.
  * Shanmugasundaram et al. (1999) Jayavel Shanmugasundaram, Kristin Tufte, Chun Zhang, Gang He, David J. DeWitt, and Jeffrey F. Naughton. 1999.  Relational Databases for Querying XML Documents: Limitations and Opportunities.  (1999), 302–314.
  * Si et al. (2019) Huayou Si, Jiayong Zhou, Zhihui Chen, Jian Wan, Neal N Xiong, Wei Zhang, and Athanasios V Vasilakos. 2019.  Association rules mining among interests and applications for users on social networks.  _IEEE Access_ 7 (2019), 116014–116026.
  * Srikant and Agrawal (1997) Ramakrishnan Srikant and Rakesh Agrawal. 1997.  Mining generalized association rules.  _Future generation computer systems_ 13, 2-3 (1997), 161–180.
  * Standl and Schlomske-Bodenstein (2021) Bernhard Standl and Nadine Schlomske-Bodenstein. 2021.  A pattern mining method for teaching practices.  _Future Internet_ 13, 5 (2021), 106.
  * Stilou et al. (2001) S Stilou, Panagiotis D Bamidis, Nicos Maglaveras, and Constantinos Pappas. 2001.  Mining association rules from clinical databases: an intelligent diagnostic process in healthcare.  _Studies in health technology and informatics_ 2 (2001), 1399–1403.
  * Tandan et al. (2021) Meera Tandan, Yogesh Acharya, Suresh Pokharel, and Mohan Timilsina. 2021.  Discovering symptom patterns of COVID-19 patients using association rule mining.  _Computers in biology and medicine_ 131 (2021), 104249.
  * Tiwari et al. (2010) Vivek Tiwari, Vipin Tiwari, Shailendra Gupta, and Renu Tiwari. 2010.  Association rule mining: A graph based approach for mining frequent itemsets. In _2010 International Conference on Networking and Information Technology_. IEEE, 309–313.
  * Vanetik et al. (2006) Natalia Vanetik, Solomon Eyal Shimony, and Ehud Gudes. 2006.  Support measures for graph data.  _Data Mining and Knowledge Discovery_ 13, 2 (2006), 243–260.
  * Vicknair et al. (2010) Chad Vicknair, Michael Macias, Zhendong Zhao, Xiaofei Nan, Yixin Chen, and Dawn Wilkins. 2010.  A comparison of a graph database and a relational database: a data provenance perspective. In _Proceedings of the 48th annual Southeast regional conference_. 1–6.
  * Wang et al. (2020) Xin Wang, Yang Xu, and Huayi Zhan. 2020.  Extending association rules with graph patterns.  _Expert Systems with Applications_ 141 (2020), 112897.
  * Zaki (2000) Mohammed Javeed Zaki. 2000.  Scalable algorithms for association mining.  _IEEE transactions on knowledge and data engineering_ 12, 3 (2000), 372–390.
  * Zhang et al. (2022) Zhenghao Zhang, Jianbin Huang, and Qinglin Tan. 2022.  Association rules enhanced knowledge graph attention network.  _Knowledge-Based Systems_ 239 (2022), 108038.