Scaling Fine-grained Modularity Clustering for Massive Graphs

1 Introduction

Our work is motivated by one question. How can we efficiently extract fine-grained clusters included in a massive graph? Modularity clustering [Newman, 2004] is a fundamental graph analysis tool to understand complicated graphs [Takahashi et al., 2017; Sato et al., 2018]. It detects a set of clusters that maximizes a clustering metric, modularity [Newman, 2004]. Since greedily maximizing the modularity achieves better clustering results, modularity clustering is employed in various AI-based applications [Louni and Subbalakshmi, 2018; Shiokawa et al., 2018].

Although modularity clustering is useful in many applications, it has two serious weaknesses. First, it fails to reproduce ground-truth clusters in massive graphs due to the resolution limit problem [Fortunato and Barth´elemy, 2007]. Fortunato et al. theoretically proved that the modularity becomes larger until each cluster contains √m edges, where m is the number of edges included in a given graph. That is, modularity maximization prefers to find coarse-grained clusters regardless of the ground-truth cluster size. Second, modularity clustering requires a large computation time to identify clusters since it exhaustively computes all nodes and edges included in a graph. In the mid-2000s, modularity clustering was applied to social networks with at most thousands of edges [Palla et al., 2005]. By contrast, recent applications must handle massive graphs with millions or even billions of edges [Louni and Subbalakshmi, 2018] because graphs are becoming larger, and large graphs can be easily found. As a result, current modularity clustering methods [Blondel et al., 2008] need to consume several dozens of hours to obtain clusters from massive graphs.

1.1 Existing Approaches and Challenges

Many studies have strived to overcome these weaknesses. One major approach is to avoid the resolution limit effects by modifying the modularity clustering metric. Localityaware modularity metrics [Muff et al., 2005; Li et al., 2008; Sankar et al., 2015] are the most successful ones. Modularity is not a scale-invariant since it implicitly assumes that each node interacts with all other nodes. However, it is more reasonable to assume that each node interacts just with its neighbors. By modifying the modularity so that it refers only to neighbor clusters, the metrics successfully moderate the resolution limit effects for small-sized graphs. Costa, however, recently pointed out that graph size still affects such metrics [Costa, 2014]. That is, the metrics do not fully reproduce ground-truth clusters if graphs are large.

Instead of locality aware metrics, Duan et al. proposed a sophisticated method, correlation-aware modularity clustering (CorMod) [Duan et al., 2014]. They found that modularity shares the same idea with a correlation measure leverage [Piatetsky-Shapiro, 1991], and they removed biases that cause the resolution limit problem from modularity through a correlation analysis on leverage. Based on the above analysis, Duan et al. defined a different type of modularity named the likelihood-ratio modularity (LRM). Unlike other modularity metrics, CorMod can avoid producing coarse-grained clusters by maximizing LRM in massive graphs.

Although CorMod can effectively reproduce the groundtruth clusters, it still suffers from the large computational costs to handle massive graphs. Similar to the original modularity clustering, CorMod iteratively computes all nodes and edges to find clusters that maximize LRM. This incurs O(nm log n) time, where n and m are the numbers of nodes and edges, respectively. Several efficient methods have been proposed for modularity maximization such as the node aggregation and pruning approaches used in Louvain [Blondel et al., 2008] and IncMod [Shiokawa et al., 2013], but they cannot be directly applied to CorMod since they have no guarantee for the clustering quality in the LRM maximization.

This is because the approaches focus on only the modularity maximization, whereas CorMod employs more complicated function LRM. Thus, it is a challenging task to improve the computational efficiency of CorMod for fine-grained modularity clustering that approximate the ground-truth clusters.

1.2 Our Approaches and Contributions

We focus on the problem of speeding up CorMod to efficiently extract clusters that well approximate the ground-truth sizes from massive graphs. We present a novel correlationaware algorithm, gScarf, which is designed to handle billionedge graphs without sacrificing the clustering quality of CorMod. The basic idea underlying gScarf is to dynamically remove unnecessary computations for nodes and edges from the clustering procedure. To determine which computations to exclude, gScarf focuses on the deterministic property of LRM as it is uniquely determined using only the structural properties of clusters such as degrees and cluster sizes. That is, LRM does not need to be computed repeatedly for clusters with the same structural properties.

