"""Murphy (2022), Chapter 23: Graph Embeddings.

Companion code for Chapter 23 of K. P. Murphy, Probabilistic Machine Learning: An Introduction
(MIT Press, 2022; April 2025 draft), pp. 753-772, written from scratch with numpy, scipy,
matplotlib and PyTorch (CPU), to be read next to the lecture notes (../ch23-graph-embeddings.html).
networkx is only used to read Zachary's karate-club graph and to draw nothing else.

Methods
* Section 23.3.2, Euclidean distance-based embeddings: classical multi-dimensional scaling of the
  shortest-path distances (classical_mds, (23.7)) and Laplacian eigenmaps as the generalised
  eigenproblem L z = lambda D z (laplacian_eigenmaps, (23.8)-(23.10)).
* Section 23.3.3, hyperbolic embeddings: the Poincare distance (poincare_dist, (23.11)), the
  Nickel-Kiela softmax loss (23.12) trained by Riemannian SGD (train_tree_embedding), and a
  constructive embedding of a tree (hyperbolic_tree), with the Euclidean analogue.
* Section 23.3.4, matrix factorisation: the best rank-L symmetric factorisation by the spectral
  theorem (sym_factor), graph factorisation on the observed edges only (23.14) (graph_factorisation)
  and the GraRep transition matrices (23.15)-(23.16) (grarep_target).
* Section 23.3.5, skip-gram: random walks, the window distribution of (23.17) (window_weights),
  the expected skip-gram-with-negative-sampling loss and its closed-form optimum
  (sgns_expected, netmf_matrix) and a sampled DeepWalk (deepwalk_sgns).
* Section 23.3.6, label propagation (23.19)-(23.21): the iteration, the harmonic closed form and label
  spreading (label_propagation, harmonic_solution, label_spreading).
* Section 23.4, graph neural networks: the contraction fixed point of the original GNN and the
  Almeida-Pineda gradient (gnn_fixed_point, implicit_grad), the GCN propagation matrix and its
  spectrum (gcn_norm), simplified GCN (sgc_features, fit_softmax), GraphSAGE neighbour sampling
  (sage_mean_variance), graph attention (gat_layer), a two-layer GCN in PyTorch (train_gcn).
* Section 23.5, deep embeddings: graph auto-encoder with the loss (23.31) (train_gae), the
  variational KL term, the DGI discriminator loss (23.34) (dgi_loss_optimal).
* Section 23.6, applications: link prediction by held-out edges and AUC, clustering and node
  classification on the planted-partition graphs.

Data. Zachary's karate-club graph (34 nodes, 78 edges, two factions) is shipped with networkx. The
node-classification and link-prediction graphs are simulated planted-partition (stochastic block
model) graphs with Gaussian node features (seeds fixed in the code); the label-propagation example
uses two interleaved half-moons (scikit-learn) joined by a k-nearest-neighbour graph. The book's
chapter has no data of its own (its figures are diagrams reprinted from the literature), so every
figure below is either my own redrawing of an idea in the chapter with computed content or a
supplementary figure for a gap filled in the notes.

Figures. Reproduced (as computed redrawings): 23.1, 23.6. Skipped, with the reason:
  23.2, 23.3, 23.4, 23.5, 23.7  block diagrams of the GraphEDM framework, shallow embeddings, the
         random-walk pipeline, GraphSAGE and unsupervised GNNs (nothing is computed);
  23.8   a financial-transaction property graph (a hand-drawn schema);
  23.9   molecule drawings and odor labels (images from the literature).
Supplementary figures for the gaps filled in the notes:
  23.S1  six embeddings of the karate-club graph (Laplacian eigenmaps, MDS, adjacency spectral,
         NetMF, DeepWalk, graph factorisation);
  23.S2  DeepWalk as an implicit matrix factorisation: window weights, and the inner products of
         trained skip-gram vectors against the closed-form target;
  23.S3  label propagation on two moons: iterations, the harmonic solution, label spreading;
  23.S4  node classification (logistic regression on features, label propagation, SGC, GCN) and
         over-smoothing against the number of propagation steps;
  23.S5  the spectrum of the GCN propagation matrix and the low-pass filters it implements;
  23.S6  GraphSAGE neighbour sampling: variance against the finite-population formula;
  23.S7  link prediction: AUC of spectral, DeepWalk-type, common-neighbour and graph auto-encoder
         scores;
  23.S8  distortion of trees in Euclidean and hyperbolic planes against depth.
Run `python3 ch23_graph_embeddings.py --list`, `python3 ch23_graph_embeddings.py` (all figures, a few
minutes) or `python3 ch23_graph_embeddings.py --fig 23.6`. Files go to ../img/ch23/; the data used by
the browser demonstrations go to ../data/ch23-*.json.
"""
import json
import os
import sys

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")

import numpy as np
from scipy import linalg, optimize, special

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import common  # noqa: E402
from common import BLUE, CYAN, GREEN, GREY, MAGENTA, ORANGE, PURPLE, RED, plt, savefig  # noqa: E402

CH = 23
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
CACHE_DIR = os.path.join(HERE, "cache")
sigmoid = common.sigmoid


# =========================================================================== graphs
def karate():
    """Zachary's karate club: adjacency matrix (34 x 34, binary), faction labels (0 = Mr. Hi, 1 = Officer)."""
    import networkx as nx
    G = nx.karate_club_graph()
    A = nx.to_numpy_array(G, nodelist=range(34), weight=None)
    y = np.array([0 if G.nodes[i]["club"] == "Mr. Hi" else 1 for i in range(34)])
    return A, y


def sbm(sizes, p_in, p_out, seed):
    """Planted-partition graph: symmetric binary adjacency and block labels."""
    rng = np.random.default_rng(seed)
    y = np.repeat(np.arange(len(sizes)), sizes)
    n = len(y)
    P = np.where(y[:, None] == y[None, :], p_in, p_out)
    U = rng.random((n, n))
    A = np.triu((U < P).astype(float), 1)
    A = A + A.T
    return A, y


def node_task(seed=1, per_class=40, k=3, p_in=0.10, p_out=0.02, sd=1.15):
    """Planted-partition graph with 2-D Gaussian features whose class means are the corners of a
    triangle: features alone are ambiguous, the graph disambiguates. Returns A, X, y."""
    A, y = sbm([per_class] * k, p_in, p_out, seed)
    rng = np.random.default_rng(seed + 100)
    ang = 2 * np.pi * np.arange(k) / k + np.pi / 2
    mu = 1.6 * np.stack([np.cos(ang), np.sin(ang)], 1)
    X = mu[y] + sd * rng.normal(size=(len(y), 2))
    # a random relabelling so that the "first m per class" training set is a random sample
    perm = rng.permutation(len(y))
    A = A[np.ix_(perm, perm)]
    return A, X[perm], y[perm]


def degree(A):
    return A.sum(1)


def laplacian(A):
    return np.diag(A.sum(1)) - A


def sp_dist(A):
    """All-pairs shortest-path (hop) distances by Floyd-Warshall style repeated BFS."""
    n = len(A)
    D = np.full((n, n), np.inf)
    for s in range(n):
        D[s, s] = 0
        front = [s]
        d = 0
        while front:
            d += 1
            nxt = []
            for u in front:
                for v in np.nonzero(A[u])[0]:
                    if D[s, v] == np.inf:
                        D[s, v] = d
                        nxt.append(v)
            front = nxt
    return D


# =========================================================================== Section 23.3.2
def classical_mds(Dist, d=2):
    """Classical (Torgerson) scaling: embed so that ||z_i - z_j|| approximates Dist_ij (see gap 23.2)."""
    n = len(Dist)
    J = np.eye(n) - 1.0 / n
    B = -0.5 * J @ (Dist ** 2) @ J
    w, V = np.linalg.eigh(B)
    idx = np.argsort(w)[::-1][:d]
    return V[:, idx] * np.sqrt(np.maximum(w[idx], 0))


