Chapter 14 · I.14

Problems

A chapter that uses mathematics has to teach that mathematics by making the reader compute. A chapter that only displays equations has failed, however correct the equations are.

M3Load-bearing

5/5 problems5/4 variants10/10 exercisesquota met, and enforced

The contract

5 worked problems, minimum.
4 distinct variants, and no variant more than half of them.
10 exercises, every one with a published solution.
At least one numeric problem — present.
At least one symbolic problem — present.
At least one limit or counterexample problem — present.
At least one complexity or shape problem — present.
At least one ▲▲▲ problem — present.

Numerical instantiationSymbolic derivationConstructed failureCost accountingDimensional algebra

Problem I.14.B01

One round of message passing, three aggregators

numeric▲△△

Exact values where possible; six decimal places otherwise.

STATEMENT

Run one round of message passing on a four-node graph with a sum, a mean and the graph convolution’s weighted average, then relabel the graph and confirm that each output is relabelled with it.

GIVEN

The paw graph: a triangle on nodes $1$ , $2$ and $3$ , and node $4$ joined to node $3$ . Scalar features $\vec x=(1,2,3,4)$ . The relabelling swaps nodes $1$ and $4$ .

FIND

$\mat A\vec x$ ; the mean over neighbours; $\hat{\mat A}\vec x$ with $\hat{\mat A}=\tilde{\mat D}^{-1/2}(\mat A+\mat I)\tilde{\mat D}^{-1/2}$ ; the same three after relabelling.

STRATEGY

Read each node’s neighbours off the graph. For the graph convolution, include the node itself and weight each pair by $1/\sqrt{\tilde d_v\tilde d_u}$ .

SOLUTION

Sum. Node $1$ ‘s neighbours are $2$ and $3$ ; node $2$ ‘s are $1$ and $3$ ; node $3$ ‘s are $1$ , $2$ and $4$ ; node $4$ ‘s is $3$ . So

\begin{aligned} \mat A\vec x&=(2+3,\;1+3,\\ &\qquad1+2+4,\;3)\\ &=(5,4,7,3). \end{aligned}

Mean. The degrees are $(2,2,3,1)$ , giving $(2.5,\;2,\;2.333333,\;3)$ .

Graph convolution. With self-loops the degrees are $(3,3,4,2)$ . Node $1$ averages nodes $1$ , $2$ and $3$ :

\begin{aligned} &(\hat{\mat A}\vec x)_1\\ &\;=\frac13+\frac23+\frac{3}{\sqrt{12}}\\ &\;=1+0.866025=1.866025. \end{aligned}

Node $2$ averages the same three nodes with the same weights, so it also gets $1.866025$ . Node $3$ gets $\tfrac{3}{\sqrt{12}}+\tfrac34+\tfrac{4}{\sqrt8}=3.030239$ , and node $4$ gets $\tfrac{3}{\sqrt8}+\tfrac42=3.060660$ .

Relabelled. Swapping nodes $1$ and $4$ gives $\vec x'=(4,2,3,1)$ , and node $1$ is now the pendant. Repeating the computation on the relabelled graph gives

\begin{aligned} &\text{sum: }(3,4,7,5),\\ &\text{mean: }(3,\,2,\,2.333333,\,2.5),\\ &\text{convolution:}\\ &\quad(3.060660,\,1.866025,\\ &\quad\;\;3.030239,\,1.866025), \end{aligned}

in each case the original output with its first and last entries swapped.

Answer

Sum $(5,4,7,3)$ ; mean $(2.5,\,2,\,2.333333,\,3)$ ; graph convolution $(1.866025,\,1.866025,$ $3.030239,\,3.060660)$ . After relabelling, each is the original with entries $1$ and $4$ exchanged.

Check — sanity

The entries of $\mat A\vec x$ add to $19$ , and each feature is counted once per neighbour: $1\cdot2+2\cdot2+3\cdot3+4\cdot1=19$ .

Check — numeric · i-14-gnn-checks.py

The complete reproduction script uses only the Python standard library. From a checkout of the repository, run:

python3 scripts/snippets/i-14-gnn-checks.py

It checks all fifteen problems of the chapter and the numbers quoted in its four propositions, including the eigenvalues of the paw graph’s $\hat{\mat A}$ , computed by Jacobi rotations, and a message-passing network run on the two-triangle and hexagon graphs.

