Revisiting 1-peer exponential graph for enhancing decentralized learning efficiency

For communication-efficient decentralized learning, it is essential to employ dy?namic graphs designed to improve the expected spectral gap by reducing deviations from global averaging. The 1-peer exponential graph demonstrates its finite-time convergence property–achieved by maximizing the expected spectral gap–but only when the number of nodes n is a power of two. However, its efficiency across any n and the commutativity of mixing matrices remain unexplored. We delve into the principles underlying the 1-peer exponential graph to explain its efficiency across any n and leverage them to develop new dynamic graphs. We propose two new dynamic graphs: the k-peer exponential graph and the null?cascade graph. Notably, the null-cascade graph achieves finite-time convergence for any n while ensuring commutativity. Our experiments confirm the effectiveness of these new graphs, particularly the null-cascade graph, in most test settings. https://github.com/garden1984/NullCascadeGraph