Dataset Information

Communication-Optimal Distributed Dynamic Graph Clustering.

ABSTRACT: 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.

SUBMITTER: Zhu CJ

PROVIDER: S-EPMC9275443 | biostudies-literature | 2019 Jul

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Communication-Optimal Distributed Dynamic Graph Clustering.

Zhu Chun Jiang CJ Zhu Tan T Lam Kam-Yiu KY Han Song S Bi Jinbo J

Proceedings of the ... AAAI Conference on Artificial Intelligence. AAAI Conference on Artificial Intelligence 20190701

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 hav ...[more]

PMID: 35833204

Similar Datasets

Project description:ObjectiveThe objectives of this paper are to 1) construct a new network model compatible with distributed computation, 2) construct the full optimal power flow (OPF) in a distributed fashion so that an effective, non-inferior solution can be found, and 3) develop a scalable algorithm that guarantees the convergence to a local minimum.Existing challengesDue to the nonconvexity of the problem, the search for a solution to OPF problems is not scalable, which makes the OPF highly limited for the system operation of large-scale real-world power grids-"the curse of dimensionality". The recent attempts at distributed computation aim for a scalable and efficient algorithm by reducing the computational cost per iteration in exchange of increased communication costs.MotivationA new network model allows for efficient computation without increasing communication costs. With the network model, recent advancements in distributed computation make it possible to develop an efficient and scalable algorithm suitable for large-scale OPF optimizations.MethodsWe propose a new network model in which all nodes are directly connected to the center node to keep the communication costs manageable. Based on the network model, we suggest a nodal distributed algorithm and direct communication to all nodes through the center node. We demonstrate that the suggested algorithm converges to a local minimum rather than a point, satisfying the first optimality condition.ResultsThe proposed algorithm identifies solutions to OPF problems in various IEEE model systems. The solutions are identical to those using a centrally optimized and heuristic approach. The computation time at each node does not depend on the system size, and Niter does not increase significantly with the system size.ConclusionOur proposed network model is a star network for maintaining the shortest node-to-node distances to allow a linear information exchange. The proposed algorithm guarantees the convergence to a local minimum rather than a maximum or a saddle point, and it maintains computational efficiency for a large-scale OPF, scalable algorithm.

Dataset Information

Communication-Optimal Distributed Dynamic Graph Clustering.

Publications

Communication-Optimal Distributed Dynamic Graph Clustering.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets