Association Rule Mining of Relational Data
objects. Problems related to skewing are, thereby, also studies tree based patterns that can represent general
encountered in this approach. graphs by repeating node labels in the tree (Goethals A
An alternative to the ILP approach is to apply the et al., 2005). These graph-based approaches differ
standard definition of association rule mining to rela- from the previous relational approaches in that they do
tions that are joined using the relational join operation. not consider a universal key or record type as the unit
While such an approach is less general it is often more of support counts. For example, in (Besemann et al.,
efficient since the join operation is highly optimized 2004) the rows for each join definition are considered
in standard database systems. It is important to note the transactions therefore the universal key is the join
that a join operation typically changes the support of an “shape” itself. Relational approaches “roll-up” to a
item set, and any support calculation should therefore common level such as single nodes. Thus graph-based
be based on the relation that uses the smallest number rule discovery must be performed in a level-by-level
of join operations (Cristofor & Simovici, 2001). basis based on each shape or join operation and by the
Defining rule interest is an important issue in number of items.
any type of association rule mining. In traditional A typical example of an association rule mining
association rule mining the problem of rule interest problem in graphs is mining of annotation data of
has been addressed in a variety of work on redundant proteins in the presence of a protein-protein interaction
rules, including closed set generation (Zaki, 2000). graph (Oyama et al., 2002). Associations are extracted
Additional rule metrics such as lift and conviction that relate functions and localizations of one protein
have been defined (Brin et al., 1997). In relational as- with those of interacting proteins. Oyama et al. use
sociation rule mining the problem has been approached association rule mining, as applied to joined relations,
by the definition of a deviation measure (Dehaspe & for this work. Another example could be association
Toivonen, 2001). Relational data records have natural rule mining of attributes associated with scientific
dependencies based on the relational link structure. publications on the graph of their mutual citations
Patterns derived by traversing the link structure will (Rahal et al., 2006).
also include dependencies. Therefore it is desirable A problem of the straight-forward approach of
to develop algorithms that can identify these natural mining joined tables directly becomes obvious upon
dependencies. Current relational and graph-based pat- further study of the rules: In most cases the output is
tern mining does not consider intra-pattern dependency. dominated by rules that involve the same item as it
In general it can be noted that relational data mining occurs in different entity instances that participate in
poses many additional problems related to skewing of a relationship. In the example of protein annotations
data compared with traditional mining on a single table within the protein interaction graph this is expressed
(Jensen & Neville, 2002). in rules like:
Relations that Represent a graph {protein(A), protein(B), interaction(A, B), location(A,
nucleus)}{location(B, nucleus)}
One type of relational data set has traditionally received
particular attention, albeit under a different name. A that states if one of two interacting proteins is in
relation representing a relationship between entity the nucleus then the other protein will also be in the
instances of the same type, also called a reflexive rela- nucleus. Similarities among relational neighbors have
tionship, can be viewed as the definition of a unipartite been observed more generally for relational databases
graph. Graphs have been used to represent social net- (Macskassy & Provost, 2003). It can be shown that
works, biological networks, communication networks, filtering of output is not a consistent solution to this
and citation graphs, just to name a few. Traditional problem, and items that are repeated for multiple nodes
graph-based approaches focus on connectivity only should be eliminated in a preprocessing step (Besemann
and are discussed in the related research section. et al., 2004). This is an example of a problem that
Recent work extends the field of graph-based patterns does not occur in association rule mining of a single
to multiple properties on nodes (Oyama et al., 2002; table and requires special attention when moving to
Besemann et al., 2004; Rahal et al., 2006; Besemann et multiple relations. The example also highlights the
al., 2006; Besemann et al., 2007). Other recent work