Multi-Level Local SGD for Heterogeneous Hierarchical Networks

• URL: http://arxiv.org/abs/2007.13819v3
• Date: Fri, 18 Feb 2022 18:43:42 GMT
• Title: Multi-Level Local SGD for Heterogeneous Hierarchical Networks
• Authors: Timothy Castiglia, Anirban Das, and Stacy Patterson
• Abstract summary: We propose Multi-Level Local SGD, a distributed gradient method for a learning, non- objective framework in a heterogeneous network. We first provide a unified mathematical that describes the Multi-Level Local SGD algorithm. We then present a theoretical analysis of the algorithm.
• Score: 11.699472346137739
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose Multi-Level Local SGD, a distributed gradient method for learning a smooth, non-convex objective in a heterogeneous multi-level network. Our network model consists of a set of disjoint sub-networks, with a single hub and multiple worker nodes; further, worker nodes may have different operating rates. The hubs exchange information with one another via a connected, but not necessarily complete communication network. In our algorithm, sub-networks execute a distributed SGD algorithm, using a hub-and-spoke paradigm, and the hubs periodically average their models with neighboring hubs. We first provide a unified mathematical framework that describes the Multi-Level Local SGD algorithm. We then present a theoretical analysis of the algorithm; our analysis shows the dependence of the convergence error on the worker node heterogeneity, hub network topology, and the number of local, sub-network, and global iterations. We back up our theoretical results via simulation-based experiments using both convex and non-convex objectives.

Related papers

• Nested stochastic block model for simultaneously clustering networks and nodes [9.860884833526407]
  We introduce the nested block model (NSBM) to cluster a collection of networks while simultaneously detecting communities within each network. NSBM has several appealing features including the ability to work on unlabeled networks with potentially different node sets.
  arXiv  Detail & Related papers  (2023-07-18T12:46:34Z)
• Network-GIANT: Fully distributed Newton-type optimization via harmonic Hessian consensus [2.8617826964327113]
  We introduce a Newton-type fully distributed optimization algorithm, Network-GIANT, based on GIANT. We prove that our algorithm guarantees semi-global and exponential convergence to the exact solution over the network assuming strongly convex and smooth loss functions. We provide empirical evidence of the superior convergence performance of Network-GIANT over other state-of-art distributed learning algorithms such as Network-DANE and Newton-Raphson Consensus.
  arXiv  Detail & Related papers  (2023-05-13T11:42:40Z)
• LSGNN: Towards General Graph Neural Network in Node Classification by Local Similarity [59.41119013018377]
  We propose to use the local similarity (LocalSim) to learn node-level weighted fusion, which can also serve as a plug-and-play module. For better fusion, we propose a novel and efficient Initial Residual Difference Connection (IRDC) to extract more informative multi-hop information. Our proposed method, namely Local Similarity Graph Neural Network (LSGNN), can offer comparable or superior state-of-the-art performance on both homophilic and heterophilic graphs.
  arXiv  Detail & Related papers  (2023-05-07T09:06:11Z)
• Multiplex Heterogeneous Graph Convolutional Network [25.494590588212542]
  This work proposes a Multiplex Heterogeneous Graph Convolutional Network (MHGCN) for heterogeneous network embedding. Our MHGCN can automatically learn the useful heterogeneous meta-path interactions of different lengths in multiplex heterogeneous networks.
  arXiv  Detail & Related papers  (2022-08-12T06:17:54Z)
• On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
  We show that gradient flow converges in direction when labels are determined by the sign of a target network with $r$ neurons. Our result may already hold for mild over- parameterization, where the width is $tildemathcalO(r)$ and independent of the sample size.
  arXiv  Detail & Related papers  (2022-05-18T16:57:10Z)
• Pay Attention to Relations: Multi-embeddings for Attributed Multiplex Networks [0.0]
  RAHMeN is a novel unified relation-aware embedding framework for attributed heterogeneous multiplex networks. Our model incorporates node attributes, motif-based features, relation-based GCN approaches, and relational self-attention to learn embeddings of nodes. We evaluate our model on four real-world datasets from Amazon, Twitter, YouTube, and Tissue PPIs in both transductive and inductive settings.
  arXiv  Detail & Related papers  (2022-03-03T18:31:29Z)
• DeHIN: A Decentralized Framework for Embedding Large-scale Heterogeneous Information Networks [64.62314068155997]
  We present textitDecentralized Embedding Framework for Heterogeneous Information Network (DeHIN) in this paper. DeHIN presents a context preserving partition mechanism that innovatively formulates a large HIN as a hypergraph. Our framework then adopts a decentralized strategy to efficiently partition HINs by adopting a tree-like pipeline.
  arXiv  Detail & Related papers  (2022-01-08T04:08:36Z)
• Global and Individualized Community Detection in Inhomogeneous Multilayer Networks [14.191073951237772]
  In network applications, it has become increasingly common to obtain datasets in the form of multiple networks observed on the same set of subjects. Such datasets can be modeled by multilayer networks where each layer is a separate network itself while different layers are associated and share some common information. The present paper studies community detection in a stylized yet informative inhomogeneous multilayer network model.
  arXiv  Detail & Related papers  (2020-12-02T02:42:52Z)
• Multi-Stage Hybrid Federated Learning over Large-Scale D2D-Enabled Fog Networks [61.30171206892684]
  We develop a hybrid of intra- and inter-layer model learning that considers the network as a multi-layer cluster-based structure. MH-FL considers the topology structures among the nodes in the clusters, including local networks formed via device-to-device (D2D) communications. It orchestrates the devices at different network layers in a collaborative/cooperative manner to form local consensus on the model parameters.
  arXiv  Detail & Related papers  (2020-07-18T20:03:07Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  We study a distributed variable for large-scale AUC for a neural network as with a deep neural network. Our model requires a much less number of communication rounds and still a number of communication rounds in theory. Our experiments on several datasets show the effectiveness of our theory and also confirm our theory.
  arXiv  Detail & Related papers  (2020-05-05T18:08:23Z)
• Detecting Communities in Heterogeneous Multi-Relational Networks:A Message Passing based Approach [89.19237792558687]
  Community is a common characteristic of networks including social networks, biological networks, computer and information networks. We propose an efficient message passing based algorithm to simultaneously detect communities for all homogeneous networks.
  arXiv  Detail & Related papers  (2020-04-06T17:36:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.