Executed in CI. The digits above are the digits it printed.

Where this breaks

The graph convolution gave nodes $1$ and $2$ the same value although their features differ, because their closed neighbourhoods coincide. A layer with a separate self-term, $\vec h_v'=w_0x_v+w_1(\mat A\vec x)_v$ , keeps them apart whenever $w_0\neq w_1$ .

Variation

With features $\vec x=(1,1,1,1)$ the sum returns the degrees $(2,2,3,1)$ , the mean returns all ones, and the graph convolution returns $(0.955342,\,0.955342,$ $1.180904,\,0.853553)$ . The mean has erased even the degrees; the graph convolution keeps a trace of them.

Problem I.14.B02

Where repeated averaging converges, and how fast

symbolic▲▲▲

Exact values where possible; six decimal places otherwise.

STATEMENT

Find the eigenvalues and the limit of the graph convolution’s averaging on the paw graph exactly, using the graph’s symmetry, and bound the distance to the limit after $k$ layers.

GIVEN

The paw graph of I.14.B01, with degrees $\tilde{\vec d}=(3,3,4,2)$ counted with self-loops, $\hat{\mat A}=\tilde{\mat D}^{-1/2}(\mat A+\mat I)\tilde{\mat D}^{-1/2}$ and $\vec x=(1,2,3,4)$ .

FIND

(a) An eigenvector with eigenvalue $1$ , and one with eigenvalue $0$ . (b) The other two eigenvalues, exactly. (c) The limit of $\hat{\mat A}^k\vec x$ . (d) A bound on the distance after $k$ layers, and its value at $k=8$ .

STRATEGY

Guess two eigenvectors from the structure: square roots of degrees, and the difference of the two nodes that swap under the graph’s symmetry. Get the other two from the trace of $\hat{\mat A}$ and of $\hat{\mat A}^2$ .

SOLUTION

(a) Let $\vec s=(\sqrt3,\sqrt3,2,\sqrt2)$ , the square roots of the degrees. Then

\begin{aligned} \hat{\mat A}\vec s &=\tilde{\mat D}^{-1/2}(\mat A+\mat I)\mathbf 1\\ &=\tilde{\mat D}^{-1/2}\tilde{\vec d}=\vec s, \end{aligned}

since each row of $\mat A+\mat I$ sums to the degree with self-loop. So $\vec s$ has eigenvalue $1$ . Nodes $1$ and $2$ have identical rows of $\hat{\mat A}$ , so $\hat{\mat A}(1,-1,0,0)^{\mathsf T}=\vec 0$ : eigenvalue $0$ .

(b) The trace of $\hat{\mat A}$ is the sum of its diagonal, $\sum_v1/\tilde d_v=\tfrac13+\tfrac13+\tfrac14+\tfrac12=\tfrac{17}{12}$ . The other two eigenvalues therefore add to $\tfrac{17}{12}-1-0=\tfrac5{12}$ . The trace of $\hat{\mat A}^2$ is the sum of squared entries. The diagonal gives $\tfrac19+\tfrac19+\tfrac1{16}+\tfrac14=\tfrac{77}{144}$ , and the four edges, each appearing twice, give $2\big(\tfrac19+\tfrac1{12}+\tfrac1{12}+\tfrac18\big)=\tfrac{116}{144}$ , for a total of $\tfrac{193}{144}$ . So the squares of the two add to $\tfrac{193}{144}-1=\tfrac{49}{144}$ , and their product is $\tfrac12\big((\tfrac5{12})^2-\tfrac{49}{144}\big)=-\tfrac1{12}$ . They solve $12\lambda^2-5\lambda-1=0$ :

\begin{aligned} \lambda&=\frac{5\pm\sqrt{73}}{24}\\ &=0.564333,\;-0.147667. \end{aligned}

(c) All other eigenvalues have absolute value below $1$ , so only the component along $\vec u_1=\vec s/\|\vec s\|$ survives, and $\|\vec s\|^2=12$ . With $\vec s^{\mathsf T}\vec x=3\sqrt3+6+4\sqrt2=16.853006$ ,

\begin{aligned} &\vec u_1\vec u_1^{\mathsf T}\vec x=\frac{16.853006}{12}\,\vec s\\ &\;=1.404417\,\vec s\\ &\;=(2.432522,\;2.432522,\\ &\;\qquad2.808834,\;1.986146). \end{aligned}

