"""Bishop and Bishop (2024), Chapter 13: Graph Neural Networks.

Reproduces the figures of Chapter 13 of C. M. Bishop and H. Bishop, Deep Learning: Foundations and
Concepts (Springer, 2024), pp. 407-427, written from scratch with numpy, PyTorch (autograd only, for
the depth experiment) and matplotlib, and supplies the data and reference
numbers of the three browser demonstrations. Every operation is a short function meant to be read
next to the lecture notes (ch13-graph-neural-networks.html):

* Section 13.1, graphs: adjacency(), the graph of Figure 13.2 (FIG132_EDGES), the graph of
  Exercise 13.3 (EX133_A), Zachary's karate club (KARATE_EDGES, KARATE_CLUB; Zachary 1977, typed in
  from the published edge list), perm_matrix() for the permutation matrix (13.3) and its action
  PX (13.4) and PAP^T (13.5), automorphism_count() and distinct_adjacency_count().
* Section 13.2, message passing: aggregate() with the sum (13.12), mean (13.13), Kipf-Welling
  (13.14), element-wise max and MLP (13.15) aggregations, mp_layer() for the update (13.16),
  mp_layer_matrix() for the matrix form of Exercise 13.6, prop_matrix() for the propagation matrices
  (including the renormalised GCN matrix D~^(-1/2)(A + I)D~^(-1/2)), normalized_laplacian(),
  readout() for graph-level outputs (13.23) and edge_probabilities() for (13.22).
* The node classifier of Section 13.2.5 in numpy with explicit forward and backward passes and Adam
  (gcn_init, gcn_forward, gcn_backward, gcn_train), written to match gcn-node-classification-demo.html
  line for line: same JSRandom weights, same arithmetic, so the page reproduces the losses.
* Section 13.3: graph attention (13.24)-(13.28) (attention_bilinear, attention_mlp), its link to
  self-attention on a complete graph (Exercise 13.9), the general edge/node/graph update
  (13.32)-(13.35) (general_gnn_layer), over-smoothing (propagate, dirichlet_energy, smoothing_rate,
  appnp_limit) and the E(n)-equivariant layer (13.38)-(13.41) (egnn_layer).
* The equivariance demo's layers (demo_layer) and the over-smoothing demo's iteration (propagate)
  are written so that permutation-equivariance-demo.html and over-smoothing-demo.html reproduce them
  number for number.

Figures reproduced: 13.2 (the adjacency matrix of a five-node graph in two node orders, computed as
A and PAP^T), 13.3 (an image as a grid graph: the shared-weight filter (13.9) computed by message
passing equals a convolution with an isotropic 3x3 kernel) and 13.4 (the receptive field of a node,
computed from the powers of A + I on a random geometric graph). Figures 13.3 and 13.4 are schematic
in the book; here each is computed.
Skipped: 13.1 (drawings of a caffeine molecule, a rail network and linked web pages: illustrations,
no data) and 13.5 (a schematic of which variables enter the edge, node and graph updates; there is
nothing to compute, and the same information is in Algorithm 13.2).

Supplementary figures (our own, numbered 13.S1-13.S7; they illustrate the gaps filled in the notes):
13.S1 the 120 reorderings of the graph of Figure 13.2: a message-passing network is equivariant and
its sum readout invariant, a network on the flattened adjacency matrix is not;
13.S2 the spectra of the normalised Laplacian and of the GCN propagation matrix;
13.S3 over-smoothing: repeated GCN propagation collapses the node features onto the leading
eigenvector at the predicted rate;
13.S4 a two-layer GCN trained on the karate club from one label per faction, against a network that
ignores the edges;
13.S5 accuracy against depth for plain, residual (13.36) and jumping-knowledge (13.37) GCNs on a
stochastic block model;
13.S6 what message passing cannot see: two triangles and a hexagon get identical embeddings, and
mean or max aggregation cannot count neighbours;
13.S7 the E(n)-equivariant layer (13.38)-(13.41) commutes with rotations, reflections and translations.
Exercise figure: fig13-ex3 draws the graph of Exercise 13.3.

Run `python3 ch13_graph_neural_networks.py --list`, `python3 ch13_graph_neural_networks.py` (all
figures, about a minute on one CPU thread, most of it for the 54 small networks of Figure 13.S5,
whose results are then cached) or `python3 ch13_graph_neural_networks.py --fig 13.2 13.S3`.
Files go to ../img/ch13/; the demos' data go to ../data/ch13-graphs.json (written by --fig data or
by a full run); slow results are cached in cache/.
"""
import itertools
import json
import math
import os

for _v in ("OPENBLAS_NUM_THREADS", "MKL_NUM_THREADS", "OMP_NUM_THREADS"):
    os.environ.setdefault(_v, "1")

import numpy as np  # noqa: E402
import matplotlib.pyplot as plt  # noqa: E402
from matplotlib.patches import Rectangle, FancyArrowPatch  # noqa: E402

import common  # noqa: E402
from common import savefig, run, panel_label  # noqa: E402

HERE = os.path.dirname(os.path.abspath(__file__))
CACHE_DIR = os.path.join(HERE, "cache")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
CH = 13
M32 = 0xFFFFFFFF


# =========================================================================== the demos' generator
def _imul(a, b):
    return (a * b) & M32


class JSRandom:
    """The seeded random numbers of the browser demos (DK.rng in courses/demo-kit.js).

    Uniforms come from the mulberry32 generator and normals from the Box-Muller transform, the
    second normal of each pair being cached, exactly as in JavaScript.
    """

    def __init__(self, seed):
        self.a = int(seed) & M32
        self.spare = None

    def u(self):
        a = (self.a + 0x6D2B79F5) & M32
        self.a = a
        t = _imul(a ^ (a >> 15), 1 | a)
        t = ((t + _imul(t ^ (t >> 7), 61 | t)) & M32) ^ t
        return ((t ^ (t >> 14)) & M32) / 4294967296.0

    def _pos(self):
        x = 0.0
        while x == 0.0:
            x = self.u()
        return x

    def norm(self):
        if self.spare is not None:
            s, self.spare = self.spare, None
            return s
        r = math.sqrt(-2.0 * math.log(self._pos()))
        th = 2.0 * math.pi * self.u()
        self.spare = r * math.sin(th)
        return r * math.cos(th)

    def normals(self, n):
        return np.array([self.norm() for _ in range(int(n))])


# =========================================================================== Section 13.1: graphs
FIG132_NODES = "ABCDE"
FIG132_EDGES = [(0, 2), (1, 2), (2, 3), (2, 4), (3, 4)]          # A-C, B-C, C-D, C-E, D-E
FIG132_POS = np.array([[0.28, 0.78], [0.05, 0.30], [0.47, 0.40], [0.72, 0.80], [0.82, 0.22]])
FIG132_PERM = [2, 4, 0, 3, 1]       # the new order (C, E, A, D, B): new node n is old node pi(n), 0-based

EX133_A = np.array([[0, 1, 1, 0, 1],
                    [1, 0, 1, 1, 1],
                    [1, 1, 0, 1, 0],
                    [0, 1, 1, 0, 0],
                    [1, 1, 0, 0, 0]], dtype=float)                # (13.42)

# Zachary's karate club (Zachary 1977): 34 members, 78 friendships; 0-based node numbers.
KARATE_EDGES = [
    (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 10), (0, 11), (0, 12), (0, 13),
    (0, 17), (0, 19), (0, 21), (0, 31), (1, 2), (1, 3), (1, 7), (1, 13), (1, 17), (1, 19), (1, 21), (1, 30),
    (2, 3), (2, 7), (2, 8), (2, 9), (2, 13), (2, 27), (2, 28), (2, 32), (3, 7), (3, 12), (3, 13), (4, 6),
    (4, 10), (5, 6), (5, 10), (5, 16), (6, 16), (8, 30), (8, 32), (8, 33), (9, 33), (13, 33), (14, 32),
    (14, 33), (15, 32), (15, 33), (18, 32), (18, 33), (19, 33), (20, 32), (20, 33), (22, 32), (22, 33),
    (23, 25), (23, 27), (23, 29), (23, 32), (23, 33), (24, 25), (24, 27), (24, 31), (25, 31), (26, 29),
    (26, 33), (27, 33), (28, 31), (28, 33), (29, 32), (29, 33), (30, 32), (30, 33), (31, 32), (31, 33),
    (32, 33)]
# the faction each member joined after the split: 0 = the instructor (node 0), 1 = the administrator (node 33)
KARATE_CLUB = [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1,
               1, 1, 1, 1]


