State-Augmented Information Routing In Communication Systems With Graph Neural Networks

We consider the problem of routing network packets in a large-scale communication system where the nodes have access to only local information. We formulate this problem as a constrained learning problem, which can be solved using a distributed optimization algorithm. We approach this distributed optimization using a novel state-augmentation (SA) strategy to maximize the aggregate information packets at different source nodes, leveraging dual variables corresponding to flow constraint violations. The construction is based on graph neural networks (GNNs) that employ graph convolutions over the underlying communication network topology. We devise an unsupervised learning algorithm to transform the output of the GNN architecture into optimal routing decisions. The proposed method takes advantage of only the local information available at each node and efficiently routes the desired packets to the destination. We provide numerical results demonstrating the superiority of the proposed method over baseline routing algorithms.