
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 installdgl
insert your hardware information in this page: https://www.dgl.ai/pages/start.html (for exampleNone
CUDA,Pip(stable)
Package,Mac
Os andPython 3.8
version, thus I can installdgl
with the following commandpip install dgl -f https://data.dgl.ai/wheels/repo.html)
. If you are experiencing problems withpip
just upgrade withpip 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 trainingprepare_edge_nodes_mat.py
provides the edges, labels and nodes’ features. Two matrices are created:E
edges matrix and graph id,N
nodes’ feature matrix and graph idprepare_GNN.py
transformsE
andN
matrix as input for the Graph Neural Network. The output is aninp
matrix, which has the form[source_node, destination_node, features of the source node, features of the destination node]
andarcnode
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 lossGNN.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.py
to visualize the karate club graph. You can run this script in a ipyhton
shell:
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)

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

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
isscipy.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 E
and N
matrices.
The first output is inp
matrix. Lines 22–36 shows how to create the input matrix, which is a concatenation between edges matrix E
and 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 r
eceives nodes’ features, whose dimension is 70 and re-map those features with 3 hidden nodes, with a tanh a
ctivation function. netOut h
as a similar architecture, it receives a 2-dimensional input, which is re-mapped through 3 nodes and return the final prediction output after softmax a
pplication:
4. Almost ready to go: main GNN
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_node
indices. 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
!!!
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 gif
and 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 valuesloop_val[1]
number of iterations performed to update the statesloop_val[2]
current nodes’ positionsloop_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.

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.