Scaling Fine-grained Modularity Clustering for Massive Graphs

Hiroaki Shiokawa, Toshiyuki Amagasa, Hiroyuki KitagawaIJCAI 2019 · DOI

TL;DR

This paper introduces gScarf, a novel algorithm that efficiently extracts fine-grained clusters from massive graphs, overcoming the limitations of existing modularity clustering methods. gScarf achieves significant speedups by intelligently pruning computations and incrementally folding subgraphs, while maintaining high clustering accuracy comparable to state-of-the-art methods.

What Problem Does This Paper Address?

Modularity clustering is a powerful technique for understanding complex graph structures. However, applying it to massive graphs (millions or billions of edges) faces two major hurdles:

  1. Resolution Limit Problem: Traditional modularity maximization tends to merge smaller, meaningful clusters into larger, coarser ones, failing to capture fine-grained structures. This is because modularity inherently favors larger clusters.
  2. Computational Cost: Existing methods are computationally expensive, requiring exhaustive iterative computations over all nodes and edges, which can take days for large graphs.

These limitations prevent the widespread application of effective clustering in areas dealing with large-scale networks, such as social media analysis, biological networks, and the internet.

Methods

gScarf tackles these challenges with a multi-pronged approach:

  • Likelihood-Ratio Modularity (LRM): Instead of standard modularity, gScarf uses LRM, a metric proposed by Duan et al. LRM is designed to avoid the resolution limit problem, allowing for the detection of fine-grained clusters regardless of graph size.
  • Incremental LRM Computation (LRM-gain): The core innovation is the derivation of an "LRM-gain" metric. This metric quantifies the increase in LRM when two clusters are merged. Crucially, LRM-gain is a deterministic criterion, meaning the decision to merge clusters based on LRM-gain is equivalent to directly maximizing LRM.
  • LRM-gain Caching: To avoid redundant calculations, gScarf caches LRM-gain scores. If the structural properties of a pair of clusters have been seen before, the cached LRM-gain is reused, significantly reducing computation. This is possible because LRM-gain is uniquely determined by the structural properties of the clusters.
  • Incremental Subgraph Folding: To further optimize performance, gScarf incrementally "folds" nodes within a cluster into a single equivalent node. This process effectively prunes redundant computations, especially in graphs with high clustering coefficients (many triangles), by merging edges and updating weights. This is inspired by aggregation techniques but adapted for LRM.

Datasets

The paper evaluates gScarf on:

  • Real-world graphs: YT, WK, LJ, OK, WB, and TW, sourced from SNAP and LAW. Statistics like number of nodes (n), edges (m), average degree (d), and ground-truth availability are provided.
  • Synthetic graphs: LFR-benchmark graphs, used to systematically evaluate performance under varying parameters (mixing parameter $\mu$ and number of nodes $n$).

Key Insights and Ideas

  • LRM-gain is equivalent to LRM maximization: This is a crucial theoretical insight. It means that a greedy approach using LRM-gain will find the same local optima as a full LRM maximization, enabling efficient pruning without sacrificing accuracy.
  • Deterministic properties are key to efficiency: The paper highlights that structural properties of clusters are deterministic for LRM-gain. This allows for caching and avoiding recomputation, a fundamental principle behind gScarf's speedup.
  • Subgraph folding efficiently handles graph structure: By incrementally folding nodes, gScarf cleverly deals with the high clustering coefficients common in real-world graphs, reducing computational overhead without compromising clustering quality.
  • Power-law degree distribution benefits gScarf: The paper notes that graphs with power-law degree distributions (common in real-world networks) are particularly well-suited for gScarf's caching mechanism, as many nodes share similar degrees, leading to more equivalent structural properties.

Key Results

  • Efficiency: gScarf is significantly faster than existing state-of-the-art methods. It achieves up to 1,100 times speedup over CorMod and is, on average, 273.7 times faster than other methods. For a Twitter graph with 1.46 billion edges, gScarf completes in under five minutes.
  • Accuracy: gScarf maintains high clustering accuracy, comparable to CorMod, as measured by Normalized Mutual Information (NMI). It outperforms other methods, especially on real-world graphs and synthetic graphs with high mixing parameters.
  • Cluster Size Approximation: gScarf and CorMod effectively reproduce ground-truth cluster sizes, avoiding the coarse-grained clusters produced by standard modularity methods.
  • Computational Cost Reduction: gScarf reduces the number of computed edges by 83.9-98.3% compared to other methods, demonstrating the effectiveness of its caching and folding techniques.

Limitations and Future Work

  • Limitations: The paper primarily focuses on undirected graphs, though it briefly outlines modifications for directed graphs in an appendix. The theoretical analysis of LRM-gain caching relies on the power-law degree distribution, which might not hold for all graph types.
  • Future Work: The authors suggest that gScarf's efficiency and accuracy on massive graphs can enhance various AI applications that rely on graph analysis. The paper also mentions handling directed graphs as a direction for future work.

Summary updated

BibTeX
@inproceedings{shiokawa2019scaling,
  author = {Hiroaki Shiokawa and Toshiyuki Amagasa and Hiroyuki Kitagawa},
  title = {{Scaling Fine-grained Modularity Clustering for Massive Graphs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/639},
}
Figure