Graph Neural Networks: An Introduction

Artificial intelligence has learned to handle tabular, sequential, and grid data, but these three forms cover only a fraction of the structures that matter. Spreadsheets, text, and images are carefully regularized special cases of a more general object. The real world is relational. People connect to people, atoms bond to atoms, cities connect through roads, and neurons connect through synapses. These connections are not decorative metadata placed on top of the observations. They determine which observations can influence one another.

The mathematical object that formalizes “things connected to things” is the graph, and the architecture that learns from graphs is the GNN, or Graph Neural Network. Our plan is honest and linear. First, we define graphs with enough rigor for a computer to manipulate them. Then we show why an ordinary convolutional or recurrent network fails when faced with them, and which symmetry principle solves the problem. Next, we derive message passing and use it to obtain the GCN, or Graph Convolutional Network, symbol by symbol. We calculate an entire layer by hand on a four-vertex graph that reappears in the interactive labs and in the C++23 implementation. We then derive the GAT, or Graph Attention Network, and GraphSAGE, connect learned representations to training objectives, and separate four limitations that are too often blended together: over-smoothing, heterophily, over-squashing, and limited expressive power.

Each major conceptual section ends with five fully solved exercises. They are part of the exposition, not an answer key glued to its side. The first exercises verify definitions, the middle ones require a calculation, and the last ones ask us to diagnose a modeling or implementation choice. A reader who covers the solution and works before reading it will turn the article into a compact course.

1. Why graphs matter

A network is neither a collection of isolated numbers nor an ordered sequence. It has structure, context, and meaning, and all three live in the pattern of its connections. Consider a social network: each user is a vertex, and each friendship is an edge. The information needed to predict whether two users will become friends does not reside only in their individual profiles. It also lies in how many friends they share, how dense their shared neighborhood is, and how central each person is to the network. None of these signals appears if we treat every user as an isolated row in a spreadsheet.

Chemistry provides the most literal example. A molecule is, without metaphor, a graph: each atom is a vertex with its own identity and attributes, such as atomic number, charge, and hybridization, while each chemical bond is an edge with its own type, such as single, double, or aromatic. The topology of this network is not decorative. It helps determine the molecule’s three-dimensional shape, its pharmacological activity, and its role in biochemical reactions. Two compounds with exactly the same atoms but different connections are different substances. An architecture that ignores connection structure is literally throwing away the information that defines the molecule.

Networks of interest to data science also have two properties that tables and sequences lack. They are large, since real graphs may contain billions of vertices, and they are often dynamic, with vertices and edges appearing and disappearing. We need an approach that respects structure, scales to real-world size, and tolerates change. That approach begins with graph theory, which we formalize next.

1.1 Solved exercises

Exercise 1.1. Identify the prediction level. A social platform wants to predict whether users Alice and Bob will connect next week. Is this a vertex, edge, or graph-level task?

Solution. The candidate output is attached to the pair $(\text{Alice},\text{Bob})$, so this is an edge-level task, usually called link prediction. Alice’s and Bob’s attributes may help, but the graph contributes common neighbors, path counts, and local density. A row-wise model can use the attributes only after someone has manually engineered those structural quantities.

Exercise 1.2. Turn a molecule into a learning example. For a molecular toxicity classifier, identify vertices, edges, vertex features, edge features, and the prediction level.

Solution. Atoms are vertices; chemical bonds are edges. Atomic number, formal charge, and aromaticity are possible vertex features. Bond order and bond type are possible edge features. Toxicity is one label for the whole molecule, so the output is graph-level. The model must therefore compute atom representations and then aggregate them into one permutation-invariant molecular representation.

Exercise 1.3. Choose direction and weight. We model a road system in which travel time from city $u$ to city $v$ differs from the reverse trip. What graph should we use?

Solution. We need a directed weighted graph. The directed edge $(u,v)$ carries the travel time $w_{uv}$, while $(v,u)$ carries $w_{vu}$. Replacing the pair by one undirected edge would assert $w_{uv}=w_{vu}$ and would erase the effect of slopes, one-way restrictions, or asymmetric congestion.

Exercise 1.4. Decide when a graph is unnecessary. A bank predicts default from a customer’s income, debt, age, and payment history, and no relationship among customers is available. Should we invent a graph?

Solution. No. A tabular model matches the available information. A GNN is justified when relationships carry a signal that the features do not already express. Connecting customers arbitrarily would introduce an inductive bias without evidence. Graphs are more general than tables, but greater generality is not free accuracy.

Exercise 1.5. Diagnose a changing graph. A recommender is retrained on Monday, and thousands of new products appear on Tuesday. Why is an inductive method attractive?

Solution. A transductive method that learns one free vector for every Monday product has no vector for a Tuesday product. An inductive GNN learns a function of features and neighborhoods, so it can compute a representation for a new product when its attributes and initial connections arrive. GraphSAGE makes this distinction explicit in Section 10.

2. Graphs: the fundamental structure

A graph is a mathematical structure that models relationships among objects. Formally, a graph $G$ is defined by the tuple $G = (V, E)$, in which $V$ is a finite set of vertices, the entities, and $E$ is a set of edges, the relationships between pairs of vertices. Throughout this article, we use $N = \vert V \vert$ for the number of vertices and $M = \vert E \vert$ for the number of edges. A vertex represents an entity: a user, an atom, or a city. An edge $e \in E$ is associated with a pair of vertices and represents a relationship between them: a friendship, a chemical bond, or a road.

2.1 Direction, weight, and adjacency

Graphs are classified first by the nature of their edges. In a directed graph, or digraph, an edge has a direction. It is an ordered pair $(u, v)$, and the relationship goes from $u$ to $v$, but not necessarily back again. The “follows” relationship in a social network is the canonical example: user $u$ may follow $v$ without $v$ following $u$. In an undirected graph, an edge is an unordered pair ${u, v}$, and the relationship is symmetric, as with mutual friendship. The attentive reader should remember the difference in notation because it will reappear in the matrices: parentheses $(u, v)$ for the ordered pair in a digraph, and braces ${u, v}$ for the unordered pair in a symmetric graph.

Edges may also carry a weight. In a weighted graph, each edge $(u, v)$ is associated with a numerical value $w_{uv}$ that quantifies the strength, cost, distance, or capacity of the connection. In a road network, $w_{uv}$ may be the distance in kilometers between two cities; in a social network, it may represent the strength of a friendship. When a graph is unweighted, we conventionally set $w_{uv} = 1$ for every existing edge.

Three connectivity terms complete the basic vocabulary. Two vertices are adjacent when an edge connects them directly. An edge is incident to the two vertices it connects. The neighborhood of a vertex $v$, denoted by $\mathcal{N}(v)$, is the set of vertices adjacent to it: $\mathcal{N}(v) = {u \mid {v, u} \in E}$. The neighborhood is the central concept of this entire article because every vertex in a GNN will collect information from it.

2.2 Degree and the handshake theorem

The degree of a vertex $v$, denoted by $\deg(v)$, is the number of edges incident to it. In a directed graph, we distinguish in-degree, which counts the edges arriving at $v$, from out-degree, which counts the edges leaving $v$. A self-loop is an edge $(v, v)$ that connects a vertex to itself. By convention, a self-loop contributes $2$ to the degree in undirected graphs so that the following result remains consistent.

Degree connects the local structure of each vertex to the global structure of the graph, and this bridge has a name.

Handshake theorem. In any undirected graph $G = (V, E)$, the sum of the degrees of all vertices equals twice the number of edges:

\[\sum_{v \in V} \deg(v) = 2 \vert E \vert\]

The proof fits in one sentence: each edge ${u, v}$ has exactly two endpoints, one incident to $u$ and the other to $v$, so it contributes exactly $2$ to the total degree sum. Summing the degrees means counting edge endpoints, and every edge has two. The intuitive reader may think of a party where each handshake involves exactly two people: the total number of hands shaken is always twice the number of handshakes. One immediate and useful corollary follows: the number of odd-degree vertices is always even because an even sum cannot contain an odd number of odd terms.

The theorem is not decoration. Once degrees are available, it provides an $O(N)$ sanity check for data that represents an undirected graph. If the degree sum is odd, the data is corrupted because no undirected graph produces an odd degree sum. Let us verify it in the example that will accompany us. Consider a four-vertex cycle graph in which every vertex has degree $2$:

The cycle has four edges, and the numbers agree.

2.3 Paths and cycles

Two final objects complete what we need. A path is a sequence of vertices in which every consecutive pair is adjacent; its length is the number of edges traversed. A cycle is a path that begins and ends at the same vertex without repeating edges or intermediate vertices. The graph used in all our examples is precisely an undirected cycle of four vertices, $v_1!-!v_2!-!v_3!-!v_4!-!v_1$, in which each person knows exactly two others. It is small enough to fit in a hand calculation and structured enough to give message passing something to propagate.

Before diving into matrices, it is worth manipulating these concepts directly. The following lab lets you build a graph, add and remove edges, and watch the adjacency, degree, and Laplacian matrices update live. I suggest that the reader verify the handshake theorem directly: add the degree column and compare it with twice the number of edges.