def adjacency(N, edges):
    """Symmetric 0/1 adjacency matrix of a simple undirected graph with the given edge list."""
    A = np.zeros((N, N))
    for n, m in edges:
        A[n, m] = A[m, n] = 1.0
    return A


def edges_of(A):
    """Edge list (n < m) of a symmetric adjacency matrix."""
    N = len(A)
    return [(n, m) for n in range(N) for m in range(n + 1, N) if A[n, m] != 0]


def karate():
    """(A, labels) for the karate club."""
    return adjacency(34, KARATE_EDGES), np.array(KARATE_CLUB)


def perm_matrix(pi):
    """The permutation matrix (13.3): row n is the unit vector u_{pi(n)}^T (pi is 0-based)."""
    N = len(pi)
    P = np.zeros((N, N))
    P[np.arange(N), np.asarray(pi)] = 1.0
    return P


def automorphism_count(A):
    """Number of permutations P with P A P^T = A (brute force; small graphs only)."""
    N = len(A)
    return sum(1 for pi in itertools.permutations(range(N)) if np.array_equal(A[np.ix_(pi, pi)], A))


def distinct_adjacency_count(A):
    """Number of different adjacency matrices P A P^T over all N! node orders."""
    N = len(A)
    return len({A[np.ix_(pi, pi)].tobytes() for pi in itertools.permutations(range(N))})


def hop_distances(A, src):
    """Breadth-first-search distances from node src (inf if unreachable)."""
    N = len(A)
    d = np.full(N, np.inf)
    d[src] = 0
    frontier = [src]
    while frontier:
        nxt = []
        for n in frontier:
            for m in np.nonzero(A[n])[0]:
                if d[m] == np.inf:
                    d[m] = d[n] + 1
                    nxt.append(m)
        frontier = nxt
    return d


def receptive_field(A, node, L):
    """Nodes whose layer-0 features can influence node `node` after L message-passing layers:
    the support of row `node` of (A + I)^L, which is the set of nodes within L hops."""
    M = np.linalg.matrix_power(A + np.eye(len(A)), L)
    return np.nonzero(M[node] > 0)[0]


def is_connected(A):
    return bool(np.all(np.isfinite(hop_distances(A, 0))))


# ================================================================ random graphs and layouts
def sbm(sizes, p_in, p_out, seed):
    """A stochastic block model: blocks of the given sizes, edge probability p_in inside a block
    and p_out between blocks. Returns (A, labels)."""
    rng = np.random.default_rng(seed)
    labels = np.repeat(np.arange(len(sizes)), sizes)
    N = len(labels)
    P = np.where(labels[:, None] == labels[None, :], p_in, p_out)
    U = rng.uniform(size=(N, N))
    A = np.triu((U < P).astype(float), 1)
    return A + A.T, labels


def connected_sbm(sizes, p_in, p_out, seed):
    s = seed
    while True:
        A, y = sbm(sizes, p_in, p_out, s)
        if is_connected(A):
            return A, y, s
        s += 1


def ring(N):
    return adjacency(N, [(n, (n + 1) % N) for n in range(N)])


def random_geometric(N, radius, seed):
    """Random geometric graph in the unit square, re-drawn until connected. Returns (A, pos)."""
    s = seed
    while True:
        rng = np.random.default_rng(s)
        pos = rng.uniform(0.05, 0.95, size=(N, 2))
        D = np.linalg.norm(pos[:, None] - pos[None], axis=2)
        A = ((D < radius) & (D > 0)).astype(float)
        if is_connected(A):
            return A, pos
        s += 1


def spring_layout(A, seed=0, iters=400):
    """Fruchterman-Reingold force-directed layout, scaled to [0.04, 0.96]^2."""
    rng = np.random.default_rng(seed)
    N = len(A)
    pos = rng.uniform(-1, 1, size=(N, 2))
    k = 1.0 / math.sqrt(N)
    t = 0.12
    for it in range(iters):
        d = pos[:, None, :] - pos[None, :, :]
        dist = np.linalg.norm(d, axis=2) + np.eye(N)
        force = (k * k / dist ** 2 - A * dist / k)            # repulsion minus attraction, divided by dist
        np.fill_diagonal(force, 0.0)
        disp = (force[:, :, None] * d).sum(1)
        L = np.linalg.norm(disp, axis=1) + 1e-12
        pos += disp / L[:, None] * np.minimum(L, t)[:, None]
        t = 0.12 * (1 - (it + 1) / iters) + 1e-3
    pos -= pos.min(0)
    pos /= pos.max(0)
    return 0.04 + 0.92 * pos


# =========================================================================== Section 13.2: message passing
def degrees(A):
    return A.sum(1)


def prop_matrix(A, kind):
    """Propagation matrices: 'sum' A (13.12); 'mean' D^-1 A (13.13); 'kipf' D^-1/2 A D^-1/2 (13.14);
    'gcn' D~^-1/2 (A + I) D~^-1/2 (the renormalised matrix of Kipf and Welling 2017);
    'rw' D~^-1 (A + I) (mean over the neighbours and the node itself); 'self' A + I (13.17)."""
    N = len(A)
    d = degrees(A)
    if kind == "sum":
        return A.copy()
    if kind == "self":
        return A + np.eye(N)
    if kind in ("mean", "kipf"):
        inv = np.where(d > 0, 1.0 / np.where(d > 0, d, 1), 0.0)
        if kind == "mean":
            return inv[:, None] * A
        s = np.sqrt(inv)
        return s[:, None] * A * s[None, :]
    At = A + np.eye(N)
    dt = At.sum(1)
    if kind == "gcn":
        s = 1.0 / np.sqrt(dt)
        return s[:, None] * At * s[None, :]
    if kind == "rw":
        return At / dt[:, None]
    raise ValueError(kind)


def normalized_laplacian(A):
    """L = I - D^-1/2 A D^-1/2 (isolated nodes get a 0 row and column in the second term)."""
    return np.eye(len(A)) - prop_matrix(A, "kipf")


def aggregate(H, A, kind, mlp=None):
    """z_n = Aggregate({h_m : m in N(n)}) for every node, row-wise. kind is 'sum' (13.12), 'mean'
    (13.13), 'kipf' (13.14), 'max' (element-wise maximum; 0 for an isolated node) or 'mlp' (13.15)
    with mlp = (phi, theta), two functions acting on rows."""
    if kind in ("sum", "mean", "kipf"):
        return prop_matrix(A, kind) @ H
    N = len(A)
    if kind == "max":
        Z = np.zeros_like(H)
        for n in range(N):
            nb = np.nonzero(A[n])[0]
            if len(nb):
                Z[n] = H[nb].max(0)
        return Z
    if kind == "mlp":
        phi, theta = mlp
        return theta(A @ phi(H))
    raise ValueError(kind)


def mp_layer(H, A, Wself, Wneigh, b, kind="sum", act=np.tanh, mlp=None):
    """One message-passing layer: aggregate (13.10), then update (13.16)
    h_n <- f(Wself h_n + Wneigh z_n + b), written node by node (column-vector convention)."""
    Z = aggregate(H, A, kind, mlp)
    out = np.zeros((len(A), Wself.shape[0]))
    for n in range(len(A)):
        out[n] = act(Wself @ H[n] + Wneigh @ Z[n] + b)
    return out


def mp_layer_matrix(H, A, Wself, Wneigh, b, act=np.tanh):
    """The same layer (sum aggregation) in matrix form, Exercise 13.6: rows of
    f(A H Wneigh^T + H Wself^T + 1_N b^T). (The book writes 1_D; the ones vector has N entries.)"""
    N = len(A)
    return act(A @ H @ Wneigh.T + H @ Wself.T + np.ones((N, 1)) @ b[None, :])


def readout(H, kind="sum"):
    """Graph-level pooling (13.23): sum, mean or element-wise max over the nodes."""
    return {"sum": H.sum(0), "mean": H.mean(0), "max": H.max(0)}[kind]


def edge_probabilities(H):
    """p(n, m) = sigma(h_n^T h_m) (13.22) for every pair, as a matrix."""
    return common.sigmoid(H @ H.T)


def mlp_apply(X, layers, act=np.tanh):
    """A small MLP acting on the rows of X; layers = [(W, b), ...] with W of shape (out, in)."""
    for i, (W, b) in enumerate(layers):
        X = X @ W.T + b
        if i < len(layers) - 1:
            X = act(X)
    return X


def random_mlp(sizes, rng, scale=1.0):
    return [(rng.normal(size=(o, i)) * scale / math.sqrt(i), rng.normal(size=o) * 0.1) for i, o in zip(sizes[:-1], sizes[1:])]


