异构网络环境下最大化谱间距的拓扑设计  

Topological Design for Maximizing Spectral Gap in Heterogeneous Network Environment

作　　者：缪一航 徐跃东 吴俊 MIAO Yi-Hang;XU Yue-Dong;WU Jun(School of Computer Science,Fudan University,Shanghai 201203,China;School of Information Science and Engineering,Fudan University,Shanghai 201203,China)

机构地区：[1]复旦大学计算机科学技术学院,上海201203 [2]复旦大学信息科学与工程学院,上海201203

出　　处：《计算机系统应用》2023年第9期248-256,共9页Computer Systems & Applications

基　　金：国家重点研发计划(2020YFA0711400);国家自然科学基金(61831018,U21A20452)。

摘　　要：分布式平均共识和去中心化机器学习是具有广泛应用的去中心化计算方法.两种方法的收敛率主要由拓扑的谱间距所决定.节点网络环境的异构性包括节点带宽和节点间连接可用性的不同.异构网络环境对去中心化计算的效率提出了挑战.本文研究异构网络环境下最大化谱间距的拓扑设计问题,推导了谱间距针对拓扑任一条边的梯度,并设计了基于该梯度的增删边算法来构建目标拓扑.构建的拓扑具有更大谱间距,且各节点的数据通信时间相近.拓扑构建算法的性能在不同程度的异构网络环境下能够保持稳定,且生成的拓扑在分布式共识中以更快的收敛率和更短的时间达到收敛.基于该算法,本文进一步验证了最新发现的谱间距与去中心化机器学习收敛率的弱相关性.Distributed average consensus and decentralized machine learning are widely employed decentralized computing methods.The convergence rates of the two methods are mainly determined by the spectral gap of the topology.The heterogeneity of the network environment among nodes includes the difference in node bandwidth and inter-node connection availability.The heterogeneous network environment poses a challenge to decentralized computation efficiency.This work studies the topology design of maximizing the spectral gap under a heterogeneous network environment.The gradient of the spectral gap for any edge of the topology is derived and an edge-addition and deletion algorithm is designed based on this gradient to construct the target topology.The generated topology has larger spectral gaps and similar data communication time of each node.The performance of this algorithm remains stable under different levels of heterogeneous network environments.The generated topology achieves convergence with a faster convergence rate and shorter time in distributed consensus.Based on this algorithm,this paper further verifies the recently discovered weak relationship between the spectral gap and convergence rate of decentralized machine learning.

关 键 词：去中心化机器学习 分布式平均共识 拓扑设计 谱间距 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]