2.4 Solved exercises

Exercise 2.1. Compute directed degrees. Let

Find the in-degree and out-degree of every vertex.

Solution. Vertex $v_1$ sends two edges and receives one, so $(\deg^-(v_1),\deg^+(v_1))=(1,2)$. Vertex $v_2$ sends one and receives one, giving $(1,1)$. Vertex $v_3$ sends one and receives two, giving $(2,1)$. Both the total in-degree and total out-degree equal $4$, one count for each directed edge.

Exercise 2.2. Use edge weights. Three undirected roads have lengths $w_{AB}=4$, $w_{AC}=10$, and $w_{BC}=3$. What is the shortest distance from $A$ to $C$?

Solution. The direct path has cost $10$. The path $A\to B\to C$ has cost $4+3=7$, so the shortest distance is $7$. Path length and path cost are different quantities here: the chosen path has length $2$, because it uses two edges, but weight $7$.

Exercise 2.3. Recover the edge count. An undirected graph has degree sequence $(3,2,2,1)$. How many edges does it have?

Exercise 2.4. Reject an impossible sequence. Can a simple undirected graph have degree sequence $(3,3,1,1,1)$?

Exercise 2.5. Read the four-cycle. In the cycle $v_1!-!v_2!-!v_3!-!v_4!-!v_1$, find $\mathcal{N}(v_1)$, the distance from $v_1$ to $v_3$, and the number of shortest paths between them.

Solution. The neighborhood is $\mathcal{N}(v_1)={v_2,v_4}$. Both $v_1\to v_2\to v_3$ and $v_1\to v_4\to v_3$ use two edges, so the distance is $2$ and there are two shortest paths. This duplicated route will matter later because two-hop messages can reach $v_1$ from $v_3$ through two intermediaries.

3. Representing graphs with matrices

For a computer, and also the diligent reader, to apply algorithms to graphs, we must represent them numerically. Three matrices are enough for everything we will do, and a fourth will open the door to spectral theory.

3.1 The adjacency matrix

For a graph with $N$ vertices, the adjacency matrix $A$ is an $N \times N$ matrix whose entry $A_{ij}$ describes the connection between vertex $i$ and vertex $j$. For unweighted graphs, $A_{ij} = 1$ if an edge exists between $i$ and $j$, and $A_{ij} = 0$ otherwise. For weighted graphs, $A_{ij} = w_{ij}$ when the edge exists, and $0$ when it does not. If the graph is undirected, the matrix is symmetric, meaning $A_{ij} = A_{ji}$, because the relationship from $i$ to $j$ is the same as the relationship from $j$ to $i$.

For our cycle graph, with $V = {v_1, v_2, v_3, v_4}$ and edges ${v_1, v_2}$, ${v_2, v_3}$, ${v_3, v_4}$, ${v_4, v_1}$, the adjacency matrix is:

Each row lists the neighbors of a vertex: row $1$ contains $1$ in columns $2$ and $4$, indicating that $v_1$ connects to $v_2$ and $v_4$; row $2$ connects $v_2$ to $v_1$ and $v_3$; and so on. The matrix is symmetric, as an undirected graph requires. The attentive reader will notice that the adjacency matrix is the structure that directly tells us where each vertex can receive information from. This is why it will sit at the center of the GCN propagation rule.

3.2 The degree matrix

The degree matrix $D$ is an $N \times N$ diagonal matrix in which every diagonal element $D_{ii}$ is the degree of vertex $i$, and every off-diagonal element is zero. For unweighted graphs without self-loops, $D_{ii} = \sum_{j} A_{ij}$: the degree of a vertex is the sum of its row in the adjacency matrix. This identity is local; the handshake theorem appears when we sum these quantities over all vertices.

In the cycle graph, every vertex has degree $2$, and summing the rows of $A$ confirms it: $\deg(v_1) = 0 + 1 + 0 + 1 = 2$, and the same holds for the others. Therefore:

The degree matrix may look trivial because it contains only a diagonal, but each of its entries will supply one of the two normalization factors applied to an edge in Section 6. Those factors prevent high-degree vertices from dominating aggregation merely because they have more neighbors.

3.3 The feature matrix

A graph without vertex attributes is only topology. In practice, every vertex carries information. The feature matrix $X$, or $H$ when discussing the network’s internal representations, is an $N \times F$ matrix in which $N$ is the number of vertices and $F$ is the number of features per vertex. Row $i$ of this matrix, denoted by $X_i$, is the feature vector for vertex $i$: a user’s profile, the properties of an atom, or even structural attributes such as degree itself.

For the cycle graph, we assign $F = 2$ features to every vertex. Think of them as each person’s energy and sociability:

Here we reserve $X$, or equivalently $H^{(0)}$, for the input features, the original vertex attributes, and use $H^{(l)}$ for the hidden representations, the vectors produced by layer $l$ of the network. This distinction matters: the network begins with $H^{(0)} = X$ and, at every layer, transforms these features by incorporating information from the neighborhood. It produces $H^{(1)}, H^{(2)}, \dots$, which encode increasingly broad patterns. The superscript $(l)$ marks the layer, a convention we will carry to the end.

3.4 The graph Laplacian

A fourth matrix will not be used in our hand calculations, but it is the theoretical root of the entire GCN family and therefore deserves a definition. The graph Laplacian is $L = D - A$: the degree matrix minus the adjacency matrix. Its symmetrically normalized version,

is the object whose eigenvectors define the graph Fourier transform. Manipulating this expression gives rise to the GCN propagation rule. Keep the formula in mind; it will return, disguised, in Section 6. The following table consolidates the notation used from this point onward.

Table 1: Graph and GNN notation

The choice of representation is not neutral. The adjacency matrix determines how information flows among neighbors; the degree matrix provides the normalization that stabilizes learning; the feature matrix defines the starting point. Although the notation uses an $N \times N$ matrix, real implementations store sparse graphs in space proportional to $N + M$, for example with adjacency lists or compressed formats. The challenge of processing enormous neighborhoods and training with mini-batches is what pushes research toward more scalable methods such as GraphSAGE in Section 10.

3.5 Solved exercises

Exercise 3.1. Build an adjacency matrix. Write the adjacency matrix of the undirected path $v_1!-!v_2!-!v_3$.

Solution. The edges are ${v_1,v_2}$ and ${v_2,v_3}$, so

The symmetry records undirected edges twice, once in each orientation. The zeros in positions $(1,3)$ and $(3,1)$ say that $v_1$ and $v_3$ are not adjacent even though a length-$2$ path connects them.

Exercise 3.2. Derive a Laplacian. Find $D$ and $L=D-A$ for the path in Exercise 3.1.

Solution. The degrees are $(1,2,1)$, hence

Every row of $L$ sums to zero. Therefore $L\mathbf{1}=\mathbf{0}$, which says that a constant signal has no variation across edges.

Exercise 3.3. Check feature dimensions. A graph has $N=10$ vertices and $F_0=6$ input features. A layer should produce $F_1=4$ features. What are the shapes of $H^{(0)}$, $W^{(0)}$, and $H^{(1)}$, and how many trainable weights does $W^{(0)}$ contain?

Solution. We have $H^{(0)}\in\mathbb{R}^{10\times6}$, $W^{(0)}\in\mathbb{R}^{6\times4}$, and $H^{(1)}\in\mathbb{R}^{10\times4}$. The weight matrix contains $6\cdot4=24$ parameters. The number of vertices affects the amount of computation but not this parameter count.

Exercise 3.4. Measure variation with $L$. For the path in Exercise 3.1 and the vertex signal $x=[1,2,4]^\top$, compute $Lx$.

Solution.

The entries sum to zero, as expected from $\mathbf{1}^\top L=\mathbf{0}^\top$. The value $2$ at $v_3$ records that its signal $4$ exceeds its only neighbor’s signal $2$ by two units.

Exercise 3.5. Quantify dense storage. Suppose $N=10^6$ and an undirected graph has $M=5\times10^6$ edges. Compare a dense double adjacency matrix with a compressed adjacency representation that stores two 64-bit endpoint entries per edge and $N+1$ 64-bit row offsets.

Solution. The dense matrix needs $N^2=10^{12}$ entries, or $8\times10^{12}$ bytes, approximately $8$ TB in decimal units. The compressed structure needs $2M=10^7$ endpoint entries, or $80$ MB, plus about $8$ MB for row offsets, approximately $88$ MB before auxiliary metadata. The ratio is about $90{,}909$ to one. Writing an $N\times N$ symbol does not grant us permission to allocate it.

4. Why traditional networks fail on graphs

Before building the right architecture, it is instructive to understand why the wrong architectures do not work. Directly applying a CNN, or Convolutional Neural Network, or an RNN, or Recurrent Neural Network, to a graph encounters obstacles rooted not in engineering but in principle.

The first is irregular structure. A CNN assumes a regular grid. Except at the borders, or after accounting for padding, every pixel has four or eight neighbors in the same relative positions: above, below, left, and right. An RNN assumes an ordered sequence with a well-defined before and after. A graph provides neither. A vertex may have two neighbors or two million, and there is no canonical “left” or “next.” A fixed-size convolutional filter simply has nothing to rest on.

The second obstacle is deeper and defines the entire field: permutation invariance. The order in which we number vertices in an adjacency matrix is arbitrary. If we permute the vertex labels, swapping $v_1$ and $v_3$, the matrices $A$ and $X$ change because their rows and columns are reordered. The underlying graph, however, remains exactly the same, and the correct answer to any question about it must also remain the same. Formally, for any permutation matrix $P$, a function $f$ that classifies the entire graph must satisfy

which means it is permutation invariant. A function that produces one output per vertex, such as vertex classification, must satisfy $f(PAP^\top, PX) = P f(A, X)$, which means it is permutation equivariant. The output is permuted along with the input, but its content does not change. A CNN and an RNN violate this requirement from the outset because both assign meaning to position. A GNN must be blind to numbering.

This requirement is not an inconvenient restriction; it is the design compass. It dictates which operations are allowed. To aggregate information from a set of neighbors without depending on the order in which they appear, we use a function that cannot see order. Sum, mean, and maximum are the most common choices, but they are not the only ones. Learned compositions of these operations and attention-weighted sums may also be permutation invariant. Summing ${a, b, c}$ produces the same result as summing ${c, a, b}$, and this blindness to order is the principle shared by GNN aggregation functions. Permutation invariance is what separates a GNN from any other network, and the next section shows how it takes shape.

We must also consider scale. Real graphs have millions or billions of vertices, making it prohibitive to manipulate $A$ as a dense matrix. There is also dynamism, since vertices and edges appear and disappear, challenging models trained on a fixed graph. Message passing solves the structural problem and respects vertex permutations; scale and dynamism require additional strategies for sparse storage, sampling, and inductive inference.

4.1 Solved exercises

Exercise 4.1. Relabel a graph. Reorder the four-cycle vertices as $(v_3,v_1,v_4,v_2)$. Write the permutation matrix $P$ that maps the original order to the new order, and compute $PAP^\top$.

Solution. Each row of $P$ selects one row from the original order:

The relabeled adjacency matrix is

The entries moved, but every vertex still has degree $2$, and the same four edges remain. Relabeling changes coordinates, not the graph.

Exercise 4.2. Distinguish invariance from equivariance. A model assigns one class to a molecule and one class to each atom. Which output must be invariant, and which must be equivariant?

Solution. The molecular class is invariant because reordering the atoms must leave the single graph label unchanged. The atom classes are equivariant because reordering the input atoms must reorder the output rows in the same way. An invariant atom classifier would be wrong because it would forget which prediction belongs to which atom.

Exercise 4.3. Test an aggregator. A vertex receives scalar neighbor features $(2,5,1)$. Compare the sums produced by the orders $(2,5,1)$ and $(1,2,5)$.

Solution. Both sums equal $8$. The equality is not accidental; addition is commutative and associative, so every permutation produces the same result. Concatenation would produce $(2,5,1)$ in one order and $(1,2,5)$ in the other, making the representation depend on an arbitrary adjacency-list order.

Exercise 4.4. Find information lost by a mean. Give two different multisets that have the same mean, and explain the consequence for a GNN.

Solution. The multisets ${1,1}$ and ${1,1,1}$ both have mean $1$. A mean aggregator therefore cannot distinguish a vertex with two identical neighbors from one with three identical neighbors when no other signal exposes the degree. A sum produces $2$ and $3$, so it preserves multiplicity in this example. Permutation invariance is necessary, but the chosen invariant function still determines what information survives.

Exercise 4.5. Explain why a CNN is not automatically a GNN. A $3\times3$ image can be represented as a grid graph. Why does an ordinary image convolution still fail the arbitrary-permutation test?

Solution. A CNN is equivariant to translations on the regular grid because kernel offsets such as “one pixel left” have fixed meaning. An arbitrary permutation destroys those geometric offsets while preserving only graph connectivity. The CNN would treat the reordered array as a different image. A GNN recovers the neighborhood from edges and aggregates without assuming that a neighbor occupies a particular array position.

5. The heart of GNNs: message passing

Imagine a conversation at a party. Each person listens to her immediate neighbors, processes what she heard, and forms a new opinion. Repeat the round a few times: people who have never spoken directly begin to influence one another because information crosses the network from neighbor to neighbor. This is, without overstating the metaphor, the principle behind every GNN. We call this mechanism message passing, and it consists of two steps repeated at every layer.

The first step is aggregation: every vertex collects the representations of its neighbors and combines them into a single message using a permutation-invariant function such as sum, mean, or maximum, for the reasons discussed in the previous section. The second step is update: every vertex combines the aggregated message with its current representation to produce a new one. One formula encompasses nearly the entire GNN family:

In this expression, $h_i^{(l)}$ is the feature vector of vertex $i$ at layer $l$, corresponding to row $i$ of $H^{(l)}$, and $\mathcal{N}(i)$ is the neighborhood of $i$, defined in Section 2.1. The AGGREGATE function receives the set of neighbor representations and compresses it into a single vector; the UPDATE function combines that vector with the vertex’s own representation.

One consequence of the layered structure deserves attention because it will cause a problem in Section 12. After one layer, every vertex knows only its direct neighbors, at distance $1$. After two layers, it knows its neighbors’ neighbors, at distance $2$, because a neighbor’s message already contains information that neighbor collected from its own neighbors. In general, $l$ layers give each vertex access to its radius-$l$ neighborhood. Stacking layers expands each vertex’s horizon of perception, which is useful until it is not. Different GNN architectures are, at heart, different choices for AGGREGATE and UPDATE. The GCN makes the simplest and most elegant choice, so we begin with it.

The formula above omits edge features only to keep the first abstraction small. In a general message-passing neural network, or MPNN, an edge may participate explicitly:

in which $e_{ij}$ is the feature vector of edge $(i,j)$, $M^{(l)}$ constructs one message, and $U^{(l)}$ updates the receiving vertex. The sum can be replaced by another invariant aggregator. This formulation matters for molecules because a single bond and an aromatic bond should not transmit identical information merely because both connect the same atom types.

5.1 Solved exercises

Exercise 5.1. Determine the receptive field. Which vertices can influence $v_1$ after two message-passing layers on the four-cycle?

Solution. After one layer, $v_1$ receives from $v_2$ and $v_4$, and possibly from itself if the update retains a self-message. After two layers, messages from $v_3$ reach $v_1$ through either $v_2$ or $v_4$. Thus the radius-$2$ receptive field contains all four vertices. Access does not imply equal influence; normalization, weights, and nonlinearities still determine how much of each signal survives.

Exercise 5.2. Compare three aggregators. The neighbors of $v_1$ have features $h_2=[0.8,0.2]$ and $h_4=[0.6,0.1]$. Compute their element-wise sum, mean, and maximum.

Solution.

The sum retains a signal about neighborhood size, the mean removes that scale, and the maximum keeps only the largest value in each coordinate. All three ignore order, but they discard different information.

Exercise 5.3. Include an edge feature. In a scalar message $m_{ij}=0.5h_j+0.1e_{ij}$, let $h_j=2$ and $e_{ij}=3$. What arrives at vertex $i$?

Solution. The message is $m_{ij}=0.5\cdot2+0.1\cdot3=1.3$. If another edge to the same type of neighbor had $e_{ik}=8$, its message would be $1.8$. Edge features allow the same neighbor representation to be interpreted differently according to the relationship that carries it.

Exercise 5.4. Handle an isolated vertex. What happens to a mean aggregator when $\mathcal{N}(i)=\varnothing$, and how can an architecture define the update?

Solution. The mean of an empty set is undefined. An implementation must not divide by zero and hope that pedagogy emerges from NaN. One option defines the empty aggregate as the zero vector and lets UPDATE retain $h_i^{(l)}$. Another adds a self-loop, making the aggregation set contain $i$. The convention must be stated because the two choices can lead to different parameterizations.

Exercise 5.5. Compare dense and sparse cost. Let the input and output feature widths be $F_l$ and $F_{l+1}$. What is the cost of transforming all vertices and then propagating over a sparse graph?

Solution. The dense feature transformation costs $O(NF_lF_{l+1})$. Propagating the resulting vectors over $M$ edges costs $O(MF_{l+1})$. The total is therefore

Using a dense adjacency multiplication would replace the edge term by $O(N^2F_{l+1})$. Sparse storage is an algorithmic requirement, not a late optimization.

6. GCN: the fundamental architecture

The GCN introduced by Kipf and Welling solves message passing with a single linear algebra expression that processes all vertices at once. The propagation rule for one layer is:

At first glance, this is a pile of symbols. Let us take it apart piece by piece because each factor solves a concrete problem, and the attentive reader has the right to demand that none of them appear by decree.

6.1 The term $H^{(l)} W^{(l)}$: transform before mixing