def flat_adjacency_net(A, layers):
    """A fully connected network applied to vec(A) (columns stacked): not permutation invariant."""
    return mlp_apply(A.T.reshape(1, -1), layers)[0]


# ================================================================ expressivity
def wl_colours(A, rounds=3):
    """Colour refinement (1-dimensional Weisfeiler-Lehman test) from a constant colouring: the
    histogram of colours after each round. Message passing with any aggregation can separate two
    graphs at most when these histograms differ (Xu et al. 2019; Morris et al. 2019)."""
    N = len(A)
    col = [0] * N
    hist = []
    for _ in range(rounds):
        sig = [(col[n], tuple(sorted(col[m] for m in np.nonzero(A[n])[0]))) for n in range(N)]
        table = {s: i for i, s in enumerate(sorted(set(sig)))}
        col = [table[s] for s in sig]
        hist.append(sorted(sig))
    return hist


# =========================================================================== the node classifier (Section 13.2.5)
def gcn_init(dims, seed):
    """Weights of the demo's GCN: for each layer l a matrix W_l (d_l x d_{l+1}, row-major) filled with
    JSRandom normals times sqrt(2/(d_l + d_{l+1})) (Glorot), then zero biases."""
    rng = JSRandom(seed)
    Ws, bs = [], []
    for din, dout in zip(dims[:-1], dims[1:]):
        s = math.sqrt(2.0 / (din + dout))
        Ws.append(np.array([[rng.norm() * s for _ in range(dout)] for _ in range(din)]))
        bs.append(np.zeros(dout))
    return Ws, bs


def gcn_forward(Ahat, X, Ws, bs, residual=False):
    """Forward pass: S_l = Ahat H_l, Z_l = S_l W_l + b_l, H_{l+1} = tanh(Z_l) (+ H_l when residual and
    the widths agree); the last Z is the matrix of logits. Returns (logits, cache)."""
    H = X
    cache = []
    L = len(Ws)
    for l in range(L):
        S = Ahat @ H
        Z = S @ Ws[l] + bs[l]
        if l < L - 1:
            T = np.tanh(Z)
            res = residual and l > 0 and H.shape[1] == T.shape[1]
            Hn = T + H if res else T
            cache.append((H, S, T, res))
            H = Hn
        else:
            cache.append((H, S, None, False))
            return Z, cache
    raise RuntimeError


def softmax_rows(Z):
    Z = Z - Z.max(1, keepdims=True)
    E = np.exp(Z)
    return E / E.sum(1, keepdims=True)


def gcn_loss(Z, T, mask, Ws, wd):
    """Mean cross-entropy over the labelled nodes, -sum t ln y / n_train, plus (wd/2) sum ||W||^2."""
    Y = softmax_rows(Z)
    idx = np.nonzero(mask)[0]
    ce = -np.sum(T[idx] * np.log(Y[idx])) / len(idx)
    return ce + 0.5 * wd * sum(np.sum(W * W) for W in Ws), Y


def gcn_backward(Ahat, Z, T, mask, Ws, cache, wd):
    """Gradients of gcn_loss with respect to every W_l and b_l (matrix-form backpropagation; the
    residual connection H_{l+1} = tanh(Z_l) + H_l passes the gradient of H_{l+1} straight to H_l)."""
    Y = softmax_rows(Z)
    n = mask.sum()
    G = (Y - T) * mask[:, None] / n
    gW = [None] * len(Ws)
    gb = [None] * len(Ws)
    extra = None                                           # residual gradient arriving at H_l
    for l in range(len(Ws) - 1, -1, -1):
        Hin, S, _, _ = cache[l]
        gW[l] = S.T @ G + wd * Ws[l]
        gb[l] = G.sum(0)
        if l == 0:
            break
        dH = Ahat.T @ (G @ Ws[l].T)
        if extra is not None:
            dH = dH + extra
        _, _, Tprev, res = cache[l - 1]
        G = dH * (1 - Tprev ** 2)
        extra = dH if res else None
    return gW, gb


def gcn_train(Ahat, X, labels, train_idx, dims, seed, steps, lr=0.05, wd=5e-4, residual=False,
              b1=0.9, b2=0.999, eps=1e-8):
    """Full-batch Adam on gcn_loss, exactly as gcn-node-classification-demo.html does it.
    Returns dict(losses, acc (on the unlabelled nodes), Ws, bs, Y)."""
    N = len(X)
    C = dims[-1]
    T = np.zeros((N, C))
    T[np.arange(N), labels] = 1.0
    mask = np.zeros(N)
    mask[list(train_idx)] = 1.0
    Ws, bs = gcn_init(dims, seed)
    mW = [np.zeros_like(W) for W in Ws]
    vW = [np.zeros_like(W) for W in Ws]
    mb = [np.zeros_like(b) for b in bs]
    vb = [np.zeros_like(b) for b in bs]
    losses, accs = [], []
    test = mask == 0
    for t in range(1, steps + 1):
        Z, cache = gcn_forward(Ahat, X, Ws, bs, residual)
        loss, Y = gcn_loss(Z, T, mask, Ws, wd)
        losses.append(loss)
        accs.append(float(np.mean(Y[test].argmax(1) == labels[test])))
        gW, gb = gcn_backward(Ahat, Z, T, mask, Ws, cache, wd)
        c1, c2 = 1 - b1 ** t, 1 - b2 ** t
        for l in range(len(Ws)):
            mW[l] = b1 * mW[l] + (1 - b1) * gW[l]
            vW[l] = b2 * vW[l] + (1 - b2) * gW[l] ** 2
            Ws[l] = Ws[l] - lr * (mW[l] / c1) / (np.sqrt(vW[l] / c2) + eps)
            mb[l] = b1 * mb[l] + (1 - b1) * gb[l]
            vb[l] = b2 * vb[l] + (1 - b2) * gb[l] ** 2
            bs[l] = bs[l] - lr * (mb[l] / c1) / (np.sqrt(vb[l] / c2) + eps)
    Z, cache = gcn_forward(Ahat, X, Ws, bs, residual)
    loss, Y = gcn_loss(Z, T, mask, Ws, wd)
    H = cache[-1][0]
    return {"losses": np.array(losses), "acc": np.array(accs), "final_loss": loss, "Ws": Ws, "bs": bs, "Y": Y,
            "hidden": H, "final_acc": float(np.mean(Y[test].argmax(1) == labels[test]))}


def gcn_features(kind, N, seed):
    """Node features of the classifier demo: 'onehot' (the identity), 'constant' (a column of ones) or
    'random' (N x 8 JSRandom normals from seed + 500, row-major)."""
    if kind == "onehot":
        return np.eye(N)
    if kind == "constant":
        return np.ones((N, 1))
    rng = JSRandom(seed + 500)
    return np.array([[rng.norm() for _ in range(8)] for _ in range(N)])


def karate_demo_run(model="gcn", L=2, width=8, feat="onehot", lr=0.05, seed=1, train=(0, 33), steps=200):
    """One run of gcn-node-classification-demo.html with the page's settings."""
    A, club = karate()
    X = gcn_features(feat, 34, seed)
    dims = [X.shape[1]] + [width] * (L - 1) + [2]
    Ahat = np.eye(34) if model == "mlp" else prop_matrix(A, "gcn")
    return gcn_train(Ahat, X, club, list(train), dims, seed, steps, lr=lr, wd=5e-4, residual=(model == "res"))


# =========================================================================== Section 13.3
def attention_bilinear(H, A, W):
    """Attention coefficients (13.27): A_nm = softmax over m in N(n) of h_n^T W h_m; zero off the graph."""
    S = H @ W @ H.T
    out = np.zeros_like(S)
    for n in range(len(A)):
        nb = np.nonzero(A[n])[0]
        if len(nb):
            s = S[n, nb] - S[n, nb].max()
            e = np.exp(s)
            out[n, nb] = e / e.sum()
    return out


def attention_mlp(H, A, layers, symmetric=True):
    """Attention coefficients (13.28) from an MLP score of the pair (h_n, h_m). With symmetric=True the
    score is MLP(h_n, h_m) + MLP(h_m, h_n), which is unchanged when the two inputs are exchanged."""
    N = len(A)
    out = np.zeros((N, N))
    for n in range(N):
        nb = np.nonzero(A[n])[0]
        if not len(nb):
            continue
        pair = np.hstack([np.repeat(H[n][None], len(nb), 0), H[nb]])
        s = mlp_apply(pair, layers)[:, 0]
        if symmetric:
            s = s + mlp_apply(np.hstack([H[nb], np.repeat(H[n][None], len(nb), 0)]), layers)[:, 0]
        e = np.exp(s - s.max())
        out[n, nb] = e / e.sum()
    return out