def laplacian_eigenmaps(A, d=2):
    """Solve min tr(Z' L Z) s.t. Z' D Z = I, Z' D 1 = 0, (23.8): generalised eigenvectors L z = lam D z
    with the smallest d non-zero eigenvalues (for a connected graph). Returns Z, eigenvalues."""
    D = A.sum(1)
    L = np.diag(D) - A
    w, V = linalg.eigh(L, np.diag(D))
    return V[:, 1:d + 1], w[1:d + 1]


def sym_factor(S, d):
    """Best rank-d symmetric factorisation S ~ Z Z' in Frobenius norm, restricted to Z real (the
    positive eigenvalues only; gap 23.3). Returns Z (n x d)."""
    w, V = np.linalg.eigh((S + S.T) / 2)
    idx = np.argsort(w)[::-1][:d]
    return V[:, idx] * np.sqrt(np.maximum(w[idx], 0))


def spectral_embedding(A, d=2):
    """The top-d eigenvectors of the adjacency matrix, scaled by sqrt(|eigenvalue|): the 'adjacency
    spectral embedding' (matrix factorisation with s(W) = W, Section 23.3.4)."""
    w, V = np.linalg.eigh(A)
    idx = np.argsort(-np.abs(w))[:d]
    return V[:, idx] * np.sqrt(np.abs(w[idx]))


# =========================================================================== Section 23.3.4
def graph_factorisation(A, d, lam=0.01, iters=6000, lr=0.5, seed=0):
    """Graph factorisation (Ahmed et al. 2013, (23.14)): minimise sum over observed edges of
    (A_ij - z_i . z_j)^2 + lam ||Z||^2 by gradient descent (cost O(edges) per step)."""
    rng = np.random.default_rng(seed)
    n = len(A)
    Z = 0.1 * rng.normal(size=(n, d))
    I, J = np.nonzero(A)
    for _ in range(iters):
        r = (Z[I] * Z[J]).sum(1) - A[I, J]
        G = np.zeros_like(Z)
        np.add.at(G, I, 2 * r[:, None] * Z[J])
        np.add.at(G, J, 2 * r[:, None] * Z[I])
        Z -= lr * (G / len(I) * 5 + 2 * lam * Z / n)
    return Z


def grarep_target(A, k):
    """The two candidate k-step targets of GraRep: the k-step transition matrix (D^-1 A)^k and the
    matrix D^-k A^k printed in (23.16) (they differ for k >= 2, gap 23.4)."""
    D = A.sum(1)
    P = A / D[:, None]
    Pk = np.linalg.matrix_power(P, k)
    Dk = np.diag(D ** (-float(k)))
    return Pk, Dk @ np.linalg.matrix_power(A, k)


# =========================================================================== Section 23.3.5
def window_weights(T, kind="dynamic"):
    """Probability omega_r that a (centre, context) pair of a random walk is at distance r, r = 1..T.
    'dynamic': the window size is drawn uniformly from {1,...,T} (word2vec), so a pair at distance r is
    used with probability (T-r+1)/T; normalised, omega_r = 2(T+1-r)/(T(T+1)).  'uniform': omega_r = 1/T."""
    r = np.arange(1, T + 1)
    if kind == "uniform":
        return np.full(T, 1.0 / T)
    w = (T + 1 - r).astype(float)
    return w / w.sum()


def pair_distribution(A, T, kind="dynamic"):
    """The joint distribution p(i, j) of (centre, context) pairs generated by a stationary random walk with
    the given window, p = sum_r omega_r diag(pi) P^r, and the marginals pi (degree / volume)."""
    D = A.sum(1)
    vol = D.sum()
    pi = D / vol
    P = A / D[:, None]
    om = window_weights(T, kind)
    Pr = np.eye(len(A))
    S = np.zeros_like(A, dtype=float)
    for r in range(1, T + 1):
        Pr = Pr @ P
        S += om[r - 1] * Pr
    return pi[:, None] * S, pi, S


def netmf_matrix(A, T, b, kind="uniform"):
    """M = vol/b * sum_r omega_r P^r D^-1 (Qiu et al. 2018, with uniform omega_r = 1/T the NetMF matrix):
    the unclipped skip-gram optimum is log M, and NetMF factorises log max(M, 1)."""
    pij, pi, S = pair_distribution(A, T, kind)
    return pij / (b * pi[:, None] * pi[None, :])


def netmf_embedding(A, T, b, d, kind="uniform"):
    M = netmf_matrix(A, T, b, kind)
    return sym_factor(np.log(np.maximum(M, 1.0)), d)


def sgns_expected(A, T, b, d, kind="dynamic", seed=0, iters=3000, tied=False):
    """Minimise the *expected* skip-gram-with-negative-sampling loss
        -sum_ij [ p_ij log sigma(x_ij) + b pi_i pi_j log sigma(-x_ij) ],  x = W C',
    with L-BFGS (no sampling noise). Returns W, C, the loss."""
    n = len(A)
    pij, pi, _ = pair_distribution(A, T, kind)
    Q = b * pi[:, None] * pi[None, :]
    rng = np.random.default_rng(seed)
    x0 = 0.1 * rng.normal(size=2 * n * d)

    def f(theta):
        W = theta[:n * d].reshape(n, d)
        C = theta[n * d:].reshape(n, d)
        X = W @ C.T
        loss = -(pij * special.log_expit(X) + Q * special.log_expit(-X)).sum()
        G = -(pij * special.expit(-X) - Q * special.expit(X))
        return loss, np.concatenate([(G @ C).ravel(), (G.T @ W).ravel()])

    res = optimize.minimize(f, x0, jac=True, method="L-BFGS-B", options=dict(maxiter=iters, ftol=1e-15, gtol=1e-10))
    return res.x[:n * d].reshape(n, d), res.x[n * d:].reshape(n, d), res.fun


def random_walks(A, num_walks, length, rng):
    n = len(A)
    nbrs = [np.nonzero(A[i])[0] for i in range(n)]
    walks = np.zeros((num_walks * n, length), dtype=int)
    k = 0
    for _ in range(num_walks):
        for s in rng.permutation(n):
            w = [s]
            for _ in range(length - 1):
                w.append(rng.choice(nbrs[w[-1]]))
            walks[k] = w
            k += 1
    return walks


def walk_pairs(walks, T, rng):
    """(centre, context) pairs with the dynamic window: for each centre position a window size is drawn
    uniformly from {1, ..., T} and all context positions within it are used."""
    nw, L = walks.shape
    cen, ctx = [], []
    for pos in range(L):
        w = rng.integers(1, T + 1, size=nw)
        for off in range(1, T + 1):
            for sgn in (-1, 1):
                q = pos + sgn * off
                if 0 <= q < L:
                    ok = w >= off
                    cen.append(walks[ok, pos])
                    ctx.append(walks[ok, q])
    return np.concatenate(cen), np.concatenate(ctx)


def deepwalk_sgns(A, d=16, T=5, b=5, num_walks=200, length=40, epochs=3, lr=0.05, batch=512, seed=0):
    """DeepWalk with skip-gram and negative sampling trained by plain mini-batch SGD on sampled walks.
    Negatives are drawn from the degree distribution (the walk's stationary distribution)."""
    rng = np.random.default_rng(seed)
    n = len(A)
    pi = A.sum(1) / A.sum()
    walks = random_walks(A, num_walks, length, rng)
    cen, ctx = walk_pairs(walks, T, rng)
    W = 0.1 * rng.normal(size=(n, d))
    C = 0.1 * rng.normal(size=(n, d))
    m = len(cen)
    for ep in range(epochs):
        order = rng.permutation(m)
        for s in range(0, m, batch):
            idx = order[s:s + batch]
            i, j = cen[idx], ctx[idx]
            neg = rng.choice(n, size=(len(idx), b), p=pi)
            gW = np.zeros_like(W)
            gC = np.zeros_like(C)
            # positive: -log sigma(w_i . c_j)
            g = -sigmoid(-(W[i] * C[j]).sum(1))
            np.add.at(gW, i, g[:, None] * C[j])
            np.add.at(gC, j, g[:, None] * W[i])
            # negatives: -log sigma(-w_i . c_k)
            for q in range(b):
                k = neg[:, q]
                g = sigmoid((W[i] * C[k]).sum(1))
                np.add.at(gW, i, g[:, None] * C[k])
                np.add.at(gC, k, g[:, None] * W[i])
            W -= lr * gW
            C -= lr * gC
    return W, C


