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 $\tilde{O}(ns)$ and $\tilde{O}(n+s)$, 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 provide almost matching communication lower and upper bounds for both multiplicative and additive spanners in the blackboard model.
The Challenge of Edge Duplication
In large-scale data science, graphs are often too big for one machine and are instead distributed across a cluster. Standard distributed algorithms for graph clustering (grouping nodes) and graph sparsification (reducing edges while keeping structural properties) usually assume that each edge lives on exactly one machine.
However, in real-world "duplication models," the same edge might be observed at multiple sites. This creates a major challenge: traditional "decomposable" methods—where each site simplifies its local graph and sends the result to a coordinator—fail because the union of these local simplifications no longer accurately represents the global graph's properties, such as its spectral Laplacian. As illustrated in the figure above, while the union of local spanners works for graphs without duplication (c), it fails to form a valid sparsifier for graphs with duplication (d).
Methods: From Resistance to Spanners
The paper shifts away from the standard "effective resistance" sampling method, which is difficult to coordinate when edges are duplicated. Instead, it uses graph spanners—subgraphs that preserve shortest-path distances—as a building block for spectral sparsifiers. By building a "t-bundle" of spanners, one can certify that non-spanner edges have low effective resistance and can be safely sampled.
Key algorithmic contributions include:
- Weighted Spanner Construction: Processes edges in logarithmic weight intervals. Sites coordinate to decide whether to add an edge to a global spanner based on whether it closes a short cycle.
- Uniform Sampling under Duplication: To achieve a global sampling probability across sites that share edges, the author proposes tuning local sampling probabilities ($p_e$) based on the known likelihood ($r_e$) of an edge residing at a specific site.
- Blackboard Model Adaptation: The author provides a systematic study of the "blackboard model," where sites communicate via a shared broadcast channel. This is shown to be significantly more efficient than the "message-passing" model (where all traffic goes through a central coordinator).
Key Results and Communication Complexity
The paper establishes new upper and lower bounds for communication complexity, demonstrating that the blackboard model can reduce costs for spanner construction from $O(ns)$ down to $O(n + s)$, a massive improvement for large networks. Using reductions from the "Multiparty Set-Disjointness" problem, the author proves that these costs are nearly optimal.
| Task | Message Passing (Upper Bound) | Blackboard (Upper Bound) |
|---|---|---|
| Spectral Sparsification | $\tilde{O}(ns)$ | $\tilde{O}(n + s)$ |
| (2k-1)-Spanner | $\tilde{O}(sn^{1+1/k})$ | $\tilde{O}(s + n^{1+1/k})$ |
| Additive +2 Spanner | $\tilde{O}(sn^{3/2})$ | $\tilde{O}(s + n\sqrt{n})$ |
Beyond complexity, the algorithms guarantee clustering results nearly as good as if all data were centralized on a single machine. Surprisingly, if the distribution of duplicates is known, the asymptotic communication cost for clustering remains the same as in non-duplication models.
Conclusion and Future Work
This work provides the first communication-optimal algorithms for graph clustering and spectral sparsification in distributed environments where edges may be duplicated. While powerful, the current uniform sampling method assumes that the probability of an edge residing at a specific site is known. Future research may focus on relaxing this assumption for arbitrary distributions and developing "local clustering" methods where communication costs depend only on the size of the retrieved cluster rather than the entire graph.
Summary updated