Distributed Scheduling using Graph Neural Networks

• URL: http://arxiv.org/abs/2011.09430v2
• Date: Sat, 6 Feb 2021 18:56:11 GMT
• Title: Distributed Scheduling using Graph Neural Networks
• Authors: Zhongyuan Zhao, Gunjan Verma, Chirag Rao, Ananthram Swami, and Santiago Segarra
• Abstract summary: A fundamental problem in the design of wireless networks is to efficiently schedule transmission in a distributed manner. We propose a distributed MWIS solver based on graph convolutional networks (GCNs) In a nutshell, a trainable GCN module learns topology-aware node embeddings that are combined with the network weights before calling a greedy solver.
• Score: 38.74504118887024
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A fundamental problem in the design of wireless networks is to efficiently schedule transmission in a distributed manner. The main challenge stems from the fact that optimal link scheduling involves solving a maximum weighted independent set (MWIS) problem, which is NP-hard. For practical link scheduling schemes, distributed greedy approaches are commonly used to approximate the solution of the MWIS problem. However, these greedy schemes mostly ignore important topological information of the wireless networks. To overcome this limitation, we propose a distributed MWIS solver based on graph convolutional networks (GCNs). In a nutshell, a trainable GCN module learns topology-aware node embeddings that are combined with the network weights before calling a greedy solver. In small- to middle-sized wireless networks with tens of links, even a shallow GCN-based MWIS scheduler can leverage the topological information of the graph to reduce in half the suboptimality gap of the distributed greedy solver with good generalizability across graphs and minimal increase in complexity.

Related papers

• Decentralized Optimization in Time-Varying Networks with Arbitrary Delays [22.40154714677385]
  We consider a decentralized optimization problem for networks affected by communication delays. Examples of such networks include collaborative machine learning, sensor networks, and multi-agent systems. To mimic communication delays, we add virtual non-computing nodes to the network, resulting in directed graphs.
  arXiv  Detail & Related papers  (2024-05-29T20:51:38Z)
• Network Interdiction Goes Neural [26.308933674471895]
  Network interdiction problems are optimization problems involving two players. One aims to solve an optimization problem on a network, while the other seeks to modify the network to thwart the first player's objectives.
  arXiv  Detail & Related papers  (2024-05-26T02:34:26Z)
• Learning State-Augmented Policies for Information Routing in Communication Networks [92.59624401684083]
  We develop a novel State Augmentation (SA) strategy to maximize the aggregate information at source nodes using graph neural network (GNN) architectures. We leverage an unsupervised learning procedure to convert the output of the GNN architecture to optimal information routing strategies. In the experiments, we perform the evaluation on real-time network topologies to validate our algorithms.
  arXiv  Detail & Related papers  (2023-09-30T04:34:25Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Learning Cooperative Beamforming with Edge-Update Empowered Graph Neural Networks [29.23937571816269]
  We propose an edge-graph-neural-network (Edge-GNN) to learn the cooperative beamforming on the graph edges. The proposed Edge-GNN achieves higher sum rate with much shorter computation time than state-of-the-art approaches.
  arXiv  Detail & Related papers  (2022-11-23T02:05:06Z)
• Distributed Link Sparsification for Scalable Scheduling Using Graph Neural Networks [37.84368235950714]
  We propose a distributed scheme for link sparsification with graph convolutional networks (GCNs) In medium-sized wireless networks, our proposed sparse scheduler beats threshold-based sparsification policies by retaining almost $70%$ of the total capacity achieved by a greedy scheduler.
  arXiv  Detail & Related papers  (2022-03-27T16:02:12Z)
• Link Scheduling using Graph Neural Networks [28.835515501826546]
  Efficient scheduling of transmissions is a key problem in wireless networks. We propose fast topological convolutional networks (GCNs) that can be implemented in centralized and distributed manners. Test results on medium-sized wireless networks show that a GCN-based centralized MWIS solver can reach a near-optimal solution quickly.
  arXiv  Detail & Related papers  (2021-09-12T15:19:59Z)
• Learning Autonomy in Management of Wireless Random Networks [102.02142856863563]
  This paper presents a machine learning strategy that tackles a distributed optimization task in a wireless network with an arbitrary number of randomly interconnected nodes. We develop a flexible deep neural network formalism termed distributed message-passing neural network (DMPNN) with forward and backward computations independent of the network topology.
  arXiv  Detail & Related papers  (2021-06-15T09:03:28Z)
• Resource Allocation via Graph Neural Networks in Free Space Optical Fronthaul Networks [119.81868223344173]
  This paper investigates the optimal resource allocation in free space optical (FSO) fronthaul networks. We consider the graph neural network (GNN) for the policy parameterization to exploit the FSO network structure. The primal-dual learning algorithm is developed to train the GNN in a model-free manner, where the knowledge of system models is not required.
  arXiv  Detail & Related papers  (2020-06-26T14:20:48Z)
• Graph Neural Networks for Motion Planning [108.51253840181677]
  We present two techniques, GNNs over dense fixed graphs for low-dimensional problems and sampling-based GNNs for high-dimensional problems. We examine the ability of a GNN to tackle planning problems such as identifying critical nodes or learning the sampling distribution in Rapidly-exploring Random Trees (RRT) Experiments with critical sampling, a pendulum and a six DoF robot arm show GNNs improve on traditional analytic methods as well as learning approaches using fully-connected or convolutional neural networks.
  arXiv  Detail & Related papers  (2020-06-11T08:19:06Z)

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.