def self_attention(X, Wq, Wk, Wv):
    """Single-head transformer self-attention softmax(Q K^T / sqrt(d_k)) V (Section 12.1 of the book)."""
    Q, K, V = X @ Wq, X @ Wk, X @ Wv
    return softmax_rows(Q @ K.T / math.sqrt(Wk.shape[1])) @ V


def general_gnn_layer(E, H, g, A, fe, fh, fg):
    """One layer of (13.32)-(13.35) with sum aggregation. E is an (N, N, De) array of edge embeddings
    (used only where A = 1), H the (N, Dh) node embeddings and g the graph embedding; fe, fh, fg are
    functions acting on concatenated vectors."""
    N = len(A)
    En = np.zeros((N, N, fe(np.zeros(E.shape[2] + 2 * H.shape[1] + len(g))).shape[0]))
    for n in range(N):
        for m in range(N):
            if A[n, m]:
                En[n, m] = fe(np.concatenate([E[n, m], H[n], H[m], g]))
    Z = (En * A[:, :, None]).sum(1)
    Hn = np.array([fh(np.concatenate([H[n], Z[n], g])) for n in range(N)])
    e_sum = (En * A[:, :, None]).sum((0, 1))
    gn = fg(np.concatenate([g, Hn.sum(0), e_sum]))
    return En, Hn, gn


def egnn_layer(h, r, A, layers_e, layers_h, layers_phi, C=None):
    """The E(n)-equivariant layer (13.38)-(13.41) of Satorras, Hoogeboom and Welling (2021):
    e_nm = MLP_e(h_n, h_m, |r_n - r_m|^2), r_n <- r_n + C sum_m (r_n - r_m) phi(e_nm),
    z_n = sum_m e_nm, h_n <- MLP_h(h_n, z_n). Edge embeddings are recomputed (no e^(l) input)."""
    N = len(A)
    De = layers_e[-1][0].shape[0]
    E = np.zeros((N, N, De))
    r_new = r.copy()
    Z = np.zeros((N, De))
    for n in range(N):
        nb = np.nonzero(A[n])[0]
        cn = C if C is not None else (1.0 / len(nb) if len(nb) else 0.0)
        for m in nb:
            d2 = np.sum((r[n] - r[m]) ** 2)
            E[n, m] = mlp_apply(np.concatenate([h[n], h[m], [d2]])[None], layers_e)[0]
            r_new[n] = r_new[n] + cn * (r[n] - r[m]) * mlp_apply(E[n, m][None], layers_phi)[0, 0]
            Z[n] += E[n, m]
    h_new = mlp_apply(np.hstack([h, Z]), layers_h)
    return h_new, r_new


# ================================================================ over-smoothing
def dirichlet_energy(H, A):
    """E(H) = trace(H^T (I - Ahat) H) with Ahat the GCN matrix of A (self-loops included)
    = (1/2) sum_{n,m} A~_nm |h_n/sqrt(d~_n) - h_m/sqrt(d~_m)|^2."""
    L = np.eye(len(A)) - prop_matrix(A, "gcn")
    return float(np.trace(H.T @ L @ H))


def smoothing_rate(A, kind="gcn"):
    """rho = the largest |eigenvalue| other than the leading eigenvalue 1 (connected graph)."""
    if kind == "rw":   # similar to the gcn matrix
        kind = "gcn"
    M = prop_matrix(A, kind)
    lam = np.sort(np.linalg.eigvalsh((M + M.T) / 2))
    return float(max(abs(lam[0]), abs(lam[-2])))


def propagate(X, A, op="gcn", k=10, alpha=0.0, book_residual=False):
    """The over-smoothing demo's iteration, k times:
    H <- (1 - alpha) M H + alpha X  (alpha = 0: plain propagation; alpha > 0: an 'initial residual'),
    with M one of 'gcn', 'rw', 'kipf' (no self-loops) or 'sum' (A + I divided by its largest eigenvalue).
    book_residual=True uses H <- (H + M H)/2 instead of M H, the linear part of (13.36) rescaled.
    Returns the list [H_0, ..., H_k]. Written with explicit loops so that the page matches it."""
    if op == "sum":
        M = prop_matrix(A, "self")
        M = M / np.max(np.linalg.eigvalsh(M))
    else:
        M = prop_matrix(A, op)
    out = [X.copy()]
    H = X.copy()
    for _ in range(k):
        MH = M @ H
        if book_residual:
            MH = 0.5 * (H + MH)
        H = (1 - alpha) * MH + alpha * X
        out.append(H)
    return out


def smoothing_limit(X, A, op="gcn", alpha=0.0, book_residual=False):
    """The limit of propagate(): the projection onto the eigenvalue-1 eigenvector (alpha = 0) or the
    fixed point alpha (I - (1 - alpha) M)^-1 X (alpha > 0)."""
    if op == "sum":
        M = prop_matrix(A, "self")
        M = M / np.max(np.linalg.eigvalsh(M))
    else:
        M = prop_matrix(A, op)
    if book_residual:
        M = 0.5 * (np.eye(len(A)) + M)
    N = len(A)
    if alpha > 0:
        return alpha * np.linalg.solve(np.eye(N) - (1 - alpha) * M, X)
    w, V = np.linalg.eig(M)
    i = np.argmax(w.real)
    w_l, U = np.linalg.eig(M.T)
    j = np.argmax(w_l.real)
    v, u = V[:, i].real, U[:, j].real
    return np.outer(v, u) @ X / (u @ v)


def appnp_limit(X, A, alpha):
    return smoothing_limit(X, A, "gcn", alpha)


# =========================================================================== demo layers (equivariance demo)
def demo_weights(seed, D, Dout=2, F=8, N=None):
    """The equivariance demo's weights, drawn from JSRandom(seed) in this order: Wself (Dout x D),
    Wneigh (Dout x D), b (Dout), the bilinear attention matrix Wa (D x D), the per-position weights
    wpos (N) used by the 'position' layer, and the flattened-adjacency network: V1 (F x N^2), c1 (F),
    v2 (F). All entries are normals times 1/sqrt(fan-in) except the biases (times 0.1)."""
    rng = JSRandom(seed)
    def mat(r, c, s):
        return np.array([[rng.norm() * s for _ in range(c)] for _ in range(r)])
    P = {}
    P["Wself"] = mat(Dout, D, 1 / math.sqrt(D))
    P["Wneigh"] = mat(Dout, D, 1 / math.sqrt(D))
    P["b"] = np.array([rng.norm() * 0.1 for _ in range(Dout)])
    P["Wa"] = mat(D, D, 1 / math.sqrt(D))
    P["wpos"] = np.array([rng.norm() for _ in range(N)])
    P["V1"] = mat(F, N * N, 1 / math.sqrt(N * N) * 3)
    P["c1"] = np.array([rng.norm() * 0.1 for _ in range(F)])
    P["v2"] = np.array([rng.norm() / math.sqrt(F) for _ in range(F)])
    return P


def demo_features(seed, N, D):
    """Node features for the equivariance demo: N x D JSRandom normals (row-major), seed + 1000."""
    rng = JSRandom(seed + 1000)
    return np.array([[rng.norm() for _ in range(D)] for _ in range(N)])


def demo_layer(X, A, P, kind):
    """The layers of permutation-equivariance-demo.html. 'sum', 'mean', 'kipf', 'gcn', 'max' and 'att'
    aggregate the neighbours (13.12)-(13.14), the renormalised GCN matrix, max, bilinear attention
    (13.27); 'position' weights neighbour m by a weight wpos[m] tied to its index (like the filter
    weights w_j of (13.8)), which breaks equivariance. Update: tanh(Wself h_n + Wneigh z_n + b)."""
    N = len(A)
    if kind in ("sum", "mean", "kipf"):
        Z = prop_matrix(A, kind) @ X
    elif kind == "gcn":
        Z = prop_matrix(A, "gcn") @ X
    elif kind == "max":
        Z = aggregate(X, A, "max")
    elif kind == "att":
        Z = attention_bilinear(X, A, P["Wa"]) @ X
    elif kind == "position":
        Z = (A * P["wpos"][None, :]) @ X
    else:
        raise ValueError(kind)
    return np.tanh(X @ P["Wself"].T + Z @ P["Wneigh"].T + P["b"][None, :])


def demo_flat(A, P):
    """The flattened-adjacency network of the demo: v2 . tanh(V1 vec(A) + c1), vec stacking rows."""
    a = A.reshape(-1)
    return float(P["v2"] @ np.tanh(P["V1"] @ a + P["c1"]))