Based on the deterministic property, gScarf employs the following techniques to improve efficiency. (1) gScarf theoretically derives an incremental form of LRM, namely LRMgain, (2) It introduces LRM-gain caching in order to skip unnecessary LRM-gain computations based on the deterministic property, and (3) it employs incremental subgraph folding to further improve the clustering speed. As a result, our algorithm has the following attractive characteristics:

• Efficiency: gScarf achieves faster clustering than stateof-the-art methods proposed in the last few years (Section 4.1). We theoretically proved that gScarf has a smaller time complexity than the methods (Theorem 1).
• High accuracy: gScarf does not sacrifice the clustering quality compared to CorMod, even though gScarf drops computations for nodes and edges (Section 4.2). We theoretically confirmed that our approach does not fail to increase LRM during the clustering procedure.
• Easy to deploy: Our approach does not require any user-specified parameters (Algorithm 1). Therefore, gScarf provides users with a simple solution for applications using modularity-based algorithms.

To the best of our knowledge, gScarf is the first solution that achieves high efficiency and fine-grained clustering results on billion-edge graphs. gScarf outperforms the state-of-the-art methods by up to three orders of magnitude in terms of clustering time. For instance, gScarf returns clusters within five minutes for a Twitter graph with 1.46 billion edges. Although modularity clustering effectively enhances application quality, it has been difficult to apply to massive graphs. However, gScarf, which is well suited to massive graphs, should improve the quality in a wider range of AI-based applications.

2 Preliminary

Here, we formally define the notations and introduce the background. Let G = (V,E,W) be an undirected graph, where V , E, and W are sets of nodes, edges, and weights of edges, respectively. The weight of edge (i, j) ∈ E is initially set to Wi,j = 1. Graph clustering divides G into disjoint clusters Ci = (Vi, Ei), in which V = ⋃i Vi and Vi ∩ Vj = ∅ for any i ̸= j. We assume graphs are undirected only to simplify the representations. Other types of graphs such as directed graphs can be handled with only slight modifications. For further discussions, we detail how to apply our proposed approaches to the directed graphs in Appendix A.

2.1 Modularity

The modularity-based algorithms detect a set of clusters C from G so that C maximizes a clustering metric, called modularity [Newman, 2004]. Modularity measures the differences in graph structures from an expected random graph. Here, we denote tp(i) = ei/2m and ep(i) = (ai/2m)2 , where ei is a number of edges within Ci, ai is a total degree of all nodes in Ci, and m is the number of edges in G. Given a set of clusters C, modularity for C is given by the following function Q(C):

Note that, in Equation (1), ep(i) = (ai/2m)2 indicates the expected fraction of edges, which is obtained by assuming that G is a random graph. Thus, Q increases when each cluster Ci has a larger fraction of inner-edges ep(i) = ei/2m than that of the random graph.

Fortunato and Barthel´emy theoretically concluded that modularity suffers from the resolution limit problem [Fortunato and Barth´elemy, 2007]. They proved that Q(C) increases until each cluster includes √2m edges. That is, if a given graph is too large, the modularity maximization produces many super-clusters. Thus, modularity maximization fails to reproduce the ground-truth clusters in massive graphs.

2.2 Likelihood-ratioModularity

To overcome the problem, Duan et al. recently proposed CorMod [Duan et al., 2014]. CorMod employs the following modularity-based metric likelihood-ratio modularity (LRM), which guarantees to avoid the resolution limit:

where Pr(p, k, n) is (nk)pk (1 - p)n-k , which denotes the binomial probability mass function. Pr(tp(i), ei, 2m) shows the probability of obtaining Ci from G, whereas Pr(ep(i), ei, 2m) is the expected probability that Ci is taken from a random graph. As shown in Equation (2), LRM is designed to balance the size of Pr(tp(i), ei, 2m) and the ratio of Pr(tp(i),ei,2m) Pr(ep(i),ei,2m) for each cluster. If Ci is small, Pr(tp(i), ei, 2m) becomes large while the ratio of P r(tp(i),ei ,2m) Pr(ep(i),ei,2m) becomes small. On the other hand, if Ci is large, Pr(tp(i), ei, 2m) becomes small, the ratio becomes large. Thus, unlike modularity, LRM successfully avoids to produce super-clusters regardless of the graph sizes.

3 ProposedMethod: gScarf

We present gScarf that efficiently detects clusters from massive graphs based on LRM maximization. First, we overview the ideas underlying gScarf and then give a full description.

3.1 Ideas

Our goal is to efficiently find clusters without sacrificing clustering quality compared with CorMod. CorMod, which is a state-of-the-art approach, iteratively computes LRM for all pairs of clusters until LRM no longer increases. By contrast, gScarf skips unnecessary LRM computations by employing the following approaches. First, we theoretically derive an incremental form of LRM named LRM-gain. LRM-gain is a deterministic criterion to measure the rise of LRM obtained after merging a pair of clusters. Second, we introduce LRMgain caching to remove duplicate LRM computations that are repeatedly invoked. Finally, we employ incremental subgraph folding to prune unnecessary computations for nodes and edges. Instead of exhaustive computations for the entire graph, gScarf computes only the essential nodes and edges efficiently to find clusters.

Our ideas have two main advantages. (1) gScarf finds all clusters with a quite-small running time on real-world graphs. Our ideas successfully handle the power-law degree distribution, which is a well-known property of real-world graphs [Faloutsos et al., 1999]. This is because gScarf increases its performance if a lot of nodes have similar degrees. Hence, the above property lead gScarf to compute efficiently. (2) gScarf produces almost the same clusters as those of CorMod [Duan et al., 2014]. We theoretically demonstrate that gScarf does not miss chances to improve LRM, although gScarf dynamically prunes nodes and edges from a graph. Thus, gScarf does not sacrifice clustering quality compared to CorMod.

3.2 Incremental LRMComputation

We define LRM-gain, which measures the rise of the LRM scores obtained after merging two clusters.

Definition 1 (LRM-gain △Li,j). Let △Li,j be the gain of LRM obtained by merging two clusters, Ci and Cj, △Li,j is given as follows:

where △Pi,j and △Qi,j are the gains of the probability ratio and the modularity, respectively. Let C(i,j) be the cluster obtained by merging Ci and Cj , and their definitions are given

where P(Ci) is tp(i) ln tp(i) ep(i) if tp(i) > 0; otherwise, 0.

Note that △Pi,j represents a gain of the probabilityratio [Brin et al., 1997], which is a well-known correlation measure. Additionally, △Qi,j is the modularity-gain [Clauset et al., 2004] that measures the increase of the modularity after merging Ci and Cj into the same cluster C(i,j). From Definition 1, we have the following property:

Lemma 1. Let C(i,k) and C(j,k) be clusters obtained by merging Ck into Ci and Cj, respectively. We always have LRM(C(i,k)) ≥ LRM(C(j,k)) iff △Li,k ≥ △Lj,k.

Proof. We first transform Equation (2) by applying the Poisson limit theorem [Papoulis and Pillai, 2002] to the binomial probability mass functions, Pr(tp(i), ei, 2m) and Pr(ep(i), ei, 2m). Since tp(i) and ep(i) are significantly small, we can transform LRM(Ci) as follows:

By letting L(Ci) = 1 2m lnLRM(Ci), we have,

Clearly, △Li,k = L(C(i,k)) - L(Ci) - L(Ck).

