Examples

In order to speed up even further the process of designing a GNN, we provide a number of examples implemented by IGNNITION. We first include a simple example which, despite not being a real-life example, we believe can be very helpful as a beginners guide to implement a very simple GNN, this being a GNN solving the Shortest path problem.

Additionally, we provide implementations of several reference papers that include different typologies of GNN. Our hope is that, given this implementations, most of the custom GNN can be produced just by making some minor changes, which should help avoid any potential designing issue. Also, in each of the respective directories of the use-cases presented, we also provide a file containing a single sample of the dataset to help the user better understand the required structure of the dataset.

Below you can find the list of examples implemented so far by IGNNITION. Stay tuned as we plan to include many more examples soon:

1. Shortest-Path

Brief description

The first illustrative example that we present is a GNN that aims to solve the well-known Shortest-Path problem, which architecture is considerably simpler than any of the other proposals that we present below -and thus is a good starting point-. To learn more about this model, check Quick step-by-step tutorial where we explain in depth the target problem, as well as the architecture of the resulting GNN.


2. Graph Query Neural Networks

Brief description

This model addresses a different problem: supervised learning of traditional routing protocols with GNN, such as shortest path or max-min routing. To this end, the authors, in the paper Learning and generating distributed routing protocols using graph-based deep learning, propose a new GNN architecture that contains two entity types: routers and interfaces, being the latter the several network interfaces of each router in the network. Thus, this model considers a two-stage message-passing scheme with the following structure:

Stage1: routers, interfaces -> interfaces

Stage2: interfaces -> routers

As output, the model determines the interfaces that will be used to transmit traffic, which eventually generates the routing configuration of the network. Another particularity of this model is in the readout definition, where it uses a pipeline with an element-wise multiplication and then a final prediction.

Contextualization

Automated network control and management have been a long-standing target of network protocols. We address in this paper the question of automated protocol design, where distributed networked nodes have to cooperate to achieve a common goal without a priori knowledge on which information to exchange or the network topology. While reinforcement learning has often been proposed for this task, we propose here to apply recent methods from semisupervised deep neural networks which are focused on graphs. Our main contribution is an approach for applying graph-based deep learning on distributed routing protocols via a novel neural network architecture named Graph-Query Neural Network. We apply our approach to the tasks of shortest path and max-min routing. We evaluate the learned protocols in cold-start and also in case of topology changes. Numerical results show that our approach is able to automatically develop efficient routing protocols for those two use-cases with accuracies larger than 95 %. We also show that specific properties of network protocols, such as resilience to packet loss, can be explicitly included in the learned protocol.

MSMP Graph

Below we provide a visualization of the corresponding MSMP graph. In this representation we can observe the two different entities, this being the interfaces (INTER) and the routers (ROUTER). Then, as mentioned before, these exchange messages in two different stages.

Try Graph Query Neural Network

To execute this example, please download the source files at Graph Query Neural Network. In this directory, you will find all the necessary material regarding Graph Query Neural Network, including a minimal dataset along with all the files composing the implementation of this GNN model –model description and training option files. Moreover, we recommend reading the provided README file in this directory, which will guide you through this process.


3. RouteNet

Brief description:

This GNN model was proposed in the paper Unveiling the potential of Graph Neural Networks for network modeling and optimization in SDN. This proposal approaches the problem of modeling optical networks for the prediction of their performance metrics. For this, it introduces the link and the path entities, which are used for the message passing divided into two different stages:

Stage 1: links -> paths

Stage 2: paths -> links

Contextualization

Network modeling is a key enabler to achieve efficient network operation in future self-driving Software-Defined Networks. However, we still lack functional network models able to produce accurate predictions of Key Performance Indicators (KPI) such as delay, jitter, or loss at limited cost. In this paper, we propose RouteNet, a novel network model-based on Graph Neural Network (GNN) that is able to understand the complex relationship between topology, routing, and input traffic to produce accurate estimates of the per-source/destination per-packet delay distribution and loss. RouteNet leverages the ability of GNNs to learn and model graph-structured information and as a result, our model is able to generalize over arbitrary topologies, routing schemes and traffic intensity. In our evaluation, we show that RouteNet is able to predict accurately the delay distribution (mean delay and jitter) and the loss even in topologies, routing, and traffic unseen in the training (worst case MRE=15.4%). Also, we present several use cases where we leverage the KPI predictions of our GNN model to achieve efficiently routing optimization and network planning.

MSMP Graph