The rightmost factor is $H^{(l)} W^{(l)}$. Here $H^{(l)}$ is the $N \times F_l$ matrix of current representations, and $W^{(l)}$ is an $F_l \times F_{l+1}$ weight matrix containing the trainable parameters that the network actually learns. The product $H^{(l)} W^{(l)}$ is a linear transformation that projects every feature vector from $F_l$ to $F_{l+1}$ dimensions, exactly as an ordinary dense layer would. This is the only place where the layer’s learnable parameters live; everything else in the formula is fixed graph structure. It is useful to think of $W^{(l)}$ as “what to learn from each feature” and of the rest as “whom to receive it from.”

6.2 The term $\tilde{A}$: include the vertex itself

If we aggregated using the raw adjacency matrix $A$, every vertex would receive information from its neighbors but no direct contribution from itself because the diagonal of $A$ is zero. After a few layers, its original representation could become diluted among those of its neighbors. The correction is to add self-loops to every vertex:

in which $I_N$ is the $N \times N$ identity matrix. The adjacency matrix with self-loops, $\tilde{A}$, contains $1$ on the diagonal, so each vertex now includes its own representation directly alongside those of its neighbors during aggregation.

6.3 The term $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$: normalize by popularity

The scale problem remains. A vertex with one thousand neighbors would receive a much larger aggregated message than a vertex with one neighbor, and this disparity could destabilize training according to vertex popularity. The solution is to normalize by the diagonal matrix of row sums of $\tilde{A}$, which we call $\tilde{D}$, with $\tilde{D}{ii} = \sum_j \tilde{A}{ij}$. This quantity is the degree used by the GCN operator, in which the diagonal entry added by $I_N$ counts once. It must not be confused with the combinatorial degree from Section 2.2, in which a self-loop in an undirected graph contributes $2$.

The naive choice would be $\tilde{D}^{-1}\tilde{A}$, which makes every row sum to $1$ and produces a simple mean of the neighbors. The GCN uses something more refined, the symmetric normalization $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$, whose element $(i, j)$ is

in which $\tilde{d}_i$ and $\tilde{d}_j$ are the degrees, including self-loops, of $i$ and $j$. Every connection is weighted by the square roots of the two degrees involved. An edge between two popular vertices carries less weight than an edge between two obscure vertices, balancing influence independently of popularity. The reader who compared this expression with the normalized Laplacian $L^{\text{sym}} = I - D^{-1/2}AD^{-1/2}$ from Section 3.4 has noticed that this is no coincidence. The GCN rule is essentially propagation based on the graph Laplacian with self-loops, which is the source of its spectral foundation. Finally, $\sigma(\cdot)$ is a nonlinear activation function, typically ReLU, or rectified linear unit, $\sigma(x) = \max(0, x)$. Without it, stacking layers would collapse into a single linear transformation.

6.4 Where the graph convolution comes from

The name convolution is not merely an analogy. Because $L^{\text{sym}}$ is real and symmetric, it has an eigendecomposition

in which the columns of the orthogonal matrix $U$ are eigenvectors and the diagonal matrix $\Lambda$ contains their eigenvalues. For a graph signal $x\in\mathbb{R}^N$, the coefficients $U^\top x$ are its graph Fourier transform. A spectral filter multiplies each coefficient by a learned response $g_\theta(\lambda)$ and returns to the vertex domain:

A free value for every eigenvalue would depend on one particular graph and would require the expensive eigenbasis. Following the localized polynomial filters developed by Defferrard, Bresson, and Vandergheynst, Kipf and Welling use a first-order approximation, tie its coefficients, and obtain an operator proportional to

Repeated application can make eigenvalues larger than one amplify signals or gradients. The renormalization trick replaces the expression by

which is the operator in our layer rule. The spatial interpretation is simpler than the derivation: each vertex collects normalized messages from itself and its immediate neighbors. The spectral derivation explains why that local operation deserves the word convolution and why it acts as a smoothing filter.

Putting everything together, the GCN layer transforms features with $W^{(l)}$, aggregates each vertex with its neighbors and itself through $\tilde{A}$, weights this aggregation by popularity through $\tilde{D}^{-1/2}(\cdot)\tilde{D}^{-1/2}$, and applies a nonlinearity. Nothing was invented without reason; every symbol answers a need. Let us move from the formula to the numbers.

6.5 Solved exercises

Exercise 6.1. Verify every matrix shape. Let $H^{(l)}\in\mathbb{R}^{N\times F_l}$ and $W^{(l)}\in\mathbb{R}^{F_l\times F_{l+1}}$. Show that the GCN output has shape $N\times F_{l+1}$.

Solution. The normalized adjacency has shape $N\times N$. Thus

The inner dimensions cancel in order. Reversing $H^{(l)}$ and $W^{(l)}$ would be invalid, and multiplying $W^{(l)}\hat A$ would be invalid unless feature width happened to equal the vertex count, a numerical coincidence with no mathematical justification.

Exercise 6.2. Normalize an irregular graph. Add self-loops to the path $v_1!-!v_2!-!v_3$. Find the nonzero entries of $\hat A$.

Solution. The row sums of $\tilde A$ are $(2,3,2)$. Therefore the two endpoint self-loop weights are $1/2$, the middle self-loop weight is $1/3$, and every endpoint-to-middle edge has weight

Hence

Unlike a row-normalized mean, the rows do not all sum to one.

Exercise 6.3. Observe a self-loop. On the path of Exercise 6.2, let the scalar feature vector be $x=[1,0,0]^\top$. What does row-normalized aggregation with self-loops produce?

Solution. The row-normalized matrix is

so the output is $[1/2,1/3,0]^\top$. Vertex $v_1$ retains half of its own signal, while $v_2$ receives one third of it. Without self-loops, $v_1$ would replace its feature entirely with $v_2$’s zero.

Exercise 6.4. Prove permutation equivariance. Let $S=\tilde D^{-1/2}\tilde A\tilde D^{-1/2}$. Under a relabeling $P$, show that one GCN layer satisfies $f(PAP^\top,PH)=Pf(A,H)$.

Solution. Relabeling gives $\tilde A’=P\tilde AP^\top$ and $\tilde D’=P\tilde DP^\top$, so $S’=PSP^\top$. Then

We used $P^\top P=I$ and the fact that an element-wise activation commutes with row permutation.

Exercise 6.5. Count trainable parameters. How many trainable weights does a GCN layer with $F_l=64$ and $F_{l+1}=32$ contain if it has no bias? Does the count depend on $N$ or $M$?

Solution. The matrix $W^{(l)}$ contains $64\cdot32=2{,}048$ trainable weights. The graph operator contains no learned entries, so the parameter count does not depend on either the number of vertices or the number of edges. Computation and memory grow with the graph, but this layer’s learned parameter count does not.

7. A GCN layer calculated by hand

Let us calculate an entire layer on the four-vertex cycle graph, reusing the adjacency matrix and the features $H^{(0)}$ from Section 3. The weights, which would be learned in a real network, are fixed here to produce clean numbers:

Step 1: add self-loops. We add the identity matrix to the adjacency matrix:

Step 2: row sums with self-loops. Summing each row of $\tilde{A}$, every vertex has normalization value $\tilde{d}_i = 3$ (two neighbors plus the diagonal entry), so $\tilde{D} = 3 I_4$.

Step 3: symmetric normalization. Since all normalization values equal $3$, we have $\tilde{D}^{-1/2} = \tfrac{1}{\sqrt{3}} I_4$, and therefore $\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2} = \tfrac{1}{3}\tilde{A}$:

In this regular graph, symmetric normalization coincides with a simple mean because all degrees are equal. In an irregular graph, the two diverge, which is where symmetric normalization shows its value.

Step 4: propagate. We multiply $\hat{A} H^{(0)}$, making every vertex the mean of itself and its two neighbors:

As a check, the first row is $\tfrac{1}{3}(h_1 + h_2 + h_4) = \tfrac{1}{3}([1.0, 0.5] + [0.8, 0.2] + [0.6, 0.1]) = [0.800, 0.267]$, exactly as shown.

Step 5: transform. We multiply by the weight matrix, $(\hat{A} H^{(0)}) W^{(0)}$:

Step 6: activate. We apply ReLU. Since all values are positive, it changes nothing, and the output of the layer is:

Every vertex now has a representation that encodes both its original features and those of its immediate neighborhood. A second layer would extend this reach to the radius-$2$ neighborhood; in this four-vertex graph, that already covers the entire graph.

The following lab reproduces these six steps exactly. The reader can change the input features and weights and watch every intermediate matrix, $\tilde{A}$, $\hat{A}$, propagation, and transformation, update. I suggest starting by reproducing the numbers above and then setting one feature to zero to observe how information from one vertex spreads through its neighbors in a single layer.

7.1 Solved exercises

Exercise 7.1. Recompute one output row. Derive the first row of $H^{(1)}$ without multiplying complete matrices.

Solution. Propagation gives

Then

Both coordinates are positive, so ReLU preserves them.

Exercise 7.2. Propagate twice without weights. Apply $\hat A$ twice to $H^{(0)}$. What is the first row of $\hat A^2H^{(0)}$?

