The world’s leading publication for data science, AI, and ML professionals.

Graph Neural Networks: a learning journey since 2008 – Part 2

The second story about Scarselli's Graph Neural Networks. Today, let's implement what we've learned: GNN in Python!

Picture by Brady Bellini on Unsplash
Picture by Brady Bellini on Unsplash

Join Medium with my referral link – Stefano Bosisio

We learned in the first part of this series the theoretical background of Scarselli’s Graph Neural Networks. In particular, we learned:

  • GNN is suitable both for node-based and graph-based predictions. In the former case, we want predictions for each node in a graph, in the latter predictions for an entire graph
  • Each node can be represented by a transition function _f𝓌 a_nd an output function g𝓌.
  • To converge to a solution, both transition and output function has to satisfy Banach’s fixed-point solution
  • Multi-layer perceptrons (MLP) do satisfy Banach’s requirements, thus _f𝓌 a_nd g_𝓌 ca_n be implemented as simple neural network layers

Keeping these points in mind, let’s see step by step how we can implement this framework in Python and apply it to a simple problem, called "Karate Club".

The Karate Club

As an example, we take Zachary’s karate club problem. This problem is traced back to Zachary’s paper "An information flow model for Conflict and Fission in Small Groups" [29], where a karate club network was studied for three years (1970–1972). The network comprises 34 members, including the karate club administrator "John A" and the instructor "Mr Hi", along with the links between pairs of members who interacted outside the club (they gathered for a beer, for a walk…). After an argument between the administrator and the instructor, the club split into two halves, thus two new groups were created. Zachary’s correctly predicted how the members re-arranged their social network/each member’s decision with the Ford-Fulkerson algorithm. This problem has brought attention to the graph-lovers community and it is widely used to test GraphNN. Scarselli’s 2009 paper applies the Graph Neural Network to correctly predict karate club member’s decisions after the split.

Github repo and installs

The main scripts are stored in this repo:

learn_graph_ml/Scarselli_GNN at master · Steboss/learn_graph_ml

Before proceeding I recommend you to create a virtual environment in a working directory (just type in your terminal python -m venv venv and a venv folder will be created). Then you can install these packages:

  • dgl is Deep Graph Library, a library specialized in graph calculations. We’ll be using this to visualize our graph during the training steps. To install dgl insert your hardware information in this page: https://www.dgl.ai/pages/start.html (for example None CUDA, Pip(stable) Package, Mac Os and Python 3.8 version, thus I can install dgl with the following command pip install dgl -f https://data.dgl.ai/wheels/repo.html). If you are experiencing problems with pip just upgrade with pip install --upgrade pip and everything should work fine.
  • pip install torch
  • pip install tensorflow
  • pip install matplotlib
  • pip install seaborn

Intro to scripts and graph

As you can see in the Github repo there are several scripts. Here is a wee description for each of them:

  • create_and_visualize.py allows to create the initial graph and draw the graph during training
  • prepare_edge_nodes_mat.py provides the edges, labels and nodes’ features. Two matrices are created: Eedges matrix and graph id, N nodes’ feature matrix and graph id
  • prepare_GNN.py transforms E and N matrix as input for the Graph Neural Network. The output is an inp matrix, which has the form [source_node, destination_node, features of the source node, features of the destination node] and arcnode matrix, a sparse matrix with the edges connection between nodes e.g. [source_node, destination_node, 1 at source index position 0 otherwise]
  • input_and_output_funcitons.py defines the f𝓌 and g_𝓌 ne_ural networks, along with validation metrics and loss
  • GNN.py main Graph Neural Network class, where the training conditions are defined, along with check of convergence. The final outputs are the training loss, nodes predictions, nodes’ positions during training and number of iteration to convergence.
  • karate.py is the main script, where the karate dataset is created and the GNN is trained.

As a first step, we can run create_and_visualize.pyto visualize the karate club graph. You can run this script in a ipyhtonshell:

The graph is created thorugh dgl.DGLGraph() within build_karate_club_graph() function. visualize_karate_club() produces the output by converting the input graph to_networkx() (fig.2)

Fig.2: the karate club as a graph. The club is composed of 34 individuals, which, after splitting, decide to group into two groups, based on their features.
Fig.2: the karate club as a graph. The club is composed of 34 individuals, which, after splitting, decide to group into two groups, based on their features.

A graphical explanation

Fig. 3 shows a graphical investigation of the computational steps. From the initial graphs two matrices are created: the nodes’ features N matrix and the edges matrix E. These two matrices are then transformed to be an input for Graph Neural Networks. In particular, matrix E and features from matrix N are used as input for the transition function f𝓌. The output from this neural network is multiply with arcnode one-hot encoding matrix to update nodes’ states. The final output is used as an input for function g_𝓌 t_o produce the final predictions

Fig.3: Graphical representation of the computational approach. The input graph is subdivided in a matrix N and E. From there the input matrices for the GraphNN are created. Matrix inp is a combination of edges matrix and features, while arcnode defines the edges connections as a one-hot encoded matrix. Then, inp matrix is used as input for the NN fw. Nodes' states are updated by matmul with arcnode matrix. The final output is produced through the output function gw
Fig.3: Graphical representation of the computational approach. The input graph is subdivided in a matrix N and E. From there the input matrices for the GraphNN are created. Matrix inp is a combination of edges matrix and features, while arcnode defines the edges connections as a one-hot encoded matrix. Then, inp matrix is used as input for the NN fw. Nodes’ states are updated by matmul with arcnode matrix. The final output is produced through the output function gw