We then prove LRM(C(i,k)) ≥ LRM(C(j,k)) ⇒ △Li,k ≥ △Lj,k. Since LRM(C(i,k)) ≥ LRM(C(j,k)), we clearly have LRM(C(i,k)) - LRM(Ci) - LRM(Ck) ≥ LRM(C(j,k)) - LRM(Cj) - LRM(Ck). Thus, we hold LRM(C(i,k)) LRM(Ci)LRM(Ck) ≥ LRM(C(j,k)) LRM(Cj)LRM(Ck) . By applying L(Ci) = 1 2m lnLRM(Ci) for the above inequality, L(C(i,k)) - L(Ci) - L(Ck) ≥ L(C(j,k)) - L(Cj ) - L(Ck). Hence, LRM(C(i,k)) ≥ LRM(C(j,k)) ⇒ △Li,k ≥ △Lj,k.

We omit the proof of △Li,k ≥ △Lj,k ⇒ LRM(C(i,k)) ≥ LRM(C(j,k)). However, it can be proved in a similar fashion of the above proof.

Lemma 1 implies that the maximization of LRM and LRMgain are equivalent. Consequently,gScarf can find clusters that increase LRM by using LRM-gain in a local maximization manner. We also identify two additional properties that play essential roles to discuss our LRM-gain caching technique shown in Section 3.3.

Lemma 2. △Li,j is uniquely determined by ei, ai, ej, aj, and ei,j, where ei,j is the number of edges between i and j.

Proof. Since tp((i, j)) = ei+2ei,j+ej 2m and ep((i, j)) = ( ai+aj 2m )2 , we can obtain △Pi,j from ei, ai, ej, aj, and ei,j. Furthermore, since △Qi,j = 2{ ei,j 2m - ( ai 2m )( aj 2m )} [Blondel et al., 2008], △Qi,j is clearly determined by ai, aj, and ei,j. Hence, we hold Lemma 2 by Definition 1.

Lemma 3. For each pair of clusters Ci and Cj, it requires O(1) time to compute its LRM-gain △Li,j .

Proof. Lemma 3 is trivial fromDefinition 1.

3.3 LRM-gain Caching

We introduce LRM-gain caching to reduce the number of computed nodes and edges. As shown in Lemma 2, LRMgain △Li,j is uniquely determined by a tuple of structural properties si,j = 〈ei, ai, ej, aj, ei,j〉. That is, if si,j equals to si′ ,j ′ , then △Li,j = △Li′ ,j ′ . Hence, once △Li,j and its corresponding structural property si,j obtained, △Li,j can be reused to compute other pairs of clusters whose structural properties are equivalent to si,j.

To leverage the above deterministic property, gScarf employs LRM-gain caching given as follows:

Definition 2 (LRM-gain caching). Let h be a hash function that stores △Lu,v with its corresponding structural property su,v. The LRM-gain caching h(si,j) for a structural property si,j = 〈ei, ai, ej , aj , ei,j〉 is defined as follows:

where si′ ,j ′ ≡ si,j denotes si′ ,j ′ is equivalent to si,j. gScarf skips the computation of △Li,j if si′ ,j ′ ≡ si,j is in h; otherwise, gScarf computes △Li,j by Definition 1.

To discuss the theoretical aspect of Definition 2, we introduce a well-known property called the power-law degree distribution [Faloutsos et al., 1999]. Under this property, the frequency of nodes with k neighbors is p(k) ∝ k-γ , where exponent γ is a positive constant that represents the skewness of the degree distribution.

Given the power-law degree distribution, LRM-gain caching has the following property according to Lemma 3:

Lemma 4. LRM-gain caching requires O(d2γ ) time during the clustering procedure, where d is the average degree.

Proof. To simplify, we assume that each cluster is a singleton, i.e. Ci = {i} for any i ∈ V . That is, si,j ≡ si′ ,j ′ iff ai = ai′ and aj = aj ′ because we always have ei = ej = 0 and ei,j = 1 for the singleton clusters. Since the frequency of nodes with k neighbors is p(k) ∝ k-γ , the expected number of pairs whose structural properties are equivalent to si,j is 2m · p(ai)p(aj). Thus, to cover the whole of a graph, gScarf needs to compute LRM-gain scores at least O( 2m 2m·p(ai)p(aj) ) ≈ O( 1 p(d)2 ) times during the clustering. From Lemma 3, each LRM-gain computation needs O(1) time, LRM-gain caching, therefore, requires O( 1 p(d)2 ) = O(d2γ ) times.