# =========================================================================== drawing helpers
NODE_FC = "#c9d3f2"
NODE_EC = "#3346a8"
RED_FC = "#f6b4b4"


def draw_graph(ax, pos, A, colours=None, labels=None, size=260, edge_colour="0.25", lw=1.1, ec=None,
               text_colour="black", fontsize=9, zorder=2, edgecolors_list=None):
    N = len(A)
    for n, m in edges_of(A):
        ax.plot([pos[n, 0], pos[m, 0]], [pos[n, 1], pos[m, 1]], color=edge_colour, lw=lw, zorder=1)
    fc = colours if colours is not None else [NODE_FC] * N
    ax.scatter(pos[:, 0], pos[:, 1], s=size, c=fc, edgecolors=edgecolors_list if edgecolors_list is not None else (ec or NODE_EC),
               linewidths=1.2, zorder=zorder)
    if labels is not None:
        for n in range(N):
            ax.text(pos[n, 0], pos[n, 1], labels[n], ha="center", va="center", fontsize=fontsize, color=text_colour,
                    zorder=zorder + 1, style="italic")
    ax.set_aspect("equal")
    ax.axis("off")


def draw_matrix(ax, M, labels, title=None):
    N = len(M)
    for i in range(N):
        for j in range(N):
            ax.add_patch(Rectangle((j, N - 1 - i), 1, 1, fc="#1f3fd6" if M[i, j] else "#fff8d8", ec="0.2", lw=0.8))
    ax.set_xlim(0, N)
    ax.set_ylim(0, N)
    ax.set_aspect("equal")
    ax.set_xticks(np.arange(N) + 0.5)
    ax.set_xticklabels(labels, style="italic")
    ax.set_yticks(np.arange(N) + 0.5)
    ax.set_yticklabels(labels[::-1], style="italic")
    ax.xaxis.tick_top()
    ax.tick_params(length=0)
    for s in ax.spines.values():
        s.set_visible(False)
    if title:
        ax.set_xlabel(title)


# =========================================================================== data for the demos
def demo_graphs():
    """The graphs and features used by the three demos (also written to ../data/ch13-graphs.json)."""
    out = {}
    out["fig132"] = {"N": 5, "edges": FIG132_EDGES, "names": list(FIG132_NODES), "pos": FIG132_POS.round(4).tolist()}
    ex_pos = np.array([[0.20, 0.80], [0.55, 0.55], [0.20, 0.25], [0.75, 0.15], [0.80, 0.85]])
    out["ex133"] = {"N": 5, "edges": edges_of(EX133_A), "names": list("ABCDE"), "pos": ex_pos.tolist()}
    Ar, posr = random_geometric(8, 0.42, 5)
    out["rand8"] = {"N": 8, "edges": edges_of(Ar), "names": [str(i + 1) for i in range(8)], "pos": posr.round(4).tolist()}
    Ak, club = karate()
    pk = spring_layout(Ak, seed=3)
    rng = np.random.default_rng(13)
    feat_k = np.array([[1.0, 0.4] if c == 0 else [-1.0, -0.4] for c in club]) + 0.55 * rng.normal(size=(34, 2))
    out["karate"] = {"N": 34, "edges": KARATE_EDGES, "club": KARATE_CLUB, "names": [str(i) for i in range(34)],
                     "pos": pk.round(4).tolist(), "feat": feat_k.round(4).tolist()}
    As, ys, s_used = connected_sbm([20, 20], 0.25, 0.02, 21)
    ps = spring_layout(As, seed=1)
    rng = np.random.default_rng(14)
    feat_s = np.array([[1.0, 0.6] if c == 0 else [-0.8, 0.9] for c in ys]) + 0.5 * rng.normal(size=(40, 2))
    out["sbm2"] = {"N": 40, "edges": edges_of(As), "club": ys.tolist(), "seed": s_used, "names": [str(i) for i in range(40)],
                   "pos": ps.round(4).tolist(), "feat": feat_s.round(4).tolist()}
    Ar16 = ring(16)
    th = 2 * np.pi * np.arange(16) / 16
    pr = 0.5 + 0.42 * np.stack([np.cos(th), np.sin(th)], 1)
    feat_r = np.stack([np.cos(th) + 0.3 * (np.arange(16) % 2), np.sin(2 * th) + 0.6 * (np.arange(16) % 2 - 0.5)], 1)
    out["ring16"] = {"N": 16, "edges": edges_of(Ar16), "club": (np.arange(16) % 2).tolist(), "names": [str(i) for i in range(16)],
                     "pos": pr.round(4).tolist(), "feat": feat_r.round(4).tolist()}
    return out


def graph_from(d):
    return adjacency(d["N"], [tuple(e) for e in d["edges"]])


def write_demo_data(out_dir=None):
    """Writes ../data/ch13-graphs.json for the browser demos."""
    os.makedirs(DATA_OUT, exist_ok=True)
    path = os.path.join(DATA_OUT, "ch13-graphs.json")
    with open(path, "w") as f:
        json.dump(demo_graphs(), f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()), "(%d bytes)" % os.path.getsize(path))
    return path


# =========================================================================== figures
def fig_13_2(out_dir=None):
    """A five-node graph and its adjacency matrix in two node orders (A and P A P^T)."""
    A = adjacency(5, FIG132_EDGES)
    P = perm_matrix(FIG132_PERM)
    At = P @ A @ P.T
    names = list(FIG132_NODES)
    new = [names[i] for i in FIG132_PERM]
    fig = plt.figure(figsize=(9.6, 3.2))
    ax0 = fig.add_axes([0.0, 0.08, 0.30, 0.82])
    draw_graph(ax0, FIG132_POS, A, labels=names, size=520, fontsize=11)
    ax0.set_xlim(-0.08, 0.95)
    ax0.set_ylim(0.08, 0.95)
    ax0.text(0.45, 0.0, "(a)", transform=ax0.transAxes, ha="center")
    ax1 = fig.add_axes([0.36, 0.08, 0.28, 0.75])
    draw_matrix(ax1, A, names)
    ax1.text(0.5, -0.12, r"(b) $\mathbf{A}$", transform=ax1.transAxes, ha="center")
    ax2 = fig.add_axes([0.70, 0.08, 0.28, 0.75])
    draw_matrix(ax2, At, new)
    ax2.text(0.5, -0.12, r"(c) $\mathbf{P}\mathbf{A}\mathbf{P}^{\mathrm{T}}$", transform=ax2.transAxes, ha="center")
    return savefig(fig, CH, "fig13-2", out_dir)


def _test_image(n=24):
    """A small synthetic grey-level image: a disc, a bar and a gradient."""
    y, x = np.mgrid[0:n, 0:n] / (n - 1)
    img = 0.3 * x + ((x - 0.35) ** 2 + (y - 0.4) ** 2 < 0.04) * 1.0 + ((np.abs(y - 0.75) < 0.06) & (x > 0.5)) * 0.8
    return img


def grid_graph(n, diagonal=True):
    """The graph of an n x n image: pixels are nodes, edges join horizontal, vertical and (if diagonal)
    diagonal neighbours; node index = row * n + column."""
    N = n * n
    A = np.zeros((N, N))
    for i in range(n):
        for j in range(n):
            for di in (-1, 0, 1):
                for dj in (-1, 0, 1):
                    if (di, dj) == (0, 0) or (not diagonal and di and dj):
                        continue
                    a, b = i + di, j + dj
                    if 0 <= a < n and 0 <= b < n:
                        A[i * n + j, a * n + b] = 1.0
    return A


def conv2d_same_zero(img, K):
    """Plain 3x3 correlation with zero padding (the filter of (13.8) applied at every pixel)."""
    n = img.shape[0]
    pad = np.pad(img, 1)
    out = np.zeros_like(img)
    for i in range(n):
        for j in range(n):
            out[i, j] = np.sum(pad[i:i + 3, j:j + 3] * K)
    return out