# =========================================================================== Section 23.3.6
def label_propagation(Wt, y, labelled, n_class, iters=1000, tol=1e-12):
    """Zhu-Ghahramani label propagation: f <- D^-1 W f with the labelled rows clamped. Returns F (n x C)
    and the iteration count."""
    n = len(Wt)
    Y = np.zeros((n, n_class))
    Y[labelled, y[labelled]] = 1.0
    P = Wt / Wt.sum(1, keepdims=True)
    F = Y.copy()
    F[~np.isin(np.arange(n), labelled)] = 1.0 / n_class
    for t in range(iters):
        Fn = P @ F
        Fn[labelled] = Y[labelled]
        if np.abs(Fn - F).max() < tol:
            return Fn, t + 1
        F = Fn
    return F, iters


def harmonic_solution(Wt, y, labelled, n_class):
    """Closed form of the clamped minimiser of sum_ij W_ij (f_i - f_j)^2: f_U = (D_UU - W_UU)^-1 W_UL f_L."""
    n = len(Wt)
    U = np.setdiff1d(np.arange(n), labelled)
    D = Wt.sum(1)
    L = np.diag(D) - Wt
    Y = np.zeros((n, n_class))
    Y[labelled, y[labelled]] = 1.0
    F = Y.copy()
    F[U] = np.linalg.solve(L[np.ix_(U, U)], Wt[np.ix_(U, labelled)] @ Y[labelled])
    return F


def label_spreading(Wt, y, labelled, n_class, alpha=0.9):
    """Zhou et al. label spreading, closed form F = (1 - alpha)(I - alpha S)^-1 Y, S = D^-1/2 W D^-1/2."""
    n = len(Wt)
    Y = np.zeros((n, n_class))
    Y[labelled, y[labelled]] = 1.0
    d = Wt.sum(1)
    S = Wt / np.sqrt(d[:, None] * d[None, :])
    return (1 - alpha) * np.linalg.solve(np.eye(n) - alpha * S, Y)


def knn_graph(X, k, sigma=None):
    """Symmetrised k-nearest-neighbour graph; weights exp(-d^2 / (2 sigma^2)) if sigma is given, else 1."""
    n = len(X)
    D2 = ((X[:, None, :] - X[None, :, :]) ** 2).sum(-1)
    np.fill_diagonal(D2, np.inf)
    Wt = np.zeros((n, n))
    nn = np.argsort(D2, 1)[:, :k]
    for i in range(n):
        Wt[i, nn[i]] = 1.0 if sigma is None else np.exp(-D2[i, nn[i]] / (2 * sigma ** 2))
    return np.maximum(Wt, Wt.T)


def moons(n=120, noise=0.13, seed=0):
    from sklearn.datasets import make_moons
    X, y = make_moons(n_samples=n, noise=noise, random_state=seed)
    return X, y


# =========================================================================== Section 23.4
def gcn_norm(A, self_loops=True):
    """Kipf-Welling propagation matrix  D~^-1/2 (A + I) D~^-1/2."""
    At = A + np.eye(len(A)) if self_loops else A
    d = At.sum(1)
    return At / np.sqrt(d[:, None] * d[None, :])


def sgc_features(A, X, K):
    S = gcn_norm(A)
    H = X.copy()
    for _ in range(K):
        H = S @ H
    return H


def fit_softmax(H, y, idx, n_class, lam=1e-2, lr=0.5, iters=300):
    """Multinomial logistic regression (with bias) on rows idx by full-batch gradient descent from zero."""
    Hb = np.hstack([H, np.ones((len(H), 1))])
    W = np.zeros((Hb.shape[1], n_class))
    Y = np.eye(n_class)[y[idx]]
    for _ in range(iters):
        Z = Hb[idx] @ W
        Z -= Z.max(1, keepdims=True)
        P = np.exp(Z)
        P /= P.sum(1, keepdims=True)
        G = Hb[idx].T @ (P - Y) / len(idx)
        G[:-1] += lam * W[:-1]
        W -= lr * G
    return W


def predict_softmax(H, W):
    return (np.hstack([H, np.ones((len(H), 1))]) @ W).argmax(1)


def dirichlet_energy(A, H):
    """sum_ij A_ij ||h_i - h_j||^2 / 2 per node after degree normalisation: tr(H' L_sym H) / ||H||_F^2."""
    d = A.sum(1)
    Ls = np.eye(len(A)) - A / np.sqrt(d[:, None] * d[None, :])
    return float(np.trace(H.T @ Ls @ H) / np.sum(H ** 2))


def zscore(H):
    """Centre each column and divide by its (population) standard deviation."""
    return (H - H.mean(0)) / H.std(0)


def sgc_accuracy_curve(A, X, y, m, lam=1e-2, kmax=30, iters=300, lr=0.5):
    """Test accuracy (on the unlabelled nodes) of simplified GCN against the number of propagation steps K, with the
    first m nodes of each class in the data order as the labelled set and z-scored propagated features; also
    the Dirichlet energy of the propagated features. Used by the browser demonstration."""
    k = int(y.max()) + 1
    idx = labelled_first(y, m)
    te = np.setdiff1d(np.arange(len(y)), idx)
    acc, en = [], []
    for K in range(kmax + 1):
        H = sgc_features(A, X, K)
        Hs = zscore(H)
        W = fit_softmax(Hs, y, idx, k, lam=lam, lr=lr, iters=iters)
        acc.append(float((predict_softmax(Hs, W)[te] == y[te]).mean()))
        en.append(dirichlet_energy(A, H))
    return acc, en


def train_test_split_per_class(y, m, seed):
    rng = np.random.default_rng(seed)
    idx = []
    for c in np.unique(y):
        idx.extend(rng.choice(np.nonzero(y == c)[0], m, replace=False))
    return np.array(sorted(idx))


def gnn_fixed_point(Ahat, X, theta, iters=500, tol=1e-13):
    """The original GNN's iteration Z <- tanh(Ahat Z theta + X) (a contraction when ||Ahat|| ||theta|| < 1)."""
    Z = np.zeros_like(X)
    for t in range(iters):
        Zn = np.tanh(Ahat @ Z @ theta + X)
        if np.abs(Zn - Z).max() < tol:
            return Zn, t + 1
        Z = Zn
    return Z, iters


def implicit_grad(Ahat, X, theta, Zs, dLdZ):
    """Almeida-Pineda: gradient of L(Z*(theta)) with respect to theta by solving the adjoint fixed point
    u = (dF/dZ)' u + dL/dZ for F(Z) = tanh(Ahat Z theta + X)."""
    pre = Ahat @ Zs @ theta + X
    s = 1 - np.tanh(pre) ** 2
    u = np.zeros_like(Zs)
    for _ in range(2000):
        # (dF/dZ)' u = Ahat' (s * u) theta'
        un = Ahat.T @ (s * u) @ theta.T + dLdZ
        if np.abs(un - u).max() < 1e-14:
            u = un
            break
        u = un
    return (Ahat @ Zs).T @ (s * u)


def sage_mean_variance(values, q):
    """Variance of the mean of q values drawn without replacement from a finite population, by the formula
    (sigma^2 / q) (d - q) / (d - 1) with sigma^2 the population variance (divisor d); gap 23.12."""
    d = len(values)
    s2 = np.var(values)
    if d == 1:
        return 0.0
    return s2 / q * (d - q) / (d - 1)