Below we provide a visualization of the corresponding MSMP graph for this use case. In this representation we can observe the two different entities, these being the links and the paths. Then we can observe the message passing that they perform into two separate stages.


4. Q-size

Brief Description

This model proposed in Towards more realistic network models based on Graph Neural Networks aims at estimating the src-dst performance of a network (i.e delay, jitter). This case presents a more complex GNN architecture that contains three entity types (links, paths, and nodes). In this case, the message passing is divided into two stages with the following structure:

Stage 1: paths -> nodes, and paths -> links

Stage 2: nodes and links -> paths

The first stage runs two message passings separately, while in the the second stage combines the hidden states of nodes and links and aggregates them using a Recurrent NN.

Contextualization

Recently, a Graph Neural Network (GNN) model called RouteNet was proposed as an efficient method to estimate end-to-end network performance metrics such as delay or jitter, given the topology, routing, and traffic of the network. Despite its success in making accurate estimations and generalizing to unseen topologies, the model makes some simplifying assumptions about the network, and does not consider all the particularities of how real networks operate. In this work we extend the architecture of RouteNet to support different features on forwarding devices, specifically we focus on devices with variable queue sizes, and we experimentally evaluate the accuracy of the extended RouteNet architecture.

MSMP Graph

Below we provide a visualization of the corresponding MSMP graph for this use case. In this representation we can observe the three different entities, these being the links, the paths, and the nodes. Then we can observe the message passing that they perform into two separate stages.


5. QM9

Brief description

The QM9 dataset contains information about 134k organic molecules containing Hydrogen (H), Carbon (C), Nitrogen (N), and Fluorine (F). For each molecule, computational quantum mechanical modeling was used to find each atom’s “positions” as well as a wide range of interesting and fundamental chemical properties, such as dipole moment, isotropic polarizability, enthalpy at 25ºC, etc.

The model presented in this example follows the GNN architecture used in Gilmer & Schoenholz (2017), which uses a single atom entity and consists of:

  • Feed-forward neural network to build atom to atom messages (single-step message passing) using the hidden states along with edge information (atom to atom distance and bond type).

  • Gated Recurrent Unit (GRU) to update atom’s hidden states.

  • Gated feed-forward neural network as readout to compute target properties.

Contextualization

Computational chemists have developed approximations to quantum mechanics, such as Density Functional Theory (DFT) with a variety of functionals Becke (1993) and Hohenberg & Kohn (1964) to compute molecular properties. Despite being widely used, DFT is simultaneously still too slow to be applied to large systems and exhibits systematic as well as random errors relative to exact solutions to Schrödinger’s equation.

Two more recent approaches by Behler & Parrinello (2007) and Rupp et al. (2012) attempt to approximate solutions to quantum mechanics directly without appealing to DFT by using statistical learning models. In the first case, single-hidden-layer neural networks were used to approximate the energy and forces for configurations of a Silicon melt to speed up molecular dynamics simulations. The second paper used Kernel Ridge Regression (KRR) to infer atomization energies over a wide range of molecules.

This approach attempts to generalize to different molecular properties of the wider array of molecules in the QM9 dataset.


6. Radio Resource Allocation

Brief description

Radio resource management, such as power control -modifying the power of the transmitters in a network-, conforms to a computationally challenging problem of great importance to the wireless networking community. Due to the characteristics of these networks, that is high scalability with low latency and high variance of their properties i.e. mobile networks, the need arises for fast and effective algorithms to optimize resource management. Traditional algorithms such as weighted minimum mean square error (WMMSE) as well as modern approaches which rely on convex optimization fall short and do not scale with different networks sizes.

In this example, we present an application of GNNs to solve the power control problem in wireless networks, as presented in Shen, Y., Shi, Y., Zhang, J., & Letaief, K. B. (2020). We generate a synthetic dataset of transmitter-receiver pairs which interfere with each other with some channel loss coefficients, computed as specified in Shi, Y., Zhang, J., & Letaief, K. B. (2015), and with additive Gaussian noise.

The model presented in this example follows the GNN architecture used in Shen, Y., Shi, Y., Zhang, J., & Letaief, K. B. (2020), which consists of:

  • Feed-forward neural network to build pair-to-pair messages using the hidden states along with edge information (pair to pair channel losses) and aggregating messages using element-wise maximum.

  • Feed-forward neural network to update pairs’ hidden states.

  • Pass-through layer which does not modify each pair’s hidden stats.