Bonus A: Classic Graph ML and Scaling

The thread so far. This bonus page is the "before and around" the GNN block: features that preceded learned embeddings (sessions 1–2) and tricks that make GNNs (sessions 3–5) affordable at scale.

Those sessions in one minute each

More questions from every session you have reached, with spaced repetition: the cumulative review.

This bonus page covers three chapters of the 2024 lecture notes that this year's slides do not: traditional features (notes ch. 1), label propagation (ch. 19) and scaling GNNs (ch. 20). They belong together: all three ask "how much can we get from the graph structure itself, cheaply?"

1. Hand-crafted features. In a classic pipeline you compute a feature vector and give it to logistic regression or a random forest. For a node: degree, centralities (eigenvector, betweenness, closeness), clustering coefficient, and the graphlet degree vector. For a pair of nodes (link prediction): common neighbours, Jaccard, Adamic–Adar (local) and the Katz index (global). For a whole graph: a kernel \(K(G,G')=\phi(G)^\top\phi(G')\), for example the graphlet kernel or the Weisfeiler–Lehman (WL) kernel.

2. Labels are signals too. Because of homophily, neighbours tend to share labels. Label propagation repeatedly sets each unlabelled node's class probability to the weighted average of its neighbours'. Correct & Smooth takes any base predictor, spreads its errors along edges (correct), then spreads the corrected predictions (smooth). Masked label prediction feeds some labels as input features and asks the model to predict the hidden ones, like BERT.

3. Scaling. Full-batch GNN training on a graph with \(10^8\)–\(10^9\) nodes does not fit in GPU memory. Neighbour sampling (GraphSAGE) keeps at most \(H\) neighbours per hop: cost \(M\cdot H^K\). Cluster-GCN trains on communities found by METIS/Louvain: cost linear in \(K\). Simplified GCN removes the nonlinearities, so \(\tilde A^K X\) is computed once as preprocessing.

How to read it (hover a step)

1. A path graph a–b–c–d. Only a (true class 1) and d (true class 0) are labelled. A base predictor that ignores the graph (for example an MLP on node features) outputs a probability of class 1 for every node. It is not confident: .60, .55, .50, .40.
2. On the labelled nodes we know the truth, so we know the error \(e_v=p_v-\hat p_v\): a is under-predicted by .40, d is over-predicted by .40. Unlabelled nodes get error 0 for now.
3. Correct. Errors are correlated along edges, so we spread them: one step of \(E\leftarrow(1-\alpha)E+\alpha\,\bar A E\) with \(\alpha=0.5\) and \(\bar A\) = "average over neighbours" (a toy version of \(\tilde A\)) gives b +.10 and c −.10. Adding them (scale \(s=1\)): b .65, c .40. Labelled nodes are set to their true labels: \(z_a=1,\ z_d=0\).
4. Smooth. Now spread the corrected labels \(z\) themselves with the same rule: a .825, b .675, c .3625, d .2 (rounded in the picture). b now clearly leans to class 1 and c to class 0, which matches its position in the graph. Labelled nodes' final values do not matter: we already know them.

The classic pipeline has two stages. (1) Design features for the objects you predict on. (2) Train any standard model (logistic regression, random forest, a small MLP) on these features. The notes say it plainly: using effective features over graphs is the key to good performance. Everything below assumes an undirected graph \(G=(V,E)\) with adjacency matrix \(A\). \(N(v)\) is the set of neighbours of \(v\) and \(k_v=|N(v)|\) is its degree.

Degree

\(k_v\): the number of neighbours. Simple and useful, but it treats all neighbours as equal: a node linked to five isolated leaves and a node linked to five hubs get the same value.

Centralities: how "important" is a node?

