Artificial intelligence has undergone a renaissance recently, making major progress in key domains such as vision, language, control, and decision-making. This has been due, in part, to cheap data and cheap compute resources, which have fit the natural strengths of deep learning. However, many defining characteristics of human intelligence, which developed under much different pressures, remain out of reach for current approaches. In particular, generalizing beyond one’s experiences–a hallmark of human intelligence from infancy–remains a formidable challenge for modern AI.
A combinatorial generalization must be a priority for AI to achieve human-like abilities, structured representations and computations are key to realizing this objective. Just as biology uses nature and nurture cooperatively, we reject the false choice between “hand-engineering” and “end-to-end” learning, and instead advocate for an approach which benefits from their complementary strengths. Graph nets explore how using relational inductive biases within deep learning architectures can facilitate learning about entities, relations, and rules for composing them. Graph nets is an AI toolkit with a strong relational inductive bias–the graph network–which generalizes and extends various approaches for neural networks that operate on graphs, and provides a straightforward interface for manipulating structured knowledge and producing structured behaviors. Networks can support relational reasoning and combinatorial generalization, laying the foundation for more sophisticated, interpretable, and flexible patterns of reasoning.

First, install the package:

and import it

Graphs have to be generated and much like a tabular learning pipeline you need some utilities to streamline it all:

With this one can output some nice graphs:

The model we explore includes three components:
– An “Encoder” graph net, which independently encodes the edge, node, and
global attributes (does not compute relations etc.).
– A “Core” graph net, which performs N rounds of processing (message-passing)
steps. The input to the Core is the concatenation of the Encoder’s output
and the previous output of the Core (labeled “Hidden(t)” below, where “t” is
the processing step).
– A “Decoder” graph net, which independently decodes the edge, node, and
global attributes (does not compute relations etc.), on each
message-passing step.

The model is trained by supervised learning. Input graphs are procedurally
generated, and output graphs have the same structure with the nodes and edges
of the shortest path labeled (using 2-element 1-hot vectors). We could have
predicted the shortest path only by labeling either the nodes or edges, and
that does work, but we decided to predict both to demonstrate the flexibility
of graph nets’ outputs.

The training loss is computed on the output of each processing step. The
reason for this is to encourage the model to try to solve the problem in as
few steps as possible. It also helps make the output of intermediate steps
more interpretable.

There’s no need for a separate evaluate dataset because the inputs are
never repeated, so the training loss is the measure of performance on graphs
from the input distribution.

We also evaluate how well the models generalize to graphs which are up to
twice as large as those on which it was trained. The loss is computed only
on the final processing step.

Variables with the suffix _tr are training parameters, and variables with the
suffix _ge are test/generalization parameters.

After around 2000-5000 training iterations the model reaches near-perfect
performance on graphs with between 8-16 nodes.

This cell resets the Tensorflow session, but keeps the same computational graph.

You can interrupt this cell’s training loop at any time, and visualize the intermediate results by running the next cell (below). You can then resume training by simply executing this cell again.

# (iteration number), T (elapsed seconds), Ltr (training loss), Lge (test/generalization loss), Ctr (training fraction nodes/edges labeled correctly), Str (training fraction examples solved correctly), Cge (test/generalization fraction nodes/edges labeled correctly), Sge (test/generalization fraction examples solved correctly)
# 00038, T 22.9, Ltr 1.0097, Lge 0.6905, Ctr 0.8351, Str 0.0000, Cge 0.9474, Sge 0.0000
# 00096, T 41.9, Ltr 0.8867, Lge 0.7074, Ctr 0.8678, Str 0.0000, Cge 0.9474, Sge 0.0000
# 00160, T 61.9, Ltr 0.8190, Lge 0.5330, Ctr 0.8773, Str 0.0000, Cge 0.9592, Sge 0.0000
# 00223, T 81.9, Ltr 0.7457, Lge 0.4636, Ctr 0.8772, Str 0.0000, Cge 0.9629, Sge 0.0000
# 00285, T 102.2, Ltr 0.5869, Lge 0.4440, Ctr 0.9047, Str 0.0000, Cge 0.9609, Sge 0.0000
# 00345, T 122.4, Ltr 0.6421, Lge 0.4271, Ctr 0.8927, Str 0.0312, Cge 0.9572, Sge 0.0100
# 00408, T 142.4, Ltr 0.4840, Lge 0.4120, Ctr 0.9219, Str 0.0312, Cge 0.9602, Sge 0.0200
# 00471, T 162.7, Ltr 0.5184, Lge 0.3747, Ctr 0.9159, Str 0.1562, Cge 0.9638, Sge 0.0500
# 00536, T 182.9, Ltr 0.4626, Lge 0.3830, Ctr 0.9277, Str 0.1250, Cge 0.9609, Sge 0.0300
# 00599, T 203.0, Ltr 0.5819, Lge 0.3564, Ctr 0.9119, Str 0.2188, Cge 0.9645, Sge 0.1300
# 00662, T 223.3, Ltr 0.4533, Lge 0.3038, Ctr 0.9166, Str 0.1875, Cge 0.9701, Sge 0.1800

# 09884, T 3184.2, Ltr 0.1494, Lge 0.0328, Ctr 0.9943, Str 0.9375, Cge 0.9956, Sge 0.7800
# 09948, T 3204.5, Ltr 0.1576, Lge 0.0778, Ctr 0.9903, Str 0.8750, Cge 0.9892, Sge 0.6600

This cell visualizes the results of training. You can visualize the intermediate results by interrupting execution of the cell above, and running this cell. You can then resume training by simply executing the above cell again.