Solution. After one step, the rows needed by $v_1$ are

Averaging them gives

The representation now contains information that originated at $v_3$, even though $v_1$ and $v_3$ are not adjacent.

Exercise 7.3. Make ReLU change the answer. Replace the weight matrix by

What is the output at $v_1$?

Solution. Using $\bar h_1=[0.8,0.266667]$,

ReLU maps negative values to zero, so $h_1^{(1)}=[0,0.266667]$. This example exposes why the activation is not a decorative final step.

Exercise 7.4. Use graph symmetry. Suppose $h_1=h_3=[a,b]$ and $h_2=h_4=[c,d]$ on the four-cycle. What can we say about the outputs after a GCN layer?

Solution. Vertices $v_1$ and $v_3$ have identical self-features and receive the same multiset, two copies of $[c,d]$. Therefore their normalized aggregates and outputs are equal. The same argument gives equal outputs for $v_2$ and $v_4$. This is equivariance doing useful work: graph automorphisms preserve indistinguishable vertices.

Exercise 7.5. Show that symmetric normalization is not a mean. Apply the symmetric operator from Exercise 6.2 to the constant signal $\mathbf{1}=[1,1,1]^\top$.

Solution.

A row-normalized mean would return $\mathbf{1}$. Symmetric normalization instead balances both source and destination degrees and therefore does not generally preserve a constant signal on an irregular graph. It preserves the degree-weighted eigenvector $\tilde D^{1/2}\mathbf{1}$.

8. The same layer in C++

The calculation in Section 7 translates directly into code. The following C++23 program is a correctness baseline: it performs the six mathematical steps in their derived order and reproduces $H^{(1)}$ to three decimal places. It is intentionally dense, so every factor in the equation remains visible, but its matrix storage is flat and contiguous. A std::span exposes one row without copying or owning it. This design avoids the allocation and pointer indirection of std::vector<std::vector<double>> while stopping well short of pretending to be a sparse GNN library.

Compile it on a CPU with g++ -std=c++23 -O2 -Wall -Wextra -Wpedantic -o gcn gcn_layer.cpp. No external library is required.

// gcn_layer.cpp, one GCN layer in C++23
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <iomanip>
#include <initializer_list>
#include <iostream>
#include <span>
#include <stdexcept>
#include <string_view>
#include <vector>

class Matrix {
public:
    Matrix(std::size_t rows, std::size_t cols, double value = 0.0)
        : rows_(rows), cols_(cols), values_(rows * cols, value) {}

    Matrix(std::size_t rows, std::size_t cols,
           std::initializer_list<double> values)
        : rows_(rows), cols_(cols), values_(values) {
        if (values_.size() != rows_ * cols_) {
            throw std::invalid_argument("matrix data does not match its shape");
        }
    }

    [[nodiscard]] std::size_t rows() const noexcept { return rows_; }
    [[nodiscard]] std::size_t cols() const noexcept { return cols_; }

    [[nodiscard]] double& operator()(std::size_t row, std::size_t col) {
        return values_[row * cols_ + col];
    }

    [[nodiscard]] double operator()(std::size_t row,
                                    std::size_t col) const {
        return values_[row * cols_ + col];
    }

    [[nodiscard]] std::span<const double> row(std::size_t index) const {
        return std::span<const double>{values_}.subspan(index * cols_, cols_);
    }

    [[nodiscard]] std::span<double> values() noexcept { return values_; }

private:
    std::size_t rows_;
    std::size_t cols_;
    // Row-major contiguous storage makes the innermost matrix-product loop
    // traverse both the right operand and the output in memory order.
    std::vector<double> values_;
};

// This is a dense reference product. The i,p,j order reuses A(i,p) while the
// innermost loop streams across one row of B and one row of C.
[[nodiscard]] static Matrix matmul(const Matrix& a, const Matrix& b) {
    if (a.cols() != b.rows()) {
        throw std::invalid_argument("incompatible matrix-product shapes");
    }

    Matrix c(a.rows(), b.cols());
    for (std::size_t i = 0; i < a.rows(); ++i) {
        for (std::size_t p = 0; p < a.cols(); ++p) {
            const double a_ip = a(i, p);
            for (std::size_t j = 0; j < b.cols(); ++j) {
                c(i, j) += a_ip * b(p, j);
            }
        }
    }
    return c;
}

// The dense decomposition mirrors the derivation so every intermediate matrix
// can be inspected. A production graph implementation would keep A sparse.
[[nodiscard]] static Matrix gcn_layer(const Matrix& adjacency,
                                      const Matrix& features,
                                      const Matrix& weights) {
    if (adjacency.rows() != adjacency.cols() ||
        adjacency.rows() != features.rows() ||
        features.cols() != weights.rows()) {
        throw std::invalid_argument("incompatible GCN layer shapes");
    }

    const std::size_t vertex_count = adjacency.rows();

    Matrix with_self_loops = adjacency;
    for (std::size_t i = 0; i < vertex_count; ++i) {
        with_self_loops(i, i) += 1.0;
    }

    std::vector<double> inverse_sqrt_degree(vertex_count);
    for (std::size_t i = 0; i < vertex_count; ++i) {
        double degree = 0.0;
        for (const double value : with_self_loops.row(i)) {
            degree += value;
        }
        // The symmetric normalization is real only for positive row sums.
        // Ordinary nonnegative adjacencies satisfy this after adding I.
        if (!(degree > 0.0)) {
            throw std::domain_error("GCN normalization requires positive degrees");
        }
        inverse_sqrt_degree[i] = 1.0 / std::sqrt(degree);
    }

    Matrix normalized(vertex_count, vertex_count);
    for (std::size_t i = 0; i < vertex_count; ++i) {
        for (std::size_t j = 0; j < vertex_count; ++j) {
            normalized(i, j) =
                inverse_sqrt_degree[i] * with_self_loops(i, j) *
                inverse_sqrt_degree[j];
        }
    }

    Matrix propagated = matmul(normalized, features);
    Matrix output = matmul(propagated, weights);

    for (double& value : output.values()) {
        value = std::max(0.0, value);
    }
    return output;
}

static void print_matrix(std::string_view name, const Matrix& matrix) {
    std::cout << name << " =\n" << std::fixed << std::setprecision(3);
    for (std::size_t i = 0; i < matrix.rows(); ++i) {
        for (const double value : matrix.row(i)) {
            std::cout << std::setw(8) << value;
        }
        std::cout << '\n';
    }
    std::cout << '\n';
}

int main() {
    const Matrix adjacency(4, 4, {
        0, 1, 0, 1,
        1, 0, 1, 0,
        0, 1, 0, 1,
        1, 0, 1, 0
    });
    const Matrix features(4, 2, {
        1.0, 0.5,
        0.8, 0.2,
        0.3, 0.7,
        0.6, 0.1
    });
    const Matrix weights(2, 2, {
        0.5, 0.3,
        0.1, 0.4
    });

    const Matrix next = gcn_layer(adjacency, features, weights);
    print_matrix("H^(1)", next);
}

The output reproduces, to three decimal places, the matrix $H^{(1)}$ that we calculated by hand:

H^(1) =
   0.427   0.347
   0.397   0.397
   0.317   0.303
   0.360   0.363

Validation against the hand calculation is not excessive caution. It confirms that the multiplication order, first $\hat{A}H$ and then multiplication by $W$, was respected and that normalization did not swap rows and columns. Stacking layers means chaining calls to gcn_layer, feeding one output as the next feature matrix and supplying a new $W$ for every layer.

This baseline costs $O(N^2)$ memory because it materializes dense adjacency matrices. That is appropriate only for our four-vertex derivation. A production CPU implementation stores the graph in a compressed sparse row structure and traverses edge lists, reducing graph storage to $O(N+M)$. A GPU implementation also begins from sparse edges, but performance depends on degree distribution, memory coalescing, load balance, and whether the feature transformation is fused with aggregation. The mathematical layer is common to both territories; the memory hierarchy is not.

8.1 Solved exercises

Exercise 8.1. Locate a flat element. In a row-major matrix with $4$ rows and $2$ columns, what is the flat offset of element $(2,1)$ when indices start at zero?

Solution. The class uses row * cols + col, so the offset is $2\cdot2+1=5$. The two entries of row $0$ occupy offsets $0$ and $1$, row $1$ occupies $2$ and $3$, and row $2$ begins at $4$.

Exercise 8.2. Trigger a shape error. Let features have shape $4\times2$ and weights have shape $3\times2$. Why must gcn_layer reject them?

Solution. The product $HW$ requires the number of columns of $H$ to equal the number of rows of $W$. Here $2\ne3$, so no inner dimension exists to sum over. Rejecting the call turns an otherwise silent out-of-bounds access into a precise precondition failure.

Exercise 8.3. Analyze the loop order. Why does the dense product use the order $i,p,j$ for row-major storage?

