Graph Neural Networks: An Introduction

Artificial intelligence has learned to handle tabular, sequential, and grid data, but these three forms cover only a small fraction of the data that matters. Spreadsheets, text, and images are domesticated special cases of a much more general structure. 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 details placed on top of the data. They are the data. This article explores how a neural network learns when information lives in edges as much as it does in vertices.

“Networks are the prerequisite for describing any complex system, indicating that complexity theory must inevitably rest on the shoulders of network theory.” (Albert-László Barabási)

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 design principle, permutation invariance, 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 will reappear in all the interactive labs. We close with two architectures that address weaknesses in the GCN, the GAT, or Graph Attention Network, and GraphSAGE, as well as the problem of over-smoothing, which imposes an inconvenient limit on anyone who wants deep networks.

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.

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. It provides a cheap 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.

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 its role is enormous. It will provide the normalization factors that prevent highly connected vertices from dominating aggregation, as we will see in Section 6.

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.

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.

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.

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.

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.

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.

8. The same layer in C++

The calculation in Section 7 translates directly into code. The following C++23 implementation performs the six steps in the order in which we derived them and reproduces $H^{(1)}$ to three decimal places. We use no external library: the goal is to keep every operation in the formula visible, not to make it fast. Compile it with g++ -O3 -std=c++23 -o gcn gcn_layer.cpp.

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

using Matrix = std::vector<std::vector<double>>;

// Matrix product C = A * B, with A of shape m x k and B of shape k x n.
static Matrix matmul(const Matrix& A, const Matrix& B) {
    const std::size_t m = A.size(), k = B.size(), n = B[0].size();
    Matrix C(m, std::vector<double>(n, 0.0));
    for (std::size_t i = 0; i < m; ++i)
        for (std::size_t p = 0; p < k; ++p)
            for (std::size_t j = 0; j < n; ++j)
                C[i][j] += A[i][p] * B[p][j];
    return C;
}

// One GCN layer: sigma( D^{-1/2} A_tilde D^{-1/2} H W ), with A_tilde = A + I.
static Matrix gcn_layer(const Matrix& A, const Matrix& H, const Matrix& W) {
    const std::size_t N = A.size();

    // Step 1: A_tilde = A + I.
    Matrix At = A;
    for (std::size_t i = 0; i < N; ++i) At[i][i] += 1.0;

    // Steps 2 and 3: degrees with self-loops and D^{-1/2}.
    std::vector<double> dinv(N);
    for (std::size_t i = 0; i < N; ++i) {
        double d = 0.0;
        for (std::size_t j = 0; j < N; ++j) d += At[i][j];
        dinv[i] = 1.0 / std::sqrt(d);
    }

    // Step 3: A_hat = D^{-1/2} A_tilde D^{-1/2}.
    Matrix Ah(N, std::vector<double>(N, 0.0));
    for (std::size_t i = 0; i < N; ++i)
        for (std::size_t j = 0; j < N; ++j)
            Ah[i][j] = dinv[i] * At[i][j] * dinv[j];

    // Steps 4 and 5: propagation and linear transformation.
    Matrix out = matmul(matmul(Ah, H), W);

    // Step 6: ReLU activation.
    for (auto& row : out)
        for (double& x : row) x = std::max(0.0, x);
    return out;
}

static void print_matrix(std::string_view name, const Matrix& M) {
    std::cout << name << " =\n" << std::fixed << std::setprecision(3);
    for (const auto& row : M) {
        for (double x : row) std::cout << std::setw(8) << x;
        std::cout << '\n';
    }
    std::cout << '\n';
}

int main() {
    Matrix A = { {0, 1, 0, 1}, {1, 0, 1, 0},
                 {0, 1, 0, 1}, {1, 0, 1, 0} };
    Matrix H = { {1.0, 0.5}, {0.8, 0.2},
                 {0.3, 0.7}, {0.6, 0.1} };
    Matrix W = { {0.5, 0.3}, {0.1, 0.4} };

    Matrix H1 = gcn_layer(A, H, W);
    print_matrix("H^(1)", H1);
    return 0;
}

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 is a cheap way to confirm that the multiplication order, first $\hat{A}H$ and then $\cdot\, W$, was respected and that normalization did not swap rows and columns. Stacking layers means chaining calls to gcn_layer, feeding the output of one call as the $H$ input to the next, with a new $W$ matrix for every layer.

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 another learned attention weight vector, and LeakyReLU, or leaky rectified linear unit, is $\text{LeakyReLU}(x) = x$ when $x \ge 0$ and $\alpha x$ with $\alpha = 0{,}2$ otherwise. 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.

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 $\text{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]$. The mean aggregator is only one of several options. 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.

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.

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 approximately $3$. After six layers, the four vertices, which began clearly distinct, have become practically indistinguishable, and 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 global mean supplies the two coefficients of this limiting signal, one for each feature. 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.

13. Conclusion

We have traveled from relational data to a network that learns from it. We saw that graphs are the structure that formalizes “things connected to things,” that permutation invariance is the principle that forces any graph architecture to aggregate neighbors with functions that are blind to order, and that message passing, composed of aggregation and update, is the resulting mechanism. We derived the GCN symbol by symbol, calculated one of its layers by hand and in C++, and saw the GAT replace fixed weights with learned attention while GraphSAGE replaced the entire graph with sampled neighborhoods. We closed with over-smoothing, a reminder that the operation that gives the GCN its power is also what limits its depth.

One idea runs through all of this 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 learning to propagate information through its structure without ever depending on how its vertices were numbered. The advanced architectures the reader will encounter next, such as Graph Transformers, heterogeneous GNNs, and networks over dynamic graphs, are all variations on this same theme.

References

BARABÁSI, Albert-László. Linked: a nova ciência dos networks: como tudo está conectado a tudo e o que isso significa para os negócios, relações sociais e ciências. Translated by Jonas Pereira dos Santos. São Paulo: Leopardo, 2009.

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.

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.

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.

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.