Software

Matlab Version

The GNN simulator was originally implemented in MATLAB. It is available for downloading in the original GNNs site, along with the benchmarks used in [SGT+09b], [SGT+09a] and more recently in [RTD+18], and a short manual.

TensorFlow Version

This Tensorflow package can be employed both in graph or node based prediction, and for any kind of graph (direct, undirect, cycle and a-cycle). With respect to the original MATLAB code, the Tensorflow implementation is much faster and able to exploit the power of GPU processing. In the following, we give a brief sketch of the implementation, completely based on matrix multiplications to allow parallelization and speed in the computations.

Matrix-based implementation

As described in Model, GNN computes two different functions, namely it iterates, until convergence, a state function \(f\) for all nodes in the graph, and then the obtained state \(x\) is used as input to an output function \(g\). Both \(f\) and \(g\) can be implemented by simple multilayer perceptrons (MLPs).

The state evaluation function of equation (1) allows us to deal with any number of neighbors. The computations follow the topology of the arcs in the input graphs.

Starting from a graph, we build the ordered edge list. If we have more than one graph we could enumerate the nodes in a way that nodes on different graphs have an empty id intersection.

This initial structure is exploited to compose the input for the state transition function \(f\), collecting:

  • the father and child node labels

  • the edge labels

  • the child node state at time \((t-1)\)

With this input, \(f\) produces the contribution to the state at time \(t\), for each edge.

../_images/state_f.svg

In order to aggregate the state per node, a matrix multiplication is performed with an edge–node matrix that encodes the neighborhood for each node. This matrix (referred to as ArcNode matrix) is sparse, to save memory.

../_images/arcnode.svg

So doing we obtain the per-node aggregated state representation.

../_images/multi.svg

This procedure is repeated until the convergence of the state.

Node–Based Output function

In case of a node–based task, the state of each node is directly given as input to the output function \(g\).

Graph–Based Output function

In case of graph–based problem, various approaches can be followed. For instance, a supernode can be selected, the state of which is representative for the entire structure. Another solution is to sum up the states of all the nodes. Hence, when processing more than one graph,it is possible to optimize the state aggregation using a matrix multiplication between the state matrix and a matrix representing the node-graph inclusion, or which node is the supernode of the graph.

Afterwards we can evaluate the output function \(g\) as summarized in the following scheme:

../_images/complete.svg