Solution. Once $i$ and $p$ are fixed, a(i,p) is reused across the complete inner loop. As $j$ increases, both b(p,j) and c(i,j) are traversed contiguously. The arithmetic count remains $O(mkn)$, but the access order avoids walking down a strided column of $B$ in the innermost loop.

Exercise 8.4. Replace the dense graph. For $N=10^6$ and $M=5\times10^6$, which part of the program must change first?

Solution. The dense adjacency, with_self_loops, and normalized matrices must become a sparse edge or compressed-row representation. The feature and weight matrices remain dense because each vertex carries a short dense vector. After transforming features, sparse propagation visits existing edges only, reducing the graph-dependent work from $O(N^2F)$ to $O(MF)$.

Exercise 8.5. Explain the degree guard. Why does the code test degree > 0.0 even after adding a self-loop?

Solution. For the nonnegative unweighted graph in the article, the added diagonal guarantees a degree of at least one. The class nevertheless accepts double weights, and negative weights could cancel the diagonal and other entries. Taking $1/\sqrt d$ for $d\le0$ is not a real-valued GCN normalization. The guard states this mathematical precondition before the invalid value contaminates every later operation.

9. GAT: when not every neighbor carries the same weight

The GCN makes a simplification that sometimes gets in the way: it weights neighbors only by their degrees, which are fixed by graph structure, and not by their content. Every neighbor with the same degree contributes equally, regardless of whether it is relevant or noise. The GAT, introduced by Veličković and collaborators, replaces this fixed weight with a learned weight that depends on the features of both vertices. This is an attention mechanism from the same conceptual family used in Transformers, but it is applied to the graph neighborhood through an additive function rather than scaled dot-product attention.

The idea is to calculate, for every edge $(i, j)$, an attention coefficient $\alpha_{ij}$ that says how much vertex $i$ should listen to vertex $j$. We keep the convention from the previous sections in which each $h_i$ is a row vector, and project the features with a weight matrix $W$, obtaining $z_i = h_i W$. To include the vertex itself, we define $\tilde{\mathcal{N}}(i) = \mathcal{N}(i) \cup {i}$. We then compute an unnormalized score for every pair $(i, j)$ with $j \in \tilde{\mathcal{N}}(i)$:

in which $[z_i \Vert z_j]$ is the concatenation of the two projected vectors, $\mathbf{a}$ is a learned attention vector, and LeakyReLU, or leaky rectified linear unit, is $\operatorname{LeakyReLU}(x) = x$ when $x \ge 0$ and $\gamma x$ with negative slope $\gamma = 0.2$ otherwise. The transpose in $\mathbf{a}^\top[z_i\Vert z_j]$ is essential: it turns the concatenated vector into the scalar that LeakyReLU receives. The scores are then normalized by a softmax over the neighborhood so that the weights for each vertex sum to $1$:

Finally, the new representation of $i$ is the attention-weighted sum of the projected neighbors, followed by a nonlinearity:

It is worth seeing a number. Consider vertex $v_1$ in the cycle graph, with neighbors $v_2$ and $v_4$ in addition to itself, using the features $H^{(0)}$ and the matrix $W^{(0)}$ from Section 7. Choose the attention vector $\mathbf{a} = [1.0,\ 0.5,\ 1.0,\ 0.5]^\top$. The projections $z_i = h_i W$ for the three vertices involved are $z_1 = [0.55,\ 0.50]$, $z_2 = [0.42,\ 0.32]$, and $z_4 = [0.31,\ 0.22]$. The scores before softmax are $e_{11} = 1.60$, $e_{12} = 1.38$, and $e_{14} = 1.22$, and softmax transforms them into the weights

which sum to $1$, as they should. Based on content, vertex $v_1$ has decided to pay more attention to itself than to its neighbors, and more attention to neighbor $v_2$ than to $v_4$, a distinction the degree-bound GCN could never make because all degrees are equal. The resulting representation before activation is $h_1’ = [0.4420,\ 0.3649]$. In practice, a GAT uses several attention heads in parallel and concatenates or averages their outputs to stabilize learning, as Transformer architectures also do.

9.1 Solved exercises

Exercise 9.1. Reproduce the attention weights. Apply softmax to the scores $(1.60,1.38,1.22)$.

Solution. Subtracting the maximum for numerical stability gives $(0,-0.22,-0.38)$. Therefore

Subtracting a common constant changes neither numerator-to-denominator ratios nor the final probabilities.

Exercise 9.2. Make attention uniform. If all three scores for a vertex equal $4$, what are the attention coefficients?

Solution. Every numerator is $e^4$, and the denominator is $3e^4$, so each coefficient is $1/3$. Learned attention can reproduce an unweighted mean when the content scores provide no distinction.

Exercise 9.3. Apply the leaky branch. With negative slope $\gamma=0.2$, what score leaves LeakyReLU when $\mathbf{a}^\top[z_i\Vert z_j]=-0.5$?

Solution. The input is negative, so the output is $0.2(-0.5)=-0.1$. The negative score is reduced rather than discarded. A standard ReLU would map it to zero and would make all negative raw scores indistinguishable before softmax.

Exercise 9.4. Verify neighbor-order invariance. What happens to $h_i’$ if an adjacency list presents neighbors in a different order?

Solution. The same score is computed for each pair $(i,j)$, and the softmax denominator is a sum over the same set. Reordering only reorders matching pairs $(\alpha_{ij},z_j)$. Their weighted sum is unchanged. Attention depends on neighbor content, not on the storage position of that neighbor.

Exercise 9.5. Determine a multi-head shape. Eight attention heads each produce $16$ features per vertex. What is the output width if the heads are concatenated? What is it if they are averaged?

Solution. Concatenation produces $8\cdot16=128$ features. Averaging combines corresponding coordinates and retains width $16$. GAT commonly concatenates intermediate heads to increase capacity and averages final heads when all must represent the same class logits.

10. GraphSAGE: sample and aggregate

In matrix form and full-batch training, GCN and GAT may require a large portion of the graph to participate in every update, which is impractical when the graph contains billions of vertices. This does not make the architectures inherently dependent on the whole graph or necessarily transductive; GAT itself can also operate in inductive settings. GraphSAGE, introduced by Hamilton, Ying, and Leskovec, takes its name from SAmple and aggreGatE and makes two useful choices for scale and generalization explicit.

The first choice is sampling: instead of aggregating all neighbors of a vertex, GraphSAGE samples a fixed number at every layer, perhaps $25$ neighbors, even if the vertex has millions. For fixed depth and a fixed number of samples per layer, this makes the cost independent of the original degree of the vertex and enables mini-batch training on enormous graphs. The total number of visited vertices still grows with the product of the sample counts across layers. The second choice is an explicit separation between the vertex’s own representation and the aggregated representation. Keeping vectors as rows, one GraphSAGE layer with a mean aggregator computes:

in which $\mathcal{S}(i)$ is the sampled set of neighbors, and $W_{\text{self}}$ and $W_{\text{neigh}}$ are two distinct weight matrices: one for what the vertex already knows, and another for what the neighborhood brings. Keeping the two weights separate gives the network freedom to treat its own information and its neighbors’ information differently, which a GCN, where everything is summed using the same $W$, does not allow.

A number makes the formula concrete. For vertex $v_1$, with neighbors $v_2$ and $v_4$, the mean of the neighbor features is $\operatorname{mean}{[0.8, 0.2], [0.6, 0.1]} = [0.70,\ 0.15]$. Using $W_{\text{self}} = W^{(0)}$ from Section 7 and $W_{\text{neigh}} = \begin{bmatrix} 0.2 & 0.6 \ 0.7 & 0.1 \end{bmatrix}$, the representation before activation is $h_1’ = h_1 W_{\text{self}} + [0.70, 0.15] W_{\text{neigh}} = [0.795,\ 0.935]$. This two-matrix expression is equivalent to concatenating the self-vector and neighbor mean and multiplying by one block matrix. The mean aggregator is only one option. GraphSAGE also supports a pooling aggregator that transforms every neighbor and then takes the element-wise maximum. This operation is permutation invariant, as required by Section 4. The ability to generalize to vertices never seen during training, called inductive inference, makes GraphSAGE a common choice for production graphs that grow continuously.

10.1 Solved exercises

Exercise 10.1. Count a sampled computation tree. A two-layer GraphSAGE model samples $25$ neighbors in the first expansion and $10$ for each vertex in the second. Ignoring duplicated vertices, how many vertices are needed for one target?

Solution. We need the target itself, $25$ first-hop vertices, and at most $25\cdot10=250$ second-hop vertices:

Without sampling, one high-degree target could require millions of first-hop vertices. With sampling, the bound is controlled, although duplicates and shared neighbors usually reduce the number of distinct vertices below $276$.

Exercise 10.2. Compare a sample with the full mean. For $v_1$, the full neighbor mean is $[0.70,0.15]$. What mean results if the one-element sample contains only $v_2$?

Solution. A mean over one vector is that vector itself, so the sample estimate is $[0.8,0.2]$. The error relative to the full mean is $[0.1,0.05]$. Sampling reduces work by accepting variance in the aggregated message.

