CCGraMi: An Effective Method for Mining Frequent Subgraphs in a Single Large Graph

MENDEL — Soft Computing Journal, Volume 2d, No.gk, .2+2K#2` 2021, Brno, Czech RepublicX ISSN: 1803-3814 (Printed), 2571-3701 (Online) https://doi.org/10.13164/mendel.2021.k.0Ny CCGraMi: An Effective Method for Mining Frequent Subgraphs in a Single Large Graph Lam B.Q. Nguyen1,2, , Ivan Zelinka3,2 , Quoc Bao Diep2 1Faculty of Information and Communications, Kien Giang University, Kien Giang, Vietnam 2Faculty of Electrical Engineering and Computer Science, VSB-Technical University of Ostrava, Czech Republic 3Faculty of Electrical and Electronics Engineering, Ton Duc Thang University, Ho Chi Minh City, Vietnam nb[email protected] , ivan.zelink[email protected], [email protected], diepquo[email protected] Abstract In modern applications, large graphs are usually applied in the simulation and analysis of large complex systems such as social networks, chemical structures, computer networks, maps, traffic networks. Therefore, graph mining is also an interesting subject attracting many researchers. Frequent subgraph mining (FSM) in a single large graph is one of the most important branches of graph mining, and FSM is defined as finding all subgraphs in a dataset whose occurrences are greater than or equal to a given frequency threshold. Among all algorithms for FSM, the GraMi algorithm is considered the state of the art and many algorithms have been proposed to improve this algorithm. In 2020, the SoGraMi algorithm was proposed to optimize the GraMi algorithm and presented an outstanding performance in terms of runing time and storage space. We propose a new algorithm in this paper to improve SoGraMi based on connected components, called CCGraMi (Connected Components GraMi). Our experiments on four real datasets (both directed and undirected) show that the proposed algorithm can outperform SoGraMi in terms of running time as well as memory requirements. Keywords: Data Mining, Pruning Techniques, Single Large Graph, Subgraph Mining, Weighted Subgraph. Received: 15 November 2021 Accepted: 20 December 2021 Published: 21 December 2021 1 Introduction Large graphs are commonly used in practical applications such as social network mining [5], decision support systems [30], web mining [11,26], map model analysis [6], consulting systems [25], criminal investigations [5], information retrieval systems, structural graph clustering [18], etc. Therefore, FSM plays an important role in research purposes as well as reallife applications [8,31]. FSM for a large graph has attracted many researchers in recent years with many published studies [1,10,17,23,24,29]. Since the graph is a non-linear structure and the complexity is NP-hard (nondeterministic polynomial time) [23], FSM has always been a challenging and interesting research area that attracts researchers [10,15,17,19,22,23]. For a real-life example, a sale company collects and analysis data on its customers [3] to find frequent customer groups to fine-tune its business strategies [22]. The single large graph Gin Fig. 1illustrates the list of their customers, in which each customer is a node in the large graph belonging to a group labeled A,B,C, or D, and the relationship (labeled x,y,z,tor w)of two customers is indicated by edges of the two those nodes. The main task of FSM algorithms is to find a set of all frequent subgraphs Sin a large graph G, these are all subgraphs whose number of appearances in a large D u6 B u13 C u7 C u14 C u9 C u2 D u3 A u0 B u15 C u16 B u4 A u10 A u5 B u11 D u17 A u12 D u8 B u1 x x x t x z w x y w y t y y t x z G z z t y z x x w z x Figure 1: A large graph G graph are greater than or equal to a given frequency threshold. A lot of methods search and count the number of isomorphisms for subgraph Sin the large graph G. However, almost all the popular FSM approaches require two computationally expensive phases: •Generating phase: in this phase, the mining process generates candidate subgraphs, and a frequent subgraph with kedges will generate candidate subgraphs with (k+ 1) edges. •Testing phase: this phase checks and counts the isomorphisms of each candidate subgraph, the mining process determines whether this candidate is frequent or not. However, in this phase, the computational cost is significantly high because 90 MENDEL — Soft Computing Journal, Volume 2d, No.gk, .2+2K#2` 2021, Brno, Czech RepublicX isomorphism processing is an NP-complete (nondeterministic polynomial) problem [10,23]. In 2014, the GraMi [10] was proposed as an FSM algorithm from a single large graph. It is based on a novel approach, only storing the templates of candidates and searching isomorphisms to mark corresponding values in the domains of the templates, this approach does not fully list all of each candidate’s appearances on the large graph [13]. GraMi had some optimizations to continuously enhance its performance: (1) unique labels, push-down pruning, decomposition pruning;(2) lazy search;(3)automorphisms. And then there are many methods introduced to improve this algorithm. ScaleMine algorithm [1] was proposed in 2016 as a parallel FSM, and SSIGRAM algorithm [24] was introduced in 2018 based on a new parallel approach using Spark. The two algorithms optimize GraMi by modeling distributed systems. In [23], PaGraMi was proposed as a new parallel approach, in which PaGraMi used multi-threads in a multi-core personal computer. In 2020, SoGraMi [23] was also developed to decrease the search space and improve the performance of the original GraMi. Although SoGraMi can overcome the weaknesses of the original GraMi algorithm, this algorithm still has some disadvantages: •The running time: because solving isomorphisms is an NP-complete problem [10,23], this leads the time for search isomorphisms is extremely long. •The memory requirements: the mining process consumes a lot of memory to store and evaluate, but the number of candidates is huge [17,23]. In this paper, based on connected components we propose two effective strategies, which help to reduce the running time as well as the memory requirements and our algorithm improves the performance of the SoGraMi algorithm [23]. We call this algorithm CCGraMi (Connected Components GraMi). The rest of our paper is organized as follows: Section 2surveys many related works of FSM. In Section 3, we present all the concepts and definitions of our strategies. Section 4 describes our two strategies and the algorithm in detail. Section 5 shows our experimental results on four directed/undirected graph datasets. Section 6 is our conclusion and some directions for further works. 2 Related Work Based on gSpan [29] algorithm, GraMi [10] searches for isomorphisms of a candidate subgraph because gSpan dramatically reduces the memory requirement compared to previous grow-and-store approaches [16,29]. The gSpan algorithm constructs a tree graph by using the DFS lexical order to represent all patterns, in the search tree, each node represents a DFS code, this is a hierarchical search space, called a DFS code tree [23]. The subgraph with size (k+1) is created by adding an edge to the subgraph with kedge in the tree, a subgraph with size (k+ 1) is corresponding to the level (k+ 1) of this tree and these nodes contain the DFS code for subgraph k. Instead of retaining all detected subgraphs, the gSpan algorithm only keeps a list of each detected subgraph, and then the isomorphisms searching process is only applied for subgraphs in the list. In 2014, the GraMi algorithm [10] was proposed for mining frequent subgraphs and patterns, it had optimizationssuchasuniquelabels[9,23], push-down pruning [10,23], decomposition pruning; lazy search; automorphisms. In which a new candidate will be constructed by adding an edge to a frequent subgraph, a frequent subgraph is a substructure of its generated candidate subgraphs. Based on minimum image-based support (MNI) the evaluation process of a candidate subgraph will stop when this subgraph has enough valid assignments to determine as frequent and the process ignores all remaining values to reduce the running time. ScaleMine [1] was proposed in 2016, and SSIGRAM [24] was proposed in 2018. They were novel parallel algorithms for FSM in a single large graph in order to optimize the GraMi algorithm in distributed systems [28]. In which, the process divides mining tasks into separate CPU cores [1] or threads on a cluster [24]. ScaleMine was implemented on the Shaheen II system (a modest cluster on a high-end Cray XC40 supercomputer), while SSIGRAM was run on the Apache Spark framework. Besides, there are some existing parallel approaches [23,28,32], such as DistGraph [28], Pregel-based systems [32], they are too computationally expensive systems and complex to carry out. The SIGRAM algorithm [16] need to restore all computational intermediary steps of MIS, but their complexity is an NP-hard problem [23], therefore this method is extremely computationally expensive [27]. In a labeled sparse undirected graph, this algorithm uses maximum independent sets (MIS) metrics to mine all frequent subgraphs. There are some algorithms which calculate the support for all mined subgraphs, such as gSpan [29], GraMi [10], O-FSM [7], ScaleMine [1], and SSIGRAM [24]. In isomorphism solving, there are several difficulties [7], because a lot of different appearances of a subgraph (isomorphisms) can overlap [10,12]. A process called graph compression used by SumISO [21] is to group vertices into super vertices, SumISO only searches isomorphisms on these compressed representations of the graphs. There is some algorithms’ goal that finds all frequent patterns by using inexact matching, such as APGM [14], this is an effective algorithm and it can mine frequent patterns with noise in real-life applications [5,14,20], the VEAM algorithm extends the APGM algorithm by a definition of approximate subisomorphism [2]. In 2020, the SoGraMi algorithm [23] was proposed to 91 MENDEL — Soft Computing Journal, Volume 2d, No.gk, .2+2K#2` 2021, Brno, Czech RepublicX L;mv2Mg2igHX,g**:`JB,gMg1772+iBp2gJ2i?Q/g7Q`gJBMBM;g6`2[m2Migam#;`T?bgBMggaBM;H2gG`;2g:`T? optimize GraMi by a sorting strategy. It sorts all frequent edges in the large graph by their supports; prioritizes to extend small frequent edges; in each candidate subgraph, the process will prioritize to process small domain edges. This efficient strategy significantly reduces the number of generated candidate subgraphs, the running time, and the memory requirements in comparison to the original GraMi algorithm. In this paper, we continue to improve the SoGraMi algorithm [23] with two proposals based on the definition of connected components. 3 Concepts and Definitions Definition 1 ([10,23]).Alarge graph G=(V,E,L) consists of a set of nodes V, a set of edges E,anda function Lassigns labels to all the nodes/edges in the graph G. Definition 2 ([10,23]).AgraphS=(VS,E S,L S)isa subgraph of G=(V,E,L)ifVS⊆V,ES⊆E;LS(v)= L(v),∀v∈VS;LS((u, v)) = L((u, v)),∀(u, v)∈ES. Definition 3 ([10,22]).Let S=(VS,E S,L S)bea subgraph in G=(V,E,L). A subgraph isomorphism I of Sto Gis a function f:VS→Vsatisfying: LS(v)= L(f(v)),∀v∈VS;(f(u),f(v)) ∈Eand LS((u, v)) = L((f(u),f(v))),∀(u, v)∈ES. To determine whether Sis frequent in Gor not, GraMi finds isomorphisms of Sin G, evaluates its support [23] based on the number of these isomorphisms. The authors define solution [10] as an isomorphism [4] for a subgraph and a constraint satisfaction problem (CSP) is represented as a tuple (X,D, C)inwhich: •X: an ordered set of variables (corresponding to nodes vin subgraph S) •D: a set of domains corresponding to variables X •C: a set of constraints between the variables in X. A solution for the CSP is an assignment to the variables in X, such that all constraints in C are satisfied. For example, the subgraph S(in Fig. 2) to large graph G(in Fig. 1) CSP is defined: {(v0,v 1,v 2), {{u0,u 5,u 10,u 12},{u1,u 4,u 11,u 13,u 15}, {u2,u 7,u 9,u 14,u 16}}, {v0=v1=v2,L(v0)=A, L(v1)=B, L(v2)=C, L(v0,v 1)=x, L(v1,v 2)=y}}. In the CSP model, for each node v∈Scorresponding to each variable xv∈Xhas a domain Dcontaining nodes u(in G) having the same node label as vin subgraph S, it means that ”ucan be assigned to v”. For example subgraph S(in Fig.2) has three nodes v0,v1and v2;thevariablev0has a domain x y A v0 B v1 C v 2 S Valid assignment Invalid assignment Variables and domains v 0 v 1 v 2 u 0 u 5 u 10 u 12 u 1 u 4 u 11 u 13 u 15 u 2 u 7 u 9 u 14 u 16 Figure 2: Valid and invalid assignments for subgraph S D(v0)=u0,u 5,u 10,u 12, these nodes uhave the same node label ”A” with v0, thus these nodes ucan be assigned to v0. Definition 4 ([23]).Assignment for a node u(in the domain D) to a node v(in subgraph S)isvalid iff there exists an isomorphism Iof Sin large graph Gthat corresponding assigns uto v,andinvalid otherwise. The GraMi algorithm uses the minimum imagebased support (MNI) [10] to evaluate each candidate subgraph whether that candidate is a frequent subgraph or not. The MNI support of Sin Gsatisfies a given frequency threshold τ,sG(S)≥τ, if every variable in Xhas at least τdistinct valid assignments. GraMi only searches for a number of isomorphisms of subgraph Sin the large graph Gthat is enough to determine whether Sis frequent [23], and it ignores all remaining isomorphisms to reduce the searching time. Definition 5 ([23]).The support of subgraph Sin large graph G(denoted by sG(S)) is the minimum number of all distinct valid assignments in the domains of S. sG(S)=min{t|t=|D(v)|,∀v∈VS} SoGraMi proposes a sorting strategy to optimize the original GraMi algorithm. SoGraMi sort all frequent edges based on ascending order of their support, which means that the process prioritizes mining lowfrequency subgraphs first; and in a subgraph, and the node with a smaller domain will be processed first. This sorting strategy [23] can significantly reduce the number of candidate subgraphs, decrease the runtime and the memory requirements. For example: In Fig. 2, the domain of v0and v1: |D(v0)|=|u0,u 5,u 10,u 12|=4 |D(v1)|=|u1,u 4,u 11,u 13,u 15|=5 SoGraMi algorithm sorts the frequent edges list fEdges(see the detail of fEdgesin Section 4.1), therefore the edge Ax −B(smallest domain in the fEdges list) will be processed first, and in edge Ax −B,node A(smaller domain in this edge) will be processed first. SoGraMi also searches for MNI support to determine whether Sis frequent [23], and it also ignores all remaining isomorphisms to reduce the searching time. Definition 6 ([23]).A subgraph Sis frequent in the 92 MENDEL — Soft Computing Journal, Volume 2d, No.gk, .2+2K#2` 2021, Brno, Czech RepublicX large graph Gif its support is greater than or equal to a given frequency threshold τ. For example: valid and invalid assignments for Sare shown in Fig. 2. sG(S)=min(|D(v0)|,|D(v1)|,|D(v2)|)= min(|u0,u 12|,|u1,u 13|,|u7,u 14|)=min(2,2,2) = 2 Because sG(S)≥τ,Sis a frequent subgraph in G. Remark. In this paper, we choose τ=2for all our examples. Although the performance of SoGraMi significantly overcomes that of the original GraMi algorithm, it still needs a lot of runtime and storage because of searching values in a domain of a candidate subgraph, a node can combine with all other nodes in this domain to form isomorphisms. This leads to the long runtime and the large memory requirements. In this paper, we continuously optimize our SoGraMi algorithm by two effective strategies based on connected components and we call it CCGraMi. In the first strategy, when evaluating a candidate subgraph, each node in its domain only combines to other nodes in the same connected component instead of combining to all available nodes in this domain, which decreases the runtime for the searching process (see detail in Subsection 4.1). In the second strategy, if a connected component does not have enough nodes to form an isomorphism, the process will delete this connected component to reduce the storage space (see detail in Subsection 4.2). 4 Proposal Algorithms 4.1 Searching Isomorphisms Based On Connected Components In SoGraMi algorithm, after pruning all infrequent edges in the large graph G (in Fig. 1), we have the remaining nodes and edges are shown as in Fig. 3. Because of deleting some nodes/edges, a large graph can be split into many separated connected components. An isomorphism is a connected subgraph, thus its nodes cannot exist in two or more connected components. In the first contribution of CCGraMi, this algorithm searches and split all nodes in G to separate connected components, the process for searching isomorphism will determine isomorphisms on each connected component instead of searching on an entire large graph. For example, the remaining nodes/edges in large graph Gare split into five separated connected components such as C1,C 2,C 3,C 4,and C5. In the SoGraMi algorithm, the mining process gets a frequent edge list fEdge [23] that contains all edges whose number of appearances is equal to or greater than a given frequency threshold; sorting this list by D u6 B u13 C u7 C u14 C u9 C u2 D u3 A u0 B u15 C u16 B u4 A u10 A u5 B u11 D u17 A u12 D u8 B u1 x x z y y y x z z y x z x C1 C2 C3 C4 C5 Figure 3: The frequent nodes/edges and five connected components in large graph G the support of each edge to decrease the number of candidate subgraphs. In Fig. 3, there are three edges in the fEdges as follow: fEdges ={Ax −B;By −C;Cz −D}. The SoGraMi algorithm has an advantage in comparison to the original algorithm GraMi, SoGraMi sorts and prioritizes the edges with small domains when generating candidate subgraphs. This sorting strategy [23] can decrease the number of candidates and reduce the time to process each candidate. For example, edge Ax −Bhas the smallest domain in the fEdges list, and node Ahas a smaller domain than node B,thus node Awill be processed first as in Fig. 4. A v0 B v1 x S1 x x x y A v0 B v1 A v2 A v0 B v1 C v2 … S 2 … S 3 … … … … Valid assignment Invalid assignment … … Nodes and domains v0 v1 v2 u0 u5 u10 u12 u1 u4 u11 u13 u15 u2 u7 u9 u14 u16 Nodes and domains v0 v1 v2 u0 u5 u10 u12 u1 u4 u11 u13 u15 u0 u5 u10 u12 Nodes and domains v0 v1 u0 u5 u10 u12 u1 u4 u11 u13 u15 Figure 4: Some subgraphs’ domains in the SoGraMi algorithm Both GraMi and SoGraMi only search isomorphisms for a subgraph Suntil they find the MNI support of S in Gthat is enough to evaluate Sas a frequent subgraph, they ignore all remaining isomorphisms to reduce the searching time [10,22]. The domain of v0 in S3has four nodes u0,u 5,u 10,and u12,the process performs sequentially these nodes. There are two isomorphisms of S3as u0,u 1,u 7and u12,u 13,u 14,therefore, nodes u0and u12 are valid assignments, while u5 and u10 are invalid assignments for v0. After searching isomorphism for u0, the mining process cannot search isomorphism for u5and u10 (in connected components C4) these steps cost time but they do not get any valid 93 MENDEL — Soft Computing Journal, Volume 2d, No.gk, .2+2K#2` 2021, Brno, Czech RepublicX L;mv2Mg2igHX,g**:`JB,gMg1772+iBp2gJ2i?Q/g7Q`gJBMBM;g6`2[m2Migam#;`T?bgBMggaBM;H2gG`;2g:`T? assignment. Meanwhile, u12 and u0are in the same connected component C1(in Fig. 3), but they are very far together in the domain to check together. We propose the first strategy in this paper, because an isomorphism cannot exist in two different connected components, we split all nodes in the domain based on each connected component. For example, when processing subgraph S6in Fig. 5(this is subgraph S3in Fig. 4), all nodes in its domain are split into five corresponding connected components. The mining process only searches isomorphisms on each connected component instead of the entire domain. After finding out two isomorphisms u0,u 1,u 7and u12,u 13,u 14,thatis enough to determine that S6is frequent, the searching process will stop to reduce running time. A v0 B v1 x S4 x x x y A v0 B v1 A v2 A v0 B v1 C v2 … S 5 S 6 … … … … Valid assignment Invalid assignment … … y … Nodes and domains v0 v1 v2 C1 u0 u12 u1 u13 u7 u14 C2 u2 C3 u9 C4 u5 u10 u4 u11 C5 u15 u16 Nodes and domains v0 v1 v2 C1 u0 u12 u1 u13 u0 u12 C4 u5 u10 u4 u11 u5 u10 C5 u15 Nodes and domains v0 v1 C1 u0 u12 u1 u13 C4 u5 u10 u4 u11 C5 u15 … Figure 5: Some subgraphs’ domains in CCGraMi 4.2 Pruning Subgraphs’ Domains Based On Connected Components The second contribution in this paper, we propose another strategy to prune subgraphs’ domains based on connected components. Any connected component that does not have enough nodes to form an isomorphism will be pruned to reduce the storage space and the time to search isomorphism on it. For example, subgraph S7and S8are the same subgraphs (they are S3in Fig.4and S6in Fig. 5), but S6has four connected components which do not have enough nodes in the domain to form any isomorphism; C2and C3lack of node with label ”A”and”B”; C4 lacksofnodewithlabel”C”; C5lack of node with label ”A”. These connected components cannot form any isomorphism of Ax −By −C(for subgraphs S7and S8in Fig. 6), deleting C2,C 3,C 4and C5,wehavethe domain as S8.Inthat,S7is a sample for a subgraph’s domain of the SoGraMi algorithm and S8is a sample for the CCGraMi algorithm. Early pruning all nodes in a domain that cannot form any isomorphism (it means they cannot be valid assignments), the mining process of CCGraMi can reduce the storagespaceaswellastheruntimetosearchisomorphism for these nodes. In the CCGraMi algorithm 1, after getting frequent x x y y A v0 B v1 C v2 A v0 B v1 C v2 S 8 S 7 Nodes and domains v0 v1 v2 C1 u0 u12 u1 u13 u7 u14 Nodes and domains v0 v1 v2 u0 u5 u10 u12 u1 u4 u11 u13 u15 u2 u7 u9 u14 u16 Figure 6: Comparision of subgraphs’ domains Algorithm 1 CCGraMi Input: AgraphGand a frequency threshold τ Output: All subgraphs Sin Gwhere sG(S)≥τ 1: resultList ←∅ 2: Let fEdges be a set of all frequent edges in G 3: Sort fEdges in ascending order based on the support 4: for each edge ed ∈fEdges do 5: resultList ←resultList ∪SubgraphExtend (ed,G,τ,fEdges) 6: Remove ed from fEdges 7: return resultList edges list fEdges (Line 2), CCGraMi sort this list (Line 3), it likely to SoGraMi algorithm. From Line 4to Line 6, the mining process extends these edges to form candidate subgraphs by SubgraphExtend() 2 [23]. In the function SubgraphExtend() 2, these are two phases of the mining process: •Generating phase: From Line 2to Line 6,this function combines each frequent subgraph with an edge in fEdge, the new candidate subgraph will be put into the candidateSet list. •Testing phase: From Line 7to Line 9, this function tests each generated subgraph in candidateSet by IsFrequent() function 3. If a candidate subgrpah is determined as frequent, this frequent subgraph will be extended recursively (Line 9) with all remaining edges in fEdges. Algorithm 2 SubgraphExtend Input: A subgraph S, a large graph G, a frequency threshold τand a set of frequent edges fEdges in G Output: All frequent subgraphs in Gextended from S 1: SList ←S, candidateSet ←∅ 2: for each edge ed ∈fEdges and node v∈Sdo 3: if ed can extend vthen 4: Let ext be an extended subgraph of Sby ed 5: if ext is not already generated then 6: candidateSet ←candidateSet ∪ext 7: for c∈candidateSet do 8: if IsFrequent(c, G, τ, fEdges)then 9: SList ←SList ∪SubgraphExtend (c, G, τ, fEdges) 10: return SList 94 MENDEL — Soft Computing Journal, Volume 2d, No.gk, .2+2K#2` 2021, Brno, Czech RepublicX Algorithm 3 IsFrequent Input: Subgraph S, large graph Gand a frequency threshold τand a set of frequent edges fEdges in G Output: true if Sis a frequent subgraph of G, false otherwise 1: Let ccList be a set of all connected components in fEdges 2: for each node vwith domain Ddo count ←∅ 3: if the size of any domain is less than τthen 4: return false 5: for element uof Ddo 6: for each connected component cc ∈ccList and u∈cc do 7: if cc does not have enough nodes for Sthen 8: Remove all node values in cc 9: if the size of any domain is less than τthen 10: return false 11: if uis already marked then 12: count++ 13: else if existing an isomorphism Iassign uto vthen 14: Mark all nodes of Iin corresponding domains 15: count++ 16: elseRemove u from the domain D 17: if count = τthen 18: Move to the next node v(Line 2) 19: return false count <τ and domain is exhausted 20: return true In the IsFrequent() function 3, the process iterates all node vin a candidate subgraph S(Line 2); for each node uin the domain of this subgraph (Line 5), instead of combining this node uwith all available nodes in the domain, our strategy only combine this node uwith the nodes in the same connected component (Line 6). Moreover, if any connected component does not have enough nodes to form isomorphism Ito subgraph S, our second strategy will remove all nodes in this connected component (from Line 7to Line 10). Let Nand nbe the number of nodes in large graph Gand subgraph S, respectively, the frequency threshold is τ. We denote psand pcas the possibilities that a node in the domain of a node is valid in the SoGraMi and CCGraMi, respectively. In total, the complexity bound of IsFrequent() function 3in SoGraMi is O(n.τ/ps.Nn−1)[10,23]. In our strategies, let Vbe the set of nodes and E be the set of edges in the large graph G, the wellknown complexity of BFS for getting all connected components (Line 1in IsFrequent() function 3)is O(|E|+|V|). Because of early deleting node values in the domain, this leads to the smaller domain, thus finding τvalid assignments will be faster and it increases the possibility that pcis greater than ps. Moreover, Nis the number of all the nodes in the large graph G, but in CCGraMi, Nwill be split to kconnected components. It means that N= N0+N1+··· +Nk−1. In total, the complexity bound of IsFrequent() function 3in CCGraMi is O(n.τ/pc.(Nn−1 0+Nn−1 1+···+Nn−1 k−1)). We have that: pc≥ps(1) Nn−1≥(Nn−1 0+Nn−1 1+···+Nn−1 k−1)(2) according to the property of polynomial expansion. Based on Eq. 1and Eq. 2:O(n.τ/ps.Nn−1)≥ O(n.τ/pc.(Nn−1 0+Nn−1 1+···+Nn−1 k−1)), in the worst case, if k= 1 (there is only one connected component in the large graph G), the complexity of the two algorithms is equal. 5 Experimental Evaluation In this section, we implement and compare the performances of GraMi, SoGraMi, and the new algorithm CCGraMi. All our experiments were conducted with the Java SE Development Kit 8, a system with Windows 10, using an Intel Core i5, 4 threads, 3.2GHz CPU, equipped with 4GB RAM. We compare three algorithms on criteria: runtime and memory requirements, on four datasets (both directed and undirected), our new algorithm CCGraMi shows that it can overcome the two previous algorithms. We recorded the all results on four datasets (Tab. 1): •MiCo: This is a large size undirected graph which contains 100,000 nodes and over one million edges. It describes Microsoft’s co-author information, in which the nodes are the authors and their labels are the areas of interest, each edge in this graph represents the collaboration among two authors, the number of co-author papers is the edge label of twonodes.Weusethisdatasetwiththesameinformation as in the SoGraMi paper to show the efficiency of our optimizations in the new algorithm CCGraMi [23]. •Facebook: This dataset is downloaded from http: //snap.stanford.edu/data/ and it is an undi95 MENDEL — Soft Computing Journal, Volume 2d, No.gk, .2+2K#2` 2021, Brno, Czech RepublicX L;mv2Mg2igHX,g**:`JB,gMg1772+iBp2gJ2i?Q/g7Q`gJBMBM;g6`2[m2Migam#;`T?bgBMggaBM;H2gG`;2g:`T? Table 1: The features of four datasets Dataset Type Nodes Node labels Edges Edge labels MiCo Undirected 100,000 29 1,080,298 106 Facebook Undirected 4,389 20 88,235 36 p2p-Gnutella09 Directed 8,114 25 26,013 40 CiteSeer Directed 3,312 6 4,732 101 rected dataset consisting of 4,389 nodes and 88,235 edges collected via the Facebook application from survey respondents. We use this dataset with the same information as in the SoGraMi paper to show the efficiency of the new algorithm CCGraMi. The original dataset does not have nodes and edges labels, we added randomly 20 distinct node labels and 36 distinct edge labels with the ratings in the SoGraMi paper [23]. •p2p-Gnutella09: This dataset is a medium-size directed dataset downloaded from http://snap. stanford.edu/data/. It is a sequence of snapshots for the Gnutella peer-to-peer file-sharing network. There are nine Gnutella network snapshots collected in August 2002. In which, the nodes represent the hosts in the Gnutella network topology, and the connections between the Gnutella hosts are the edges in this graph. Likely to Facebook dataset, we add these randomly 25 distinct node labels and 40 distinct edge labels with the following ratings in Tabs. 2and 3,respectively. •CiteSeer: This is a small size directed graph dataset including 3,312 publications, each publication is corresponding to a node and 4,732 citations between the publications (each citation corresponds to an edge). Each node has a label that presents a field of Computer Science and each edge has a label (from 0 to 100), this edge label is the similarity between two publications, in which the smaller the label, the higher the degree of similarity. Likely to MiCo and Facebook datasets, we use the CiteSeer dataset with the same information as in the SoGraMi paper to show the efficiency of the new algorithm CCGraMi [23]. Using these four datasets with undirected and directed graphs, we use different frequency thresholds τ to demonstrate that our new algorithm has outstanding performance in comparison to GraMi and SoGraMi algorithms, and we try to reduce the frequency thresholds τuntil our personal computer cannot execute it any more. First, we record and compare the runtime of three algorithms in all four datasets. In all datasets, the lower the threshold, the better the CCGraMi algorithm is in comparison to the two previous algorithms. Moreover, CCGraMi always crashes at lower thresholds in comparison to GraMi and SoGraMi. The MiCo dataset is a large undirected dataset (in Fig. 7), because of the computing power and storage capacity of the computer, we only take the tests at high thresholds in our experiments. Our experiments did not complete at τ=9,200 because of exceeding the internal memory. At the lowest threshold τ=9,250, CCGraMi can reduce the runtime to 75.5% in comparison to that of SoGraMi, and 21.7% to original GraMi. All three algorithms crash at the threshold τ= 9200. 0 1,000 2,000 3,000 4,000 5,000 6,000 9650 9550 9450 9350 9250 Time in seconds Support threshold τ MiCo dataset GraMi SoGraMi CCGraMi Figure 7: Running time for MiCo dataset With the Facebook dataset, a medium undirected dataset (in Fig. 8), the mining process can implement at low thresholds. CCGraMi can reduce the runtime to 87.2% of that of SoGraMi, and 56.5% of that of the original GraMi at τ= 125. At τ= 120, CCGraMi’s experiment can be implemented with 348.322 seconds, SoGraMi needs 404.538 seconds, while GraMi crashes because it exceeds the available memory. 0 100 200 300 400 500 140 135 130 125 120 Time in seconds Support threshold τ Facebook dataset GraMi SoGraMi CCGraMi Figure 8: Running time for Facebook dataset With the p2p-Gnutella09 dataset, this is a mediumdirected dataset in Fig. 9. Our proposed algorithm shows that the running time at τ= 40 can be decreased to 85.0% that of the SoGraMi, to 71.9% of the original GraMi. At τ= 35, CCGraMi still runs and takes 442.531 seconds (82.9% in comparison to SoGraMi), SoGraMi costs 535.532 seconds, while GraMi is out of available memory at this threshold. 96 MENDEL — Soft Computing Journal, Volume 2d, No.gk, .2+2K#2` 2021, Brno, Czech RepublicX Table 2: The labels of nodes and their ratings Labels of nodes 1 2 3 4 5 6 7 8 9 10 11 12 13 Rating(%) 2015107.56.5 6 4 3.5 3 2.52.52.5 2 Labels of nodes 14 15 16 17 18 19 20 21 22 23 24 25 - Rating (%) 2 2 2 1.5 1.5 1.5 1 1 1 0.5 0.5 0.5 - Table 3: The labels of edges and their ratings Labelsofedges1234567891011121314 Rating (%) 22 13 10 8 7 5 3 2.5 2.5 2.5 2 1.8 1.6 1.2 Labels of edges 15 16 17 18 19 20 21 22 23 24 25 26 27 28 Rating (%) 1.2 1.1 1.1 1.1 1 1 1 1 0.9 0.9 0.9 0.9 0.8 0.8 Labels of edges 29 30 31 32 33 34 35 36 37 38 39 40 - - Rating (%) 0.8 0.7 0.6 0.6 0.3 0.3 0.2 0.2 0.2 0.1 0.1 0.1 - - 0 100 200 300 400 500 600 55 50 45 40 35 Time in seconds Support threshold τ p2p-Gnutella09 dataset GraMi SoGraMi CCGraMi Figure 9: Running time for p2p-Gnutella09 dataset With the CiteSeer dataset in Fig. 10,thisisasmall size directed dataset. Our proposed CCGraMi shows that the running time can be decreased to 78.3% that of the SoGraMi, to 66.7% of the original GraMi at the threshold τ= 12. At τ= 11, CCGraMi still runs and takes 490.653 seconds (77.6% in comparison to SoGraMi), SoGraMi costs 631.785 seconds, while GraMi is out of available memory at this threshold. 0 100 200 300 400 500 600 700 15 14 13 12 11 Time in seconds Support threshold τ CiteSeer dataset GraMi SoGraMi CCGraMi Figure 10: Running time for CiteSeer dataset Finally, we record and compare the memory requirements for the three algorithms GraMi, SoGraMi, and CCGraMi. Because CCGraMi prunes the domain of each candidate subgraph based on connected components which cannot form any isomorphism for this candidate, the memory requirement is also significantly reduced. For the MiCo dataset, because the numbers are small, the magnitude of our improvements (in Fig. 11) is not well illustrated. CCGraMi only reduces the memory requirements to 95.3% compared with SoGraMi, and 92.8% of that is needed for GraMi at the last threshold τ=9,250, and all the versions of algorithms crash at τ=9,200. 400 410 420 430 440 450 460 470 480 9650 9550 9450 9350 9250 Memory (MB) Support threshold τ MiCo dataset GraMi SoGraMi CCGraMi Figure 11: Memory requirements for MiCo dataset For the medium undirected Facebook dataset (in Fig. 12), there are many candidates and our results show that the improvement of CCGraMi is significant. The memory requirement of the new algorithm can be reduced to 72.1% that of the SoGraMi, and to 39.1% of the original GraMi at the threshold τ= 120. At the last threshold τ= 120, the GraMi algorithm crashes because it exceeds the available memory, CCGraMi can reduce the memory requirements to 71.6% compared to SoGraMi, which only needs 478.402 MB, and SoGraMi needs 667.515 MB. On the medium-size dataset p2p-Gnutella09, this is a directed dataset (in Fig. 13),becauseofalargenumber of generated candidate subgraphs, our approach shows significant results. At τ= 40, the memory requirement can be reduced to 56.2% that of the original GraMi and 76.1% that of SoGraMi. At the last threshold τ= 35, the original GraMi ran out of the available memory, SoGraMi needed 703.470 MB, while CCGraMi needs 75.7% of the storage space of SoGraMi, it only consumed 679.192 MB. On the CiteSeer dataset, the memory reductions are more significantly at the lower thresholds τ(in Fig. 14). 97 MENDEL — Soft Computing Journal, Volume 2d, No.gk, .2+2K#2` 2021, Brno, Czech RepublicX L;mv2Mg2igHX,g**:`JB,gMg1772+iBp2gJ2i?Q/g7Q`gJBMBM;g6`2[m2Migam#;`T?bgBMggaBM;H2gG`;2g:`T? 0 200 400 600 800 1000 140 135 130 125 120 Memory (MB) Support threshold τ Facebook dataset GraMi SoGraMi CCGraMi Figure 12: Memory requirements for Facebook dataset 0 200 400 600 800 1000 55 50 45 40 35 Memory (MB) Support threshold τ p2p-Gnutella09 dataset GraMi SoGraMi CCGraMi Figure 13: Memory requirements for p2p-Gnutella09 dataset With τ= 12, CCGraMi only consumes 82.1% and 68.1% in comparison to memory requirements of SoGraMi and GraMi. Especially, at the threshold τ= 11, the original algorithm GraMi crashed because of exceeding available memory but SoGraMi and CCGraMi still worked, our new algorithm reduced the memory to 81.1% in comparison to that of SoGraMi, SoGraMi consumed 959.834 MB, CCGraMi only needed 778.652 MB. 0 200 400 600 800 1,000 1,200 15 14 13 12 11 Memory (MB) Support threshold τ CiteSeer dataset GraMi SoGraMi CCGraMi Figure 14: Memory requirements for CiteSeer dataset 6 Conclusions and Future Work In this paper, we have proposed a new algorithm CCGraMi with two effective strategies based on connected components: Searching isomorphisms and Pruning subgraphs’ domains. Our experiments on four real datasets (both directed and undirected graphs) showed that the proposed algorithm CCGraMi has good results compared to the original algorithm GraMi and optimized algorithm SoGraMi in terms of running time and memory requirements. In the future, we will continue to research new methods based on connected components such as parallel processing on each connected component, arranging connected components by size to prioritize the processing of small-sized connected components to decrease storage space during the mining process, and combining high-powered computer systems to be able to mine larger graphs with smaller frequency thresholds. Acknowledgement: The following grants are acknowledged for the financial support provided for this research: Grant of SGS No. SP2022/22, VSBTechnical University of Ostrava. References [1] Abdelhamid, E., Abdelaziz, I., Kalnis, P., Khayyat, Z., and Jamour, F. Scalemine: Scalable parallel frequent subgraph mining in a single large graph. In SC’16: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (2016), pp. 716–727. [2] Acosta-Mendoza, N., Gago-Alonso, A., and Medina-Pagola, J. E. Frequent approximate subgraphs as features for graph-based image classification. Knowledge-Based Systems 27 (2012), 381–392. [3] Amaranatha Reddy, P., and Hazarath Murali Krishna Prasad, M. High utility item-set mining from retail market data stream with various discount strategies using egui-tree. Journal of Ambient Intelligence and Humanized Computing (2021), 1–12. [4] Ansari, Z. A., Jahiruddin, and Abulaish, M. An efficient subgraph isomorphism solver for large graphs. IEEE Access 9 (2021), 61697–61709. [5] Basu, K., Zhou, C., Sen, A., and Goliber, V. H. A novel graph analytic approach to monitor terrorist networks. In 2018 IEEE Intl Conf on Parallel Distributed Processing with Applications, Ubiquitous Computing Communications, Big Data Cloud Computing, Social Computing Networking, Sustainable Computing Communications (ISPA/IUCC/BDCloud/SocialCom/SustainCom) (2018), pp. 1159–1166. [6] Daniel, C. B., Saravanan, S., and Mathew, S. Gis based road connectivity evaluation using graph theory. In Transportation Research (Singapore, 2020), T. V. Mathew, G. J. Joshi, N. R. Velaga, and S. Arkatkar, Eds., Springer Singapore, pp. 213–226. [7] Dhiman, A., and Jain, S. Optimizing frequent subgraph mining for single large graph. Procedia Computer Science 89 (2016), 378–385. Twelfth International Conference on Communication Networks, ICCN 2016, August 19– 21, 2016, Bangalore, India Twelfth International Conference on Data Mining and Warehousing, ICDMW 2016, 98