FastEnsemble: A new scalable ensemble clustering method
Yasamin Tabatabaee Eleanor Wedell Minhyuk Park Tandy Warnow






Fast Ensemble Clustering  





Tabatabaee et al. 


Siebel School of Computing and Data Science, University of Illinois Urbana-Champaign, Urbana IL 61801

{warnow}@illinois.edu
 


FastEnsemble: A new scalable ensemble clustering method 
    Yasamin Tabatabaee10000-0002-7811-5989 
Eleanor Wedell10000-0002-7911-9156 
Minhyuk Park10000-0002-8676-7565 Tandy Warnow10000-0001-7717-3514
    September 9, 2024
=================================================================================================================================================






§ ABSTRACT 
Many community detection algorithms are stochastic in nature, and their output can vary based on different input parameters and random seeds. 
Consensus clustering methods, such as FastConsensus and ECG, combine clusterings from multiple runs of the same clustering algorithm, in order to improve stability and accuracy.
In this study we present a new consensus clustering method, , and show that it provides advantages over both FastConsensus and ECG. 
Furthermore,  is designed for use with any clustering method, and 
we show results using with Leiden optimizing modularity or the Constant Potts model.
is available in Github at 
<https://github.com/ytabatabaee/fast-ensemble>
<cit.>.








§ INTRODUCTION




Community detection, also known as clustering, is the problem of dividing the nodes of a given network into disjoint subsets so that each subset displays features of a community, such as increased edge density, separability from the rest of the network, strong internal edge connectivity, etc.  
Several community detection methods have been developed in the past few decades <cit.>, some of which employ randomness in different ways to produce a desirable community.
For example, some methods are based on modularity <cit.> or the constant Potts model (CPM) <cit.>, which are NP-hard optimization problems.
The popular software  Louvain <cit.> and Leiden <cit.>
provide effective heuristics for modularity, and Leiden also provides an effective heuristic for optimizing under the CPM criterion.


One of the difficulties in using clustering methods that optimize modularity or CPM is the variability in the outputs, as searches for NP-hard problems based on different starting points, random seeds, or tie-breaking rules often produce different results <cit.>.



To address these challenges,  consensus (or ensemble) clustering approaches have been proposed that use different algorithmic strategies to combine information from different runs in order to extract a reliable clustering, and 

these consensus approaches can lead to more robust and stable partitions, and improve the accuracy of the output clustering <cit.>. 



A class of consensus clustering methods, as introduced in <cit.>, take a network G as input and run a clustering algorithm (such as Leiden with different random seeds) on it np times to get np different partitions. Next, they summarize the information from these partitions (i.e., nodes that are frequently co-clustered together) into a co-classification matrix and create a new weighted network G^' from this matrix. The new network is again given to the clustering algorithm np times to produce np partitions. This procedure is continued until the network G^' converges to a stationary network after multiple iterations. Various flavors of this consensus approach have been proposed in the literature <cit.>.






Scalability is an issue for these approaches, as building the co-classification matrix  is itself computationally intensive.
FastConsensus <cit.> is a recent method that tries to address the scalability issue by using a sampling technique, where the co-classification matrix is only computed for a subset of node pairs. 
Another recent and  promising consensus  method is   Ensemble Clustering for Graphs (ECG) <cit.>, but  it uses a somewhat simpler technique than FastConsensus, which suggests that it should be even faster.







We report on a new consensus clustering method, .
The algorithmic technique in is very simple, omitting much of the sophisticated technicalities of both ECG and FastConsensus so that it can scale to very large networks.
can be run with any given clustering method, and can even be used to combine the outputs of different clustering methods.








In this study we evaluate  for use in modularity-optimization on synthetic networks with ground truth communities with up to ∼ 3.8M nodes. 
We compare to FastConsensus and ECG with respect to accuracy and runtime. Both ECG and are fast enough to run on the very large networks we analyze, but FastConsensus is slower. We also find that produces improved accuracy compared to FastConsensus and ECG on networks that are challenging to cluster accurately and matches or comes close to the same accuracy on the easier networks. 
The rest of this paper is organized as follows. We describe in Section <ref>.
In Section <ref>, we describe the performance study, including datasets, methods, and evaluation procedure.   Section <ref> includes the details of the experiments and their results. We discuss the trends in Section <ref> and conclude in Section <ref> with a summary and directions for future work. 
Supplementary Materials are available online at <cit.>.
 