• Eigenvector centrality. A node is important if its neighbours are important: \(c_v=\frac{1}{\lambda}\sum_{u\in N(v)}c_u\). Written for all nodes at once this is \(\lambda c=Ac\), an eigenvector equation. We take the eigenvector of the largest eigenvalue \(\lambda_{\max}\). By the Perron–Frobenius theorem (for a connected graph) \(\lambda_{\max}\) is positive and simple, and its eigenvector can be chosen with all entries positive, so it is a valid score. (PageRank is a close cousin with a random-jump term.)
• Betweenness centrality. A node is important if it is a gatekeeper: it lies on many shortest paths between other nodes. \[ c_v=\sum_{s\neq v\neq t}\frac{\#\{\text{shortest paths } s\to t \text{ through } v\}}{\#\{\text{shortest paths } s\to t\}} \] Each pair \((s,t)\) gives one unit of "flow", split equally among its shortest paths; \(v\) collects the share that passes through it.
• Closeness centrality. A node is important if it is close to everyone: \(c_v=\dfrac{1}{\sum_{u\neq v} d(u,v)}\), where \(d(u,v)\) is the shortest-path length. (The notes' formula prints "number of shortest paths" in the denominator; the standard definition, used here, sums shortest-path lengths.)

Clustering coefficient

How connected are \(v\)'s neighbours to each other? \[ e_v=\frac{\#\{\text{edges among } N(v)\}}{\binom{k_v}{2}}\in[0,1] \] The denominator is the number of possible edges among \(k_v\) neighbours. \(e_v\) counts triangles through \(v\) in its ego-network (the subgraph induced by \(\{v\}\cup N(v)\)). Social networks have very high clustering: your friends tend to know each other.

Graphlet degree vector (GDV)

The clustering coefficient counts one pattern (the triangle). Why not count all small patterns? Graphlets are small rooted, connected, induced, non-isomorphic subgraphs. "Rooted" means we also record which position \(v\) holds in the pattern (in a 3-node path, the centre and an end are different positions, called orbits). "Induced" means we take a node subset with all edges between those nodes. The GDV of \(v\) counts, for each graphlet position, how many times \(v\) appears there. Using all graphlets with 2–5 nodes gives a vector of 73 numbers: a detailed fingerprint of \(v\)'s local topology.

Two families of node features. Importance-based features (degree, centralities) help predict influential nodes, such as celebrities on X. Structure-based features (degree, clustering, GDV) capture the shape of the neighbourhood, which helps predict a node's role, such as a bridge or a member of a dense group. The limitation (notes p.10): these features are all local; two nodes in far-apart but similar regions get the same features.

Link prediction comes in two forms (notes p.10):

• Links missing at random. Remove a random set of edges and try to recover them (for example, unknown drug–drug interactions).
• Links over time. Given the graph \(G[t_0,t_0']\) with edges up to time \(t_0'\), output a ranked list \(L\) of pairs that will appear in \(G[t_1,t_1']\). Evaluation: let \(n=|E_{\text{new}}|\) be the number of new edges in the test period; take the top \(n\) pairs of \(L\) and count how many are correct.

The method: compute a score \(c(x,y)\) for every pair \((x,y)\), sort, and predict the top pairs as links. Scores:

• Common neighbours: \(c(u,v)=|N(u)\cap N(v)|\).
• Jaccard coefficient: \(c(u,v)=\dfrac{|N(u)\cap N(v)|}{|N(u)\cup N(v)|}\). Normalises by the size of the neighbourhoods, so two hubs do not win just because they are big.
• Adamic–Adar: \(c(u,v)=\sum_{w\in N(u)\cap N(v)}\dfrac{1}{\log k_w}\). A shared neighbour with few friends is strong evidence; a shared celebrity is weak evidence. (The notes print \(1/k_u\); that is the "resource allocation" index. Adamic–Adar uses \(1/\log k_w\).)

The problem with all three: they are 0 when \(u\) and \(v\) share no neighbour, even if they are very close in the graph. A global score fixes this.

Katz index

Count all walks between \(u\) and \(v\), of every length, with shorter walks weighted more. The key fact: \((A^\ell)_{uv}\) = number of walks of length \(\ell\) from \(u\) to \(v\) (proof by induction: \((A^{\ell+1})_{uv}=\sum_w (A^\ell)_{uw}A_{wv}\), i.e. extend each length-\(\ell\) walk by one edge). So \[ S_{uv}=\sum_{\ell=1}^{\infty}\beta^\ell (A^\ell)_{uv},\qquad S=\sum_{\ell=1}^\infty(\beta A)^\ell=(I-\beta A)^{-1}-I. \] \(\beta\in(0,1)\) is a decay factor. The closed form is the geometric series of matrices; it converges when \(\beta\lt 1/\lambda_{\max}(A)\) (the notes just say \(\beta\lt 1\), which is necessary but not sufficient for graphs with \(\lambda_{\max}\gt 1\)).

To classify whole graphs (is this molecule toxic?), we need a feature vector for an entire graph. Kernel methods (for example SVMs) do not need explicit features; they need a similarity \(K(G,G')\in\mathbb R\) such that the kernel matrix \([K(G,G')]_{G,G'}\) is always positive semi-definite. Then there exists a feature map \(\phi\) (maybe infinite-dimensional) with \(K(G,G')=\phi(G)^\top\phi(G')\). In practice we design \(\phi\) directly.

Idea: bag-of-X. In NLP, bag-of-words counts words and ignores order. For graphs, "bag of nodes" (count nodes) is too weak: every graph with 4 nodes looks the same. "Bag of degrees" is better. Graph kernels count richer things.

Graphlet kernel

Here graphlets are defined slightly differently from the node-level version: they are not rooted and need not be connected. For size \(k=3\) there are 4 graphlets: no edge, one edge, a path of two edges, a triangle. The feature \(f_G\in\mathbb R^{n_k}\) counts how many \(k\)-node subsets of \(G\) induce each graphlet. Because bigger graphs have bigger counts, normalise: \(h_G=f_G/\sum_i f_{G,i}\), then \(K(G,G')=h_G^\top h_{G'}\).

The limitation is cost. Counting size-\(k\) graphlets by enumeration in a graph with \(n\) nodes takes \(O(n^k)\), because each subset needs an isomorphism test (and subgraph isomorphism is NP-hard in general). With maximum degree \(d\), connected graphlets can be enumerated in \(O(n d^{k-1})\) (notes p.11).

Weisfeiler–Lehman (WL) kernel (not in these notes; from earlier years' lecture 2 slides)

Goal: an efficient feature that still sees structure. Use colour refinement:

1. Give every node the same initial colour \(c^{(0)}(v)\) (or its node label).
2. Repeat \(K\) times: \(c^{(k+1)}(v)=\text{HASH}\big(c^{(k)}(v),\ \{\!\{c^{(k)}(u):u\in N(v)\}\!\}\big)\). HASH maps each distinct (own colour, multiset of neighbour colours) pair to a new colour. After \(k\) steps, a node's colour summarises its \(k\)-hop neighbourhood.
3. \(\phi(G)\) = counts of every colour that appeared in any round. \(K(G,G')=\phi(G)^\top\phi(G')\).

Each round costs \(O(|E|)\), so the whole kernel is linear in the number of edges per iteration. This is the same aggregation that message-passing GNNs do, which is why the WL test is the ceiling of their expressive power (the GIN result).

Setting (transductive, also called semi-supervised, node classification). We know labels \(Y_v\) for some nodes of one graph \(G=(V,E)\) and want the labels of the rest. Node embeddings and GNNs use features and structure, but they do not use the known labels of neighbours as input. Label propagation does.

Why would neighbours share labels? Two social mechanisms (notes p.103):

• Homophily: people link to similar people ("birds of a feather"). Similarity causes the link.
• Influence: linked people become similar (you adopt your friends' opinions). The link causes the similarity.

Either way, labels are correlated across edges, and that correlation is a signal.

The algorithm

Binary labels \(Y_v\in\{0,1\}\). Keep a probability \(P(Y_v=c)\) for each node.

1. Initialise: labelled nodes get their true label (\(P=1\) for their class). Unlabelled nodes get \(P(Y_v=1)=\tfrac12\).
2. Update every unlabelled node to the weighted average of its neighbours: \[ P^{(t+1)}(Y_v=c)=\frac{1}{\sum_{(v,u)\in E}A_{v,u}}\sum_{(v,u)\in E}A_{v,u}\,P^{(t)}(Y_u=c). \] \(A_{v,u}\) is the edge weight (1 for unweighted graphs), so the denominator is \(v\)'s (weighted) degree. Labelled nodes stay fixed.
3. Stop when \(|P^{(t)}(Y_v)-P^{(t-1)}(Y_v)|\le\epsilon\) for all \(v\), or after a maximum number of iterations. Predict class 1 if \(P(Y_v=1)\gt 0.5\).

Mini-example. Path 1–2–3–4–5, node 1 has label 1, node 5 has label 0. Start: 2, 3, 4 at 0.5. One synchronous step: node 2 = (1+0.5)/2 = 0.75, node 3 = (0.5+0.5)/2 = 0.5, node 4 = (0.5+0)/2 = 0.25. Next step: node 2 = (1+0.5)/2 = 0.75, node 3 = (0.75+0.25)/2 = 0.5, node 4 = (0.5+0)/2 = 0.25 — nothing changes, so it has converged. The probabilities fall linearly from the 1-labelled end to the 0-labelled end.

Issues (notes p.104): convergence can be slow and is not guaranteed (for example oscillation on bipartite graphs if you also update all nodes synchronously without anchoring); and it ignores node features. One step is very cheap, and overall it is usually cheaper than training a deep network, but GNN inference on new data is faster than re-running propagation.

Motivation. GNNs can fail badly when node features are only mildly predictive (figure above). Correct & Smooth (C&S) is a post-processing method that is model-agnostic: take your favourite base model (even a plain MLP) and improve it with the graph. The key observation: the errors of a base predictor are also correlated along edges. If the model underestimates class 1 at a node, it probably also underestimates it at that node's neighbours.

The diffusion matrix

Add self-loops (\(A_{ii}=1\)), let \(D\) be the diagonal degree matrix (\(D_{ii}=\deg i\)), and define \[ \tilde A=D^{-1/2}AD^{-1/2},\qquad \tilde A_{ij}=\frac{1}{\sqrt{d_i d_j}}\ \text{ if } i\sim j. \] Each edge weight accounts for the degree of both endpoints, so hubs do not dominate.

Theorem (notes p.106). All eigenvalues of \(\tilde A\) lie in \([-1,1]\), and the largest is 1 with eigenvector \(D^{1/2}\mathbf 1\). Hence powers \(\tilde A^K\) neither explode nor vanish.

The algorithm

1. Train a base predictor that outputs soft labels (class probabilities) for every node. Use the labelled nodes for training and validation.
2. Apply it to all nodes (labelled ones too) to get soft labels \(\hat p_v\); stack them as the matrix \(\hat P\).
3. Correct step. Compute the training error on labelled nodes and zero elsewhere: \[ e_v=\begin{cases}p_v-\hat p_v & v \text{ labelled } (p_v=\text{one-hot true label})\\ 0 & v \text{ unlabelled}\end{cases} \] Diffuse the error matrix \(E^{(0)}\) for \(T\) steps: \(E^{(t+1)}=(1-\alpha)E^{(t)}+\alpha\tilde AE^{(t)}\). Add it back with a scale \(s\): \(\tilde P=\hat P+sE^{(T)}\). Then set \(z_v=p_v\) for labelled nodes and \(z_v=\tilde p_v\) for unlabelled ones.
4. Smooth step. Neighbouring nodes tend to share labels, so diffuse \(Z\): \(Z^{(t+1)}=(1-\alpha)Z^{(t)}+\alpha\tilde AZ^{(t)}\). The final \(Z\) gives the predictions.

\(\alpha\in(0,1)\) controls how much a node trusts its neighbours over itself; the notes describe it as controlling the assumed degree of homophily. The picture section walks through all four steps on a small path.

Strictly speaking: the original paper (Huang et al. 2021) uses the "label spreading" form \(E^{(t+1)}=(1-\alpha)E^{(0)}+\alpha\tilde AE^{(t)}\), which keeps pulling back to the initial signal (like personalised PageRank). The notes' form replaces \(E^{(0)}\) by \(E^{(t)}\). Both spread the signal along edges; the paper's form has a well-defined fixed point \((1-\alpha)(I-\alpha\tilde A)^{-1}E^{(0)}\).

Results (notes p.107): C&S significantly improves the base model, beats a smooth-only baseline, and can be combined with GNNs. In the paper, a linear model or MLP plus C&S matched or beat much larger GNNs on several OGB benchmarks, with far fewer parameters.

Masked label prediction

Inspired by BERT's masked-word objective (notes p.107). Treat labels as extra node features: concatenate the label matrix to the feature matrix, \([X,\ \dot Y]\), where \(\dot Y\) holds the observed labels (one-hot) and zeros for unknown nodes.

• Training: corrupt \(\dot Y\) into \(\tilde Y\) by masking a random portion of the known labels to 0. Feed \([X,\tilde Y]\) to a GNN and predict the masked labels. The masking prevents the trivial solution "copy your own label".
• Inference: use all known labels \(\dot Y\) as input and predict the unlabelled nodes.

Like link prediction, this is a self-supervised task: the supervision is made from the data itself. The GNN learns how to propagate labels, instead of using a fixed averaging rule.

Real graphs are huge (notes p.107–108): recommender systems (Amazon, YouTube, Pinterest) have \(10^8\)–\(10^9\) users and \(10^7\)–\(10^9\) items; social networks (Facebook, X, Instagram) have \(10^8\)–\(10^9\) users; academic graphs (Microsoft Academic Graph) and knowledge graphs (Wikidata, Freebase, about \(10^8\) entities) are similar.

Normal deep learning minimises an average loss \(\ell(\theta)=\frac1N\sum_{i=0}^{N-1}\ell_i(\theta)\) with SGD: sample a mini-batch \(B\) of \(M\ll N\) examples, compute \(\hat\ell(\theta)\) on it, update \(\theta\leftarrow\theta-\alpha\nabla\hat\ell(\theta)\). This works because examples are independent.

GNNs break this. A node's embedding depends on its neighbours, so a random mini-batch of nodes is useless on its own: sampled nodes are usually far apart and their neighbours are missing. The alternative, full-batch training, updates all nodes at once, layer by layer: \[ H^{(k+1)}=\sigma\big(\tilde AH^{(k)}W_k^\top+H^{(k)}B_k^\top\big), \] where \(H^{(k)}\) holds all node embeddings at layer \(k\), \(W_k\) transforms neighbour messages and \(B_k\) transforms the node's own embedding. This needs all embeddings of all layers in GPU memory (10–20 GB at the time of the notes): impossible for \(10^9\) nodes.

Three fixes: two methods compute on small subgraphs (neighbour sampling, Cluster-GCN), one turns the GNN into feature preprocessing (Simplified GCN).

Neighbour sampling (GraphSAGE)

To compute one node's embedding with a \(K\)-layer GNN, you only need its \(K\)-hop computational graph. So: sample \(M\) target nodes, build their computational graphs, train on those. The problem: \(K\)-hop neighbourhoods grow exponentially, and one hub (a node with millions of followers) makes the graph explode.

Fix: at hop \(k\), keep at most \(H_k\) randomly sampled neighbours per node; prune the rest. A \(K\)-layer GNN then touches at most \(\prod_{k=1}^K H_k\) leaf nodes per target. With equal \(H\), total cost is \(M\cdot H^K\).

• Trade-off: small \(H\) = cheaper but higher-variance aggregation, so training is less stable.
• Still exponential in \(K\): each extra layer multiplies the cost by \(H\).
• Better sampling: instead of uniform sampling, run random walks with restarts from the node and keep the neighbours with the highest visit scores (this is what PinSAGE does). It works better in practice on natural graphs.

Worked count. With \(K=2\) and \(H_1=H_2=10\), each target needs at most \(10+10\cdot10=110\) sampled neighbours, of which 100 are leaves, whatever the hub sizes. With \(K=3\) it becomes up to 1000 leaves: one more layer, ten times the work.

Observation. Neighbour sampling is wasteful: when targets share neighbours, the same embeddings are recomputed many times. Full-batch training avoids this with layer-wise updates: a \(K\)-layer GNN needs only about \(2K|E|\) messages (each edge sends one message in each direction per layer), because each layer reuses the previous layer's embeddings. That is efficient, but does not fit in memory for the whole graph.

Idea: do layer-wise full-batch updates on a small subgraph. Which subgraph? Messages travel along edges, so the subgraph should keep as many edges as possible. Real graphs have community structure, so sample a community.

Vanilla Cluster-GCN:

1. Preprocessing: partition \(V\) into \(C\) groups \(V_1,\dots,V_C\) with a community-detection or graph-partitioning algorithm (Louvain, METIS). Each \(V_c\) induces a subgraph \(G_c\). Edges between groups are dropped.
2. Mini-batch training: sample one group \(V_c\), run the GNN layer-wise on \(G_c\), compute the loss on its nodes, update.

Issues: (a) dropped between-group edges bias the gradient estimates; (b) one group covers only a small, concentrated part of the data; (c) groups are not diverse, so gradients differ a lot between groups, giving high variance and slow SGD convergence.

Advanced Cluster-GCN: partition into many small groups; each mini-batch samples \(q\) groups \(V_{i_1},\dots,V_{i_q}\) and runs the GNN on the subgraph induced by their union. This restores the edges among the chosen groups and mixes different parts of the graph in each batch, so gradients are less biased and less noisy.

Cost. For \(M\) target nodes, a \(K\)-layer Cluster-GCN costs about \(K\cdot M\cdot D_{\text{avg}}\) (\(D_{\text{avg}}\) = average degree): linear in \(K\), versus \(M\cdot H^K\) for neighbour sampling. Example: with \(K=3\), \(H=10\), \(D_{\text{avg}}=10\): \(1000M\) versus \(30M\).

Start from the GCN layer: \(E^{(k+1)}=\text{ReLU}(\tilde AE^{(k)}W^{(k)})\). Simplified GCN (SGC) removes the ReLU. Then the layers collapse: \[ E^{(K)}=\tilde A\big(\cdots\tilde A(\tilde A X W^{(0)})W^{(1)}\cdots\big)W^{(K-1)}=\tilde A^KX\,\underbrace{W^{(0)}W^{(1)}\cdots W^{(K-1)}}_{=:W}. \] A product of linear maps is one linear map, so the model is \(\tilde A^K X W\) with a single \(W\). SGC also adds self-loops, \(A\leftarrow A+I\), before normalising, and takes the node features \(X\) as given (unlike LightGCN, which has no self-loops and learns the node embeddings).

1. Preprocess once (on CPU, sparse matrix products): \(\tilde X=\tilde A^KX\). This is \(K\) sparse multiplications.
2. Train any standard model (logistic regression, MLP) on the rows of \(\tilde X\). Now nodes are independent examples, so ordinary mini-batch SGD works and scales to billions of nodes.

Drawback: less expressive (a linear model on fixed features). Surprise: on many node-classification benchmarks it performs about as well as GCN. Why? Homophily: connected nodes tend to share labels, and \(\tilde A^K X\) averages features over \(K\)-hop neighbourhoods, so nodes in the same region get similar pre-processed features, which is exactly what a homophilous task needs. (The notes' Q&A: does that mean much of what GNNs learn is linear? "Yes.")

Graph structure is a feature generator: hand-crafted counts (degree, centrality, graphlets, Katz, WL colours) were the first graph ML. Homophily makes labels and errors smooth over edges, so cheap diffusion (label propagation, Correct & Smooth) rivals deep GNNs. At web scale, either compute on small subgraphs (neighbour sampling, Cluster-GCN) or precompute the diffusion once (SGC).

All three are the same operator: multiply by a normalised adjacency matrix, again and again. They differ in what is diffused (labels, errors, features).

This bonus session collects the formulas that predate GNNs or run beside them. They are simple, and that is their value: each can be computed by hand on a small graph, as below, and several of them are what a GNN reduces to when its weights are removed.

Symbols used in this session

Carried forward. Use it as a baseline toolkit for the project: run label propagation and classic features before a GNN, and reach for sampling when the graph does not fit on a GPU.

One problem in olympiad style. Give it fifteen minutes on paper before you open the first hint; the hints are graded, so open them one at a time.

Not in the lecture notes. Three or four points where the chapter rounds something off: the exact statement, a second way to see it, and where it stops being true. Each is short and has a pointer for going further.

Try it live. In the Graph Explorer: node features, community detection, link heuristics and label propagation against a GCN. Each lesson has predict-then-check questions.

notebook · L20 classic graph ML computes classic node and link features, Katz, label propagation, Correct & Smooth, Cluster-GCN and SGC.

Flashcards (click to flip)

• 1934–1950s — sociometry and centrality. Moreno drew the first "sociograms" of who-likes-whom; Bavelas (1950) studied closeness in communication groups; Katz (1953) proposed his status index from walk counts.
• 1954 — "homophily" is named by Lazarsfeld and Merton; McPherson, Smith-Lovin and Cook's 2001 review "Birds of a Feather" made it a pillar of network science.
• 1968 — Weisfeiler–Lehman colour refinement for graph isomorphism. 1977 — Freeman's betweenness, from sociology. 2003 — Adamic–Adar; Liben-Nowell & Kleinberg frame link prediction.
• 2002–2004 — label propagation (Zhu & Ghahramani; Zhou et al.'s label spreading). 2007 — Pržulj's graphlet degree vectors in biology. 2009–2011 — graphlet and WL kernels (Shervashidze, Borgwardt).
• 2017–2019 — scaling GNNs: GraphSAGE (sampling), PinSAGE (3 billion nodes at Pinterest), Cluster-GCN, SGC, GraphSAINT. 2020 — C&S and UniMP top the Open Graph Benchmark with label-aware tricks.

Go deeper in the SNA course. The twelve-unit course on social network analysis in this repository gives the classic side of this lecture in full, with labs and real-data analyses: Unit 1 · Ties, triads & the roots of SNA (common neighbours, Adamic–Adar and Katz as classic link predictors); Unit 2 · Homophily, balance & brokerage (label propagation: homophily used directly, with no learning); Unit 3 · Centrality & link analysis (centralities as hand-made node features, and the Katz index); Unit 5 · Heavy tails & the scale-free debate (neighbour sampling: scaling GNNs when a few hubs own most of the edges); Unit 6 · Communities & statistical network models (Louvain, modularity and label propagation as baselines); Unit 8 · Epidemics & opinion dynamics (label propagation and Correct & Smooth: opinion dynamics as a classifier); Unit 11 · Polarization, algorithms & misinformation (hand-made features and label propagation: the baselines a detector has to beat).

Running project. Section L20 · label propagation of notebooks/project/retweet_thread.py applies this lecture to one synthetic X world with coordinated rings, the same graph across the whole course.

Research extension. experiments/motif-signatures (hypotheses written before running): label propagation from 3 known ring members works best on a synchronised co-retweet graph in stealthy worlds (0.96 and 0.76 vs 0.91 and 0.58 on the plain graph): homophily needs reach.

Generated by scripts/sync_guides.py from the experiments' committed results and the dataset catalogue; rerun it (make sync-guides) after an experiment changes.

motif-signatures

Question. Which small patterns give rings away, and does timing help? experiment folder ↗

Verdicts (hypotheses written before running): H1 refuted, H2 supported, H3 refuted, H4 refuted.

Datasets for this session

From the repo's catalogue (gl.datasets; the full list with sources and licences is in data/README.md). Load one with gl.datasets.graph(name), temporal(name) or node_data(name).

• Next: Bonus B — geometric GNNs, subgraph matching and motifs, and explainability.
• Expressivity link: the WL kernel here is the same algorithm as the WL test in the GNN theory lectures (6–7): GIN is a learnable WL kernel.
• Beyond homophily: Zhu et al. (2020) "Beyond Homophily in Graph Neural Networks" (H2GCN, arXiv:2006.11468) — design choices for heterophilous graphs.
• Scaling, later: GraphSAINT (subgraph sampling with unbiased normalisation, arXiv:1907.04931) and GNNAutoScale (historical embeddings for dropped neighbours, arXiv:2106.05609).
• Open question: is there a principled way to choose between "diffuse labels" and "learn features" for a given graph, from measurable statistics such as edge homophily and feature informativeness?