Communication-Optimal Distributed Dynamic Graph Clustering


  • Chun Jiang Zhu University of Connecticut
  • Tan Zhu University of Connecticut
  • Kam-Yiu Lam University of Hong Kong
  • Song Han University of Connecticut
  • Jinbo Bi University of Connecticut



We consider the problem of clustering graph nodes over large-scale dynamic graphs, such as citation networks, images and web networks, when graph updates such as node/edge insertions/deletions are observed distributively. We propose communication-efficient algorithms for two well-established communication models namely the message passing and the blackboard models. Given a graph with n nodes that is observed at s remote sites over time [1,t], the two proposed algorithms have communication costs Õ(ns) and Õ(n + s) (Õ hides a polylogarithmic factor), almost matching their lower bounds, Ω(ns) and Ω(n + s), respectively, in the message passing and the blackboard models. More importantly, we prove that at each time point in [1,t] our algorithms generate clustering quality nearly as good as that of centralizing all updates up to that time and then applying a standard centralized clustering algorithm. We conducted extensive experiments on both synthetic and real-life datasets which confirmed the communication efficiency of our approach over baseline algorithms while achieving comparable clustering results.




How to Cite

Zhu, C. J., Zhu, T., Lam, K.-Y., Han, S., & Bi, J. (2019). Communication-Optimal Distributed Dynamic Graph Clustering. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 5957-5964.



AAAI Technical Track: Machine Learning