3.4 Incremental Subgraph Folding

We introduce incremental subgraph folding that removes unnecessary computations. Real-world graphs generally have high clustering coefficient [Watts and Strogatz, 1998]; they have a lot of triangles in a graph. However, a high clustering coefficient entails unnecessary computations in CorMod since the triangles create numerous duplicate edges between clusters. To avoid such computations, gScarf incrementally folds nodes placed in the same cluster into an equivalent node with weighted edges by extending theoretical aspects of the incremental aggregation presented in [Shiokawa et al., 2013]. First, we define the subgraph folding as follows:

Definition 3 (Subgraph Folding). Given G = (V,E,W), i ∈ Ci and j ∈ Cj, where Ci = (Vi,Ei) and Cj = (Vj,Ej). Let f be a function that maps every nodes in V \{Vi ∪ Vj} to itself; otherwise, maps it to a new node x. The subgraph folding of nodes i and j results in a new graph G′ = (V ′ ,E′ ,W ′ ), where V ′ = V \{Vi ∪ Vj} ∪ {x} and E′ = {(f(u), f(v))|(u, v) ∈ E} with updated weight values W ′f(u),f(v) such that

Definition 3 transforms two nodes i and j into an equivalent single node x with weighted edges. It replaces multiple edges between i and j into a self-loop edge (x, x) ∈ E′ with a weight value Wx,x, which represents the number of edges between i and j. Similarly, let k ∈ Γ(x), it merges edges (i, k) and (j, k) into weighted single edge (x, k). Thus, the subgraph folding reduces the number of nodes/edges from G.

Lemma 5. Let nodes i, j ∈ V be in the same cluster (i.e. Ci = Cj). If gScarf folds the nodes i and j into a new node w by Definition 3, then LRM taken from node w is equivalent to that of the C(i,j) composed of nodes i and j.

Proof. Recall Equation (7), we have L(Cw) = tp(w) ln tp(w) ep(w) - {tp(w) - ep(w)}. Since gScarf folds the nodes i and j into node w, ew = ei + ej + 2ei,j and aw = ai + aj by Definition 3.Thus, we have

By Lemma 1, if L(Cw) = L(C(i,j)), then we have LRM(Cw) = LRM(C(i,j)). Therefore, from Equation (9), we hold Lemma 5.

From Lemma 5, the subgraph folding does not fail to capture LRM-gain that shows a positive score. That is, gScarf reduces the number of duplicated edges without sacrificing the clustering quality of CorMod.

Based on Definition 3, gScarf performs subgraph folding in an incremental manner during the clustering procedure. gScarf greedily searches clusters using LRM-gain shown in Definition 1. Once cluster Ci is chosen, gScarf computes LRM-gain △Li,j for all neighbor clusters Cj ∈ Γ(Ci), where Γ(Ci) denotes a set of clusters neighboring Ci. After that, gScarf folds a pair of clusters that yields the largest positive LRM-gain based on Definition 3.

Our incremental subgraph folding has the following theoretical property in terms of the computational costs.

Lemma 6. A subgraph folding entails O(d) times, where d is the average degree.

Proof. By Definition 3, the subgraph folding requires to update the weights of each edge by traversing all neighboring clusters. Thus, a subgraph folding for Ci and Cj entails timecomplexity O(min{|Γ(Ci)|, |Γ(Cj )|}) = O(d).

3.5 Algorithm

Algorithm 1 gives a full description of gScarf. First, gScarf initializes each node as a singleton cluster, i.e. Ci = {i}, and it stores all clusters into a target node set T (lines 1-3). Then, gScarf starts the clustering phase to find a set of clusters C that maximizes LRM in a local maximization manner (lines 4-15). Once gScarf selects a cluster Ci from T (line 5), it explores neighboring cluster Cbest that yields the largest

Algorithm 1 Proposed method: gScarf

