Pattern mining in dynamic graphs has received a lot of attention in recent years. However, proposed methods are typically limited to specific classes of patterns expressing only a specific types of changes. In this paper, we propose a new algorithm, DGRMiner, which is able to mine patterns in the form of graph rules capturing various types of changes, i.e. addition and deletion of vertices and edges, and relabeling of vertices and edges. This algorithm works both with directed and undirected dynamic graphs with multiedges. It is designed both for the singledynamic-graph and the set-of-dynamic-graphs scenarios. The performance of the algorithm has been evaluated by using two real-world and two synthetic datasets.
Data mining of complex structures has been extensively
studied for quite a while. Recently, more attention has
been drawn to the area of dynamic graphs, i.e. graphs
evolving through time. A lot of research has been
carried out both from the global and local perspectives of
dynamic graphs. For instance, global characteristics such as
density and diameter were studied in real dynamic graphs
in [
Nevertheless, most of the pattern mining methods for
dynamic graphs impose various restrictions, such as the
type of the dynamic graphs or the type of changes
captured by such patterns. For example, GERM algorithm [
In this paper, we propose a new algorithm DGRMiner for mining frequent patterns that can capture various changes in dynamic graphs. Specifically, the patterns are in the form of predictive rules expressing how a subgraph can be changed into another subgraph by adding new vertices and edges, deleting specific vertices and edges, or relabeling vertices and edges. An example of a dynamic graph and two predictive rules are illustrated in Fig. 1.
The algorithm is able to mine patterns from a single dynamic graph and also from a set of dynamic graphs. Such graph rules are useful for prediction in dynamic graphs, they can be used as pattern features representing dynamic graphs or simply for gaining an insight into internal processes of the graphs.
The paper is organized as follows. Section 2 gives the
necessary definitions and presents the representation of
dynamic graphs. Section 3 then provides a short
description of the gSpan algorithm [
In this section, we provide definitions of a dynamic graph and predictive rules. Definitions of significance measures support and confidence are also part of this section. 2.1
Before defining a dynamic graph, we need to consider the notion of a static graph. In this paper, by a static graph we will denote a directed labeled multigraph without loops and with a restriction that no two edges with the same source and target vertices can have the same label. The proposed mining algorithm, however, can work with undirected edges too. For the sake of simplicity, we will restrict ourselves only to directed graphs in this section. Definition 1 (Static graph). A static graph is a 5-tuple G = (VG, EG, fG, lG,V , lG,E ), where VG is a set of vertices, EG is a set of edges, fG : EG → VG × VG is a map assigning a pair of vertices (u, v), u 6= v, to every edge, lG,V and lG,E are two maps describing labeling of the vertices and edges, respectively. Furthermore, ∀e1, e2 ∈ EG( f (e1) = f (e2) ⇒ lE (e1) 6= lE (e2)).
A dynamic graph is then given by a finite sequence of static graphs in which no two adjacent graphs are identical as we want to capture only the changes in the dynamic graph. Moreover, we extend each static graph G by timestamp functions tG,V : VG → T and tG,E : EG → T , which map each vertex and edge to a point in time. We will work with discretized time and thus T will be the set of integers, i.e. T = Z.
Definition 2 (Dynamic graph). A dynamic graph is a finite sequence DG = (G1, G2, ..., Gn), where Gi is a static graph extended by timestamp functions tGi,V , tGi,E for all 1 ≤ i ≤ n, and G j 6= G j+1 for all 1 ≤ j ≤ n-1. Graph Gi is referred to as the snapshot of DG at time i. In addition, for each 1 ≤ i ≤ n, the timestamp functions tGi,V , tGi,E assign to each vertex and edge the time from which they have their current label, i.e. tGi,V (v) = min( j|1 ≤ j ≤ i ∧ ∀k, j ≤ k ≤ i, v ∈ VGk ∧ lGk,V (v) = lGi,V (v)) and similarly for tGi,E (e).
As we want to capture patterns with rich information, we will also assume that the dynamic graph keeps track of the deleted vertices and edges, but only until they are added back into the graph. For example, consider the dynamic graph in Fig. 1 with five snapshots. Then tG1,V (v1) = 1, tG4,V (v5) = 3, etc. Also notice the edge between vertices v3 and v1 in snapshot G3. It is deleted in snapshot G4 but we keep information about this deleted edge in this snapshot. This information is discarded in snapshot G5 because a new edge with exactly the same information is added there. 2.2
The aim of the mining algorithm is to find predictive graph rules, i.e. rules expressing how a subgraph of a snapshot will most likely change in future. As we want to incorporate the time information into the rules and at the same time we are interested in mining general patterns which are not tied to absolute time, we need to use relative timestamps for rules. A relative timestamp equal to 0 will denote a current change and timestamp equal to −t will denote a change that happened t snapshots earlier. Now we can define predictive graph rules as follows.
Definition 3 (Predictive Graph Rule). Let GA, GC be two static graphs with timestamp functions tGA,V , tGA,E , tGC,V , tGC,E restricted to range (−∞, 0] such that union graph1 of GA and GC is a connected graph and exactly one of the following conditions holds: 1A graph created from union of vertices and edges. i. VGA = 0/ ∧ VGC 6= 0/ ∧ ∀v ∈ VGC (tGC,V (v) = 0) ∧ ∀e ∈ EGC (tGC,E (e) = 0) ii. VGA 6= 0/ ∧ VGC = 0/ iii. (VGA ∩ VGC 6= 0/)∧ (∃v ∈ VGC (tGC,V (v) = 0) ∨ ∃e ∈ EGC (tGC,E (e) = 0))∧ (∀v ∈ VGC r VGA (tGC,V (v) = 0))∧ (∀e ∈ EGC r EGA (tGC,E (e) = 0))∧ (∀v ∈ VGA ∩VGC ((tGC,V (v) = tGA,V (v) − 1 ∧ lGC,V (v) = lGA,V (v)) ∨ (0 = tGC,V (v) ≥ tGA,V (v) ∧ lGC,V (v) 6= lGA,V (v)))∧ (∀e ∈ EGA ∩ EGC ( fGC (e) = fGA (e) ∧ ((tGC,E (e) = tGA,E (e) − 1 ∧ lGC,E (e) = lGA,E (e)) ∨ (0 = tGC,E (e) ≥ tGA,E (e) ∧ lGC,E (e) 6= lGA,E (e))))
Then we say that GA ⇒ GC is a predictive graph rule, where GA is called antecedent and GC consequent.
The first two conditions in the above definition cover situations in which the rules express either addition of an isolated graph into a dynamic graph or a deletion of a subgraph from a dynamic graph. The third condition covers situations in which one subgraph is transformed into another subgraph. Here, we require VGA ∩ VGC 6= 0/ because we are not interested in rules consisting of unrelated graphs. In addition, we require the rule to contain at least one change related to a vertex or an edge. Vertices and edges occurring only in consequent must have timestamp equal to 0 as they represent an addition. For vertices and edges common for both graphs we require that they either were not changed a thus their relative timestamps differ by one, or they were changed and thus their timestamp cannot be lower in the consequent. Moreover, we cannot change edges by reorienting them, i.e. we would have to delete the original edge and add a new one with the opposite orientation. Lastly, as we keep track of the deleted edges and vertices in the dynamic graph, the predictive rules can also contain these deleted vertices and edges. It does not pose any restriction to the patterns, contrariwise it can only help us capture more information in the patterns in case such information is present in the dynamic graph.
In Fig. 1 we can see two examples of graph prediction rules. Both rules depict changes in connection and also label changes. There is also a vertex with label A in both rules which is not changed and thus its timestamp is decreased by one in the consequent.
In order to select only interesting rules, various measures of significance are typically used. Here, we use support and confidence. As we use relative timestamps for graphs in rules, we also need to provide the notion of an occurrence of such a graph in the given dynamic graph. Definition 4 (Occurrence of a rule graph). Let G be a graph used in a rule, say in antecedent without loss of generality, with timestamp functions tG,V , tG,E , and let DG = (G1, ..., Gi, ..., Gn) be a dynamic graph. We say that G occurs in snapshot Gi, written as G v Gi, if there exists a function ϕ : VG → VGi such that: i. ∀u ∈ VG(ϕ (u) ∈ VGi ∧ lG,V (u) = lGi,V (ϕ (u)) ∧ tG,V (u) = tGi,V (ϕ (u)) − i), ii. ∀e ∈ EG( fG(e) = (u, v) ⇒ ∃!e0 ∈ EGi ( fGi (e0) = (ϕ (u), ϕ (v)) ∧ lG,E (e) = lGi,E (e0) ∧ tG,E (e) = tGi,E (e0) − i) Definition 5 (Support and Confidence). Let GA ⇒ GC be a rule and DG = (G1, ..., Gi, ..., Gn) a dynamic graph. We define support of GA ⇒ GC, support of GA, and confidence of GA ⇒ GC as follows: σDG(GA ⇒ GC) = |{i|GA v Gi, GC v Gi+1,
1 ≤ i ≤ n − 1}|/(n − 1) σDG(GA) = |{i|GA v Gi, 1 ≤ i ≤ n − 1}|/(n − 1) con fDG(GA ⇒ GC) = σDG(GA ⇒ GC)/σDG(GA) dynamic graphs DGS = we extend these definitions as
For a set of {DG1, DG2, ..., DGm} follows: σDGS(GA ⇒ GC) = |{i|σDGi (GA ⇒ GC) > 0,
1 ≤ i ≤ m}|/m σDGS(GA) = |{i|σDGi (GA) > 0, 1 ≤ i ≤ m}|/m con fDGS(GA ⇒ GC) = σDGS(GA ⇒ GC)/σDGS(GA)
Thus, support of a rule for a single dynamic graph expresses the fraction of snapshots that were changed by the rule. For a set of dynamic graphs, we count the fraction of dynamic graphs that had at least one snapshot changed by the rule. Confidence expresses the frequency of such a change if we observe an occurrence of the antecedent. For example, both rules in Fig. 1 have support equal to 0.25 and confidence equal to 1.
Given a minimum support value σmin and a minimum confidence value con fmin, the task is to find all predictive graph rules for which σ ≥ σmin and con f ≥ con fmin.
gSpan Revisited
The novel algorithm for mining predictive graph rules
employs the framework of the gSpan algorithm [
gSpan [
gSpan starts from single-edge patterns and extends these patterns edge by edge to create larger patterns. Each such pattern can be encoded by a DFS (Depth-First Search) code. A DFS code of a pattern represents a specific DFS traversal of the pattern and it is represented by a list of 5-tuples (i, j, li, l(i, j), l j). Such a 5-tuple represents an edge between the i-th and j-th discovered vertices by the DFS traversal, li and l j are labels of those vertices, and l(i, j) is the label of the edge. Thus, the first 5-tuple has always i = 0 and j = 1, and it holds for other 5-tuples that i < j if it is a forward edge in the DFS traversal and i > j if it is a backward edge.
As there are more ways the DFS traversal can be performed on a single pattern, there are also more DFS codes for each pattern. A lexicographic order is defined on DFS codes and the minimum one is maintained for each pattern. This lexicographic order is also applied on codes of different patterns to represent the search space as a tree, called DFS Code Tree. In this DFS Code Tree, each vertex represents one DFS code and children of a vertex can be obtained by all possible single-edge extensions of the vertex. Therefore all codes on the same level of the tree have the same number of edges. Moreover, children of a vertex are ordered according to the lexicographic order. gSpan generates larger patterns in such a way that it corresponds to a depth-first search traversal of this DFS Code Tree, i.e. it generates patterns according to the lexicographic order. gSpan does not have to extend each pattern in all possible ways, it is enough to grow edges only from vertices on the rightmost path2. Specifically, it grows either a backward edge from the rightmost vertex3 to another vertex on the rightmost path or a forward edge from a vertex on the rightmost path to a newly introduced vertex. When traversing the search space, gSpan checks whether the pattern of the considered DFS code is frequent. If not, it prunes the search space tree on this vertex and backtracks. This is possible because of the anti-monotonicity of the support measure. It also checks whether the considered code is the minimum one for the corresponding pattern. If it is not minimum, the search space tree is pruned on this vertex because all patterns in this pruned subtree were already found earlier.
2The rightmost path is given by the DFS code and it is the path from the root to the lastly discovered vertex by the DFS traversal. 3The last vertex on the rightmost path from root. Algorithm 1 gSpan(D,S) 1: sort the labels in D by their frequency; 2: remove infrequent vertices and edges; 3: relabel the remaining vertices and edges; 4: S1 ← all frequent 1-edge graphs in D; 5: Sort S1 in DFS lexicographic order; 6: S ← S1; 7: for each edge e ∈ S1 do 8: initialize s with e, set s.D by graphs containing e; 9: Subgraph_Mining(D,S,s); 10: D ← D − e; 11: if |D| < σmin then 12: break; Algorithm 2 Subgraph_Mining(D,S,s) 1: if s 6= min(s) then 2: return; 3: S ← S ∪ {s}; 4: enumerate s in each graph in D and count its children; 5: for each c, c is s’ child do 6: if σ (c) ≥ σmin then 7: s ← c; 8: Subgraph_Mining(Ds,S,s);
The pseudocode of gSpan is given in Algorithm 1. By removing the infrequent vertices and edges, the input graphs can be significantly reduced and the overall efficiency increased. Frequent vertices are appended to results as the smallest frequent patterns. The main part of the algorithm starts from single-edge patterns. Specifically, Subgraph_Mining 2 procedure is recursively called on each such pattern. This procedure first tests whether the code s is minimum. If it is minimum, it enumerates its children by taking single-edge extensions. The procedure is then called on the frequent children. 4
In this section we describe the new algorithm called DGRMiner. It is based on the framework of gSpan, however, the framework is modified and extended. First, we provide necessary details about main modifications used in DGRMiner and then we present the pseudocode of the whole algorithm with description of remaining building blocks. 4.1
The first step is a transformation of an input dynamic graph4 into a data structure that can be considered as a set of static graphs. The idea is that we are able to represent the graph rules by single graphs and the input dynamic 4Here, we assume that there is only one dynamic graph on the input. Extension to a set of dynamic graphs is described in Subsection 4.4. graph as a set of static graphs in such a way that a modified static subgraph mining algorithm can be employed.
Let us start with the transformation of rules. In order to create a single graph from a rule, we take the union of the vertices and edges from its antecedent and consequent. Edges and vertices that do not represent any change in the rule will keep their labels and timestamps from the consequent. Let us remind that rules have relative timestamps less than or equal to 0 and thus these edges and vertices will have timestamps less than 0. Edges and vertices representing addition will keep their consequent timestamp, which is 0, but their labels will contain flag representing addition, for example label A will be changed to +A. However, timestamps of vertices and edges that were deleted or relabeled will have timestamps that are opposites of the antecedent timestamps. We know that consequent timestamps of such changes are equal to 0 so we can easily get the original value of the antecedent. We take the opposite values because later it will help us recognize current changes simply by timestamps greater than or equal to 0. Vertices and edges that were deleted or relabeled will also have new labels that can be easily decoded, for example −A for deletion of an object with label A and A => B for relabeling from A to B. Transformed rules from Fig. 1 are shown in Fig. 2.
Transformation of the input dynamic graph is very similar. Suppose that we have n snapshots in the dynamic graph. As the first snapshot does not represent any changes by itself, we create n − 1 new graphs in the following way. When creating the k-th graph, consider union of vertices and edges from snapshots 1 to k as an antecedent, where vertices and edges have their last assigned labels and timestamps of last changes relative to k. We can assume that all vertices and edges from the first snapshot had timestamps equal to 1. Similarly, use snapshots 1 to k + 1 to create a consequent. Then we use the method for rule transformation to create the k-th graph. All n − 1 graphs can be computed in a single pass as we can update the i-th graph to get the (i + 1)-th one.
Union of all graphs from the beginning may contain vertices and edges with very old changes that are not useful for the predictive rules. We use a window parameter to remove such vertices and edges from the union graphs. As edges cannot exist without their adjacent vertices, we do not remove old vertices adjacent to edges that are not old. Union graphs of the dynamic graph from Fig. 1 are shown in Fig. 2. In this case, window size is not set. 4.2
Now that we have the dynamic graph represented by union graphs, which can be viewed as a set of static graphs, we made a large step towards mining the graph rules. There are, however, still several issues to be addressed.
Let us start with a richer representation of edges. In Section 3, we showed that gSpan uses 5-tuples of the form (i, j, li, l(i, j), l j) to represent edges of patterns. In order to incorporate relative timestamps of rules and orientation of the edges, we simply extend these 5-tuples to 9-tuples of the form (i, j, li, ti, d(i, j), l(i, j), t(i, j), l j, t j). It is the same as the original 5-tuple except for the new elements. Specifically, ti, t j, t(i, j) are used for the relative timestamps of vertex i, vertex j, and the edge between i and j. Element d(i, j) represents the orientation of the edge between i and j, and it is one of the following: ←, →, −. The last one is used for undirected edges. Each pattern, i.e. graph rule in the condensed representation, can be represented as a list of such 9-tuples. Furthermore, it is easy to extend the gSpan’s DFS Code for these 9-tuples and thus we can create ordering between patterns and find a minimum DFS Code for each pattern. For example, suppose that we obtained the following order of vertex labels: A, +x, C=>D, A=>B, -x. Then the minimum code of the Predictive Rule 1 from Fig. 2 is (0, 1, A, −1, →, +x, 0, A => B, 1), (0, 2, A, −1, →, +x, 0, A => B, 1), (0, 3, A, −1, ←, −x, 1,C => D, 1). 4.3
In order to be able to deal with a broader class of dynamic graphs, we extended the mining algorithm to include two time abstraction methods. By time abstraction we mean usage of coarser timestamp values of union graphs in situations where exact values are not required or suitable.
The first method helps us to ignore timestamps of vertices. Specifically, we apply the signum function to all relative timestamps of vertices. Thus, negative timestamps become equal to −1 and positive timestamps become equal to 1. This method is useful for dynamic graphs in which all or almost all changes are caused by edges and vertices remain more or less intact.
The second method also uses the signum function but now it converts timestamps of both vertices and edges. It is useful in situations where patterns in dynamic graphs are very diverse and it is not possible to find many frequent patterns with exact timestamps. 4.4
In this section we provide remaining details and a description of the whole DGRMiner algorithm for predictive graph rule mining. The pseudocode of DGRMiner is given in Algorithm 3.
First, DGRMiner converts the input dynamic graph into a set of union graphs as described in Section 4.1. In the case of a set of dynamic graphs, the algorithm simply computes union graphs for each one of them and then concatenates the results. It only needs to keep the mapping of those union graphs into the original dynamic graphs in order to be able to compute their support and confidence correctly. Optional application of an abstraction method, described in Section 4.3, follows next. Then the algorithm removes infrequent vertices and edges but only those that represent changes as the other ones may be used later for confidence computation. When computing frequencies, it takes labels, timestamps, and edge orientations into account. Before moving to single-edge patterns, DGRMiner outputs frequent single-vertex patterns with high enough confidence. To compute confidence, it needs to decode antecedents of the patterns and then compute their support. After that, the algorithm takes frequent initial edges and sort them according to the extended version of the DFS lexicographic order of gSpan. An initial edge is such an edge that represents a change or at least one of its vertices does.
Now for each initial edge we recursively call subprocedure DGR_Subgraph_Mining, which searches for patterns growing from a given initial edge. This subprocedure, described in Algorithm 4, uses several arguments. s denotes the current pattern, which is represented by its DFS Code. In D and A we keep union graphs in which current pattern and its antecedent can be found. Finally, when growing patterns from the i-th initial edge, we keep the first i initial edges in Estart . This last argument is used in function min, which can be found in the first line of Algorithm 4. The purpose of this function is to check whether the DFS code of the given pattern is minimum, i.e. it was not found earlier when traversing the search space. Because all patterns grow only from the initial edges S1, it is enough to check whether we cannot represent the current pattern by a smaller DFS Code which starts by one of the edges in Algorithm 3 DGRMiner(DG) 1: convert the input dynamic graph(s) DG into the union graph representation D; 2: optional: apply a time abstraction method on union graphs; 3: remove infrequent vertices and edges; 4: output frequent change vertices with high enough confidence; 5: S1 ← all frequent initial edges in D sorted in DFS lexicographic order; 6: for i ← 1 to |S1| do 7: p ← i-th edge from S1 8: p.D ← graphs which contain p; 9: p.A ← graphs which contain antecedent of p; 10: Estart ← firsti edges from S1 11: DGR_Subgraph_Mining(p,p.D,p.A,Estart ); Algorithm 4 DGR_Subgraph_Mining(s,D,A,Estart ) 1: if s 6= min(s, Estart ) then 2: return; 3: enumerate s in each graph in D and count its children; 4: remove children of s which are infrequent; 5: enumerate antecedent of s in graphs given by A; 6: set s.A by graphs which contain antecedent of s; 7: con f ← confidence ofs; 8: if con f ≥ con fmin then 9: output s; 10: sort remaining children in DFS lexicographic order; 11: for each child c do 12: DGR_Subgraph_Mining(c,c.D,s.A,Estart ); Estart . If we can find such a smaller code, then the pattern must have been discovered earlier a thus we backtrack.
If the code is minimum, we continue by enumerating the pattern in relevant graphs given by D and searching for its children candidates. This step is similar to the one in gSpan. Also, all infrequent children are removed. Before saving the current pattern, we need to compute its confidence. As we described in Section 4.1, we are able to extract the antecedent from the current pattern and then count its occurrences. Set A represents a set of candidate graphs, in which we should search for the antecedent occurrences. The actual set of graphs containing the antecedent is then saved to s.A, where s.A ⊆ A, and it used as the A set for the pattern’s children.
Before recursive processing of the children of the current pattern, we need to sort the children according to the extended version of the DFS lexicographic order. Set c.D was created when the pattern s was enumerated and its children were counted. 5
In this section we present results of experiments on three datasets. All the experiments were conducted by a C++
ENRON RESOLUTION SYNTH SYNTH 20
1 103
1
20
implementation of DGRMiner on a PC equipped with
CPU Intel i5-4570, 3.2GHz, 16GB of main memory, and
running 64-bit version of Windows 8.1. For all
experiments, we set con fmin = 0 and window size for union
graphs equal to 10.
The first dataset used in experiments is based on the email
correspondence in the Enron company [
Results on ENRON with σmin = 0.1 can be found in the first row in Table 3. We decided to apply the time abstrac
tion method for vertices because they are only added in the first snapshot and never changed. We found 187 frequent rules, none of which was a single-vertex rule.
We also modified the previous dataset by deleting edges
which were not updated immediately the next day. This
modified dataset is named ENRON DEL in Table 3. The
change allows us to capture patterns which could not be
captured only by edge additions. Examples of two rules
from this dataset are shown in Fig. 3.
We used the set of graphs representing resolutions in
propositional logic from [
We conducted two experiments on this dataset, both with σmin = 0.05 as there were not many frequent patterns. One with no time abstraction, and one with time abstraction of both vertices and edges. From Table 3 we can see that the time abstraction helped us to find ten times more frequent rules for the same value of the minimum support. Furthermore, most of the rules were 1-vertex rules when the abstraction was not applied. Such rules capture vertex additions, deletions and relabelings without any context and may not be very informative. 5.3
with 10 vertices and 20 randomly assigned edges was created. Then we iteratively built 100 snapshots, each snapshot from the previous one by randomly chosen changes. The number of changes ranged uniformly 0–1 for vertex deletion, 0–1 for edge deletion, 0–1 for vertex addition, 0– 3 for edge addition, 0–2 for vertex label change, and 0–2 for edge label change. All newly selected vertex (edge) labels were chosen from a uniform distribution over set {A, B} ({y, z}). Each new snapshot had to be different from the previous one. In order to keep approximately the same number of vertices (edges) through time, additions or deletions of vertices (edges) were suspended if the number of vertices (edges) was not in the [k/2, 2k] interval, where k = 10 (and k = 20 for edges). The second dataset, SYNTH 20, was created from 20 dynamic graphs, each one of them built by the process just described.
For SYNTH and σmin = 0.1, the time abstraction of both vertices and edges was applied because there were almost no frequent patterns without the abstraction. On the other hand, experiments on SYNTH 20 with 20 dynamic graphs did not require any time abstraction and approximately 1600 frequent rules were found for the same value of the minimum support. This suggests that the support definition for a single dynamic graph is stricter than the one for a set of graphs. 6
Besides real-world data, we also tested our method on a
synthetic datasets. One of this dataset, SYNTH in
Table 1, was generated in the following way. First, a graph
Several algorithms have been proposed for graph rule
mining. However, a lot of these algorithms are expecting
that the only changes in a dynamic graph are caused by
edge additions, or by vertex additions if the vertices
belong to the edges being added. These algorithms include
GERM [
The work most related to ours is probably the algorithm
for mining interesting patterns and rules proposed in [
Predictive graph rules can be also seen as subgraph
sequences of length two. Mining of subgraph subsequences
from a set of graph sequences (dynamic graphs) is
considered in [
Dynamic GREW [
Except for FRISSMiner, the algorithms presented in this section are designed only for the single-dynamic-graph scenario. On the contrary, FRISSMiner is designed only for the set-of-dynamic-graphs scenario.
Experimental comparison of the above algorithms with DGRMiner is difficult due to the fact that each algorithm mines different type of patterns. Also, different definitions of support and confidence affect which patterns are frequent. For example, GERM computes absolute support and counts multiple occurrences of a pattern in a snapshot. On the other hand, DGRMiner computes support of a pattern as a fraction of snapshots containing at least one occurrence of the pattern. Another difficulty arises from the fact that implementations of the algorithms, with the exception of GERM, are not freely available for download. Lastly, the datasets used for experimental evaluation of the above algorithms are often either not available or it is not possible to reproduce the same data. 7
We proposed a new algorithm DGRMiner for mining frequent predictive graph rules from both single dynamic graphs and sets of dynamic graphs. This algorithm is able to capture various changes in dynamic graphs. Edges in dynamic graphs are allowed to be directed or undirected multiedges. DGRMiner uses support and confidence as significance measures of the rules. Such graph rules are useful for prediction in dynamic graphs, they can be used as pattern features representing dynamic graphs or simply for gaining an insight into internal processes of the graphs. We evaluated the algorithm on two real-world and two synthetic datasets.
As future work, we plan to further investigate time abstraction methods and other ways of support computation. We also intend to modify the method for mining frequent closed patterns.
Acknowledgments. We would like to thank to Luboš Popelínský and other members of KDLab FI MU for their help and comments.