Graph Neural Networks

Node 4 is 3 hops from node 0 (0→1→3→4 or 0→2→3→4). This means a walk of length 2 cannot possibly reach it. Longer walks capture more distant structural information — but also blur local patterns.

Wait — let's re-check. d(s,x) is shortest-path distance in the original graph between s=2 and x.

Hmm, all neighbors of t=1 happen to be direct neighbors of s=2, so α = 1 for all. But for q to matter, we need a neighbor of t that is NOT a neighbor of s. Let's consider a different scenario.

Actually, let's trace from s=0 to t=1 instead, where node 3 is a neighbor of t=1 but d(0,3) = 2:

With q=2, the walk is discouraged from moving to node 3 (which is far from the source). This makes the walk more BFS-like, staying near the source's local neighborhood. With q=0.5, it would be encouraged to explore outward.

Skip-gram takes each node in the walk as a "center word" and pairs it with all nodes within the window. With window=1, node v is paired with u (left context) and w (right context). When u is the center, it's paired with v. When w is the center, it's paired with v. All symmetric pairs are generated.

In practice, negative sampling replaces the expensive softmax. For each positive pair, sample k random "negative" nodes and train a binary classifier to distinguish real context from noise.

Typical embedding dimensions are 64-256. Too small and you can't capture the graph's structure. Too large and you overfit (especially with limited random walks) and waste memory. The embedding table has |V| × d parameters — at d = 10,000 that's 100M parameters just for the lookup table on a 10K-node graph, which is absurdly overparameterized.

javascript
function randomWalk(adjList, start, length) {
  const walk = [start];
  let curr = start;
  for (let i = 0; i < length; i++) {
    const neighbors = adjList[curr];
    curr = neighbors[Math.floor(Math.random() * neighbors.length)];
    walk.push(curr);
  }
  return walk;
}

Node 1 has degree 3 in à (neighbors 0, 2, plus self-loop). So each neighbor's feature contributes 1/3 to the average. This is the "mean aggregation" that defines GCN.

Node 1 averages its own features [0,1] with neighbors 0's [1,0] and 2's [1,1]. The output [0.667, 0.667] is the centroid of those three feature vectors. After ReLU (which is a no-op since both values are positive), this becomes node 1's new representation.

Notice: nodes 0 and 3 have the same output [0.5, 0.5] even though they started with different features! Both are degree-1 nodes at the ends of a path, so they average their own features with their one neighbor's. After one layer, symmetrical positions in the graph get similar representations. This is a preview of the over-smoothing problem we'll study in Chapter 4.

Without self-loops, D^-1A averages ONLY the neighbors' features, throwing away the node's own features entirely. After one layer, node 0 with features [1,0] would get h' = x₁ = [0,1] (its only neighbor). Its own identity is completely lost. Adding I to A ensures each node includes itself in the aggregation.

Notice: the parameter count does NOT depend on the number of nodes or edges! The same W is applied to every node. This is why GNNs generalize across graphs of different sizes — unlike MLPs, which would need N × d_in parameters in the first layer alone.

Line 7 is the bug. The code computes ÃX but never normalizes by D̄^-1. It computes the degree on line 6 but never uses it! Without D̄^-1 normalization, each node sums its neighbors' features instead of averaging. High-degree nodes accumulate huge values, causing features to explode exponentially with each layer.

The fix: divide each row of AX by the corresponding degree. AX[i] = AX[i].map(v => v / deg[i]).

With W = I, GCN simply averages the features. h'₂[1] = 0.667. The mean operation treats all neighbors equally — node 3 with its "empty" features [0,0] dilutes the average just as much as informative node 1.

The key difference from GCN: the node's OWN features are kept separate from the neighbors' aggregate. This means the weight matrix W can learn different transformations for self-information vs. neighborhood information. The concatenated vector has dimension 2d (4 in this case), and W maps it back to d_out.

Wait — let me recompute carefully:

