# Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergence arXiv: https://arxiv.org/abs/2305.11420 ยท HTML: https://mlsanity.com/paper/2305.11420/ ## Key facts - Cited by 9 papers in the map (data through 14 Oct 2026). - Builds on 44 of its 55 references that are in the map. - First posted on arXiv 19 May 2023. ## Builds on (most cited first, 30 of 44) - [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015) - [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014) - [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016) - [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016) - [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017) - [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019) - [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018) - [Group Normalization](https://mlsanity.com/paper/1803.08494/) (2018) - [Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification](https://mlsanity.com/paper/1909.06335/) (2019) - [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017) - [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020) - [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019) - [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019) - [Asynchronous Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1710.06952/) (2017) - [Stochastic Gradient Push for Distributed Deep Learning](https://mlsanity.com/paper/1811.10792/) (2018) - [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016) - [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018) - [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017) - [Decentralized Deep Learning with Arbitrary Communication Compression](https://mlsanity.com/paper/1907.09356/) (2019) - [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016) - [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018) - [Communication Compression for Decentralized Training](https://mlsanity.com/paper/1803.06443/) (2018) - [Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2102.04761/) (2021) - [MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling](https://mlsanity.com/paper/1905.09435/) (2019) - [Optimal Complexity in Decentralized Training](https://mlsanity.com/paper/2006.08085/) (2020) - [Exponential Graph is Provably Efficient for Decentralized Deep Training](https://mlsanity.com/paper/2110.13363/) (2021) - [A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates](https://mlsanity.com/paper/1704.07807/) (2017) - [Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development](https://mlsanity.com/paper/1702.05122/) (2017) - [Consensus Control for Decentralized Deep Learning](https://mlsanity.com/paper/2102.04828/) (2021) - [A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2006.11077/) (2020) ## Built on by (most cited first, 9 of 9) - [Log-Scale Quantization in Distributed First-Order Methods: Gradient-based Learning from Distributed Data](https://mlsanity.com/paper/2406.00621/) (2024) - [From promise to practice: realizing high-performance decentralized training](https://mlsanity.com/paper/2410.11998/) (2024) - [Scalable Decentralized Learning with Teleportation](https://mlsanity.com/paper/2501.15259/) (2025) - [DICE: Data Influence Cascade in Decentralized Learning](https://mlsanity.com/paper/2507.06931/) (2025) - [Enhancing Parallelism in Decentralized Stochastic Convex Optimization](https://mlsanity.com/paper/2506.00961/) (2025) - [SeedFlood: A Step Toward Scalable Decentralized Fine-Tuning of LLMs](https://mlsanity.com/paper/2602.18181/) (2026) - [Improved Convergence Analysis of Topology Dependence in Decentralized SGD](https://mlsanity.com/paper/2606.09154/) (2026) - [Accelerating MoE Model Inference with Expert Sharding](https://mlsanity.com/paper/2503.08467/) (2025) - [Decentralized SGD with Controlled Disagreement Finds Flatter Minima](https://mlsanity.com/paper/2602.02899/) (2026) ## Abstract (arXiv) Decentralized learning has recently been attracting increasing attention for its applications in parallel computation and privacy preservation. Many recent studies stated that the underlying network topology with a faster consensus rate (a.k.a. spectral gap) leads to a better convergence rate and accuracy for decentralized learning. However, a topology with a fast consensus rate, e.g., the exponential graph, generally has a large maximum degree, which incurs significant communication costs. Thus, seeking topologies with both a fast consensus rate and small maximum degree is important. In this study, we propose a novel topology combining both a fast consensus rate and small maximum degree called the Base-(k + 1) Graph. Unlike the existing topologies, the Base-(k + 1) Graph enables all nodes to reach the exact consensus after a finite number of iterations for any number of nodes and maximum degree k. Thanks to this favorable property, the Base-(k + 1) Graph endows Decentralized SGD (DSGD) with both a faster convergence rate and more communication efficiency than the exponential graph. We conducted experiments with various topologies, demonstrating that the Base-(k + 1) Graph enables various decentralized learning methods to achieve higher accuracy with better communication efficiency than the existing topologies.