What a graph layer costs

STATEMENT

Count the work and memory of one graph-convolution layer on a large sparse graph, with a dense adjacency matrix and with an edge list, and count how fast a node’s receptive field grows with depth.

GIVEN

$n=10^6$ nodes, $m=10^7$ undirected edges, width $d=128$, $32$-bit floats for the dense matrix and $64$-bit integers for the edge list. For sampling, $25$ neighbours per node in the first layer and $10$ in the second.

FIND

Multiply-accumulates for $\hat{\mat A}\mat H$ dense and sparse, and for $\mat H\mat W$; memory for the dense $\hat{\mat A}$ and for the edge list; the average degree; a bound on the nodes a three-layer prediction can depend on; the bound with sampling for two layers.

STRATEGY

Use (I.14.9). Each undirected edge is stored as two directed entries, each with two indices.

SOLUTION

Work. A dense product of an $n\times n$ matrix with an $n\times d$ matrix costs $n^2d=1.28\times10^{14}$ multiply-accumulates. With an edge list, each of the $2m$ directed entries adds one $d$-vector: $2md=2.56\times10^9$. The weight product $\mat H\mat W$ costs $nd^2=1.64\times10^{10}$ either way. The sparse layer totals $1.89\times10^{10}$, about $6{,}800$ times less than the dense product alone.

Memory. The dense $\hat{\mat A}$ needs $n^2\cdot4=4\times10^{12}$ bytes, four terabytes, almost all of them zeros. The edge list needs $2m\cdot2\cdot8=3.2\times10^8$ bytes, $320$ megabytes.

Receptive field. The average degree is $2m/n=20$. A node has about $20$ neighbours, each with about $20$ more, so within three hops there can be up to $20^3=8{,}000$ nodes, and a three-layer prediction for one node can depend on all of them. Computing it exactly for a batch of targets means gathering their neighbourhoods first.

Sampling. Drawing $25$ neighbours per node for the first layer and $10$ for the second bounds a two-layer neighbourhood at $25\times10=250$ nodes, whatever the degrees. Hamilton, Ying and Leskovec (2017) trained on large graphs this way.

Check — sanity

On a sparse graph the neighbour sums are cheaper than the weight product: $2md<nd^2$ exactly when the average degree $2m/n$ is below $d$, here $20<128$.