1. Input preprocessing: edges, labels and features

learn_graph_ml/prepare_edge_nodes_mat.py at master · Steboss/learn_graph_ml

prepare_edge_nodes_mat.py allows the creation of two matrices: the edges’ matrix E and the nodes’ features matrix N .

To create edges, I provided an input file in data/edges.txt :

Edges’ matrix E is created from edges input plus a final column which defines the graph_id The graph_id in this case is 0, as we want node-focused predictions. If you were performing graph-based predictions you would add a graph_id .

The final content of matrix E is [source_node, destination_node, graph_id]:

Nodes’ features are created as a one-hot encoded matrix with sp.eye(np.max(edges+1), dtype=np.float32).tocsr():

  • sp.eye is scipy.sparse matrix,
  • np.max(edges+1) defines the index where we want to have the value of 1,
  • tocsr() is compressed sparse row format

Features are concatenated with graph_id to create the final nodes’ features matrix N , whose content thus is [ node's features, graph_id] and dimensions are [number_of_nodes, number_of_nodes+1] :

In this case, labels (0 or 1) are assigned as:

Finally, the script randomly picks 4 nodes to be used as labelled nodes for a supervised training.

2. From matrices to GNN inputs

learn_graph_ml/prepare_GNN.py at master · Steboss/learn_graph_ml

prepare_GNN.py helps in creating the inputs for a neural network from Eand Nmatrices.

The first output is inp matrix. Lines 22–36 shows how to create the input matrix, which is a concatenation between edges matrix Eand nodes’ features N. The final content is[source_node, destination_node, source_features, destination_features]. As an example, for the first edge, between node 0 and 1, inp content is:

The second output is arcnode , which encodes the edges information in SparseMatrix format, whose dimensions are [number_of_nodes, number_of_edges] ( in this case 34×78). The sparse format allow to save memory and identify only the pair of row-column indices with value of 1, otherwise 0.

3. Define the input and output function

learn_graph_ml/input_and_output_functions.py at master · Steboss/learn_graph_ml

input_and_output_functions.py defines the underlying transition and output functions as MLP. The core function for class Net are netSt and netOut which creates the NN for f𝓌 and g_𝓌 re_spectively, which defines a 2 layers Neural Networks. netSt receives nodes’ features, whose dimension is 70 and re-map those features with 3 hidden nodes, with a tanh activation function. netOut has a similar architecture, it receives a 2-dimensional input, which is re-mapped through 3 nodes and return the final prediction output after softmax application:

4. Almost ready to go: main GNN

learn_graph_ml/GNN.py at master · Steboss/learn_graph_ml

The last step is GNN.py where we are going to define how the neural network architecture should work. The functions convergence , condition and Loop are the core parts of the entire architecture, where the nodes’ states are updated

The training session starts at line 293 and Loop function is encapsulated in self.loss_op . In Loop tf.while_loop , line 221, is called to run condition and convergence . This last function update the current nodes’ state:

In fig.10 a[:,1] is the input matrix inp[:,1] , namely all the destination_nodeindices. tf.gather return all the old_state values for each destination node, resulting in a 78×2 matrix, whose values are zeros at first iteration – since old_state at first is initiated as a matrix of zeros, np.zeros((ArcNode.dense_shape[0], self.state_dim)) ([line 261](http://self.state: np.zeros((ArcNode.dense_shape[0], self.state_dim)),)).

sl = a[:, 2:] returns all the source_node and destination_node features (dimensions 78×68), which is then concatenated as inp for the transition neural network function. The output state from f𝓌 is updated with the edges connection through a matrix multiplication sparse_tensor_dense_matmul . The new state is passed back to Loop function (line 237) and it is then used as input for g_𝓌 o_utput function:out=self.net.netOut(stf)

Karate club in action

You are now ready to run karate.py !!!

learn_graph_ml/karate.py at master · Steboss/learn_graph_ml

The final output has little meaning, but it is a remarkable example to see the power of graph neural networks and how graphs can be used as inputs for our predictions.

The main part of karate.py script is at line 61, where the training step is performed. It is up to you if you want to save the final results as a gifand if you want to visualize the neural network results in tensorboard – here the command to open tensorboard with final output:

venv/bin/tensorboard --logdir tmp/path/to/folder_with_out.tfevents

Connect your browser to http://localhost:PORT where port is defined as output in the terminal, to have the full working tensorboard

The main output form g.Train is loop_val . This variable reports:

  • loop_val[0] nodes’ prediction values
  • loop_val[1] number of iterations performed to update the states
  • loop_val[2] current nodes’ positions
  • loop_val[3] nodes’ features

Fig. 11 animates the training run, from the initial guess where there are no predictions for nodes, till the end, where there is a linear separation between nodes.

Fig. 11: Nodes subdivision through epochs, based on predictions from GraphNN
Fig. 11: Nodes subdivision through epochs, based on predictions from GraphNN

That’s all for today! Stay tuned for a new post on Graphs and ML very soon!!!!


Please, feel free to send me an email for questions or comments at: [email protected] or directly here in Medium.


Related Articles