(d) Write $\vec x$ minus its limit in the remaining orthonormal eigenvectors. Each component is multiplied by its eigenvalue at every layer, and none exceeds $0.564333$ in absolute value, so

\begin{aligned} &\big\|\hat{\mat A}^k\vec x-\vec u_1\vec u_1^{\mathsf T}\vec x\big\|\\ &\;\;\leq0.564333^k\cdot2.516217, \end{aligned}

where $2.516217$ is the starting distance. At $k=8$ the bound is $0.025884$ and the actual distance $0.024757$ : almost all of the remainder lies along the second eigenvector.

Answer

Eigenvalues $1$ , $(5+\sqrt{73})/24=0.564333$ , $0$ and $(5-\sqrt{73})/24=-0.147667$ ; limit $1.404417\,\vec s=(2.432522,\,2.432522,$ $2.808834,\,1.986146)$ ; distance at most $0.564333^k\cdot2.516217$ , which is $0.025884$ at $k=8$ , against an actual $0.024757$ .

Check — sanity

The four eigenvalues add to $\tfrac{17}{12}$ , the trace. Divided by $\sqrt{\tilde d_v}$ , every entry of the limit is $1.404417$ : the nodes are indistinguishable except through their degrees.

Where this breaks

Without self-loops the graph’s normalised adjacency would have eigenvalue $-1$ if the graph were bipartite; the paw is not, because it contains a triangle. Learned weights between layers change the rate, and the bound then needs their singular values as well.

Variation

The zero eigenvalue means one layer removes the difference between nodes $1$ and $2$ completely, which is why I.14.B01 found them equal. Any graph with two nodes sharing a closed neighbourhood and a degree has such an eigenvector.

Problem I.14.B03

Two triangles and a hexagon

counterexample▲▲△

Exact.

STATEMENT

Exhibit two graphs that differ in structure but that every message-passing network maps to the same output, and name a quantity that tells them apart.

GIVEN

Graph $G_1$ is two disjoint triangles; $G_2$ is a cycle of six nodes. Every node starts with the same feature vector. A message-passing network has any number of layers of the form (I.14.2), any aggregator, and a sum readout.

FIND

The colour-refinement colours of both graphs; the network’s outputs; the number of triangles and of connected components in each.

STRATEGY

Run colour refinement by hand: it stalls after one round. Then apply the induction of I.14.T4.

SOLUTION

Refinement. All nodes start with one colour. In both graphs every node has two neighbours, each with that colour, so every node receives the same signature, (one colour, two neighbours of that colour), and one new colour. The next round sees the same thing. The colour counts, six nodes of one colour, agree at every round.

The network. By the induction in proposition 4, a node’s state after layer $t$ is a function of its colour after round $t$ . All twelve nodes share a colour at every round, so all twelve have the same state at every layer, whatever the weights. The sum readout returns six times that state for both graphs. The outputs are identical.

The check script confirms it for three randomly weighted sum networks of three layers: the sorted node states of $G_1$ and $G_2$ agree to twelve decimal places.

What differs. The number of triangles is $\operatorname{tr}(\mat A^3)/6$ , because each triangle gives six closed walks of length three: $2$ for $G_1$ and $0$ for $G_2$ . $G_1$ has two connected components and $G_2$ one. A molecule-property model could hardly be indifferent to either.

Answer

Every node gets the same colour at every round in both graphs, so every message-passing network gives identical node states and readouts. They differ in triangles, $2$ against $0$ , and components, $2$ against $1$ .

Check — sanity

Both graphs have six nodes and six edges and are $2$ -regular, so any statistic built from degrees alone must agree. The difference is in cycles, which no fixed number of local averaging steps can count here.

Where this breaks

The construction needs identical starting features. Give each node its number of triangles as a feature, and a single layer separates the graphs. Random features also separate them, at the price of an output that is equivariant only in distribution.

Variation

Any two $r$ -regular graphs on the same number of nodes are indistinguishable by colour refinement and hence by message passing. Two disjoint copies of the complete graph on four nodes and the cube are both $3$ -regular on eight nodes; the first has $8$ triangles and the second none.

Problem I.14.B04

What a graph layer costs

complexity▲▲△

Three significant figures.

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.

Answer

