Communication-efficient distributed graph clustering and sparsification under duplication models

DOI10.1007/978-3-031-30448-4_27MaRDI QIDQ6057354zbMATH OpenFDO

Authors Chun Jiang Zhu

Publication date 4 October 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2302.09652

zbMATH Keywords

distributed graph clusteringgraph spannersgraph sparsificationspectral sparsifiers

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: In this paper, we consider the problem of clustering graph nodes and sparsifying graph edges over distributed graphs, when graph edges with possibly edge duplicates are observed at physically remote sites. Although edge duplicates across different sites appear to be beneficial at the first glance, in fact they could make the clustering and sparsification more complicated since potentially their processing would need extra computations and communications. We propose the first communication-optimal algorithms for two well-established communication models namely the message passing and the blackboard models. Specifically, given a graph on $n$ nodes with edges observed at $s$ sites, our algorithms achieve communication costs $ildeO(ns)$ and $ildeO(n+s)$ ($ildeO$ hides a polylogarithmic factor), which almost match their lower bounds, $Omega(ns)$ and $Omega(n+s)$, in the message passing and the blackboard models respectively. The communication costs are asymptotically the same as those under non-duplication models, under an assumption on edge distribution. Our algorithms can also guarantee clustering quality nearly as good as that of centralizing all edges and then applying any standard clustering algorithm. Moreover, we perform the first investigation of distributed constructions of graph spanners in the blackboard model. We provide almost matching communication lower and upper bounds for both multiplicative and additive spanners. For example, the communication lower bounds of constructing a $(2k-1)$-spanner in the blackboard with and without duplication models are $Omega(s+n^{1+1/k}logs)$ and $Omega(s+n^{1+1/k}max1,s^{-1/2-1/(2k)}logs)$ respectively, which almost match the upper bound $ildeO(s+n^{1+1/k})$ for both models.

Cites work

• A general framework for graph sparsification
• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• Approximate distance oracles
• Graph spanners in the message-passing model
• Graph spanners: a tutorial review
• Graph sparsification by effective resistances
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• Lower bounds for number-in-hand multiparty communication complexity, made easy
• New additive spanners
• On sparse spanners of weighted graphs
• Partitioning well-clustered graphs: spectral clustering works!
• Spectral sparsification of graphs
• The 4/3 additive spanner exponent is tight
• The communication complexity of multiparty set disjointness under product distributions
• The Communication Complexity of Optimization
• Tight bounds for distributed functional monitoring

Cited in

(1)

• A distributed algorithm for spectral sparsification of graphs with applications to data clustering

This page was built for publication: Communication-efficient distributed graph clustering and sparsification under duplication models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6057354)