A novel temporal frequent subgraph based mining algorithm using spark

Abstract

Generally, big interaction networks keep the interaction records of actors over a certain period. With the rapid increase of these networks users, the demand for frequent subgraph mining on a large database is more and more intense. However, most of the existing studies of frequent subgraphs have not considered the temporal information of the graph. To fill this research gap, this article presents a novel temporal frequent subgraph-based mining algorithm (TFSBMA) using spark. TFSBMA employs frequent subgraph mining with a minimum threshold in a spark environment. The proposed algorithm attempts to analyze the temporal frequent subgraph (TFS) using a Frequent Subgraph Mining Based Using Spark (FSMBUS) method with a minimum support threshold and evaluate its frequency in a temporal manner. Furthermore, based on the FSMBUS results, the study also tries to compute TFS using an incremental update strategy. Experimental results show that the proposed algorithm can accurately and efficiently compute all the TFS with corresponding frequencies. In addition, we also apply the proposed algorithm on a real-world dataset having artificial time information that confirms the practical usability of the proposed algorithm.

Keywords

Data mining subgraph mining temporal frequent subgraph mining parallel mining

1. Introduction

Data mining is the process of extracting statistically significant and useful knowledge or information from the data in databases [1]. The data may exist in many forms such as vectors, tables, texts, images, and so on. It can also be presented by different means, such as structured data and semi-structured data. Structured data and semi-structured data are more suitable and naturally fit for graph representation. Mining of the graph data is referred to as graph mining or graph-based data mining. It is an important research area in the domain of data mining and has attracted much attention in recent years. Frequent subgraph mining (FSM) is an important aspect of graph mining. The main aim of FSM is to extract all the frequent subgraphs in a given data set, whose occurrence counts are above a specified threshold [2]. One of the main challenges in FSM is the information mining of graphs with dynamic nature, which is called temporal FSM.

Many real-world graph applications contain temporal information. For example, telecommunication companies record massive amounts of phone calls and Short Message Services (SMS) every day, where each phone call or SMS record contains attributes about the sender, the recipient, and the time when the phone call was made, or the SMS was transmitted. As another example, online social networking companies keep logs about the interactions between users and the time when each interaction occurred. We can take advantage of temporal diverse information networks (DIN) to capture this type of relational structure. In DIN, nodes represent individuals of different entity types and edges stand for several kinds of correlation. Besides, each edge is related to a time interval to record the durations that two individuals come across and interact with, where each interval entails a starting timestamp and an end timestamp. Alternatively, considering real-world social activities typically follow a particular intervallic property, such as a day for human life and a year for a conference venue. This kind of data overtime period should be integrated into DIN. Hence, we regard social activities in a specific time period as a temporal snapshot by gathering networks graphs ( $g_{1}$ , $g_{2}$ , $g_{3}$ , $\ldots$ , $g_{n}$ ) that occur in a sequence of time periods ( $t_{1}$ , $t_{2}$ , $t_{3}$ , $\ldots$ , $t_{n}$ ). The real-world databases of the social networks, in which each entity interaction stands for a graph containing social interactions in a certain time period, combinedly create a single large graph database.

The main contributions of this article are summarized as:

1)
A new framework for graph mining strategy is studied called the TFS mining framework.
2)
A novel TFS mining algorithm is proposed using a spark environment.
3)
The proposed algorithm is applied on a real-world dataset having artificial time information that confirms the practical usability of the proposed algorithm.
4)
Extensive experiments have been performed on different data sets including real-world data set. Experimental results of the proposed algorithm are compared with non-TFS mining in order to show its efficiency and accuracy.

The rest of the paper is organized as follow: Section 2 presents related work, Section 3 describes the graph preliminaries, Section 4 discusses the proposed method for mining frequent substructure patterns in temporal graph dataset, and Section 5 presents performance evaluation of the proposed method. Finally, Section 6 concludes the paper with future work.
2. Related work

Generally, several types of processes are characterized by a set of actors that interact in a network over a period. In many real-world applications (social and communication networks), one of the common objectives is the dynamic behavior modeling of the component entities (people). Recently, a considerable number of studies have focused on the analysis of the practical applications, including the evolution of bibliographic databases [3, 4, 5, 6, 7], influence and information spread in a social network [8, 9, 10], and the web and other information networks [11, 12]. Most of the existing studies employed various graph mining algorithms, such as GRAMI [13].

