Browse the docs · Apsi 2.4.4

Graphs that reach far

Graph neural networks pass messages along edges: one layer moves information one hop. Two problems follow, and both are measurable:

Values do not travel far. In a post-norm network that also counts each node as its own neighbour, every layer dilutes what arrived from the neighbours; in practice values make it about three hops, however many layers there are.
Everything is squeezed into one vector. A node that has heard from eight leaves holds one summary of them and cannot say which leaf carried which value. A mean over the whole graph has the same problem.

use layers has the tools large graph models use against both:

Tool	What it does	Reach
`graph_transformer(d, heads, relations)`	pre-norm residual block: attention over the neighbours only, separate key/value weights per relation, a learned bias per relation and per hop distance, then an MLP	one hop per layer, kept over many layers
`global_attention(d, heads, max_keys=4096)`	every node attends to every node of its own graph by content; graphs of a batch never see each other; above `max_keys` nodes the keys are an evenly strided subset	any distance in one layer
`k_hop(g, k)`	adds a shortcut edge to everything within `k` hops (`edge.hop` = distance)	k hops per layer
`mix_hop(n_in, n_out, hops=[0, 1, 2])`	several distances in parallel in one layer: `[x, Âx, Â²x, …]`, each with its own weights	parallel hops
`graph_memory(d, k)`	the `k` most salient node states of every graph, weighted by a learned score: `[graphs, k, d]` for a decoder to attend into	the whole graph, node by node
`graph_transformer_net(n_in, d, out, layers, heads, relations, global_every, task)`	a complete model: input projection, local blocks with a global block every `global_every` layers, final norm, node or graph output	all of the above
`hop_distances(g, node)`, `eccentricity(g)`	breadth-first hop counts; the longest shortest path	measuring how far information must go

Relations and both directions

let g = graph(edges=edges, n=n, types=kinds, reverse=true, batch=graph_of_node)

types gives every edge a relation (0, 1, …), for example syntax, data flow and calls in a program graph. reverse=true adds every edge backwards as a relation of its own, so information flows both ways with separate weights (from a use back to its definition, from a callee back to its caller). graph_transformer(…, relations= g.relations) learns one key and value projection per relation.

A task that needs reach

Node 0 of each chain must report a class written at the other end, five hops away (the full program is examples/42_long_range_graphs.apsi):

let model = graph_transformer_net(4, 16, 2, layers=1, heads=2, relations=2, global_every=1)
let r = fit(model, model.init(seed=0), X, y, loss="cross_entropy", opt=adam(lr=0.01), epochs=150,
            graph=g, mask=mask, verbose=false)

Measured by the test suite (tests/test_graphs.py):

Model	Accuracy at node 0
1 `graph_transformer` + 1 `global_attention`	100 % (one global step reaches the far end)
6 `graph_transformer` blocks, no global attention	100 % (values survive six layers)
2 `graph_transformer` blocks	at chance (the far end is out of reach)

Cost

graph_transformer: proportional to the number of edges, like gat.
global_attention: nodes × keys per graph (keys = nodes up to max_keys, then max_keys). For large graphs put a global block after every second local block, as global_every=2 does.
k_hop: the number of edges grows with the k-hop neighbourhood; use it for sparse graphs and small k.
All of these train with fit(…) and Apsi's own autodiff; fit(…, workers=N) spreads mini-batches over cores.

Found a mistake? Report it · Markdown source