Hmm, I stated 0.4 as the answer. Let me re-examine the setup. With a = [0.2, 0.3, -0.1, 0.4]:

The raw attention score is 0.9. After LeakyReLU (positive value, so unchanged) and softmax over all neighbors, this becomes a normalized weight. The key insight: GAT learns a to assign different importance to different neighbors based on their features.

GraphSAGE's neighbor sampling is the key innovation for scalability. Instead of aggregating all 10,000 neighbors, it samples a fixed k (typically 10-25). This makes computation cost per node O(k) regardless of degree. GCN's mean aggregation still requires touching all neighbors, and GAT needs to compute attention scores for all neighbors. In practice, mini-batch training with sampling (as in GraphSAGE and later DGL/PyG implementations) is essential for large graphs.

The GAT paper uses concatenation for hidden layers (to preserve expressiveness) but averaging for the output layer (to produce a fixed-size output for classification). This is analogous to multi-head attention in transformers, where heads are concatenated then projected.

On this graph, a 4-layer GCN lets every node see every other node. After that, additional layers only smooth further. For real-world social networks with diameter ~6 (six degrees of separation), even a 3-layer GNN covers most of the graph.

λ₂ = 1. This measures how well-connected the graph is. For the complete graph K₃, λ₂ = 3 (maximally connected). For a disconnected graph, λ₂ = 0. Higher λ₂ means faster mixing, which means faster over-smoothing in GNNs.

The star graph has diameter 2, so after 2 GCN layers every node's receptive field covers the entire graph. The chain has diameter 20, so you'd need 20 layers to fully connect it. Over-smoothing is directly tied to the spectral gap (λ₂) of the normalized Laplacian — larger gap = faster convergence to the stationary distribution = faster over-smoothing. The star graph has a large spectral gap.

Increasing width does NOT help with over-smoothing. The problem is that (D̄^-1Ã)^k converges to rank-1 regardless of feature dimension. Residual connections preserve the original signal. JK-Net accesses early-layer representations that haven't been smoothed yet. DropEdge slows the mixing by removing random edges each epoch. All three are proven strategies; wider layers are not.

The MAD after the initial features X is much higher. As you add layers, MAD decreases toward 0 — that's over-smoothing quantified. When MAD ≈ 0, all node representations are essentially identical and classification becomes impossible.

By symmetry of K_n, the Laplacian eigenvalues are known: λ = 0 (multiplicity 1) and λ = n (multiplicity n-1).

The eigenvector for λ=0 is always [1,1,...,1]/√n (constant signal). The eigenvectors for λ=3 span the space orthogonal to this — they represent "high frequency" signals where adjacent nodes differ. A GCN (low-pass filter) suppresses these λ=3 components, smoothing towards the constant eigenvector.

The normalized Laplacian has eigenvalues in [0, 2]. For K₃: λ = 0, 3/2, 3/2. The normalization rescales the spectrum into a fixed range, which is why Kipf & Welling approximate λ_max ≈ 2 for the Chebyshev polynomial.

In ChebNet, K=3 means the filter uses T₀(L̃), T₁(L̃), T₂(L̃), T₃(L̃) with learnable coefficients θ₀,...,θ₃. Each T_k(L̃)x involves exactly k hops of neighborhood aggregation, so K controls the receptive field size. GCN (K=1) only uses T₀ and T₁.

The Chebyshev recurrence T_k(L)x = 2L · T_k-1(L)x - T_k-2(L)x only needs matrix-vector multiplies with L. Since L is sparse (|E| nonzeros), each multiply is O(|E|). K iterations cost O(K|E|), which is linear in graph size. No eigendecomposition needed. This is the fundamental insight that made spectral GNNs practical.

The low-frequency component (λ = 0, the "constant" signal) has gain 1 — perfectly preserved. The high-frequency component (λ = 1.5) has gain -0.5 — attenuated by half. After k layers, this becomes (-0.5)^k, which rapidly goes to 0. This IS over-smoothing, viewed through the spectral lens: high-frequency information (node differences) is exponentially suppressed.

A perfect score of 0 means the translation h + r lands exactly on t. In practice, scores are slightly negative due to imperfect embeddings. The loss function (margin-based) pushes correct triples toward 0 and incorrect ones below -γ (the margin).

Both TransE and DistMult give 0 for this triple, but for different geometric reasons. TransE measures translational distance; DistMult measures multiplicative interaction. Note that DistMult(h, r, t) = DistMult(t, r, h) — it's symmetric. This means it can't distinguish "born_in" from "birthplace_of." TransE can, because h + r = t but t + r ≠ h.

If (Einstein, born_in, Germany) and (Hilbert, born_in, Germany) are both true, then h_Einstein + r ≈ t_Germany and h_Hilbert + r ≈ t_Germany. This forces h_Einstein ≈ h_Hilbert. For 1-to-N relations, all head entities sharing the same (relation, tail) get collapsed to the same point. Symmetric relations are also problematic: h + r = t and t + r = h forces r = 0. RotatE and ComplEx address these issues using rotations/complex numbers.

Wait — the TransE score for the positive should be HIGHER (closer to 0) than the negative. Let me reconsider the formula. The standard margin loss is:

where d = ||h + r - t|| (distance, not score). So d_pos = 0.3, d_neg = 1.5:

Actually, the answer depends on whether we use score or distance. Using the negative score formulation where we want score_pos > score_neg + γ:

Loss = 0. No update needed. The positive triple already scores higher than the negative by more than the margin. The model has successfully separated this pair.

The entity embeddings dominate. This is the FB15k-237 benchmark scale. Larger KGs like Wikidata (100M+ entities) at d=200 would need 20B+ parameters just for entity embeddings — this is why KG embedding at web scale requires careful engineering (e.g., PBG by Facebook uses distributed training).

Two common neighbors suggest a likely edge between 0 and 3. In social networks, this is "friends of friends" — the more mutual friends two people have, the more likely they should be connected.

Jaccard normalizes by the union. This prevents high-degree nodes from dominating: CN(celebrity, anyone) is large simply because the celebrity has many neighbors. Jaccard says "what fraction of their combined connections do they share?" — a more meaningful similarity measure.

If the common neighbors had degree 100 instead: AA = 2/log(100) = 2/4.605 = 0.434 — much lower. High-degree common neighbors contribute less. Adamic-Adar consistently outperforms CN and Jaccard on real-world link prediction benchmarks.

The dot product measures embedding similarity. Higher score = more likely edge. To convert to a probability, pass through sigmoid: σ(0.56) = 0.636. Training uses binary cross-entropy: existing edges are positive examples, sampled non-edges are negatives.

The negative pair with score 0.7 is causing problems — it's ranked higher than two positive pairs. AUC = 0.5 is random; AUC = 1.0 is perfect separation. 0.778 is decent but shows the model is confusing some non-edges for edges. State-of-the-art link prediction AUCs on citation networks are ~0.95+.