The GRAMI algorithm is one of the most effective single-machine algorithms for mining frequent subgraphs on a single graph. It turns the problem of mining frequent subgraphs into the problem of constraint satisfaction problem (CSP). However, the GRAMI algorithm is a stand-alone algorithm, which has low efficiency in large-scale graph operation and is difficult to support the mining of frequent subgraphs with low support. Moreover, the existing algorithms for FSM of a single graph in a distributed environment [14, 15] are for the directed graph and need to specify the number of vertices of subgraphs. It does not support the mining of subgraph growth patterns.

Most of the other distributed frequent subgraph mining algorithms [16, 17] are based on the MapReduce framework [18], which need to read and write disks many times during the iterative calculation, resulting in a large amount of input and output (I/O), serialization and deserialization costs, and also cannot be transplanted to the single graph for mining. Based on the above defects, recently, Frequent Subgraph Mining Based Using Spark (FSMBUS) [19] and Spark-based Single Graph Mining (SSIGRAM) [20] algorithms are proposed, which are based on Apache Spark Framework. But the above-mentioned spark-based algorithms lack the temporal information attributes of the temporal graph.

However, most of the existing graph mining algorithms mentioned above do not consider temporal information in a graph, which fails to exploit the temporal attributes for detecting important temporal patterns. This work attempts to analyze the TFS using an FSMBUS algorithm with a minimum support threshold and temporally evaluate its frequency. Furthermore, based on the FSMBUS results, this article also tries to compute TFS using an incremental update strategy.

3. Graph preliminaries

In this section, some basic concepts of graph theory and notations used in the paper are defined.

Definition 1. Graph: A graph is a pair $G=(V,E)$ consisting of a set of vertices $V$ and a set of edges $E\sqsubseteq$ V $\times$ V such that every edge $e\in E$ relates to a pair of vertices ( $V_{1}$ , $V_{2})$ [21].

Definition 2. Graph Isomorphism: Two graphs $G_{1}=$ ( $V_{1}$ , $E_{1}$ ) and $G_{2}=(V_{2},E_{2})$ are isomorphic if they are topologically identical to each other; that is, there is a mapping from $G_{1}$ to $G_{2}$ such that each edge in $E_{1}$ is mapped to a single edge in $E_{2}$ and vice versa. In the case of labeled graphs, this mapping must also preserve the labels on the vertices and edges [21].

Definition 3. Subgraph: A graph $G_{2}=(V_{2},E_{2})$ is a subgraph of another graph $G_{1}=(V_{1}$ , $E_{1}$ ) if $V_{2}\subseteq V_{1}$ , and $E_{2}\sqsubseteq E_{1}\wedge$ ( $V_{1}$ , $V_{2}$ ) $\in E_{2}\to V_{1}\in V_{2}$ and $V_{2}\in V_{2}$ (Fig. 1).

Figure 1.

Graph-1 is a subgraph but Graph-2 is not subgraph of Graph (a).

Figure 2.

TFS mining framework. Vertex RDD ( $V_{\textit{rdd}}$ ), Edge RDD ( $E_{\textit{rdd}}$ ), Frequent Subgraph RDD (FS ${}_{\textit{rdd}}$ ).

Definition 4. Subgraph Isomorphism: Given two graphs $G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$ , the problem of subgraph isomorphism is to find an isomorphism between $G_{2}$ and a subgraph of $G_{1}$ , that is, to determine whether or not $G_{2}$ is included in $G_{1}$ [21].

Definition 5. Frequent Subgraph: A frequent subgraph is a graph whose support is not less than a minimum user-specified support threshold. Given a labeled graph dataset $G_{D}={\{}G_{1},G_{2}\ldots G_{K}{\}}$ , support or frequency of a subgraph g is the percentage (or number) of graphs in $G_{D}$ where g is a subgraph [21].

4. The proposed framework and algorithm

Figure 3.

The structure of CSP domain.

