Source-linked AI summary
Multi-level algorithms for modularity clustering
Andreas Noack, Randolf Rotta
TL;DR
Maximizing modularity is NP-hard, and the relative performance of many practical coarsening and refinement heuristics was not well established. The paper experimentally compares these algorithms and finds that simple coarsening with multi-level refinement is competitive with the best published heuristics.
Problem
Maximizing modularity is NP-hard, while the relative effectiveness and efficiency of proposed heuristic algorithms remain incompletely compared.
Method
The paper experimentally compares coarsening and refinement heuristics using achieved modularity and runtime, including new prioritizers and multi-level refinement.
Results
Simple coarsening with multi-level refinement outperformed several widely used or complex alternatives and was competitive with the best existing heuristics.
Takeaways & Limitations
Single-Step Greedy coarsening by Significance with Multi-Level Fast Greedy refinement is the paper’s recommended competitive heuristic.
Takeaways & Limitations
The comparison is not exhaustive because implementations and sufficient experimental results were unavailable for some proposed heuristics.
Abstract
from arXiv · showhide
Modularity is one of the most widely used quality measures for graph clusterings. Maximizing modularity is NP-hard, and the runtime of exact algorithms is prohibitive for large graphs. A simple and effective class of heuristics coarsens the graph by iteratively merging clusters (starting from singletons), and optionally refines the resulting clustering by iteratively moving individual vertices between clusters. Several heuristics of this type have been proposed in the literature, but little is known about their relative performance. This paper experimentally compares existing and new coarsening- and refinement-based heuristics with respect to their effectiveness (achieved modularity) and efficiency (runtime). Concerning coarsening, it turns out that the most widely used criterion for merging clusters (modularity increase) is outperformed by other simple criteria, and that a recent algorithm by Schuetz and Caflisch is no improvement over simple greedy coarsening for these criteria. Concerning refinement, a new multi-level algorithm is shown to produce significantly better clusterings than conventional single-level algorithms. A comparison with published benchmark results and algorithm implementations shows that combinations of coarsening and multi-level refinement are competitive with the best algorithms in the literature.
1 Introduction
Modularity clustering is important but computationally difficult, so practical work relies on heuristic coarsening and refinement algorithms. This paper compares their effectiveness and efficiency, finding strong performance from simple coarsening combined with multi-level refinement.
- Maximizing modularity is NP-hard, and exact algorithms scale only to graphs with a few hundred vertices.
- Coarsening heuristics merge cluster pairs from singleton clusters, while refinement heuristics move individual vertices between clusters.The paper examines both algorithm families and their combinations.
- Published evaluations are difficult to compare because they use different, often small, graph collections and lack a coherent design space.
- Combinations of simple coarsening and multi-level refinement are competitive with the best available heuristics.
2 Graph Clusterings and Modularity
The paper defines graph clusterings as partitions of vertices and modularity as a quality measure balancing observed and null-model intra-cluster connectivity. It also derives modularity changes for merging clusters and moving vertices.
- A graph clustering partitions the vertex set into disjoint, non-empty clusters.
- Modularity evaluates clusterings using actual intra-cluster edge weight relative to expected intra-cluster weight under a null model.
- The null model assigns expected edge weight between vertices according to the product of their degrees relative to the total graph degree.
- The paper gives formulas for modularity changes caused by merging two clusters or moving a vertex to another cluster.
3 Coarsening Algorithms
Coarsening algorithms repeatedly merge clusters according to merge priorities, using either single-step or multi-step strategies. The paper introduces simple prioritizers and reports limitations of some alternatives.
- Single-Step Greedy: Single-Step Greedy starts with singleton clusters and repeatedly merges the highest-priority pair while modularity increases.
- Multi-Step Greedy: Multi-Step Greedy merges several disjoint high-priority pairs per iteration to reduce extremely unbalanced cluster growth.
- Merge prioritizers: Merge prioritizers determine the order of cluster-pair merges, and implementation efficiency depends on dynamically maintaining adjacent-cluster edge data.
- Limitations: The Schuetz–Caflisch formula for selecting the multi-step merge count is unsuitable for weighted graphs because rescaling edge weights changes the formula but not the optimal clustering.
- Merge prioritizers: Weight Density and Significance are proposed as simple alternatives to Modularity Increase, with Significance balancing Modularity Increase and Weight Density.
- Limitations: Preliminary experiments suggest that more complicated and expensive prioritizers may not outperform the simple prioritizers considered here.
4 Refinement Algorithms
Refinement algorithms locally improve modularity by moving vertices between clusters. The paper considers greedy variants, including complete greedy refinement, while the broader study also develops multi-level refinement.
- Refinement algorithms repeatedly move individual vertices to clusters when the move increases modularity.
- The paper examines greedy refinement variants and introduces refinement across multiple levels of the coarsening hierarchy.
- Greedy refinement: Complete Greedy repeatedly performs the vertex move with the largest modularity increase until no improving move remains.
repeat
Fast Greedy refinement repeatedly moves each vertex to its best cluster, making each iteration cheaper than finding the globally best move. Its effectiveness relative to Complete Greedy refinement is evaluated experimentally.
- Fast Greedy refinement repeatedly scans all vertices and moves each to its best cluster until no improvement remains.Finding a vertex's best move is cheaper than finding the globally best vertex move.
- Its efficiency may come at the cost of effectiveness, motivating an experiment comparing it with Complete Greedy refinement.
- The algorithm is presented as a refinement procedure that takes a graph and clustering as input and returns a clustering.
repeat
This refinement variant repeatedly performs the best available move for each currently unmoved vertex, while retaining the best clustering encountered. Its implementation has Complete Greedy's worst-case runtime under the stated assumption but is slower in practice because it permits modularity-decreasing moves.
- Adapted Kernighan-Lin repeatedly selects the best move involving an unmoved vertex, moves it once, and records the highest-modularity clustering reached.
- The algorithm takes a graph and clustering as input and returns a clustering.
repeat
Multi-Level refinement addresses the limitations of individual vertex moves by refining across coarsened graphs, from the coarsest level back to the original graph. This design can improve clustering quality without necessarily increasing runtime substantially.
- Motivation: Multi-Level refinement can move groups formed during coarsening, avoiding sequences of sharply modularity-decreasing individual vertex moves.Individual-vertex refinement can get stuck in suboptimal clusterings because it cannot easily relocate densely interconnected groups.
- Multi-Level Clustering: The algorithm coarsens a graph, records multiple levels, then applies refinement from the coarsest level to the original graph while transferring cluster memberships between levels.At the coarsest level, every vertex starts in a separate cluster; finer-level memberships are copied from the preceding coarser level.
- Comparison: Single-Level refinement is the special case of Multi-Level refinement with a reduction factor of 100%.
- Efficiency: Additional coarsening levels may improve clusterings without significantly increasing runtime because cheap coarse-graph moves can replace many expensive fine-graph moves.
- Algorithm: Multi-Level Clustering combines a coarsener, a refiner, and a reduction factor, returning a clustering after successive coarsening and reverse-order refinement phases.The algorithm repeatedly constructs coarser levels until no clusters are merged, then projects and refines the clustering at each finer level.
- Related Work: The method is related to other multi-level approaches but differs from methods that only coarsen or use multi-level processing without the same refinement procedure.
5 Experiments
Experiments compare modularity-clustering heuristics by achieved modularity and runtime. Single-Step Greedy with Danon or Significance and Multi-Level refinement provides the strongest overall combination, while deeper refinement levels often add cost without much modularity gain.
- Experimental setup: The experiments measure heuristic effectiveness by mean modularity and efficiency by runtime across graph instances.Generated graphs are excluded, and graph-reading time is omitted from runtime measurements.
- Coarsening algorithms: Wakita’s HE and HN prioritizers are less effective than the alternatives and are not more efficient.Their lower effectiveness also appears in Wakita’s original implementation.
- Coarsening algorithms: Multi-Step Greedy is generally less effective and less efficient than Single-Step Greedy, except for limited gains with Modularity Increase.For Modularity Increase, Multi-Step Greedy is faster and slightly more effective at merge fractions of 2% and 5%.
- Refinement algorithms: 50% Multi-Level refinement is more effective than Single-Level refinement at similar efficiency, whereas lower reduction factors mainly increase Fast Greedy runtime.Reduction factors below 50% do not considerably improve modularity but significantly increase runtime for Fast Greedy.
- Comparative findings: Multi-Level refinement is consistently more effective across merge prioritizers, while Single-Step Greedy remains preferable for its simplicity and efficiency.With Multi-Level refinement, the best coarseners are similarly effective, but Single-Step Greedy is more effective without refinement.
- Comparative findings: The best tested combination is Single-Step Greedy coarsening with Danon or Significance and Multi-Level Fast Greedy refinement.Multi-Level Kernighan-Lin is an alternative when efficiency is not a concern; Danon and Significance outperform Modularity Increase especially with refinement.
6 Related Algorithms
The paper compares published modularity-clustering algorithms and implementations with the recommended SS+ML and SS-Sig+ML heuristics. These comparisons show competitive modularity, efficiency trade-offs, and limitations in the breadth of available evaluations.
- Scope and comparison: The review aims to show that SS+ML is competitive with existing modularity-clustering methods, while acknowledging that the comparison is not exhaustive.The authors note that some proposed heuristics lack published implementations or sufficient experimental results.
- Published benchmark results: SS+ML achieves modularities very close to mathematical programming approaches, while scaling to larger graphs at much lower computational cost.Compared with the best algorithms in other classes, SS+ML is very competitive and significantly better on large graphs.
- Experimental setup: The benchmark uses 23 unweighted graphs ranging from a few to 75k vertices, comparing publicly available implementations where supported.Some implementations could not process weighted edges or self-edges, restricting the usable graph subset.
- Implementation comparison: Our reimplementations roughly reproduce or slightly improve the mean modularities of published implementations, including Schuetz and Caflisch’s algorithm.Refinement is unavailable in the Wakita–Tsurumi and Clauset implementations and optional in Schuetz and Caflisch’s.
- Published implementations: SS-Sig+ML matches Reichardt and Bornholdt’s high modularity with substantially lower runtime, while Blondel et al. is faster but less effective.The simpler SS-Sig+SL variant also remains competitive with Schuetz and Caflisch’s more complex, parameterized method.
7 Summary and Conclusion
The paper organizes coarsening and refinement heuristics into a four-dimensional design space and experimentally identifies effective combinations. Single-Step Greedy coarsening by Significance with Multi-Level Fast Greedy refinement is competitive in modularity and efficiency against existing methods.
- Design space: The design space has four dimensions: merge fraction, merge prioritizer, refinement algorithm, and reduction factor.Merge fraction includes Single-Step and Multi-Step Greedy coarsening, while reduction factor includes Single-Level and Multi-Level refinement.
- Experimental conclusions: Several complex or widely used alternatives are outperformed by simpler or newly proposed choices, especially Significance prioritization with Single-Step Greedy coarsening and Multi-Level Fast Greedy refinement.The comparison specifically identifies Multi-Step Greedy coarsening, Modularity Increase prioritization, and Single-Level refinement as weaker alternatives.
- Practical comparison: The recommended heuristic is more efficient than algorithms with similar modularity and achieves higher modularity than algorithms with similar or better efficiency.This conclusion is based on comparisons with published implementations and benchmark results.
A The Benchmark Graph Collection
The benchmark collection documents the graphs used for the experiments and identifies their source collections. Graphs marked UW were used without edge weights and self-edges for comparisons with published implementations.
- Graph collection: The benchmark graph collection includes original graphs and largest connected components, with graphs labeled “main” restricted to the largest connectivity component.The graph source collection is listed for each graph.
- Graph preprocessing: Graphs in the UW subset were used without edge weights and self-edges for experiments involving published implementations.This preprocessing reflects the limitations of some external implementations.
- Documentation: Table 2 lists the benchmark graphs, while Table 3 lists their source collections and web addresses.The tables separate graph identities from source information.