Input: A graph G = (V,E,W); Output: A set of clusters C; 1: T = ∅; 2: for each i ∈ V do 3: Ci = {i}, and T = T∪ {Ci}; 4: while T ̸= ∅ do 5: Get Ci fromT; 6: Cbest = Ci; 7: for Cj ∈ Γ(Ci) do 8: si,j = 〈ei, ai, ej , aj , ei,j 〉; 9: if h(si,j ) = null then h(si,j ) ← △Li,j ; 10: if h(si,j ) > h(si,best) then Cbest = Cj ; 11: if h(si,best) > 0 then 12: C′ ← fold(Ci,Cbest) by Definition 3; 13: T = T\{Ci, Cbest} ∪ {C′ }; 14: else T = T\{Ci}; 15: return C;

positive score of LRM-gain (lines 6-10). To improve the clustering efficiency, gScarf uses the LRM-gain caching h(si,j) in Definition 2; gScarf skips unnecessary computations based on the deterministic property shown in Lemma 2 (lines 8-10). If gScarf finds the structural property si′ ,j ′ ≡ si,j in h, then it reuses h(si′ ,j ′) = △Li′ ,j ′ instead of △Li,j; otherwise, it computes △Li,j by Definition 1 (line 9). After finding Cbest, gScarf performs the incremental subgraph folding for Ci and Cbest (lines 11-14). If h(si,best) = △Li,best > 0, gScarf contracts Ci and Cbest into a single cluster C ′ by Definition 3 (line 19). gScarf terminates when T = ∅ (line 4). Finally, it outputs a set of clusters C in (line 15).

The computational cost of gScarf is analyzed as follows:

Theorem 1. gScarf incurs O(m+d2γ ) time to obtain a clustering result from a graph G, where m is the number of edges in G, d is the average degree, and γ is a positive constant that controls the skewness of the degree distribution.

Proof. Algorithm 1 requires O(|T|) ≈ O(n) iterations for the clustering phase. In each iteration, gScarf invokes at most one subgraph folding (lines 18-21) that entails O(d) costs from Lemma 6. Thus, it has O(nd) = O(m) times to perform the clustering phase. Additionally, gScarf employs the LRM-gain caching during the iterations. As we proved in Lemma 4, it incurs O(d2γ ) times. Therefore, gScarf requires O(m+ d2γ ) times to obtain a clustering result.

The computational costs of gScarf are dramatically smaller than those of CorMod, which requires O(nmlogn) time. In practice, real-world graphs show d2γ ≪ m since they generally have small values of d and γ due to the power-law degree distribution [Faloutsos et al., 1999]. Specifically, as shown in Table 1, the real-world datasets examined in the next section have d < 39 and γ < 2.3. Thus, gScarf has a nearly linear time complexity against the graph size (i.e., O(m + d2γ ) ≈ O(m)) on the real-world graphs with the power-law degree distribution. Furthermore, our incremental subgraph folding effectively handles the clustering coefficient [Watts and Strogatz, 1998; Shiokawa et al., 2015] to further reduce the computational costs. Thus, gScarf has an even smaller cost than the one shown in Theorem 1.

4 Experimental Evaluation

In this section, we experimentally evaluate the efficiency and the clustering accuracy of gScarf.

We compared gScarf with the following state-of-the-art graph clustering baseline algorithms:

• CorMod: The original correlation-aware modularity clustering [Duan et al., 2014]. CorMod greedily maximizes the same criteria (LRM) as gScarf.
• Louvain: The most popular modularity clustering for large graphs [Blondel et al., 2008]. This method greedily maximizes the modularity in Equation (1).
• IncMod: The fastest modularity maximization method proposed by [Shiokawa et al., 2013]. It improves the efficiency of Louvain via incremental aggregation and pruning techniques.
• pSCAN: The density-based graph clustering recently proposed by [Chang et al., 2017]. It extracts clusters by measuring a density of node connections based on thresholds ϵ and µ. We set ϵ = 0.6 and µ = 5 as the same settings as used in [Chang et al., 2017].
• CEIL: A scalable resolution limit-free method based on a new clustering metric that quantifies internal and external densities of the cluster [Sankar et al., 2015]. It detects clusters by greedily maximizing the metric.
• MaxPerm: The resolution limit free method based on the localization approach [Chakraborty et al., 2014]. This method quantifies permanence of a node within a cluster, and it greedily explores clusters so that the permanence increases.
• TECTONIC: The motif-aware clustering method proposed by [Tsourakakis et al., 2017]. This method extracts connected components as clusters by removing edges with a smaller number of triangles than threshold θ. We used the recommended value θ = 0.06.