In this section, we propose an efficient TFSBMA using spark. The TFS parallel mining method from the temporal dataset is mainly designed based on FSM using spark distributed architecture illustrated in Fig. 2. It has two significant phases: the initial phase and the mining phase. The initial phase is also called the preparation phase, where the system loads graph data having time attribute from Hadoop Distributed File System (HDFS), divides the edges by time series, makes single Resilient Distributed Datasets (RDDs) for the same time attribute, and compute frequent edges. The mining phase has two sub-phases FSM and temporal frequency calculation phase. The FSM phase receives the frequent edges RDD ( $FE_{\textit{rdd}}$ ) and mines the subgraphs iteratively. This phase repeats for every time series RDD and passes to the next phase for temporal frequency calculation. In the mining phase, we get $\textit{FS}_{\textit{rdd}}-1$ , $\textit{FS}_{\textit{rdd}}-2$ $\ldots$ $\textit{FS}_{\textit{rdd}}-n$ from the FSM phase. After that, we calculate the temporal frequency for all subgraphs and the final results are sent to HDFS.

4.1 Initial phase

The main tasks of the initial phase that need to be completed are generating multiple $E_{\textit{rdd}}$ , collecting frequent edge data, and initializing frequent subgraph data. First, $E_{\textit{rdd}}$ are formed on the bases of additional time attribute from the input edge dataset, which can be seen in the initial phase of Fig. 2. According to the combination of edges and vertices of the graph, the Edge with Minimum Image (MNI) [13] based support less than the given minimum support is directly filtered as the infrequent edges. The remaining frequent edge is stored in the format of a triplet (srclabel, attr, dstlabel), where srclabel is a source vertex label, attr is edge label, and dstlabel is a target vertex label (as like the property of GraphX triplets). These frequent edges are the frequent subgraphs of the first layer in the suboptimal tree which consist of Canonical Adjacency Matrices (CAMs), where the root of the tree is an empty matrix. Then, an edge with the vertex ID of all frequent edge patterns is found by traversing the original graph according to the frequent edge. After mapping frequent edge and vertex ID, it is stored as a domain (D in the CSP model). This ( $\textit{FE}_{\textit{rdd}}$ ) will be used to extend the candidate subgraph in the iteration process of FSM and will be cached directly to speed up the expansion. The structure of domain D is shown in Fig. 3, where the structure in Fig. 3a represents a candidate subgraph with $k$ -vertices. $u_{x}$ represents the effectively assigned vertices to $D(1)$ and $u_{y}$ to $D(k-2)$ . ${\{}k-2\to{\{}u_{y}{\}}{\}}$ represent the connection between $u_{x}$ of $D(1)$ and $u_{y}$ of $D(k-2)$ .

Meanwhile, this algorithm is applied to the mining of undirected graphs, such as on $D(k-2)$ . In addition, there will be symmetric connection information with $D(1)$ . Figure 3b and c are the example of Fig. 1a, which is an undirected graph, and according to Fig. 3b, it can get an edge connection. The advantage of this storage structure is that it can be directly used to calculate the support of candidate subgraphs.

4.2 Mining phase

It is the main phase of our framework, which consists of FSM and temporal frequency calculation. In the FSM phase, all frequent subgraphs are calculated iteratively, including candidate generation of searching the data fields for corresponding candidate subgraphs and its support calculation. In the temporal frequency calculation, first the frequency is assigned to each frequent subgraph calculated for the time periods in the previous step, after that, the cumulative frequency is calculated for all generated subgraph with respect to the time period.

Table 1
Frequent subgraphs of a social interaction network

Time period	Frequent subgraphs
1 ${}^{\text{st}}$ Month	(A, call, B) (A, call, C) (B, call, D) (A, meet, B) (A, meet, C) (B, meet, C) (A, meet, B&C) (A, meet, C&D) (A&B, at, restaurant) (A&C, at, cafe) (B, C, D, at, restaurant) (A, meet, B&C) (A, meet, C&D) (A, B, D, at, restaurant) (A, B, C, D at, cafe)
2 ${}^{\text{nd}}$ Month	(A, call, B) (A, call, C) (B, call, C) (B, call, D) (A, meet, E) (A, at, lab) (E, at lab) (B, at, restaurant) (C, at, restaurant) (D, at, restaurant) (D, at, bar) (B, meet, C) (B, meet, D) (A&E, at, lab) (B, C, D, at restaurant) (B, call, C&D) (B, meet, C&D)

4.3 Frequent subgraph mining