Exercise 10.3. Check unbiasedness. If we sample either $v_2$ or $v_4$ uniformly, one at a time, what is the expected sampled mean?

Solution.

The one-neighbor estimator is unbiased under uniform sampling, even though each realization differs from the full mean. Nonuniform samplers require importance weights if we want the same expectation.

Exercise 10.4. Count GraphSAGE weights. Let $F_l=64$ and $F_{l+1}=32$. How many weights are in $W_{\text{self}}$ and $W_{\text{neigh}}$ together?

Solution. Each matrix contains $64\cdot32=2{,}048$ weights, for a total of $4{,}096$. Equivalently, concatenating two 64-dimensional vectors gives width $128$, and a $128\times32$ block matrix also contains $4{,}096$ entries.

Exercise 10.5. Test inductive generalization. A new vertex arrives with features and edges to existing vertices. What does GraphSAGE need in order to represent it?

Solution. It needs the new feature vector, sampled neighbor features or representations, and the already learned aggregation weights. It does not need a trainable embedding tied to the new vertex identifier. If the model used only identifier embeddings and no transferable features, calling it inductive would not magically create information for the unseen identifier.

11. Training: from representations to tasks

A GNN does not exist to produce beautiful $H^{(L)}$ matrices; it exists to solve tasks, and the task determines what we place on top of the network. Three families cover almost everything.

In vertex classification, such as distinguishing a legitimate user from a spammer or classifying a scientific paper by field, we apply a final layer with softmax to the representation of every vertex, $\text{softmax}(H^{(L)} W_{\text{class}})$, obtaining one probability distribution over classes for each vertex. In graph classification, such as determining whether a molecule is toxic, we need a single vector for the entire graph. We obtain it through a global pooling operation that aggregates the representations of all vertices, usually by sum or mean, while respecting the permutation invariance discussed in Section 4; a classifier is then applied to this vector. In edge prediction, such as suggesting friendships or recommending products, we score a pair of vertices by the similarity of their representations, for example $\text{score}(h_i, h_j) = h_i^\top h_j$, and use a threshold to decide whether the edge should exist.

The training loop is the familiar neural network loop. Graph structure determines the dependencies in the forward pass and, consequently, the path followed by gradients during backpropagation. We propagate data through the stack of GNN layers to obtain representations and predictions; calculate a loss function by comparing predictions with true labels, usually cross-entropy for classification; obtain the gradients of the loss with respect to all weights $W^{(l)}$ through backpropagation; update the weights with an optimizer such as Adam or SGD, or stochastic gradient descent; and repeat until convergence. The adjusted parameters include the layer and classifier weight matrices and, in a GAT, the attention vectors. Graph structure remains fixed input data, not a parameter.

For $C$ classes and a logit vector $s_i\in\mathbb{R}^C$, softmax defines

If the true class of labeled vertex $i$ is $y_i$, its cross-entropy loss is $-\log p_{i,y_i}$. In semi-supervised vertex classification, we sum or average this loss only over labeled training vertices, even though message passing may use features from unlabeled vertices. This is one reason a GCN can learn useful representations when labels are scarce: structure participates in the forward computation without pretending that an unlabeled vertex has a target.

Evaluation requires more care than the formula suggests. Training, validation, and test labels must be separated. For edge prediction, test edges must also be hidden from the message-passing graph when their presence would reveal the answer. Negative edges should be sampled under a stated rule, and temporal applications should split by time rather than allow the model to train on the future. A spectacular accuracy obtained after structural leakage is merely a fast way to grade the answer key.

11.1 Solved exercises

Exercise 11.1. Compute a classification loss. A vertex has logits $(2,1,0)$ for classes numbered $0$, $1$, and $2$, and its true class is $0$. Find the softmax probabilities and cross-entropy loss.

Solution. Subtracting the maximum gives $(0,-1,-2)$. The probabilities are

The true class is the first coordinate, so the loss is

Exercise 11.2. Compare graph pooling. Three vertex representations are $[1,0]$, $[0,1]$, and $[1,1]$. Compute sum and mean pooling.

Solution.

Both are permutation invariant. Sum pooling retains graph size when features have comparable scale; mean pooling normalizes it away. The appropriate choice depends on whether size carries signal for the task.

Exercise 11.3. Score candidate edges. Let $h_1=[1,0]$, $h_2=[1,1]$, and $h_3=[0,1]$. Compare the dot-product scores for edges $(1,2)$ and $(1,3)$.

Solution.

The model ranks $(1,2)$ above $(1,3)$. A dot product has no trainable parameters and favors aligned vectors; a learned edge decoder can represent more complex relationships but introduces additional parameters and leakage risks.

Exercise 11.4. Compute a binary edge loss. A positive edge receives probability $0.8$, and a sampled negative edge receives probability $0.1$. What is their mean binary cross-entropy?

Solution.

The positive term rewards a high edge probability, while the negative term rewards a low one. Changing how negatives are sampled changes the learning problem, so the sampling rule belongs in the methodology.

Exercise 11.5. Find structural leakage. We randomly hold out $10\%$ of edges as test positives but leave them inside the adjacency matrix used by the GNN. What is wrong?

Solution. The forward pass can directly aggregate across an edge whose existence it is supposed to predict. The test label has leaked into the input structure. The held-out positive edges must be removed from the training message-passing graph, while preserving whatever connectivity the evaluation protocol explicitly permits. In a temporal graph, the safer split trains on earlier edges and tests on later ones.

12. The inconvenient limit: over-smoothing

We close with the problem that blocks the naive solution of “just stack more layers.” We saw in Section 5 that $l$ layers give every vertex access to its radius-$l$ neighborhood. It would be natural to assume that very deep networks, with dozens of layers, would capture rich structures. In many diffusion-based GNNs, however, successive layers make vertex representations increasingly similar. This phenomenon is over-smoothing: the network gradually loses its ability to distinguish one vertex from another.

The cause is the same operation that makes the GCN elegant. Every layer replaces a vertex representation with a weighted mean of its neighborhood. Repeatedly applying a mean is a diffusion process, and diffusion naturally homogenizes. Repeated often enough, it drives everything toward the same equilibrium value. In our cycle graph, this is visible and measurable. Define the spread of a feature as the difference between its maximum and minimum values across the four vertices, and apply $\hat{A}$ repeatedly. The spread of the first feature evolves as follows:

At every layer, the spread shrinks by a factor of exactly $3$ for this signal and this regular graph. After six layers, the first-feature spread is approximately $0.000960$, and the four vertices have become practically indistinguishable. Their representations converge to the global mean $[0.675,\ 0.375]$. This happens because the signal that is constant across all four vertices is the dominant eigenvector of $\hat{A}$, with eigenvalue $1$; the nonconstant components have eigenvalue magnitude $1/3$ and therefore lose two thirds of their amplitude per propagation. The deep network can barely distinguish local structure anymore. It sees a uniform soup.

The following lab makes the collapse visible. The reader can stack layers one by one and watch the four points, initially scattered, converge to a single point. I suggest pushing the control to ten layers to see the complete disaster, then noticing that the damage is already nearly complete by the fifth.

Known solutions attack diffusion without abandoning it. Residual connections, also called skip connections, add the input of a layer to its output, preserving a trace of the original representation that averaging cannot erase. This is the same idea that made it possible to train convolutional networks with hundreds of layers. Normalization layers designed for graphs can preserve the spread of representations at every step. The GAT from Section 9 may also mitigate the problem when attention learns to reduce the influence of certain neighbors. None of these strategies guarantees the elimination of over-smoothing; they only push the depth limit a little farther away.

12.1 Solved exercises

Exercise 12.1. Continue the spread sequence. What is the first-feature spread after three applications of $\hat A$?

Solution. The initial spread is $0.7$, and each application divides it by $3$, so

This agrees with the fourth entry of the displayed sequence when the initial state is called layer $0$.

Exercise 12.2. Find the collapse depth. What is the smallest $l$ for which $0.7/3^l<0.001$?

Solution. We need $3^l>700$. Since $3^5=243$ and $3^6=729$, the smallest depth is $l=6$. The spread is then $0.7/729\approx0.000960$, just below the threshold.

Exercise 12.3. Compute the limiting vector. Find the mean of the four input rows in $H^{(0)}$.

Solution.

Because the four-cycle with self-loops is regular and $\hat A$ is doubly stochastic, repeated propagation preserves this mean and removes the nonconstant components.

Exercise 12.4. Add an initial residual. Consider

Compare the first-feature spread after five layers with pure propagation.

Solution. Direct iteration gives a residual spread of approximately $0.191596$ after five layers. Pure propagation gives $0.7/3^5\approx0.002881$. Injecting $20\%$ of the initial representation at every layer prevents convergence to a uniform vector in this example, although it changes the operator and does not solve every deep-GNN problem.

Exercise 12.5. Separate over-smoothing from overfitting. Training accuracy and validation accuracy are both poor in a 32-layer GCN, and vertex embeddings have almost identical pairwise values. Which diagnosis is supported?

