Distributed k-Means and k-Median Clustering on General Topologies

1 Introduction

• Prior distributed clustering algorithms [15, 30, 11, 21, 24] lack theoretical clustering-quality guarantees, do not minimize communication, and often assume all-to-all or coordinator-based communication.The paper motivates its work by the distribution of data across locations, including sensor networks.Source: §1 · p. 1
• A coreset acts as a small proxy for the data, with approximately the same cost as the original data for any fixed set of centers.The paper uses this approach to reduce communication while retaining guarantees on clustering quality.Source: §1 · p. 1
• Each node builds a local portion of a global coreset using local data and communicated costs of local approximate solutions.The nodes then share their portions using message passing over general graphs.Source: §1 · p. 2
• For a fixed amount of communication, experiments on large-scale data sets report that the algorithm outperforms other coreset construction algorithms.The paper also reports that the algorithm performs well in practice.Source: §1 · p. 2
• The global coreset is smaller by a factor of n in general graphs and independent of communication topology.The construction distributes coreset building rather than combining local coresets; the earlier tree-based approach can require coresets quadratic in diameter for k-median and quartic for k-means.Source: §1 · p. 2

2 Preliminaries

• k-means minimizes the sum of squared distances to the nearest center, while k-median minimizes the sum of distances.Both objectives are NP-hard to minimize, and polynomial-time constant-approximation algorithms are available.Source: §2 · p. 3
• The task places data across n nodes on an undirected connected graph and seeks k centers that optimize global clustering cost with low communication.Communication is measured by the number of transmitted points, and latency is assumed to be absent.Source: §2 · p. 3

2.1 Coresets

• A coreset is a weighted point set whose cost approximates the original data's cost for every set of k centers.Local summaries can reduce the data transmitted to a coordinator.Source: §2.1 · pp. 3–4
• The proposed distributed construction produces a global coreset of centralized-construction size while communicating only a single value to each node.Simply combining local coresets would make the global coreset larger by a factor of n.Source: §2.1 · p. 4

3 Distributed Coreset Construction

• Each node builds a local coreset portion using its local approximation and communicated local costs; the union is an ϵ-coreset with probability at least 1 −δ and communication cost O(mn).The technique is also stated to extend to additive objectives such as k-line median.Source: §3 · p. 4

3.1 Proof of Theorem 1: k-median

• For k-median, local approximation centers can replace global centers in sampling and weighting, and the weighted sample with those centers approximates costs for any center set.The analysis bounds total communication by O(mn), including when nodes know only their neighbors.Source: §3.1 · pp. 6–7

3.2 Proof of Theorem 1: k-means

• For k-means, the proof separates good and bad points because squared-distance cost lacks the direct triangle-inequality bound used for k-median.Compensating for the 1/ϵ factor requires accuracy ϵ^2, resulting in O(1/ϵ^4) sample complexity.Source: §3.2 · pp. 7–8

4 Effect of Network Topology on Communication Cost

• Message passing collects construction information and shares local coreset portions; with a coordinator, collecting them costs the size of the coreset.The clustering algorithm can then run centrally on the collected coreset.Source: §4 · pp. 8–9

4.1 General Graphs

• On arbitrary connected graphs, an α-approximation subroutine yields a (1 + ϵ)α-approximation with probability at least 1 − δ.The algorithm uses message passing to share local costs and coreset portions.Source: §4.1 · p. 9, §4 · p. 9

4.2 Rooted Trees

• On a rooted tree of height h, an α-approximation subroutine yields a (1 + ϵ)α-approximation with probability at least 1 − δ.The theorem gives a communication-cost bound that depends on tree height h.Source: §4.2 · p. 10
• Avoiding coreset construction atop child coresets improves dependence on tree height over Zhang et al..In a grid network, any rooted spanning tree has height h = Ω(√n), where the paper reports a significant improvement over existing algorithms.Source: §4.2 · p. 10

Experimental Methodology

• Evaluation covers synthetic and real datasets, including YearPredictionMSD (515345 points in R90), over random, grid, and preferential graphs with varied partitions.Coreset quality is measured by running Lloyd’s algorithm on the coreset and global data and averaging the cost ratio over 30 runs.Source: §5 · p. 11

Results

• Uniform partitions perform nearly the same as COMBINE, and similarity-based partitions show similar results because both yield balanced local costs.With uniform costs and equal communication, the proposed algorithm reduces to COMBINE.Source: §5 · pp. 11–12
• 2% −5% lower solution costs and 10% −20% less communication at the same approximation ratio are reported versus COMBINE when local costs differ.These gains occur in weighted and degree-based partitions.Source: Figure 2 · p. 12, §5 · p. 12
• For a 1.1 cost ratio, coreset size and thus communication are only 0.1% −1% of the theoretical bound.This result is reported across the network topologies and partition methods shown in Figure 2.Source: §5 · p. 11, Figure 2 · p. 12
• About 20% improvement in cost over Zhang et al. is reported on spanning trees.The paper attributes the difference to Zhang et al. needing larger coresets to prevent accumulated errors.Source: §5 · p. 12

Distributed clustering algorithms

• Distributed adaptations sending sufficient statistics or data across iterations generally lack bounds on clustering quality or communication cost.A local-summary method [21] sends summaries to a central node and considers only a flat two-tier topology.Source: §6 · pp. 12–13

Coresets

• Prior coreset algorithms for k-median, k-means, and k-line median construct coresets centrally, unlike this paper’s distributed construction.Source: §6 · p. 13

Parallel clustering

• Parallel coreset merging and k-means|| address parallel clustering; k-means|| cannot build an ϵ-coreset for ϵ = o(1) and guarantees only constant approximation solutions.Source: §6 · p. 13

Random sampling

• The sampling approach has a multiplicative factor dependent on optimal average cost, can fare poorly with distant outliers, and does not apply to k-means.Its stated average-cost bound is twice optimal average cost plus an error bound ϵ.Source: §6 · p. 14

Other distributed problems

• Related distributed classification work and optimization work [22] include k-means under a separability assumption.Source: §6 · p. 14

Proof of Lemma 1

• The proof represents integer-weighted points by repeated copies, turning weighted sampling into uniform sampling before applying Theorem 4.For each point p, it includes m_p copies and defines each copy’s function value as f(p)/m_p.Source: A Proofs for Section 3 · p. 16
• The cited theorem’s dimension term is corrected with a log dim(F, P) factor because the two sources use different dimension definitions.The correction follows from the relationship d = O(d′ log d′).Source: A Proofs for Section 3 · p. 16
• For nearby p and bp, triangle-inequality steps bound the change in squared distances relative to either endpoint’s squared distance.The proof concludes with bounds of 8ϵ times each endpoint’s squared distance.Source: A Proofs for Section 3 · p. 17

• The algorithm performs nearly the same as COMBINE under uniform and similarity-based partitions, and its performance changes little across the reported topologies and partition methods.Source: B Complete Experimental Results · pp. 17–18, Figure 4 · p. 19, Figure 5 · p. 20
• With weighted partitions on random graphs, it improves k-means cost by 2%-5% and saves 10%-30% communication cost at the same approximation ratio.Source: B Complete Experimental Results · p. 17, Figure 4 · p. 19
• On spanning-tree graphs, the algorithm improves k-means cost by 10%-30% over Zhang et al. and achieves a better approximation ratio with only 10% communication cost.The comparison covers spanning trees of random, grid, and preferential graphs.Source: B Complete Experimental Results · p. 18, Figure 6 · p. 21, Figure 7 · p. 22