§ FAST ENSEMBLE CLUSTERING






We have developed a basic algorithmic structure that can be used with one or a combination of clustering paradigms, and implemented it for use with Leiden optimizing CPM, Leiden optimizing modularity, and Louvain. 
While the code is. under active development and new features are being added, in


 this study we only explore two variants of this approach, which we now describe.




In its simplest form, uses three main parameters: the clustering method, the number of partitions np, and  the threshold t.
Given an input network N, uses 
 the specified clustering method to generate np partitions of  N, and then builds a new network on the same node and edge set but with the edges weighted by the fraction of the partitions in which the endpoints are in the same cluster. If a given edge has weight less than t, then the edge is removed from the network; hence the new network can have fewer edges than the original network.  
 The new weighted network is then clustered just once more using the selected clustering method.



Increasing the number np of partitions may improve accuracy and stability, but at a computational cost; therefore, for very large networks,  np defaults to 10. 
 
In Experiment 1 we use synthetic networks to determine a default setting for the parameter t.
However, setting t=1 produces a special case that we refer to as the Strict Consensus Clustering (SC).









§ PERFORMANCE STUDY





Due to space limitations, we provide a brief description of the performance study; see the supplementary materials document for full details.







 §.§ Networks




We used a selected set of synthetic networks, some available from prior studies, and some generated for this study.

Table <ref> provides a summary of empirical statistics, including network size and mixing parameters <cit.> for these networks.
Note that networks that have  mixing parameters of 0.5 or larger are considered “complex" and challenging to cluster  
while networks with much smaller mixing parameters are generally easy to cluster  <cit.>.






  
Training Experiments.
For the training experiment, we generated LFR networks using parameters taken from similar networks  used in  <cit.>, but with the exponent for the cluster size distribution modified to better fit real-world networks (see Supplementary Materials for further discussion). 
Each of these synthetic networks has 10,000 nodes with calculated mixing parameter values that vary between 0.196-0.978 (note that the model mixing parameters, which are used to generate the networks, are drawn from 0.1, 0.2, …, 1.0, but the resultant mixing parameters are different).







  
Testing Experiments.
We use 27 LFR <cit.> networks from <cit.>; these were generated using parameters from Leiden-mod and Leiden-CPM clusterings of five real-world networks: cit_hepph, the Curated Exosome Network (CEN), Open Citations (OC), wiki_topcats, and cit_patents.
Two of these LFR networks had a substantial percentage of ground truth clusters that were disconnected, and were not included in the experiment in <cit.>, and are also not used in this study, and LFR failed to return a network for one model condition.
We also use ring-of-cliques networks <cit.>,  Erdős-Rényi  graphs <cit.>, and graphs formed by merging Erdős-Rényi  graphs with LFR networks.

 
 












 §.§ Methods 