Lines 4-5 (specifically line 4) are the bug. The model is trained on the FULL graph including test edges, then evaluated on those same test edges. This is data leakage — the model has already seen the "test" edges during training via the message passing (they're in the adjacency matrix). The fix: train the GNN only on the subgraph with train edges, removing test edges from the adjacency matrix during training.

Each permutation gives a different adjacency matrix representation of the same graph. If a graph has automorphisms (symmetries), some permutations give identical adjacency matrices, so the number of distinct matrices is 4! / |Aut(G)|. For a graph with no symmetry, all 24 matrices are different.

This is exactly the number of entries in the lower triangle of the adjacency matrix — one per possible edge. The sequence length grows quadratically. For n = 100, that's 4,950 decisions. GraphRNN uses a "BFS edge ordering" trick to reduce the effective sequence length by only predicting edges to recent BFS neighbors.

This is the complete graph K₁₀. Real molecular graphs are much sparser (each atom bonds to 1-4 others), so the edge density is typically |E| / C(n,2) < 0.1. Graph generation models exploit this sparsity — most edge predictions should be "no edge."

BFS visits nodes layer by layer from a starting node. Node i in BFS order is typically connected only to nodes within the current and previous BFS layer — a narrow window of size M. Instead of predicting i-1 edge decisions, node i only predicts M decisions (M is often 3-5 for sparse graphs). This reduces the effective sequence length from O(n²) to O(nM), making generation tractable for larger graphs.

Graph generation quality is measured by comparing DISTRIBUTIONS of graph statistics (degree distribution, clustering coefficient distribution, orbit counts) between generated and real graphs, using metrics like MMD (Maximum Mean Discrepancy). These statistics are permutation-invariant — they don't depend on which node is labeled 0, 1, 2, etc. Two isomorphic graphs contribute identically to all these metrics.

Ethanol's heavy-atom skeleton: C—C—O, a simple path of 3 nodes with 2 edges. In practice, hydrogen atoms are often omitted from the graph (they can be inferred from valence rules), reducing graph size significantly. Node features encode atom type (C=6, O=8), formal charge, aromaticity, etc. Edge features encode bond type (single, double, triple, aromatic).

Correct order: SMILES → Encode → GNN Layers → Readout → Predict

1. Parse the SMILES string into a molecular graph (atoms, bonds, features)

2. Encode atom features (atomic number, degree, charge, etc.) into d-dimensional vectors

3. Run K layers of GNN message passing to propagate information

4. Readout: pool all node embeddings into a single graph-level vector

5. MLP head maps graph vector to the predicted property (scalar)

~43K parameters — tiny by transformer standards! Most GNNs for molecular property prediction are in the 10K-500K parameter range. The inductive bias from graph structure (message passing on molecular topology) compensates for the small parameter budget. Larger is not always better — GNNs are often data-limited (thousands of molecules, not billions of tokens).

The paper "How Powerful are Graph Neural Networks?" (Xu et al., 2019) proved that GIN with sum aggregation and injective update functions (MLPs) is as powerful as the 1-WL test. Mean and max aggregations lose information: mean can't distinguish {1,1,1} from {1}, and max can't distinguish {1,1,1} from {1,2,1} (if max is the same). Sum is injective on multisets: sum({1,1,1}) = 3 ≠ sum({1}) = 1. GIN exploits this with the update: h^(k)_v = MLP((1+ε) · h^(k-1)_v + ∑ h^(k-1)_u).

Sum pooling preserves the most information. Mean pooling loses size: a molecule with 10 carbon atoms and one with 20 carbons (with the same average embedding) would be indistinguishable. Max pooling loses multiplicity. In practice, concatenating sum + mean + max often works best — each captures different information. Set2Set (an LSTM-based readout) is even more expressive but slower.

javascript
function graphReadout(embeddings) {
  const N = embeddings.length, d = embeddings[0].length;
  const sum = Array(d).fill(0);
  const max = Array(d).fill(-Infinity);
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < d; j++) {
      sum[j] += embeddings[i][j];
      if (embeddings[i][j] > max[j]) max[j] = embeddings[i][j];
    }
  }
  const mean = sum.map(v => v / N);
  return { sum, mean, max };
}

3-5 layers is the sweet spot for molecular graphs. With diameter ~5-10, 3-5 layers let every atom "see" every other atom. More layers cause over-smoothing (Chapter 4) without adding information. Empirically, GNN performance on molecular benchmarks peaks at 3-5 layers and degrades beyond that. Compare to transformers: they can use 96+ layers because they have residual connections, layer normalization, and self-attention (not neighborhood averaging).

Line 4 is the bug. The code sorts graphs by size but does NOT sort the labels to match. After sorting, graph[i] no longer corresponds to labels[i]. The model learns to correlate molecule size with the target property (a spurious shortcut) instead of learning actual chemical structure. The fix: sort (graph, label) pairs together, or remove the sorting.