Distributed Graph Clustering and Sparsification

He Sun, Luca ZanettiACM Trans. Parallel Comput 2017 · OpenReview

TL;DR

This paper introduces a novel distributed algorithm for graph clustering that efficiently handles large, decentralized datasets. It achieves this by first creating a "sparse subgraph" that preserves the essential cluster structure of the original dense graph, and then applying a fast, distributed clustering algorithm to this sparser representation. This approach significantly reduces communication overhead, making it practical for massive real-world networks.

What Problem Does This Paper Address?

Graph clustering, the task of grouping nodes in a network based on their connectivity, is crucial for understanding complex systems in fields like social network analysis, machine learning, and data mining. However, many existing state-of-the-art clustering algorithms rely on computationally intensive spectral techniques or convex optimization. These methods are often impractical for modern, large-scale networks where data is distributed across multiple sites, making direct application difficult due to communication bottlenecks. The core challenge is to develop a clustering algorithm that is both simple to implement in a distributed setting and efficient in terms of communication and computation, especially for graphs with a clear underlying cluster structure.

Methods

The paper proposes a two-pronged approach:

  1. Cluster-Preserving Sparsification: The first key contribution is a distributed algorithm that takes a dense graph and produces a sparse subgraph. This subgraph is designed to provably preserve the "cluster-structure" of the original graph. Unlike previous sparsification methods that might require complex spectral solvers or combinatorial constructions, this algorithm is based on a simple edge sampling scheme. Each edge is sampled with a probability that depends on the degrees of its endpoints and a parameter related to the graph's spectral gap. This method is designed to be easily implemented in a distributed manner, with communication only occurring when an edge is sampled.
  2. Distributed Clustering Algorithm: Once a sparse subgraph is obtained, the paper presents a distributed algorithm to partition this subgraph into clusters. This algorithm operates in a fixed number of rounds (poly-logarithmic in the number of nodes) and involves three main steps:
  3. Seeding: A small set of "active" nodes are chosen probabilistically to initiate the process.
  4. Averaging: Each active node's state (represented by a vector) is iteratively updated based on its neighbors' states. This process is shown to approximate the projection onto the bottom eigenvectors of the graph Laplacian, which are known to capture cluster information.
  5. Query: Each node uses its final state vector to determine its cluster label.

The combination of these two steps allows for efficient distributed clustering while preserving the essential cluster structure.

Datasets

The paper evaluates its sparsification algorithm on three datasets:

  • Twomoons: A synthetic dataset with 1,000 to 15,000 points in 2D, where nodes are connected based on their Euclidean distance.
  • Gaussians: Another synthetic dataset with 1,000 to 15,000 points, sampled from a mixture of three isotropic Gaussians.
  • Sculpture: A real-world dataset derived from an image, where each pixel is a node. This dataset has approximately 11,000 nodes and 68 million edges, with a known cluster structure of 3 clusters.

These datasets are noted to be similar to those used in prior work on spectral sparsification, allowing for direct comparison.

Key Insights and Ideas

  • Sparsification Preserves Cluster Structure: The most significant insight is that a carefully designed edge sampling scheme can create a sparse graph that retains the essential cluster structure of a much denser graph. This is crucial because it allows us to apply efficient distributed algorithms on a significantly smaller representation.
  • Distributed Simplicity: The proposed sparsification method is remarkably simple to implement in a distributed setting, relying on local edge sampling and minimal communication. This contrasts sharply with more complex spectral sparsification techniques.
  • Bridging Sparsification and Clustering: The paper effectively demonstrates how sparsification can be a powerful preprocessing step for distributed graph clustering, enabling algorithms that would otherwise be too communication-heavy.
  • Poly-Logarithmic Rounds: The distributed clustering algorithm achieves its results in a poly-logarithmic number of rounds, which is highly efficient for large-scale networks.

Key Results

  • Sparsification Efficiency: The sparsification algorithm produces subgraphs with a significantly reduced number of edges. For instance, on the Twomoons and Gaussians datasets, the sparsified graphs retained only about 0.14% to 3.13% of the original edges. For the Sculpture dataset, it reduced 68 million edges to 320,000 (0.37%).
  • Clustering Quality: Spectral clustering applied to the sparsified graphs yielded results very close to those obtained on the original dense graphs. For the Twomoons and Gaussians datasets, the error ratios (err1 for original, err2 for sparsified) were consistently close. For the Sculpture dataset, the normalized cut value was nearly identical (0.0938 for original vs. 0.0935 for sparsified).
  • Distributed Algorithm Performance: The distributed clustering algorithm finishes in a poly-logarithmic number of rounds and achieves a low volume of misclassified nodes (o(vol(V))). The communication complexity is also efficient, being sublinear in the size of dense graphs.

Limitations and Future Work

  • Gap Assumption: Both the sparsification and clustering algorithms rely on a "gap assumption" related to the eigenvalues of the graph Laplacian (specifically, a gap between $\lambda_{k+1}$ and $\lambda_k$). While the paper notes that this assumption is often met in practice and experiments show good performance even with small gaps, it's a theoretical requirement.
  • Balanced Clusters: Theorem 1.2, which describes the distributed clustering algorithm, assumes that the optimal clusters are of "balanced size" (i.e., $vol(S_i) \ge \beta vol(V)$). The paper doesn't explicitly detail performance on highly unbalanced clusters.
  • Parameter Tuning: The sparsification algorithm uses a parameter $\tau$ that needs to be set appropriately. The paper mentions a doubling method to find a suitable $\tau$ and notes it adds only a poly-logarithmic factor to the complexity. However, the theoretical bound for $\tau$ depends on $\lambda_{k+1}$, which might not be known a priori.

Future work could explore relaxing the balanced cluster assumption for the distributed clustering algorithm and investigating more robust methods for parameter selection in the sparsification step. The paper also suggests that the presented techniques could be extended to other graph problems requiring distributed processing.

Summary updated

Abstract

Graph clustering is a fundamental computational problem with a number of applications in algorithm design, machine learning, data mining, and analysis of social networks. Over the past decades, researchers have proposed a number of algorithmic design methods for graph clustering. Most of these methods, however, are based on complicated spectral techniques or convex optimisation, and cannot be directly applied for clustering many networks that occur in practice, whose information is often collected on different sites. Designing a simple and distributed clustering algorithm is of great interest, and has wide applications for processing big datasets. In this paper we present a simple and distributed algorithm for graph clustering: for a wide class of graphs that are characterised by a strong cluster-structure, our algorithm finishes in a poly-logarithmic number of rounds, and recovers a partition of the graph close to optimal. One of the main components behind our algorithm is a sampling scheme that, given a dense graph as input, produces a sparse subgraph that provably preserves the cluster-structure of the input. Compared with previous sparsification algorithms that require Laplacian solvers or involve combinatorial constructions, this component is easy to implement in a distributed way and runs fast in practice.
BibTeX
@article{sun2017distributed,
  author = {He Sun and Luca Zanetti},
  title = {{Distributed Graph Clustering and Sparsification}},
  journal = {ACM Trans. Parallel Comput.},
  year = {2017},
  url = {https://openreview.net/forum?id=RQCQoD3fcA},
}
Figure