In FSM, we have used the FSMBUS [17] mining strategy due to its efficiency and accuracy. First, all the candidate frequent subgraphs are generated in the $i-1$ iteration using the breadth-first search strategy through Fast FSM i.e., FFSM-join and FFSM-extend, and a new candidate subgraph is equivalent to adding an edge to the parent subgraph, which is called an extended edge. The data structure of the new candidate subgraph includes the ID of its parent subgraph, as well as its topological structure, which can help the candidate subgraph to construct the candidate and search in the frequent edges graph data. After that, support is calculated. After subgraph extension, all the newly generated subgraphs are sent to the next procedure for support evaluation, and it employs the CSP model as the subgraph support calculation strategy entails of MNI based support technique, which is an efficient way for finding subgraph isomorphism. It uses an iterative and incremental design of RDD and the join transformation in Spark, which saves the CSP domain data of every generated subgraph. The first join operation combines the newly generated subgraphs and frequent edges to get the extended edges, while the second join combines newly generated subgraphs and extended edges to generate the search way. This process will continue until no infrequent is left. Accordingly, combine subgraphs and send to the next phase for temporal frequency calculation and repeat the whole process for $E_{\textit{rdd}}-2$ , $E_{\textit{rdd}}-3$ $\ldots$ $E_{\textit{rdd}}-n$ as shown in Fig. 2.

4.4 Temporal frequency calculation

According to the FSM step, all frequent subgraphs are efficiently calculated and stored in the lists $\textit{FS}_{\textit{rdd}}$ as shown in the mining phase of Fig. 2, and all (1, 2 $\ldots$ $n$ ) show the collation of frequent subgraphs of different time periods, all frequent subgraphs in $\textit{FS}_{\textit{rdd}}$ in the form of the matrix. In this step, we calculate the frequency for all frequent subgraphs in a timely manner, which is called TFS. All search is performed iteratively. First $\textit{FS}_{\textit{rdd}}-1$ is imported and considered that all elements (Frequent Subgraphs) have frequency value “1” in the $\textit{FS}_{\textit{rdd}}-1$ , then $\textit{FS}_{\textit{rdd}}-2$ and searched for the subgraph which will make isomorphism to the candidate frequent subgraph matrix in $\textit{FS}_{\textit{rdd}}-2$ . It is assumed that all the elements (frequent subgraphs) in $\textit{FS}_{\textit{rdd}}$ are unique and should not be more than one element (matrix), and each element will be searched only once. While searching for a candidate subgraph (matrix) in the $\textit{FS}_{\textit{rdd}}-2$ , if a matrix is matched, then its frequency will be increased by “1” and will not search the whole RDD, and the curser will be shifted to the next iteration of the $\textit{FS}_{\textit{rdd}}$ .

When the search is completed, the results are combined in one RRD for the next search of $\textit{FS}_{\textit{rdd}}-2$ , and now the whole matching process will be repeated to combine the RDDs. This process will continue for remaining each RDD till to the $n .$ For example, a temporal diverse information network database consisting of two months record (i.e., two time periods) and each month is an interaction of temporal DIN database, and its frequent subgraphs are shown in Table 1. The database contains two node types, including person and location, and three types of edge, including “call”, “meet” and “at”. Where “call” means that persons are making a phone call to others, “at” means that a person stays at a specific place, and “meet” means a person meets another one. There are five persons (i.e., A, B, C, D, E) and four locations (i.e., bar, lab, restaurant, cafe). Each interaction is composed of a set of social interactions that are recorded on different days using four-tuple items. Each tuple contains a source node, relationship, target node, and timestamp. For example, the interaction: (A, call, B, 0101) where the first two digits show a month and the last two digits mean a day. So, in the 2 ${}^{\text{nd}}$ column of the above Table 1, we have shown calculated frequent subgraphs of two months. Now we can understand the temporal frequency calculation more in detail using some frequent subgraphs from the above Table 1 and show graphical representation in Fig. 4. Consider a single FSG (A-call-B) from “1 ${}^{\text{st}}$ month” having “frequency 1” and search it in “2 ${}^{\text{nd}}$ month”, if it exists in “2 ${}^{\text{nd}}$ month” then its frequency will increase by “1” otherwise frequency will remain the same, as it exists so its frequency will update to one. Now, FSG (B-call-D) does not exist in “2 ${}^{\text{nd}}$ month”; hence, its frequency remains the same, and so on until the last FSG. After that, combine the results of both months. If there is also “next month”, then the same process will be repeated with the combined result of 1 ${}^{\text{st}}$ month and 2 ${}^{\text{nd}}$ month. Thus, the whole process will be repeated for all months to find which frequent subgraph FSG is TFS. In this way, the results for all the TFS with relevant computed frequencies are calculated.