def fig_13_3(out_dir=None):
    """An image as a graph: the shared-weight filter (13.9) by message passing equals a convolution."""
    n = 24
    img = _test_image(n)
    A = grid_graph(n)
    w_self, w_neigh, bias = 1.0, -0.125, 0.0
    h = img.reshape(-1)
    mp = (w_neigh * (A @ h) + w_self * h + bias).reshape(n, n)       # (13.9) without the nonlinearity
    K = np.full((3, 3), w_neigh)
    K[1, 1] = w_self
    cv = conv2d_same_zero(img, K)
    fig, axes = plt.subplots(1, 4, figsize=(11.6, 3.0), gridspec_kw={"width_ratios": [1.05, 1, 1, 1]})
    ax = axes[0]
    m = 5
    pos = np.array([[j, m - 1 - i] for i in range(m) for j in range(m)], float)
    Ag = grid_graph(m)
    centre = 2 * m + 2
    nb = np.nonzero(Ag[centre])[0]
    for i in range(m):
        for j in range(m):
            ax.add_patch(Rectangle((j - 0.5, m - 1 - i - 0.5), 1, 1, fc="#fff8d8", ec="0.6", lw=0.6))
    ax.add_patch(Rectangle((0.5, 0.5), 3, 3, fc="none", ec=common.RED, lw=2.0))
    for k in nb:
        ax.add_patch(FancyArrowPatch(pos[k], pos[centre], arrowstyle="-|>", mutation_scale=9, color=common.BLUE,
                                     shrinkA=7, shrinkB=9, lw=1.1))
    cols = [RED_FC if k == centre else (NODE_FC if k in nb else "white") for k in range(m * m)]
    ax.scatter(pos[:, 0], pos[:, 1], s=95, c=cols, edgecolors=NODE_EC, linewidths=1.0, zorder=3)
    ax.text(pos[centre, 0], pos[centre, 1], r"$i$", ha="center", va="center", fontsize=9, zorder=4)
    ax.set_xlim(-0.6, m - 0.4)
    ax.set_ylim(-0.6, m - 0.4)
    ax.set_aspect("equal")
    ax.axis("off")
    ax.set_title("(a) messages into pixel $i$\nfrom its 8 neighbours", fontsize=9.5)
    for ax, M, t in zip(axes[1:], (img, mp, cv), ("(b) input image $z^{(l)}$", "(c) message passing (13.9)",
                                                     "(d) 3x3 convolution")):
        ax.imshow(M, cmap="gray", interpolation="nearest")
        ax.set_xticks([])
        ax.set_yticks([])
        ax.set_title(t, fontsize=9.5)
    axes[3].text(0.5, -0.1, "max |(c) - (d)| = %.0e" % np.abs(mp - cv).max(), transform=axes[3].transAxes,
                 ha="center", va="top", fontsize=9)
    return savefig(fig, CH, "fig13-3", out_dir)


def spaced_geometric(N, radius, min_dist, seed):
    """Random geometric graph whose points are at least min_dist apart (rejection sampling), re-drawn
    until connected. Returns (A, pos)."""
    s = seed
    while True:
        rng = np.random.default_rng(s)
        pts = []
        while len(pts) < N:
            p = rng.uniform(0.06, 0.94, size=2)
            if all(np.linalg.norm(p - q) >= min_dist for q in pts):
                pts.append(p)
        pos = np.array(pts)
        D = np.linalg.norm(pos[:, None] - pos[None], axis=2)
        A = ((D < radius) & (D > 0)).astype(float)
        if is_connected(A):
            return A, pos
        s += 1


