{
"cells": [
{
"cell_type": "markdown",
"id": "82b1b350",
"metadata": {},
"source": [
"# Graph and Geometric Deep Learning\n",
"\n",
"*The Mathematics of Large Language Models ยท Chapter 9*\n",
"\n",
"Follow relationships, audit bridges and test what local labels miss.\n",
"\n",
"These pages illustrate the mathematics. Read the saved figures and calculations in order, or open [the interactive browser edition](reader.html) to change the examples. No code editing is needed.\n",
"\n",
"Request node labels, an undirected edge list, nonnegative weights and the meaning of an edge. Draw the supplied relationship graph and compare positive-weight connected components and lambda 2 before and after a proposed edge removal; relate lambda-tilde 2 to the weakest cut. For propagation request node features, normalization, self-loops and depth; return the resulting values and the degree-weighted limiting pattern only when its hypotheses hold. Report edge curvature and propagation coefficients between distant nodes as bottleneck diagnostics, not guarantees. Treat WL label agreement as a limited local test, and state the filter polynomial degree for spectral filters."
]
},
{
"cell_type": "markdown",
"id": "e30d8ff8",
"metadata": {},
"source": [
"Reproducing these calculations
\n",
"\n",
"The optional calculation cells use Python with NumPy, SciPy, and Matplotlib. All inputs are included in this file. The figures below are saved, so running these cells is optional.\n",
"\n",
"Show the answer
\n",
"\n",
"Only the bridge contributes: 0.5 x (2 - (-2))^2 = 8. Counting both directions gives 16 before dividing by two.\n",
"\n",
"Show the answer
\n",
"\n",
"No. If every count is c, the symmetric weight is 1/sqrt(c x c) = 1/c, the same as the row rule. They differ only when counts differ.\n",
"\n",
"Show the answer
\n",
"\n",
"The distance is at most 2 x 0.8^3 = 1.024. It is only an upper bound; the real distance can be smaller.\n",
"\n",
"Show the answer
\n",
"\n",
"Yes. Unique IDs give every node a different class at the start. The blindness result only holds when starting labels are identical, so it cannot be reused for the new setup.\n",
"\n",
"Show the answer
\n",
"\n",
"Between 0.02 / 2 = 0.01 and sqrt(2 x 0.02) = 0.2. A small eigenvalue therefore guarantees a cut with score at most 0.2.\n",
"\n",
"Show the answer
\n",
"\n",
"Positive, 2/3. Node 0 spreads over nodes 1, 2, 3 and node 1 over nodes 0, 2, 3. Two thirds of the mass already overlaps, so only 1/3 moves, at cost 1/3.\n",
"\n",
"Show the answer
\n",
"\n",
"1/3. Each extra step crosses a node pair with counts 3 and 3, so the weight is 1/sqrt(3 x 3) = 1/3. This matches the barbell values, which fall by a factor of 3 per step.\n",
"\n",
"Show the answer
\n",
"\n",
"It only rescales the signal by theta_0 and mixes no neighbors. Every frequency gets the same response, so no frequency is removed.\n",
"\n",
"