Figure 4.

The flow of temporal frequency calculation.

4.5 TFS time accumulation

During the frequency calculation, If the data item (frequent subgraph) frequently appears in the data flow and the last acquiring time is close to the current time node, then it means that the frequency of this data item is high at the current time. It is more likely to become frequent, which forms the basic idea of dynamic frequency-time accumulation calculation based on time accumulation. The details of the calculation process are as follows.

The number of counting times divided by time granularity into different time periods of data flow from the initial time to the current t time, which is represented by $T^{t}$ where $t$ is the value of the last time. $M_{t}=\{m^{t}_{i}|i=1,2,3,\ldots\}$ , where $m_{i}^{t}$ is the total number of times when the single subgraph $I_{i}$ actually appears at each counting time from the initial time to total time t. For example, taking the year as the time granularity, the starting time of data flow is 2010 and the ending time is 2020, and $T^{2020}=$ 10. During this time, the data items $I_{i}$ appear in two years of 2015 and 2019, then the current frequency is $m_{i}^{2020}=$ 2, and time is 10. The cumulative statistical formulas are given below [22].

$\displaystyle T^{t}=T^{t-1}+1$ (1) $\displaystyle m_{i}^{t}=\left\{{{\begin{array}[]{ll}m_{i}^{t-1}+1&I_{i}\ % \textit{didn't appear at}\ t\\ m_{i}^{t-1}&I_{i}\ \textit{appear at}\ t\\ \end{array}}}\right.$ (2)

Algorithm 1: Parallel TFS Mining
1:	INPUT: Vertex data storage path ‘vertex path’; Edges data storage path ‘edges path’; Minimum support for frequent subgraphs ‘minsup’; Spark context ‘sc’;
2:	(k-list) ${}_{t}$ $=$ get items from vertex path;
3:	Val vertices RDD $=$ get vertices from vertex path;
4:	for Each item $i\in$ (k-list) ${}_{t}$ do
5:	Val graph $=$ Graph (vertices RDD, edges RDD $i$ );
6:	Val frequent Edges RDD $=$ Collect Frequent Edges RDD(graph, FE);
7:	Val edgeFreqMap BR $=$ sc.Broadcast(frequentEdgesRDD);
8:	Val PG $=$ generate parent graph using graph and edgeFreqMapBR;
9:	Val $S_{1}\leftarrow$ FSMBUS mining (vertices RDD, edges RDD ${}_{i}$ , minsup);
10:	Val FSG list $=$ put $S_{1}$ in the list for further use in the frequency calculation;
11:	end for
12:	for Each item $i\in$ FSGlist do
13:	TS $\leftarrow$ temporal Frequency Count (FSG ${}_{i}$ , FSG ${}_{i+1}$ );
14:	end for
15:	OUTPUT: TS ${}_{k}$ ;

4.6 Proposed algorithms

Algorithm 1 shows the whole process of temporal FSM and how it is conducted in the spark framework, in which temporal graph datasets and minimum support for frequent subgraphs are given as input. After initializing inputs, the graph is created with the combination of vertices for each edge data in a specified time period. In the lines (5–7), all frequent edges are calculated for the generated graph $i$ . Accordingly, the above-generated graphs are cached to generate a parent graph for every edge, which is frequent. Finally, all frequent parent graphs are passed to the mining step, where all frequent subgraphs are calculated.

The temporal frequency is calculated by using Algorithm 2. It shows the temporal frequency calculation process for every frequent subgraph data generated in the mining step. It will take $i$ and $i+1$ frequent subgraph list data, which consists of matrices, and compute its frequency, as shown in Fig. 2. This algorithm can find all the frequencies for each subgraph.

Algorithm 2: Temporal frequency count
1:	INPUT: Source FSG ‘ $S_{1}$ ’; Target FSG ‘ $S_{2}$ ’;
2:	for each item $x\in S_{1}$ do
3:	flag $\leftarrow$ false;
4:	for each item $y\in S_{2}$
5:	if size of $x=$ size of $y$ then
6:	Check for corresponding values of both matrix;
7:	else
8:	Go to the next matrix;
9:	end if
10:	for each row do
11:	for each column do
12:	if column $=$ row then
13:	Compare its value;
14:	else
15:	Compare both matrix edges value and also check for empty value;
16:	end if
17:	end for
18:	end for
19:	flag $\leftarrow$ true and update Frequency ‘y’;
20:	end for
21:	if flag $=$ false then
22:	Add $x$ in TS;
23:	end if
24:	end for
25:	Add each item of $S_{2}$ in TS
26:	OUTPUT: TS;

5. Experimental results and discussion

In this section, we will describe the experimental process and results along with a comparative discussion.

5.1 Experimental setup and data

The main issue addressed in this article is the TFSs mining in a single graph using the spark framework. The whole experimental setup is given as: a host PC with Intel Core i7-7700HQ CPU at 2.40 GHz and 20 GB RAM with Ubuntu 19.04 operating system and spark version 2.3.1 with the Scala version 2.11. The spark cluster is built on it with one master node and two worker nodes with the same configuration for the master node with 8 G memory and each worker node with a 2 G memory.

The main graph data involved in our work is a single large graph. To show the accuracy and efficiency of our solution followed by using different experimental processes on simulation data generated by random function using in java, which containing temporal information. Furthermore, the study categorized the whole simulation data into 11 years from 2000 to 2010, having 100,000 vertices with 100 distinct labels and combine the total number of edges (relation) are 1,080,298 with high density, and the characteristics of the annual data are summarized in Table 2.

Table 2
Simulation database

Year	Relations (Edges)	Year	Relations (Edges)
2000	98503	2006	98338
2001	98114	2007	98170
2002	98118	2008	98451
2003	97980	2009	98641
2004	98350	2010	97712
2005	97858

5.2 Effectiveness of temporal frequency

In order to verify the effectiveness of temporal frequency, we compare the results of frequent subgraphs (non-temporal frequency) and frequent subgraphs with the temporal frequency (which is also called TFSs) of each year with last year correspondingly. We computed the frequent subgraphs using three different minimum support values for each year, and the corresponding results are shown in Table 3 with four columns. Each row represents the number of frequent subgraphs that occurred each year with respect to the minimum support value. The support values 5, 6, and 7 are respectively used in experiments and placed in the heading of the table.

Table 3
Frequent subgraph for every year

Year	Support-7	Support-6	Support-5
2000	163	410	894
2001	134	340	848
2002	127	357	877
2003	146	392	912
2004	170	414	924
2005	161	419	941
2006	118	358	903
2007	144	396	933
2008	122	359	931
2009	156	396	924
2010	158	382	931

Figure 5.

Temporal frequent subgraphs TFSs.

The data from 2000 to 2010 is extracted by using FSM techniques for each year, then the temporal frequency is calculated for every two years correspondingly. For example, in the temporal frequency calculation for 2001, we take the frequent subgraphs of 2000 and searched that how many of them have occurred in the 2001 subgraphs, and this process is repeated for different data calculated by different minimum support. All the results are illustrated in Fig. 5a, where the x-axis consists of time periods with values from 2001–2010, and the y-axis shows the number of temporal subgraphs occurrences of the corresponding year data. As shown in the graph, we can see the dramatic change when the minimum support value is decreased, which increased the number of frequent subgraphs as well as TFSs exponentially. It can also be found in Table 3 that the average number of frequent subgraphs data calculated with the minimum support-7 is less than the data calculated with support-6 and much less than support-5. However, the average accuracy of the TFSs of minimum support-7 and support-6 (2.69% and 8.39%) is very low with respect to data calculated with minimum support-5, which is 17.01%. It is evident that with less minimum support, more frequent subgraphs may result in temporal frequency, which will turn in results for better future prediction.

On the other hand, Fig. 5b shows the results of the TFSs for all years, where the y-axis represents the number of TFSs, and the x-axis represents the frequency of the resultant data with different three line for different minimum support. As shown in Fig. 5, the cumulative number of subgraph occurrences is very high for all three lines representing different minimum support data at the frequency “1”, which shows the non-TFSs because these subgraphs occurred only once in the whole time period. We can also see that most of the TFSs have a frequency equal to “2”. In addition, the number of occurrences is decreasing when the temporal frequency is increasing as shown in Fig. 5b.

5.3 Contrast experiment of TFS and Non-TFS

Figure 6 illustrates the results of the contrast effects of TFSs and non-TFSs from 2006 to 2010, where the y-axis indicates the number of TFSs and non-TFSs occurrences, and the x-axis consists of time periods with values from 2006–2010, respectively. The contrast experiments of the forecast results of TFSs and non-TFSs are conducted for every year with the compression of the last five years to that year such as mining for 2006, we have used 2001 to 2005, for mining 2007, we used 2002 to 2006. Similarly, the same mining procedure for the rest of the years.

Figure 6.

Contrast effects of TFSs and non-TFSs.

We have used the “20” threshold values, which is the lowest minimum support value for every five years, and the threshold value “5” is used for each year. As can be seen from Fig. 6, the number of TFSs is gradually increased, which predicted that the temporal frequency is more in the 2011 dataset. It also shows that the number of TFSs appears less than the number of non-TFS which indicates that many meaningless subgraphs are excluded. The average number of subgraphs in temporal frequency prediction of five groups’ data is 59.91% less than non-temporal frequency prediction. Therefore, the prediction effect of temporal frequency is better in the future for decision making, because it accumulates the time to make the frequent subgraph mining data more practical and useful.

5.4 Effect of spark parallelism

The scalability experiments of the proposed TFSBMA were conducted using Spark is to evaluate the time effect of executors in the Spark cluster and built on a host configured with Ubuntu19.04, Intel Core i7-7700HQ CPU at 2.80 GHz with 20 GB RAM and four additional virtual nodes are set up with the same configuration of 2 GB memory. The computing nodes are parallel connected to the master node. The time performance of the algorithm is calculated for combined temporal frequency for all years with the support values (5, 6, 7), respectively. The experimental results are shown below in Fig. 7a and b.

Where Fig. 7a shows the results of all support values and Fig. 7b shows only support-6 and support-7 for better understanding the difference of executions. As shown in Fig. 7a, under the threshold values for temporal frequency calculation, the run time taken by the algorithm is decreasing, and the number of executors is increasing. As the number of executors increases, the time consumed by the algorithm decreases, and the curve starts to slow down. Also, for support-6 and support-7, which can be seen clearly in Fig. 7b, due to the parallel process among computing nodes causes an increase in time overhead. At the same time, the execution number is the same, and the threshold for temporal frequency calculation is different. However, the running time still continuously decreases as the number of core processes is increasing for all worker nodes, and the amount of the data calculation remains the same, which verifies the efficiency of a distributed environment.

Figure 7.

Time performance of spark executors.

6. Discussion

The reasons why the proposed algorithm performed better than non-temporal can be attributed to the following two aspects:

1.
The proposed algorithm is based on Spark, which enables us to process a large amount of data, beyond what can fit on a single machine with a high-level library. Spark’s design and interface are unique, and it is one of the fastest systems of its kind.
2.
Since the proposed algorithm can find frequent subgraphs using the lowest threshold value over a specific interval, therefore, we get more frequent subgraphs, which can lead to better future prediction. As a result, the proposed algorithm performs better than non-temporal FSM.

7. Conclusion

Mining frequent subgraphs from the graph-based structure is a visual representation of structural information. New methodologies are discovered to explore the structural relationships of a large graph, especially when the graph is dynamic. In this paper, we proposed a new framework and a novel algorithm TFSBMA for TFS mining using spark for large temporal graphs. Our framework consists of two phases: the initial phase, and the mining phase, where the initial phase is the data preparation phase, and the mining phase is responsible for FSM and temporal frequency calculation. Extensive experiments were conducted in different ways to predict the possible events for the future. The effectiveness and performance of the proposed framework and algorithm are evaluated by performing different contrast experiments. Compared to the non-temporal frequency frequent subgraphs, the proposed algorithm has higher accuracy for future prediction.

In this work, model temporal datasets were used for experimental results, which is the cause of a small percentage of prediction in future data. In the future, it can be improved with real temporal graph datasets which can achieve the actual percentage in the data for better future prediction. On the other hand, FSM with the lowest minimum support is a significant factor for better future prediction in a temporal way. In the mining phase, when a subgraph involves a node with a very big degree, the FSM phase algorithm will not go to the next iteration until the executor finishes calculating the support of this subgraph. In the future, we plan to design a strategy that decomposes the evaluation task for this type of subgraph to all executors, which may accelerate the search speed further.

References

Chen

M-S

Han

. Data mining: an overview from a database perspective. IEEE Transactions on Knowledge and Data Engineering. 1999 Dec; 8(6): 866-883.

Jiang

Coenen

Michele

. A survey of frequent subgraph mining algorithms. The Knowledge Engineering Review. 2012; 28(1): 75-105.

Barabasi

Jeong

Neda

Ravasz

Schubert

Vicsek

. Evolution of the social network of scientific collaborations. Physica A: Statistical Mechanics and its Applications. 2002 Aug; 311(3-4): 590-614.

Borner

Maru

Goldstone

. The simultaneous evolution of author and paper networks. PNAS. 2004; 101(1): 5266-5273.

Borner

DallAsta

Vespignani

. Studying the emerging global brain: Analyzing and visualizing the impact of co-authorship teams. Complexity. 2005; 10(4): 57-67.

Liben

Kleinberg

. The link prediction problem for social networks. Proceedings of the twelfth international conference on Information and knowledge management, 2003; 556-559.

Ramasco

Dorogovtsev

Pastor-Satorras

. Self-organization of collaboration networks. Physical Review E, 2004 Oct; 70(3 Pt 2): 036106.

Baumes

Goldberg

Magdon-Ismail

Wallace

. Discovering hidden groups in communication networks. in: Proceedings of the 2nd NSF/NIJ Symposium on Intelligence and Security Informatics, 2004.

Broido

Claffy

. Internet topology: connectivity of ip graphs. in Proceedings of SPIE ITCom, 2001.

10.

Carley

. Communicating new ideas: The potential impact of information and telecommunication technology. Technology in Society. 1996; 18(2): 219-230.

11.

Fetterly

Manasse

Najork

Wiener

. A large-scale study of the evolution of web pages. in Proceedings of WWW, 2003.

12.

Kleinberg

. Temporal dynamics of on-line information streams. draft chapter for the forthcoming book Data Stream Management: Processing High-Speed Data Streams (Garofalakis M, Gehrke J, Rastogi R, eds.), Springer.

13.

Elseidy

Abdelhamid

Skiadopoulos

, et al. GRAMI: Frequent subgraph and pattern mining in a single large mining graph. Proc of the 40th Int Conf on Very Large Data Bases Berlin: Springer, 2014: 517-528.

14.

Liu

Jiang

Chen

, et al. Mapreduce-based pattern finding algorithm applied in motif detection for prescription compatibility network. Advanced Parallel Processing Technologies. Berlin: Springer, 2009; 341-355.

15.

Shahrivari

Jalili

. Distributed discovery of frequent subgraphs of a network using MapReduce. [201-03-25]. http//link-springer-com.web.bisu.edu.cn/article/10.1007/s00607-015-0446-9.

16.

Bhuiyan

Al Hassan

. An iterative MapReduce based frequent subgraph mining algorithm. IEEE Trans on Knowledge and Data Engineering. 2013; 27(3): 608-620.

17.

Chen

Tung

AKH

, et al. Efficiently extracting frequent subgraph using mapreduce. Proc of the 1st IEEE Int Conf on Big Data. Piscataway, NJ: IEEE. 2013639-647.

18.

Dean

. Ghemawat

. MapReduce: Simplified data processing on large clusters. Communications of the ACM. 2008; 51(1): 107-113.

19.

Yan

Dong

. et al. FSMBUS: A Frequent Subgraph Mining Algorithm in Single Large-Scale Graph Using Spark. Journal of Computer Research and Development. 2015; 52(8): 1768.

20.

Qiao

Zhang

, et al. A Parallel Approach for Frequent Subgraph Mining in a Single Large Graph Using Spark. Applied Sciences. 2018; 8: 230.

21.

Rehman

S-U

Asghar

Zhuang

Fong

. Performance Evaluation of frequent Subgraph Discovery Techniques. Mathematical Problems in Engineering. 2014 Aug; 2014(2): 1-6.

22.

Zhao

Huang,

Wang,

Zhang,

, Incremental Temporal Frequent Pattern Mining Based on Spark Streaming. IEEE In 12th International Conference on Intelligent Human-Machine Systems and Cybernetics. 2020: 12(2): 22-27.

A novel temporal frequent subgraph based mining algorithm using spark

Abstract

Keywords

1. Introduction

3. Graph preliminaries

4.2 Mining phase

Table 1 Frequent subgraphs of a social interaction network

4.4 Temporal frequency calculation

5. Experimental results and discussion

5.1 Experimental setup and data

Table 2 Simulation database

Table 3 Frequent subgraph for every year

References

Table 1
Frequent subgraphs of a social interaction network

Table 2
Simulation database

Table 3
Frequent subgraph for every year