Dense $\hat{\mat A}\mat H$ : $1.28\times10^{14}$ ; sparse: $2.56\times10^9$ ; $\mat H\mat W$ : $1.64\times10^{10}$ ; sparse layer $1.89\times10^{10}$ . Dense matrix $4\times10^{12}$ bytes; edge list $3.2\times10^8$ . Average degree $20$ ; up to $8{,}000$ nodes in three hops; $250$ with sampling over two layers.

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$ .

Where this breaks

The counts assume the edge list is processed with gather and scatter operations whose cost is proportional to the work. On hardware tuned for dense products, irregular memory access can make the sparse layer slower per operation, though never by the four orders of magnitude separating the two counts.

Variation

At width $d=16$ the weight product shrinks to $2.56\times10^8$ , and the neighbour sums, $3.2\times10^8$ , dominate. Narrow graph networks are limited by the edges, wide ones by the weights.

Problem I.14.B05

A batch of three graphs

shape▲▲△

Exact.

STATEMENT

Put three graphs of different sizes into one batch, give the shape of every array, and find what goes wrong when the edge lists are not offset.

GIVEN

The paw graph ( $4$ nodes, edges $01$ , $02$ , $12$ , $23$ ), a path on $3$ nodes ( $01$ , $12$ ) and a cycle on $5$ nodes ( $01$ , $12$ , $23$ , $34$ , $40$ ), each numbered from $0$ . Node features have width $d$ . The readout sums node states per graph. For the check, every feature is $1$ and one round of sum aggregation is applied.

FIND

The total node count; the shapes of the batched features, the batch vector, the edge index and the readout; the offsets; the readouts with and without offsets.

STRATEGY

Stack the graphs’ nodes one after another. A batch is then one large graph whose adjacency matrix is block diagonal, provided every edge is shifted by the number of nodes before its graph.

SOLUTION

Shapes. There are $4+3+5=12$ nodes, so the features are $12\times d$ . The batch vector, of length $12$ , records each node’s graph: $(0,0,0,0,1,1,1,2,2,2,2,2)$ . The $11$ undirected edges become $22$ directed entries, so the edge index is $2\times22$ . The readout is $3\times d$ , one row per graph.

Offsets. Graph $g$ ‘s node $i$ becomes node $i+o_g$ with $o=(0,4,7)$ , the running total of earlier sizes. The adjacency matrix of the batch is then block diagonal, and no message crosses between graphs. Since sum aggregation over a block-diagonal matrix acts on each block separately, batching changes no graph’s result.

The check. With all features $1$ , one round of sum aggregation gives each node its degree, and the per-graph sum of degrees is twice the edge count: $8$ , $4$ and $10$ .

Without offsets. All three edge lists then refer to nodes $0$ to $4$ . The path’s edges coincide with two of the paw’s and merge into them, and the cycle’s edges connect the paw’s nodes to one another and to node $4$ , which belongs to the path. The readouts become $10$ , $2$ and $0$ . The shapes are all still correct, so nothing fails until the numbers are compared.

Answer

$12$ nodes; features $12\times d$ ; batch vector length $12$ ; edge index $2\times22$ ; readout $3\times d$ ; offsets $(0,4,7)$ . Readouts $8$ , $4$ , $10$ with offsets and $10$ , $2$ , $0$ without.

Check — sanity

Each correct readout equals twice that graph’s number of edges, $2\cdot4$ , $2\cdot2$ and $2\cdot5$ , as the handshake count requires.

Where this breaks

A readout by mean needs each graph’s node count, $4$ , $3$ and $5$ , taken from the batch vector; dividing by $12$ would mix the graphs again. Graph libraries keep the batch vector for exactly this reason.

Variation

A dense alternative pads every graph to the largest size, $5$ , giving features of shape $3\times5\times d$ and three $5\times5$ adjacency matrices. It wastes $3$ of $15$ node slots here, and far more when sizes vary widely.

Exercises

Every one has a published solution. A hidden solution is a solution; a missing one is an abandonment.

I.14.X01A graph convolution on a path of threenumeric▲△△

For the path $1$ – $2$ – $3$ , write $\hat{\mat A}$ of (I.14.5) and apply it to the signal $(1,0,0)$ , a unit at one end. Where has the signal gone after one layer?

Hint