def gat_layer(H, A, Wt, a_src, a_dst, slope=0.2):
    """One attention head: e_ij = LeakyReLU(a_src . W h_i + a_dst . W h_j), softmax over neighbours (with a
    self loop), output sum_j alpha_ij W h_j. Returns the output and the attention matrix."""
    Hw = H @ Wt
    e = (Hw @ a_src)[:, None] + (Hw @ a_dst)[None, :]
    e = np.where(e > 0, e, slope * e)
    mask = (A + np.eye(len(A))) > 0
    e = np.where(mask, e, -np.inf)
    e = e - e.max(1, keepdims=True)
    al = np.exp(e)
    al /= al.sum(1, keepdims=True)
    return al @ Hw, al


def train_gcn(A, X, y, train_idx, hidden=16, epochs=200, lr=0.02, wd=5e-4, dropout=0.5, seed=0, use_graph=True):
    """Two-layer GCN (Kipf and Welling) in PyTorch; use_graph=False replaces the propagation by the
    identity (an MLP with the same sizes). Returns predictions for all nodes."""
    import torch
    torch.manual_seed(seed)
    S = torch.tensor(gcn_norm(A) if use_graph else np.eye(len(A)), dtype=torch.float32)
    Xt = torch.tensor(X, dtype=torch.float32)
    yt = torch.tensor(y)
    k = int(y.max()) + 1
    W0 = torch.nn.Parameter(torch.randn(X.shape[1], hidden) * (1 / np.sqrt(X.shape[1])))
    W1 = torch.nn.Parameter(torch.randn(hidden, k) * (1 / np.sqrt(hidden)))
    opt = torch.optim.Adam([W0, W1], lr=lr, weight_decay=wd)
    tr = torch.tensor(train_idx)
    for ep in range(epochs):
        opt.zero_grad()
        H = torch.relu(S @ (torch.nn.functional.dropout(Xt, dropout) @ W0))
        out = S @ (torch.nn.functional.dropout(H, dropout) @ W1)
        loss = torch.nn.functional.cross_entropy(out[tr], yt[tr])
        loss.backward()
        opt.step()
    with torch.no_grad():
        H = torch.relu(S @ (Xt @ W0))
        out = S @ (H @ W1)
    return out.argmax(1).numpy()


# =========================================================================== Section 23.5
def train_gae(A_train, d=16, epochs=200, lr=0.02, hidden=32, seed=0, X=None):
    """Graph auto-encoder of Kipf and Welling: Z = Ahat relu(Ahat X W0) W1, decoder sigma(Z Z'),
    loss (23.31) with the positive pairs re-weighted by (n^2 - m)/m. X = identity if not given.
    Returns the embedding and the score matrix Z Z'."""
    import torch
    torch.manual_seed(seed)
    n = len(A_train)
    S = torch.tensor(gcn_norm(A_train), dtype=torch.float32)
    Xt = torch.eye(n) if X is None else torch.tensor(X, dtype=torch.float32)
    At = torch.tensor(A_train + np.eye(n), dtype=torch.float32)
    m = float(At.sum())
    pos_w = (n * n - m) / m
    norm = n * n / (2.0 * (n * n - m))
    W0 = torch.nn.Parameter(torch.randn(Xt.shape[1], hidden) * np.sqrt(2.0 / (Xt.shape[1] + hidden)))
    W1 = torch.nn.Parameter(torch.randn(hidden, d) * np.sqrt(2.0 / (hidden + d)))
    opt = torch.optim.Adam([W0, W1], lr=lr)
    for ep in range(epochs):
        opt.zero_grad()
        Z = S @ (torch.relu(S @ (Xt @ W0)) @ W1)
        logits = Z @ Z.T
        loss = norm * torch.nn.functional.binary_cross_entropy_with_logits(logits, At, pos_weight=torch.tensor(pos_w))
        loss.backward()
        opt.step()
    with torch.no_grad():
        Z = S @ (torch.relu(S @ (Xt @ W0)) @ W1)
    return Z.numpy(), (Z @ Z.T).numpy()


def kl_gauss_std_normal(mu, logvar):
    """KL( N(mu, diag(exp(logvar))) || N(0, I) ) = 0.5 sum (exp(logvar) + mu^2 - 1 - logvar)."""
    return 0.5 * np.sum(np.exp(logvar) + mu ** 2 - 1 - logvar)


def dgi_loss_optimal(p, q):
    """Value of the DGI-type discriminator loss E_p[-log D] + E_q[-log(1 - D)] at the optimal D = p/(p+q)
    for two discrete distributions, and 2 log 2 - 2 JSD(p, q)."""
    D = p / (p + q)
    L = -(p * np.log(D)).sum() - (q * np.log(1 - D)).sum()
    m = (p + q) / 2
    jsd = 0.5 * np.sum(p * np.log(p / m)) + 0.5 * np.sum(q * np.log(q / m))
    return L, 2 * np.log(2) - 2 * jsd, jsd


def auc_score(pos, neg):
    """Area under the ROC curve = P(score of a random positive > score of a random negative) (ties count 1/2)."""
    pos = np.asarray(pos)[:, None]
    neg = np.asarray(neg)[None, :]
    return float((pos > neg).mean() + 0.5 * (pos == neg).mean())


def split_edges(A, frac, seed):
    """Hold out a fraction of the edges (and the same number of non-edges) for link prediction.
    Returns A_train, held-out edges, sampled non-edges."""
    rng = np.random.default_rng(seed)
    n = len(A)
    iu = np.triu_indices(n, 1)
    E = np.array([(i, j) for i, j in zip(*iu) if A[i, j] > 0])
    Ne = np.array([(i, j) for i, j in zip(*iu) if A[i, j] == 0])
    m = int(round(frac * len(E)))
    te = E[rng.choice(len(E), m, replace=False)]
    ne = Ne[rng.choice(len(Ne), m, replace=False)]
    At = A.copy()
    At[te[:, 0], te[:, 1]] = 0
    At[te[:, 1], te[:, 0]] = 0
    return At, te, ne


# =========================================================================== Section 23.3.3: hyperbolic
def poincare_dist(x, y):
    """Poincare-ball distance (23.11), rows of x and y."""
    x = np.atleast_2d(x)
    y = np.atleast_2d(y)
    num = ((x - y) ** 2).sum(-1)
    den = (1 - (x ** 2).sum(-1)) * (1 - (y ** 2).sum(-1))
    return np.arccosh(1 + 2 * num / den)


def balanced_tree(b, depth):
    """Adjacency of the complete b-ary tree of the given depth, parent array and depth array (root = 0)."""
    n = sum(b ** k for k in range(depth + 1))
    A = np.zeros((n, n))
    parent = -np.ones(n, dtype=int)
    dep = np.zeros(n, dtype=int)
    for v in range(1, n):
        p = (v - 1) // b
        A[p, v] = A[v, p] = 1
        parent[v] = p
        dep[v] = dep[p] + 1
    return A, parent, dep


def mobius_translate(z, p):
    """Hyperbolic translation of the Poincare disk (complex numbers) taking 0 to p."""
    return (z + p) / (1 + np.conj(p) * z)