We include ,  ECG, FastConsensus,  and Leiden, each for modularity optimization (“Leiden-mod").
In the final experiment we examine and Leiden for CPM-optimization.








 §.§ Evaluation criteria


We report accuracy on networks with known ground-truth using Normalized Mutual Information (NMI) 
and Adjusted Rand Index (ARI) as implemented by the Scikit-learn <cit.> library.
We also report the F1-score.




We also compute false negative and false positive error rates, defined as follows.
By considering true and estimated clusterings each as an equivalence relation, and thus defined by a set of pairs (where (x,y) is in the relation if and only if nodes x and y  are in the same cluster), we can also define false negatives (pairs that are in the true clustering but missing in the estimated clustering), false positives (pairs that are in the estimated clustering but not in the true clustering), true positives (pairs that are in both the true and estimated clustering), and true negatives (pairs that are in neither clustering).
Using these, we report
the False Negative Rate (FNR) and False Positive Rate (FPR),  given by fn/fn+tp and fp/fp+tn respectively, where
fn denotes the number of false negatives, fp denotes the number of false positives, and tn denotes the number of true negatives.






 §.§ Experiments



We perform five experiments, four comparing pipelines that are based on modularity (i.e., Leiden-mod, used with Leiden-mod, FastConsensus, and ECG) and a final experiment that focuses on and includes CPM-optimization.
In each case, synthetic networks were used and accuracy was evaluated in comparison to the ground truth clusterings.
Except for Experiment 5, all analyses were given four hours of runtime and 64Gb of memory on the University of Illinois Campus Cluster; failures to complete within that time limit were noted.




  * Experiment 1: We set the default for the threshold parameter in 
  * Experiment 2: We evaluate modularity-based pipelines with respect to both accuracy and scalability on synthetic networks with 
    ∼ 10K
    to ∼ 3.8M  nodes.
     
  * Experiment 3: We evaluate clusterings on networks that are either entirely or partially Erdős-Rényi   graphs.
    
  * Experiment 4: We evaluate robustness to the resolution limit  on  ring-of-cliques networks with  up to 100K nodes.
   
      
  * Experiment 5: We evaluate the accuracy of on large  synthetic LFR networks (up to ∼ 3.8M nodes) 
      from <cit.>. 



Experiments 1, 2, and  5  use networks with a range of mixing parameters,  Experiment 3 uses networks with moderate to high mixing parameters,
and Experiment 4 uses networks with extremely low mixing parameters (Table <ref>).






§ RESULTS





 






 §.§ Experiment 1: Training experiment







In this first experiment we set the default value for the threshold parameter t,  so that edges with support below t are removed from the network.
In Fig <ref> (left), we  compare results for only three threshold values: t=0.2, 0.5, and 0.8. We see that overall the best accuracy across all the networks is obtained using t=0.8.
In Fig <ref> (right), we show results for just one of the networks with the mixing parameter 0.5, but allowing t = 0.1, 0.2, …, 0.9.
On this model condition, values  for t between 0.7 and 0.9 produce the best accuracy.
Based on this experiment, we set  t=0.8 as the default. 

Note the impact of the mixing parameter: while accuracy is very high for networks with the lowest mixing parameter, it quickly drops as the mixing parameter increases.
This reflects the discussion in  <cit.>.




 








 §.§ Experiment 2: Accuracy and scalability of clustering pipelines



We use two collections of synthetic networks in this experiment: the LFR networks based on modularity clusterings of large real-world networks from <cit.> 
(which go up to ∼ 3.8M nodes) and  the training datasets used in Experiment 1. 
Each analysis was limited to 4 hours and 64Gb of memory.

Results on LFR networks from <cit.>: For all the methods, the only network they completed on within four hours was cit_hepph, the smallest network with only ∼ 34K nodes, and
 all three methods had  nearly perfect ARI and NMI scores (Supplementary Materials).


We then allowed  all three methods to run for up to 48 hours on the four remaining networks. 
completed on all the remaining networks, using between 7 and 28 hours.
FastConsensus completed only on one of these networks (using 14.5 hrs),
where it had excellent accuracy that was somewhat better than .
 ECG completed on all networks,  using from 6 hrs to 36 hrs on each.
 Thus, and ECG were both faster than FastConsensus.
 ECG was  less accurate than on three networks and more accurate on one network, where both ECG and had  very high ARI/NMI scores, indicating that the network was relatively easy to cluster   (Supplementary
Materials).

Results on the training networks:  Fig <ref> shows that accuracy decreases for all methods as the model mixing parameter increases.
The method with the best accuracy for the two smallest model mixing parameters (0.1 and 0.2) is ECG, but then has the best accuracy for the larger model mixing parameters.
Both ECG and consistently match or improve on Leiden-mod. FastConsensus improves on Leiden-mod for the large mixing parameter values but is less accurate than  Leiden-mod for the smaller mixing parameters.   



 










    










 §.§ Experiment 3: Detecting unclusterable portions of the network




  
  Erdős-Rényi  graphs do not have valid communities, and so all nodes are best represented as being singleton clusters. We use Erdős-Rényi  graphs to evaluate  to what extent   clustering pipelines are able to reject community structure 
  by
  returning no or very few non-singleton clusters.
  We also create networks that are combinations of Erdős-Rényi  graphs and LFR networks, and see to what extent the clustering pipelines we examine produce communities that are limited to nodes that are in the LFR subnetwork.
  We evaluate these questions by examining both the cluster size distribution as well as by examining clustering accuracy.


    
    For Erdős-Rényi  graphs with very low values for density p   (Fig <ref> (top)), all pipelines tested have good accuracy,  returning mostly singletons and clusters of size 2 or 3. However,  as the density  p increases,  both ECG and Leiden-mod return  clusters that increase in size, indicating that they are  finding community structure in these random networks.
    At the two largest tested densities, FastConsensus also produces large clusters, while Strict Consensus and continue to return mainly small clusters. 
    

    
  

    We see somewhat different trends on networks that are combinations of Erdős-Rényi  graphs and LFR networks (Fig <ref> (bottom)).  Note that in this setting, FastConsensus and ECG have much better accuracy than on Erdős-Rényi  graphs, and only Leiden-mod has really poor accuracy.
    The two best methods are the two variants of Strict Consensus, with in third place. 

     




   















 §.§ Experiment 4: The Resolution Limit








The resolution limit for modularity was established in
<cit.>, which shows that under some conditions, an optimal modularity clustering will fail to return what are the “obvious" communities if they are too small.
Furthermore, <cit.>  provide as an example the family of ring-of-cliques networks, which are parameterized by the clique size k and the number n of cliques; in a ring-of-cliques  network, the cliques are placed in a ring, and each  clique is attached to the cliques on each side by a single edge.
They establish that  when 
 n ≥ k(k-1)+2,  then the optimal modularity clustering will put two or more cliques together into a single cluster, instead of the obviously preferred clustering that returns each clique as a separate cluster.


  

Here we examine whether consensus clustering methods can address this vulnerability of modularity-based clustering from an empirical perspective, using  ring-of-clique networks where each clique is of size k=10 but the  number n of cliques is allowed to vary.  
According to the previous paragraph, when n ≥ 91 then an optimal modularity clustering will group two or more of the cliques together.
Hence, we examine values of n that are both smaller and larger than n=91 in this experiment.
We examine Leiden-mod, FastConsensus, ECG, , and two ways of running the Strict Consensus that vary in terms of the number of partitions (np) on these networks.

As seen in  Fig <ref>,
for n=90 clusters, all the methods produce clusterings where each clique is a cluster, as desired. 
However, as the number of clusters increases, but not their sizes, then Leiden-mod starts merging cliques together, as predicted by the theory from <cit.>.
We also see that all the consensus clustering methods (e.g., FastConsensus, ECG, , and Strict Consensus) reduce the tendency to merge cliques into clusters, and that the Strict Consensus variants, especially with np=50, have  the best accuracy.
Interestingly, has poor accuracy, especially for the large numbers of clusters, where it is nearly as poor as Leiden-mod.

Fig <ref> also shows the FNR and FPR rates for these methods.
Note that all the methods return essentially zero FNR, indicating that no clique in the ring-of-cliques network is ever split apart.
On the other hand, the methods differ in terms of FPR, with Leiden-mod having high FPR rates except for n=90.  Again, is almost as poor as Leiden-mod,
while the other consensus methods have much lower FPR.










The Supplementary Materials shows results for the same data but for clusterings based on CPM-optimization. 
Note that, in contrast to the theory for modularity, <cit.> established that for every setting of the resolution parameter r, there will be a value N so that every optimal CPM(r) clustering of a ring-of-cliques network with n ≥ N cliques of size k will return the individual cliques as clusters. 
However, our experimental results show that for large enough numbers of cliques of size 10, Leiden-CPM groups cliques together into clusters.
This vulnerability occurs for all of the small resolution values, but disappears when r ≥ 0.01.
Fortunately,  using the Strict Consensus with Leiden-CPM fixes this issue, and returns just the cliques as the clusters.







 §.§ Experiment 5: Results on very large networks





 






 



 


In this experiment we
explore  and Leiden, using both modularity and CPM-optimization, on 27 large synthetic networks based on clustered real-world networks (Materials and Methods) that range up to  ∼ 3.8M nodes.
We allow up to 48 hrs runtime and provide 64Gb memory.
is nearly always at least as accurate as Leiden for all 27 model conditions, and tends to be more accurate when used with Leiden-mod or with Leiden-CPM with small resolution values (Fig. <ref>).  
Furthermore, the improvement in accuracy is sometimes very large.
Finally,  all analyses using CPM-optimization completed in under 3 hours, and only one of the modularity-based analyses required more than 24 hrs (Supplementary Materials).
Thus, this experiment establishes that can run on very large networks, up to 3.8 million nodes, and provides an improvement in accuracy over both Leiden-mod and Leiden-CPM.





§ DISCUSSION






This study reported results on synthetic networks for three consensus clustering methods:  ECG, FastConsensus, and FastEnsemble.
When optimizing for modularity, each of these reliably produced clusterings that were more accurate than Leiden-mod clusterings under many conditions, and did not reduce accuracy. 
However,  while both ECG and could run on the very large networks, FastConsensus was slower and failed to complete within the allowed 48 hr time period on nearly all networks with 1M or more nodes.

The consensus clustering methods showed very different performance in terms of accuracy.
While there were certainly some model conditions where there were often very little differences in accuracy, there were many conditions where provided the best accuracy, and some conditions where ECG or FastConsensus provided the best accuracy.

Experiments 3 and 4 focused on networks that are generally atypical of real-world networks and Experiment 5 only examined , and so we restrict this discussion to  Experiments 1 and 2.
Experiment 1 networks have a range of mixing parameters (and hence clustering difficulty), and this experiment suggests that has an advantage when the mixing parameter is not too small (and conversely, ECG has an advantage for the smallest mixing parameters). 
Experiment 2 includes these training networks and also modularity-based networks from <cit.>, which have very low mixing parameters (Supplementary Materials).
For the Experiment 2 networks, when FastConsensus or ECG is more accurate than , it is only by small amount, and the mixing parameter is small (Supplementary Materials).

Thus, these two experiments suggest that when ECG or FastConsensus is more accurate than , then the network is generally very easy to cluster, and the top methods have very high accuracy; moreover, these networks have low mixing parameters.
Here we note that CPM-based clusterings of real-world networks reported in <cit.> typically  have moderate to high mixing parameters (Supplementary Materials), suggesting that accuracy on networks with moderate or higher mixing parameters is the more important criterion.




















 
 


 


Finally, we only tested the Strict Consensus variant of in Experiments 3 and 4, which address performance on graphs that are largely unclusterable or that present the resolution limit challenge, respectively.
As we expected, the Strict Consensus  provides excellent results for those problems.

Thus, the tested consensus methods have different strengths, with best suited to networks that have at least moderate mixing parameters,  ECG and FastConsensus better suited to networks with small mixing parameters, and the Strict Consensus suited to the case where the goal is to avoid false discovery.
However, we also observed that FastConsensus was much slower than both ECG and , especially on the networks with more than 1,000,000 nodes.








































§ CONCLUSIONS

 


Our study showed that can provide very good results, matching or improving on both ECG and FastConsensus, two other consensus methods that use more sophisticated techniques, on many networks that are generally difficult to cluster, such as those with moderate to high mixing parameters.
However, ECG and FastConsensus  sometimes provide better results  than for networks with low mixing parameters, so that the three consensus clustering methods each have contexts where they have an advantage.
We also  found that ECG and are both faster and more scalable than FastConsensus.
Finally, we showed that , used with Leiden-CPM provided improved accuracy compared to Leiden-CPM, but Leiden-CPM is not enabled for use within  ECG and FastConsensus.


In this initial study,   we did not evaluate the feature in the code that allows a set of clustering algorithms, each with a weight, to be combined;
future work should  investigate whether these additional features lead to improvements in accuracy.
A better understanding of scalability requires  real-world networks, such as the Open Citations network with ∼ 13M nodes <cit.>, and so this is an obvious next step.
Our study was primarily performed using synthetic networks generated using LFR, but other simulators, including ABCD <cit.> and Stochastic Block Models, could be used; see <cit.> for review.



New approaches to consensus clustering have been developed, some of which have also been shown to be scalable to large networks; an example is the recent method in arXiv by Hussain et al. <cit.>;
future work will need to compare to these developments.









Data and Code Availability. The code and scripts used in this study are available at <https://github.com/ytabatabaee/fast-ensemble>. The data are available at <https://github.com/ytabatabaee/ensemble-clustering-data>.





spmpsci
 