With self-loops the degrees are $2$ , $3$ and $2$ , and $\hat A_{vu}=1/\sqrt{\tilde d_v\tilde d_u}$ for neighbours and for $u=v$ .

Solution

The matrix is

\hat{\mat A}=\begin{bmatrix} \tfrac12&\tfrac1{\sqrt6}&0\\[2pt] \tfrac1{\sqrt6}&\tfrac13&\tfrac1{\sqrt6}\\[2pt] 0&\tfrac1{\sqrt6}&\tfrac12 \end{bmatrix}.

Its first column is the output for the input $(1,0,0)$ : $(0.5,\;0.408248,\;0)$ . Half of the unit stays at node $1$ , part moves to its neighbour, and node $3$ , two hops away, receives nothing. A second layer would reach it, as I.14.T2 says.

The output’s entries add to $0.908248$ , not $1$ : the symmetric normalisation does not preserve sums. It preserves the vector of square roots of degrees, $(\sqrt2,\sqrt3,\sqrt2)$ , which it maps to itself.

I.14.X08Message passing with an edge listshape▲△△

Store the paw graph as an edge index: a $2\times E$ array whose columns are (source, target) pairs. How large is $E$ for message passing in both directions, and with self-loops? Implement $\mat A\vec x$ for $\vec x=(1,2,3,4)$ as a gather followed by a scatter-add, and give the shape of each intermediate.

Hint

An undirected edge sends messages both ways, so it is stored twice.

Solution

The paw has $4$ undirected edges. Stored in both directions they give $E=8$ columns; adding one self-loop per node gives $12$ .

The gather reads the source of each column: with features of width $d$ it produces an $E\times d$ array of messages, here $8\times1$ . The scatter-add sends each message to its target and sums by target, producing $n\times d$ , here $4\times1$ . The result is $(5,4,7,3)$ , the same as $\mat A\vec x$ in I.14.B01, and it never forms the $4\times4$ matrix.

Two details matter in practice. The scatter must add, not assign: node $3$ has three incoming messages, and assignment would keep one of them, the mistake I.11.T2 warned against for overlapping windows. And the order of additions is not fixed on parallel hardware, so results can differ in the last bits from run to run, though never in a way that depends on the labelling.

I.14.X02Equivariance, proved and brokenproof▲▲△

Prove that the sum layer $\mat H'=\sigma(\mat H\mat W_0+\mat A\mat H\mat W_1)$ , with $\sigma$ applied entrywise, is permutation-equivariant, and that the readout $\mathbf 1^{\mathsf T}\mat H'$ is invariant. Then show that the layer “take the feature of your lowest-numbered neighbour” is not equivariant, using the paw graph with $\vec x=(1,2,3,4)$ and the relabelling that swaps nodes $1$ and $4$ .

Hint

$\mat P^{\mathsf T}\mat P=\mat I$ , an entrywise function commutes with reordering rows, and $\mathbf 1^{\mathsf T}\mat P=\mathbf 1^{\mathsf T}$ .

Solution

Equivariance. Relabel: $\mat A\mapsto\mat P\mat A\mat P^{\mathsf T}$ and $\mat H\mapsto\mat P\mat H$ . The pre-activation becomes

\begin{aligned} &\mat P\mat H\mat W_0+\mat P\mat A\mat P^{\mathsf T}\mat P\mat H\mat W_1\\ &\;\;=\mat P\big(\mat H\mat W_0+\mat A\mat H\mat W_1\big). \end{aligned}

An entrywise $\sigma$ applied to a matrix with reordered rows gives the same rows reordered, so the output is $\mat P\mat H'$ . $\blacksquare$