Solution. The near-identical embeddings support over-smoothing. Overfitting would usually produce low training error and worse validation error because the model memorized training peculiarities. Both phenomena can coexist, but representation collapse is direct evidence for over-smoothing and should be measured rather than inferred from depth alone.

13. Three limits that depth alone cannot fix

Over-smoothing is only one reason a message-passing GNN may fail. We should separate it from heterophily, limited expressive power, and over-squashing, because the same intervention does not repair all four.

The GCN has a strong smoothing bias. That bias is useful under homophily, the tendency of adjacent vertices to have similar features or labels. For a labeled undirected graph, one simple edge homophily ratio is

A value near $1$ means most connected labels agree. Under heterophily, adjacent vertices systematically differ, as buyers connect to sellers or users connect to items. Averaging one-hop neighbors may then erase the very distinction needed by the classifier. Architectures can respond by keeping self and neighbor channels separate, using signed or relation-aware messages, or combining information from different hop distances. GraphSAGE already showed the first design in Section 10.

The second limit concerns what aggregation can distinguish. A message-passing GNN repeatedly maps multisets of neighbor representations to vectors. If that mapping is not injective, different multisets collapse to the same value, as the mean did in Exercise 4.4. More generally, standard message-passing GNNs cannot distinguish every pair of nonisomorphic graphs. Their classical ceiling is connected to the one-dimensional Weisfeiler-Lehman, or 1-WL, graph isomorphism test. The Graph Isomorphism Network, or GIN, uses an injective sum-based construction and reaches that ceiling under stated conditions, but even 1-WL fails on some regular graphs. More layers repeat the same indistinguishable update; they do not manufacture missing expressive power.

The third limit is over-squashing. The radius-$l$ neighborhood can grow exponentially with $l$, while every layer compresses all incoming information into a fixed-width vector. A distant signal may have to cross a narrow cut in the graph and compete with exponentially many other messages. The result can be poor long-range sensitivity even when vertex representations have not become equal. Rewiring, positional or structural encodings, attention, larger hidden states, and architectures with global communication can help, but each changes a different part of the bottleneck.

We now have a useful diagnostic. Similar embeddings everywhere suggest over-smoothing. Poor performance when connected labels differ suggests that a homophilic smoothing bias is wrong for the data. Failure to distinguish structurally different but locally identical graphs suggests an expressivity limit. Failure to transmit a distant dependency through a narrow region suggests over-squashing. Calling every deep-GNN failure “over-smoothing” is convenient, concise, and often wrong.

13.1 Solved exercises

Exercise 13.1. Compute edge homophily. A labeled undirected graph has five edges, three joining equal labels and two joining different labels. What is $h_E$?

Solution.

The value says that $60\%$ of observed edges are homophilic under this label definition. It does not by itself prove that a GCN will succeed, because feature quality, class imbalance, split design, and where the heterophilic edges occur also matter.

Exercise 13.2. Diagnose a bipartite graph. Every edge joins a class-$0$ vertex to a class-$1$ vertex. What are the one-hop and two-hop label patterns?

Solution. Edge homophily is $0$. Every one-hop neighbor has the opposite label, so a one-hop mean pushes a vertex toward the other class. Every two-hop neighbor returns to the original side of the bipartition and therefore has the same label. Separating hop distances can expose a useful two-hop signal that indiscriminate smoothing would mix away.

Exercise 13.3. Find a 1-WL ambiguity. Compare a six-cycle with two disconnected triangles. All six vertices begin with the same feature. What does a standard message-passing layer see?

Solution. Every vertex in both graphs has degree $2$ and receives the same multiset, two copies of the common feature. By induction, every layer assigns the same representation to every vertex in both graphs. Because each graph has six vertices, sum pooling also produces the same graph vector. The graphs are not isomorphic, one is connected and the other is not, but this message-passing scheme cannot distinguish them.

Exercise 13.4. Quantify a growing neighborhood. A complete binary tree has depth $5$, with the root at depth $0$. How many leaves can influence the root after five layers, and how many vertices are in the receptive field?

Solution. The tree has $2^5=32$ leaves and

vertices in the radius-$5$ receptive field. All leaf information must be combined through two messages entering the root and compressed into its fixed-width representation. This is the structural bottleneck behind over-squashing.

Exercise 13.5. Distinguish two depth failures. In a deep tree GNN, vertex embeddings remain visibly different, but changing a distant leaf barely changes the root prediction. Is this evidence of over-smoothing or over-squashing?

Solution. It is evidence of over-squashing. The representations have not collapsed to a common value, so the defining symptom of over-smoothing is absent. The root is insensitive to distant information because many signals compete through a narrow route. Measuring gradients or output sensitivity from the root to distant leaves would test this diagnosis directly.

14. Conclusion

We have traveled from relational data to a network that learns from it. We saw that graphs formalize entities and relationships, that permutation symmetry constrains every valid architecture, and that message passing emerges from aggregation followed by update. We derived the GCN from both spatial and spectral viewpoints, calculated one layer by hand and in C++23, and saw the GAT replace fixed structural weights with learned attention while GraphSAGE bounded neighborhood work through sampling. We connected representations to training objectives and then separated over-smoothing, heterophily, limited expressivity, and over-squashing.

The sixty-five solved exercises turned definitions into calculations and calculations into design decisions. One idea runs through all of them and is worth carrying forward: in a GNN, information lies not only in the vertices but also in the pattern of connections; learning from a graph means propagating information through that structure without depending on how its vertices were numbered. Graph Transformers, heterogeneous GNNs, and dynamic graph networks alter how far, how selectively, and across which relation types information travels, but they remain accountable to that symmetry.

References

ALON, U.; YAHAV, E. On the Bottleneck of Graph Neural Networks and its Practical Implications. International Conference on Learning Representations (ICLR), 2021. Available at: https://arxiv.org/abs/2006.05205.

BRONSTEIN, M. M.; BRUNA, J.; COHEN, T.; VELIČKOVIĆ, P. Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. 2021. Available at: https://arxiv.org/abs/2104.13478.

DEFFERRARD, M.; BRESSON, X.; VANDERGHEYNST, P. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. Advances in Neural Information Processing Systems, v. 29, 2016. Available at: https://arxiv.org/abs/1606.09375.

GILMER, J.; SCHOENHOLZ, S. S.; RILEY, P. F.; VINYALS, O.; DAHL, G. E. Neural Message Passing for Quantum Chemistry. Proceedings of the 34th International Conference on Machine Learning, PMLR, v. 70, p. 1263–1272, 2017. Available at: https://arxiv.org/abs/1704.01212.

HAMILTON, W. L.; YING, R.; LESKOVEC, J. Inductive Representation Learning on Large Graphs. Advances in Neural Information Processing Systems, v. 30, 2017. Available at: https://arxiv.org/abs/1706.02216.

HE, K.; ZHANG, X.; REN, S.; SUN, J. Deep Residual Learning for Image Recognition. IEEE Conference on Computer Vision and Pattern Recognition, p. 770–778, 2016. Available at: https://arxiv.org/abs/1512.03385.

KINGMA, D. P.; BA, J. Adam: A Method for Stochastic Optimization. International Conference on Learning Representations (ICLR), 2015. Available at: https://arxiv.org/abs/1412.6980.

KIPF, T. N.; WELLING, M. Semi-Supervised Classification with Graph Convolutional Networks. International Conference on Learning Representations (ICLR), 2017. Available at: https://arxiv.org/abs/1609.02907.

LI, Q.; HAN, Z.; WU, X.-M. Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning. Proceedings of the AAAI Conference on Artificial Intelligence, v. 32, 2018. Available at: https://arxiv.org/abs/1801.07606.

SCARSELLI, F.; GORI, M.; TSOI, A. C.; HAGENBUCHNER, M.; MONFARDINI, G. E. The Graph Neural Network Model. IEEE Transactions on Neural Networks, v. 20, n. 1, p. 61–80, 2009. DOI: https://doi.org/10.1109/TNN.2008.2005605.

VELIČKOVIĆ, P.; CUCURULL, G.; CASANOVA, A.; ROMERO, A.; LIÒ, P.; BENGIO, Y. Graph Attention Networks. International Conference on Learning Representations (ICLR), 2018. Available at: https://arxiv.org/abs/1710.10903.

WEISFEILER, B.; LEMAN, A. A Reduction of a Graph to a Canonical Form and an Algebra Arising During This Reduction. Nauchno-Technicheskaya Informatsia, series 2, n. 9, p. 12–16, 1968.

XU, K.; HU, W.; LESKOVEC, J.; JEGELKA, S. How Powerful Are Graph Neural Networks?. International Conference on Learning Representations (ICLR), 2019. Available at: https://arxiv.org/abs/1810.00826.

ZHU, J.; YAN, Y.; ZHAO, L.; HEIMANN, M.; AKOGLU, L.; KOUTRA, D. Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs. Advances in Neural Information Processing Systems, v. 33, p. 7793–7804, 2020. Available at: https://proceedings.neurips.cc/paper/2020/hash/58ae23d878a47004366189884c2f8440-Abstract.html.