def hyperbolic_tree(b, depth, tau, geometry="hyperbolic"):
    """Constructive embedding of the complete b-ary tree in the plane with every edge of length tau in the
    chosen geometry. Hyperbolic: points of the Poincare disk (complex), children of a node placed at
    equal angles around it (excluding the direction of the parent) after moving the node to the origin.
    Euclidean: the same recipe in the plane. Returns complex coordinates."""
    A, parent, dep = balanced_tree(b, depth)
    n = len(A)
    z = np.zeros(n, dtype=complex)
    hyp = geometry == "hyperbolic"
    r = np.tanh(tau / 2) if hyp else tau
    for v in range(n):
        kids = [c for c in range(b * v + 1, b * v + b + 1) if c < n]
        if not kids:
            continue
        if v == 0:
            alpha, nang = 0.0, b
            offs = [2 * np.pi * j / nang for j in range(len(kids))]
        else:
            nang = b + 1
            if hyp:
                par_local = (z[parent[v]] - z[v]) / (1 - np.conj(z[v]) * z[parent[v]])
            else:
                par_local = z[parent[v]] - z[v]
            alpha = np.angle(par_local)
            offs = [2 * np.pi * (j + 1) / nang for j in range(len(kids))]
        for c, o in zip(kids, offs):
            loc = r * np.exp(1j * (alpha + o))
            z[c] = mobius_translate(loc, z[v]) if hyp else loc + z[v]
    return z, A, parent, dep


def pair_dist_complex(z, geometry="hyperbolic"):
    if geometry == "hyperbolic":
        a = z[:, None]
        b_ = z[None, :]
        num = np.abs(a - b_) ** 2
        den = (1 - np.abs(a) ** 2) * (1 - np.abs(b_) ** 2)
        return np.arccosh(np.maximum(1 + 2 * num / den, 1.0))
    return np.abs(z[:, None] - z[None, :])


def tree_distortion(z, A, tau, geometry="hyperbolic"):
    """Average and worst relative distortion  |d_emb / (tau * d_tree) - 1|  over all node pairs."""
    Dt = sp_dist(A)
    De = pair_dist_complex(z, geometry)
    iu = np.triu_indices(len(A), 1)
    r = De[iu] / (tau * Dt[iu])
    return float(np.mean(np.abs(r - 1))), float(np.max(np.abs(r - 1)))


def train_tree_embedding(A, dim=2, geometry="hyperbolic", epochs=300, lr=0.3, n_neg=10, burn=20, seed=0, batch=32):
    """Nickel-Kiela embedding of the ancestor relation of a tree: softmax loss (23.12) with sampled
    negatives, hyperbolic version by Riemannian SGD (the Euclidean gradient is multiplied by
    (1 - ||x||^2)^2 / 4 and the update is projected back into the ball). The Euclidean version uses
    plain SGD with the Euclidean distance. Returns the embedding (n x dim)."""
    import torch
    torch.manual_seed(seed)
    rng = np.random.default_rng(seed)
    n = len(A)
    _, parent, dep = balanced_tree(int(round((A.sum(1)[0]))), int(dep_of(A).max()))
    anc = []
    for v in range(n):
        u = parent[v]
        while u >= 0:
            anc.append((u, v))     # u is an ancestor of v
            u = parent[u]
    anc = np.array([pr for pr in anc if pr[0] != 0])   # the root is related to every node: no negatives
    anc_all = anc
    related = np.zeros((n, n), dtype=bool)
    related[0, :] = related[:, 0] = True
    related[anc[:, 0], anc[:, 1]] = True
    related[anc[:, 1], anc[:, 0]] = True
    related[np.arange(n), np.arange(n)] = True
    X = torch.nn.Parameter(1e-3 * (2 * torch.rand(n, dim, dtype=torch.float64) - 1))
    hyp = geometry == "hyperbolic"

    def dist(a, b_):
        if hyp:
            num = ((a - b_) ** 2).sum(-1)
            den = (1 - (a ** 2).sum(-1)).clamp_min(1e-9) * (1 - (b_ ** 2).sum(-1)).clamp_min(1e-9)
            return torch.acosh(1 + 2 * num / den + 1e-12)
        return torch.sqrt(((a - b_) ** 2).sum(-1) + 1e-12)

    for ep in range(epochs):
        step = lr / 10 if ep < burn else lr
        order = rng.permutation(len(anc))
        for s in range(0, len(order), batch):
            pr = anc[order[s:s + batch]]
            u, v = pr[:, 0], pr[:, 1]
            negs = np.zeros((len(pr), n_neg), dtype=int)
            for k in range(len(pr)):
                cand = np.nonzero(~related[u[k]])[0]
                negs[k] = rng.choice(cand, n_neg)
            if X.grad is not None:
                X.grad.zero_()
            dp = dist(X[u], X[v])
            dn = dist(X[u][:, None, :], X[negs])
            logits = torch.cat([-dp[:, None], -dn], 1)
            loss = -torch.log_softmax(logits, 1)[:, 0].sum()
            loss.backward()
            with torch.no_grad():
                g = X.grad
                if hyp:
                    g = g * ((1 - (X ** 2).sum(-1, keepdim=True)) ** 2 / 4)
                X -= step * g
                if hyp:
                    nr = X.norm(dim=-1, keepdim=True)
                    X.copy_(torch.where(nr >= 1 - 1e-5, X / nr * (1 - 1e-5), X))
    return X.detach().numpy()


def dep_of(A):
    """Depth of every node of a tree given as adjacency (root = node 0)."""
    return sp_dist(A)[0].astype(int)


def embedding_quality(Z, A, geometry):
    """Spearman correlation between embedding distances and tree distances over all pairs, and the mean
    relative distortion after the best global rescaling (median of the ratio)."""
    from scipy.stats import spearmanr
    Dt = sp_dist(A)
    if geometry == "hyperbolic":
        De = poincare_dist(Z[:, None, :], Z[None, :, :])
    else:
        De = np.sqrt(((Z[:, None, :] - Z[None, :, :]) ** 2).sum(-1))
    iu = np.triu_indices(len(A), 1)
    rho = spearmanr(De[iu], Dt[iu])[0]
    ratio = De[iu] / Dt[iu]
    s = np.median(ratio)
    return float(rho), float(np.mean(np.abs(ratio / s - 1)))


# =========================================================================== figures
def _scatter_two(ax, Z, y, title=None, labels=False, s=34):
    cols = np.where(y == 0, RED, BLUE)
    ax.scatter(Z[:, 0], Z[:, 1], c=cols, s=s, edgecolor="white", linewidth=0.5, zorder=3)
    if labels:
        for i, (a, b_) in enumerate(Z[:, :2]):
            ax.annotate(str(i + 1), (a, b_), fontsize=6, xytext=(2, 2), textcoords="offset points")
    if title:
        ax.set_title(title, fontsize=9.5)
    ax.set_xticks([])
    ax.set_yticks([])


def _draw_edges(ax, Z, A, colour="#bbbbbb", lw=0.6):
    I, J = np.nonzero(np.triu(A))
    for i, j in zip(I, J):
        ax.plot([Z[i, 0], Z[j, 0]], [Z[i, 1], Z[j, 1]], color=colour, lw=lw, zorder=1)


def kmeans_accuracy(Z, y, seed=0):
    from sklearn.cluster import KMeans
    lab = KMeans(2, n_init=10, random_state=seed).fit_predict(Z)
    acc = (lab == y).mean()
    return max(acc, 1 - acc)


def loo_knn_accuracy(Z, y, k=3):
    """Leave-one-out k-nearest-neighbour accuracy of the labels y in the embedding Z (Euclidean)."""
    D = np.round(((Z[:, None, :] - Z[None, :, :]) ** 2).sum(-1), 9)   # ties (collapsed points) broken by index
    np.fill_diagonal(D, np.inf)
    nn = np.argsort(D, 1, kind="stable")[:, :k]
    pred = (y[nn].mean(1) > 0.5).astype(int)
    return float((pred == y).mean())


def mean_average_precision(Z, A, geometry):
    """Mean over nodes of the average precision of ranking the other nodes by embedding distance, the
    relevant ones being the tree neighbours (parent and children)."""
    if geometry == "hyperbolic":
        D = poincare_dist(Z[:, None, :], Z[None, :, :])
    else:
        D = np.sqrt(((Z[:, None, :] - Z[None, :, :]) ** 2).sum(-1))
    aps = []
    for u in range(len(A)):
        o = np.argsort(D[u])
        o = o[o != u]
        rel = A[u][o] > 0
        hits = np.cumsum(rel)
        aps.append((hits[rel] / (np.nonzero(rel)[0] + 1)).mean())
    return float(np.mean(aps))