Invariance. A permutation matrix’s columns each contain one $1$ , so $\mathbf 1^{\mathsf T}\mat P=\mathbf 1^{\mathsf T}$ and $\mathbf 1^{\mathsf T}(\mat P\mat H')=\mathbf 1^{\mathsf T}\mat H'$ . $\blacksquare$

A layer that breaks it. On the paw the lowest-numbered neighbours of nodes $1$ to $4$ are $2$ , $1$ , $1$ and $3$ , so the layer returns $(2,1,1,3)$ . After swapping nodes $1$ and $4$ , the features are $(4,2,3,1)$ and the lowest-numbered neighbours are $3$ , $3$ , $1$ and $2$ : the layer returns $(3,3,4,2)$ . Equivariance would require the original output with its first and last entries swapped, $(3,1,1,2)$ . The second and third entries differ: node $2$ ‘s output changed although nothing about node $2$ did. The layer reads the labelling, which carries no information about the graph.

I.14.X03A mean and a max cannot countcounterexample▲▲△

Find what the sum, the mean and the maximum return for the multisets $\{1,1,2,2\}$ and $\{1,2\}$ , and for $\{1,1,2\}$ and $\{1,2,2\}$ . Then give every node of a star with two leaves and of a star with four leaves the feature $1$ , and compare what each aggregator delivers to the centre.

Hint

A mean sees proportions; a maximum sees which values occur.

Solution

multisets	sum	mean	max
$\{1,1,2,2\}$ , $\{1,2\}$	$6$ , $3$	$1.5$ , $1.5$	$2$ , $2$
$\{1,1,2\}$ , $\{1,2,2\}$	$4$ , $5$	$1.333333$ , $1.666667$	$2$ , $2$

The first pair has the same proportions, so the mean cannot separate it, and the same values, so the maximum cannot either. The second pair has different proportions but the same values: the mean separates it and the maximum does not. The sum separates both.

At the stars’ centres, the neighbour features are $\{1,1\}$ and $\{1,1,1,1\}$ . The mean gives $1$ and $1$ , the maximum $1$ and $1$ , the sum $2$ and $4$ . With constant features, a mean- or max-aggregating network cannot even learn a node’s degree.

So mean and max aggregators separate strictly fewer graphs than colour refinement, which counts. This is why the graph isomorphism network of (I.14.8) sums. The mean has its uses: it keeps the scale of the state independent of the degree, which helps on graphs with very uneven degrees. The choice trades counting for stability.

I.14.X04No direction on a cyclesymbolic▲▲△

On a cycle of six nodes, write $\hat{\mat A}$ and find its eigenvalues. Show that no polynomial in $\hat{\mat A}$ , and hence no stack of linear graph convolutions with scalar weights, can compute the difference $x_{i+1}-x_{i-1}$ at every node.

Hint

$\hat{\mat A}$ is a circulant matrix, and its eigenvectors are the discrete Fourier modes. For the second part, compare transposes.

Solution

Every node has degree $3$ with its self-loop, so $\hat{\mat A}$ has $\tfrac13$ on the diagonal and on the two neighbouring positions of each row, cyclically. On the Fourier mode $x_i=e^{\mathrm i\theta i}$ with $\theta=2\pi j/6$ it acts as multiplication by

\frac{e^{-\mathrm i\theta}+1+e^{\mathrm i\theta}}{3}=\frac{1+2\cos\theta}{3},

so the eigenvalues are $1$ , $\tfrac23$ , $\tfrac23$ , $0$ , $0$ and $-\tfrac13$ . High frequencies are damped and the lowest kept: a low-pass filter.

The difference operator $\mat D$ , with $(\mat D\vec x)_i=x_{i+1}-x_{i-1}$ , satisfies $\mat D^{\mathsf T}=-\mat D$ : it is antisymmetric. Every power of the symmetric $\hat{\mat A}$ is symmetric, so every polynomial $\sum_kc_k\hat{\mat A}^k$ is symmetric. A matrix that is both symmetric and antisymmetric is zero, and $\mat D$ is not zero. So no polynomial in $\hat{\mat A}$ equals $\mat D$ . $\blacksquare$

A convolution of width three, as in I.11, computes $\mat D$ with weights $(-1,0,1)$ . The graph convolution cannot, because it has no way to tell the neighbour at $i+1$ from the one at $i-1$ . Features that encode position around the cycle, which the bare graph does not supply, would be needed.

I.14.X05How fast a hexagon smooths, and why self-loops matterlimit▲▲△

Using the eigenvalues of I.14.X04, find how many graph-convolution layers bring the distance from the limit on a hexagon below one per cent of where it started. Then drop the self-loops, using $\mat D^{-1/2}\mat A\mat D^{-1/2}$ , and apply it repeatedly to the alternating signal $(1,-1,1,-1,1,-1)$ . What happens as the number of layers grows?

Hint

The distance shrinks by at most the largest eigenvalue below $1$ in absolute value per layer. Without self-loops every degree is $2$ .

Solution

The eigenvalues other than $1$ are $\tfrac23$ , $\tfrac23$ , $0$ , $0$ and $-\tfrac13$ , so $|\lambda_2|=\tfrac23$ and the distance after $k$ layers is at most $(\tfrac23)^k$ times its start. $(\tfrac23)^{11}=0.011561$ and $(\tfrac23)^{12}=0.007707$ , so $12$ layers suffice for any starting signal, and a signal with a component along the slowest mode needs that many.

Without self-loops the operator is $\mat A/2$ , and its eigenvalues are $\cos\theta$ for $\theta=2\pi j/6$ : $1$ , $\tfrac12$ , $\tfrac12$ , $-\tfrac12$ , $-\tfrac12$ and $-1$ . The eigenvalue $-1$ belongs to the alternating signal: each node’s two neighbours have the opposite sign, so the average is exactly the negative. The signal flips sign at every layer and never converges. The limit of I.14.T3 does not exist.

The hexagon is bipartite, since its nodes split into alternate halves with every edge between them, and every bipartite graph has this eigenvalue. The self-loop mixes each node with itself. On a graph where every degree is $r$ it maps each eigenvalue $\lambda$ of the plain operator to $(r\lambda+1)/(r+1)$ , so $-1$ becomes $(1-r)/(r+1)$ , which is $-\tfrac13$ here. On any connected graph it rules out $-1$ .

I.14.X06Backpropagation through one graph convolutiongradient▲▲△

Derive the gradients of a loss $\mathcal L$ with respect to $\mat W$ and $\mat H$ for the linear layer $\mat Y=\hat{\mat A}\mat H\mat W$ , given $\mat G=\partial\mathcal L/\partial\mat Y$ . Then evaluate them for the paw graph with scalar features $\vec x=(1,2,3,4)$ , weight $w=0.5$ , target $\vec t=(0,0,1,1)$ and $\mathcal L=\tfrac12\|\vec y-\vec t\|^2$ .

Hint

Treat $\hat{\mat A}\mat H$ as one matrix and use the chain rule for matrix products (The chain rule for matrix products 0.MC.07). $\hat{\mat A}$ is symmetric.

Solution

With $\mat Z=\hat{\mat A}\mat H$ , $\mat Y=\mat Z\mat W$ , so $\partial\mathcal L/\partial\mat W=\mat Z^{\mathsf T}\mat G=(\hat{\mat A}\mat H)^{\mathsf T}\mat G$ and $\partial\mathcal L/\partial\mat Z=\mat G\mat W^{\mathsf T}$ . Then $\partial\mathcal L/\partial\mat H=\hat{\mat A}^{\mathsf T}\mat G\mat W^{\mathsf T}=\hat{\mat A}\mat G\mat W^{\mathsf T}$ . The backward pass through a graph convolution is another graph convolution, applied to the gradients: each node receives a degree-weighted average of its neighbours’ errors.

For the numbers, $\hat{\mat A}\vec x=(1.866025,\,1.866025,$ $3.030239,\,3.060660)$ from I.14.B01, so

\begin{aligned} \vec y&=(0.933013,\;0.933013,\\ &\qquad1.515119,\;1.530330), \end{aligned}

the residual is $\vec y-\vec t=(0.933013,\,0.933013,$ $0.515119,\,0.530330)$ , and $\mathcal L=1.143812$ . The weight’s gradient is the dot product of $\hat{\mat A}\vec x$ with the residual, $6.666146$ . The input’s gradient is $0.5\,\hat{\mat A}(\vec y-\vec t)=(0.385355,\,0.385355,$ $0.427478,\,0.223644)$ .

Nodes $1$ and $2$ receive the same gradient, as they produced the same output: one layer cannot tell them apart in either direction. The script confirms all five derivatives by central finite differences.

I.14.X07Two layers cannot see three hopsnumeric▲▲△

Give every node the feature $1$ on a path of four nodes and on a path of five. Apply the graph convolution’s $\hat{\mat A}$ one, two and three times, and compare the value at node $1$ , an end of each path. When do the two first differ, and why then?

Hint

After $k$ applications node $1$ depends on the degrees and features within $k$ hops. In both paths nodes $1$ , $2$ and $3$ have the same degrees; node $4$ does not.

Solution

layers	path of four	path of five
$1$	$0.908248$	$0.908248$
$2$	$0.892956$	$0.892956$
$3$	$0.890408$	$0.880213$

The values agree for two layers and differ at the third. Node $1$ ‘s value after $k$ layers uses the entries of $\hat{\mat A}$ along walks of length at most $k$ from it. Those entries depend on the degrees at both ends of each edge walked. Within two hops of node $1$ the walks touch only nodes $1$ , $2$ and $3$ , whose degrees are $1$ , $2$ and $2$ in both paths. The third layer walks the edge from node $3$ to node $4$ , and node $4$ has degree $1$ in the shorter path and $2$ in the longer.

So a two-layer network cannot tell whether node $1$ sits on a path of four or five, whatever its width or weights. That is I.14.T2 at work: a task that depends on something three hops away needs three layers, and the averaging of proposition 3 makes each extra layer cost something.

I.14.X09Averaging over sampled neighboursprobability▲▲△

A node has $100$ neighbours whose features have mean $\mu$ and variance $\sigma^2=1$ around it. A sampled layer averages $s$ of them, drawn without replacement. Show that the sampled mean is unbiased, find its variance, and evaluate it for $s=10$ , $25$ and $100$ .

Hint

Each neighbour is included with probability $s/100$ . For sampling without replacement from a finite population of size $N$ , the variance of the sample mean is $(\sigma^2/s)(N-s)/(N-1)$ .

Solution

Write the sampled mean as $\tfrac1s\sum_uI_ux_u$ , where $I_u$ is $1$ if neighbour $u$ is drawn. Each $I_u$ has mean $s/N$ , so the expectation is $\tfrac1s\cdot\tfrac sN\sum_ux_u=\mu$ : unbiased.

The draws are not independent, since choosing one neighbour makes the others slightly less likely. The covariance of two indicators is $-\tfrac sN\cdot\tfrac{N-s}{N(N-1)}$ , and summing gives the finite-population variance

\operatorname{Var}=\frac{\sigma^2}{s}\cdot\frac{N-s}{N-1}.

With $N=100$ and $\sigma^2=1$ : $0.090909$ at $s=10$ , $0.030303$ at $s=25$ , and $0$ at $s=100$ , where every neighbour is used and the mean is exact. Independent draws would have given $0.1$ and $0.04$ ; the factor $(N-s)/(N-1)$ is what sampling without replacement saves.

The layer stays unbiased in expectation, but a nonlinearity applied after it does not average out the noise exactly, and stacking sampled layers compounds it. Sampling buys a fixed cost per node at the price of a noisy, slightly biased deep network, a trade Hamilton, Ying and Leskovec (2017) found worth making on large graphs.

I.14.X10The Laplacian spectrum separates the pairsymbolic▲▲△

Find the eigenvalues of the Laplacian $\mat L=\mat D-\mat A$ for two disjoint triangles and for a hexagon. Show that they differ, explain which eigenvalue counts components, and say what goes wrong if the eigenvectors are fed to a network as node positions.

Hint

A cycle of $n$ nodes has Laplacian eigenvalues $2-2\cos(2\pi j/n)$ . The spectrum of a disjoint union is the union of the spectra.

Solution

For the hexagon, $2-2\cos(2\pi j/6)$ for $j=0,\ldots,5$ gives $0,1,3,4,3,1$ , that is $\{0,1,1,3,3,4\}$ . For one triangle it gives $0,3,3$ ; for two, $\{0,0,3,3,3,3\}$ . The spectra differ, so a network given spectral information can separate the pair that defeated colour refinement in I.14.B03.

The eigenvalue $0$ counts connected components. Since $\vec x^{\mathsf T}\mat L\vec x=\sum_{(u,v)\in E}(x_u-x_v)^2$ by (I.14.4), $\mat L\vec x=\vec 0$ exactly when $\vec x$ is constant across every edge, that is, constant on each component. There is one independent such vector per component: one for the hexagon, two for the triangles.

As positions the eigenvectors have two ambiguities. Each is defined only up to sign, so a network must give the same answer for $\vec v$ and $-\vec v$ , or it depends on an arbitrary choice made by the eigensolver. And a repeated eigenvalue has no preferred basis: the two triangles’ eigenvalue $3$ has a four-dimensional eigenspace, and any rotation within it is as valid as any other. Positional features from the Laplacian therefore need architectures invariant to these choices, or they reintroduce exactly the dependence on arbitrary labels that equivariance was built to remove.