def fig4_graph():
    A, pos = spaced_geometric(22, 0.30, 0.13, 40)
    d = [hop_distances(A, n) for n in range(len(A))]
    # pick a node whose 2-hop field is a moderate fraction of the graph
    ecc = [np.sum(di <= 2) for di in d]
    node = int(np.argsort(ecc)[len(ecc) // 2])
    return A, pos, node


def fig_13_4(out_dir=None):
    """The receptive field of one node grows with the number of message-passing layers."""
    A, pos, node = fig4_graph()
    fig, axes = plt.subplots(1, 3, figsize=(10.0, 3.6))
    for k, ax in enumerate(axes):
        L = 2 - k                 # layer 1 shows the 2-hop field, layer 3 the node itself
        field = set(receptive_field(A, node, L).tolist())
        cols = [RED_FC if n in field else NODE_FC for n in range(len(A))]
        ecs = [common.RED if n in field else NODE_EC for n in range(len(A))]
        ax.add_patch(Rectangle((-0.02, -0.02), 1.04, 1.04, fc="#fffbe6", ec="0.3", lw=0.9))
        draw_graph(ax, pos, A, colours=cols, size=90, edgecolors_list=ecs, lw=0.9)
        ax.set_xlim(-0.05, 1.05)
        ax.set_ylim(-0.05, 1.05)
        ax.set_title("layer %d: %d node%s in red" % (k + 1, len(field), "" if len(field) == 1 else "s"), fontsize=10)
    for k in range(2):
        fig.add_artist(FancyArrowPatch((0.315 + 0.333 * k, 0.94), (0.355 + 0.333 * k, 0.94), transform=fig.transFigure,
                                       arrowstyle="-|>", mutation_scale=14, lw=2, color="black"))
    return savefig(fig, CH, "fig13-4", out_dir)


def fig_13_ex3(out_dir=None):
    """The graph of Exercise 13.3, drawn from its adjacency matrix (13.42)."""
    pos = np.array([[0.20, 0.80], [0.55, 0.55], [0.20, 0.25], [0.75, 0.15], [0.80, 0.85]])
    fig, ax = plt.subplots(figsize=(3.2, 2.9))
    draw_graph(ax, pos, EX133_A, labels=list("ABCDE"), size=480, fontsize=11)
    ax.set_xlim(0.05, 0.95)
    ax.set_ylim(0.03, 0.97)
    return savefig(fig, CH, "fig13-ex3", out_dir)


def s1_data():
    """Outputs of an equivariant network and of a flattened-adjacency network for all 120 node orders."""
    A = adjacency(5, FIG132_EDGES)
    X = demo_features(7, 5, 2)
    P = demo_weights(7, 2, 2, 8, 5)
    Y0 = demo_layer(X, A, P, "sum")
    eq_err, inv_err, flat = [], [], []
    for pi in itertools.permutations(range(5)):
        Pm = perm_matrix(pi)
        Y = demo_layer(Pm @ X, Pm @ A @ Pm.T, P, "sum")
        eq_err.append(np.abs(Y - Pm @ Y0).max())
        inv_err.append(np.abs(readout(Y) - readout(Y0)).max())
        flat.append(demo_flat(Pm @ A @ Pm.T, P))
    return np.array(eq_err), np.array(inv_err), np.array(flat)


def fig_13_s1(out_dir=None):
    """All 120 node orders of the graph of Figure 13.2."""
    eq, inv, flat = s1_data()
    fig, axes = plt.subplots(1, 2, figsize=(9.4, 3.1))
    ax = axes[0]
    ax.semilogy(np.arange(120), np.maximum(eq, 1e-18), "o", ms=3, color=common.BLUE, label="node outputs: max |Y(PX, PAP$^T$) - PY(X, A)|")
    ax.semilogy(np.arange(120), np.maximum(inv, 1e-18), "s", ms=3, mfc="none", color=common.GREEN, label="sum readout: max |y(PX, PAP$^T$) - y(X, A)|")
    ax.set_ylim(1e-18, 1)
    ax.axhline(1e-16, color="0.6", lw=0.8, ls=":")
    ax.set_xlabel("node order (all 5! = 120 permutations)")
    ax.set_ylabel("difference (0 shown as 1e-18)")
    ax.legend(loc="upper right", fontsize=7.5, frameon=False)
    ax.set_title("(a) message passing: equivariant and invariant")
    ax = axes[1]
    vals = np.sort(flat)
    ax.plot(np.arange(120), vals, ".", color=common.RED, ms=4)
    ax.set_xlabel("node order (sorted by output)")
    ax.set_ylabel("network output on vec(PAP$^T$)")
    ax.set_title("(b) flattened adjacency: %d different outputs" % len(np.unique(np.round(flat, 12))))
    return savefig(fig, CH, "fig13-s1", out_dir)


def fig_13_s2(out_dir=None):
    """Spectra of the normalised Laplacian I - D^-1/2 A D^-1/2 and of the GCN matrix."""
    Ak, _ = karate()
    graphs = [("karate club", Ak), ("ring of 16 (bipartite)", ring(16)), ("two communities", graph_from(demo_graphs()["sbm2"]))]
    fig, axes = plt.subplots(1, 2, figsize=(9.6, 3.2))
    cols = [common.BLUE, common.RED, common.GREEN]
    for (name, A), c in zip(graphs, cols):
        lam = np.sort(np.linalg.eigvalsh(normalized_laplacian(A)))
        axes[0].plot(np.linspace(0, 1, len(lam)), lam, "o-", ms=2.5, lw=1, color=c, label=name)
        mu = np.sort(np.linalg.eigvalsh(prop_matrix(A, "gcn")))
        axes[1].plot(np.linspace(0, 1, len(mu)), mu, "o-", ms=2.5, lw=1, color=c, label=name)
    axes[0].axhline(0, color="0.5", lw=0.8, ls=":")
    axes[0].axhline(2, color="0.5", lw=0.8, ls=":")
    axes[0].set_ylim(-0.1, 2.1)
    axes[0].set_title(r"(a) eigenvalues of $\mathbf{I}-\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$: in [0, 2]")
    axes[1].axhline(1, color="0.5", lw=0.8, ls=":")
    axes[1].axhline(-1, color="0.5", lw=0.8, ls=":")
    axes[1].set_ylim(-1.1, 1.1)
    axes[1].set_title(r"(b) eigenvalues of $\tilde{\mathbf{D}}^{-1/2}(\mathbf{A}+\mathbf{I})\tilde{\mathbf{D}}^{-1/2}$: in (-1, 1]")
    for ax in axes:
        ax.set_xlabel("rank (scaled to [0, 1])")
    axes[0].legend(fontsize=8, frameon=False, loc="upper left")
    return savefig(fig, CH, "fig13-s2", out_dir)


def fig_13_s3(out_dir=None):
    """Over-smoothing on the karate club: features after k GCN propagations, and the decay rate."""
    G = demo_graphs()["karate"]
    A = graph_from(G)
    X = np.array(G["feat"])
    club = np.array(G["club"])
    Hs = propagate(X, A, "gcn", 64)
    rho = smoothing_rate(A)
    Hinf = smoothing_limit(X, A, "gcn")
    fig = plt.figure(figsize=(11.2, 3.3))
    ks = [0, 2, 8, 64]
    for i, k in enumerate(ks):
        ax = fig.add_axes([0.02 + 0.165 * i, 0.14, 0.15, 0.72])
        H = Hs[k]
        ax.scatter(H[:, 0], H[:, 1], s=14, c=[common.RED if c == 0 else common.BLUE for c in club], edgecolors="none")
        if k:
            ax.scatter(Hinf[:, 0], Hinf[:, 1], s=30, facecolors="none", edgecolors="0.4", lw=0.6)
        ax.set_xlim(-2.6, 2.6)
        ax.set_ylim(-2.2, 2.2)
        ax.set_xticks([])
        ax.set_yticks([])
        ax.set_title("$k$ = %d" % k)
    ax = fig.add_axes([0.72, 0.16, 0.27, 0.70])
    ks_all = np.arange(65)
    dist = np.array([np.linalg.norm(H - Hinf) for H in Hs]) / np.linalg.norm(X - Hinf)
    en = np.array([dirichlet_energy(H, A) for H in Hs]) / dirichlet_energy(X, A)
    ax.semilogy(ks_all, dist, color=common.BLUE, label=r"$\|\mathbf{H}_k-\mathbf{H}_\infty\|/\|\mathbf{H}_0-\mathbf{H}_\infty\|$")
    ax.semilogy(ks_all, en, color=common.GREEN, label="Dirichlet energy ratio")
    ax.semilogy(ks_all, rho ** ks_all, "--", color=common.RED, lw=1, label=r"bound $\rho^k$, $\rho$ = %.3f" % rho)
    ax.semilogy(ks_all, rho ** (2 * ks_all), ":", color=common.RED, lw=1.2, label=r"bound $\rho^{2k}$")
    ax.set_xlabel("number of propagations $k$")
    ax.set_ylim(1e-12, 2)
    ax.legend(fontsize=7, frameon=False, loc="lower left")
    return savefig(fig, CH, "fig13-s3", out_dir)


KARATE_TRAIN = [0, 33]


def karate_runs(steps=300):
    Ak, club = karate()
    X = np.eye(34)
    res = {}
    res["gcn"] = gcn_train(prop_matrix(Ak, "gcn"), X, club, KARATE_TRAIN, [34, 8, 2], seed=1, steps=steps, lr=0.05, wd=5e-4)
    res["mlp"] = gcn_train(np.eye(34), X, club, KARATE_TRAIN, [34, 8, 2], seed=1, steps=steps, lr=0.05, wd=5e-4)
    return res


def fig_13_s4(out_dir=None):
    """A two-layer GCN on the karate club, trained from one label per faction."""
    G = demo_graphs()["karate"]
    Ak, club = karate()
    pos = np.array(G["pos"])
    res = karate_runs()
    fig = plt.figure(figsize=(11.0, 3.6))
    for i, key in enumerate(("gcn", "mlp")):
        ax = fig.add_axes([0.0 + 0.30 * i, 0.04, 0.29, 0.82])
        p = res[key]["Y"][:, 1]
        cmap = plt.get_cmap("coolwarm")
        ec = ["black" if n in KARATE_TRAIN else (common.RED if (p[n] > 0.5) != club[n] else "0.4") for n in range(34)]
        draw_graph(ax, pos, Ak, colours=[cmap(v) for v in p], size=[150 if n in KARATE_TRAIN else 80 for n in range(34)],
                   edgecolors_list=ec, lw=0.5, edge_colour="0.65")
        ax.set_title("(%s) %s: %.0f%% of the 32 unlabelled nodes" % ("ab"[i], "GCN" if key == "gcn" else "no edges (A = I)",
                                                                   100 * res[key]["final_acc"]), fontsize=9.5)
    ax = fig.add_axes([0.66, 0.16, 0.32, 0.68])
    for key, c, lab in (("gcn", common.BLUE, "GCN"), ("mlp", common.ORANGE, "no edges")):
        ax.plot(res[key]["acc"], color=c, label=lab + ": accuracy (unlabelled)")
        ax.plot(res[key]["losses"], color=c, ls="--", lw=1, label=lab + ": training loss")
    ax.set_xlabel("Adam step")
    ax.set_ylim(0, 1.05)
    ax.legend(fontsize=7.5, frameon=False, loc="upper right", bbox_to_anchor=(1.0, 0.9))
    ax.set_title("(c) learning curves")
    return savefig(fig, CH, "fig13-s4", out_dir)


# ================================================================ depth experiment (torch)
def depth_data(seed=0):
    rng = np.random.default_rng(seed)
    A, y, _ = connected_sbm([100, 100, 100], 0.05, 0.01, 100 + seed)
    D = 8
    means = rng.normal(size=(3, D)) * 0.6
    X = means[y] + rng.normal(size=(300, D))
    train = np.concatenate([rng.choice(np.nonzero(y == c)[0], 10, replace=False) for c in range(3)])
    return A, X, y, train


def depth_run(L, variant, seed, steps=300):
    """Train an L-layer GCN (input encoder, L propagation layers with ReLU, linear readout) on the
    stochastic block model of depth_data(seed). variant: 'plain', 'residual' (13.36) or 'jk' (13.37)."""
    torch = common.torch_setup(seed, threads=1)
    A, X, y, train = depth_data(seed)
    Ah = torch.tensor(prop_matrix(A, "gcn"), dtype=torch.float32)
    Xt = torch.tensor(X, dtype=torch.float32)
    yt = torch.tensor(y)
    Hd = 16
    enc = torch.nn.Linear(X.shape[1], Hd)
    lays = torch.nn.ModuleList([torch.nn.Linear(Hd, Hd) for _ in range(L)])
    out = torch.nn.Linear(Hd * (L if variant == "jk" else 1), 3)
    params = list(enc.parameters()) + list(lays.parameters()) + list(out.parameters())
    opt = torch.optim.Adam(params, lr=0.01, weight_decay=5e-4)
    test = np.setdiff1d(np.arange(len(y)), train)

    def forward():
        H = enc(Xt)
        hs = []
        for lay in lays:
            U = torch.relu(lay(Ah @ H))
            H = H + U if variant == "residual" else U
            hs.append(H)
        return out(torch.cat(hs, 1) if variant == "jk" else H), H

    for _ in range(steps):
        opt.zero_grad()
        logits, _ = forward()
        loss = torch.nn.functional.cross_entropy(logits[train], yt[train])
        loss.backward()
        opt.step()
    with torch.no_grad():
        logits, H = forward()
        acc = float((logits.argmax(1).numpy()[test] == y[test]).mean())
        tr = float((logits.argmax(1).numpy()[train] == y[train]).mean())
    return acc, tr


DEPTHS = [1, 2, 4, 8, 16, 32]


def depth_results():
    path = os.path.join(CACHE_DIR, "ch13_depth.json")
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    res = {}
    for variant in ("plain", "residual", "jk"):
        res[variant] = [[depth_run(L, variant, s) for s in range(3)] for L in DEPTHS]
    os.makedirs(CACHE_DIR, exist_ok=True)
    with open(path, "w") as f:
        json.dump(res, f)
    return res


def fig_13_s5(out_dir=None):
    """Test accuracy against depth: plain GCN, residual connections (13.36), jumping knowledge (13.37)."""
    res = depth_results()
    fig, axes = plt.subplots(1, 2, figsize=(9.4, 3.2))
    for variant, c, lab in (("plain", common.RED, "plain GCN"), ("residual", common.BLUE, "residual (13.36)"),
                            ("jk", common.GREEN, "concatenate all layers (13.37)")):
        R = np.array(res[variant])           # depth x seed x (test, train)
        axes[0].errorbar(DEPTHS, R[:, :, 0].mean(1), yerr=R[:, :, 0].std(1), marker="o", ms=4, color=c, label=lab, capsize=2)
        axes[1].plot(DEPTHS, R[:, :, 1].mean(1), marker="o", ms=4, color=c, label=lab)
    for ax, t in zip(axes, ("(a) accuracy on the 270 unlabelled nodes", "(b) accuracy on the 30 labelled nodes")):
        ax.set_xscale("log", base=2)
        ax.set_xticks(DEPTHS)
        ax.set_xticklabels([str(d) for d in DEPTHS])
        ax.set_xlabel("number of message-passing layers $L$")
        ax.set_ylim(0.2, 1.03)
        ax.axhline(1 / 3, color="0.6", ls=":", lw=0.8)
        ax.set_title(t)
    axes[0].legend(fontsize=8, frameon=False, loc="lower left")
    return savefig(fig, CH, "fig13-s5", out_dir)


def two_triangles_hexagon():
    A1 = adjacency(6, [(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3)])
    A2 = ring(6)
    return A1, A2


def fig_13_s6(out_dir=None):
    """Two graphs that message passing cannot tell apart, and three multisets that mean or max cannot."""
    A1, A2 = two_triangles_hexagon()
    X = np.ones((6, 1))
    fig = plt.figure(figsize=(10.4, 3.0))
    th = 2 * np.pi * np.arange(6) / 6
    pos2 = 0.5 + 0.38 * np.stack([np.cos(th), np.sin(th)], 1)
    pos1 = np.array([[0.1, 0.25], [0.45, 0.25], [0.27, 0.6], [0.55, 0.45], [0.9, 0.45], [0.72, 0.8]])
    for i, (A, pos, t) in enumerate(((A1, pos1, "(a) two triangles"), (A2, pos2, "(b) a hexagon"))):
        ax = fig.add_axes([0.0 + 0.2 * i, 0.08, 0.19, 0.76])
        draw_graph(ax, pos, A, size=110)
        ax.set_xlim(0, 1)
        ax.set_ylim(0.05, 0.95)
        ax.set_title(t, fontsize=10)
    # embeddings of the two graphs after 1-3 sum-aggregation layers with shared random weights
    ax = fig.add_axes([0.44, 0.18, 0.22, 0.62])
    rng = np.random.default_rng(5)
    Ws = [(rng.normal(size=(4, 1 if l == 0 else 4)), rng.normal(size=(4, 1 if l == 0 else 4)), rng.normal(size=4) * 0.3) for l in range(3)]
    for A, c, mk, lab in ((A1, common.BLUE, "o", "two triangles"), (A2, common.RED, "x", "hexagon")):
        H = X
        r = []
        for Wself, Wneigh, b in Ws:
            H = mp_layer(H, A, Wself, Wneigh, b, "sum")
            r.append(readout(H)[0])
        ax.plot([1, 2, 3], r, marker=mk, color=c, ms=8 if mk == "x" else 6, mfc="none", ls="none", label=lab)
    ax.set_xticks([1, 2, 3])
    ax.set_xlabel("layer")
    ax.set_ylabel("first entry of the sum readout")
    ax.legend(fontsize=8, frameon=False)
    ax.set_title("(c) identical readouts", fontsize=10)
    # multisets
    ax = fig.add_axes([0.73, 0.18, 0.26, 0.62])
    sets = [[1.0], [1.0, 1.0], [0.0, 1.0, 1.0, 0.0]]
    labs = ["{1}", "{1, 1}", "{0, 0, 1, 1}"]
    for j, (agg, c) in enumerate((("sum", common.BLUE), ("mean", common.GREEN), ("max", common.ORANGE))):
        vals = [{"sum": np.sum, "mean": np.mean, "max": np.max}[agg](s) for s in sets]
        ax.bar(np.arange(3) + (j - 1) * 0.26, vals, width=0.25, color=c, label=agg)
    ax.set_xticks(np.arange(3))
    ax.set_xticklabels(labs)
    ax.set_title("(d) aggregating three multisets", fontsize=10)
    ax.legend(fontsize=8, frameon=False, loc="upper left")
    return savefig(fig, CH, "fig13-s6", out_dir)


def egnn_example(seed=4):
    rng = np.random.default_rng(seed)
    N = 9
    r = rng.normal(size=(N, 2)) * 1.1
    D = np.linalg.norm(r[:, None] - r[None], axis=2)
    A = ((D < 1.6) & (D > 0)).astype(float)
    h = rng.normal(size=(N, 3))
    Le = random_mlp([3 + 3 + 1, 8, 4], rng)
    Lh = random_mlp([3 + 4, 8, 3], rng)
    Lp = random_mlp([4, 8, 1], rng, scale=0.5)
    return h, r, A, Le, Lh, Lp


def egnn_stack(h, r, A, Le, Lh, Lp, layers=3):
    for _ in range(layers):
        h, r = egnn_layer(h, r, A, Le, Lh, Lp)
    return h, r


def fig_13_s7(out_dir=None):
    """E(n) equivariance of the layer (13.38)-(13.41)."""
    h, r, A, Le, Lh, Lp = egnn_example()
    th = 2.0
    R = np.array([[math.cos(th), -math.sin(th)], [math.sin(th), math.cos(th)]]) @ np.diag([1.0, -1.0])   # rotation x reflection
    c = np.array([3.5, 1.0])
    h1, r1 = egnn_stack(h, r, A, Le, Lh, Lp)
    h2, r2 = egnn_stack(h, r @ R.T + c, A, Le, Lh, Lp)
    fig, axes = plt.subplots(1, 3, figsize=(11.4, 3.6), gridspec_kw={"width_ratios": [1, 1, 0.8]})
    for ax, (rin, rout, t) in zip(axes[:2], ((r, r1, "(a) input and output positions"),
                                             (r @ R.T + c, r2, "(b) the same, input moved by R r + c"))):
        for n, m in edges_of(A):
            ax.plot(rin[[n, m], 0], rin[[n, m], 1], color="0.8", lw=0.8)
        ax.scatter(rin[:, 0], rin[:, 1], s=30, color=common.BLUE, label="input $r$", zorder=3)
        ax.scatter(rout[:, 0], rout[:, 1], s=30, color=common.RED, marker="^", label="after 3 layers", zorder=3)
        for n in range(len(r)):
            ax.annotate("", rout[n], rin[n], arrowprops=dict(arrowstyle="->", color="0.5", lw=0.7))
        both = np.vstack([rin, rout])
        lo, hi = both.min(0) - 0.35, both.max(0) + 0.35
        lo[1] -= 0.9                      # room for the legend
        ax.set_xlim(lo[0], hi[0])
        ax.set_ylim(lo[1], hi[1])
        ax.set_aspect("equal", adjustable="box")
        ax.set_title(t, fontsize=10)
        ax.legend(fontsize=7.5, frameon=False, loc="lower right")
    ax = axes[2]
    err_r = np.abs(r1 @ R.T + c - r2).max()
    err_h = np.abs(h1 - h2).max()
    ax.bar([0, 1], [max(err_r, 1e-18), max(err_h, 1e-18)], color=[common.RED, common.GREEN])
    ax.set_yscale("log")
    ax.set_ylim(1e-18, 1)
    ax.set_xticks([0, 1])
    ax.set_xticklabels([r"$|R\,r^{(3)}+c-\tilde r^{(3)}|$", r"$|h^{(3)}-\tilde h^{(3)}|$"])
    ax.set_title("(c) largest differences", fontsize=10)
    return savefig(fig, CH, "fig13-s7", out_dir)


def fig_data(out_dir=None):
    """Write the demos' JSON data file."""
    return write_demo_data(out_dir)


FIGURES = {"13.2": fig_13_2, "13.3": fig_13_3, "13.4": fig_13_4,
           "13.S1": fig_13_s1, "13.S2": fig_13_s2, "13.S3": fig_13_s3, "13.S4": fig_13_s4, "13.S5": fig_13_s5,
           "13.S6": fig_13_s6, "13.S7": fig_13_s7, "13.ex3": fig_13_ex3, "data": fig_data}

if __name__ == "__main__":
    run(FIGURES, CH)