def fig_23_1(out=None):
    """Figure 23.1: a grid (every interior node has the same four neighbours) against an irregular graph."""
    fig, axes = plt.subplots(1, 3, figsize=(9.2, 3.0), gridspec_kw=dict(width_ratios=[1, 1, 1.15]))
    ax = axes[0]
    g = 6
    xs, ys = np.meshgrid(np.arange(g), np.arange(g))
    P = np.stack([xs.ravel(), ys.ravel()], 1).astype(float)
    Ag = np.zeros((g * g, g * g))
    for i in range(g):
        for j in range(g):
            v = i * g + j
            if j + 1 < g:
                Ag[v, v + 1] = Ag[v + 1, v] = 1
            if i + 1 < g:
                Ag[v, v + g] = Ag[v + g, v] = 1
    _draw_edges(ax, P, Ag)
    deg = Ag.sum(1)
    ax.scatter(P[:, 0], P[:, 1], c=np.where(deg == 4, BLUE, GREY), s=40, zorder=3, edgecolor="white")
    ax.set_title("(a) grid: interior degree 4", fontsize=9.5)
    ax.axis("off")
    ax.set_aspect("equal")
    ax = axes[1]
    A, y = karate()
    Z, _ = laplacian_eigenmaps(A, 2)
    import networkx as nx
    pos = nx.spring_layout(nx.from_numpy_array(A), seed=3, k=0.35, iterations=200)
    P2 = np.array([pos[i] for i in range(34)])
    _draw_edges(ax, P2, A)
    dg = A.sum(1)
    ax.scatter(P2[:, 0], P2[:, 1], s=14 + 9 * dg, c=dg, cmap="viridis", zorder=3, edgecolor="white")
    ax.set_title("(b) karate club: degrees 1 to 17", fontsize=9.5)
    ax.axis("off")
    ax.set_aspect("equal")
    ax = axes[2]
    bins = np.arange(0.5, 19.5, 1)
    ax.hist(dg, bins=bins, color=ORANGE, alpha=0.9, label="karate club (34 nodes)")
    ax.hist(deg, bins=bins, color=BLUE, alpha=0.9, label="6 x 6 grid (36 nodes)")
    ax.set_xlabel("degree")
    ax.set_ylabel("number of nodes")
    ax.legend(frameon=False, fontsize=8)
    ax.set_title("(c) neighbourhood sizes", fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig23-1", out)


def fig_23_6(out=None):
    """Figure 23.6: a complete binary tree (63 nodes, depth 5) embedded in the plane, Euclidean against hyperbolic, trained with the
    loss (23.12) (shallow embeddings), and the constructive hyperbolic embedding."""
    A, parent, dep = balanced_tree(2, 5)
    res = embedding_results(A)
    zh, _, _, _ = hyperbolic_tree(2, 5, 1.0)
    fig, axes = plt.subplots(1, 3, figsize=(10.2, 3.5))
    cmap = plt.get_cmap("viridis")
    for ax, (Z, ttl) in zip(axes, [(res["euc"], "(a) Euclidean plane, trained (23.12)"),
                                   (res["hyp"], "(b) Poincaré disk, trained (23.12)"),
                                   (np.stack([zh.real, zh.imag], 1), "(c) Poincaré disk, constructed")]):
        _draw_edges(ax, Z, A, "#aaaaaa", 0.6)
        ax.scatter(Z[:, 0], Z[:, 1], c=dep, cmap=cmap, s=22, edgecolor="white", linewidth=0.4, zorder=3)
        ax.set_title(ttl, fontsize=9.5)
        ax.set_aspect("equal")
        ax.set_xticks([])
        ax.set_yticks([])
        if "disk" in ttl:
            t = np.linspace(0, 2 * np.pi, 200)
            ax.plot(np.cos(t), np.sin(t), color="#666", lw=0.8)
            ax.set_xlim(-1.05, 1.05)
            ax.set_ylim(-1.05, 1.05)
    axes[0].set_xlabel("neighbour MAP %.2f, Spearman %.2f" % (res["map_euc"], res["q_euc"][0]), fontsize=8.5)
    axes[1].set_xlabel("neighbour MAP %.2f, Spearman %.2f" % (res["map_hyp"], res["q_hyp"][0]), fontsize=8.5)
    zc = hyperbolic_tree(2, 5, 1.0)
    axes[2].set_xlabel("mean distortion %.2f (edge length 1)" % tree_distortion(zc[0], zc[1], 1.0)[0], fontsize=8.5)
    fig.tight_layout()
    savefig(fig, CH, "fig23-6", out)


def embedding_results(A):
    """Train (and cache) the Euclidean and Poincare embeddings of the 127-node binary tree."""
    os.makedirs(CACHE_DIR, exist_ok=True)
    path = os.path.join(CACHE_DIR, "ch23_tree_embeddings_d5.npz")
    if os.path.exists(path):
        d = np.load(path)
        euc, hyp = d["euc"], d["hyp"]
    else:
        euc = train_tree_embedding(A, 2, "euclid", epochs=100, lr=0.03, burn=10, seed=0)
        hyp = train_tree_embedding(A, 2, "hyperbolic", epochs=100, lr=0.1, burn=10, seed=0)
        np.savez(path, euc=euc, hyp=hyp)
    return dict(euc=euc, hyp=hyp, q_euc=embedding_quality(euc, A, "euclid"), q_hyp=embedding_quality(hyp, A, "hyperbolic"),
                map_euc=mean_average_precision(euc, A, "euclid"), map_hyp=mean_average_precision(hyp, A, "hyperbolic"))


def karate_embeddings():
    A, y = karate()
    out = {}
    out["Laplacian eigenmaps"] = laplacian_eigenmaps(A, 2)[0]
    out["MDS (hop distances)"] = classical_mds(sp_dist(A), 2)
    out["adjacency spectral"] = spectral_embedding(A, 2)
    out["NetMF (T = 5, b = 1)"] = netmf_embedding(A, 5, 1.0, 2)
    W, C, _ = sgns_expected(A, 5, 1, 2, kind="uniform", seed=1)
    out["skip-gram optimum (d = 2)"] = W
    out["graph factorisation"] = graph_factorisation(A, 2)
    return A, y, out


def fig_S1(out=None):
    """Figure 23.S1: six embeddings of the karate-club graph."""
    A, y, emb = karate_embeddings()
    fig, axes = plt.subplots(2, 3, figsize=(9.2, 6.0))
    for ax, (name, Z) in zip(axes.ravel(), emb.items()):
        _draw_edges(ax, Z, A, "#cccccc", 0.5)
        acc = loo_knn_accuracy(Z, y)
        _scatter_two(ax, Z, y, "%s\nleave-one-out 3-NN: %d of 34 right" % (name, round(acc * 34)))
    fig.tight_layout()
    savefig(fig, CH, "fig23-S1", out)


def fig_S2(out=None):
    """Figure 23.S2: window weights, and skip-gram vectors against the closed-form target."""
    A, y = karate()
    T, b = 5, 1.0
    fig, axes = plt.subplots(1, 3, figsize=(10.0, 3.3))
    ax = axes[0]
    Tm = 8
    r = np.arange(1, Tm + 1)
    ax.plot(r, window_weights(Tm, "dynamic"), "o-", color=BLUE, label="dynamic window: $2(T+1-r)/(T(T+1))$")
    ax.plot(r, window_weights(Tm, "uniform"), "s--", color=ORANGE, label="uniform window: $1/T$")
    ax.plot(r, (Tm - 1 + r) / Tm, "^:", color=RED, label="as printed: $(T-1+q)/T$")
    ax.axhline(1.0, color="#999", lw=0.5)
    ax.set_xlabel("distance r between centre and context")
    ax.set_ylabel("weight")
    ax.set_title("(a) window weights, T = %d" % Tm, fontsize=9.5)
    ax.legend(frameon=False, fontsize=7, loc=(0.02, 0.3))
    # (b) expected SGNS optimum vs target, (c) sampled DeepWalk vs target
    pij, pi, S = pair_distribution(A, 10, "dynamic")
    target = np.log(pij / (1.0 * pi[:, None] * pi[None, :]))
    W, C, _ = sgns_expected(A, 10, 1, 34, kind="dynamic", seed=0)
    X1 = W @ C.T
    ax = axes[1]
    ax.scatter(target.ravel(), X1.ravel(), s=3, color=BLUE, alpha=0.5)
    lim = [target.min() - .3, target.max() + .3]
    ax.plot(lim, lim, color="k", lw=0.8)
    ax.set_xlabel("target $\\log\\,p_{ij}/(b\\pi_i\\pi_j)$")
    ax.set_ylabel("$w_i\\cdot c_j$ at the optimum")
    ax.set_title("(b) exact objective, d = 34", fontsize=9.5)
    Wd, Cd = deepwalk_sgns(A, d=16, T=10, b=1, num_walks=100, length=40, epochs=3, lr=0.05, seed=0)
    X2 = Wd @ Cd.T
    ax = axes[2]
    ax.scatter(target.ravel(), X2.ravel(), s=3, color=GREEN, alpha=0.5)
    ax.plot(lim, lim, color="k", lw=0.8)
    c = np.corrcoef(target.ravel(), X2.ravel())[0, 1]
    ax.set_xlabel("target $\\log\\,p_{ij}/(b\\pi_i\\pi_j)$")
    ax.set_title("(c) sampled walks, d = 16 (r = %.2f)" % c, fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig23-S2", out)


def moons_task(n=120, k=6, seed=0):
    X, y = moons(n, 0.13, seed)
    Wt = knn_graph(X, k)
    return X, y, Wt


def labelled_first(y, m):
    """Indices of the first m points of each class in the data order."""
    return np.concatenate([np.nonzero(y == c)[0][:m] for c in np.unique(y)])


def fig_S3(out=None):
    """Figure 23.S3: label propagation on two moons."""
    X, y, Wt = moons_task()
    lab = labelled_first(y, 1)
    fig, axes = plt.subplots(1, 4, figsize=(11.0, 2.9))
    for ax, t in zip(axes[:3], [0, 10, 200]):
        F, _ = label_propagation(Wt, y, lab, 2, iters=t) if t > 0 else (None, 0)
        if t == 0:
            Fv = np.full(len(X), 0.5)
            Fv[lab] = y[lab]
        else:
            Fv = F[:, 1] / np.maximum(F.sum(1), 1e-12)
        _draw_edges(ax, X, Wt, "#dddddd", 0.4)
        sc = ax.scatter(X[:, 0], X[:, 1], c=Fv, cmap="coolwarm", vmin=0, vmax=1, s=22, edgecolor="white", linewidth=0.3, zorder=3)
        ax.scatter(X[lab, 0], X[lab, 1], s=90, facecolor="none", edgecolor="k", linewidth=1.4, zorder=4)
        ax.set_title("after %d sweeps" % t, fontsize=9.5)
        ax.set_xticks([])
        ax.set_yticks([])
    ax = axes[3]
    ms = [1, 2, 3, 5, 8]
    acc_lp, acc_ls, acc_knn = [], [], []
    from sklearn.neighbors import KNeighborsClassifier
    for m in ms:
        l = labelled_first(y, m)
        acc_lp.append((harmonic_solution(Wt, y, l, 2).argmax(1) == y).mean())
        acc_ls.append((label_spreading(Wt, y, l, 2, 0.99).argmax(1) == y).mean())
        acc_knn.append((KNeighborsClassifier(1).fit(X[l], y[l]).predict(X) == y).mean())
    ax.plot(ms, acc_lp, "o-", color=BLUE, label="label propagation")
    ax.plot(ms, acc_ls, "s--", color=GREEN, label="label spreading")
    ax.plot(ms, acc_knn, "^:", color=RED, label="1-NN on coordinates")
    ax.set_xlabel("labelled points per class")
    ax.set_ylabel("accuracy")
    ax.set_ylim(0.45, 1.02)
    ax.legend(frameon=False, fontsize=7.5)
    fig.tight_layout()
    savefig(fig, CH, "fig23-S3", out)


def node_classification(seed_graph=1, m=4, n_splits=10):
    """Accuracy of five node classifiers on the planted-partition task over several random labelled sets."""
    A, X, y = node_task(seed_graph)
    k = int(y.max()) + 1
    rows = {k_: [] for k_ in ["features only", "label propagation", "SGC K=2", "GCN (2 layers)", "MLP (2 layers)"]}
    for s in range(n_splits):
        idx = train_test_split_per_class(y, m, 100 + s)
        te = np.setdiff1d(np.arange(len(y)), idx)
        W0 = fit_softmax(X, y, idx, k)
        rows["features only"].append((predict_softmax(X, W0)[te] == y[te]).mean())
        rows["label propagation"].append((harmonic_solution(A + 1e-9, y, idx, k).argmax(1)[te] == y[te]).mean())
        H = sgc_features(A, X, 2)
        W2 = fit_softmax(H, y, idx, k)
        rows["SGC K=2"].append((predict_softmax(H, W2)[te] == y[te]).mean())
        rows["GCN (2 layers)"].append((train_gcn(A, X, y, idx, seed=s)[te] == y[te]).mean())
        rows["MLP (2 layers)"].append((train_gcn(A, X, y, idx, seed=s, use_graph=False)[te] == y[te]).mean())
    return {k_: (float(np.mean(v)), float(np.std(v))) for k_, v in rows.items()}


def fig_S4(out=None):
    """Figure 23.S4: node classification and over-smoothing."""
    A, X, y = node_task(1)
    k = 3
    res = node_classification()
    fig, axes = plt.subplots(1, 3, figsize=(10.4, 3.3))
    ax = axes[0]
    names = list(res)
    ax.barh(range(len(names)), [res[n_][0] for n_ in names], xerr=[res[n_][1] for n_ in names],
            color=[GREY, GREEN, BLUE, RED, ORANGE], height=0.6, error_kw=dict(lw=0.8))
    ax.set_yticks(range(len(names)))
    ax.set_yticklabels(names, fontsize=8)
    ax.invert_yaxis()
    ax.set_xlim(0.4, 1.0)
    ax.set_xlabel("test accuracy (4 labels per class)")
    ax.set_title("(a) planted partition, 120 nodes", fontsize=9.5)
    Ks = np.arange(0, 41)
    ax = axes[1]
    acc = []
    en = []
    for K in Ks:
        H = sgc_features(A, X, K)
        a_ = []
        for s in range(10):
            idx = train_test_split_per_class(y, 4, 100 + s)
            te = np.setdiff1d(np.arange(len(y)), idx)
            Hs = zscore(H)
            Wk = fit_softmax(Hs, y, idx, k)
            a_.append((predict_softmax(Hs, Wk)[te] == y[te]).mean())
        acc.append(np.mean(a_))
        en.append(dirichlet_energy(A, H))
    ax.plot(Ks, acc, "o-", ms=3, color=BLUE)
    ax.set_xlabel("propagation steps K")
    ax.set_ylabel("test accuracy of SGC")
    ax.set_title("(b) smoothing helps, then hurts", fontsize=9.5)
    ax = axes[2]
    ax.semilogy(Ks, en, "o-", ms=3, color=RED)
    ax.set_xlabel("propagation steps K")
    ax.set_ylabel("$\\mathrm{tr}(H^\\top L_{sym} H)/\\|H\\|_F^2$")
    ax.set_title("(c) Dirichlet energy of the features", fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig23-S4", out)


def fig_S5(out=None):
    """Figure 23.S5: spectrum of the GCN propagation matrix and the filters it implements."""
    A, X, y = node_task(1)
    S = gcn_norm(A)
    w, V = np.linalg.eigh(S)
    order = np.argsort(w)[::-1]
    w, V = w[order], V[:, order]
    fig, axes = plt.subplots(1, 3, figsize=(10.2, 3.2))
    ax = axes[0]
    ax.plot(w, ".", color=BLUE)
    ax.axhline(1, color="#999", lw=0.5)
    ax.axhline(-1, color="#999", lw=0.5)
    ax.set_xlabel("index")
    ax.set_ylabel("eigenvalue $\\mu_i$ of $\\hat S$")
    ax.set_title("(a) spectrum lies in $(-1, 1]$", fontsize=9.5)
    ax = axes[1]
    mu = np.linspace(-1, 1, 200)
    for K, c in zip([1, 2, 4, 8], [BLUE, GREEN, ORANGE, RED]):
        ax.plot(mu, mu ** K, color=c, label="K = %d" % K)
    ax.legend(frameon=False, fontsize=8)
    ax.set_xlabel("$\\mu$")
    ax.set_ylabel("$\\mu^K$")
    ax.set_title("(b) the filter after K layers", fontsize=9.5)
    ax = axes[2]
    Y1 = np.eye(3)[y] - np.eye(3)[y].mean(0)
    en = ((V.T @ Y1) ** 2).sum(1)
    ax.bar(np.arange(len(w)), en, color=MAGENTA, width=0.9)
    ax.set_xlabel("eigenvector index (largest $\\mu$ first)")
    ax.set_ylabel("energy of the label signal")
    ax.set_title("(c) labels live on the top eigenvectors", fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig23-S5", out)


def fig_S6(out=None):
    """Figure 23.S6: GraphSAGE neighbour sampling variance."""
    rng = np.random.default_rng(0)
    d = 30
    vals = rng.normal(size=d) ** 2
    qs = np.arange(1, d + 1)
    emp = []
    for q in qs:
        m = [vals[rng.choice(d, q, replace=False)].mean() for _ in range(4000)]
        emp.append(np.var(m))
    th = [sage_mean_variance(vals, q) for q in qs]
    fig, ax = plt.subplots(figsize=(4.4, 3.2))
    ax.semilogy(qs, emp, "o", ms=4, color=BLUE, label="simulation (4000 draws)")
    ax.semilogy(qs, np.maximum(th, 1e-6), "-", color=RED, label="$\\frac{\\sigma^2}{q}\\,\\frac{d-q}{d-1}$")
    ax.set_xlabel("sampled neighbours q (of d = 30)")
    ax.set_ylabel("variance of the sampled mean")
    ax.legend(frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig23-S6", out)


def link_prediction_scores(seed=0):
    """AUC of several link predictors on a planted-partition graph with 10% of the edges held out."""
    A, y = sbm([40, 40, 40, 40], 0.30, 0.01, seed + 5)
    At, te, ne = split_edges(A, 0.10, seed)
    out = {}

    def auc_from(M):
        return auc_score(M[te[:, 0], te[:, 1]], M[ne[:, 0], ne[:, 1]])

    out["common neighbours"] = auc_from(At @ At)
    for d in (4, 16):
        Z = spectral_embedding(At, d)
        out["adjacency spectral d=%d" % d] = auc_from(Z @ Z.T)
    Zl = laplacian_eigenmaps(At + 1e-9, 4)[0]
    out["Laplacian eigenmaps d=4"] = auc_from(-((Zl[:, None] - Zl[None]) ** 2).sum(-1))
    Zn = netmf_embedding(At + 1e-9, 5, 1.0, 16)
    out["NetMF d=16"] = auc_from(Zn @ Zn.T)
    _, Sg = train_gae(At, d=16, seed=seed)
    out["graph auto-encoder"] = auc_from(Sg)
    return out


def fig_S7(out=None):
    """Figure 23.S7: link prediction AUC."""
    res = {}
    for s in range(5):
        for k, v in link_prediction_scores(s).items():
            res.setdefault(k, []).append(v)
    fig, ax = plt.subplots(figsize=(5.6, 3.2))
    names = list(res)
    ax.barh(range(len(names)), [np.mean(res[n_]) for n_ in names], xerr=[np.std(res[n_]) for n_ in names], color=BLUE, height=0.6, error_kw=dict(lw=0.8))
    ax.set_yticks(range(len(names)))
    ax.set_yticklabels(names, fontsize=8)
    ax.invert_yaxis()
    ax.set_xlim(0.5, 1.0)
    ax.set_xlabel("AUC on held-out edges (5 random splits)")
    fig.tight_layout()
    savefig(fig, CH, "fig23-S7", out)


def fig_S8(out=None):
    """Figure 23.S8: tree distortion against depth."""
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 3.2))
    ax = axes[0]
    for tau, c in [(0.5, GREY), (1.0, ORANGE), (2.0, BLUE), (4.0, GREEN)]:
        dis = []
        for dpt in range(1, 8):
            z, A, _, _ = hyperbolic_tree(2, dpt, tau)
            dis.append(tree_distortion(z, A, tau)[0])
        ax.plot(range(1, 8), dis, "o-", ms=3, color=c, label="edge length %.1f" % tau)
    ax.set_xlabel("tree depth")
    ax.set_ylabel("mean relative distortion")
    ax.set_title("(a) Poincaré disk", fontsize=9.5)
    ax.legend(frameon=False, fontsize=8)
    ax = axes[1]
    for tau, c in [(1.0, ORANGE), (2.0, BLUE), (4.0, GREEN)]:
        dis = []
        for dpt in range(1, 8):
            z, A, _, _ = hyperbolic_tree(2, dpt, tau, "euclid")
            dis.append(tree_distortion(z, A, tau, "euclid")[0])
        ax.plot(range(1, 8), dis, "o-", ms=3, color=c, label="edge length %.1f" % tau)
    ax.set_xlabel("tree depth")
    ax.set_title("(b) Euclidean plane (same recipe)", fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig23-S8", out)


# =========================================================================== data for the demonstrations
def export_json():
    os.makedirs(DATA_OUT, exist_ok=True)
    A, y = karate()
    I, J = np.nonzero(np.triu(A))
    with open(os.path.join(DATA_OUT, "ch23-karate.json"), "w") as f:
        json.dump(dict(n=34, edges=[[int(i), int(j)] for i, j in zip(I, J)], club=[int(v) for v in y]), f, separators=(",", ":"))
    X, ym = moons(120, 0.13, 0)
    with open(os.path.join(DATA_OUT, "ch23-moons.json"), "w") as f:
        json.dump(dict(X=np.round(X, 5).tolist(), y=[int(v) for v in ym]), f, separators=(",", ":"))
    Ab, Xb, yb = node_task(1)
    Ib, Jb = np.nonzero(np.triu(Ab))
    with open(os.path.join(DATA_OUT, "ch23-sbm.json"), "w") as f:
        json.dump(dict(n=len(yb), edges=[[int(i), int(j)] for i, j in zip(Ib, Jb)], X=np.round(Xb, 5).tolist(), y=[int(v) for v in yb]),
                  f, separators=(",", ":"))
    print("wrote ch23-*.json")


FIGURES = {"23.1": fig_23_1, "23.6": fig_23_6, "23.S1": fig_S1, "23.S2": fig_S2, "23.S3": fig_S3, "23.S4": fig_S4,
           "23.S5": fig_S5, "23.S6": fig_S6, "23.S7": fig_S7, "23.S8": fig_S8}


def main(argv=None):
    export_json()
    common.run(FIGURES, CH, argv)


if __name__ == "__main__":
    main()