All experiments were conducted on a Linux server with Intel Xeon E5-2690 CPU 2.60 GHz and 128 GB RAM. All algorithms were implemented in C/C++ as a single-threaded program with the entire graph held in the main memory.

We used six real-world graphs published by SNAP [Leskovec and Krevl, 2014] and LAW [Boldi et al., 2011]. Table 1 shows their statistics. The symbols, d and γ denote the average degree and the skewness of the power-law degree distribution, respectively. As shown in Table 1, only YT, LJ, and OK have their ground-truth clusters. In our experiments, we also used synthetic graphs with their ground-truth clusters generated by LFR-benchmark [Lancichinetti et al., 2009], which is the de facto standard model for generating graphs. The setting are described in detail in Section 4.2.

4.1 Efficiency

We evaluated the clustering times of each algorithm in the real-world graphs (Figure 1). Note that we omitted the results of CEIL, MaxPerm, and TECTONIC for large graphs since they did not finish within 24 hours. Overall, gScarf outperforms the other algorithms in terms of running time. On average, gScarf is 273.7 times faster than the other methods. Specifically, gScarf is up to 1,100 times faster than CorMod, although they optimize the same clustering criterion. This is because gScarf exploits LRM-gain caching and does not compute all nodes and edges. In addition, it further reduces redundant computations incurred by triangles included in a graph by incrementally folding subgraphs. As a result, as we proved in Theorem 1, gScarf shows a nearly linear running time against the graph size. That is why our approach is superior to the other methods in terms of running time.

To verify how gScarf effectively reduces the number of computations, Figure 2 plots the computed edges in each algorithm for YT where a black (white) dot indicates that the (i,j)-th element is (is not) computed. gScarf decreases the computational costs by 83.9-98.3% compared to the other methods. The results indicate that the LRM-gain caching and the incremental subgraph folding successfully reduce unnecessary computations. This is due to the power-law degree distribution, which is a natural property of real-world graphs including YT. If a graph has a strong skewness in its degree distribution, there are numerous equivalent structural properties since the graph should have similar degrees. Hence, gScarf can remove a large amount of computations.

We then evaluated the effectiveness of our key approaches. We compared the runtimes of gScarf with its variants that exclude either LRM-gain caching or incremental subgraph folding. Figure 3 shows the runtimes of each algorithm in realworld graphs, where W/O-Caching and W/O-Folding indicate gScarf without LRM-gain caching and incremental subgraph folding, respectively. gScarf is 21.6 and 10.4 times faster than W/O-Caching and W/O-Folding on average, respectively. These results indicate that LRM-gain caching contributes more to the efficiency improvements even though it requires O(d2γ ) times. As discussed in Section 3.5, realworld graphs generally have small values of d and γ due to the power-law degree distribution. For instance, as shown in Table 1, the datasets that we examined have small d and γ, i.e., d ≤ 38.1 and γ < 2.3 at most. Consequently, the time complexity O(d2γ ) is much smaller than the cost for incremental subgraph folding in real-world graphs. Hence, gScarf can efficiently reduce its running time.

Figure 3: Effectiveness of key approaches.

4.2 Accuracy of Clustering Results

One major advantage of gScarf is that it does not sacrifice clustering quality, although it dynamically skips unnecessary computations. To verify the accuracy of gScarf, we evaluated the clustering quality against ground-truth clusters on both real-world and synthetic graphs. We used normalized mutual information (NMI) [Cilibrasi and Vit´anyi, 2005] to measure the accuracy compared with the ground-truth clusters.

Real-world graphs

Figure 4 (a) shows NMI scores of each algorithm in YT, LJ, and OK. We used the top-5000-community datasets [Leskovec and Krevl, 2014] as the ground-truth clusters for all graphs. In the datasets, several nodes belong to multiple ground-truth clusters. We thus assigned such nodes into the cluster where most of its neighbor nodes are located.

As shown in Figure 4, gScarf shows higher NMI scores than the other methods except for CorMod. In addition, gScarf has almost the same or slightly higher NMI score than the original method CorMod. This is because both employ Parameter mu

(c) LFR benchmark graphs varying n.

Table 2: Average cluster sizes.

LRM maximization to avoid the resolution limit problem. Furthermore, gScarf is theoretically designed not to miss any chance to increase LRM by Lemma 1 and Lemma 5. That is, the greedy LRM-gain maximization in gScarf is equivalent to that in CorMod. Hence, gScarf achieves better NMI scores even though it dynamically prunes unnecessary nodes/edges by LRM-gain caching and incremental subgraph folding.

To analyze the cluster resolution, we compared the average sizes of clusters extracted by each algorithm. As shown in Table 2, gScarf and CorMod effectively reproduce the cluster sizes of the ground-truth in large real-world graphs. This is because LRM maximization is designed to avoid the resolution limit problem [Duan et al., 2014], and LRM effectively extract cluster sizes that approximate the ground-truth clusters. On the other hand, other algorithms extract coarsegrained or significantly smaller clusters. Especially in the modularity maximization methods (i.e. Louvain and IncMod), they output larger clusters than the ground-truth since they grow clusters until their sizes reach √m.

Synthetic graphs

To verify the effects of graph structures and graph sizes, we evaluated the NMI scores on LFR-benchmark graphs. In Figure 4 (b), we generated graphs composed of 106 nodes with average degree 20 by varying the mixing parameter mu from 0.1 to 0.9. mu controls the fraction of neighbor nodes included in other clusters; as mu increases, it becomes more difficult to reveal the intrinsic clusters. In contrast, in Figure 4 (c), we used graphs generated by varying the number of nodes from 104 to 107 , where the average degree and mu are set to 20 and 0.5, respectively.

Figure 4 (b) shows that gScarf and CorMod achieve high accuracy even if the parameter mu increases, whereas most of the other methods degrade NMI scores for large mu. In addition, as shown in Figure 4 (c), gScarf also shows higher NMI scores than the others for large graphs since LRM effectively avoids to output super-clusters regardless of inputted graph sizes. Hence, gScarf efficiently detects clusters that effectively approximate the ground-truth clusters in massive graphs. From these results, we confirmed that gScarf does not sacrifice the clustering quality of CorMod.

5 Conclusion

We proposed gScarf, an efficient algorithm that produces fine-grained modularity-based clusters from massive graphs. gScarf avoids unnecessary computations by LRMgain caching and incremental subgraph folding. Experiments showed that gScarf offers an improved efficiency for massive graphs without sacrificing the clustering quality compared to existing approaches. By providing our efficient approaches that suit for massive graphs, gScarf will enhance the effectiveness of future applications based on the graph analysis.

Acknowledgements

This work was partially supported by JST ACT-I. We thank to Prof. Ken-ichi Kawarabayashi (National Institute of Informatics, Japan) for his helps and useful discussions.

A How to Handle Directed Graphs

We here detail gScarf modifications for directed graphs. As discussed in [Nicosia et al., 2009], we can handle the directed graphs in the modularity maximization by replacing ai to ain i aout i in ep(i), where ain i and aout i are in-degree and outdegree of node i, respectively. Thus, our LRM-gain caching can handle the directed graphs by replacing ai and aj of si,j in Definition 2 to ain i aout i and ain j aout j , respectively. Similarly, we need to modify Definition 3 so that the folding technique takes account of directions of edges. That is, our incremental subgraph folding can handle the directed graphs by aggregating in-degree edges and out-degree separately.